marked 0.3.14 hangs on the attached file, worked in 0.3.9

[paulkoerbitz]

Expectation

example.txt
should be converted to html. This worked with marked 0.3.9.

Result

With marked 0.3.14 marked "hangs" when given the file.

What was attempted

npm install marked@0.3.14
node_modules/marked/bin/marked

[Feder1co5oave]

I'm investigating this.

Commit a8f2d7f introduced this behavior.

It is caused by this piece of markdown:

~~~
move.rs:9:9: 9:22 error: cannot move out of borrowed content
move.rs:9         &MyEnum::Y(y) => println!("{}", *y)  // <-- Error, y cannot be moved out of a reference
                  ^~~~~~~~~~~~~
move.rs:9:20: 9:21 note: attempting to move value to here
move.rs:9         &MyEnum::Y(y) => println!("{}", *y)  // <-- Error, y cannot be moved out of a reference
                             ^
move.rs:9:20: 9:21 help: to prevent the move, use `ref y` or `ref mut y` to capture value by reference
move.rs:9         &MyEnum::Y(y) => println!("{}", *y)  // <-- Error, y cannot be moved out of a reference
                             ^
~~~

[Feder1co5oave]

This causes a hang:

> marked.InlineLexer.rules.tag
/^<!--[\s\S]*?-->|^<\/?[a-zA-Z0-9\-]+(?:"[^"]*"|'[^']*'|\s[^<'">\/]*)*?\/?>/

> marked.InlineLexer.rules.tag.exec(`<-- Error, y cannot be moved out of a reference
...                              ^`)

I don't really understand the reason underlying this.

[paulkoerbitz]

Wow, quick turn around. My guess is that the regex backtracks and that it hangs because of this (Kind of like here: http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016). Can't fully pinpoint the issue though. More info here: https://www.regular-expressions.info/catastrophic.html

[Feder1co5oave]

Thanks @paulkoerbitz, I too thought immediately to catastrophic backtracking but that group (?: ... ) should not be affected by it because its branches are mutually exclusive.
I've worked a patch for this but I wanna be sure it doesn't break anything before posting it.
I'll post it here in a bit and any help would be welcome, since I cannot figure out why that works and the current one doesn't.

[paulkoerbitz]

@Feder1co5oave thank you for the quick replies. I can't really pinpoint it either (but it seems you know a lot more about this than me anyway ;) ) - I've worked around the issue by pinning my dependency to 0.3.9, so from my side the need for a fix is not super urgent.

[Feder1co5oave]

@paulkoerbitz and thank you for reporting and helping. Unfortunately regexes are tricky, and there is no way to determine they run smoothly on every possible input. What I'm trying to work on is to widen our test base.

I think I found it is in fact exponential backtracking. I wrote a script to test this:

const regex = /^<!--[\s\S]*?-->|^<\/?[a-zA-Z0-9\-]+(?:"[^"]*"|'[^']*'|\s[^<'">\/]*)*?\/?>/;
var src = '<-- Error, y cannot be moved out of a reference';

for (let i = 0; i < 18; i++) {
	let begin = process.hrtime();
	regex.exec(src);
	end = process.hrtime(begin);
	console.log(`Matching '${src}' Took ${end[0] * 1000 + end[1] / 10**6} milliseconds`);
	src += ' ';
}

this prints out:

Matching '<-- Error, y cannot be moved out of a reference' Took 0.28264 milliseconds
Matching '<-- Error, y cannot be moved out of a reference ' Took 0.099293 milliseconds
Matching '<-- Error, y cannot be moved out of a reference  ' Took 0.094701 milliseconds
Matching '<-- Error, y cannot be moved out of a reference   ' Took 0.102704 milliseconds
Matching '<-- Error, y cannot be moved out of a reference    ' Took 0.156877 milliseconds
Matching '<-- Error, y cannot be moved out of a reference     ' Took 0.291632 milliseconds
Matching '<-- Error, y cannot be moved out of a reference      ' Took 0.516443 milliseconds
Matching '<-- Error, y cannot be moved out of a reference       ' Took 0.993562 milliseconds
Matching '<-- Error, y cannot be moved out of a reference        ' Took 2.872591 milliseconds
Matching '<-- Error, y cannot be moved out of a reference         ' Took 3.970916 milliseconds
Matching '<-- Error, y cannot be moved out of a reference          ' Took 8.493158 milliseconds
Matching '<-- Error, y cannot be moved out of a reference           ' Took 16.972238 milliseconds
Matching '<-- Error, y cannot be moved out of a reference            ' Took 35.138719 milliseconds
Matching '<-- Error, y cannot be moved out of a reference             ' Took 65.447452 milliseconds
Matching '<-- Error, y cannot be moved out of a reference              ' Took 140.613324 milliseconds
Matching '<-- Error, y cannot be moved out of a reference               ' Took 263.678523 milliseconds
Matching '<-- Error, y cannot be moved out of a reference                ' Took 504.905385 milliseconds
Matching '<-- Error, y cannot be moved out of a reference                 ' Took 1031.746128 milliseconds

with any additional space added, it takes roughly double the time and gets terribly slow pretty soon. So that group needs to be rewritten.

[davisjam]

there is no way to determine they run smoothly on every possible input

This is a good starting place: https://github.com/NicolaasWeideman/RegexStaticAnalysis
Some setup required.

[Feder1co5oave]

@davisjam Thanks! I've been looking for something like this for a while!