8 ms·

Data Structures in the Fleet Editor

139 points by jsnell 5y ago

rubyist5eva 5y ago
Ok this is cool and all...but when can I start using it.
- Aeolun 5y ago
  Maybe it would be faster to build your own editor given this new information?
  - vidarh 5y ago
    While I think this comes across a bit unnecessarily snarky, I think writing a simple editor is something "every" developer ought to try at least once. It's not a big project - you can write a small editor in ~500-1000 lines of code (or much less for a really sparse one in a compact language), and there are lots of examples out there. My own editor was based on Femto, initially. It's now entirely unrecognisable, and I've used it as my main editor for the last couple of years. I'm linking Femto rather than mine because mine is huge compared to Femto, and full of assumptions that only holds for me -- that was part of the purpose for me; I realised my .emacs file had grown to the point where I could literally write an editor in fewer lines. That's not to say I'm suggesting that most people should write their own editor with the purpose of making it their main editor, because that will likely only work without turning into a massive time suck if you (like me) like your editors spartan and care more about ergonomics in a very simple package than "fancy IDE's". But writing an editor is fun because it can start very simple and you can gradually rediscover or reinvent all kinds of model-view abstractions, and get somewhere usable very quickly. [1] https://github.com/agorf/femto https://github.com/agorf/femto
- hathym 5y ago
  sometime in 2022 ( see part 1 of the series)
junkerm 5y ago
I was reading on ropes a couple of months ago when researching emacs internals. Apparently emacs and vs code are using gap buffers. Would be interesting to know the reasons for the decisions.
- ben-schaaf 5y ago
  fwiw Sublime Text uses a rope (using a rbtree).
  - ilrwbwrkhv 5y ago
    That already makes me look forward to fleet. If it can be as fast as sublime that will be life changing. Although webstorm can't handle large typescript projects with a lot of computed type as well as vs code.
    - searealist 5y ago
      You can't beat the efficiency of a gap buffer for just typing. The downside of gap buffers is its a linear operation to move the cursor.
      - moonchild 5y ago
        I see no reason why a rope would be slower than a gap buffer for 'just typing'. And the gap buffer will choke when you fill it up and want to continue typing.
        searealist 5y ago
        I'm just saying that "gap buffer" is not a reason any editor is perceived to be slow unless its slow when moving the cursor in a large buffer (or as you point out, the amortized growth of a large buffer, which will happen max log n times in a buffer of size n)
        5y ago
vidarh 5y ago
For my own editor, for syntax highlighting, instead of storing any part of an AST, I'm working on instead storing the starting state of Rouge's lexers at fixed intervals. It means restarting the syntax highlighting shortly before the point of a change and running it only for the minimal number of lines until the state again matches the old state is trivial. Most of the time, the full state at the beginning of a line is just a single symbol. If you want/need the AST for other analysis I guess it might be worth doing something more complex there. For my use it mattered more to keep the editor minimal.
- danuker 5y ago
  Beautiful and scalable! Is this your editor? https://github.com/vidarh/re https://github.com/vidarh/re Found it through your profile page. Thanks!
  - vidarh 5y ago
    Yeah, with a couple of huge caveats: That version lags the one I'm using massively at the moment. I'm slowly bringing it up to date. It also has a number of dependencies on my system that needs to be resolved for it to be usable for anyone else. I really should make the warnings in the README even more explicit. E.g. if you try to split the current window, it calls a script that's just expected to be there. My current incarnation of that script uses bspc to split the current window tile (note the README is outdated enough to refer to i3wm which I switched away from a couple of years ago...). It then executes its arguments to open a second client in the open tile that attaches to the same buffer. With respect to the syntax highlighting I don't think the version on Github is remotely up to date - I believe that variant still depends on simply lexing the visible buffer rather than cache the state, but I may be wrong. Just lexing the visible buffer was my quick and dirty starting point to have something, and works surprisingly well (but it gets imprecise and annoying if you e.g. have start of block comments moving in and out of view, hence the switch to caching the Rouge state to make it precise; the next step is to move the lexing to a separate thread in the server process instead of having the clients run it). It's also buggy, as I fix only the bugs which bothers me... Now that I've scared you sufficiently, if you have any questions, my e-mail is also on my profile.
jillesvangurp 5y ago
Hmm, makes me wonder if this data structure would also support CRDTs. Collaborative editing is a nice thing to be able to support. 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.
- anchpop 5y ago
  > 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/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... [2]: https://martin.kleppmann.com/papers/move-op.pdf https://martin.kleppmann.com/papers/move-op.pdf
nsajko 5y ago
A must-read paper in this space is the 1998 paper by Charles Crowley, Data Structures for Text Sequences: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.1265&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48... It explores the space from a different angle: the paper doesn't mention ropes, but it promotes a data structure called a piece table (or sometimes piece chain, piece tree, ...). These two data structure approaches are orthogonal, in that ropes can be used to implement the piece tables' descriptor sequences. Some salient points from the paper about the advantages of the piece table: * All buffers used are either read-only or append-only, so they are easy to cache and work well over a network. * It follows that items never move once placed in a buffer, which is nice as pointers to items never need updating. * Implementing undo is easy. EDIT: this blog post is also nice: https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r...
dzaima 5y ago
I've been working on my own text editor (which I'm apparently not the only one doing that here), and my plan is to switch to using a single B-tree, where the leaf nodes, besides holding the text (and also a color list for basic syntax highlighting), also a list of "pointer" objects, which would hold the carets/extra highlighting references/whatnot. Means two objects per selection (separate start & end pointer), but only one tree to have to scan through.
raphlinus 5y ago
I'm happy to see them cite my Rope Science series. Looking back, there were some things that xi did wrong, most importantly separating the front-end from the back-end with async communication, but the data structures and text manipulation algorithms were solid. I'm considering starting a new, similar, series called "The Book of Monoids," which covers some of the same ground but with more of a focus on parallelism (GPU) than incremental computation.
- phyrex 5y ago
  Could you explain why you say that it was a mistake to separate the editor frontend from the backend?
  - raphlinus 5y ago
    So... separating front-end from back-end in and of itself is not necessarily a problem, but using async to do it adds complexity that is not worth it. Originally, I was hoping that a CRDT or similar mechanisms could be used to smooth out all such problems in a general way (including letting plugins contribute their annotations without causing jank on the main thread), but I discovered that such a collaboration layer cannot hide the underlying explosion in the potential state space. I wrote about this in some detail: https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.html https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.h...
    - mwcampbell 5y ago
      Maybe it would have been better to embed the core inside platform-specific front-end apps using a synchronous FFI. But then, you also discovered that the platform-native GUIs are overrated, at least for this application. Addendum: One thing that excites me about Rust is the potential to cut down on the excessive use of IPC, by letting us implement reusable libraries in a safe language that imposes minimal runtime requirements, then use Rust's powerful metaprogramming features to auto-generate safe language bindings for those libraries. That's one reason I chose Rust for AccessKit. I know diplomat [1] is making some progress in this area. [1]: https://github.com/rust-diplomat/diplomat https://github.com/rust-diplomat/diplomat

139 points by jsnell 5y ago

rubyist5eva 5y ago

Ok this is cool and all...but when can I start using it.

Aeolun 5y ago
Maybe it would be faster to build your own editor given this new information?
- vidarh 5y ago
  While I think this comes across a bit unnecessarily snarky, I think writing a simple editor is something "every" developer ought to try at least once. It's not a big project - you can write a small editor in ~500-1000 lines of code (or much less for a really sparse one in a compact language), and there are lots of examples out there. My own editor was based on Femto, initially. It's now entirely unrecognisable, and I've used it as my main editor for the last couple of years. I'm linking Femto rather than mine because mine is huge compared to Femto, and full of assumptions that only holds for me -- that was part of the purpose for me; I realised my .emacs file had grown to the point where I could literally write an editor in fewer lines. That's not to say I'm suggesting that most people should write their own editor with the purpose of making it their main editor, because that will likely only work without turning into a massive time suck if you (like me) like your editors spartan and care more about ergonomics in a very simple package than "fancy IDE's". But writing an editor is fun because it can start very simple and you can gradually rediscover or reinvent all kinds of model-view abstractions, and get somewhere usable very quickly. [1] https://github.com/agorf/femto https://github.com/agorf/femto
hathym 5y ago
sometime in 2022 ( see part 1 of the series)

junkerm 5y ago

I was reading on ropes a couple of months ago when researching emacs internals. Apparently emacs and vs code are using gap buffers. Would be interesting to know the reasons for the decisions.

ben-schaaf 5y ago
fwiw Sublime Text uses a rope (using a rbtree).
- ilrwbwrkhv 5y ago
  That already makes me look forward to fleet. If it can be as fast as sublime that will be life changing. Although webstorm can't handle large typescript projects with a lot of computed type as well as vs code.
  - searealist 5y ago
    You can't beat the efficiency of a gap buffer for just typing. The downside of gap buffers is its a linear operation to move the cursor.
    - moonchild 5y ago
      I see no reason why a rope would be slower than a gap buffer for 'just typing'. And the gap buffer will choke when you fill it up and want to continue typing.
      - searealist 5y ago
        I'm just saying that "gap buffer" is not a reason any editor is perceived to be slow unless its slow when moving the cursor in a large buffer (or as you point out, the amortized growth of a large buffer, which will happen max log n times in a buffer of size n)
        5y ago

vidarh 5y ago

For my own editor, for syntax highlighting, instead of storing any part of an AST, I'm working on instead storing the starting state of Rouge's lexers at fixed intervals. It means restarting the syntax highlighting shortly before the point of a change and running it only for the minimal number of lines until the state again matches the old state is trivial. Most of the time, the full state at the beginning of a line is just a single symbol. If you want/need the AST for other analysis I guess it might be worth doing something more complex there. For my use it mattered more to keep the editor minimal.

danuker 5y ago
Beautiful and scalable! Is this your editor? https://github.com/vidarh/re https://github.com/vidarh/re Found it through your profile page. Thanks!
- vidarh 5y ago
  Yeah, with a couple of huge caveats: That version lags the one I'm using massively at the moment. I'm slowly bringing it up to date. It also has a number of dependencies on my system that needs to be resolved for it to be usable for anyone else. I really should make the warnings in the README even more explicit. E.g. if you try to split the current window, it calls a script that's just expected to be there. My current incarnation of that script uses bspc to split the current window tile (note the README is outdated enough to refer to i3wm which I switched away from a couple of years ago...). It then executes its arguments to open a second client in the open tile that attaches to the same buffer. With respect to the syntax highlighting I don't think the version on Github is remotely up to date - I believe that variant still depends on simply lexing the visible buffer rather than cache the state, but I may be wrong. Just lexing the visible buffer was my quick and dirty starting point to have something, and works surprisingly well (but it gets imprecise and annoying if you e.g. have start of block comments moving in and out of view, hence the switch to caching the Rouge state to make it precise; the next step is to move the lexing to a separate thread in the server process instead of having the clients run it). It's also buggy, as I fix only the bugs which bothers me... Now that I've scared you sufficiently, if you have any questions, my e-mail is also on my profile.

jillesvangurp 5y ago

Hmm, makes me wonder if this data structure would also support CRDTs. Collaborative editing is a nice thing to be able to support. 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.

anchpop 5y ago
> 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/grcwy5c699d67b9c444219b60cdb90ccbabc7 https://writer.zohopublic.com/writer/published/grcwy5c699d67... [2]: https://martin.kleppmann.com/papers/move-op.pdf https://martin.kleppmann.com/papers/move-op.pdf

nsajko 5y ago

A must-read paper in this space is the 1998 paper by Charles Crowley, Data Structures for Text Sequences: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.1265&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48... It explores the space from a different angle: the paper doesn't mention ropes, but it promotes a data structure called a piece table (or sometimes piece chain, piece tree, ...). These two data structure approaches are orthogonal, in that ropes can be used to implement the piece tables' descriptor sequences. Some salient points from the paper about the advantages of the piece table: * All buffers used are either read-only or append-only, so they are easy to cache and work well over a network. * It follows that items never move once placed in a buffer, which is nice as pointers to items never need updating. * Implementing undo is easy. EDIT: this blog post is also nice: https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r...

dzaima 5y ago

I've been working on my own text editor (which I'm apparently not the only one doing that here), and my plan is to switch to using a single B-tree, where the leaf nodes, besides holding the text (and also a color list for basic syntax highlighting), also a list of "pointer" objects, which would hold the carets/extra highlighting references/whatnot. Means two objects per selection (separate start & end pointer), but only one tree to have to scan through.

raphlinus 5y ago

I'm happy to see them cite my Rope Science series. Looking back, there were some things that xi did wrong, most importantly separating the front-end from the back-end with async communication, but the data structures and text manipulation algorithms were solid. I'm considering starting a new, similar, series called "The Book of Monoids," which covers some of the same ground but with more of a focus on parallelism (GPU) than incremental computation.

phyrex 5y ago
Could you explain why you say that it was a mistake to separate the editor frontend from the backend?
- raphlinus 5y ago
  So... separating front-end from back-end in and of itself is not necessarily a problem, but using async to do it adds complexity that is not worth it. Originally, I was hoping that a CRDT or similar mechanisms could be used to smooth out all such problems in a general way (including letting plugins contribute their annotations without causing jank on the main thread), but I discovered that such a collaboration layer cannot hide the underlying explosion in the potential state space. I wrote about this in some detail: https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.html https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.h...
  - mwcampbell 5y ago
    Maybe it would have been better to embed the core inside platform-specific front-end apps using a synchronous FFI. But then, you also discovered that the platform-native GUIs are overrated, at least for this application. Addendum: One thing that excites me about Rust is the potential to cut down on the excessive use of IPC, by letting us implement reusable libraries in a safe language that imposes minimal runtime requirements, then use Rust's powerful metaprogramming features to auto-generate safe language bindings for those libraries. That's one reason I chose Rust for AccessKit. I know diplomat [1] is making some progress in this area. [1]: https://github.com/rust-diplomat/diplomat https://github.com/rust-diplomat/diplomat