js: Parse is quadratic in the number of distinct names in a scope

js.Parse takes time quadratic in the number of distinct names in a scope. Scope.findDeclared, Scope.findUndeclared and Scope.AddUndeclared (js/ast.go) each scan the scope's Declared or Undeclared slice, and the parser calls them once per declaration or reference, so a flat program with n distinct names does O(n²) comparisons. No nesting is needed, so NestedStmtLimit and NestedExprLimit do not bound it.

Witness, against v2.8.16 with Go 1.26.3 on linux/amd64:

package main

import (
	"fmt"
	"strings"
	"time"

	"github.com/tdewolff/parse/v2"
	"github.com/tdewolff/parse/v2/js"
)

func main() {
	for _, n := range []int{4000, 8000, 16000, 32000} {
		var b strings.Builder
		b.WriteString("let ")
		for i := 0; i < n; i++ {
			if i > 0 {
				b.WriteString(",")
			}
			fmt.Fprintf(&b, "v%d", i)
		}
		start := time.Now()
		_, err := js.Parse(parse.NewInputString(b.String()), js.Options{})
		fmt.Println(n, b.Len(), time.Since(start), err)
	}
}

Shape	4,000 names	8,000	16,000	32,000
`let v0,v1,…` (declarations)	12 ms	58 ms	168 ms	754 ms
`v0;v1;…` (undeclared references)	15 ms	58 ms	152 ms	713 ms
`({v0,v1,…})` (shorthand properties)	27 ms	122 ms	333 ms	1.66 s

The shorthand object is the slowest, presumably because the parenthesized expression is scoped once as a possible arrow-function parameter list and then again when it is not one (UndeclareScope).

Context: we parse untrusted JavaScript with js.Parse (we never execute it) and currently bound this by capping input at 64 KiB, where the worst case above is about 0.5 s. A map from name to *Var alongside each slice, or a lazily built index once a slice passes some length, would make the lookups constant time without changing the slices' order, which findDeclared relies on for shadowing (for(let a in []){let a}).

A related observation: NumForDecls, NumFuncArgs and NumArgUses are uint16 offsets into those slices, so a scope with more than 65,535 names would wrap them. We stay well below that at our input cap, but an unbounded input could reach it.

Thank you for the library; it has otherwise parsed every one of about 19,000 real programs we checked it against, in agreement with acorn.

A correction to the context above: the cost also multiplies with nesting depth, so an input-size cap alone does not bound it. When a block closes, HoistUndeclared moves its names into the enclosing scope, scanning that scope's Declared and Undeclared for each one, so names referenced inside d nested blocks are scanned about d times over. 64 KiB of distinct undeclared reads inside 990 nested blocks (just under the default NestedStmtLimit) took over four minutes to parse:

src := strings.Repeat("{", 990) + "v0;v1;v2;…" /* up to 64 KiB */ + strings.Repeat("}", 990)
_, err := js.Parse(parse.NewInputString(src), js.Options{})

We now lower NestedStmtLimit and NestedExprLimit and cap the number of distinct names before parsing, which brings our worst case back to about half a second; a constant-time lookup would remove the need for the name cap.

Thank you very much for bringing this to attention. I've fixed this by adding an index lookup whenever the number of variables (declared and undeclared) is above 16. This dropped the >4min test to about 8 milliseconds (test added). Please let me know your feedback!

Also, I've changed the uint16 to int, not sure why it was uint16 in the first place.

Thanks for the quick fix. Testing a2caccf against my local codebase, the nested shapes went from seconds to milliseconds. Two problems turned up, both in the indexed path.

1. Panic, and hoisting against the wrong scope. In Scope.HoistUndeclared (and UndeclareScope), the indexed branch looks names up in the closing scope's own s.VarIndices, s.Declared and s.Undeclared, where the unindexed branch uses s.Parent. The inner for i := ... also shadows the outer i, so s.Undeclared[i] = v writes at a position taken from indices.

This panics with index out of range [1] with length 1:

function f(x = a) { let b0, b1, b2, b3, b4, b5, b6, b7, b8, b9, b10, b11, b12, b13, a }

When it doesn't panic, a read in an indexed scope finds itself in s.Undeclared, sets vorig.Link = vorig and is never hoisted. With let a; { let c0; ...; let c19; a }, the outer a ends with Uses == 1 at a2caccf and 2 at v2.8.16.

2. Read-then-declare is still quadratic, and slower than before. Declare's reuse of an earlier read still scans s.Undeclared[s.NumArgUses:], and in an indexed scope it then walks all of s.VarIndices to shift indices. a0;a1;...;aN; var a0,a1,...,aN (about 39 KB at N = 3,490):

N	v2.8.16	`a2caccf`
850	2.7 ms	11 ms
1,700	6.6 ms	45 ms
3,490	26 ms	186 ms

The time grows about 4x per doubling, against about 2x for a linear program of the same size.

JS: fix bug in variable lookup, see #132

JS: fix bug in variable lookup due to looking into wrong scope, see #132

JS: fix slow Declare when replacing an undeclared var by a declared v…

I've added fixes for each problem, please let me know how this works for you! Thanks for the great feedback.

There seems to be another bug, it gets into an infinite loop but haven't figured out why...

JS: fix bugs in use of VarIndices, see #132

I hope this fixes all of it, please let me know if you run into problems in your tests!

Thanks, e5b8fd1 fixes both problems from my last comment. The panic is gone, read-then-declare is linear (a0;…;aN; var a0,…,aN at N = 8,000 parses in 2.1 ms, against 718 ms at a2caccf and 107 ms at v2.8.16), and the 990-deep nested-blocks case parses in 348 ms at 8,000 names, against 56 s at v2.8.16. 11.7 million fuzz executions through our extractor found no hang or panic.

One regression remains, and a2caccf has it too: when a scope with 16 or more names closes, its reads of names declared in an enclosing scope are not linked to that declaration. The read stays undeclared, or binds to a same-named variable further out:

let a; {let b0,b1,b2,b3,b4,b5,b6,b7,b8,b9,b10,b11,b12,b13,b14; a}
// v2.8.16: the inner `a` links to the outer `let a` (Uses 2)
// e5b8fd1f42: the inner `a` is a new undeclared var; the outer `let a` has Uses 1

var x; function f(x) {{let b0,…,b14; x}}
// e5b8fd1f42: the inner `x` links to the global `var x`, not the parameter

This miscompiles in minify. With parse at e5b8fd1, minify v2.24.19 turns

function f(x){{let b0=0,b1=0,b2=0,b3=0,b4=0,b5=0,b6=0,b7=0,b8=0,b9=0,b10=0,b11=0,b12=0,b13=0,b14=0;return x+b0+b1+b2+b3+b4+b5+b6+b7+b8+b9+b10+b11+b12+b13+b14}}console.log(f(5))

into function f(){{let e=0,…;return x+e+…}}console.log(f(5)), which drops the parameter and throws ReferenceError: x is not defined; v2.8.16 gives function f(e){…return e+…} and prints 5.

The cause looks like the branch condition in HoistUndeclared and UndeclareScope: both test s.VarIndices != nil, the closing scope, and then look the name up in s.Parent.VarIndices, which is nil when the parent has fewer than 16 names, so the lookup finds nothing and the name is hoisted as undeclared. Testing the parent instead fixes it:

-			if s.VarIndices != nil {
+			if s.Parent.VarIndices != nil {
 				indices := s.Parent.VarIndices[string(vorig.Data)]

(and the same line in UndeclareScope). With that change, the declaration, link and use count of every variable match v2.8.16 across 60,000 generated programs that mix nested blocks, functions, default parameters, arrows, for…of, catch and read-before-var, at 16 or more names per scope; e5b8fd1 differs from v2.8.16 on 592 of them. The timings above are unchanged with the fix.

JS: fix final bug in VarIndices, see #132

Fantastic, fixed!

Update parse dependency, fix cases of slow parsing of JS (see tdewolf…

Thanks, v2.8.17 fixes it.

Across 60,004 generated programs (nested blocks, functions, default parameters, arrows, for…of, catch and read-before-var), 6,243 of them with a scope of 16 or more names, every js.Var's declaration, link and use count now matches v2.8.16: 0 of 844,515 differ, against 172,496 at e5b8fd1. 663k fuzz executions through our extractor found no hang or panic. The worst nested cases stay far below v2.8.16. Reads nested in classes and methods, repeated, run at a median of 49 times a linear program of the same size, against 2,716 at v2.8.16. Reads nested in blocks and parentheses, repeated, run at 24 against 1,673.

One remaining difference from v2.8.16, which doesn't affect us since we don't read either list: in a scope with 16 or more names, Scope.Undeclared also lists variables that the same scope's Declared holds. We found 111,085 such entries across 5,401 programs. It never happens in a smaller scope, and no entry v2.8.16 has is missing. Mentioning it in case minify relies on the two lists being disjoint.

JS: temporarily reverse a bug until we find a better solution, see #132

I have temporarily reversed a change until we can fix the bug. I don't have time to work on this project and it is fairly complex code.

Perhaps we should cleanup the Undeclared list in HoistUndeclared (called when we exit a scope in the parser), this would fix your last paragraph.

We need to make sure that setting Decl to anything but NoDecl in Undeclared is enough (this fixes the timing bug as don't need to adjust indices in VarIndices since we never remove an item from Undeclared), perhaps we need to check for Decl explicitly everywhere? The bug is happens in minify/js/vars.go whenever we check if a variable name is reserved or used (isReserved). I'm also not sure when Link is relevant in these cases.

Thanks, and no worries about time.

One thing to know about v2.8.18: it brings back the quadratic read-then-declare. a0;…;aN; var a0,…,aN takes 44 ms at N = 2,000, 176 ms at 4,000 and 719 ms at 8,000, against 0.5, 1.1 and 2.9 ms at v2.8.17. Declaring before reading is unaffected. The cost is the loop over every VarIndices entry on each Declare that takes over an undeclared var.

Cleaning up Undeclared in HoistUndeclared sounds right to me. Declare could keep v2.8.17's cheap path (set Decl and leave the entry in place, so no index shifting), and when a scope closes, the entries whose Decl is no longer NoDecl are dropped from its Undeclared in one pass before the rest are hoisted. That keeps the two lists disjoint for isReserved without a scan per declaration, as long as every scope, the global one included, goes through it.

I'm happy to put together a PR for that if you'd prefer, with a test for the overlap and the same differential against v2.8.16 as before.

Hi Joshua, a PR would be highly appreciated! I hope that cleaning up in HoistUndeclared fixes the issue mentioned in tdewolff/minify#1049. I'm aware that the commit brings back the timing bug, but I'd rather have it slow than never terminating!

You've informative feedback is of tremendous help, thank you for that.

pr #133 avail for your review

Great, thank you, new version has been released!

thank you!

Navigation Menu

Repository navigation

js: Parse is quadratic in the number of distinct names in a scope #132

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

js: Parse is quadratic in the number of distinct names in a scope #132

Description

Activity

joshuarubin commented on Oct 10, 2026

tdewolff commented on Oct 10, 2026

joshuarubin commented on Oct 11, 2026

tdewolff commented on Oct 12, 2026

tdewolff commented on Oct 12, 2026

tdewolff commented on Oct 12, 2026

joshuarubin commented on Oct 13, 2026

tdewolff commented on Oct 14, 2026

joshuarubin commented on Oct 14, 2026

tdewolff commented on Oct 15, 2026

joshuarubin commented on Oct 15, 2026

tdewolff commented on Oct 15, 2026

joshuarubin commented on Oct 18, 2026

tdewolff commented on Oct 18, 2026

joshuarubin commented on Oct 19, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions