HN Explorer

Ask HN: How to learn about text editor architectures and implementations?

195 points by s3arch ↗ HN
I am a self taught developer. Its been more than 3 years. I know decent JavaScript, and full-stack developement knowledge. I recently started admiring text editors. I use vscode. I have also used VIM and EMACS. I tried reading their source code, also of atom, brackets, light table etc.

Honestly I don't understand anything. I am not able to make sense of the data flow and the architecture. I want to understand how text editors work under the hood. Also I want to understand the plugable architecture they use to extend the functionalities of the editor.

Please suggest me any articles, videos, conferences, blogs, where I can pick up the concepts. I have been troubled by this lack of knowledge and unclear path to access it.

Edit: Reasons for this quest: I am not here to create yet another text editor. But I do understand that they are one of the complex peice of software which still is under constant improvisation and developement. Also text processing is the one of the core concepts of computer science. A lot of algorithm and data structure knowledge is hidden inside it. Besides, I feel through real world projects one can learn alot about core computer science foundations.

76 comments

[ 3.4 ms ] story [ 140 ms ] thread
ketanmaheshwari
I would suggest start with getting familiar with the C programming language. I suggest use Beej's guide for C. Next, pick up the "The Linux Programming Interface" book by Michael Kerrisk. As you read the book you will get better at understanding source code of at least Vim and Emacs if not others.
teddyh
You want this:

The Craft of Text Editing

—or—

Emacs for the Modern World

–by–

Craig A. Finseth

https://www.finseth.com/craft/

RapperWhoMadeIt
As far as I know, some of these terminal text editors use the ncurses library to handle their "frontend", the way in which they properly display text in your terminal. As mentioned in another comment it is utmost necessary that you feel comfortable reading code in C (with a decent knowledge of syscalls) in order for you to understand the programs' source code. But when you have already achieved that level, you can start learning about ncurses with this basic tutorial [0].

[0] https://tldp.org/HOWTO/NCURSES-Programming-HOWTO/

Someone
https://news.ycombinator.com/item?id=20603567, discussing https://viewsourcecode.org/snaptoken/kilo/index.html probably will give you some hints.

Architecture-wise, you can start with an ordered list of lines, with each line stored as a string.

Features that complicate things are:

- supporting large documents and staying speedy (“replace all” is a good test case)

- supporting line wrapping or proportional fonts (makes it harder to translate between screen locations and (line, character) offsets)

- supporting Unicode (makes it harder to translate between screen locations and (line, byte position) offsets)

- syntax-colouring

- plug-ins

- regular expression based search (fairly simple for single-line search _if_ you store each line as a string; harder for custom data structures, as you can’t just use a regexp library)

- supporting larger-than-memory files (especially on systems without virtual memory, but I think that’s somewhat of a lost art)

- safely saving documents even if the disk doesn’t have space for two files (a lost art. Might not even have been fully solved, ever)

Edit: you also want to look at https://news.ycombinator.com/item?id=11244103, discussing https://ecc-comp.blogspot.com/2015/05/a-brief-glance-at-how-...

mkhnews
Yea, a double-linked list of lines or what some call a gap-buffer. And how to display it all is another big part.
amichail
For WYSIWYG scientific/math editors, see the open source TeXmacs.
jmiskovic
Lately I've been studying lite editor which is mostly Lua code. It's quite easy to read the code and follow along. Before that I wrote my own editor which kind of works, but it mostly made me appreciate the lite's design.

    https://github.com/rxi/lite
    https://rxi.github.io/lite_an_implementation_overview.html
    https://rxi.github.io/a_simple_undo_system.html
buescher
It's from a completely different time and point of view than "full-stack development", vi, or emacs, but Petter Hesselberg's Programming Industrial Strength Windows: Shrink-Wrap Your App! presents a complete text editor for Windows as an example of a complete "real-world" Windows application.
[deleted]
(comment deleted)
jesperlang
The rope data structure is an interesting concept worth checking out!

https://en.wikipedia.org/wiki/Rope_(data_structure)

evanmoran
Glad to see this here. This is was my original thought too as one of the original data structures for text editing. It's used to quickly insert/delete within a very large string.

Has anyone used other mechanisms for large document types? It seems like an array of paragraphs, each containing a simple string could probably handle most editing tasks and might be easier to layout and manage. Curious what other data structures people have used!

raphlinus
In my opinion, the rope is easily superior to these other types, but it also depends on whether your language supports abstractions well. The problem with an "array of paragraphs" is that it helps when your problem involves the paragraph boundary, but gets in the way when it doesn't. For example, pressing backspace at the beginning of paragraph 2 causes a merge of paragraphs 1 and 2, which is not trivial. With a rope, it's the same as deleting a backspace within a simple string, once you have a good rope library under you.

The other big reason to prefer a rope is that the worst case complexity is excellent. Basically all incremental operations are O(log n). With an "array of paragraphs" you get various pathological performance cases such as a huge number of small paragraphs or one very big one.

A good rope implementation is not trivial, but when done right it hides its internal complexity from the layer above. And it's a solved problem. There are at least two or three solid rope crates for Rust (just to pick the language I'm most familiar with), and will likely be more, as people find it fun to implement.

jhallenworld
I would say the key is to abstract the lower level data structure, so that it could be (relatively) easily swapped-out. So for example, don't start with a doubly-linked list of lines or for sure your upper level code is going to have pointers to line headers. Better to have some kind of smart pointer which is an abstract index into the edit buffer and provide functions like "find next line", "find previous line".

BTW, with any of these tree-based structures (like rope) you can store other meta-data in the the headers to make a fast index. For example, I would put a newline count in the rope headers, to make find a particular line a fast operation.

jhallenworld
I used a double-linked list of gap buffers (each in its own fixed length block that can swapped out to disk) for JOE. It works great on large files, but still I would start with rope these days.

Gap buffer was appealing on really slow machines, where you are counting cycles on each key-press. If the gap is at the right position, the cycle count is very low. But you can probably do the same even with a tree-structure: you need to keep a pointer to the leaf in the abstract pointer used for the cursor.

Also I would tie in the undo system to the data structure if possible. Rope does this with copy-on-write. Every version of the file could be a different top-node, and most middle and leaf nodes would be shared between revisions.

scandox
You could start by looking at something super simple like Kilo:

https://github.com/antirez/kilo

Even I could understand this one pretty well and that's no small matter.

sam_lowry_
The screencast by antirez is a joy to watch.
[deleted]
(comment deleted)
fcatalan
I loved following this one a few summers ago and even went beyond the end of the tutorial adding functionality and trying more advanced data structures. I think I would have ended with a completely usable hyper-personal editor but unicode support didn't look like fun.
danielbarla
Object oriented programming and design patterns in particular get a bad rap these days, however, the original Design Patterns book [1] has a case study chapter about designing a WYSIWYG document editor. Also, one of the authors, Erich Gamma, joined Microsoft in 2011, and works on the Monaco suite of components that VS Code is built on top of. So, while I am sure there's a fair bit of difference in the years since they wrote that book, as well as the needs of implementation in JS, I'd say it's a fairly good deep dive into some of the topics from one of the actual architects behind it.

Fair warning though, it's a fairly hard book to read. For a lighter, more fun intro to design patterns in particular, I always recommend Game Programming Patterns [2]

[1] https://www.amazon.com/Design-Patterns-Elements-Reusable-Obj...

[2] https://gameprogrammingpatterns.com/contents.html

forinti
I was once tasked with writing a simple text editor. I knew this book inside out so I decided to try putting the text into a tree the way it describes.

This made selecting text quite hard. So I gave up and just put the whole thing into an array. It made everything a lot easier.

armchairhacker
See RSyntaxTextArea (open-source code editor) and the underlying JTextArea / swing code.

There are a few weird design decisions especially in swing, but overall it's very easy to read and understand.

whartung
If you're interested in visual editors and if you're looking for something perhaps more accessible (and I can't honestly say how much it really is, I have not looked at it) then consider taking a look at 'less', the pager.

Less does almost everything an "editor" does, at least visually, except change text. It pages through text, forward and backward, line by line, it handles lines that are too long, tab expansion, it searches, even has an extended command set. (Can less do syntax coloring?)

It also handles files too big for memory. These are all editor problems. Mind its solutions may not be optimized for an editor, but it's certainly smaller.

Today, modern machines "suffer" from "too much" performance which actually frees you from not having to worry so much about the actual backing store, especially early on. Do you really intend to be editing a 2GB file? Honestly, how big is an average text file? And how many billion cycles per second does a modern CPU handle? Sucking the entire file in to RAM, and just pushing stuff around with block moves will take you very far on a modern machine. Not that you should not look at the other data structures (there are many), but you don't have to start there, depending on where your interest lies.

Also consider hunting down the book "Software Tools". There's two editions, the original and "Software Tools in Pascal". It's by Kernighan and Plauger. They go through in detail and write a version of the 'ed' line editor.

And if you really want to work on an editor, the CP/M world would love a new one. There, it's all about efficiency.

nicoburns
> Do you really intend to be editing a 2GB file?

I don't know about most people, but I deal with such files (usually JSON) on a weekly basis. It's surely one of the things that makes implementing text editors tricky.

hutzlibu
Most people won't, they will just get annoyed, if they accidently open a video and the editor hangs up for some time, trying to process it.

And I regulary work with JSON files the size of some MB, which already puts some editors into a real struggle.

Out of curiosity, why do you have so big files? (A whole DB as a json file?) And what editor do you use for them?

nicoburns
> A whole DB as a json file

More like a whole database table as a JSON file - I split the whole database export into tables using `jq` (an export from Firebase Realtime Database). I generally use sublime text to open them, it's quite happy with anything that will fit in RAM. For very large file it just shows a load bar while it loads it.

It was vital for exploring the shape of our data during a data migration to Postgres as our data was not very regular in shape and firebase's querying capabilities are pretty limited.

whartung
Honest question, do you just open the files, or do you change them and write them back out?

I, too, have dealt with huge files. My primary large file use case for vim is as an interactive grep, opening files, then just performing iterative filters reducing the file to something "manageable". If the file is too big, I might resort to raw streaming filters to temp files before going all vim on it (even vim has issues with huge files -- huge files are issues all their own).

But it's more a matter of pragmatism as to how far one wants to take a pet project like this. There's a curve of diminishing return depending on what someone wants from such a thing.

A single RAM buffer is a bad idea, to be sure, but raw horsepower of modern systems and CPUs cover up a lot of bad ideas. Simply the idea that you COULD mmap or even malloc a 2G buffer to suck the file in, and it would WORK, is enough to make ones teeth itch. I remember long a ago an article from someone encountering an early workstation with 1G of RAM, and the worlds it opened up. We have come far from those days.

If the OP is interested in buffer mechanics, then starting with an API backed by a simple buffer goes a long way. If they're interested in screen painting, window management, etc, then the RAM buffer may be all they need. Otherwise, they can work on replacing their back end with all of the assorted structures folks have mentioned, see what they like best, as they all have tradeoffs.

nicoburns
I don't often need to edit the files (I also mostly use for searching and my most common editing action would be pretty printing which I could well manage externally if need be). However, I very commonly accidentally edit the files due to a stray keypress, so if edits are not disabled entirely then not locking up or crashing if edits do occur would definitely be a requirement. Occasionally it useful to be able to edit, and it's nice to have at least an editor that can do this.
cmg
Just this morning I needed to do a global find/replace for a string in a 3GB .sql file. I was in VS Code anyway so tried that - but the app choked on it. Ended up going with sed and it worked perfectly.
antidnan
Prosemirror is a good place to start. https://prosemirror.net/docs/guide/ https://marijnhaverbeke.nl/blog/prosemirror.html

They have a well architected model, including plugins to extend functionality, see https://tiptap.dev/ which is built ontop of Prosemirror

bonus: The author talks about collaborative editing here: https://marijnhaverbeke.nl/blog/collaborative-editing.html

codethief
I came here to mention Marijn Haverbeke's blog! His articles (about ProseMirror but also CodeMirror) are full of insights!
evilhackerdude
Seconded! Marijn has thought about this stuff a _lot_.