Quadratic behavior in Commonmark renderer involving get_containing_block

commonmark / cmark

CommonMark parsing and rendering library and program in C

Other

1.62k stars 539 forks source link

Quadratic behavior in Commonmark renderer involving get_containing_block #431

Closed nwellnhof closed 2 years ago

nwellnhof commented 2 years ago

Found by OSS-Fuzz:

https://oss-fuzz.com/testcase-detail/6306452753481728
https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=41619

I haven't investigated the test case form OSS-Fuzz, but the stack trace contains the function get_containing_block in the Commonmark renderer which can obviously lead to quadratic behavior with deeply nested inlines:

python3 -c 'print("*"*100000+"a"+"*"*100000)' |build/src/cmark -t commonmark |wc -c

jgm commented 2 years ago

Your fix seems excellent -- go ahead and submit a PR.