Lilac 0.1.0.0 / compile.org

Compile

1 Overview

Compilation is the intermediate step we perform on Org files, such that they can be tangled or woven. Org documents cannot be tangled or woven directly; instead they must first be compiled into objects, and then collected into an archive. We perform additional checks during each step so that we can tangle and weave reliably.

We use JSON as the underlying format because it's easy to debug and is widely supported. In the future we could use another format for scalability or performance reasons, but JSON is good enough for now.

2 Lilac.Compile module

🔗
module:Lilac.Compile
🎯 src/Lilac/Compile.hs
module Lilac.Compile
  ( cumulativeOffsets,
    findCycles,
    findExternalOids,
    gciToName,
    makeRelativeToObjectPath,
    mkArchive,
    mkGTOC,
    mkObject,
    parseCitationStyle,
    readObjectsFrom,
  )
where

import Citeproc qualified as CP
import Citeproc.CslJson (CslJson)
import Data.Aeson (eitherDecodeStrictText)
import Data.Graph qualified as G
import Data.IntMap.Strict (IntMap)
import Data.IntMap.Strict qualified as IntMap
import Data.List (partition)
import Data.Map.Strict qualified as M
import Data.Set qualified as Set
import Data.Text qualified as T
import Data.Tree
  ( Tree (Node),
    unfoldTreeM,
  )
import Lilac.Parse qualified as LP
import Lilac.Types
  ( Archive
      ( Archive,
        ancestry,
        backlinks,
        bibs,
        csls,
        glossary,
        gtoc,
        objects,
        offsets,
        symbols
      ),
    BToken (BTokenLinkTarget, BTokenPadding, BTokenString),
    Block (body, meta, parentOid),
    Cell
      ( CBlock,
        CCommand,
        CFigure,
        CFootnote,
        CGlossaryTerm,
        CHeading,
        CListItem,
        CMathFragment,
        CParagraph,
        CTable
      ),
    Figure (caption, link, meta, parentOid),
    Footnote (body, name),
    GCI (GCI, unGCI),
    GPath,
    GTOC (GTOC),
    GlossaryTerm (definition, term),
    Heading (body, meta),
    LCI (LCI, unLCI),
    Link (Link, target),
    LinkOid (LinkOid, name, oid),
    LinkTarget
      ( LinkTargetFilePath,
        LinkTargetFootnote,
        LinkTargetLineLabel,
        LinkTargetOid,
        LinkTargetURI
      ),
    MathFragment (meta, parentOid),
    OID,
    Object (Object, externalOids, orgDoc, symbols),
    OrgDoc (bibPaths, cells, cslPath, glossary, oid, pseudoEdges),
    PToken
      ( PTokenCitation,
        PTokenDivEnd,
        PTokenDivStart,
        PTokenLink,
        PTokenMathFragment,
        PTokenStyledText
      ),
    ProjectConf (bibliography, citationStyle),
    Prose (Prose, unProse),
    PseudoEdge (PseudoEdge),
    Style (Verbatim),
    Table (caption, grid, meta, parentOid),
    decodeGPath,
    emptyGPath,
    encodeGPath,
    gciToObjCell,
    getProseContents,
    getSectionNumber,
    ptext,
    stripLinks,
  )
import Lilac.Util qualified as LU
import Relude
  ( Bool,
    Either (Left, Right),
    FilePath,
    IO,
    Int,
    Map,
    Maybe (Just, Nothing),
    State,
    String,
    Text,
    Type,
    abs,
    catMaybes,
    concat,
    concatMap,
    elem,
    filter,
    fmap,
    foldl',
    foldlM,
    fromList,
    fst,
    get,
    hashNub,
    intercalate,
    length,
    map,
    mapAccumL,
    mapM,
    mapMaybe,
    maybeToList,
    mempty,
    modify,
    not,
    null,
    otherwise,
    pure,
    repeat,
    runState,
    show,
    snd,
    sort,
    unlines,
    when,
    zip,
    (!!?),
    ($),
    (+),
    (-),
    (.),
    (/=),
    (<),
    (<$>),
    (<>),
    (=<<),
    (==),
    (>),
  )
import Relude.Extra.Map (elems, insert, insertWith, lookup, member)
import System.Directory.OsPath qualified as D
import System.Exit (die)
import System.FilePath (splitDirectories)
import System.OsPath qualified as P

f:mkObject
f:mkSymbols
f:getLineLabels
f:getSymbols
f:mkArchive
f:combineSymbolsAndGlossary
f:docOidsToSymbols
f:mkOffsets
f:prependOffsets
f:findBrokenLinks
f:findBrokenFileLinks
f:getCitationDeps
f:finalizeEdges
f:mkBacklinks
f:readObjectsFrom
f:buildGraph
f:getBlocksFromArchive
f:getBlockGCIsFromArchive
f:mkBlockAncestry
f:findCycles
f:cumulativeOffsets
f:findExternalOids
data:PathState
f:mkGTOC
f:findRootIndex
f:isIndexObjPath
f:getChildPaths
f:getCitationStyles
f:getCitationStyle
f:parseCitationStyle
f:getBibliographies
f:getBibliography
f:parseBibliography
f:makeRelativeToObjectPath
f:gciToName

3 Objects

The data:Object augments the data:OrgDoc with some additional metadata (derived from the OrgDoc).

🔗
data:Object ⇪
type Object :: Type
data Object = Object
  { orgDoc :: OrgDoc,
    symbols :: Map LinkOid LCI, -- 1
    externalOids :: [LinkOid] -- 2
  }
  deriving stock (Eq, Ord, Generic, Show)
  deriving anyclass (FromJSON, ToJSON)

The externalOids 2 lists all OID link targets which cannot be resolved by the symbols in this document. The expectation is that these external OIDs will be found in the data:Archive from other objects that have them.

The symbols 1 houses all links that point to cells inside the current OrgDoc. We use data:LinkOid as a key for convenience, and for this we need to define at least a ToJSONKey instance and FromJSONKey instance. Otherwise, Data.Aeson can give an unrelated error message like

🔗
Error in $.symbols: parsing Map failed, expected Array, but encountered Object

when trying to parse the JSON for symbols ("symbols":{}), such that "symbols":[] won't give an error (strange!).

3.1 JSON conversion

Marshaling to JSON is straightforward, because we can just reuse the instance:Show LinkOid, which already knows how to convert a LinkOid to a String value.

Unmarshaling is tricky because we have to inform Data.Aeson how to convert a Text to LinkOid. This is what we do in f:parseJSONLinkOid.

🔗
f:parseJSONLinkOid ⇪
parseJSONLinkOid :: Text -> Parser LinkOid
parseJSONLinkOid t = do
  oidAndNameText <- maybe (fail "invalid LinkOid") pure (T.stripPrefix "id:" t)
  let oidText = T.take 36 oidAndNameText
      maybeNameText = T.drop 36 oidAndNameText
      name =
        if T.length maybeNameText > 2
          then T.drop 2 maybeNameText
          else ""
  case Lilac.Types.fromText oidText of
    Nothing -> fail "invalid LinkOid"
    Just oid -> pure $ LinkOid oid name

This function is not very strict (it only implicitly checks for the :: separator between the UUID and the name (if any)), because it's good enough.

Now we're ready to define the boilerplate for doing the round trip to and back from JSON. The instance:ToJSON LinkOid converts the LinkOid to a JSON Value type (one of the constructors being a JSON string, or Data.Aeson.Types.String).

🔗
instance:ToJSON LinkOid ⇪
instance ToJSON LinkOid where
  toJSON linkOid = Data.Aeson.Types.String (T.show linkOid)

The instance:ToJSONKey LinkOid is simpler, because it just expects a type that can be a key. The use of toJSONKeyText (from Data.Aeson.Types) is important because it results in encoding the surrounding map as a JSON object {...} instead of an array of key-value pairs [...] (see the upstream docs here).

🔗
instance:ToJSONKey LinkOid ⇪
instance ToJSONKey LinkOid where
  toJSONKey = toJSONKeyText show

The instances for both FromJSON and FromJSONKey rely on the f:parseJSONLinkOid we defined above.

🔗
instance:FromJSON LinkOid ⇪
instance FromJSON LinkOid where
  parseJSON = withText "LinkOid" parseJSONLinkOid
🔗
instance:FromJSONKey LinkOid ⇪
instance FromJSONKey LinkOid where
  fromJSONKey = FromJSONKeyTextParser parseJSONLinkOid

3.2 Construction

f:mkObject creates an object out of a single data:OrgDoc.

🔗
f:mkObject ⇑
mkObject :: OrgDoc -> Object
mkObject orgDoc =
  Object
    { orgDoc = orgDoc,
      symbols = mkSymbols orgDoc, -- 3
      externalOids = findExternalOids orgDoc -- 4
    }

f:mkSymbols 3 and f:findExternalOids 4 are discussed separately below.

3.2.1 Symbols

f:mkSymbols 3 generates a mapping of all data:LinkOid keys to their local cell index values 5 (also known as the newtype:LCI values). This represents the locations (cell indices) of where these symbols can be found.

🔗
f:mkSymbols ⇑
mkSymbols :: OrgDoc -> Map LinkOid LCI
mkSymbols orgDoc =
  fromList
    . concatMap f
    $ zip
      (map LCI [0 ..]) -- 5
      orgDoc.cells
  where
    f (lci, cell) = case cell of -- 6
      CHeading heading
        | Just oidText <- lookup "ID" heading.meta,
          Just oid <- LP.validateOidText oidText ->
            [ ( LinkOid
                  { oid = oid,
                    name = T.empty
                  },
                lci
              )
            ]
        | otherwise -> []
      CBlock block ->
        ( getSymbols
            orgDoc.oid
            block.parentOid
            block.meta
            lci
        )
          <> (getLineLabels orgDoc.oid block.parentOid lci block) -- 7
      CFigure figure ->
        getSymbols
          orgDoc.oid
          figure.parentOid
          figure.meta
          lci
      CMathFragment mathFragment ->
        getSymbols
          orgDoc.oid
          mathFragment.parentOid
          mathFragment.meta
          lci
      CTable table ->
        getSymbols
          orgDoc.oid
          table.parentOid
          table.meta
          lci
      CFootnote {}
      CListItem {}
      CParagraph {}
      CGlossaryTerm {}
      CCommand {} -> [] -- 8

f:getLineLabels 7 associates a link to a line label with the code block cell that contains that line label. We use this information in f:weaveLink to look up the containing code block's name when the line label is contained in an external doc (because the name of the code block gives additional context).

🔗
f:getLineLabels ⇑
getLineLabels :: OID -> OID -> LCI -> Block -> [(LinkOid, LCI)]
getLineLabels docOid parentOid lci block = foldl' f [] block.body
  where
    f acc bToken = case bToken of
      (BTokenLinkTarget (LinkTargetLineLabel linkOid)) ->
        (LinkOid docOid linkOid.name, lci)
          : (LinkOid parentOid linkOid.name, lci)
          : acc
      _ -> acc

Only headings, blocks, figures, math fragments, and tables can be linked to using a LinkOid. The other cell types are ignored 8.

We call the cell index the lci 6 for local cell index to differentiate it against the global cell index, which is used when handling archives, such as in f:gciToObjCell.

The f:getSymbols helper generates either one or two symbols for the same cell; these correspond to whether we use one OID (document OID) or two OIDs (document OID or the closest parent heading's OID) 9.

🔗
f:getSymbols ⇑
getSymbols :: OID -> OID -> Map Text Text -> LCI -> [(LinkOid, LCI)]
getSymbols docOid parentOid cellMeta lci =
  let oids =
        if parentOid /= docOid -- 9
          then [parentOid, docOid]
          else [docOid]
   in mapMaybe extractName oids
  where
    extractName oid -- 10
      | Just name <- lookup "name" cellMeta =
          Just
            ( LinkOid
                { oid = oid,
                  name = name
                },
              lci
            )
      | Just tanglePath <- lookup "tangle" cellMeta -- 11
        =
          Just
            ( LinkOid
                { oid = oid,
                  name = tanglePath <> "\NUL"
                },
              lci
            )
      | Just anonBlockNumber <- lookup "__anon_block_number" cellMeta -- 12
        =
          Just
            ( LinkOid
                { oid = oid,
                  name = anonBlockNumber <> "\NUL__anon_block_number"
                },
              lci
            )
      | otherwise = Nothing

The extractName function 10 tries to get some semblance of a name from the cell. Other than the name metadata, the tangle path 11 and the internal names of anonymous blocks 12 are used. We need 11 because some root blocks (that need to be tangled in f:expandRootBlocks) may be anonymous. Unless we include anonymous blocks as a symbol for these cases, they will be skipped over. And we need 12 because we need them for navigating a block's ancestry; specifically, a block may have an anonymous parent, and we still want to include such parents in f:getBlockGCIsFromArchive, which powers f:mkBlockAncestry.

Note that f:mkSymbols needs to return a Map LinkOid LCI. Because both 11 and 12 deal with anonymous blocks, their LinkOid values are constructed artificially. For both of them we inject a \NUL character so as to make it impossible to clash with a user-defined LinkOid (no sane user or text editor will let users mix in \NUL characters with other text). Avoiding clashes is important because the keys of a Map must be unique to avoid overwriting each other's values.

3.2.2 External OIDs

f:findExternalOids 4 looks for LinkTargetOid links that point to cells that are not inside the current Org file. We just look at all links and see if any of them point to an OID that is not accounted for in the symbols 16.

🔗
f:findExternalOids ⇑
findExternalOids :: OrgDoc -> [LinkOid]
findExternalOids orgDoc =
  sort
    . Set.toList
    . fromList
    $ concatMap searchInsideProse orgDoc.cells
  where
    searchInsideProse cell = case cell of -- 13
      CBlock block -> foldl' getLinkFromBToken [] block.body
      CHeading heading -> foldl' getLinkFromPToken [] heading.body.unProse
      CParagraph prose -> foldl' getLinkFromPToken [] prose.unProse
      CGlossaryTerm glossaryTerm ->
        foldl' getLinkFromPToken [] glossaryTerm.definition.unProse
      CTable table ->
        foldl'
          (\acc prose -> foldl' getLinkFromPToken acc prose.unProse)
          []
          table.grid
      CFigure {}
      CFootnote {}
      CListItem {}
      CMathFragment {}
      CCommand {} -> []
    getLinkFromBToken acc bToken = case bToken of -- 14
      BTokenLinkTarget linkTarget -> keepIfExternal acc linkTarget
      BTokenString {}
      BTokenPadding -> acc
    getLinkFromPToken acc pToken = case pToken of -- 15
      PTokenLink link -> keepIfExternal acc link.target
      PTokenStyledText {}
      PTokenCitation {}
      PTokenMathFragment {}
      PTokenDivStart {}
      PTokenDivEnd {} -> acc
    symbols = mkSymbols orgDoc -- 16
    keepIfExternal acc linkTarget = case linkTarget of -- 17
      LinkTargetOid linkOid ->
        if member linkOid symbols
          then acc
          else linkOid : acc
      LinkTargetLineLabel linkOid ->
        if member linkOid symbols
          then acc
          else linkOid : acc
      LinkTargetFootnote {}
      LinkTargetFilePath {}
      LinkTargetURI {} -> acc

First we have to look at all areas where prose text can occur 13. The prose-like containers fall into two categories: data:BToken and data:PToken; these are handled by getLinkFromBToken 14 and getLinkFromPToken 15 respectively, which harvest the links out of them. Then we check if the link's target is external or not, only keeping it if it is external 17 (i.e., not found in symbols 16).

Although we call the helper keepIfExternal, internal links that point to OIDs within the document will still get treated as "external" if there is a typo in the name data:LinkOid → 75 part, because there won't be any local symbols for it. And then these links will get picked up as broken links in f:mkArchive.

Links to code blocks within the same document, whether explicitly defined with an OID or not, shouldn't result in external links.

🔗
ti:0400-no-external-symbols-code-blocks
🎯 test/Lilac/CompileSpec/0400-no-external-symbols-code-blocks
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000d000
:END:

#+name: c
#+begin_src haskell
c1
#+end_src

#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
  <<b>>
a1
  <<b>>
#+end_src

#+name: b
#+begin_src haskell
b1
b2
<<id:00000000-0000-0000-0000-00000000d000::c>>
b3
#+end_src
🔗
t:0400-no-external-symbols-code-blocks ↑
checkExternalLinkOids
  "0400-no-external-symbols-code-blocks"
  []

Here is a more complex example, with internal links inside headings and paragraphs as well.

🔗
ti:0400-no-external-symbols-complex
🎯 test/Lilac/CompileSpec/0400-no-external-symbols-complex
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000d001
:END:

* h1 [[t:foo]]

#+name: t:foo
#+begin_src haskell
foo
#+end_src

Link to [[bar
baz]] and [[bar baz][long
description]]. Same link: [[id:00000000-0000-0000-0000-00000000d001::bar
baz]]. Another link [[id:00000000-0000-0000-0000-00000000d001::t:foo][here]].

#+name: bar baz
#+begin_src haskell
foo
<<t:foo>>
<<id:00000000-0000-0000-0000-00000000d001::t:foo>>
#+end_src
🔗
t:0400-no-external-symbols-complex ↑
checkExternalLinkOids
  "0400-no-external-symbols-complex"
  []

Check for external links.

🔗
ti:0400-external-symbols
🎯 test/Lilac/CompileSpec/0400-external-symbols
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000d002
:END:

Hello [[id:ffffffff-0000-0000-0000-00000000d001::a]]
🔗
t:0400-external-symbols ↑
checkExternalLinkOids
  "0400-external-symbols"
  [ LinkOid
      { oid = fromWords 0xffffffff00000000 0x000000000000d001,
        name = "a"
      }
  ]

Here's a more complicated example with external links that break over multiple lines.

🔗
ti:0400-external-symbols-newlines
🎯 test/Lilac/CompileSpec/0400-external-symbols-newlines
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000d002
:END:

Hello [[id:ffffffff-0000-0000-0000-00000000d001::Hello
World]]. Another one: [[id:ffffffff-0000-0000-0000-00000000d001::a b c
d e][a b c d e]].
🔗
t:0400-external-symbols-newlines ↑
checkExternalLinkOids
  "0400-external-symbols-newlines"
  [ LinkOid
      { oid = fromWords 0xffffffff00000000 0x000000000000d001,
        name = "Hello World"
      },
    LinkOid
      { oid = fromWords 0xffffffff00000000 0x000000000000d001,
        name = "a b c d e"
      }
  ]

4 Archives

A data:Archive is a collection of data:Object values. The objects field 18 holds this collection, where the newtype:GPath is the key of where that object was found. We have to use GPath because there is no ToJSONKey instance for P.OsPath (which would otherwise have been our first choice).

🔗
data:Archive ⇪
type Archive :: Type
data Archive = Archive
  { objects :: Map GPath Object, -- 18
    symbols :: Map LinkOid GCI, -- 19
    ancestry :: Map GCI [GCI], -- 20
    glossary :: Map (Text, GPath) LCI, -- 21
    backlinks :: Map GPath (Map GPath [(GCI, GCI)]), -- 22
    offsets :: IntMap GPath, -- 23
    gtoc :: GTOC, -- 24
    csls :: Map FilePath Text, -- 25
    bibs :: Map FilePath [CP.Reference (CslJson Text)] -- 26
  }
  deriving stock (Eq, Generic, Show)
  deriving anyclass (FromJSON, ToJSON)

Archives use a global cell index with newtype:GCI to distinguish these against a local cell index (newtype:LCI). This is required because there are multiple objects each with their own LCI, and we have to tell these apart from each other.

🔗
newtype:GCI ⇪
type GCI :: Type
newtype GCI = GCI
  { unGCI :: Int
  }
  deriving stock (Eq, Ord, Generic, Show)
  deriving anyclass (FromJSON, FromJSONKey, Hashable, ToJSON, ToJSONKey)

Archives also keep track of a global table of contents, called GTOC (for global Table of Contents) at 24. This is the global table of contents which puts every object found in the archive into a single hierarchy. So whereas a normal Page contents has entries that are headings in the current object, the GTOC has entries which are objects in the archive. So in a sense, the GTOC is basically the "sitemap" of all navigable HTML pages.

It uses a tree data structure to encode the name of an object, or the fact that there is a directory (with objects presumably inside it).

🔗
newtype:GTOC ⇪
type GTOC :: Type
newtype GTOC = GTOC
  { unGTOC :: Tree GPath
  }
  deriving stock (Eq, Ord, Generic, Show)
  deriving anyclass (FromJSON, FromJSONKey, Hashable, ToJSON, ToJSONKey)

The other fields in data:Archive are based on the objects 18 inside it:

4.1 Construction

To construct the archive, f:mkArchive reads a list of path and object pairs and performs some processing on them to produce a data:Archive value. We need the path information mainly because ultimately when we weave these objects, we need to be able to understand the relative file path relationship between them in order to construct a relative HTML link, because the file structure layout of these objects will be preserved in the HTML file locations (by contrast, tangling does not involve tangling to relative paths).

🔗
f:mkArchive ⇑
mkArchive :: ProjectConf -> [(GPath, Object)] -> IO (Either String Archive)
mkArchive projectConf pathObjs = do
  let pathObjsNonEmpty =
        filter (\(_, obj) -> length obj.orgDoc.cells > 0) pathObjs -- 27
      (symbols, glossary) = combineSymbolsAndGlossary pathObjsNonEmpty
      offsets = mkOffsets pathObjsNonEmpty
      backlinks = mkBacklinks pathObjsNonEmpty symbols offsets
      brokenLinks = findBrokenLinks pathObjsNonEmpty symbols -- 28
  brokenFileLinks <- findBrokenFileLinks pathObjs
  (csls, bibs) <- getCitationDeps projectConf pathObjsNonEmpty
  if
    | brokenLinks /= [] ->
        pure
          . Left
          $ "Found broken links:\n"
          <> intercalate
            "\n"
            (map showBrokenLink brokenLinks)
    | brokenFileLinks /= [] ->
        pure
          . Left
          $ "Found broken file paths (from \"[[file:...]]\" links):\n"
          <> intercalate
            "\n"
            (map showBrokenFileLink brokenFileLinks)
    | otherwise ->
        case mkGTOC pathObjs of
          Left err -> pure $ Left err
          Right gtoc -> do
            let archive =
                  Archive
                    { objects = fromList pathObjs,
                      symbols = symbols,
                      ancestry = mempty,
                      glossary = glossary,
                      backlinks = backlinks,
                      offsets = offsets,
                      gtoc = gtoc,
                      csls = csls,
                      bibs = bibs
                    }
                ancestry =
                  mkBlockAncestry archive
                    $ getBlockGCIsFromArchive archive -- 29
            pure $ Right archive {ancestry = ancestry}
  where
    showBrokenLink :: (GPath, LinkOid) -> String
    showBrokenLink (gPath, link) =
      "  " <> (T.unpack $ show link) <> " (" <> (decodeGPath gPath) <> ")"
    showBrokenFileLink :: (GPath, FilePath) -> String
    showBrokenFileLink (gPath, filePath) =
      "  " <> (filePath) <> " (" <> (decodeGPath gPath) <> ")"

The first thing we do is remove any empty objects that don't have any content 27, because they're meaningless and also probably introduce bugs into offset calculation in f:mkOffsets. Then the main thing is to see that there are no broken links within this collection of objects 28; see Broken link detection and f:findBrokenLinks.

Other than the checks, the other concern is to combine the different parts of an object together with other objects. Some parts of an object can be simply combined together with the same parts in another object (there's not much more processing to do). These are the object's symbols 1 and glossary data:OrgDoc → 6. This is done in f:combineSymbolsAndGlossary.

🔗
f:combineSymbolsAndGlossary ⇑
combineSymbolsAndGlossary ::
  [(GPath, Object)] ->
  (Map LinkOid GCI, Map (Text, GPath) LCI)
combineSymbolsAndGlossary pathObjs =
  foldl' f (docOidsToSymbols pathObjs, mempty) $ prependOffsets pathObjs
  where
    f ::
      (Map LinkOid GCI, Map (Text, GPath) LCI) ->
      (Int, (GPath, Object)) ->
      (Map LinkOid GCI, Map (Text, GPath) LCI)
    f (accSyms, accGloss) (offset, (path, obj)) =
      ( (M.map (\lci -> GCI $ lci.unLCI + offset) obj.symbols) -- 30
          <> accSyms,
        (M.mapKeys (\term -> (term, path)) obj.orgDoc.glossary) <> accGloss
      )

LCI values of symbols are converted into GCI ones at 30, using offsets. These symbols come from cells (see f:mkSymbols).

We also generate (deterministically of course) a separate set of non-cell-based symbols for representing the documents (i.e., links to an Org document as a whole, not to any one of its constituent cells) in f:docOidsToSymbols. This can only be done at the archiving stage because an object by itself has no understanding of how many other objects there are in the archive, and hence, which index position it has relative to those other objects. These index positions are determined by sorting the objects by their path and using negative numbers so as not to clash with the positive GCI numbers from symbols targeting typical cell indices.

🔗
f:docOidsToSymbols ⇑
docOidsToSymbols :: [(GPath, Object)] -> Map LinkOid GCI
docOidsToSymbols pathObjs =
  let topLevelLinkOids =
        fromList
          $ zip
            (map (objToLinkOid . snd) $ sort pathObjs)
            (map GCI [-1, -2 ..])
      objToLinkOid :: Object -> LinkOid
      objToLinkOid obj =
        LinkOid
          { oid = obj.orgDoc.oid,
            name = ""
          }
   in topLevelLinkOids

Several functions like f:combineSymbolsAndGlossary and f:mkBacklinks use f:prependOffsets to calculate offsets. This offset information is saved in compact form in f:mkOffsets. Let's first look at f:prependOffsets.

🔗
f:prependOffsets ⇑
prependOffsets :: [(GPath, Object)] -> [(Int, (GPath, Object))]
prependOffsets pathObjs =
  cumulativeOffsets
    . map (\(path, obj) -> (length obj.orgDoc.cells, (path, obj)))
    $ sort pathObjs

This just sums up the number of cells for each object, and then builds up cumulative sums. After this cumulative step in f:cumulativeOffsets, you can think of each offset as like a step in a staircase --- each offset is higher than the previous one. Indeed, f:cumulativeOffsets takes a list of offsets (each offset inside a tuple), and converts them so that the offsets are cumulative (building on each other).

🔗
f:cumulativeOffsets ⇑
cumulativeOffsets :: [(Int, a)] -> [(Int, a)]
cumulativeOffsets xs = snd (mapAccumL f 0 xs)
  where
    f :: Int -> (Int, a) -> (Int, (Int, a))
    f currentSum (offset, x) =
      let newSum = currentSum + offset
       in (newSum, (currentSum, x))
🔗
t:0500-cumulativeOffsets-sanity ↑
describe "cumulativeOffsets sanity check" $ do
  it "works for empty case" $ do
    let input = [] :: [(Int, String)]
        output = [] :: [(Int, String)]
    LC.cumulativeOffsets input `shouldBe` output
  it "works for simple case" $ do
    let input = [(3, "a"), (9, "b"), (1, "c"), (2, "d")] :: [(Int, String)]
        output = [(0, "a"), (3, "b"), (12, "c"), (13, "d")] :: [(Int, String)]
    LC.cumulativeOffsets input `shouldBe` output

f:mkOffsets just converts these cumulative offsets into a more compact IntMap form, so that we can make use of the very convenient IntMap.lookupLE function (such as in f:gciToObjCell).

🔗
f:mkOffsets ⇑
mkOffsets :: [(GPath, Object)] -> IntMap GPath
mkOffsets pathObjs =
  IntMap.fromList
    . map (\(offset, (path, _obj)) -> (offset, path))
    $ prependOffsets pathObjs

4.2.1 Tests

Detect broken Noweb links.

Detect broken links in paragraphs. In this case, [[foo]] is not a named cell anywhere.

If we define the cell, the error goes away.

Referring to a non-existent line label of the same name (modulo parentheses) as a named cell should result in an error.

Below is similar to t:0401-broken-links-noweb, but the broken links have been fixed (we define the x cell and also the external document (dependency) that has cell c).

Ensure we allow links to an external cell, where the OID is either the top-level OID of the external Org doc, or the OID of the parent heading.

4.4.1 Tests

We use the f:checkCycles helper (powered by f:findCycles underneath) to detect cycles (or lack thereof).

First let's check for the happy path where there are no cycles. Note the use of :noweb off in the block's metadata so as to preserve the Noweb link declaration (see f:nowebLinkTargetParser and t:0007-blocks-noweb for more sample usage of :noweb off).

🔗
ti:0100-dag-no-loops
🎯 test/Lilac/CompileSpec/0100-dag-no-loops
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e000
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:b>>
#+end_src

#+name: f:b
#+begin_src haskell
g = 2 + 2
#+end_src
🔗
t:0100-dag-no-loops ↑
checkCycles
  ["0100-dag-no-loops"]
  []

Now check for the simplest case of a single self-loop.

🔗
ti:0100-dag-self-loop
🎯 test/Lilac/CompileSpec/0100-dag-self-loop
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e001
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:a>>
#+end_src
🔗
t:0100-dag-self-loop ↑
checkCycles
  ["0100-dag-self-loop"]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e001,
              name = "f:a"
            },
        subForest = []
      }
  ]

Below is the same, but for the case where there is an intervening heading.

🔗
ti:0100-dag-self-loop-heading
🎯 test/Lilac/CompileSpec/0100-dag-self-loop-heading
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e001
:END:

* heading
:PROPERTIES:
:ID:       11111111-1111-1111-1111-111111111111
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:a>>
#+end_src
🔗
t:0100-dag-self-loop-heading ↑
checkCycles
  ["0100-dag-self-loop-heading"]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e001,
              name = "f:a"
            },
        subForest = []
      },
    Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e001,
              name = "f:a"
            },
        subForest = []
      }
  ]

We get two nodes (vertices) in t:0100-dag-self-loop-heading instead of just one in ti:0100-dag-self-loop because when we add the two vertices for this case in f:buildGraph, both vertices will link out to the same document OID (implicitly) as an out link when they are parsed in at f:oidReferenceParser → 80. So from the cycle detection algorithm it's as if we linked from the code block (vertex) in the test to another code block that sits above the heading, which them links to itself forming a 2-block cycle.

Check whether we can detect two independent self-loops.

🔗
ti:0100-dag-self-loops
🎯 test/Lilac/CompileSpec/0100-dag-self-loops
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e003
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:a>>
#+end_src

#+name: f:b
#+begin_src haskell
f = 1 + 1
<<f:b>>
#+end_src
🔗
t:0100-dag-self-loops ↑
checkCycles
  ["0100-dag-self-loops"]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e003,
              name = "f:a"
            },
        subForest = []
      },
    Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e003,
              name = "f:b"
            },
        subForest = []
      }
  ]

t:0100-dag-2-node-loop checks whether we can detect a back edge to an ancestor by a cycle involving 2 nodes.

🔗
ti:0100-dag-2-node-loop
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e004
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:b>>
#+end_src

#+name: f:b
#+begin_src haskell
f = 1 + 1
<<f:a>>
#+end_src
🔗
t:0100-dag-2-node-loop ↑
checkCycles
  ["0100-dag-2-node-loop"]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e004,
              name = "f:a"
            },
        subForest =
          [ Node
              { rootLabel =
                  LinkOid
                    { oid = fromWords 0x0000000000000000 0x000000000000e004,
                      name = "f:b"
                    },
                subForest = []
              }
          ]
      }
  ]

The test below is like ti:0100-dag-2-node-loop but with an intervening heading.

🔗
ti:0100-dag-2-node-loop-heading
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop-heading
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e004
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:b>>
#+end_src

* heading
:PROPERTIES:
:ID:       11111111-1111-1111-1111-111111111111
:END:

#+name: f:b
#+begin_src haskell
f = 1 + 1
<<f:a>>
#+end_src
🔗
t:0100-dag-2-node-loop-heading ↑
checkCycles
  ["0100-dag-2-node-loop-heading"]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e004,
              name = "f:a"
            },
        subForest =
          [ Node
              { rootLabel =
                  LinkOid
                    { oid = fromWords 0x0000000000000000 0x000000000000e004,
                      name = "f:b"
                    },
                subForest = []
              }
          ]
      }
  ]

Test case t:0100-dag-3-node-loop is like the previous one, but where the loop is one node longer (involves 3 nodes instead of 2).

🔗
ti:0100-dag-3-node-loop
🎯 test/Lilac/CompileSpec/0100-dag-3-node-loop
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e005
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:b>>
#+end_src

#+name: f:b
#+begin_src haskell
f = 1 + 1
<<f:c>>
#+end_src

#+name: f:c
#+begin_src haskell
f = 1 + 1
<<f:a>>
#+end_src
🔗
t:0100-dag-3-node-loop ↑
checkCycles
  ["0100-dag-3-node-loop"]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e005,
              name = "f:a"
            },
        subForest =
          [ Node
              { rootLabel =
                  LinkOid
                    { oid = fromWords 0x0000000000000000 0x000000000000e005,
                      name = "f:b"
                    },
                subForest =
                  [ Node
                      { rootLabel =
                          LinkOid
                            { oid =
                                fromWords
                                  0x0000000000000000
                                  0x000000000000e005,
                              name = "f:c"
                            },
                        subForest = []
                      }
                  ]
              }
          ]
      }
  ]

Lastly, we have a test case involving complex loops. There are many back edges involved here; we just want to make sure that our algorithm for finding cycles is still able to handle such pathological input.

🔗
ti:0100-dag-complex-loops
🎯 test/Lilac/CompileSpec/0100-dag-complex-loops
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e006
:END:

#+name: f:a
#+begin_src haskell
f = 1 + 1
<<f:b>>
#+end_src

#+name: f:b
#+begin_src haskell
f = 1 + 1
<<f:c>>
<<f:d>>
#+end_src

#+name: f:c
#+begin_src haskell
f = 1 + 1
<<f:a>>
#+end_src

#+name: f:d
#+begin_src haskell
f = 1 + 1
<<f:b>>
<<f:d>>
#+end_src

#+name: f:e
#+begin_src haskell
f = 1 + 1
<<f:e>>
#+end_src
🔗
t:0100-dag-complex-loops ↑
checkCycles
  ["0100-dag-complex-loops"]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e006,
              name = "f:a"
            },
        subForest =
          [ Node
              { rootLabel =
                  LinkOid
                    { oid = fromWords 0x0000000000000000 0x000000000000e006,
                      name = "f:b"
                    },
                subForest =
                  [ Node
                      { rootLabel =
                          LinkOid
                            { oid =
                                fromWords
                                  0x0000000000000000
                                  0x000000000000e006,
                              name = "f:c"
                            },
                        subForest = []
                      },
                    Node
                      { rootLabel =
                          LinkOid
                            { oid =
                                fromWords
                                  0x0000000000000000
                                  0x000000000000e006,
                              name = "f:d"
                            },
                        subForest = []
                      }
                  ]
              }
          ]
      },
    Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000e006,
              name = "f:e"
            },
        subForest = []
      }
  ]

Cycle detection should still work even for cycles that span across two files.

🔗
ti:0100-dag-2-node-loop-2-files-parent
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop-2-files-parent
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f004
:END:
#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
hello from a
<<id:00000000-0000-0000-0000-00000000f005::b>>
#+end_src
🔗
ti:0100-dag-2-node-loop-2-files-child
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop-2-files-child
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f005
:END:
#+name: b
#+begin_src haskell
hello from b
<<id:00000000-0000-0000-0000-00000000f004::a>>
#+end_src
🔗
t:0100-dag-2-node-loop-2-files ↑
checkCycles
  [ "0100-dag-2-node-loop-2-files-parent",
    "0100-dag-2-node-loop-2-files-child"
  ]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000f004,
              name = "a"
            },
        subForest =
          [ Node
              { rootLabel =
                  LinkOid
                    { oid = fromWords 0x0000000000000000 0x000000000000f005,
                      name = "b"
                    },
                subForest = []
              }
          ]
      }
  ]

Below is the same test, but involving an intervening heading (only for the parent).

🔗
ti:0100-dag-2-node-loop-2-files-parent-heading
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop-2-files-parent-heading
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f004
:END:

* heading
:PROPERTIES:
:ID:       11111111-1111-1111-1111-111111111111
:END:

#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
hello from a
<<id:00000000-0000-0000-0000-00000000f005::b>>
#+end_src
🔗
t:0100-dag-2-node-loop-2-files-heading ↑
checkCycles
  [ "0100-dag-2-node-loop-2-files-parent-heading",
    "0100-dag-2-node-loop-2-files-child"
  ]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000f004,
              name = "a"
            },
        subForest =
          [ Node
              { rootLabel =
                  LinkOid
                    { oid = fromWords 0x0000000000000000 0x000000000000f005,
                      name = "b"
                    },
                subForest = []
              }
          ]
      }
  ]

If three files form a cycle, that should also be detected.

🔗
ti:0100-dag-2-node-loop-3-files-parent
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop-3-files-parent
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f006
:END:
#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
hello from a
<<id:00000000-0000-0000-0000-00000000f007::b>>
#+end_src
🔗
ti:0100-dag-2-node-loop-3-files-middleman
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop-3-files-middleman
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f007
:END:
#+name: b
#+begin_src haskell
hello from b
<<id:00000000-0000-0000-0000-00000000f008::c>>
#+end_src
🔗
ti:0100-dag-2-node-loop-3-files-child
🎯 test/Lilac/CompileSpec/0100-dag-2-node-loop-3-files-child
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f008
:END:
#+name: c
#+begin_src haskell
hello from c
<<id:00000000-0000-0000-0000-00000000f006::a>>
#+end_src
🔗
t:0100-dag-2-node-loop-3-files ↑
checkCycles
  [ "0100-dag-2-node-loop-3-files-parent",
    "0100-dag-2-node-loop-3-files-middleman",
    "0100-dag-2-node-loop-3-files-child"
  ]
  [ Node
      { rootLabel =
          LinkOid
            { oid = fromWords 0x0000000000000000 0x000000000000f006,
              name = "a"
            },
        subForest =
          [ Node
              { rootLabel =
                  LinkOid
                    { oid = fromWords 0x0000000000000000 0x000000000000f007,
                      name = "b"
                    },
                subForest =
                  [ Node
                      { rootLabel =
                          LinkOid
                            { oid =
                                fromWords
                                  0x0000000000000000
                                  0x000000000000f008,
                              name = "c"
                            },
                        subForest = []
                      }
                  ]
              }
          ]
      }
  ]

4.5 Block ancestry

f:mkBlockAncestry builds a "graph" similar to the one used in f:findCycles, but with a few differences:

This information is used in f:weaveBlockAncestry to generate ancestry information. This can be helpful to know where exactly a block is referenced by a Noweb link.

🔗
f:mkBlockAncestry ⇑
mkBlockAncestry :: Archive -> [GCI] -> Map GCI [GCI]
mkBlockAncestry archive blockGCIs = foldl' f mempty blockGCIs
  where
    f :: Map GCI [GCI] -> GCI -> Map GCI [GCI]
    f acc blockGCI
      | Just (_, CBlock block) <- gciToObjCell archive blockGCI =
          ( \childLinks ->
              foldl'
                ( \acc' childLink ->
                    case lookup childLink archive.symbols of
                      Just childGCI ->
                        insertWith
                          (\old new -> hashNub (old <> new))
                          childGCI
                          [blockGCI]
                          acc'
                      Nothing -> acc'
                )
                acc
                childLinks
          )
            . catMaybes
            $ map getChildLinks block.body
      | otherwise = acc
    getChildLinks = \case
      BTokenLinkTarget (LinkTargetOid linkOid) -> Just linkOid
      BTokenLinkTarget {}
      BTokenPadding {}
      BTokenString {} -> Nothing

f:getBlockGCIsFromArchive gets all code blocks (by their newtype:GCI) from the archive. This is used for calling f:mkBlockAncestry 29.

🔗
f:getBlockGCIsFromArchive ⇑
getBlockGCIsFromArchive :: Archive -> [GCI]
getBlockGCIsFromArchive archive = foldl' f [] $ elems archive.symbols
  where
    f :: [GCI] -> GCI -> [GCI]
    f acc gci
      | Just (_, cell) <- gciToObjCell archive gci =
          case cell of
            CBlock {} -> gci : acc
            CHeading {}
            CListItem {}
            CParagraph {}
            CGlossaryTerm {}
            CMathFragment {}
            CFigure {}
            CTable {}
            CFootnote {}
            CCommand {} -> acc
      | otherwise = acc

The line elems archive.symbols just gets all code blocks from the symbols field of the data:Archive (perhaps elems is a poor name and should have been called values instead, but that's probably because "values" from "keys and values" shadows the "values" in "types vs values").

4.7 Citation dependencies

f:getCitationDeps reads CSL files and also bibliographies (JSON files). This is the main workhorse, as the other functions in this section are just helpers to f:getCitationDeps.

🔗
f:getCitationDeps ⇑
getCitationDeps ::
  ProjectConf ->
  [(GPath, Object)] ->
  IO (Map FilePath Text, Map FilePath [CP.Reference (CslJson Text)])
getCitationDeps projectConf pathObjs = do
  csls <- getCitationStyles projectConf pathObjs
  bibs <- getBibliographies projectConf pathObjs
  pure (csls, bibs)

We'll first look at citations, and then bibliographies.

4.7.1 Read citation style (XML) files

f:getCitationStyles relies on f:getCitationStyle which returns both the raw XML content as well as the parsed content. We discard the latter with a map fst 39. We can only keep the raw XML (as a Text) because we want to store it in f:mkArchive, and there is no ToJSON instance for the CP.Style type.

🔗
f:getCitationStyles ⇑
getCitationStyles :: ProjectConf -> [(GPath, Object)] -> IO (Map FilePath Text)
getCitationStyles projectConf pathObjs = do
  allCslPaths <-
    concat
      <$> mapM
        ( \(gPath, obj) ->
            makeRelativeToObjectPath gPath -- 38
              $ maybeToList obj.orgDoc.cslPath
        )
        pathObjs
  cslRawXMLs <- map fst <$> mapM getCitationStyle allCslPaths -- 39
  let m = fromList $ zip allCslPaths cslRawXMLs
  case projectConf.citationStyle of
    Just cslPath -> do
      (text, _) <- getCitationStyle cslPath
      pure $ insert cslPath text m -- 40
    Nothing -> do
      pure m

The returned type is a Map FilePath Text where the key is the path to the CSL file, and the Text is the contents of it. During weaving in f:prepareCitations, we do a lookup into this Map.

40 inserts the default CSL path, if any, into the response. This is used as a fallback in f:prepareCitations if an Org doc does not specify a CSL style.

f:makeRelativeToObjectPath 38 gets a [FilePath] and makes them relative to the given GPath (by just combining the GPath with the file paths). This is useful for getting paths defined inside an Org doc (such as the path to a CSL style or bibliography JSON) to be relative to where the Org doc is located.

🔗
f:makeRelativeToObjectPath ⇑
makeRelativeToObjectPath :: GPath -> [FilePath] -> IO [FilePath]
makeRelativeToObjectPath objGPath fps = do
  let objPath = decodeGPath objGPath
  objOsp <- P.encodeUtf objPath
  let objDir = P.takeDirectory objOsp
  mapM (f objDir) fps
  where
    f :: P.OsPath -> FilePath -> IO FilePath
    f objDir fp = do
      p <- P.encodeUtf fp
      let relPath = P.combine objDir p
      P.decodeUtf relPath

For parsing the CSL style file (XML), we read a given path, then defer to f:parseCitationStyle. Even though we discard this parsed content in f:getCitationStyles, we still want to parse it here because it's important validation (to know that the underlying XML is valid).

🔗
f:getCitationStyle ⇑
getCitationStyle :: FilePath -> IO (Text, (CP.Style (CslJson Text)))
getCitationStyle filePath = do
  p <- P.encodeUtf filePath
  input <- LU.readFileRobustly p
  case parseCitationStyle input of
    Left errMsg -> die $ "while parsing " <> filePath <> ":" <> errMsg
    Right style -> pure (input, style)

f:parseCitationStyle just delegates most of the work to parseStyle from Citeproc.Style. We expect the contents to be in CslJson Text format.

🔗
f:parseCitationStyle ⇑
parseCitationStyle :: Text -> Either String (CP.Style (CslJson Text))
parseCitationStyle input = do
  result <- CP.parseStyle (\_ -> pure mempty) input
  case result of
    Left citeprocError -> Left $ show citeprocError
    Right style -> Right style

4.7.2 Read bibliography (JSON) files

The f:getBibliographies reads multiple JSON files that have bibliographical entries in them.

🔗
f:getBibliographies ⇑
getBibliographies ::
  ProjectConf ->
  [(GPath, Object)] ->
  IO (Map FilePath [CP.Reference (CslJson Text)])
getBibliographies projectConf pathObjs = do
  bibPaths <-
    concat
      <$> mapM
        (\(gPath, obj) -> makeRelativeToObjectPath gPath obj.orgDoc.bibPaths)
        pathObjs
  let allBibPaths = projectConf.bibliography <> bibPaths
  fromList <$> mapM (\p -> fmap (\b -> (p, b)) (getBibliography p)) allBibPaths

The f:getBibliography parses a single JSON file which has a list of references inside it.

🔗
f:getBibliography ⇑
getBibliography :: FilePath -> IO [CP.Reference (CslJson Text)]
getBibliography filePath = do
  p <- P.encodeUtf filePath
  input <- LU.readFileRobustly p
  case parseBibliography input of
    Left errMsg -> die $ "while parsing " <> filePath <> ":" <> errMsg
    Right references -> pure references

f:parseBibliography just delegates to eitherDecodeStrictText from Data.Aeson. This is possible because the Reference type (from Citeproc.Types) has a FromJSON instance.

🔗
f:parseBibliography ⇑
parseBibliography :: Text -> Either String [CP.Reference (CslJson Text)]
parseBibliography = eitherDecodeStrictText

4.8 GTOC

GTOC construction needs to find all index.org objects, and the special index code block inside each one. We have to then construct a single large tree out of this, where the values in the leaf nodes are GPath strings of objects in the archive.

Below are some type signatures with some small modifications to better understand where we want to go.

🔗
unfoldTree :: (b -> (a, [b])) -> b -> Tree a -- 41
unfoldTree :: (seed -> (final_val, [seed])) -> seed -> Tree final_val -- 42
unfoldTreeM :: generator -> (GPath, Object) -> m Tree GPath -- 43

unfoldTree 41 is the basic function which knows how to grow a tree, starting from a seed value b and a generator function which can grow the next level of a tree. 42 is the same signature but with more descriptive type names. Finally 43 shows the signature with the types we'll be using, with m representing a monadic context; we use the State monad at 46 so that we can record invalid paths as we start building up the tree. Invalid paths are stored in data:PathState.

🔗
data:PathState ⇑
type PathState :: Type
data PathState = PathState
  { objMap :: Map GPath Object, -- 44
    invalidPaths :: [GPath] -- 45
  }

As for the details around growing the tree itself, it is as follows:

  1. Find the root index.org object (along with its GPath).

  2. Find the index code block and get a list of all paths.

  3. Convert each path in the list with a new (synthetic) GPath.

  4. Replace each GPath by its object, by doing a lookup in the map of all objects. The map is visible from the State monad so that we can read from it at any time without having to pass it along to every child call.

    If the path does not exist in the objMap 44, then record it inside 45.

The first step is done in f:findRootIndex, which is called by f:mkGTOC. The remaining steps are carried out in f:getChildPaths.

🔗
f:mkGTOC ⇑
mkGTOC :: [(GPath, Object)] -> Either String GTOC
mkGTOC pathObjs
  | Just pathObj <- findRootIndex pathObjs =
      let objMap = fromList pathObjs
          invalidPaths = [] :: [GPath]
          initialState = PathState objMap invalidPaths
          (gtoc, finalState) = runState (f pathObj) initialState
       in if null finalState.invalidPaths
            then Right gtoc
            else
              let paths =
                    map
                      (("  " <>) . T.pack . decodeGPath)
                      finalState.invalidPaths
               in Left
                    $ "Invalid GTOC object paths:\n"
                    <> (T.unpack $ unlines paths)
  | otherwise = Right . GTOC $ Node emptyGPath []
  where
    f :: (GPath, Object) -> State PathState GTOC
    f pathObj = GTOC <$> unfoldTreeM generator pathObj -- 46
    generator ::
      (GPath, Object) ->
      State PathState (GPath, [(GPath, Object)])
    generator (path, obj)
      | isIndexObjPath path = do
          childPaths <- getChildPaths (path, obj)
          pure (path, childPaths)
      | otherwise = pure (path, [])

f:isIndexObjPath just checks if the file ends in a index.lobj file path.

🔗
f:isIndexObjPath ⇑
isIndexObjPath :: GPath -> Bool
isIndexObjPath gpath = "index.lobj" `T.isSuffixOf` (T.pack $ decodeGPath gpath)

f:findRootIndex retrieves the root index.org object, if there is one. It finds the index.org path which has the fewest number of leading parent directories. This assumes that there is only one index.org file inside any directory.

🔗
f:findRootIndex ⇑
findRootIndex :: [(GPath, Object)] -> Maybe (GPath, Object)
findRootIndex pathObjs =
  let result = foldl' f Nothing pathObjs
   in snd <$> result
  where
    f ::
      Maybe (Int, (GPath, Object)) ->
      (GPath, Object) ->
      Maybe (Int, (GPath, Object))
    f acc (curGPath, obj) =
      let pathStr = decodeGPath curGPath
       in if isIndexObjPath curGPath
            then
              let curDepth = length $ splitDirectories pathStr
               in case acc of
                    Nothing -> Just (curDepth, (curGPath, obj))
                    Just (shallowestDepth, _)
                      | curDepth < shallowestDepth ->
                          Just (curDepth, (curGPath, obj))
                      | otherwise -> acc
            else acc

f:getChildPaths gets all the paths inside an index code block. These paths are "incomplete" in a way, because they only hold the name of the directory or file at the current level. So we have to complete the path by merging it with the path information of the parent object.

🔗
f:getChildPaths ⇑
getChildPaths :: (GPath, Object) -> State PathState [(GPath, Object)]
getChildPaths (path, obj) = foldlM f [] obj.orgDoc.cells
  where
    f :: [(GPath, Object)] -> Cell -> State PathState [(GPath, Object)]
    f acc = \case
      CBlock b
        | Just "index" <- lookup "name" b.meta -> do
            let rawText = T.concat $ map extractBTokenStringOnly b.body
                indexPath = T.pack $ decodeGPath path -- 47
                startingPath = T.dropEnd 10 indexPath -- 48
                rawChildPaths = T.lines rawText
                isIndexPath :: Text -> Bool
                isIndexPath = (== "index.org") -- 49
                (indexPaths, standardPaths) = partition isIndexPath rawChildPaths
                toGPath' = mapMaybe (toGPath startingPath)
                paths = toGPath' standardPaths -- 50
                invalidIndexPaths = toGPath' indexPaths
            when (not $ null invalidIndexPaths) $ do
              modify
                $ \s ->
                  s
                    { invalidPaths = s.invalidPaths <> invalidIndexPaths
                    }
            results <- mapM lookupSingle paths
            pure $ acc <> catMaybes results
      _ -> pure acc
    toGPath :: Text -> Text -> Maybe GPath
    toGPath startingPath textPath =
      let joinedPath = startingPath <> textPath -- 51
          constructedPath =
            -- 52
            if ".org" `T.isSuffixOf` joinedPath
              then (T.dropEnd 3 joinedPath) <> "lobj"
              else joinedPath <> "/index.lobj"
       in encodeGPath $ T.unpack constructedPath
    lookupSingle :: GPath -> State PathState (Maybe (GPath, Object))
    lookupSingle p = do
      st <- get
      case lookup p st.objMap of
        Just o -> pure $ Just (p, o)
        Nothing -> do
          modify $ \s -> s {invalidPaths = s.invalidPaths <> [p]}
          pure Nothing
    extractBTokenStringOnly :: BToken -> Text
    extractBTokenStringOnly = \case
      BTokenString text -> text
      _ -> ""

The sequence of operations (with the state of the path at each step) is below:

  1. Start with the indexPath 47 (e.g., dir/index.lobj).

  2. Drop the last 10 chars 48 to get the parent dir, dir/.

  3. Add the textPath 51 to get dir/foo.org.

  4. 52 If ending in .org, replace with .lobj. Otherwise this is a directory, so add it and then also add a trailing /index.lobj to it.

50 avoids recursing into another index.org document, because that will lead to infinite recursion. The check at 49 doesn't take into account any directory slashes, because child paths may only refer to direct children within the same directory.

4.8.1 Tests

Don't error out if there's no index.lobj --- GTOC generation is optional.

🔗
ti:0105-gtoc-no-root-index
🎯 test/Lilac/CompileSpec/0105/foo.org
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f010
:END:

foo
🔗
t:0105-gtoc-no-root-index ↑
expectGTOC
  ["0105/foo.org"]
  (Right . GTOC $ Node emptyGPath [])

Root index.lobj exists, but without an index code block.

🔗
ti:0105-gtoc-root-index-without-index-block
🎯 test/Lilac/CompileSpec/0105/index.org
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f011
:END:

This is an index file.
🔗
t:0105-gtoc-root-index-without-index-block ↑
expectGTOC
  [ "0105/foo.org",
    "0105/index.org"
  ]
  (Right . GTOC $ Node (GPath "test/Lilac/CompileSpec/0105/index.lobj") [])

Root index.lobj exists, with a basic index code block.

🔗
ti:0105-gtoc-basic-foo
🎯 test/Lilac/CompileSpec/0105/basic/foo.org
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f012
:END:

foo
🔗
ti:0105-gtoc-basic-bar
🎯 test/Lilac/CompileSpec/0105/basic/bar.org
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f013
:END:

foo
🔗
ti:0105-gtoc-basic-index
🎯 test/Lilac/CompileSpec/0105/basic/index.org
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f014
:END:

This is an index file.

#+name: index
#+begin_src txt
foo.org
bar.org
#+end_src
🔗
t:0105-gtoc-basic ↑
expectGTOC
  [ "0105/basic/foo.org",
    "0105/basic/bar.org",
    "0105/basic/index.org"
  ]
  ( Right
      . GTOC
      $ Node
        (GPath "test/Lilac/CompileSpec/0105/basic/index.lobj")
        [ Node (GPath "test/Lilac/CompileSpec/0105/basic/foo.lobj") [],
          Node (GPath "test/Lilac/CompileSpec/0105/basic/bar.lobj") []
        ]
  )

Invalid paths specified in the index code block, but which do not exist in the Archive's list of object paths should show up as an error. In the code block, we specify a directory named dir1 and an Org file README.org, but neither are present in the given list of paths.

🔗
ti:0105-gtoc-invalid-paths
🎯 test/Lilac/CompileSpec/0105/invalid-paths/index.org
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f014
:END:

This is an index file.

#+name: index
#+begin_src txt
dir1
README.org
#+end_src
🔗
t:0105-gtoc-invalid-paths ↑
expectGTOC
  [ "0105/invalid-paths/index.org"
  ]
  ( Left
      """
      Invalid GTOC object paths:
        test/Lilac/CompileSpec/0105/invalid-paths/dir1/index.lobj
        test/Lilac/CompileSpec/0105/invalid-paths/README.lobj

      """
  )

Listing index.org in the list of child paths is invalid.

🔗
ti:0105-gtoc-invalid-paths-self
🎯 test/Lilac/CompileSpec/0105/invalid-paths-self/index.org
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f014
:END:

This is an index file.

#+name: index
#+begin_src txt
index.org
dir1
README.org
#+end_src
🔗
t:0105-gtoc-invalid-paths-self ↑
expectGTOC
  [ "0105/invalid-paths-self/index.org"
  ]
  ( Left
      """
      Invalid GTOC object paths:
        test/Lilac/CompileSpec/0105/invalid-paths-self/index.lobj
        test/Lilac/CompileSpec/0105/invalid-paths-self/dir1/index.lobj
        test/Lilac/CompileSpec/0105/invalid-paths-self/README.lobj

      """
  )

5 Utility functions

f:gciToName gives a human-friendly name of the cell. Much of it is patterned after f:getLinkAnchor, which gives a semi-human-friendly (and definitely machine-friendly) name for a given cell. We use the pilcrow (¶) and section symbol (§) directly for paragraphs and headings because f:weaveStyledText will escape non-HTML-safe characters with HTML entities, such that if we do &para; the & will get escaped to &amp;, which would result in the broken &amp;para;.

🔗
f:gciToName ⇑
gciToName :: Archive -> Int -> GCI -> Maybe Prose
gciToName archive offset gci
  | Just (_, cell) <- gciToObjCell archive gci =
      case cell of
        CHeading heading ->
          plain
            $ "§ "
            <> (getSectionNumber heading)
            <> " "
            <> (getProseContents heading.body)
        CParagraph _ ->
          Just
            $ Prose
              [ ptext "¶ (" [],
                ptext cellRef [Verbatim],
                ptext ")" []
              ]
        CGlossaryTerm glossaryTerm ->
          Just
            $ Prose [ptext "✿ " []]
            <> stripLinks glossaryTerm.term -- 53
        CFigure figure
          | Just name <- lookup "name" figure.meta -> verbatim name
          | Just figureNum <- lookup "__figure_number" figure.meta ->
              plain $ "Figure " <> figureNum
          | otherwise -> plain "Figure"
        CTable table
          | Just name <- lookup "name" table.meta -> verbatim name
          | Just tableNum <- lookup "__table_number" table.meta ->
              plain $ "Table " <> tableNum
          | otherwise -> plain "Table"
        CFootnote footnote ->
          Just
            $ Prose
              [ ptext "Footnote (" [],
                ptext ("fn:" <> footnote.name) [Verbatim],
                ptext ")" []
              ]
        CBlock block
          | Just name <- lookup "name" block.meta ->
              verbatim name
          | otherwise -> plain $ "Anonymous Block" <> cellRef
        CMathFragment mathFragment
          | Just name <- lookup "name" mathFragment.meta ->
              verbatim name
          | Just eqNum <- lookup "__equation_number" mathFragment.meta ->
              plain $ "Equation " <> eqNum
          | Just eqNum <- lookup "__equation_anon_number" mathFragment.meta ->
              plain $ "Anonymous Equation " <> eqNum
          | otherwise -> plain "Math Fragment"
        CListItem {}
        CCommand {} -> Nothing
  | otherwise = Nothing
  where
    cellRef = "Cell " <> (T.show $ gci.unGCI - offset)
    plain body = Just $ Prose [ptext body []]
    verbatim body = Just $ Prose [ptext body [Verbatim]]

We have to convert links (PTokenLink) into styled text (PTokenStyledText) at 53 because otherwise when we create backlinks at f:weaveBacklinks, we can potentially end up with nested <a> tags (because backlink generation means always wrapping the name of a backlink with a link (<a> tag) to that backlink), which would be illegal HTML (HTML does not allow nesting of <a> tags). f:stripLinks just takes the display name of any link and turns that into styled text.

f:stripStyles removes all styling masks.

🔗
f:stripStyles ⇪
stripStyles :: Prose -> Prose
stripStyles (Prose pTokens) = Prose (concatMap stripStyle pTokens)
  where
    stripStyle :: PToken -> [PToken]
    stripStyle = \case
      PTokenStyledText styledText -> [ptext styledText.body []]
      pToken -> [pToken]

f:getCellName is similar to f:gciToName, but it only returns a Just value if the cell is a block, figure, table, footnote, or math fragment that has a #+name: ....

🔗
f:getCellName ⇪
getCellName :: Cell -> Maybe Prose
getCellName = \case
  CFigure figure
    | Just name <- lookup "name" figure.meta -> verbatim name
    | otherwise -> Nothing
  CTable table
    | Just name <- lookup "name" table.meta -> verbatim name
    | otherwise -> Nothing
  CFootnote footnote ->
    Just
      $ Prose
        [ ptext "Footnote (" [],
          ptext ("fn:" <> footnote.name) [Verbatim],
          ptext ")" []
        ]
  CBlock block
    | Just name <- lookup "name" block.meta ->
        verbatim name
    | otherwise -> Nothing
  CMathFragment mathFragment
    | Just name <- lookup "name" mathFragment.meta ->
        verbatim name
    | otherwise -> Nothing
  CHeading {}
  CParagraph {}
  CGlossaryTerm {}
  CListItem {}
  CCommand {} -> Nothing
  where
    verbatim body = Just $ Prose [ptext body [Verbatim]]

f:gciToObjCell takes a global cell index and converts it to the right cell and the object (Org doc) that contains it, as a tuple.

🔗
f:gciToObjCell ⇪
gciToObjCell :: Archive -> GCI -> Maybe (Object, Cell)
gciToObjCell archive gci
  | Just (offset, path) <- IntMap.lookupLE gci.unGCI archive.offsets,
    Just obj <- lookup path archive.objects,
    Just cell <- obj.orgDoc.cells !!? (gci.unGCI - offset) =
      Just (obj, cell)
  | otherwise = Nothing

f:gciToObjPath gets the path of the object by the negative GCI index; it is in this sense the opposite of f:docOidsToSymbols.

🔗
f:gciToObjPath ⇪
gciToObjPath :: Archive -> GCI -> Maybe GPath
gciToObjPath archive gci
  | gci.unGCI < 0 =
      (sort $ keys archive.objects) !!? (abs gci.unGCI - 1)
  | Just (_, path) <- IntMap.lookupLE gci.unGCI archive.offsets =
      Just path
  | otherwise = Nothing

6 Testing framework

The testing framework here is modeled closely after module:Lilac.ParseSpec.

6.1 Test module and helpers

🔗
module:Lilac.CompileSpec
🎯 test/Lilac/CompileSpec.hs
module Lilac.CompileSpec (spec) where

import Data.Graph qualified as G
import Data.Text qualified as T
import Data.Tree
  ( Tree (Node, rootLabel, subForest),
  )
import Lilac.Compile qualified as LC
import Lilac.Parse qualified as LP
import Lilac.Types
  ( GTOC (GTOC),
    LinkOid (LinkOid, name, oid),
    Object,
    decodeGPath,
    emptyGPath,
    emptyProjectConf,
    encodeGPath,
    fromWords,
  )
import Lilac.Types.Internal (GPath (GPath))
import Lilac.Util qualified as LU
import Relude
  ( Either (Left, Right),
    FilePath,
    Int,
    Maybe (Just, Nothing),
    MonadFail,
    String,
    fail,
    isRight,
    map,
    pure,
    show,
    traverse,
    ($),
    (.),
    (<>),
  )
import Test.Hspec
  ( Spec,
    describe,
    expectationFailure,
    it,
    runIO,
    shouldBe,
    shouldSatisfy,
  )

spec :: Spec
spec = do
  All test cases

CompileSpec helpers

The test cases in All test cases will be defined with the following test helpers.

🔗
CompileSpec helpers ⇑
f:checkExternalLinkOids
f:expectArchiveError
f:expectArchiveOk
f:checkCycles
f:expectGTOC

Note that the helpers use the more convenient FilePath type instead of P.OsPath, mainly because using the QuasiQuoter for P.OsPath slows down the compilation process and because data:Archive uses GPath anyway (and not P.OsPath).

f:checkExternalLinkOids checks if we can detect which symbols (named by their LinkOid) cannot be accounted for in the current object, and are hence external.

🔗
f:checkExternalLinkOids ↑
checkExternalLinkOids :: FilePath -> [LinkOid] -> Spec
checkExternalLinkOids path expectedExternalOids = do
  it path $ do
    (Right od) <- read
    LC.findExternalOids od `shouldBe` expectedExternalOids
  where
    read = do
      input <- LU.readFrom "test/Lilac/CompileSpec/" path
      pure $ LP.parseOrgDoc input

f:readObjectsFrom reads files from a given parent directory, and converts them into data:Object values. This is used in tests where we want to read multiple objects for a test case.

🔗
f:readObjectsFrom ⇑
readObjectsFrom :: FilePath -> [FilePath] -> IO [(GPath, Object)]
readObjectsFrom parentDir = foldlM f []
  where
    f :: [(GPath, Object)] -> FilePath -> IO [(GPath, Object)]
    f acc path = do
      parentDirEncoded <- P.encodeUtf parentDir
      p <- P.encodeUtf path
      let relPath = P.combine parentDirEncoded p
      input <- LU.readFileRobustly relPath
      case LP.parseOrgDoc input of
        Left errTxt -> die $ T.unpack errTxt
        Right od -> do
          relPath' <- encodeGPath =<< P.decodeUtf relPath
          pure $ (relPath', mkObject od) : acc

We want to check broken links for data:Archive values as well. For this we have f:expectArchiveError.

🔗
f:expectArchiveError ↑
expectArchiveError :: [FilePath] -> String -> Spec
expectArchiveError paths expected = do
  it (show paths) $ do
    pathObjs <- LC.readObjectsFrom "test/Lilac/CompileSpec/" paths
    maybeArchive <- LC.mkArchive emptyProjectConf pathObjs
    maybeArchive `shouldBe` (Left expected)

The other side of the coin is f:expectArchiveOk which expects the archive to be successfully created.

🔗
f:expectArchiveOk ↑
expectArchiveOk :: [FilePath] -> Spec
expectArchiveOk paths = do
  it (show paths) $ do
    pathObjs <- LC.readObjectsFrom "test/Lilac/CompileSpec/" paths
    maybeArchive <- LC.mkArchive emptyProjectConf pathObjs
    maybeArchive `shouldSatisfy` isRight

The f:checkCycles function uses f:findCycles to see if the archive that is constructed from the given Org documents has any cycles.

🔗
f:checkCycles ↑
checkCycles :: [FilePath] -> [G.Tree LinkOid] -> Spec
checkCycles paths expectedCycles = do
  pathObjs <- runIO $ LC.readObjectsFrom "test/Lilac/CompileSpec/" paths
  maybeArchive <- runIO $ LC.mkArchive emptyProjectConf pathObjs
  case maybeArchive of
    Left errMsg -> it "programmer error" $ expectationFailure errMsg
    Right archive -> it (show paths) $ do
      (LC.findCycles archive) `shouldBe` expectedCycles

f:expectGTOC looks at file paths and checks the result of running f:mkGTOC against them.

Normally, Lilac users would compile the Org files into objects, then feed those objects into f:mkArchive which would result in the .lobj filename extensions. However for testing purposes we take a shortcut and perform this .lobj conversion by simply replacing .org with .lobj. This business with extensions matters because f:mkGTOC expects file paths to end in .lobj.

🔗
f:expectGTOC ↑
expectGTOC :: [FilePath] -> Either String GTOC -> Spec
expectGTOC paths expected = do
  it (show paths) $ do
    pathObjs <- LC.readObjectsFrom "test/Lilac/CompileSpec/" paths
    pathObjs' <- orgToLobj pathObjs
    LC.mkGTOC pathObjs' `shouldBe` expected
  where
    orgToLobj ::
      (MonadFail m) =>
      [(GPath, Object)] ->
      m [(GPath, Object)]
    orgToLobj pairs = do
      traverse reencode transformed
      where
        transformed :: [(T.Text, Object)]
        transformed = map transformPath pairs

        transformPath :: (GPath, Object) -> (T.Text, Object)
        transformPath (gp, obj) =
          let path = T.pack $ decodeGPath gp
              newPath =
                if ".org" `T.isSuffixOf` path
                  then (T.dropEnd 4 path) <> ".lobj"
                  else path
           in (newPath, obj)

        reencode :: (MonadFail m) => (T.Text, Object) -> m (GPath, Object)
        reencode (t, obj) =
          case encodeGPath (T.unpack t) of
            Just newGp -> pure (newGp, obj)
            Nothing ->
              fail
                $ "Failed to re-encode path: "
                <> T.unpack t

6.2 All test cases

Below are all of the individual test cases.

7 Glossary

ancestry
↑ 20 A map of global cell indices of blocks to their parents (a block can have multiple parents because more than one block can refer to the same child block). This is created by f:mkBlockAncestry and later used by f:weaveBlockAncestry for making each block link back to its parents, if any.
archive
↑ A self-contained collection of objects. All objects inside an archive can link to each other (headings, code blocks, etc) without any issues. Uses file extension *.larc, and is encoded as JSON.
backlinks
↑ 22 A map where the keys are the paths (of objects) and the values are the backlinks to that object. We use a map because we want to organize all of the backlinks by the document they are starting out from. The actual backlinks are just edges between cells (vertices), where the edges are created by a reference (via data:LinkOid) from one cell to another. They are based on newtype:PseudoEdge which are constructed in f:oidLinkParser. See f:weaveBacklinks for how they are used during weaving.
bibs
↑ 26 Collection of all bibliography files used by documents. See CSL JSON (bibliographical entries). Needed for processing Citations and printing bibliographies. See Citation dependencies.
csls
↑ 25 Collection of CSL paths and their raw XML values (see CSL style file (XML)). We have to store the information as a Text value, because there is no ToJSON instance for the Citeproc.Types.Style type. Typically csls will have at most a handful of entries, because most (if not all) documents inside an archive will all use the same CSL style. Needed for processing Citations and printing bibliographies. See Citation dependencies.
glossary
↑ 21 This is the combined set of all glossary terms found in all objects. The main difference is that the key includes not just the term itself (Text) but also the path of the object to identify which object has this term. This also avoids clashes because two documents could very well define the same glossary term (in different ways).
object
↑ An even more machine-friendly representation of a single Org document. Uses file extension *.lobj, and is encoded as JSON.
offsets
↑ 23 The offset of each object's cells, in relation to the global (flattened) list of all cells in the archive. This is used to convert a GCI back into an LCI (so that we can look up the actual cell at this index inside the object).
symbols
↑ 19 A table for finding the cell by its GCI based on a given data:LinkOid. It could be the case that the user decides to link to the top-level UUID of the document data:OrgDoc → 1. This presents a problem because documents are not cells (they contain cells) so using a GCI doesn't really make sense. So instead we use negative numbers so as not to collide with the regular cell index numbers. See f:docOidsToSymbols.

8 Bibliography

[1]
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. Cambridge, Mass: MIT Press, 2009.

Page metrics

Backlinks (33)

  1. parse.org (10)
    1. data:Archive (3)
      1. ¶ (Cell 43)
      2. ¶ (Cell 398)
      3. ¶ (Cell 1350)
    2. f:buildGraph ← ¶ (Cell 454)
    3. f:finalizeEdges ← ¶ (Cell 43)
    4. f:mkArchive ← ¶ (Cell 43)
    5. f:mkBacklinks ← ¶ (Cell 43)
    6. f:mkSymbols ← ¶ (Cell 898)
    7. ti:0401-broken-links-line-label ← ¶ (Cell 443)
    8. § 4.4 Cycle detection for Noweb links ← ¶ (Cell 974)
  2. weave.org (9)
    1. data:Archive (3)
      1. ¶ (Cell 13)
      2. ¶ (Cell 22)
      3. ¶ (Cell 293)
    2. data:Object (3)
      1. ¶ (Cell 13)
      2. ¶ (Cell 78)
      3. ¶ (Cell 235)
    3. f:stripLinks ← ¶ (Cell 444)
    4. f:stripStyles ← ¶ (Cell 446)
    5. § 4.6 Backlinks ← ¶ (Cell 664)
  3. cli.org (8)
    1. data:Archive (4)
      1. ¶ (Cell 15)
      2. ¶ (Cell 19)
      3. ¶ (Cell 40)
      4. ¶ (Cell 79)
    2. data:Object (2)
      1. ¶ (Cell 19)
      2. ¶ (Cell 79)
    3. f:mkArchive ← ¶ (Cell 82)
    4. f:mkObject ← ¶ (Cell 76)
  4. tangle.org (3)
    1. data:Archive (2)
      1. ¶ (Cell 16)
      2. ¶ (Cell 88)
    2. ^ Top ← ¶ (Cell 3)
  5. build.org (1)
    1. ^ Top ← ¶ (Cell 152)
  6. index.org (1)
    1. ^ Top ← ✿ compile.org
  7. types.org (1)
    1. instance:ToJSONKey LinkOid ← ¶ (Cell 20)

Tangled files (36)

  1. image/cycles.pikchr
  2. src/Lilac/Compile.hs
  3. test/Lilac/CompileSpec.hs
  4. test/Lilac/CompileSpec/0100-dag-2-node-loop
  5. test/Lilac/CompileSpec/0100-dag-2-node-loop-2-files-child
  6. test/Lilac/CompileSpec/0100-dag-2-node-loop-2-files-parent
  7. test/Lilac/CompileSpec/0100-dag-2-node-loop-2-files-parent-heading
  8. test/Lilac/CompileSpec/0100-dag-2-node-loop-3-files-child
  9. test/Lilac/CompileSpec/0100-dag-2-node-loop-3-files-middleman
  10. test/Lilac/CompileSpec/0100-dag-2-node-loop-3-files-parent
  11. test/Lilac/CompileSpec/0100-dag-2-node-loop-heading
  12. test/Lilac/CompileSpec/0100-dag-3-node-loop
  13. test/Lilac/CompileSpec/0100-dag-complex-loops
  14. test/Lilac/CompileSpec/0100-dag-no-loops
  15. test/Lilac/CompileSpec/0100-dag-self-loop
  16. test/Lilac/CompileSpec/0100-dag-self-loop-heading
  17. test/Lilac/CompileSpec/0100-dag-self-loops
  18. test/Lilac/CompileSpec/0105/basic/bar.org
  19. test/Lilac/CompileSpec/0105/basic/foo.org
  20. test/Lilac/CompileSpec/0105/basic/index.org
  21. test/Lilac/CompileSpec/0105/foo.org
  22. test/Lilac/CompileSpec/0105/index.org
  23. test/Lilac/CompileSpec/0105/invalid-paths-self/index.org
  24. test/Lilac/CompileSpec/0105/invalid-paths/index.org
  25. test/Lilac/CompileSpec/0400-external-symbols
  26. test/Lilac/CompileSpec/0400-external-symbols-newlines
  27. test/Lilac/CompileSpec/0400-no-external-symbols-code-blocks
  28. test/Lilac/CompileSpec/0400-no-external-symbols-complex
  29. test/Lilac/CompileSpec/0401-broken-links-line-label
  30. test/Lilac/CompileSpec/0401-broken-links-multi-ok
  31. test/Lilac/CompileSpec/0401-broken-links-multi-ok-alternates-child
  32. test/Lilac/CompileSpec/0401-broken-links-multi-ok-alternates-parent
  33. test/Lilac/CompileSpec/0401-broken-links-multi-ok-dependency
  34. test/Lilac/CompileSpec/0401-broken-links-noweb
  35. test/Lilac/CompileSpec/0401-broken-links-paragraph
  36. test/Lilac/CompileSpec/0401-broken-links-paragraph-ok

Named cells (120)

  1. All test cases
  2. CompileSpec helpers
  3. data:Archive
  4. data:Object
  5. data:PathState
  6. f:buildGraph
  7. f:checkCycles
  8. f:checkExternalLinkOids
  9. f:combineSymbolsAndGlossary
  10. f:cumulativeOffsets
  11. f:docOidsToSymbols
  12. f:expectArchiveError
  13. f:expectArchiveOk
  14. f:expectGTOC
  15. f:finalizeEdges
  16. f:findBrokenFileLinks
  17. f:findBrokenLinks
  18. f:findCycles
  19. f:findExternalOids
  20. f:findRootIndex
  21. f:gciToName
  22. f:gciToObjCell
  23. f:gciToObjPath
  24. f:getBibliographies
  25. f:getBibliography
  26. f:getBlockGCIsFromArchive
  27. f:getBlocksFromArchive
  28. f:getCellName
  29. f:getChildPaths
  30. f:getCitationDeps
  31. f:getCitationStyle
  32. f:getCitationStyles
  33. f:getLineLabels
  34. f:getSymbols
  35. f:isIndexObjPath
  36. f:makeRelativeToObjectPath
  37. f:mkArchive
  38. f:mkBacklinks
  39. f:mkBlockAncestry
  40. f:mkGTOC
  41. f:mkObject
  42. f:mkOffsets
  43. f:mkSymbols
  44. f:parseBibliography
  45. f:parseCitationStyle
  46. f:parseJSONLinkOid
  47. f:prependOffsets
  48. f:readObjectsFrom
  49. f:stripLinks
  50. f:stripStyles
  51. fig:cycles
  52. fig:cycles.pikchr
  53. instance:FromJSON LinkOid
  54. instance:FromJSONKey LinkOid
  55. instance:ToJSON LinkOid
  56. instance:ToJSONKey LinkOid
  57. module:Lilac.Compile
  58. module:Lilac.CompileSpec
  59. newtype:GCI
  60. newtype:GTOC
  61. t:0100-dag-2-node-loop
  62. t:0100-dag-2-node-loop-2-files
  63. t:0100-dag-2-node-loop-2-files-heading
  64. t:0100-dag-2-node-loop-3-files
  65. t:0100-dag-2-node-loop-heading
  66. t:0100-dag-3-node-loop
  67. t:0100-dag-complex-loops
  68. t:0100-dag-no-loops
  69. t:0100-dag-self-loop
  70. t:0100-dag-self-loop-heading
  71. t:0100-dag-self-loops
  72. t:0105-gtoc-basic
  73. t:0105-gtoc-invalid-paths
  74. t:0105-gtoc-invalid-paths-self
  75. t:0105-gtoc-no-root-index
  76. t:0105-gtoc-root-index-without-index-block
  77. t:0400-external-symbols
  78. t:0400-external-symbols-newlines
  79. t:0400-no-external-symbols-code-blocks
  80. t:0400-no-external-symbols-complex
  81. t:0401-broken-links-line-label
  82. t:0401-broken-links-multi-ok
  83. t:0401-broken-links-multi-ok-alternates
  84. t:0401-broken-links-noweb
  85. t:0401-broken-links-paragraph
  86. t:0401-broken-links-paragraph-ok
  87. t:0500-cumulativeOffsets-sanity
  88. ti:0100-dag-2-node-loop
  89. ti:0100-dag-2-node-loop-2-files-child
  90. ti:0100-dag-2-node-loop-2-files-parent
  91. ti:0100-dag-2-node-loop-2-files-parent-heading
  92. ti:0100-dag-2-node-loop-3-files-child
  93. ti:0100-dag-2-node-loop-3-files-middleman
  94. ti:0100-dag-2-node-loop-3-files-parent
  95. ti:0100-dag-2-node-loop-heading
  96. ti:0100-dag-3-node-loop
  97. ti:0100-dag-complex-loops
  98. ti:0100-dag-no-loops
  99. ti:0100-dag-self-loop
  100. ti:0100-dag-self-loop-heading
  101. ti:0100-dag-self-loops
  102. ti:0105-gtoc-basic-bar
  103. ti:0105-gtoc-basic-foo
  104. ti:0105-gtoc-basic-index
  105. ti:0105-gtoc-invalid-paths
  106. ti:0105-gtoc-invalid-paths-self
  107. ti:0105-gtoc-no-root-index
  108. ti:0105-gtoc-root-index-without-index-block
  109. ti:0400-external-symbols
  110. ti:0400-external-symbols-newlines
  111. ti:0400-no-external-symbols-code-blocks
  112. ti:0400-no-external-symbols-complex
  113. ti:0401-broken-links-line-label
  114. ti:0401-broken-links-multi-ok
  115. ti:0401-broken-links-multi-ok-alternates-child
  116. ti:0401-broken-links-multi-ok-alternates-parent
  117. ti:0401-broken-links-multi-ok-dependency
  118. ti:0401-broken-links-noweb
  119. ti:0401-broken-links-paragraph
  120. ti:0401-broken-links-paragraph-ok