diff options
| -rw-r--r-- | algorithm.md | 116 |
1 files changed, 0 insertions, 116 deletions
diff --git a/algorithm.md b/algorithm.md deleted file mode 100644 index 88fe96e..0000000 --- a/algorithm.md +++ /dev/null @@ -1,116 +0,0 @@ -Algorithm for parsing nested links, images, emphasis, and quotes -================================================================ - -When we're parsing inlines and we hit - -- a run of `*` or `_` characters -- a `[` or `![` - -we insert a text node with the literal content, and add a pointer -to this text node to the **delimiter stack.** - -The **delimiter stack** is a doubly linked list. Each -element contains a pointer to a text node, plus information about - -- the type of delimiter (`[`, `![`, `*`, `_`) -- the number of delimiters, -- whether the delimiter is "active" (all are active to start), and -- whether the delimiter is a potential opener, a potential closer, - or both. - -When we hit a `]` character, we call the `look_for_link_or_image` -procedure (see below). - -When we hit the end of the input, we call the `process_emphasis` -procedure (see below), with `stack_bottom` = NULL. - -`look_for_link_or_image` ------------------------- - -Starting at the top of the delimiter stack, we look backwards -through the stack for a `[` or `![` delimiter. - -If we don't find one, we return a literal text node `]`. - -If we do find one, but it's not *active*, we remove the inactive -delimiter from the stack, and return a literal text node `]`. - -If we find one and it's active, then we parse ahead to see if -we have an inline link/image, reference link/image, compact reference -link/image, or shortcut reference link/image. - -If we don't, then we remove the `[` or `![` delimiter from the -delimiter stack and return a literal text node `]`. - -If we do, then - -- We return a link or image node whose children are the inlines - after the text node pointed to by the opening delimiter. - -- We run `process_emphasis` on these inlines, with the `[` opener - as `stack_bottom`. - -- We remove the opening delimiter. - -- If we have a link (and not an image), we also set all - `[` delimiters before the opening delimiter to *inactive*. (This - will prevent us from getting links within links.) - - -`process_emphasis` ------------------- - -Parameter `stack_bottom` sets a lower bound to how far we -descend in the **delimiter stack**. If it is NULL, we can -go all the way to the bottom. Otherwise, we stop before -visiting `stack_bottom`. - -Let `current_position` point to the element on the delimiter -just above `stack_bottom` (or the first element if `stack_bottom` -is NULL). - -We keep track of the `openers_bottom` for each delimiter -type (`*`, `_`). Initialize this to `stack_bottom`. - -Then we repeat the following until we run out of potential -closers: - -- Move `current_position` forward in the delimiter stack (if needed) - until we find the first potential closer with delimiter `*` or `_`. - (This will be the potential closer closest - to the beginning of the input -- the first one in parse order.) - -- Now, look back in the stack (staying above `stack_bottom` and - the `openers_bottom` for this delimiter type) for the - first matching potential opener ("matching" means same delimiter). - -- If one is found: - - - Figure out whether we have emphasis or strong emphasis: - if both closer and opener spans have length >= 2, we have - strong, otherwise regular. - - Insert an emph or strong emph node accordingly, after - the text node corresponding to the opener. - - Remove delimiters between opener and closer from the delimiter - stack. - - Remove 1 (for regular emph) or 2 (for strong emph) delimiters - from the opening and closing text nodes. If they become empty - as a result, remove them and remove the corresponding element - of the delimiter stack. If the closing node is removed, reset - `current_position` to the next element in the stack. - -- If none in found: - - - Set `openers_bottom` to the element before `current_position`. - (We know that there are no openers for this kind of closer up to and - including this point, so this puts a lower bound on future searches.) - - If the closer at `current_position` is not a potential opener, - remove it from the delimiter stack (since we know it can't - be a closer either). - - Advance `current_position` to the next element in the stack. - -- Repeat. - -- After we're done, remove all delimiters above `stack_bottom` from the - delimiter stack. - |