Repeated edits stack anonymous levels in the tree and highlightTree walks them through hasChild (@lezer/common 1.5.4)

@lezerlezer/common 1.5.4 (and 1.5.3 for comparis@lezern), @lezer/l@lezer 1.4.11, @lezer/javascript 1.5.6, @lezer/highlight 1.2.5, Node 26.

Typing at one spot of a large JavaScript file, with one incremental parse per character, makes the tree deeper by one anonymous level per edit. The levels are not at the cursor (the depth at the cursor stays at 6) but elsewhere in the tree. highlightTree over a small range around the cursor gets about ten times slower after a few hundred edits.

import { parser } from '@lezer/javascript';
import { Tree, TreeFragment } from '@lezer/common';
import { highlightTree, classHighlighter } from '@lezer/highlight';

const unit = (i) =>
  `/**\n * Returns the number ${i}.\n */\nfunction f${i}() {\n  return ${i};\n}\n\n`;
let doc = Array.from({ length: 5000 }, (_, i) => unit(i)).join('');
let tree = parser.parse(doc);
let at = doc.indexOf('\n\n', doc.length >> 1) + 1;

function maxDepth(node = tree, from = 0, depth = 1, best = { depth: 0, at: 0 }) {
  if (!(node instanceof Tree)) return best;
  if (depth > best.depth) Object.assign(best, { depth, at: from });
  node.children.forEach((child, i) => maxDepth(child, from + node.positions[i], depth + 1, best));
  return best;
}
function highlightAroundCursor() {
  const start = performance.now();
  for (let i = 0; i < 20; i++)
    highlightTree(tree, classHighlighter, () => {}, at - 1500, at + 1500);
  return ((performance.now() - start) / 20).toFixed(2);
}

const line = '\nconst total = count + offset * scale - 1';
for (let edit = 1; edit <= 400; edit++) {
  const ch = line[edit % line.length];
  doc = doc.slice(0, at) + ch + doc.slice(at);
  const fragments = TreeFragment.applyChanges(TreeFragment.addTree(tree), [
    { fromA: at, toA: at, fromB: at, toB: at + 1 },
  ]);
  tree = parser.parse(doc, fragments);
  at++;
  if ([1, 10, 50, 100, 200, 400].includes(edit)) {
    const { depth, at: deepAt } = maxDepth();
    console.log(edit, depth, deepAt, at, highlightAroundCursor());
  }
}

Edits 1.5.3: max depth (at) 1.5.3: highlight 1.5.4: max depth (at) 1.5.4: highlight
1 6 (180886) 0.38 ms 7 (167488) 0.41 ms
50 55 (333102) 0.13 ms 55 (198198) 0.19 ms
100 64 (333152) 0.09 ms 105 (333152) 0.25 ms
200 64 (333252) 0.11 ms 205 (333252) 0.55 ms
400 64 (333452) 0.08 ms 258 (45868) 0.97 ms

The cursor is around 181000 in a 360000 character document. With a counter in a copy of hasChild, one highlightTree call over the range makes 208 hasChild calls with 1.5.3 (recursion depth 4) and 62815 with 1.5.4 (recursion depth 261). hasChild ignores the range of the iteration, so nextChild pays for a deep anonymous chain outside the range. tree.iterate over the same range does not call it.

I suspect a relation with b5203bfa (“Don’t over-state the look-ahead of balanced repeat nodes”): more repeat nodes are now reused, and each parse seems to wrap the reused ones in one more anonymous level. 1.5.3 also stacks levels (64 here, up to 394 on a TypeScript file of 10000 lines) but they did not end up under the nodes highlightTree enters. In CodeMirror the effect shows up as 1 to 3.8 ms per keystroke in highlightTree after a few bursts of typing at the same spot, on a 10000 line TypeScript file. https://code.haverbeke.berlin/lezer/lezer/issues/77

There’s no need to open both a forum thread and an issue about the same problem. See #77.

Sorry about the duplicate ! I wasn’t sure which channel was best. I’ll continue in #77. Thanks !