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.