Summary
_normalize_ts_import_types (graphify/extract.py) can hang forever on a single ordinary TypeScript file. _TS_IMPORT_TYPE_CALL_RE has two nested lazy quantifiers inside a + group, which produces catastrophic regex backtracking when a line contains several import(...) occurrences without a following >( that lets the overall match succeed.
Introduced with the #3154 normalizer; still present in 0.9.53. During graphify update . one worker pegs a full core at ~100% CPU and the AST-extraction counter stops advancing (looks like a pool deadlock on a many-core box, because one pinned core reads as ~3% aggregate CPU).
The regex
_TS_IMPORT_TYPE_CALL_RE = re.compile(
rb"<((?:[^;{}]*?\bimport\s*\([^()]+\)[^;{}]*?)+)>(?=\s*\()"
)The filler [^;{}]*? appears both before and after import(...) inside a +-repeated group. When the trailing >( lookahead fails, the engine can partition the filler between group iterations in ~2^k ways for k import( tokens, so it backtracks exponentially before giving up on the line.
Minimal repro (pure re, no graphify needed)
import re, time
OLD = re.compile(rb"<((?:[^;{}]*?\bimport\s*\([^()]+\)[^;{}]*?)+)>(?=\s*\()")
for k in (3, 5, 7, 9, 11):
s = b"x < " + b" ".join(b'import("m%d")' % i for i in range(k)) + b" and more text no close"
t = time.time(); OLD.search(s); print(f"imports={k}: {time.time()-t:.3f}s")imports=3: 0.000s
imports=5: 0.005s
imports=7: 0.156s
imports=9: 4.914s
imports=11: (does not finish)
Real-world trigger was a 13 KB .ts file mixing <, several import("...") type references and generic calls; _normalize_ts_import_types(source) never returned.
Suggested fix
Forbid import (and </>) inside the filler so the decomposition is unique — same matches, linear time:
_TS_IMPORT_TYPE_CALL_RE = re.compile(
rb"<((?:(?!import)[^;{}<>])*"
rb"(?:\bimport\s*\([^()]+\)(?:(?!import)[^;{}<>])*)+)>(?=\s*\()"
)Verified parity on the intended positives and negatives:
| input |
old |
new |
f<typeof import("mod")>() |
typeof import("mod") |
same |
f<import("mod").Foo>() |
import("mod").Foo |
same |
g<import("a").A, import("b").B>() |
import("a").A, import("b").B |
same |
a < b && c > (d) |
(no match) |
(no match) |
With the patched pattern the previously-hanging file returns in ~0 ms.
Environment
Summary
_normalize_ts_import_types(graphify/extract.py) can hang forever on a single ordinary TypeScript file._TS_IMPORT_TYPE_CALL_REhas two nested lazy quantifiers inside a+group, which produces catastrophic regex backtracking when a line contains severalimport(...)occurrences without a following>(that lets the overall match succeed.Introduced with the #3154 normalizer; still present in 0.9.53. During
graphify update .one worker pegs a full core at ~100% CPU and the AST-extraction counter stops advancing (looks like a pool deadlock on a many-core box, because one pinned core reads as ~3% aggregate CPU).The regex
The filler
[^;{}]*?appears both before and afterimport(...)inside a+-repeated group. When the trailing>(lookahead fails, the engine can partition the filler between group iterations in ~2^k ways for kimport(tokens, so it backtracks exponentially before giving up on the line.Minimal repro (pure
re, no graphify needed)Real-world trigger was a 13 KB
.tsfile mixing<, severalimport("...")type references and generic calls;_normalize_ts_import_types(source)never returned.Suggested fix
Forbid
import(and</>) inside the filler so the decomposition is unique — same matches, linear time:Verified parity on the intended positives and negatives:
f<typeof import("mod")>()typeof import("mod")f<import("mod").Foo>()import("mod").Foog<import("a").A, import("b").B>()import("a").A, import("b").Ba < b && c > (d)With the patched pattern the previously-hanging file returns in ~0 ms.
Environment
import(...)type used as an explicit type argument is a syntax error, dropping symbols after it #3154 (added this normalizer), TS: #3154import(...)normalizer erases runtime dynamic imports; withimport ("…")the dependency is lost entirely (regression in 0.9.52) #3210 (a separate regression in the same normalizer)