martanne

Of course all data structures have different trade-offs. I just think the piece chain has some of the most favorable ones. The fragmentation issue you mention is true.

Its effects can be mitigated by:

1) storing the pieces in a balanced search tree instead of a linked list. This would make random access logarithmic in the number of non-consecutive changes.

2) implement some kind of compaction algorithm which merges adjacent changes. This would increase memory usage because not only the changed text but also some unrelated data in between would have to be stored in a contiguous memory region. Furthermore this duplication of "unchanged data" would harm some other nice properties of the data structure. For example marks could no longer be represented as simple pointers into the underlying buffers because their content would not be unique (i.e. a character could be part of multiple buffers).

The pointer chasing you mention is an issue for all non-trivial (i.e. not stored in a consecutive memory region) data structures. Screen updates are a non issue since the output region is of fixed size (a terminal). For syntax highlighting using LPeg the relevant text region is temporarily copied to a contiguous memory region. This is simplified by the fact that vis currently always soft wraps lines and does not support folds.

Gap buffers have other issues, for example you only have one gap. What happens if you support multiple cursors/selections which might be on totally different regions of the file? You will have to move the gap.

This is not an issue for a doubly-linked list of gap buffers unless the cursors are on the same line. However what happens if you have a single line file (like minified Javascript)?

Anyway I find the piece chain and its support for (non chronological) undo/redo as well as mark management rather elegant.

In practice it seems to work quite well for vis. I haven't encountered performance issue in daily usage. To the contrary users reported that is "blazing fast".

In the same vein as the article, the code for insertion can be found at[0]. The interesting thing about the piece chain is indeed that it is a persistent data structure.

This makes it relatively easy to implement non chronological undo/redo operations i.e. an undo tree.

Because old versions of the text are available one could for example link compiler error messages back to the state when the file was last saved. Thus after a long build only those errors which are still relevant (i.e. not already fixed in the meantime) would be displayed.

Piece chains also map well to POSIX system where the initial file can be mmap(2)-ed. That is the reason why vis supports editing of large files efficiently. All editing operations are independent of the file size, but linear in the number of non-consecutive changes. Of course things like go to line nn will have to read the file content, there is no way around that. But for example navigating using the nn% command is possible in constant time. The way syntax highlighting is implemented it should also (mostly) work for all types of files.

[0] https://github.com/martanne/vis/blob/master/text.c#L555

"Writing a standard C library from scratch is crazy. Its one of the most commoditized pieces of software. Its almost impossible to do it significantly better than existing implementations [...]"

As the musl developers have shown, this clearly not the case.

Switching from bionic to musl would indeed be interesting.

I'm all for experimenting with new ideas, however this seems to duplicate all the conceptual shortcomings I see in tmux.

First of all, session support and terminal multiplexing are two distinct features which shouldn't be intermingled. What ever happened to the Unix principle of doing one thing and doing it well? My take on this problem is a combination of abduco[1] and dvtm[2].

Next a built in copy mode seems wrong, there is no need to implement vi(m) or emacs key bindings when you can make use of the complete editor. That is why dvtm uses my vim clone vis[3] as a filter: the terminal (scroll back) content is piped to $EDITOR and whatever the editor writes to stdout is kept in a register to be pasted in other terminal windows.

Furthermore I think the completion menu should also be implemented as a standalone tool (using e.g. dmenu or slmenu) as is done for the vis file open dialog.

As a last point I consider Pyhton not really suitable for core system tools, if you want something more expressible than C then something like Rust would probably have been a better choice.

[1] https://github.com/martanne/abduco [2] https://github.com/martanne/dvtm [3] https://github.com/martanne/vis

I too find kakoune interesting and have recently begun to add multiple cursor/selection support to my vim like editor.

https://github.com/martanne/vis

I had the chance to take a Oberon related lecture and its simplicity is really nice. Some things found in Oberon, like tiling window management, I use everyday. The book describes the whole system including the RISC CPU design.

As part of the Niklaus Wirth Birthday Symposium to celebrate his 80th birthday he also gave a talk titled "Reviving a computer system of 25 years ago" (Abstract[0], Slides[1], Video[2]).

There was also a demonstration on the original hardware, the system really seemed ahead of its time.

Project Oberon also inspired me to write a text editor[3] using a piece table data structure as described in Chapter 5.

[0] http://wirth-symposium.ethz.ch/speakers.html#Wirth

[1] http://wirth-symposium.ethz.ch/slides/wirth.pdf

[2] http://www.multimedia.ethz.ch/conferences/2014/wirth/?doi=10...

[3] https://github.com/martanne/vis#why-another-text-editor

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.

[0] https://github.com/martanne/vis#text-management-using-a-piec...

[1] https://github.com/martanne/vis/blob/master/text.c#L1152

Did you consider contributing to libfirm[0]/cparser[1]

0: http://pp.ipd.kit.edu/firm/ 1: https://github.com/MatzeB/cparser

Since I've recently implemented a text editor based on a piece table myself, I spent some time researching where the concept was first used.

One of the first references (1974) I found was to the Bravo text editor for the Alto from Xerox PARC.

"Alto User’s Handbook" http://research.microsoft.com/en-us/um/people/blampson/15a-A...

Then in 1985 a text editor called Lara by J. Gutknecht who in the following years joined Wirth to build Project Oberon whose text management system is also based on a piece table.

"Concepts of the text editor Lara" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98....

If somebody as other, in particular earlier references, that would be interesting.

My recent implementation: https://github.com/martanne/vis/blob/master/text.c

If your window manager is not able to manage your windows to your liking, you might want to fix it? Arguably creating a new window per tab is the correct thing to do. This allows your window manager to do its job. It is also more flexible, for example you can use something like tabbed (http://tools.suckless.org/tabbed/) to group multiple applications into a tab-like interface.

As for the editor case, in dwm/dvtm lingo each editor instance (or filename?) would get its own (dynamic?) tag. Therefore you can easily switch to a view which only contains your editor related windows.

Again if your navigation among tmux windows is slow/cumbersome you might want to improve that instead of duplicating the functionality at another layer.

No. They are not the same and shouldn't be. Rather they should communicate with each other. That is vim shouldn't have its own window functionality but instead detect that it runs within a terminal multiplexer and instruct it to create a new window. When I find the time I will try to experiment with this design in vis.

https://github.com/martanne/vis

As for the copy mode, in my opinion the multiplexer should use the editor as a filter (which requires that the editor uses stderr for its regular output). The whole scroll back buffer is piped to the editor and whatever the editor writes to stdout is kept around in a copy buffer.

That is the way it is implemented in the latest dvtm releases.

http://www.brain-dump.org/projects/dvtm/

For some reason I share the feeling about emacs. However I personally prefer dwm in X11 environments and have thus written a "clone" for terminal/ssh sessions called dvtm.

http://www.brain-dump.org/projects/dvtm/

Then the underlying file is scanned. The performance of this depends on the number of non contiguous changes made to the document. At load time i.e. with no changes this will be relatively fast since it is a single memory mapped piece/buffer.

Further request are then either served from line 12345 or the start of the file, depending on which is nearer.

At the moment only the line number corresponding to the start of the viewable area is cached. Further requests are served based on that. Since the underlying pieces/buffers remain unchanged, one could also maintain a more complex data structure such as a balanced binary search tree.

Author here, both by email or by using the aforementioned github repository is fine.

In my opinion starting out from the mess that vim's code base has become over the years, can't result in something good.

That is why I started from scratch:

https://github.com/martanne/vis