Repository navigation
Understanding The Internals
Warning
AI is used for some parts of this documentation page specifically. I wanted to try out using AI for documentation as this could be extremely useful.
I know some of you have strong feelings about AI so I'll always leave a notice if I've used AI anywhere.
I decided to use AI for this because I was running low on time and I believe I'm not harming anybody using this. After all, writing documentation has no creative or expressional intent.
If you feel differently about this. Feel free to contact me through a github issue and provide me with some good arguments against it.
Anyways everything else ranging from the code all the way to the other documentation, is still written by me :)
This page explains some of the internal systems that make YAMP work. It explains how the different parts of YAMP fit together and work behind the scenes. This page is designed for people that are interested in the inner workings of the parser or want a deeper understanding of the processing.
If you are implementing custom syntax, I recommend reading all of the other pages custom syntax documentation first.
A call to YAMP.parse() goes through a couple of stages:
Markdown
β
βΌ
Split into lines
β
βΌ
Check cache
β
βΌ
Initialise a CharMap (might also be created from cache)
β
βΌ
Parse every line (that isn't cached) into an AST ββ βΊ Modify Char Map
β
βΌ
Generate HTML
β
βΌ
Convert CharMap
β
βΌ
{ html, char_map }
The important thing here is that YAMP does not generate HTML while it is figuring out what the Markdown means during the parsing phase.
First an AST is created. Only after that is each node converted to HTML.
This makes it possible for things like multiline syntax and nested inline syntax to keep their own state without having to deal with already-generated HTML.
Parser
β
ββββββββββββββ΄βββββββββββββ
β β
βΌ βΌ
SingleLineParser InlineParser
β
βΌ
MultilineParser
As you can see, every parser is part of the Parser class. This implements basic things like the PRIORITY, register_escape_chars and escape_text
Then we have InlineParser which implement their custom method for parsing inline syntax.
Next we have the SingleLineParser which implements the main parse method that runs for each line aswell as the parse_inline_method and the generate method.
The MultilineParser is an extension of the SingleLineParser this one implements an extend method, a try_extend helper method and the parse_single_line method
Every enabled SingleLineParser is sorted by their PRIORITY.
For every line, YAMP goes through them in that order:
Parser A
β
βββ FAIL βββΊ Parser B
β
βββ success
β
βΌ
use result
The first parser that successfully parses the line wins.
The normal text parser, Paragraph, is used as the fallback when no other parser accepts the line.
Multiline syntax uses the same parser system instead of having a completely separate parser.
When a line is parsed. Each node can decide to extend the previous node depending on their own conditions.
hello world
this is a newline
test stuff
# Headerwill turn into
line 1 β new Paragraph
line 2 β extend paragraph
line 3 β extend paragraph
line 4 β new Header
This is what YAMP.Parser.EXTEND is used for.
MultilineParser.try_extend() checks the last AST node and calls its extend() method if it belongs to the same parser.
This means the AST node itself stores the state required while the main parser doesn't need to care about any of that.
For example, a code block can keep track of its contents without the main parser needing to know anything about how a code block works.
The parse method of an InlineParser isn't called by the main parser. Instead it's a sub method of the SingleLineParser which can customize on what parts of text inline parsers may work.
Although, inline syntax cannot simply modify the string while it is being parsed.
Consider:
**_hello_**
If the ** parser changes the string first, the indices used by the _ parser are no longer correct which would result in the char map being completely off.
Instead, inline parsers return an array of InlineModifers:
input
β
βββ parser A β modifiers βββ¬ββΊ Modify Char Map
βββ parser B β modifiers βββΌββΊ Modify Char Map
βββ parser C β modifiers βββΌββΊ Modify Char Map
β
βΌ
sort by index
β
βΌ
apply right β left
β
βΌ
modified output string
The modifiers are sorted from the highest index to the lowest index before being applied.
This is important because changing something near the end of a string does not change the indices of anything before it.
The modifier also knows whether the corresponding change should modify the CharMap. This keeps the string transformation and the source-to-HTML mapping separate.
The CharMap starts as a width map.
Each Markdown character has a value describing how many HTML cursor positions belong to it:
| Type | ||||||
|---|---|---|---|---|---|---|
| Markdown: | a | b | c | * | * | d |
| Width: | 0 | 0 | 0 | 255 | 255 | 0 |
| Absolute: | 0 | 1 | 2 | / | / | 5 |
255 means that the character has been discarded. While 0 means a width of one cursor position and 2 means a width of 3 cursor positions
The useful part about this representation is that the Markdown indices never have to move. If some syntax is removed, YAMP just marks those characters as discarded.
Only after parsing and HTML generation are finished is the width map converted into the absolute map returned by parse().
This is also why the CharMap is passed around during parsing instead of being generated afterwards. Parsers already know which source characters they consume.
Sometimes a parser starts modifying the CharMap before it knows whether it will actually succeed.
That would be a problem:
Parser A
β
βββ Modify CharMap
β
βββ FAIL
β
βΌ
Parser B ββββΊ Uses those characters
Parser B would now be working with changes made by a parser that did not even claim the syntax.
The queue solves this.
Input
βββ que_discard_event()
βββ que_extend_event()
βββ parsing succeeds?
/ \
yes no
β |
apply_que() cancel()
The main parser calls cancel_que() before trying another parser, so failed parsing attempts do not leave changes behind.
This is especially useful for syntax where the parser needs to inspect more input before it can be certain that the syntax is valid.
YAMP caches the result of previous parsing operations.
A cache entry can represent 3 states:
-
node(which means we can re-use the object) -
extend(which means that this line didn't change and got extended last time) -
parse_again(which means we have to re-parse the node)
The pipeline is as follows
Markdown
β
βΌ
Split into lines
β
βΌ
Check cache
β
βΌ
Generate a cache entry for each line
β
βΌ
Initialise a CharMap (reuse the char map lines when caching permits)
β
βΌ
Parse every line (that isn't cached) into an AST ββ βΊ Modify Char Map
β
βΌ
Cache the node and input for every parsed line
β
βΌ
Generate HTML
β
βΌ
Cache the generated output for every parsed line
β
βΌ
Cache char map
β
βΌ
Convert CharMap to absolute form
β
βΌ
{ html, char_map }
A normal unchanged line can therefore skip parsing entirely and reuse its generated HTML.
Multiline syntax makes this slightly more interesting.
If line 5 starts a multiline node and line 7 changes:
line 5 β node
line 6 β extend
line 7 β extend β changed
line 8 β extend
YAMP cannot safely reuse lines 5, 6 or 8 by itself. The whole multiline node needs to be parsed again because changing one of its lines can change the meaning of the following lines.
This is why the cache keeps track of which lines belong to the same node.
The CharMap is cached separately from the AST output. This allows both parsing work and mapping work to be reused.
AST nodes contain the information needed to generate their HTML later.
Conceptually:
Markdown
β
βΌ
Parser
β
βΌ
AST node
β
βΌ
generate()
β
βΌ
HTML
This separation is useful for more than just keeping the code organized.
It means the parser can freely work with Markdown indices while generate() can create as much HTML as necessary without changing those indices.
The CharMap is what connects these two representations.
EscapeIncompleteHtml is implemented as an InlineParser, even though it may look more like a final cleanup step.
This is intentional.
Raw HTML needs to be inspected while the source positions are still known. Simply replacing every < with < would also break valid HTML.
The parser therefore keeps track of things such as:
- whether it is currently inside a tag
- quoted attributes
- opening and closing tags
- nested tags
It does not try to implement a complete HTML parser. It only needs enough information to decide whether HTML-looking text should remain HTML or be escaped.
This also explains why disabling the HTML finalizer can cause problems with the CharMap.
Most of the internal complexity in YAMP comes from having to satisfy several requirements at once:
ββββββββββββββββ
β Parsers β
ββββββββ¬ββββββββ
β
βΌ
ββββββββββββββββ
β AST β
ββββββββ¬ββββββββ
β
βΌ
ββββββββββββββββ
β HTML β
ββββββββββββββββ
Each system has a different job:
- Parsers decide what the Markdown means.
- AST nodes keep the state of parsed syntax.
- Inline modifiers allow several inline parsers to modify the same input safely.
- CharMap keeps the connection between Markdown and generated HTML.
- Cache avoids doing the same work again.
Trying to combine these into one transformation would make the implementation considerably harder, especially once multiline syntax, nested modifiers, and cursor positions are involved.
The other documentation pagesx explain how to use these systems and interact with them to create your own syntax. This page should give you enough context to understand the internals of the parser and should give you a kickstart if you'd like to contribute
~ wiki by theblackswitch