[Toybox] [PATCH] vi: Replace linelist with mem_block based design

[Jarno Mäkipää]

On Fri, Jan 17, 2020 at 7:48 PM enh <enh at google.com> wrote:
>
> On Fri, Jan 17, 2020 at 1:10 AM Jarno Mäkipää <jmakip87 at gmail.com> wrote:
> >
> > I think both has ups and downs, piece table is better for large files,
> > and also for doing repeated inserts in random parts of file, such as
> > regexp find and replace.
> >
> > Gap buffer is better for doing lots of inserts around same area.
>
> also known as "typing", the common case :-)

Vi is not like basic editors where you just do small movements with
cursor keys and type alot, instead you use movement commands, jump
into line numbers, yank data into registers etc...

>
> > Also
> > searching is easier since it has 2 continuous regions.
>
> historically i've actually just cheated and moved the gap to the end
> of the file. that lets you just use existing regex implementations
> without having to try to get them to work across gaps. afaik, a piece
> table will require a regular expression API that takes something like
> a Java CharSequence where you can hide that the bytes aren't actually
> consecutive. which would be fine if you weren't trying to use C.

This is the best benefit on gap buffer I see. With my version of piece
table regexp search needs to copy some data into temporary buffer
unless file has no inserts.

>
> > Also data does
> > not need to be copied as much for drawing, only around gap. Good for
> > small files. Cant really open large files since it needs heap of
> > filesize+gap or perhaps as read-only gap can be zero and memory be
> > mmap() into file.
>
> gap is usually small. humans can't type fast, and computers can copy
> large blocks of memory *very* fast, so even 128 bytes or whatever
> amortizes fine. (you can special case "paste" so it doesn't get
> pathological on large pastes.)
>
> > both suck at jumping into line number
>
> but piece table sucks a lot harder, because you have to effectively
> apply all the edits to work out where you are.

Yeah finding text under cursor position on gap buffer is just
multiply, but ordered piece table worst case is iterate number of
inserts + multiply

But I think that yank registers and marks could benefit from piece
table. I dont have any idea how to implement marks in gap buffer. With
piece table I could just slice the current line when user saves mark,
and check if given slice still exist when user try to jump into mark.
Well if we decide to only have one yank register and marks reset after
every edit, then gap buffer is fine.

>
> > Ideally commands such as less should share vi code just editing
> > commands disabled, so buffer opening, drawing, searching, cursoring
> > and jumping should be same.
> >
> > Right now I only have 2 functions for insert and cut, and i think its
> > all needed.
>
> like i said (you should read those papers), you actually only need
> "replace". doesn't make much difference yet (and i've certainly had
> one-line helpers to translate insert and cut in replace historically),
> but only having one primitive edit makes undo/redo easier when you get
> to them.
>
> > int insert_str(const char *data, size_t offset, size_t size, size_t len,
> >   enum alloc_flag type)
> > int cut_str(size_t offset, size_t len)
> >
> > and few commands for searching line breaks, copying current line,
> > checking that current codepoint is valid for cursoring...
> > size_t text_strchr(size_t offset, char c)
> > size_t text_strrchr(size_t offset, char c)
> > size_t text_filesize()
> > char text_byte(size_t offset)
> > int text_codepoint(char *dest, size_t offset)
> > size_t text_getline(char *dest, size_t offset, size_t max_len)
> >
> > So I think now that I added extra layer we can still later switch into
> > gap_buffer, if we dont touch directly into buffer handing in actual vi
> > commands? (and some of this abstraction can be removed when cleaning
> > up codebase after we are satisfied what type of buffer we should use)
>
> personally i'd go the other way. gap buffer is a lot easier, and you
> can always switch to a piece table if/when it proves necessary. if we
> were aiming for syntax coloring, say, that would be a mark in favor of
> the piece table. but aiui we're not [and i've seen a separate table of
> style runs work fine/better for that in the past anyway]. like i said,
> it would be good to explicitly agree the goals/non-goals with rob.
>


I think I fill finish up what I have to be in same level of
functionality as linelist one was. Since im very close to that. I will
send patch number 2 hopefully this weekend. If we decide to switch to
gap buffer later its much easier on top of this, than on top of
current master, since linelist based one iterated data directly on
linkedlists all over the vi.c.


-Jarno