Quadratic blowup on pathological input.

[DemiMarie]

This takes ~1s on my machine:

perl -e 'print "_a* " x 40000' | time comrak >/dev/null

This allows a denial of service in any application using Comrak to process untrusted input, and thus prevents it from being used for that purpose, forcing the use of a C library such as cmark or MD4C instead.

[kivikakk]

This may be related to commonmark/cmark#178 — I'll look into it and work out a fix shortly. Thank you! ❤️

[kivikakk]

Turns out it's unrelated to that — it's instead to do with the translation of process_emphasis into Rust. I believe we're not adjusting indices into openers_bottom everywhere we should be; the original just uses a bunch of linked lists floating around and doesn't need to worry about such things.

[kivikakk]

Not even that — we're removing from all over self.delimiters in process_emphasis, which is a Vec. Because we're not just popping from the back, end up doing large amounts of shifts of data, which adds up to quadratic in its complexity. I'll likely need to redo this as linked lists/as an arena.

[kivikakk]

Thanks so much; this is fixed!

[kivikakk]

kahekkass ~/kivikakk/comrak quadratic$ perl -e 'print "_a* " x 80000' | time target/release/comrak >/dev/null; perl -e 'print "_a* " x 640000' | time target/release/comrak >/dev/null
        0.08 real         0.05 user         0.02 sys
        0.63 real         0.46 user         0.16 sys