Performance issue when combining a link with apostrophe and multiple apostrophes in text

[davidbgk]

Explain the problem.

Running pandoc test.md with this file:

Lorem [foo](https://fr.wikipedia.org/wiki/bar'baz) Lorem ips'um dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididun't ut labore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt u't labore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehend'erit in voluptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt ut l'abore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consecte'tur adipisicing elit, sed do eiusmod
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nu'lla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt ut lab'ore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt ut l'abore et do'lore magna aliqua. Ut en'im ad minim veniam,
quis nostrud exercitation ullamco laboris nisi ut aliquip e'x ea commodo
consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamc'o laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehenderit in vol'uptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation u'llamco laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia deserunt mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod
tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam,
quis nostrud exer'citation ullamco laboris nisi ut aliquip ex ea commodo
consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse
cillum dolore eu fugiat nulla pariat'ur. Excepteur sint occaecat cupidatat non
proident, sunt in culpa qui officia de'serunt mo'llit anim id est laborum.

will lead to a significant time to generate the HTML. The more you add ' (apostrophes) within the text, the longer it will take to process the file. It was hard to find a reproductible case :)

Pandoc version?
Latest version (3.7.0.1) installed on macOS using the installer from packages
pandoc-3.7.0.1-x86_64-macOS.pkg, it was working (faster) with 3.6.3.

When using a linux machine with pandoc-3.7.0.1-1-amd64.deb this is not reproductible so it might be related to the macOS packaging?

[jgm]

Very strange. I can't see at the moment why having the link at the beginning should matter. I will look into it.

[davidbgk]

My first guess was related to issue #10631 but it doesn't explain the environment-specific issue.

[jgm]

pandoc.org/try times out (that's on linux).
So I'm skeptical that it is macos only.
(Also there is no way to explain that.)

[davidbgk]

I confirm the bug is still present with the latest version (3.8.2.1 released on Oct, 20).

[TuongNM]

I did a git bisect and found that the performance issue was first introduced with: bf1c17c8

I think what's happening is that with the addition of notFollowedBy linkTitle' the parser:

• encounters the single quote inside the URL
• tries to parse it as a title, looking for the next closing single quote
• determines what's between the single quotes isn't a title
• backtracks but because notFollowedBy linkTitle' is checked at every character position, the failing title checks keep occuring at every single quote
• only after exhausting every single quote does notFollowedBy linkTitle' finish so that the URL parser can continue with parenthesizedChars

Not sure what to do about that while still allowing line breaks between URL and title. But hopefully this analysis will be helpful for others.

[davidbgk]

@TuongNM thank you so much for taking the time to dig into it 🙏

[jgm]

I have a fix; time on this sample goes from 7s to 0.04s.

[jgm]

Thanks @TuongNM for the correct analysis.