Reproduce-first (ms-typescript reallyLargeFile.ts, 2026-07-07): a file * whose root node has hundreds of thousands of FLAT SIBLINGS (580k //// * comment lines in the 3.5 MB fourslash fixture) hung extraction for over * 15 minutes: walk_defs pushed children via index-based ts_node_child(i), * which is O(i) per call in tree-sitter — O(n^2) per wide node (~1.7e11 * iterator steps on the real fil
| 9627 | * children under the root, plus sparse real defs so the breadth check cannot |
| 9628 | * pass vacuously). Returns elapsed milliseconds; stores the def count. */ |
| 9629 | static long extract_wide_flat_ms(int n, int *out_defs) { |
| 9630 | const size_t cap = (size_t)n * 24 + (size_t)8192; /* "// wide filler N\n" <= 24 chars */ |
| 9631 | char *src = malloc(cap); |
| 9632 | if (!src) { |
| 9633 | return -1; |
| 9634 | } |
| 9635 | size_t off = 0; |
| 9636 | /* CONSTANT def count (10), independent of n: defs that scale WITH n make |
| 9637 | * the fixture superlinear through the separate per-def sibling-scan cost |
| 9638 | * (O(defs x siblings)) — on windows-CLANG64 ASan that pushed the ratio |
| 9639 | * of LINEAR walk code to 43x. Ten spread-out defs keep the breadth check |
| 9640 | * honest while the sibling-scan term stays 10 x n = linear. */ |
| 9641 | const int def_stride = n / 10; |
| 9642 | for (int i = 0; i < n; i++) { |
| 9643 | off += (size_t)snprintf(src + off, cap - off, "// wide filler %d\n", i); |
| 9644 | if (i % def_stride == 0) { |
| 9645 | off += (size_t)snprintf(src + off, cap - off, "var wide_a%d = %d;\n", i, i); |
| 9646 | } |
| 9647 | } |
| 9648 | struct timespec a; |
| 9649 | struct timespec b; |
| 9650 | cbm_clock_gettime(CLOCK_MONOTONIC, &a); |
| 9651 | CBMFileResult *r = |
| 9652 | cbm_extract_file(src, (int)off, CBM_LANG_JAVASCRIPT, "proj", "wide.js", 0, NULL, NULL); |
| 9653 | cbm_clock_gettime(CLOCK_MONOTONIC, &b); |
| 9654 | free(src); |
| 9655 | if (!r) { |
| 9656 | return -1; |
| 9657 | } |
| 9658 | *out_defs = r->defs.count; |
| 9659 | cbm_free_result(r); |
| 9660 | return (b.tv_sec - a.tv_sec) * 1000L + (b.tv_nsec - a.tv_nsec) / 1000000L; |
| 9661 | } |
| 9662 | |
| 9663 | /* Best-of-N. Timing noise only ever ADDS time, so the minimum of a few runs is |
| 9664 | * the cheapest good estimate of the noise-free cost. A single sample at each |
no test coverage detected