Data Structures in the Fleet Editor
blog.jetbrains.com
blog.jetbrains.com
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-r...
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.
I wrote about this in some detail: https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.h...
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.
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.
Is this your editor? https://github.com/vidarh/re
Found it through your profile page. Thanks!
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.
I am not scared, I think dogfooding a text editor is remarkable. But I am worried about the time it takes to get it working and get used to it.
I don't know how familiar you are with Ruby, but DrB lets you remote Ruby objects pretty trivially. So the first thing the editor does on startup is try to connect to a server holding the buffers, and if one isn't running it'll spawn itself in server mode.
The server on startup reloads the latest snapshot of all the buffers from a JSON file. I can delete those buffers, but currently my server process holds 1757 buffers loaded from about 52MB of JSON. Some of those buffers have literally been "open" for several years.
Because of DrB remoting the buffer storage like that is a couple of hundred lines of code total. The server runs a thread that snapshots the buffers to disk every few seconds, so if the server crashes I won't lose much unless things are heavily corrupted. I'm actually at a point where I'd like to start paring that back because crashes are so rare that there's no point snapshotting that often (but I like not having to think about whether or not I've saved files before shutting down my laptop).
The beauty of this is that DrB forwards everything you want it to, including exceptions caused by the server-side code. Which means that short of me doing something stupid that silently corrupts the buffers, it takes a lot to bring down the server so badly that I lose the ability to keep using existing open editor windows.
Couple that with an exception handler that throws me into Pry (a REPL), and even a server-side exception will "just" throw me to a repl where I can inspect both the client-side and server-side state, including taking steps to e.g. save anything important.
I found that once I felt confident I wouldn't lose data putting up with bugs and missing pieces to get to the point where I used it daily was pretty easy. To the point where most of the time I edit the editor source code in itself, and run my editor instances from my editor working directory. Of course now and again I end up being forced to use another instance because I've broken something, but it also helps expose bugs quickly so it's worth it.
Worst case scenario is if you open something like a block comment which doesn't close and doesn't hit an error condition which resets the parser state. If you need to consider large files that's a reason to re-parse the buffer lazily in the background...
But, yes, if you write your own parsers you certainly would also need to ensure the state is as compact as possible.
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.
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...
Although webstorm can't handle large typescript projects with a lot of computed type as well as vs code.
You can do better than log if you care to; just grow the buffer more quickly. It's just that exponential growth tends to work pretty well (and, notably, amortizes the overhead of copying such that it is O(1)). Also: people tend to take breaks when typing, so you can asynchronously try to grow the buffer when it is close to full.
Before modern JavaScript VMs, I made an in-browser text editor, and I tried using a finger-tree data structure with string segments. It was extremely slow. I replaced it with two strings. Then it ran at human speeds. Memcpying the whole string upon a keypress was faster than some fancy data structure.
The moment you're willing to set an arbitrary limit above which you're ok with dropping performance, you can go very simple the way you did.
And that limit where things start to slow down can be far over the size of files most people need most of the time.
For my own part I'm fine with falling back to e.g. emacs the one time every few months I need do do something with an unusually large file.
For complex analysis of the code-base, sure, you may want to build an AST. For my part I have no interest in having that functionality in-process in the editor - I'd rather have that provided by an external service.
How? You have a bracket `[` at start of 2GB file and the closing bracket `]` somewhere at end at end of the file.
Without analysis you can't tell where it is.
> The moment you're willing to set an arbitrary limit above which you're ok with dropping performance, you can go very simple the way you did.
and this:
> For my own part I'm fine with falling back to e.g. emacs the one time every few months I need do do something with an unusually large file.
Point being I have no interest in making my editor handle 2GB files, because I don't edit 2GB files. I may occasionally happen to want to look at a large log file or something, in which case I'm happy to use Emacs. Or grep.
To this you answered:
> You still can't avoid the performance penalty of a tree allocation for something like bracket pairing. Or AST analysis or any one of billion things people want from a code editor.
And at least for bracket pairing this is true if you want to apply it to 2GB files and want to be able to quickly find the closing token, but that was explicitly out of scope of what I'm talking about; I'd explicitly excluded large files from consideration in the comment you replied to.
For the types of files I'm interested in handling - up to tens of thousands of lines but beyond that I really don't care - just storing the parser state per line coupled with linearly scanning as needed is more than fast enough. Even in Ruby, which is what I'm using.
You'll note my objection was not to doing analysis, but to the need for keeping any more complex structure in sync over the data. My editor uses just a plain array of lines represented as strings.
It will break horribly on huge files.
That's perfectly fine.
The point of the comment you replied to was explicitly to argue that for some editors it'd be just fine to make the explicit design choice not to cater for extreme cases like that.
Of course I'm not arguing for all editors to do this. Then I wouldn't have anything to use on the rare cases I need it. I'm arguing for people to consider whether their editor need to able to handle all kinds of outliers; maybe it need to - Jetbrains probably do need their editor to for commercial reasons - maybe it doesn't; mine does not need to.
Instead I optimise for what makes it pleasant for me for my common case, and fall back to emacs the once every few months where I for some reason need to do something with an absurdly large file.
> For my own part I'm fine with falling back > That's perfectly fine.
That's for you. I want to open a huge XML file and edit it with autocomplete.
I mean you could just say. I'm ok with Notepad. Ok. Sure. I'm not.
> My editor uses just a plain array of lines represented as strings.
Any naive approach is going to run into edge cases quickly[1]. Any more sophisticated approach is going to run into performance issues.
> It will break horribly on huge files.
I suspect it will break waaaay before that. Even using some language with greater complexity would cause issues.
[1] For example using regex to color syntax. Reasonably fast yes, but fails in any moderately complex scenario.
I get that, which is why I specified what it was I had replied to in order to clear it up.
> That's for you. I want to open a huge XML file and edit it with autocomplete.
That's fine. My editor is for me, not for you. To me, if you have to do bracket matching on a 2GB XML file an editor is the wrong tool. I'd work with that in a REPL. But that's me. You're totally free to pick your editor based on the need to handle 2GB files, just as I'm free not care one iota about opening 2GB files.
Hence my point that a lot of people don't seem to think about whether or not they actually need this. I decided I don't need it, and it let me simplify things a lot. It won't work for everyone, and that's fine.
> I mean you could just say. I'm ok with Notepad. Ok. Sure. I'm not.
Well, if I'd been ok with notepad, I'd have used notepad. I wrote my own editor because I'm not ok with Notepad. Or Emacs. The tradeoffs I care about are very different.
> Any naive approach is going to run into edge cases quickly[1]. Any more sophisticated approach is going to run into performance issues.
For large files, yes. It's more than fast enough to run just fine - even in pure Ruby - on files of the sizes I pointed out are the sizes I've decided I care about.
> [1] For example using regex to color syntax. Reasonably fast yes, but fails in any moderately complex scenario.
Which is why I'm using Rouge for the syntax-highlighting for my editor. It uses Regex for low level lexing where people choose to, but it supports state machines and multi-layered lexing or your own custom code. It supports all the languages I care about and dozens more just fine. My approach of caching the lexer state works just fine with Rouge and the approach I've outlined to e.g. parse my Ruby code with a precise Ruby mode, switch to a Markdown mode inside comment blocks, and feed the output of that into a layer that applies further custom rules based on my preferences. All without needing to build an AST for any of those.
> I suspect it will break waaaay before that. Even using some language with greater complexity would cause issues.
It handles every language supported by Rouge [1] just fine, and that's far more than I have need for.
[1] https://github.com/rouge-ruby/rouge/blob/master/docs/Languag...
Ok. But tbh I hate REPLs and/or CLI. Text is just better served by a visual text editor.
Then you can't really compare something for general use case to something used for you.
> Which is why I'm using...
It was an example how naive approaches failed. Your personal editor doesn't particularly interests me.
For my part I love a repl. My editor has a repl too. Different needs.
> It was an example how naive approaches failed. Your personal editor doesn't particularly interests me.
You made pronouncements about how things would fail that you implied would affect a simplified model. I've pointed out why those assumptions don't hold under the design constraints I stated in my first comments. I get that you replied on the basis of the general case. That's fine - we simply talked past each other in that respect.
In that respect my editor serves as an example of viability, that's all. Nobody is asking you to be interested in it. If anything I'm explicitly warning people against expecting it to be usable for them.
That your needs from an editor are different is fine. I'm not questioning the validity of your needs for you.
And you said, they do fail? Can I load a several GB of data from weather or LHC?
I haven't really heard of Rouge or if something else that uses it. But some of the choices you mentioned (like external services doing code analysis) is some of the stuff I've seen as dead ends when making a code editor (see Lure of Modular software).
https://raphlinus.github.io/xi/2020/06/27/xi-retrospective.h...
------
Like ok, you made a toy editor that works in your case. Ok.
Good for you, but for me and probably 90% of people, if it can't open large file, can't automcomplete, can't reference XSD schema, can't reference, can't give good overall structure, can't refactor, can't recognize SQL in strings, can't deal with macros, source gens, debugging etc. It's not that useful.
It "fails" in the same way a car fails to fly. I set out my requirements. It meets my requirements. You're intent on arguing over how my car really should have wings and a jet engine.
> I haven't really heard of Rouge or if something else that uses it.
Gitlab is one of the most prominent examples.
> But some of the choices you mentioned (like external services doing code analysis) is some of the stuff I've seen as dead ends when making a code editor (see Lure of Modular software).
Every code editor that uses language servers makes that choice. Most modern code editors either have direct support or extensions providing client support for it, with a more coming on a regular basis. I was sceptical too, but writing my own editor very quickly demonstrated that the benefits far outweighed the downsides.
It's only hard to make this work if you make it hard on yourself. Xi made it hard on themselves by implementing their own RPC and using CRDTs instead of using "off the shelf" components and making functionality tradeoffs. That's a valid choice, but it makes their experiences with modularity relatively uninteresting when considering editors that makes entirely different choices.
To specifically address one point in the link you gave:
> I think it’s worth asking the question: is it useful to have the front-end continue after the core crashes, or the other way around? I think probably not; in the latter case it might be able to safely save the file, but you can also do that by frequently checkpointing.
E.g. to this I'd answer a resounding yes, because unlike their design 1) because of the use of Ruby and DrB, most bugs that could have taken down the server doesn't take down the server because the exceptions gets forwarded to the client. 2) every window is a client in my case, so a crashing frontend means one window goes. My - as of writing this - 16 other open editor windows do not. I can make changes to the editor itself and only affect the frontends I choose to restart. I've kept meaning to add ability for the clients to reconnect, but because of #1 it's exceptionally hard to make the server crash even if I make a severely buggy update, so it's stayed far down my priority list.
More importantly, this approach meant I did not have to build any GUI support at all to support multi-window editing. Splitting a pane is done by starting another client. It's part of a general decision to focus on minimalism.
Xi had different design goals, and Xi made tradeoffs that always sounded like a lot of bikeshedding ("hand-rolled our own xi-rpc layer" for example) to me. A lot of it was interesting, but at the same time it's pretty much the opposite of what I aimed for. Xi aimed for perfectionism where I aimed for MVPs. The Xi rope implementation alone has a higher LOC count than my entire editor... If that meets their goals, then that's fine.
My entire backend is ~500 lines. Including the buffer storage. It wouldn't be that small if it tried to cater for 2GB files, or tried to cater for concurrent editing of the same piece of data from multiple clients or cater for multiple frontends written by different people in different languages.
What my design tradeoffs got me was the ability to build an editor that was capable of being my main work tool within a few months.
My point is not that other people should use my editor. Absolutely not - I have no interest in supporting that. My point is that by building a special purpose tool and picking ready-made components where possible and making choices that focuses on modular design and optimises for simplicity over making something general, I now have an editor tailor-made for my own needs in a way that other editors I have used didn't.
> Like ok, you made a toy editor that works in your case. Ok.
The fact that it works in my case means it is not a toy editor, no matter how rude you try to be about it. It's my main work tool, and has been for several years, out of choice. I have plenty of editors installed. I switched slowly, over time, as I increasingly got the features in place that made me actually prefer to use it. That it's not a tool that suits you does not make it a toy.
This kind of attitude that something needs to be generalist to be worthwhile is something I've opposed my entire career. A whole lot of things would be a lot better if more people carefully considered whether to build yet another generalist tool or whether to build specialist tooling that does a smaller subset of things well.
I get paid a lot of money to write specialist tools that will never be available to most people, and would be of little use to most people.
> Good for you, but for me and probably 90% of people, if it can't open large file, can't automcomplete, can't reference XSD schema, can't reference, can't give good overall structure, can't refactor, can't recognize SQL in strings, can't deal with macros, source gens, debugging etc. It's not that useful.
That's fine. I didn't write my editor with the intent of 90% of people using it. I wrote it with the intent of using it myself. It has the features I prioritise, and not a single feature I don't use. That means alongside the software development I do to e.g. support the ability to read the front matter of the novels I write as a hobby and cross reference and highlight character and location names matters, while XSD doesn't matter to me one bit. Not for the last 15 years at least. If XSD had mattered to me, I'd have added support for it, as supporting it is trivial (been there, written schema validators and code generators, got the PTSD).
You seem to still struggle with the idea that not every editor need to be designed to cater for you or for the needs of everyone else. Which demonstrates that you're still struggling to deal with my original point:
That there are benefits to not aiming to build a general purpose tool if a general purpose tool isn't what you need.
If you're optimizing for a 2 GB apache log, you're probably focusing on the wrong thing.
https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r...
Not sure if this is still the case, but it was as of 2018.
Its really kind of fascinating to me, all the different ways we've come up with over the years just to manipulate text.
One of the things that strikes me is how much effort goes into making these editors work well with absurdly large files, rather than more editors punting on that and having people fall back on specific tools for huge files.
For my own editor I basically decided to ignore large files entirely and fall back on using emacs for the very rare case where I need to open an absurdly large file.
I know that's a luxury Jetbrains doesn't have, because we've come to expect all editors to handle ridiculous sized files well.
But the point being that for reasonably sized files - up to tens of thousands of lines - just an array of strings is more than fast enough.
Even with an editor like my personal one (not really usable for anyone else, though I've started packaging up parts of the code) written in Ruby (which introduces a substantial overhead per string).
I think if I ever decide to make my editor handle really huge files, I'll "just" split them in suitably large chunks and lazily do the necessary processing as needed
That falls apart the moment you need some non-basic feature like matching open/closed brackets/elements, etc.
Or references. Or refactoring ...
That said, it's not true that it needs to affect features like the ones you mentioned - all you need is to add a facade that gives your tools whatever interface to the buffer they need. As it is, my editor stores its buffer in a separate server process, because it was trivial to do so and gave me a bunch of benefits like multiple clients connecting to the same buffer, which also means I can trivially have out-of-process services augmenting the buffers with additional state lazily without needing to know anything about how the buffers are represented. The server process + a facade for the current buffer implementation + most of the basic editing operations the rest is built on is ~500 lines of code.
So why did TECO use a gap buffer? The gap buffer was an easy way to manage an edit buffer back when machine clock speeds were measured in kilohertz and RAM in kilobytes. There were no fonts (no rendering at all), six or seven bit characters, oh, and the machines were often timeshared.
Likewise, vi is just a visual addition to ed, itself a clone of the Multics qed, itself a clone of qed on earlier machines. Those machines were, by modern standards, equally resource starved.
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.