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.

Sign up for GitHub

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

Jump to bottom

Quadratic behavior when parsing smart quotes #388

Closed
nwellnhof opened this issue Jul 13, 2021 · 0 comments · Fixed by #390
Closed

Quadratic behavior when parsing smart quotes #388

nwellnhof opened this issue Jul 13, 2021 · 0 comments · Fixed by #390

Comments

@nwellnhof
Copy link
Contributor

nwellnhof commented Jul 13, 2021 •
edited
Loading

Simply parsing a sequence of single or double quote characters exhibits quadratic behavior when the "smart" option is enabled:

$ for n in 5000 10000 20000; do python3 -c "print(\"'\"*$n)" |time -f "$n chars: %e secs" build/src/cmark --smart >/dev/null; done
5000 chars: 0.15 secs
10000 chars: 0.70 secs
20000 chars: 4.33 secs

This seems to be caused by this loop in process_emphasis.
nwellnhof added a commit to nwellnhof/cmark that referenced this issue Jul 13, 2021
@nwellnhof
Fix quadratic behavior with smart quotes
5cb26e0 
Make sure to remove matching smart quote delimiters. Otherwise, the
same opener could be found over and over again, preventing the
`openers_bottom` optimization from kicking in and leading to quadratic
behavior when processing lots of quotes.

Fixes commonmark#388.
@nwellnhof nwellnhof mentioned this issue Jul 13, 2021
Merged
@jgm jgm closed this as completed in #390 Jul 16, 2021
jgm pushed a commit that referenced this issue Jul 16, 2021
@nwellnhof @jgm
Fix quadratic behavior with smart quotes
10b56dc 
Make sure to remove matching smart quote delimiters. Otherwise, the
same opener could be found over and over again, preventing the
`openers_bottom` optimization from kicking in and leading to quadratic
behavior when processing lots of quotes.

Fixes #388.
kraj pushed a commit to YoeDistro/meta-openembedded that referenced this issue Jul 23, 2021
@wangmingyu84 @kraj
cmark: upgrade 0.30.0 -> 0.30.1
76bd49f 
Changelog:
Properly indent block-level contents of list items in man (openembedded#258).
commonmark/cmark#258
This handles nested lists as well as items with multiple paragraphs.
The change requires addition of a new field block_number_in_list_item
to cmark_renderer, but this does not change the public API.

Fix quadratic behavior when parsing emphasis (openembedded#389, Nick
Wellnhofer). Delimiters can be deleted, so store delimiter positions
instead of pointers in openers_bottom. Besides causing undefined
behavior when reading a dangling pointer, this could also result
in quadratic behavior when parsing emphasis.
commonmark/cmark#389

Fix quadratic behavior when parsing smart quotes (openembedded#388, Nick Wellnhofer).
Remove matching smart quote delimiters. Otherwise, the same opener
could be found over and over, preventing the openers_bottom
optimization from kicking in and leading to quadratic behavior when
processing lots of quotes.
commonmark/cmark#388

Modify CMake configuration so that the project can be built with
older versions of CMake (openembedded#384, Saleem Abdulrasool). (In 0.30.0,
some features were used that require CMake >= 3.3.) The cost of this
backwards compatibility is that developers must now explicitly invoke
cmark_add_compile_options when a new compilation target is added.
commonmark/cmark#384

Remove a comma at the end of an enumerator list, which was flagged
by clang as a C++11 extension.

make_man_page.py: use absolute path with CDLL. This avoids the error
"file system relative paths not allowed in hardened programs."

Include cmark version in cmark(3) man page (instead of LOCAL).

Signed-off-by: Wang Mingyu <[email protected]>
Signed-off-by: Khem Raj <[email protected]>
kraj pushed a commit to YoeDistro/meta-openembedded that referenced this issue Jul 23, 2021
@wangmingyu84 @kraj
cmark: upgrade 0.30.0 -> 0.30.1
1220888 
Changelog:
Properly indent block-level contents of list items in man (openembedded#258).
commonmark/cmark#258
This handles nested lists as well as items with multiple paragraphs.
The change requires addition of a new field block_number_in_list_item
to cmark_renderer, but this does not change the public API.

Fix quadratic behavior when parsing emphasis (openembedded#389, Nick
Wellnhofer). Delimiters can be deleted, so store delimiter positions
instead of pointers in openers_bottom. Besides causing undefined
behavior when reading a dangling pointer, this could also result
in quadratic behavior when parsing emphasis.
commonmark/cmark#389

Fix quadratic behavior when parsing smart quotes (openembedded#388, Nick Wellnhofer).
Remove matching smart quote delimiters. Otherwise, the same opener
could be found over and over, preventing the openers_bottom
optimization from kicking in and leading to quadratic behavior when
processing lots of quotes.
commonmark/cmark#388

Modify CMake configuration so that the project can be built with
older versions of CMake (openembedded#384, Saleem Abdulrasool). (In 0.30.0,
some features were used that require CMake >= 3.3.) The cost of this
backwards compatibility is that developers must now explicitly invoke
cmark_add_compile_options when a new compilation target is added.
commonmark/cmark#384

Remove a comma at the end of an enumerator list, which was flagged
by clang as a C++11 extension.

make_man_page.py: use absolute path with CDLL. This avoids the error
"file system relative paths not allowed in hardened programs."

Include cmark version in cmark(3) man page (instead of LOCAL).

Signed-off-by: Wang Mingyu <[email protected]>
Signed-off-by: Khem Raj <[email protected]>
halstead pushed a commit to openembedded/meta-openembedded that referenced this issue Jul 27, 2021
@wangmingyu84 @kraj
cmark: upgrade 0.30.0 -> 0.30.1
4d6141d 
Changelog:
Properly indent block-level contents of list items in man (#258).
commonmark/cmark#258
This handles nested lists as well as items with multiple paragraphs.
The change requires addition of a new field block_number_in_list_item
to cmark_renderer, but this does not change the public API.

Fix quadratic behavior when parsing emphasis (#389, Nick
Wellnhofer). Delimiters can be deleted, so store delimiter positions
instead of pointers in openers_bottom. Besides causing undefined
behavior when reading a dangling pointer, this could also result
in quadratic behavior when parsing emphasis.
commonmark/cmark#389

Fix quadratic behavior when parsing smart quotes (#388, Nick Wellnhofer).
Remove matching smart quote delimiters. Otherwise, the same opener
could be found over and over, preventing the openers_bottom
optimization from kicking in and leading to quadratic behavior when
processing lots of quotes.
commonmark/cmark#388

Modify CMake configuration so that the project can be built with
older versions of CMake (#384, Saleem Abdulrasool). (In 0.30.0,
some features were used that require CMake >= 3.3.) The cost of this
backwards compatibility is that developers must now explicitly invoke
cmark_add_compile_options when a new compilation target is added.
commonmark/cmark#384

Remove a comma at the end of an enumerator list, which was flagged
by clang as a C++11 extension.

make_man_page.py: use absolute path with CDLL. This avoids the error
"file system relative paths not allowed in hardened programs."

Include cmark version in cmark(3) man page (instead of LOCAL).

Signed-off-by: Wang Mingyu <[email protected]>
Signed-off-by: Khem Raj <[email protected]>
anticomputer pushed a commit to github/cmark-gfm that referenced this issue Jan 23, 2023
@nwellnhof @kevinbackhouse
Fix quadratic behavior with smart quotes
7e49343 
Make sure to remove matching smart quote delimiters. Otherwise, the
same opener could be found over and over again, preventing the
`openers_bottom` optimization from kicking in and leading to quadratic
behavior when processing lots of quotes.

Fixes commonmark#388.
daregit pushed a commit to daregit/yocto-combined that referenced this issue May 22, 2024
@wangmingyu84 @kraj
src/meta-openembedded:cmark: upgrade 0.30.0 -> 0.30.1
8597c16 
Changelog:
Properly indent block-level contents of list items in man (#258).
commonmark/cmark#258
This handles nested lists as well as items with multiple paragraphs.
The change requires addition of a new field block_number_in_list_item
to cmark_renderer, but this does not change the public API.

Fix quadratic behavior when parsing emphasis (#389, Nick
Wellnhofer). Delimiters can be deleted, so store delimiter positions
instead of pointers in openers_bottom. Besides causing undefined
behavior when reading a dangling pointer, this could also result
in quadratic behavior when parsing emphasis.
commonmark/cmark#389

Fix quadratic behavior when parsing smart quotes (#388, Nick Wellnhofer).
Remove matching smart quote delimiters. Otherwise, the same opener
could be found over and over, preventing the openers_bottom
optimization from kicking in and leading to quadratic behavior when
processing lots of quotes.
commonmark/cmark#388

Modify CMake configuration so that the project can be built with
older versions of CMake (#384, Saleem Abdulrasool). (In 0.30.0,
some features were used that require CMake >= 3.3.) The cost of this
backwards compatibility is that developers must now explicitly invoke
cmark_add_compile_options when a new compilation target is added.
commonmark/cmark#384

Remove a comma at the end of an enumerator list, which was flagged
by clang as a C++11 extension.

make_man_page.py: use absolute path with CDLL. This avoids the error
"file system relative paths not allowed in hardened programs."

Include cmark version in cmark(3) man page (instead of LOCAL).

Signed-off-by: Wang Mingyu <[email protected]>
Signed-off-by: Khem Raj <[email protected]>
daregit pushed a commit to daregit/yocto-combined that referenced this issue May 22, 2024
@wangmingyu84 @kraj
src/meta-openembedded:cmark: upgrade 0.30.0 -> 0.30.1
d885cb6 
Changelog:
Properly indent block-level contents of list items in man (#258).
commonmark/cmark#258
This handles nested lists as well as items with multiple paragraphs.
The change requires addition of a new field block_number_in_list_item
to cmark_renderer, but this does not change the public API.

Fix quadratic behavior when parsing emphasis (#389, Nick
Wellnhofer). Delimiters can be deleted, so store delimiter positions
instead of pointers in openers_bottom. Besides causing undefined
behavior when reading a dangling pointer, this could also result
in quadratic behavior when parsing emphasis.
commonmark/cmark#389

Fix quadratic behavior when parsing smart quotes (#388, Nick Wellnhofer).
Remove matching smart quote delimiters. Otherwise, the same opener
could be found over and over, preventing the openers_bottom
optimization from kicking in and leading to quadratic behavior when
processing lots of quotes.
commonmark/cmark#388

Modify CMake configuration so that the project can be built with
older versions of CMake (#384, Saleem Abdulrasool). (In 0.30.0,
some features were used that require CMake >= 3.3.) The cost of this
backwards compatibility is that developers must now explicitly invoke
cmark_add_compile_options when a new compilation target is added.
commonmark/cmark#384

Remove a comma at the end of an enumerator list, which was flagged
by clang as a C++11 extension.

make_man_page.py: use absolute path with CDLL. This avoids the error
"file system relative paths not allowed in hardened programs."

Include cmark version in cmark(3) man page (instead of LOCAL).

Signed-off-by: Wang Mingyu <[email protected]>
Signed-off-by: Khem Raj <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Fix quadratic behavior when processing emphasis nwellnhof/cmark
1 participant
@nwellnhof