Title: Avoid quadratic-time parsing for inline HTML · Issue #447 · commonmark/commonmark-java · GitHub
Open Graph Title: Avoid quadratic-time parsing for inline HTML · Issue #447 · commonmark/commonmark-java
X Title: Avoid quadratic-time parsing for inline HTML · Issue #447 · commonmark/commonmark-java
Description: Summary Every < in a document makes the inline parser look for the end of the construct it might start, and the scan is thrown away when that end is not there. On input made of < whose construct never ends, each one walks to the end of t...
Open Graph Description: Summary Every < in a document makes the inline parser look for the end of the construct it might start, and the scan is thrown away when that end is not there. On input made of < whose construct ne...
X Description: Summary Every < in a document makes the inline parser look for the end of the construct it might start, and the scan is thrown away when that end is not there. On input made of < whose constr...
Opengraph URL: https://github.com/commonmark/commonmark-java/issues/447
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Avoid quadratic-time parsing for inline HTML","articleBody":"### Summary\n\nEvery `\u003c` in a document makes the inline parser look for the end of the construct it might start, and the scan is thrown away when that end is not there. On input made of `\u003c` whose construct never ends, each one walks to the end of the input, so parsing is quadratic in the size of the input. Roughly 800 KB of `x \u003c!-- >` keeps a core busy for over a minute, so a single request can stall a worker in any application that renders untrusted Markdown (comments, chat, wikis).\n\n### Details\n\n[`HtmlInlineParser`](https://github.com/commonmark/commonmark-java/blob/7a68e9204c8f4e521f8206aff3b64361e1a605b1/commonmark/src/main/java/org/commonmark/internal/inline/HtmlInlineParser.java) is triggered by `\u003c` and has four scans of this shape:\n\n| Construct | Looks for | Code |\n|---|---|---|\n| processing instruction | `?>` | [L153](https://github.com/commonmark/commonmark-java/blob/7a68e9204c8f4e521f8206aff3b64361e1a605b1/commonmark/src/main/java/org/commonmark/internal/inline/HtmlInlineParser.java#L153) |\n| comment | `-->` | [L177](https://github.com/commonmark/commonmark-java/blob/7a68e9204c8f4e521f8206aff3b64361e1a605b1/commonmark/src/main/java/org/commonmark/internal/inline/HtmlInlineParser.java#L177) |\n| CDATA section | `]]>` | [L196](https://github.com/commonmark/commonmark-java/blob/7a68e9204c8f4e521f8206aff3b64361e1a605b1/commonmark/src/main/java/org/commonmark/internal/inline/HtmlInlineParser.java#L196) |\n| declaration | `>` | [L215](https://github.com/commonmark/commonmark-java/blob/7a68e9204c8f4e521f8206aff3b64361e1a605b1/commonmark/src/main/java/org/commonmark/internal/inline/HtmlInlineParser.java#L215) |\n\nEach of them ends up in [`Scanner.find`](https://github.com/commonmark/commonmark-java/blob/7a68e9204c8f4e521f8206aff3b64361e1a605b1/commonmark/src/main/java/org/commonmark/parser/beta/Scanner.java#L196), which advances one character at a time and only gives up at the end of the input:\n\n```java\nwhile (scanner.find('-') >= 0) { // no `-->` ahead, so this walks to the end of the input\n if (scanner.next(\"-->\")) {\n return true;\n } else {\n scanner.next();\n }\n}\n```\n\nThe candidate is then rejected, the position is reset, and the next `\u003c` starts the same scan over again. With n openers that is n scans of average length n/2. Plain paragraph text is enough to reach it:\n\n| Input, repeated | Size at 100,000 | 25,000 | 50,000 | 100,000 | 100,000 with the patch |\n|---|---|--:|--:|--:|--:|\n| `x \u003c? >` | 586 KB | 1.7 s | 6.6 s | 26.7 s | 0.08 s |\n| `x \u003c!-- >` | 781 KB | 4.6 s | 19.2 s | 76.7 s | 0.07 s |\n| `x \u003c. \nCollected and verified by [OSTIF](https://ostif.org) using AI with their own harness. \nManually verified, fixed, and reported by [Shielder](https://www.shielder.com).","author":{"url":"https://github.com/fromVeeko","@type":"Person","name":"fromVeeko"},"datePublished":"2026-08-05T16:28:16Z","url":"https://github.com/commonmark/commonmark-java/issues/447"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:24953c6e-e6ef-9c9f-a46e-d81ec9acf846 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | 833C:2E0E94:2DCC97:3E12AE:6AFBB232 |
| html-safe-nonce | 8b548c06e48f83201024383fe4d0c88feddc1283672c332fec7d5cf1b1d41c36 |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4MzNDOjJFMEU5NDoyRENDOTc6M0UxMkFFOjZBRkJCMjMyIiwidmlzaXRvcl9pZCI6IjM5MDMyMzczMDIyNTUzMzM5MzgiLCJyZWdpb25fZWRnZSI6ImlhZCIsInJlZ2lvbl9yZW5kZXIiOiJpYWQifQ== |
| visitor-hmac | fc9f0acf71e997998d5b4a285b46db059d7fd9edcf64bbc4896f16ff37476d6b |
| hovercard-subject-tag | issue:5073060653 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/commonmark/commonmark-java/447/issue_layout |
| twitter:image | https://opengraph.githubassets.com/81109a52dc42910bfe342a73011f63c2d5a2d343e58aa3fd2ccb78f374bc21aa/commonmark/commonmark-java/issues/447 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/81109a52dc42910bfe342a73011f63c2d5a2d343e58aa3fd2ccb78f374bc21aa/commonmark/commonmark-java/issues/447 |
| og:image:alt | Summary Every < in a document makes the inline parser look for the end of the construct it might start, and the scan is thrown away when that end is not there. On input made of < whose construct ne... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | fromVeeko |
| hostname | github.com |
| expected-hostname | github.com |
| None | 2b2ef9c1578c18d8ed27027940544c958743213cf4461659f14d3ccdf51e162c |
| turbo-cache-control | no-preview |
| go-import | github.com/commonmark/commonmark-java git https://github.com/commonmark/commonmark-java.git |
| octolytics-dimension-user_id | 8661225 |
| octolytics-dimension-user_login | commonmark |
| octolytics-dimension-repository_id | 39477878 |
| octolytics-dimension-repository_nwo | commonmark/commonmark-java |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 39477878 |
| octolytics-dimension-repository_network_root_nwo | commonmark/commonmark-java |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | e4cce0e99cf61481a318ff12c2e8580153a6c7c6 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width