Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Quadratic output size explosion with tables extension #1000

Closed
notriddle opened this issue Jan 29, 2024 · 1 comment
Closed

Quadratic output size explosion with tables extension #1000

notriddle opened this issue Jan 29, 2024 · 1 comment

Comments

@notriddle
Copy link
Contributor

notriddle commented Jan 29, 2024

Same issue as pulldown-cmark/pulldown-cmark#832 and jgm/commonmark-hs#145.

The problem is, because the table extension fills in missing table cells, you can force the output to grow as the square of the input by adding one column and one row. This is a side-effect of the extension as specified, and follows from the geometric definition of "squaring": the size of the output is proportional to the area of a square, but the input is proportional to the parameter.

$ python -c 'N=100; print("x|" * N + "\n" + "-|" * N + "\n" + "x|\n" * N)' | ./bin/markdown-it.mjs | wc -c
102362
$ python -c 'N=1000; print("x|" * N + "\n" + "-|" * N + "\n" + "x|\n" * N)' | ./bin/markdown-it.mjs | wc -c
10023062
$ python -c 'N=10000; print("x|" * N + "\n" + "-|" * N + "\n" + "x|\n" * N)' | ./bin/markdown-it.mjs | wc -c
FATAL ERROR: Reached heap limit Allocation failed - JavaScript heap out of memory

The output size grows roughly as square of the input size: factor of 10 growth on input means factor of 100 growth on output.

cmark-gfm avoids this problem by putting a limit on the number of cells it will "autocomplete." md4c simply limits the number of columns.

@rlidwka rlidwka closed this as completed in 00b8a93 Mar 1, 2024
@rlidwka
Copy link
Member

rlidwka commented Mar 1, 2024

Fixed the same way as in the two parsers linked above (i.e. limit the number of autocomplete cells).

Thanks for reporting!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants