"An algorithm for parsing nested emphasis and links" is outdated

[mity]

In https://spec.commonmark.org/0.28/#phase-2-inline-structure, at least the section called "An algorithm for parsing nested emphasis and links" is outdated, as it operates with single delimiter stack.

Given "the rule of three" in parsing *-styled intraword delimiter runs, single stack implementation has worst case O(n^2) as mity/md4c#63 shows. Even Cmark uses multiple stacks for * delimiter runs, if I understand correctly the code you pointed to.

[jgm]

I'm not sure I understand. cmark does use a single stack. However, it uses a map keyed to delimiter types to keep track of the "openers bottom" for each type. (This is documented in the section on parsing emphasis.)

We keep track of the openers_bottom for each delimiter type (*, _). Initialize this to stack_bottom.

[mity]

Yes, I missed there are multiple pointers into it, and "stack with multiple bottoms" is more or less equivalent to "multiple stacks".

But still, there is this sentence:

We keep track of the openers_bottom for each delimiter type (*, _).

which suggests you have single openers_bottom for all *-based openers, which is not enough because then the input "x***" * 5000 leads to O(n^2).

There should be some description that you need multiple openers_bottom for *-based openers so that you can find appropriate opener for given closer fast with the respect to the "rule of three" (you have to use the one most recent which is compatible with the current closer, given properties of the opener and properties of the closer).