Exponential-time parsing for non-closed fenced divs

[heatherleaf]

Pandoc version?

3.1.12.3

Explain the problem

If you accidentally forget to close a fenced div, the parser becomes extremely slow. Here's a minmal example:

#!/bin/bash

base="
# Here's an example
::: tag
This is a fenced div that's not closed.
"

echo > test.md
for ((i=1;i<=100;i++)); do 
    echo "$base" >> test.md
    echo -n "# $i:    "
    /usr/bin/time pandoc --metadata title="title" -o test.html test.md
done

On my computer I get this:

...
# 10:            0,14 real         0,13 user         0,00 sys
# 11:            0,28 real         0,27 user         0,00 sys
# 12:            0,53 real         0,52 user         0,00 sys
# 13:            1,07 real         1,05 user         0,00 sys
# 14:            2,08 real         2,06 user         0,00 sys
# 15:            4,15 real         4,13 user         0,01 sys
# 16:            8,31 real         8,28 user         0,01 sys
# 17:           16,66 real        16,61 user         0,02 sys
# 18:           33,37 real        33,28 user         0,03 sys
# 19:           68,65 real        68,49 user         0,07 sys
...

Solution suggestion

Any of these two should be fine:

• When you reach a new section title: auto-close the fenced div, or report an error, or a warning
• When you reach the end of the markdown file and there are still open fenced divs: auto-close, or report error/warning

Yes, sometimes you want section titles within a fenced div, but many times not. So perhaps a new cmd-line option where you can say how to handle nested fenced divs / sections. Perhaps a maximum nesting depth?

[jgm]

Section titles inside divs are okay. But perhaps the auto-close behavior would be sensible.

Note that commonmark_x already has the auto-close behavior.

[heatherleaf]

I also don't mind the current semantics, but the exponential behaviour is a problem. It took me several hours to understand why Pandoc all of a sudden became so slow, until I found out I had accidentally removed some closing divs

[jgm]

Agreed. I think I will implement the auto-close behavior (along with a warning).

[jgm]

New behavior with the above script:

# 1:    [WARNING] Div at test.md line 4 column 1 unclosed at test.md line 8 column 1, closing implicitly.

real	0m2.495s
user	0m0.415s
sys	0m0.098s
# 2:    [WARNING] Div at test.md line 9 column 1 unclosed at test.md line 13 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 13 column 1, closing implicitly.

real	0m0.230s
user	0m0.156s
sys	0m0.039s
# 3:    [WARNING] Div at test.md line 14 column 1 unclosed at test.md line 18 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 18 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 18 column 1, closing implicitly.

real	0m0.203s
user	0m0.152s
sys	0m0.031s
# 4:    [WARNING] Div at test.md line 19 column 1 unclosed at test.md line 23 column 1, closing implicitly.
[WARNING] Div at test.md line 14 column 1 unclosed at test.md line 23 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 23 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 23 column 1, closing implicitly.

real	0m0.203s
user	0m0.149s
sys	0m0.030s
# 5:    [WARNING] Div at test.md line 24 column 1 unclosed at test.md line 28 column 1, closing implicitly.
[WARNING] Div at test.md line 19 column 1 unclosed at test.md line 28 column 1, closing implicitly.
[WARNING] Div at test.md line 14 column 1 unclosed at test.md line 28 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 28 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 28 column 1, closing implicitly.

real	0m0.203s
user	0m0.149s
sys	0m0.030s
# 6:    [WARNING] Div at test.md line 29 column 1 unclosed at test.md line 33 column 1, closing implicitly.
[WARNING] Div at test.md line 24 column 1 unclosed at test.md line 33 column 1, closing implicitly.
[WARNING] Div at test.md line 19 column 1 unclosed at test.md line 33 column 1, closing implicitly.
[WARNING] Div at test.md line 14 column 1 unclosed at test.md line 33 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 33 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 33 column 1, closing implicitly.

real	0m0.203s
user	0m0.150s
sys	0m0.031s
# 7:    [WARNING] Div at test.md line 34 column 1 unclosed at test.md line 38 column 1, closing implicitly.
[WARNING] Div at test.md line 29 column 1 unclosed at test.md line 38 column 1, closing implicitly.
[WARNING] Div at test.md line 24 column 1 unclosed at test.md line 38 column 1, closing implicitly.
[WARNING] Div at test.md line 19 column 1 unclosed at test.md line 38 column 1, closing implicitly.
[WARNING] Div at test.md line 14 column 1 unclosed at test.md line 38 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 38 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 38 column 1, closing implicitly.

real	0m0.203s
user	0m0.151s
sys	0m0.032s
# 8:    [WARNING] Div at test.md line 39 column 1 unclosed at test.md line 43 column 1, closing implicitly.
[WARNING] Div at test.md line 34 column 1 unclosed at test.md line 43 column 1, closing implicitly.
[WARNING] Div at test.md line 29 column 1 unclosed at test.md line 43 column 1, closing implicitly.
[WARNING] Div at test.md line 24 column 1 unclosed at test.md line 43 column 1, closing implicitly.
[WARNING] Div at test.md line 19 column 1 unclosed at test.md line 43 column 1, closing implicitly.
[WARNING] Div at test.md line 14 column 1 unclosed at test.md line 43 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 43 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 43 column 1, closing implicitly.

real	0m0.203s
user	0m0.151s
sys	0m0.031s
# 9:    [WARNING] Div at test.md line 44 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 39 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 34 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 29 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 24 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 19 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 14 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 48 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 48 column 1, closing implicitly.

real	0m0.203s
user	0m0.151s
sys	0m0.031s
# 10:    [WARNING] Div at test.md line 49 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 44 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 39 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 34 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 29 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 24 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 19 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 14 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 9 column 1 unclosed at test.md line 53 column 1, closing implicitly.
[WARNING] Div at test.md line 4 column 1 unclosed at test.md line 53 column 1, closing implicitly.

real	0m0.215s
user	0m0.153s
sys	0m0.040s

[heatherleaf]

Wow that was quick! 🙏🙏

[heatherleaf]

Just a curious question: what’s the rule now for autoclose?

I tried to read your code… does it autoclose when it encounters a new fenced div on the same level? (The same or fewer number of “:”s?)

[jgm]

It will auto-close in exactly the situations where previously it would have given up parsing as a div and backtracked. So, not when it encounters a new fenced div on the same level. It will accept this as a nested div (as before).