While Tree-sitter is heavily influenced by Wagner's thesis, our error recovery strategy actually uses a novel approach, so it is fair to question whether Wagner's would have different properties.
For error recovery, Tree-sitter is currently optimized for some goals that are a bit different from the goals of a single-language IDE like Rust-Analyzer:
* Like RA, we want to minimize the impact of syntax errors on basic features like syntax highlighting and symbol name extraction (which are important to GitHub, and in lightweight text editors like Neovim and Atom).
* Unlike RA, I wanted to avoid requiring grammar authors to think about error recovery at all.
* We needed to tightly control the performance cost of pathological error recovery cases, like parsing a large Ruby file as Go (either accidentally or adversarially).
My understanding is that Wagner's thesis is mostly concerned with "history-sensitive" error recovery in an IDE: using earlier syntax trees as an additional input to the error recovery process in order to better understand the user's intent when editing.
I think this idea makes a lot of sense, but it doesn't address cases like Matklad has prevented here, where the IDE is presented with already-invalid file.
> My understanding is that Wagner's thesis is mostly concerned with "history-sensitive" error recovery in an IDE: using earlier syntax trees as an additional input to the error recovery process in order to better understand the user's intent when editing.
That matches my understanding (note that Wagner's error recovery algorithm is probably best supplemented with Lukas Diekmann's thesis, which corrects and expands it a bit https://diekmann.co.uk/diekmann_phd.pdf).
Because Wagner's algorithm relies on history and context, it does sometimes do some unexpected (and not always useful things). However, I don't see any fundamental reason why it couldn't be paired with a "traditional" error recovery approach (I have one to sell!) to try and get the best of both worlds.
Yeah, I agree. To really demonstrate the best possible IDE error recovery that LR/GLR can provide, pairing a robust batch error recovery strategy with Wagner's (and your and Lukas's) history-sensitive approach is probably the way to go.
At the time that I was implementing error recovery for Tree-sitter, that felt beyond my "complexity budget", since batch error recovery was already not trivial, and the batch approach was good enough for the features I was building on GitHub/Atom. Someday, I could imagine augmenting it with history-sensitive behavior. I am thankful that Lukas has helped to "pave that path" so thoroughly.
For error recovery, Tree-sitter is currently optimized for some goals that are a bit different from the goals of a single-language IDE like Rust-Analyzer:
My understanding is that Wagner's thesis is mostly concerned with "history-sensitive" error recovery in an IDE: using earlier syntax trees as an additional input to the error recovery process in order to better understand the user's intent when editing.I think this idea makes a lot of sense, but it doesn't address cases like Matklad has prevented here, where the IDE is presented with already-invalid file.