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 #472

Closed kevinbackhouse closed 1 year ago

kevinbackhouse commented 1 year ago

This is a cherry-pick of one of the commits that we added in cmark-gfm to fix https://github.com/github/cmark-gfm/security/advisories/GHSA-r8vr-c48j-fcc5. (Only one of the bugs affects cmark too.)

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.

The solution is to keep track of the current item number, rather than recomputing it on every iteration by counting the number of elements in the list.

kevinbackhouse commented 1 year ago

It turns out that this solution is incorrect (see https://github.com/github/cmark-gfm/issues/321). I'm going to implement a new solution and post a new PR when it's ready.