You know, it's funny how it's 2015 and we're just dripping with raw power on our developer machines, yet, open a few hundred kilobytes of text and accidentally invoke a handful of O(n^2) algorithms and <i>blammo</i>, there goes all your power. Sobering.<p>Edit: We need a type system which makes O(n^2) algorithms illegal. (Yes... I know what I just dialed up. You can't see it, but I'm giving a very big ol' evil grin.)
A piece table[0] solves this rather elegantly. Since it is a persistent data structure, a mark can be represented as a pointer into an underlying buffer. If the corresponding text is deleted, marks are updated automatically, since the pointer is no longer reachable from the piece chain. Lookup is linear[1] (or logarithmic if you store pieces in a balanced search tree) in the number of pieces i.e. non-consecutive editing operations.<p>[0] <a href="https://github.com/martanne/vis#text-management-using-a-piece-tablechain" rel="nofollow">https://github.com/martanne/vis#text-management-using-a-piec...</a><p>[1] <a href="https://github.com/martanne/vis/blob/master/text.c#L1152" rel="nofollow">https://github.com/martanne/vis/blob/master/text.c#L1152</a>
I tried out Atom a few weeks ago. I loved the UI! Absolutely fantastic, beautiful, nothing but praise there.<p>But I had so many issues with stability, and really missed small but important features that were present in my other editors. I also found that most of the plugins worked either poorly or sporadically.<p>In the end, I decided that it was not worth either using Atom or spending time contributing to it when I have some "pretty close" solutions today. Definitely looking forward to the 1.0 version though, and hats off to all those spending their time contributing to it. I'm sure it's going to become something great!
I actually just retried Atom yesterday. Aside from the normal complaints (it's sloooww, undo doesn't affect markers or selections), one thing that struck me is that markers can't be zero-width. Well, they can but they won't show up. I'm wondering if this is related to the technique mentioned here - it's certainly been a pain to work around. Sublime Text even has multiple options for this (DRAW_EMPTY and DRAW_EMPTY_AS_OVERWRITE).<p>That said, I'm loving the API design. Coming from Sublime Text, it's a massive upgrade. The ability to embed literally anything a web browser can render in a well-designed framework is mindblowing.
Didn't the Xanadu project solve this problem in 1972?<p><a href="https://en.wikipedia.org/wiki/Enfilade_%28Xanadu%29" rel="nofollow">https://en.wikipedia.org/wiki/Enfilade_%28Xanadu%29</a><p>Solve it, keep it secret, and then fail to properly write about it to this day.
I really, really, don't get the whole "implement everything using web technologies" thing. As an outsider from that dev ecosystem it looks like the youtube videos you see of people implementing electronic circuits in Minecraft.
If you thought this was an interesting article, here 's the obligatory link to just about the only book on crafting a text editor, "Craft of Text Editing": <a href="http://www.finseth.com/craft/" rel="nofollow">http://www.finseth.com/craft/</a>
Recently I learned all contributors will receive a gift for Atom pre-1.0, and when I asked a Github stuff when will I receive the gift (I'm moving during this summer) he mentioned it would be sent out in early July. I guess we can expect a pre-1.0 before August.<p>One of the main remaining functionality to be implemented is good support for large files. Looking at this issue [1], it seems Atom team is making some progress but there are still some problems to be tackled.<p>In 0.208.0 (released 7 days ago) they mentioned in the changelog <i>Atom now opens files larger than 2MB with syntax highlighting, soft wrap, and folds disabled. We'll work on raising the limits with these features enabled moving forward</i>. Little bit disappointed at the progress as you could open large file with these features disabled long time ago through a package "view-tail-large-files".<p>Just updated to 0.209.0 and using ember.js (1.9 MB) to test. Editing/scrolling has some delays but it's better than previous versions.<p>Good luck Atom team!<p>[1]: <a href="https://github.com/atom/atom/issues/307#event-325455529" rel="nofollow">https://github.com/atom/atom/issues/307#event-325455529</a>
Appreciate the candidness of the team writing about their naive approach. Definitely would have been a simpler fix to just search the currently visible text, but I'm glad they fixed the root issue to make markers more efficient for all.
This kind of knowledge and experience exists in Microsoft campus for years thanks to Visual Studio team. That's why Code is much more efficient. I only wish if it was open source so I could totally move away from Sublime Text.
This reminds me of how I re-implemented nested sets in relational databases as spans in a "coordinate" system.<p><pre><code> | Root |
| Node | Node|
| Node | Node |
</code></pre>
I stored only "X" and "Y" coordinates for every node, so you had to read "next" node in a row to get current node's "size".<p>It was a bit more human-readable when looking at the data. More importantly, it reduced (on average) the number of nodes I needed to update on insert compared to nested set and gave an easy way of retrieving immediate children. But you still had to "move over" all the nodes "right" of the one you're inserting.<p>The structure in the article looks eerily similar. I wonder whether it's somehow possible to apply GitHub's optimization to this "coordinate" based schema and make it relative without messing up the benefits of column indexing. Hm...
Vim also has a similar optimization: when a file changes, Vim only runs syntax highlighter on a visible part of the text + some buffer in both directions.
Hmmm... So the article seems to suggest that for every insertion of a character, a log time lookup is made. Is that really the case? If so, why is the leaf node that the cursor is in not saved? If you were to use a B+-tree implementation then you would already have access to neighbour pointers for rebalancing purposes, making the majority of incremental changes very cheap (constant time). This is just a thought, there may be good reasons why it's not possible.
One thing I love about vanilla JS is that you can both set and get with the same property. I wonder if having both setters and getters is enforced by CoffeeScript or a design decision of the Atom team!?