Incremental parsing

[ftomassetti]

Should ANTLR 5 consider supporting incremental parsing as an option?

I am not sure where is the line for new features in ANTLR 5, so perhaps that is too big of a change, but I guess this is what discussions are for :)

While the disadvantage is more work and probably some significant complications, the advantages would be:

• Performance within editor processing very large files
• Performance improvements in processing that depends on the tree returned by ANTLR. If we can provide a list of changes w.r.t. the previous version of the tree other processes (like semantic error checking happening outside ANTLR, symbol resolution, code generation, etc.) could also become incremental

[ericvergnaud]

I think it's definitely worth exploring

[KvanTTT]

DFA cache itself resolves the problem of incremental parsing but I haven't investigate deeply what else is needed.

[ftomassetti]

I am not sure how DFA cache helps with incremental parsing.

By incremental parsing I mean that if I parse a large file a second time, after having performed a minor change, the parsing should be way quicker w.r.t. the first time I parsed the file, and also I should get a sort of diff w.r.t. the original parse tree. In other words, I should not have to throw away the entire previous parse tree but I could keep most of it and just have a few elements change. This would be helpful because also further processing of the tree could become incremental. For example, symbol resolution.

I think that DFA caches could help in making the second parsing faster, but not in updating an existing tree instead of replacing it completely.

This is an example of library implementing incremental parsing: https://github.com/Eliah-Lakhin/papa-carlo

[ericvergnaud]

Yes, this would be super useful when editing code. Do you have any idea of how it could be implemented?

[ftomassetti]

I did not really study this problem, so I can share just a first idea

I would look at what they do in #19 .

I think that seen from the external world incremental parsing means two things:

1. Parsing is faster when applying tiny changes to large files
2. One could get delta/changes w.r.t. to a previously parsed parse-tree instead of a whole tree, as a key to make processing after parsing faster

I think that the second point is more important than the first provided that ANTLR is fast enough in most cases (I guess we would need to verify this opinion).

To implement the second point we need to communicate differences between the current parse-tree and the previous one. We could even just "remember" the last parse-tree, compare it to the latest one and producing a diff to be returned or to be communicated through listeners or observers. If we can do this fast enough the fact that we produce the diff in this naive way instead of using some "proper" incremental approach would be invisible to consumers of the parse-tree. I think that anyway what is expensive is what people do with parse-trees, so making that incremental is what matters.

On the first point, I have only confused guesses. To do the parsing incremental "without cheating", I wonder if we can cache sort of check-points: when parsing a file we could write down the state of the parser after each token or at every start of every line. Then when parsing the second time the file we can "resume" parsing from the last valid check-point. On average that would mean that we would have 50% of the code to parse from the second run. We could then end up "reconverging" on one of the existing check-points, if the change can be "re-absorbed".

For example, if I have this code:

a = 1
b = 2
c = 3

And I change the second line:

a = 1
b = 4
c = 3

At the start of the third line, the parser should be in the same state as it was during the first run. Maybe we can use that to speed up the parsing of the remaining code?

[ericvergnaud]

I guess mileage varies... in my experience, parsing in JS is way too slow. You can parse 30 lines of code fast enough to provide a decent user experience, but not 100.
That parsing performance problem is one of the main original drivers for switching to WebAssembly. I did some experiments with it a couple of years ago, only to find that the cost of exchanging data between JS and WASM was very high. At the time there was no GC and that was a showstopper because I didn't want to invest in Rust, only to throw things away 2 years later...
The code editors I know of (Eclipse and Ace) already support deltas, and although far from trivial, there's nothing in the way of genuine incremental parsing for a given language.
I suspect that doing it in a generic way might be more challenging, but don't we have the right people in this team ? 😆

[KvanTTT]

ANTLR is fast enough in most cases

I agree with @ericvergnaud that it's also not always true, it depends on use-case. I suspect if code-sample to parse is quite simple, small or middle, ANTLR is fast. But if it's big or complex (especially if it forces switching LL -> SLL), ANTLR could be slow and could be very memory-consuming because of growing DFA cache. I parsed huge files 30 MB files on my previous work and it was not very good.

I guess mileage varies... in my experience, parsing in JS is way too slow. You can parse 30 lines of code fast enough to provide a decent user experience, but not 100.

JS runtime is quite fast and it's comparible to C# unlike Python. I made benchmarks some time ago: AntlrBenchmarks and I had the same problems with performance with C# runtime on my previous work (I tried to parse JS but got LL -> SLL switching on valid code, it slows down a lot). If performance is bad, firstly, it's due to poorly-written grammar or ALL algorithm, and only secondly it's due to limitation/poorly-written runtime.

That parsing performance problem is one of the main original drivers for switching to WebAssembly

Sorry, but I don't think switching to WebAssembly resolves all problems with performance.

[KvanTTT]

The topic with incremental compilation is usefull and interesting, no doubt. But it makes sense to investigate how other parser deal with that, which data-structures use and so on.

[ftomassetti]

Another example of solution implementing incremental parsing should be tree-sitter