> Hmm, makes me wonder if this data structure would also support CRDTs. Collaborative editing is a nice thing to be able to support.
Text CRDTs are not very difficult, but representing an AST as a CRDT is an open problem. See [1]. There has thankfully been some progress from HN's own dmulligan, see [2].
[1]: https://writer.zohopublic.com/writer/published/grcwy5c699d67...
Another thing I was wondering is how easy this is to integrate with compiler frontends. Basically they need the same thing: an AST. And incrementally updating those is a big reason intellij uses so much resources and CPU since it is constantly boiling the oceans to update ASTs all over the place. Any time it gets out of wack (which happens a lot), you are looking at lengthy rebuilds using external tools such as gradle. And of course, Jetbrains is currently working on a new compiler frontend for the Kotlin compiler.
I used to use Eclipse back when I was still doing Java. These days people pull up their nose for that. But it had one powerful feature: a tightly integrated incremental compiler. Intellij is orders of magnitudes slower than Eclispe was.
With intellij, the best case performance of making a 1 character change to a test that you just ran and then re-running it is in the order of seconds. Three seconds would be pretty good. Eclipse was able to do this in well under a second. Compilation would have completed within milliseconds of the character being added. That felt as if it had no delay. Jetbrains never came close to that level of performance. It also never came close to having the same level of consistency. If eclipse told you the source code compiled, it generally did. If intellij tells me I have no errors, I can't trust that to be true until I do a full rebuild. Which can take like half a minute and then often fails for me (because there are obvious syntax errors somewhere). The more changes you make, the more likely it is to be lying about whether things still compile.
So, it's a big problem to tackle. The Kotlin compiler is pretty slow. A full recompilation (without even running tests) can easily take a minute plus on a reasonably sized code base. They are still optimizing it and I'm looking forward to the new compiler frontend they've been working on. But reliable & robust incremental compilation for Kotlin tightly integrated into the IDE would make life a lot more pleasant for me.