FYI: GtkText current design issues

[Derek Simkowiak <dereks kd-dev com>]

	I'm one of the people working on a replacement GtkText widget.
This email describes some of the issues I'm currently dealing with.  See
prior messages prefixed "FYI: GtkText" for further info.

	I've been working on the replacement for the LineCache list.

	Originally, the LineCache was supposed to be a cache of computed
geometry information about the lines that are currently on the screen,
plus a few above and below the currently displayed lines, for making
drawing faster.  However, for some reason it was decided to never expire
that cache, and instead to keep a linked list of information about every
line (including wrapped lines) in the displayed file.  Owen sent out a
message about this a while ago.

	I've been trying to decide if I need to maintain a linked list of
information about each of the text file's lines.  I have decided that I do
need to maintain such information.

	One of the design requirements for my widget is word- and
line-wrapping to the current width of the window.  That is already
implemented in the current GtkText, and is no big deal; however, unlike
the GtkText, I want the user to be able to save files with a \n inserted
at the wrap points.  The wrap point could be the window width, or a
specified column.

	I also want to be able to store bookmarks (and later, when I write
a GUI interface to gdb, breakpoints) at certain lines.  I'm thinking of
bookmarks as implemented in the Win32 program "TextPad".

	If I don't maintain information about every line, then when I go
to save the text file I would need to 'virtually render' each of the lines
in the file, even the ones that were not currently visible, in order to
compute where the line would wrap if it were displayed onscreen (so I
could insert a \n into the buffer at that point).  That sounds like it
would be very slow.  Also, if I don't maintain information about every
line, I'd need to maintain separate linked lists for the bookmarks and
breakpoints, which would then need to be corrected everytime I inserted or
deleted a line.

	GtkExText (a GtkText replacement that Mikael Hermansson is working
on) currently has a "GtkExTextLineData" struct, which is the following:

/* this is a wrapped and sshould be public for the user */
/* this calculates startpos and endpos */
/* and the return it to the user */
/* structure is READONLY for the user */
typedef struct _GtkExTextLineData
{
        /* in text startpos */
        gint startpos;
        /* in text endpos */          
        gint endpos;
        /* the line number */
        gint line_number;
        /* line height */
        gint line_height;

        /* first line property OR nearest backward (maybe prev line) */
        GtkExTextProperty *property_first;

        /* the real lineptr */   
        LineCache *lineptr;
} GtkExTextLineData;

	...which is the kind of thing I'm thinking of (FYI, he does not
maintain a list of such structs, he only caches the first visible line in
such a struct).  I believe that storing the startposition and endposition
of each line is futile, because if I enter text near the beginning of the
file I need to correct every startpos and endpos of every line that comes
after the insertion point, at every keystroke.  In a file with 50,000
lines, that could really suck.

	I tried to figure out if I should store the linenumber (in the
file, i.e. as would be reported by grep or gdb) in my line struct, but
that again is a number that would need to be corrected everytime I hit the
ENTER key.  That could get real slow if I inserted a line at the beginning
of a large file.

	In general, having any data in a linked list which would need to
be "corrected" due to an insertion or deletion is a bad idea.

	I also tried to figure out an algorithm faster than a linked list.
I thought perhaps using a hash table, where the key was the line number of
the line in question.  Unfortunately, as soon as I inserted a line near
the beginning of the file all my keys would be invalidated.  I thought
about a linked list, similar to the TextProperty, that stored offsets for
certain sections of the file (so that my hash keys would be +5 or -3, if I
deleted 5 lines or inserted 3 lines) but that turned out to be stupid.

	I suspect that a tree might be useful here.  Note to self: figure
out how a tree would be useful...

	The current forerunner idea is storing a linked list of line data
that, besides things like pixel height and width, and whether or not the
line is a bookmark (or a breakpoint), would only contain a length (in
characters), instead of an absolute offset.  Then, I would maintain the
current line number manually (by counting the number of \n's between one
position and the next, and at every ENTER keystroke).  This is how the
PropertyList is currently done.  Then, if I insert a line in the middle of
the file, I'd just splice in that list element.  And moving from one line
to the next would be as easy as figuring the number of lines forward or
backward (count the \n's), and then have a for loop akin to

for (i=0; i < number_of_lines_moved; i++) {
	line_data_element = line_data_element->next;
}

	Another issue I'm dealing with is the whole linenumbers thing.  
One design goal of the new GtkText is to be able to display the current
line number (ala TextPad).  However, if a line is wrapped, then it should
not have an associated line number, because it is really a continuation of
the line before it.

	So now I have a linked list of LineData where some of the lines
correspond to line numbers, and some don't (because they are just wrapped
lines).  Suddenly my little for loop above won't work.

	One solution is to simply add a gboolean "is_a_wrapped_line" to
the LineData struct, and if it's a wrapped line then simply not count it
as I iterate through the list.  The current GtkText has such a variable.  
But another, more interesting idea I'm playing with is having each node of
the linked list have a linked list within it, which contained any 'child'
lines (where a child line is a line that is just a wrap of a 'parent'
line, and every 'parent' line has an associated line number in the text
file).  This would let me maintain the list of 'parent' nodes, and have a
one-to-one relationship between lines of text in the file and displayed
'parent' lines in the file.  The biggest problem I see with this scheme is
that it would be very messy to write.

	Generally speaking, I'm a bit concerned about the heavy use of
linked lists in my current design.  The DataBuffer has a property list, a
tab list, and now I'm considering a separate LineData list (which would
probably wind up in the Renderer struct).  It just seems that for
sequential data, such as a text buffer, lists are the easiest to work with
because you can splice them in (or out) without touching any of the other
nodes, and they always remain in sequence without doing any extra
calculations.

	Anyway, that's what I've been working on.  After this is
finalized, my structures should be done and I can begin on the API, which
is only one step away from actually coding :).  As always,
feedback/suggestions are welcome.


Thanks,
Derek Simkowiak
dereks@kd-dev.com