Tangle


1 Overview

In Literate Programming, tangling is the act of extracting just the source code out of a document. It is the opposite of documentation generation found in many programming language environments, such as javadoc, where documentation is extracted from source code.

2 Lilac.Tangle module

This module is quite short, because much of the hard work around validation (no broken links, no cycles) are handled in Compile.

module:Lilac.Tangle
🎯 src/Lilac/Tangle.hs
module Lilac.Tangle (expandRootBlocks) where

import Data.Text qualified as T
import Lilac.Types
  ( Archive (objects, symbols),
    BToken (BTokenLinkTarget, BTokenPadding, BTokenString),
    Block (body, meta),
    Cell (CBlock),
    LCI (unLCI),
    LinkOid (name),
    LinkTarget (LinkTargetLineLabel, LinkTargetOid),
    Object (orgDoc, symbols),
    OrgDoc (cells),
    gciToObjCell,
  )
import Relude
  ( Bool (False, True),
    Maybe (Just),
    Text,
    concat,
    foldl',
    fst,
    map,
    otherwise,
    reverse,
    (!!?),
    ($),
    (.),
    (/=),
    (<>),
    (==),
  )
import Relude.Extra.Map (lookup)
import System.OsPath (OsPath)
import System.OsPath qualified as P

f:expandRootBlocks
f:expandRootBlock
f:expandBlock
f:getPrefix
f:prependExistingPrefix
f:prefixTailLines

3 Tangling algorithm

Tangling essentially boils down to the following:

  1. find all code blocks that need to get tangled (they have #+header: :tangle ... in their metadata), which we call root blocks, and

  2. for each of these code blocks expand any Noweb references in them until none are left, and finally

  3. write the files to disk (but only for those files that are different than what we already have on disk).

The first two steps are the bare minimum required in order to feed source code to the computer for interpretation by it. The third step only writes files if they're different than what's on the disk, because otherwise the modification timestamps will change; this is not good if we are using a Makefile (because they use those timestamps to determine whether a rule needs to be run again).

3.1 Block expansion

We examine the given data:Archive for all of the root blocks in it, and expand each one in f:expandRootBlocks. The output is a list of tuples, where each tuple encodes the filesystem path where we want to write content (text), and the contents themselves --- hence the type is (OsPath, Text).

f:expandRootBlocks
expandRootBlocks :: Archive -> OsPath -> [(OsPath, Text)]
expandRootBlocks archive outDir =
  map (expandRootBlock archive) rootBlocks
  where
    rootBlocks =
      concat $ foldl' getRootBlocksFromObject [] archive.objects
    getRootBlocksFromObject ::
      [[(OsPath, Block)]] ->
      Object ->
      [[(OsPath, Block)]]
    getRootBlocksFromObject acc object =
      foldl' (getRootBlock object.orgDoc.cells) [] object.symbols : acc
    getRootBlock cells acc lci -- 1
      | Just (CBlock b) <- cells !!? lci.unLCI,
        Just tPath <- lookup "tangle" b.meta,
        Just tOsPath <- P.encodeUtf $ T.unpack tPath =
          (P.combine outDir tOsPath, b) : acc
      | otherwise = acc

f:expandRootBlocks is mainly concerned with collecting all of the root blocks first 1 before handing them off to f:expandRootBlock for the actual block expansions (where "expansion" just means converting any Noweb links we find with the actual contents of that linked code block).

f:expandRootBlock
expandRootBlock :: Archive -> (OsPath, Block) -> (OsPath, Text)
expandRootBlock archive (tanglePath, rootBlock) =
  ( tanglePath,
    maybeAddShebang rootBlock -- 2
      . trimTrailingSpaces -- 3
      $ expandBlock archive rootBlock ""
  )
  where
    trimTrailingSpaces :: Text -> Text
    trimTrailingSpaces text =
      T.unlines
        . map (T.dropWhileEnd (== ' '))
        $ T.lines text
    maybeAddShebang :: Block -> Text -> Text
    maybeAddShebang block text
      | Just shebang <- lookup "shebang" block.meta =
          shebang <> "\n" <> text
      | otherwise = text

We add a special shebang line at the beginning of the file 2, if one was specified using the :shebang header. See unit-test.sh for an example.

We also trim lines with only spaces in them 3, because these can happen from the prependExistingPrefix function in f:expandBlock.

Finally in f:expandBlock, we recursively expand all Noweb links (linkOid) until there are none 5.

f:expandBlock
expandBlock :: Archive -> Block -> Text -> Text
expandBlock archive block existingPrefix =
  let acc = "" :: Text
      prefix = "" :: Text
   in fst $ foldl' expand (acc, prefix) block.body
  where
    expand (acc, _) BTokenPadding =
      (acc <> "\n", "")
    expand (acc, _) (BTokenString text) =
      (acc <> prependExistingPrefix existingPrefix text, getPrefix text) -- 4
    expand (acc, prefix) (BTokenLinkTarget (LinkTargetOid linkOid)) -- 5
      | Just gci <- lookup linkOid archive.symbols,
        Just (_, (CBlock targetBlock)) <- gciToObjCell archive gci =
          ( acc <> (expandBlock archive targetBlock $ existingPrefix <> prefix),
            prefix
          )
      | otherwise = (acc, prefix)
    expand (acc, prefix) (BTokenLinkTarget (LinkTargetLineLabel lineLabel))
      | Just "tangle" <- lookup "line-label" block.meta =
          ( acc <> "(ref:" <> (T.drop 1 $ T.dropEnd 1 lineLabel.name) <> ")",
            prefix
          )
      | otherwise = (acc, prefix)
    expand (acc, prefix) _ = (acc, prefix)

The other main concern of f:expandBlock is the business around prefixes. Essentially, whenever we expand a Noweb link, we want to treat any preceding text on the same line as the link as a special prefix that we use for all expanded lines. For example, in the following block

    <<foo>>

all of the lines inside the <<foo>> block should inherit the 4-space indentation, which we call a prefix here because it can also take into account non-space characters.

f:getPrefix
getPrefix :: Text -> Text
getPrefix text = T.takeWhileEnd (/= '\n') text

When we encounter a BTokenString token in f:expandBlock 4 we search for a prefix with f:getPrefix. See ti:0101-block-expansion-prefix and ti:0101-block-expansion-prefix-nested for examples using indentation as prefixes, and ti:0101-block-expansion-prefix-nonspace and ti:0101-block-expansion-prefix-nonspace-nested for examples of non-space-based prefixes.

f:prependExistingPrefix splits up the given text, and injects the prefix on every line in the text except the very first line.

f:prependExistingPrefix
prependExistingPrefix :: Text -> Text -> Text
prependExistingPrefix existingPrefix text =
  T.intercalate "\n"
    . reverse
    . fst
    . foldl' (prefixTailLines existingPrefix) ([], True)
    $ T.split (== '\n') text

We need this function because given the text

xx<<a>>

where xx is the prefix, we only want to give this prefix to the lines in <<a>> except the first line (because the first line of <<a>> is already prefixed (from the outer block) with xx); so only the lines after the first line in <<a>> need the xx prefix. This is what we do in f:prefixTailLines, where we avoid adding the prefix to the "head", and instead only add it to the "tail."

f:prefixTailLines
prefixTailLines :: Text -> ([Text], Bool) -> Text -> ([Text], Bool)
prefixTailLines existingPrefix (acc, isFirstLine) line
  | isFirstLine = (line : acc, False)
  | otherwise = (T.append existingPrefix line : acc, False)

Going back to f:prependExistingPrefix, we use T.intercalate and T.split, to avoid losing any information about the exact locations of newlines. If we used T.lines we would lose information about whether the last line actually had a trailing newline, because T.lines "a\nb" and T.lines "a\nb\n" both give ["a", "b"]. For a demonstration of this lossy behavior, see the test case below.

t:lines-unlines-info-loss
it "loses information" $ do
  let withoutNewline = T.lines "a\nb"
      withNewline = T.lines "a\nb\n"
  T.unlines withoutNewline `shouldBe` T.unlines withNewline

3.2 Tests

Expand a single code block.

ti:0101-block-expansion
🎯 test/Lilac/TangleSpec/0101-block-expansion
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e007
:END:

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

#+name: b
#+begin_src haskell
b
#+end_src
t:0101-block-expansion
checkExpansion
  ["0101-block-expansion"]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "b",
          "a2"
        ]
    )
  ]

Expand many code blocks in the same place, but the number of repeated expansions shouldn't result in a cumulative number of newlines; we should expect just one newline for the expanded content.

ti:0101-block-expansion-deeply-nested
🎯 test/Lilac/TangleSpec/0101-block-expansion-deeply-nested
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e008
:END:

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

#+name: b
#+begin_src haskell
<<c>>
#+end_src

#+name: c
#+begin_src haskell
<<d>>
#+end_src

#+name: d
#+begin_src haskell
<<e>>
#+end_src

#+name: e
#+begin_src haskell
e
#+end_src
t:0101-block-expansion-deeply-nested
checkExpansion
  ["0101-block-expansion-deeply-nested"]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "e",
          "a2"
        ]
    )
  ]

If the link name is indented, we have to indent the contents of that block.

ti:0101-block-expansion-prefix
🎯 test/Lilac/TangleSpec/0101-block-expansion-prefix
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e009
:END:

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

#+name: b
#+begin_src haskell
b1
b2
b3
#+end_src
t:0101-block-expansion-prefix
checkExpansion
  ["0101-block-expansion-prefix"]
  [ ( "equations.txt",
      T.unlines
        [ "  b1",
          "  b2",
          "  b3",
          "a1",
          "  b1",
          "  b2",
          "  b3"
        ]
    )
  ]

The indentation can be nested. For example if the named block itself links to other blocks with an indent, those inner blocks should be indented with the sum of the indent found in the current and outer surrounding blocks.

ti:0101-block-expansion-prefix-nested
🎯 test/Lilac/TangleSpec/0101-block-expansion-prefix-nested
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e00a
:END:

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

#+name: b
#+begin_src haskell
b1
b2
b3
  <<c>>
#+end_src

#+name: c
#+begin_src haskell
c1
c2
#+end_src
t:0101-block-expansion-prefix-nested
checkExpansion
  ["0101-block-expansion-prefix-nested"]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "  b1",
          "  b2",
          "  b3",
          "    c1",
          "    c2"
        ]
    )
  ]

The prefix is any string, up to the (preceding) newline. So this mean it can have non-space characters in it as well.

ti:0101-block-expansion-prefix-nonspace
🎯 test/Lilac/TangleSpec/0101-block-expansion-prefix-nonspace
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e00b
:END:

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

#+name: b
#+begin_src haskell
b1
b2
b3
#+end_src
t:0101-block-expansion-prefix-nonspace
checkExpansion
  ["0101-block-expansion-prefix-nonspace"]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "  -> b1",
          "  -> b2",
          "  -> b3"
        ]
    )
  ]

Non-space prefixes can also be nested.

ti:0101-block-expansion-prefix-nonspace-nested
🎯 test/Lilac/TangleSpec/0101-block-expansion-prefix-nonspace-nested
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e00c
:END:

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

#+name: b
#+begin_src haskell
b1
b2
b3
-- <<c>>
#+end_src

#+name: c
#+begin_src haskell
c1
c2
#+end_src
t:0101-block-expansion-prefix-nonspace-nested
checkExpansion
  ["0101-block-expansion-prefix-nonspace-nested"]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "  -> b1",
          "  -> b2",
          "  -> b3",
          "  -> -- c1",
          "  -> -- c2"
        ]
    )
  ]

The following test case has some complex expansions.

ti:0101-block-expansion-complex
🎯 test/Lilac/TangleSpec/0101-block-expansion-complex
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e00d
:END:

#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
a1
<<b>>
a2
  <<c>>
a3
<<g>>
<<h>>
#+end_src

#+name: b
#+begin_src haskell
b
#+end_src

#+name: c
#+begin_src haskell
c
c
  <<d>>
c
#+end_src

#+name: d
#+begin_src haskell
d

d
<<e>>
#+end_src

#+name: e
#+begin_src haskell
e <<f>>!
#+end_src

#+name: f
#+begin_src haskell
hello
#+end_src

#+name: g
#+begin_src haskell
g
#+end_src

#+name: h
#+begin_src haskell
h
#+end_src
t:0101-block-expansion-complex
checkExpansion
  ["0101-block-expansion-complex"]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "b",
          "a2",
          "  c",
          "  c",
          "    d",
          "",
          "    d",
          "    e hello!",
          "  c",
          "a3",
          "g",
          "",
          "h"
        ]
    )
  ]

Due to f:padConsecutiveNowebLinks, insert extra newlines between consecutive Noweb links.

Sometimes we want to use Noweb links on the same line as existing code, surrounded by other text. In these cases we shouldn't do any padding, because adding padding makes sense only when the link is at the very end (otherwise, we could end up introducing a newline right in the middle of a line). In the test case below the links to <<b1>> and <<b2>> have a trailing comma, so it doesn't make sense to add a newline between the link and the comma.

Insert shebang lines if the user specifies them with the :shebang header.

ti:0103-shebang
🎯 test/Lilac/TangleSpec/0103-shebang
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e00f
:END:

#+name: a
#+header: :tangle a.sh
#+header: :shebang #!/usr/bin/env bash
#+begin_src sh
a1
#+end_src
t:0103-shebang
checkExpansion
  ["0103-shebang"]
  [ ( "a.sh",
      T.unlines
        [ "#!/usr/bin/env bash",
          "a1"
        ]
    )
  ]

Expand blocks even if they have Noweb links that point to a block from an external file.

ti:0101-block-expansion-external-parent
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-parent
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e010
:END:

#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
a1
<<id:00000000-0000-0000-0000-00000000f000::a>>
a2
#+end_src
ti:0101-block-expansion-external-child
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-child
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f000
:END:
#+name: a
#+begin_src haskell
hello from child
#+end_src
t:0101-block-expansion-external
checkExpansion
  [ "0101-block-expansion-external-parent",
    "0101-block-expansion-external-child"
  ]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "hello from child",
          "a2"
        ]
    )
  ]

The expansion should work for external Noweb links which refer to a block using a heading's ID, not the ID that's set at the file level.

ti:0101-block-expansion-external-headingchild-parent
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-headingchild-parent
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e011
:END:

#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
a1
<<id:00000000-0000-0000-0000-00000000f00a::a>>
a2
#+end_src
ti:0101-block-expansion-external-headingchild
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-headingchild
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f009
:END:

* A heading
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f00a
:END:

#+name: a
#+begin_src haskell
hello from child
#+end_src
t:0101-block-expansion-external-headingchild
checkExpansion
  [ "0101-block-expansion-external-headingchild-parent",
    "0101-block-expansion-external-headingchild"
  ]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "hello from child",
          "a2"
        ]
    )
  ]

An external block itself can refer to another external block. In t:0101-block-expansion-external-2-hops we use a middleman that itself refers to the external child block from t:0101-block-expansion-external.

ti:0101-block-expansion-external-2-hops-parent
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-2-hops-parent
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000e012
:END:

#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
a1
<<id:00000000-0000-0000-0000-00000000f001::a>>
a2
#+end_src
ti:0101-block-expansion-external-2-hops-middleman
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-2-hops-middleman
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f001
:END:
#+name: a
#+begin_src haskell
hello from middleman
<<id:00000000-0000-0000-0000-00000000f000::a>>
#+end_src
t:0101-block-expansion-external-2-hops
checkExpansion
  [ "0101-block-expansion-external-2-hops-parent",
    "0101-block-expansion-external-2-hops-middleman",
    "0101-block-expansion-external-child"
  ]
  [ ( "equations.txt",
      T.unlines
        [ "a1",
          "hello from middleman",
          "hello from child",
          "a2"
        ]
    )
  ]

We allow two files to refer to each other's code blocks as well, as long as there isn't a cycle.

ti:0101-block-expansion-external-mutual-a
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-mutual-a
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f002
:END:
#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
hello from a
<<id:00000000-0000-0000-0000-00000000f003::b>>
#+end_src

#+name: c
#+begin_src haskell
hello from c
#+end_src
ti:0101-block-expansion-external-mutual-b
🎯 test/Lilac/TangleSpec/0101-block-expansion-external-mutual-b
:PROPERTIES:
:ID:       00000000-0000-0000-0000-00000000f003
:END:
#+name: b
#+begin_src haskell
hello from b
<<id:00000000-0000-0000-0000-00000000f002::c>>
#+end_src
t:0101-block-expansion-external-mutual
checkExpansion
  [ "0101-block-expansion-external-mutual-a",
    "0101-block-expansion-external-mutual-b"
  ]
  [ ( "equations.txt",
      T.unlines
        [ "hello from a",
          "hello from b",
          "hello from c"
        ]
    )
  ]

4 Testing framework

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

4.1 Test module and helpers

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

import Data.Text qualified as T
import Lilac.Compile qualified as LC
import Lilac.Tangle qualified as LT
import Lilac.Types (emptyProjectConf)
import Relude
  ( Either (Left, Right),
    FilePath,
    Text,
    first,
    fmap,
    mempty,
    show,
    ($),
  )
import System.OsPath qualified as P
import Test.Hspec (Spec, expectationFailure, it, runIO, shouldBe)

spec :: Spec
spec = do
  All test cases

f:checkExpansion

The f:checkExpansion function expands all source code blocks (found in the collection of Org documents, first converted into a data:Archive) and compares them with the expected output.

f:checkExpansion
checkExpansion :: [FilePath] -> [(FilePath, Text)] -> Spec
checkExpansion paths expectedExpansions = do
  pathObjs <- runIO $ LC.readObjectsFrom "test/Lilac/TangleSpec/" paths
  maybeArchive <- runIO $ LC.mkArchive emptyProjectConf pathObjs
  case maybeArchive of
    Left errMsg -> it "programmer error" $ expectationFailure errMsg
    Right archive -> it (show paths) $ do
      (LT.expandRootBlocks archive mempty)
        `shouldBe` (fmap (first P.unsafeEncodeUtf) expectedExpansions)

4.2 All test cases

Below are all of the individual test cases.

Page metrics

Tangled files (20)

  1. src/Lilac/Tangle.hs
  2. test/Lilac/TangleSpec.hs
  3. test/Lilac/TangleSpec/0101-block-expansion
  4. test/Lilac/TangleSpec/0101-block-expansion-complex
  5. test/Lilac/TangleSpec/0101-block-expansion-deeply-nested
  6. test/Lilac/TangleSpec/0101-block-expansion-external-2-hops-middleman
  7. test/Lilac/TangleSpec/0101-block-expansion-external-2-hops-parent
  8. test/Lilac/TangleSpec/0101-block-expansion-external-child
  9. test/Lilac/TangleSpec/0101-block-expansion-external-headingchild
  10. test/Lilac/TangleSpec/0101-block-expansion-external-headingchild-parent
  11. test/Lilac/TangleSpec/0101-block-expansion-external-mutual-a
  12. test/Lilac/TangleSpec/0101-block-expansion-external-mutual-b
  13. test/Lilac/TangleSpec/0101-block-expansion-external-parent
  14. test/Lilac/TangleSpec/0101-block-expansion-prefix
  15. test/Lilac/TangleSpec/0101-block-expansion-prefix-nested
  16. test/Lilac/TangleSpec/0101-block-expansion-prefix-nonspace
  17. test/Lilac/TangleSpec/0101-block-expansion-prefix-nonspace-nested
  18. test/Lilac/TangleSpec/0102-pad-between-consecutive-links
  19. test/Lilac/TangleSpec/0102-pad-between-consecutive-links-except-embedded
  20. test/Lilac/TangleSpec/0103-shebang

Named cells (43)

  1. All test cases
  2. f:checkExpansion
  3. f:expandBlock
  4. f:expandRootBlock
  5. f:expandRootBlocks
  6. f:getPrefix
  7. f:prefixTailLines
  8. f:prependExistingPrefix
  9. module:Lilac.Tangle
  10. module:Lilac.TangleSpec
  11. t:0101-block-expansion
  12. t:0101-block-expansion-complex
  13. t:0101-block-expansion-deeply-nested
  14. t:0101-block-expansion-external
  15. t:0101-block-expansion-external-2-hops
  16. t:0101-block-expansion-external-headingchild
  17. t:0101-block-expansion-external-mutual
  18. t:0101-block-expansion-prefix
  19. t:0101-block-expansion-prefix-nested
  20. t:0101-block-expansion-prefix-nonspace
  21. t:0101-block-expansion-prefix-nonspace-nested
  22. t:0102-pad-between-consecutive-links
  23. t:0102-pad-between-consecutive-links-except-embedded
  24. t:0103-shebang
  25. t:lines-unlines-info-loss
  26. ti:0101-block-expansion
  27. ti:0101-block-expansion-complex
  28. ti:0101-block-expansion-deeply-nested
  29. ti:0101-block-expansion-external-2-hops-middleman
  30. ti:0101-block-expansion-external-2-hops-parent
  31. ti:0101-block-expansion-external-child
  32. ti:0101-block-expansion-external-headingchild
  33. ti:0101-block-expansion-external-headingchild-parent
  34. ti:0101-block-expansion-external-mutual-a
  35. ti:0101-block-expansion-external-mutual-b
  36. ti:0101-block-expansion-external-parent
  37. ti:0101-block-expansion-prefix
  38. ti:0101-block-expansion-prefix-nested
  39. ti:0101-block-expansion-prefix-nonspace
  40. ti:0101-block-expansion-prefix-nonspace-nested
  41. ti:0102-pad-between-consecutive-links
  42. ti:0102-pad-between-consecutive-links-except-embedded
  43. ti:0103-shebang