Syntax Tree node duplication bug

lishid · January 27, 2022, 7:48pm

I’m running into a rare and extremely difficult bug with @codemirror/language and @codemirror/stream-parser where on long documents (currently testing with ~80k chars), typing almost at the end of the document causes the syntax tree to contain duplicate nodes from the previous syntax tree for the part of the document that is after the position of the cursor.

The problem is actually not easily reproducible if the editor started viewing (and parsing) at the beginning of the document - one must open the document and simultaneously scroll it somewhere further down (before more parsing runs) to trigger this bug.

Example:

[3k lines of simple text with no formatting]

$$1234$$

This generates 3 nodes when iterating the syntax tree.
Let’s pretend the first $ starts at position 80000:
[80000, 80002] = “math start”
[80002, 80006] = “math text”
[80006, 80008] = “math end”

When I type a character in the empty line preceding the math block:

[3k lines of simple text with no formatting]
d
$$1234$$

We expect the following nodes:
[80001, 80003] = “math start”
[80003, 80007] = “math text”
[80007, 80009] = “math end”

Except I get the following now:
[80000, 80002] = “math start”
[80002, 80006] = “math text”
[80006, 80008] = “math end”
[80001, 80003] = “math start”
[80003, 80007] = “math text”
[80007, 80009] = “math end”

An example of console log:
This seems to have generated 4 duplicate copies after typing 3 characters with a pause in between each.

lishid · January 27, 2022, 8:03pm

I suspect this has something to do with various optimizations related to the chunking and tree cutting/reusing. Unfortunately the code around that is not something I could wrap my head around for now, but I suspect it might be something related to these two:

github.com

codemirror/stream-parser/blob/4947f4c9c6c8ae19ced307c6bd07be9e2e718cf9/src/stream-parser.ts#L135

    
      
            let state = off >= startPos && off + tree.length <= before && tree.prop(lang.stateAfter)
            if (state) return {state: lang.streamParser.copyState(state), pos: off + tree.length}
            for (let i = tree.children.length - 1; i >= 0; i--) {
              let child = tree.children[i], pos = off + tree.positions[i]
              let found = child instanceof Tree && pos < before && findState(lang, child, pos, startPos, before)
              if (found) return found
            }
            return null
          }
          
          
function cutTree(lang: StreamLanguage<unknown>, tree: Tree, from: number, to: number, inside: boolean): Tree | null {
            if (inside && from <= 0 && to >= tree.length) return tree
            if (!inside && tree.type == lang.topNode) inside = true
            for (let i = tree.children.length - 1; i >= 0; i--) {
              let pos = tree.positions[i] + from, child = tree.children[i], inner
              if (pos < to && child instanceof Tree) {
                if (!(inner = cutTree(lang, child, from - pos, to - pos, inside))) break
                return !inside ? inner
                  : new Tree(tree.type, tree.children.slice(0, i).concat(inner), tree.positions.slice(0, i + 1), pos + inner.length)
              }
            }

github.com

codemirror/stream-parser/blob/4947f4c9c6c8ae19ced307c6bd07be9e2e718cf9/src/stream-parser.ts#L149

    
      
              let pos = tree.positions[i] + from, child = tree.children[i], inner
              if (pos < to && child instanceof Tree) {
                if (!(inner = cutTree(lang, child, from - pos, to - pos, inside))) break
                return !inside ? inner
                  : new Tree(tree.type, tree.children.slice(0, i).concat(inner), tree.positions.slice(0, i + 1), pos + inner.length)
              }
            }
            return null
          }
          
          
function findStartInFragments<State>(lang: StreamLanguage<State>, fragments: readonly TreeFragment[],
                                               startPos: number, editorState?: EditorState) {
            for (let f of fragments) {
              let from = f.from + (f.openStart ? 25 : 0), to = f.to - (f.openEnd ? 25 : 0)
              let found = from <= startPos && to > startPos && findState(lang, f.tree, 0 - f.offset, startPos, to), tree
              if (found && (tree = cutTree(lang, f.tree, startPos + f.offset, found.pos + f.offset, false)))
                return {state: found.state, tree}
            }
            return {state: lang.streamParser.startState(editorState ? getIndentUnit(editorState) : 4), tree: Tree.empty}
          }

marijn · January 28, 2022, 9:18am

Thanks for reporting that. @codemirror/stream-parser 0.19.5 (via below patch) should work better.

lishid · January 28, 2022, 3:08pm

Thank you! This was driving me crazy haha…