Summary
Prettier's Markdown parser (parser "markdown", also reached through "mdx" table content) ships a bundled micromark-extension-gfm-table whose EditMap resolves event edits by linearly scanning an in-memory array on every edit. A GFM table with N body rows triggers O(N) edits, each scanning an O(N) list (plus an O(N) event slice per edit in consume()), so formatting time grows as O(N²).
A ~40 KB Markdown document that is a single GFM table with 4,000 rows takes ~1.1 s to format, whereas a paragraph of the identical byte size takes ~65 ms. Doubling the row count roughly quadruples the time. Because Prettier is embedded in countless online formatters, playgrounds, and review/comment widgets that turn untrusted Markdown into HTML or formatted text, an attacker can send a small (~100–300 KB) Markdown payload that pins a CPU core for tens of seconds. There is no error, no malformed input required — the table is valid CommonMark/GFM.
No prototype-pollution vector was found; this is an availability (algorithmic-complexity) issue only.
Details
- Affected package:
prettier (npm), version 3.9.9 (latest stable), commit cdd17f2 ("Release 3.9.9", 2026-09-23). Node v22.23.2, macOS arm64.
- The Markdown parser was newly migrated to
micromark in Prettier 3.9.0 (2026-06-27); this code path is new and had not been load-tested against adversarial table shapes.
- Bundled dependency:
[email protected] (pinned in Prettier's lockfile). The linear-scan EditMap.add is the root cause.
- Root cause file/line (upstream source of the bundled code):
micromark-extension-gfm-table/lib/edit-map.js, function addImplementation, the while (index < editMap.map.length) linear scan (≈ lines 132–153), compounded by the reverse-iteration events.slice() loop in consume() (≈ lines 98–119).
- Root cause in the Prettier bundle:
node_modules/prettier/plugins/markdown.mjs, line 33. The minified EditMap class is var Kr=class{constructor(){this.map=[]}add(t,r,n){sd(this,t,r,n)}consume(t){...}} (ctor at line 33 col 22432) and the linear-scan inserter is function sd(e,t,r,n){...for(;a<e.map.length;){if(e.map[a][0]===t){...}a+=1}e.map.push([t,r,n])} (line 33 col 22793). The table resolveAll function cd(...) allocates p=new Kr and calls p.add(...) once per cell boundary per row.
- Why it is quadratic: for a table with
N rows, cd/Qr/ro issue ~4N add() calls. Each add scans the entire map array (which grows to O(N)) to dedupe edits at a given index → O(N²) comparisons. consume() then iterates the O(N) edits in reverse, calling events.slice(...) (an O(events.length) copy) each time → a second O(N²) term.
- Sibling surface checked: the same
EditMap is used only by GFM tables. Plain nested links/images ([[[...x...]]]) show a much milder linear-in-N² term in core micromark (≈10× smaller constant; ~150 ms at N=6,400) and are not reported here as a separate issue. The less/postcss-less parser showed a superlinear signal in isolation but it originates in postcss-less itself and is not reachable through Prettier's bundled version with a smaller constant; not included.
- Prototype pollution: canaries planted on
Object.prototype and fed __proto__/constructor.prototype keys across JSON, YAML, babel, graphql, glimmer, html, css parsers did not result in pollution of a fresh object.
Tested patch
The following patch was tested before reporting:
From 0000000000000000000000000000000000000000 (prettier bundled micromark-extension-gfm-table 2.1.1)
Subject: [PATCH] perf(markdown): make GFM table EditMap add O(1) instead of O(n)
The bundled micromark-extension-gfm-table EditMap resolved edits by linearly
scanning `map` for a matching index on every `add()` call. A table with N
rows issues O(N) edits, each scanning an O(N)-length array, making table
parsing O(N^2). A second O(N) factor comes from the per-edit
`events.slice()` inside `consume()`.
This change keys edits by index in a Map, mirroring the upstream fix
(shipped in micromark-extension-gfm-table 2.1.2). Output is byte-identical.
---
src/language-markdown/parse/micromark/edit-map.js (derived) | 16 ++++++++------
1 file changed, 10 insertions(+), 6 deletions(-)
diff --git a/edit-map.js b/edit-map.js
--- a/edit-map.js
+++ b/edit-map.js
@@ -34,6 +34,11 @@ export class EditMap {
* @type {Array<Change>}
*/
this.map = [];
+
+ /**
+ * Changes by index, so `add` does not scan `map`.
+ * @type {Map<number, Change>}
+ */
+ this.index = new Map();
}
...
@@ -132,21 +137,17 @@ function addImplementation(editMap, at, remove, add) {
if (remove === 0 && add.length === 0) {
return;
}
- let index = 0;
- while (index < editMap.map.length) {
- if (editMap.map[index][0] === at) {
- editMap.map[index][1] += remove;
- editMap.map[index][2].push(...add);
- return;
- }
- index += 1;
- }
- editMap.map.push([at, remove, add]);
+ const existing = editMap.index.get(at);
+ if (existing) {
+ existing[1] += remove;
+ existing[2].push(...add);
+ return;
+ }
+ const change = [at, remove, add];
+ editMap.map.push(change);
+ editMap.index.set(at, change);
}
...
// in consume(), after `this.map.length = 0;` add:
+ this.index.clear();
Release note:
Markdown: fix quadratic (O(n^2)) CPU usage when formatting GFM tables with
many rows. A table of N rows now parses in O(N) instead of O(N^2); output
is unchanged. Upgrades bundled micromark-extension-gfm-table to 2.1.2.
Proof of concept
Environment: Node v22.23.2, [email protected] from npm, prettier.format(code, { parser: "markdown" }).
Exploit input (4,000-row GFM table, ~40 KB):
| a | b |
|---|---|
| x | y |
| x | y |
... (4,000 identical rows)
Control (paragraph of identical byte length, ~40 KB): word word word ...
Measured wall time (pre-patch, captured):
| N (rows) |
Exploit table (ms) |
Control paragraph (ms) |
| 500 |
44 |
14 |
| 1,000 |
104 |
22 |
| 2,000 |
309 |
37 |
| 4,000 |
1,079 |
66 |
| 8,000 |
4,087 |
113 |
Doubling N → ~3.5–4× time (constant ms/N² ≈ 4e-5); control grows linearly (~2×). A 25,600-row table (~250 KB) exceeds ~40 s on one core.
Post-patch (applying the fix below — keying EditMap edits by index in a Map):
| N (rows) |
Exploit table (ms) post-patch |
| 500 |
32 |
| 1,000 |
58 |
| 2,000 |
81 |
| 4,000 |
157 |
| 8,000 |
360 |
Doubling N → ~2× (linear). At N=8,000 the table format time dropped from 4,087 ms to 360 ms (≈11×). Output on the exploit and on a representative table corpus was verified byte-identical (112,028 bytes matched exactly before/after).
A runnable harness (poc.js, verify-identical.js) and the raw timing tables are in the artifacts directory.
Impact
- Availability denial: a single small HTTP request to an online Prettier-based Markdown formatter/playground pins a worker CPU core for seconds-to-minutes. A handful of concurrent such requests exhausts the formatter's worker pool, denying service to legitimate users.
- Confidentiality and integrity are unaffected; no code execution, no information disclosure, no prototype pollution.
- The payload is valid, syntactically correct GFM — no fuzzing/crash conditions, no parser error — so it passes through normal input filters.
- Scope of affected users: anyone exposing Prettier's Markdown parser to untrusted input (playgrounds, issue/comment renderers, docs pipelines, shared format-as-a-service).
Summary
Prettier's Markdown parser (parser
"markdown", also reached through"mdx"table content) ships a bundledmicromark-extension-gfm-tablewhoseEditMapresolves event edits by linearly scanning an in-memory array on every edit. A GFM table withNbody rows triggersO(N)edits, each scanning anO(N)list (plus anO(N)event slice per edit inconsume()), so formatting time grows asO(N²).A ~40 KB Markdown document that is a single GFM table with 4,000 rows takes ~1.1 s to format, whereas a paragraph of the identical byte size takes ~65 ms. Doubling the row count roughly quadruples the time. Because Prettier is embedded in countless online formatters, playgrounds, and review/comment widgets that turn untrusted Markdown into HTML or formatted text, an attacker can send a small (~100–300 KB) Markdown payload that pins a CPU core for tens of seconds. There is no error, no malformed input required — the table is valid CommonMark/GFM.
No prototype-pollution vector was found; this is an availability (algorithmic-complexity) issue only.
Details
prettier(npm), version 3.9.9 (latest stable), commit cdd17f2 ("Release 3.9.9", 2026-09-23). Node v22.23.2, macOS arm64.micromarkin Prettier 3.9.0 (2026-06-27); this code path is new and had not been load-tested against adversarial table shapes.[email protected](pinned in Prettier's lockfile). The linear-scanEditMap.addis the root cause.micromark-extension-gfm-table/lib/edit-map.js, functionaddImplementation, thewhile (index < editMap.map.length)linear scan (≈ lines 132–153), compounded by the reverse-iterationevents.slice()loop inconsume()(≈ lines 98–119).node_modules/prettier/plugins/markdown.mjs, line 33. The minifiedEditMapclass isvar Kr=class{constructor(){this.map=[]}add(t,r,n){sd(this,t,r,n)}consume(t){...}}(ctor at line 33 col 22432) and the linear-scan inserter isfunction sd(e,t,r,n){...for(;a<e.map.length;){if(e.map[a][0]===t){...}a+=1}e.map.push([t,r,n])}(line 33 col 22793). The tableresolveAllfunctioncd(...)allocatesp=new Krand callsp.add(...)once per cell boundary per row.Nrows,cd/Qr/roissue~4Nadd()calls. Eachaddscans the entiremaparray (which grows toO(N)) to dedupe edits at a given index →O(N²)comparisons.consume()then iterates theO(N)edits in reverse, callingevents.slice(...)(anO(events.length)copy) each time → a secondO(N²)term.EditMapis used only by GFM tables. Plain nested links/images ([[[...x...]]]) show a much milder linear-in-N² term in coremicromark(≈10× smaller constant; ~150 ms at N=6,400) and are not reported here as a separate issue. Theless/postcss-lessparser showed a superlinear signal in isolation but it originates inpostcss-lessitself and is not reachable through Prettier's bundled version with a smaller constant; not included.Object.prototypeand fed__proto__/constructor.prototypekeys across JSON, YAML, babel, graphql, glimmer, html, css parsers did not result in pollution of a fresh object.Tested patch
The following patch was tested before reporting:
Proof of concept
Environment: Node v22.23.2,
[email protected]from npm,prettier.format(code, { parser: "markdown" }).Exploit input (4,000-row GFM table, ~40 KB):
Control (paragraph of identical byte length, ~40 KB):
word word word ...Measured wall time (pre-patch, captured):
Doubling N → ~3.5–4× time (constant
ms/N² ≈ 4e-5); control grows linearly (~2×). A 25,600-row table (~250 KB) exceeds ~40 s on one core.Post-patch (applying the fix below — keying
EditMapedits by index in aMap):Doubling N → ~2× (linear). At N=8,000 the table format time dropped from 4,087 ms to 360 ms (≈11×). Output on the exploit and on a representative table corpus was verified byte-identical (112,028 bytes matched exactly before/after).
A runnable harness (
poc.js,verify-identical.js) and the raw timing tables are in the artifacts directory.Impact