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 (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:prefixTailLines3 Tangling algorithm
Tangling essentially boils down to the following:
find all code blocks that need to get tangled (they have #+header: :tangle ... in their metadata), which we call root blocks, and
for each of these code blocks expand any Noweb references in them until none are left, and finally
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).
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 = accf: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).
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 = textWe 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.
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.
getPrefix :: Text -> Text
getPrefix text = T.takeWhileEnd (/= '\n') textWhen 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.
prependExistingPrefix :: Text -> Text -> Text
prependExistingPrefix existingPrefix text =
T.intercalate "\n"
. reverse
. fst
. foldl' (prefixTailLines existingPrefix) ([], True)
$ T.split (== '\n') textWe 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."
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.
it "loses information" $ do
let withoutNewline = T.lines "a\nb"
withNewline = T.lines "a\nb\n"
T.unlines withoutNewline `shouldBe` T.unlines withNewline3.2 Tests
Expand a single code block.
: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_srccheckExpansion
["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.
: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_srccheckExpansion
["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.
: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_srccheckExpansion
["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.
: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_srccheckExpansion
["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.
: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_srccheckExpansion
["0101-block-expansion-prefix-nonspace"]
[ ( "equations.txt",
T.unlines
[ "a1",
" -> b1",
" -> b2",
" -> b3"
]
)
]Non-space prefixes can also be 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_srccheckExpansion
["0101-block-expansion-prefix-nonspace-nested"]
[ ( "equations.txt",
T.unlines
[ "a1",
" -> b1",
" -> b2",
" -> b3",
" -> -- c1",
" -> -- c2"
]
)
]The following test case has some complex expansions.
: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_srccheckExpansion
["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.
:PROPERTIES:
:ID: 00000000-0000-0000-0000-00000000e00e
:END:
#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
a1
<<b1>>
<<b2>>
a2
<<b1>>
<<b2>>
<<b3>>
Even if indentation is different, still pad between them.
<<b1>>
<<b2>>
<<b3>>
Even pad for the same block repeated multiple times.
<<b1>>
<<b1>>
<<b1>>
Lines with multiple links still count as being consecutive.
<<b3>>
<<b3>>
<<b1>> <<b2>>
<<b3>>
<<b3>>
No padding if only one link...
<<b1>>
...is by itself.
#+end_src
#+name: b1
#+begin_src haskell
b1
#+end_src
#+name: b2
#+begin_src haskell
b2
#+end_src
#+name: b3
#+begin_src haskell
b3
#+end_srccheckExpansion
["0102-pad-between-consecutive-links"]
[ ( "equations.txt",
T.unlines
[ "a1",
"b1",
"",
"b2",
"a2",
" b1",
"",
" b2",
"",
" b3",
"Even if indentation is different, still pad between them.",
" b1",
"",
" b2",
"",
" b3",
"Even pad for the same block repeated multiple times.",
" b1",
"",
" b1",
"",
" b1",
"Lines with multiple links still count as being consecutive.",
" b3",
"",
" b3",
"",
" b1 b2",
"",
" b3",
"",
" b3",
"No padding if only one link...",
" b1",
"...is by itself."
]
)
]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.
:PROPERTIES:
:ID: 00000000-0000-0000-0000-00000000e00e
:END:
#+name: a
#+header: :tangle equations.txt
#+begin_src haskell
a1 <<b1>>,
a2 <<b2>>,
a3 <<b3>>
#+end_src
#+name: b1
#+begin_src haskell
b1
#+end_src
#+name: b2
#+begin_src haskell
b2
#+end_src
#+name: b3
#+begin_src haskell
b3
#+end_srccheckExpansion
["0102-pad-between-consecutive-links-except-embedded"]
[ ( "equations.txt",
T.unlines
[ "a1 b1,",
"a2 b2,",
"a3 b3"
]
)
]Insert shebang lines if the user specifies them with the :shebang header.
: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_srccheckExpansion
["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.
: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:PROPERTIES:
:ID: 00000000-0000-0000-0000-00000000f000
:END:
#+name: a
#+begin_src haskell
hello from child
#+end_srccheckExpansion
[ "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.
: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: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_srccheckExpansion
[ "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.
: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:PROPERTIES:
:ID: 00000000-0000-0000-0000-00000000f001
:END:
#+name: a
#+begin_src haskell
hello from middleman
<<id:00000000-0000-0000-0000-00000000f000::a>>
#+end_srccheckExpansion
[ "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.
: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:PROPERTIES:
:ID: 00000000-0000-0000-0000-00000000f003
:END:
#+name: b
#+begin_src haskell
hello from b
<<id:00000000-0000-0000-0000-00000000f002::c>>
#+end_srccheckExpansion
[ "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 (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:checkExpansionThe 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.
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.
t:0101-block-expansion
t:0101-block-expansion-deeply-nested
t:0101-block-expansion-prefix
t:0101-block-expansion-prefix-nested
t:0101-block-expansion-prefix-nonspace
t:0101-block-expansion-prefix-nonspace-nested
t:0101-block-expansion-complex
t:0101-block-expansion-external
t:0101-block-expansion-external-headingchild
t:0101-block-expansion-external-2-hops
t:0101-block-expansion-external-mutual
t:lines-unlines-info-loss
t:0102-pad-between-consecutive-links
t:0102-pad-between-consecutive-links-except-embedded
t:0103-shebangTangled files (20)
- src/Lilac/Tangle.hs
- test/Lilac/TangleSpec.hs
- test/Lilac/TangleSpec/0101-block-expansion
- test/Lilac/TangleSpec/0101-block-expansion-complex
- test/Lilac/TangleSpec/0101-block-expansion-deeply-nested
- test/Lilac/TangleSpec/0101-block-expansion-external-2-hops-middleman
- test/Lilac/TangleSpec/0101-block-expansion-external-2-hops-parent
- test/Lilac/TangleSpec/0101-block-expansion-external-child
- test/Lilac/TangleSpec/0101-block-expansion-external-headingchild
- test/Lilac/TangleSpec/0101-block-expansion-external-headingchild-parent
- test/Lilac/TangleSpec/0101-block-expansion-external-mutual-a
- test/Lilac/TangleSpec/0101-block-expansion-external-mutual-b
- test/Lilac/TangleSpec/0101-block-expansion-external-parent
- test/Lilac/TangleSpec/0101-block-expansion-prefix
- test/Lilac/TangleSpec/0101-block-expansion-prefix-nested
- test/Lilac/TangleSpec/0101-block-expansion-prefix-nonspace
- test/Lilac/TangleSpec/0101-block-expansion-prefix-nonspace-nested
- test/Lilac/TangleSpec/0102-pad-between-consecutive-links
- test/Lilac/TangleSpec/0102-pad-between-consecutive-links-except-embedded
- test/Lilac/TangleSpec/0103-shebang
Named cells (43)
- All test cases
- f:checkExpansion
- f:expandBlock
- f:expandRootBlock
- f:expandRootBlocks
- f:getPrefix
- f:prefixTailLines
- f:prependExistingPrefix
- module:Lilac.Tangle
- module:Lilac.TangleSpec
- t:0101-block-expansion
- t:0101-block-expansion-complex
- t:0101-block-expansion-deeply-nested
- t:0101-block-expansion-external
- t:0101-block-expansion-external-2-hops
- t:0101-block-expansion-external-headingchild
- t:0101-block-expansion-external-mutual
- t:0101-block-expansion-prefix
- t:0101-block-expansion-prefix-nested
- t:0101-block-expansion-prefix-nonspace
- t:0101-block-expansion-prefix-nonspace-nested
- t:0102-pad-between-consecutive-links
- t:0102-pad-between-consecutive-links-except-embedded
- t:0103-shebang
- t:lines-unlines-info-loss
- ti:0101-block-expansion
- ti:0101-block-expansion-complex
- ti:0101-block-expansion-deeply-nested
- ti:0101-block-expansion-external-2-hops-middleman
- ti:0101-block-expansion-external-2-hops-parent
- ti:0101-block-expansion-external-child
- ti:0101-block-expansion-external-headingchild
- ti:0101-block-expansion-external-headingchild-parent
- ti:0101-block-expansion-external-mutual-a
- ti:0101-block-expansion-external-mutual-b
- ti:0101-block-expansion-external-parent
- ti:0101-block-expansion-prefix
- ti:0101-block-expansion-prefix-nested
- ti:0101-block-expansion-prefix-nonspace
- ti:0101-block-expansion-prefix-nonspace-nested
- ti:0102-pad-between-consecutive-links
- ti:0102-pad-between-consecutive-links-except-embedded
- ti:0103-shebang