search

commonmark / cmark

CommonMark parsing and rendering library and program in C
Other
1.6k stars 534 forks source link

Fix quadratic performance issue in list numbering #473

Open kevinbackhouse opened 1 year ago

kevinbackhouse commented 1 year ago

This is the same fix as https://github.com/github/cmark-gfm/pull/322. It fixes the bug described in https://github.com/github/cmark-gfm/security/advisories/GHSA-r8vr-c48j-fcc5.

To reproduce the bug:

python3 -c 'n = 10000; print("1.\n" + " 2.\n"*n)' | time ./src/cmark -t commonmark
python3 -c 'n = 10000; print("1.\n" + " 2.\n"*n)' | time ./src/cmark -t man

Increasing the number 10000 in the above command causes the running time to increase quadratically.

This PR replaces #472, which didn't work correctly (see https://github.com/github/cmark-gfm/issues/321).

jgm commented 1 year ago

Thanks for submitting this! I haven't had a chance to look at it in detail yet.