Added Josh Macdonald's description of the Text widget's internals.

1 files changed, 477 insertions, 0 deletions

diff --git a/docs/text_widget.txt b/docs/text_widget.txt
new file mode 100644
index 0000000000..83d3b31e5a
--- /dev/null
+++ b/docs/text_widget.txt
@@ -0,0 +1,477 @@
+Date: Sun, 14 Sep 1997 20:17:06 -0700 (PDT)
+From: Josh MacDonald <jmacd@CS.Berkeley.EDU>
+To: gnome@athena.nuclecu.unam.mx, gtk-list@redhat.com
+Subject: [gtk-list] gtktext widget internal documentation
+
+
+Pete convinced me to just write up the text widget and let someone else
+finish it.  I'm pretty busy and have other commitments now.  Sorry.  I think
+I'm not the most qualified for some of the remaining work anyway, because I
+don't really know Gtk and it's event model very well.  Most of the work so 
+far was possible without knowing Gtk all that well, it was simply a data 
+structure exercise (though after reading this you might say it was a fairly
+complicated data structure exercise).  I'm happy to answer questions.
+
+-josh
+
+
+High level description:
+
+There are several layers of data structure to the widget.  They are
+seperated from each other as much as possible.  The first is a gapped
+text segment similar to the data structure Emacs uses for representing
+text.  Then there is a property list, which stores text properties for
+various ranges of text.  There is no direct relation between the text
+property list and the gapped text segment.  Finally there is a drawn
+line parameter cache to speed calculations when drawing and redrawing
+lines on screen.  In addition to these data structures, there are
+structures to help iterate over text in the buffer.
+
+The gapped text segment is quite simple.  It's parameters are (all
+parameters I mention here are in the structure GtkText):
+
+  guchar* text;
+  guint text_len;
+  guint gap_position;
+  guint gap_size;
+  guint text_end;
+
+TEXT is the buffer, TEXT_LEN is its allocated length.  TEXT_END is the
+length of the text, including the gap.  GAP_POSITION is the start of
+the gap, and GAP_SIZE is the gap's length.  Therefore, TEXT_END -
+GAP_SIZE is the length of the text in the buffer.  The macro
+TEXT_LENGTH returns this value.  To get the value of a character in
+the buffer, use the macro TEXT_INDEX(TEXT,INDEX).  This macro tests
+whether the index is less than the GAP_POSITION and returns
+TEXT[INDEX] or returns TEXT[GAP_SIZE+INDEX].  The function
+MOVE_GAP_TO_POINT positions the gap to a particular index.  The
+function MAKE_FORWARD_SPACE lengthens the gap to provide room for a
+certain number of characters.
+
+The property list is a doubly linked list (GList) of text property
+data for each contiguous set of characters with similar properties.
+The data field of the GList points to a TextProperty structure, which
+contains:
+
+  TextFont* font;
+  GdkColor* back_color;
+  GdkColor* fore_color;
+  guint length;
+
+Currently, only font and color data are contained in the property
+list, but it can be extended by modifying the INSERT_TEXT_PROPERTY,
+TEXT_PROPERTIES_EQUAL, and a few other procedures.  The text property
+structure does not contain an absolute offset, only a length.  As a
+result, inserting a character into the buffer simply requires moving
+the gap to the correct position, making room in the buffer, and either
+inserting a new property or extending the old one.  This logic is done
+by INSERT_TEXT_PROPERTY.  A similar procedure exists to delete from
+the text property list, DELETE_TEXT_PROPERTY.  Since the property
+structure doesn't contain an offset, insertion into the list is an
+O(1) operation.  All such operations act on the insertion point, which
+is the POINT field of the GtkText structure.
+
+The GtkPropertyMark structure is used for keeping track of the mapping
+between absolute buffer offsets and positions in the property list.
+These will be referred to as property marks.  Generally, there are
+four property marks the system keeps track of.  Two are trivial, the
+beginning and the end of the buffer are easy to find.  The other two
+are the insertion point (POINT) and the cursor point (CURSOR_MARK).
+All operations on the text buffer are done using a property mark as a
+sort of cursor to keep track of the alignment of the property list and
+the absolute buffer offset.  The GtkPropertyMark structure contains:
+
+  GList* property;
+  guint offset;
+  guint index;
+
+PROPERTY is a pointer at the current property list element.  INDEX is
+the absolute buffer index, and OFFSET is the offset of INDEX from the
+beginning of PROPERTY.  It is essential to keep property marks valid,
+or else you will have the wrong text properties at each property mark
+transition.  An important point is that all property marks are invalid
+after a buffer modification unless care is taken to keep them
+accurate.  That is the difficulty of the insert and delete operations,
+because as the next section describes, line data is cached and by
+neccesity contains text property marks.  The functions for operating
+and computing property marks are:
+
+ void advance_mark     (GtkPropertyMark* mark);
+ void decrement_mark   (GtkPropertyMark* mark);
+ void advance_mark_n   (GtkPropertyMark* mark, gint n);
+ void decrement_mark_n (GtkPropertyMark* mark, gint n);
+ void move_mark_n      (GtkPropertyMark* mark, gint n);
+
+ GtkPropertyMark find_mark      (GtkText* text, guint mark_position);
+ GtkPropertyMark find_mark_near (GtkText* text, guint mark_position,
+                                 const GtkPropertyMark* near);
+
+ADVANCE_MARK and DECREMENT_MARK modify the mark by plus or minus one
+buffer index.  ADVANCE_MARK_N and DECREMENT_MARK_N modify the mark by
+plus or minus N indices.  MOVE_MARK_N accepts a positive or negative
+argument.  FIND_MARK returns a mark at MARK_POSITION using a linear
+search from the nearest known property mark (the beginning, the end,
+the point, etc).  FIND_MARK_NEAR also does a linear search, but
+searches from the NEAR argument.  A number of macros exist at the top
+of the file for doing things like getting the current text property,
+or some component of the current property.  See the MARK_* macros.
+
+Next there is a LineParams structure which contains all the
+information neccesary to draw one line of text on screen.  When I say
+"line" here, I do not mean one line of text seperated by newlines,
+rather I mean one row of text on screen.  It is a matter of policy how
+visible lines are chosen and there are currently two policies,
+line-wrap and no-line-wrap.  I suspect it would not be difficult to
+implement new policies for doing such things as justification.  The
+LineParams structure includes the following fields:
+
+  guint font_ascent;
+  guint font_descent;
+  guint pixel_width;
+  guint displayable_chars;
+  guint wraps : 1;
+
+  PrevTabCont tab_cont;
+  PrevTabCont tab_cont_next;
+
+  GtkPropertyMark start;
+  GtkPropertyMark end;
+
+FONT_ASCENT and FONT_DESCENT are the maximum ascent and descent of any
+character in the line.  PIXEL_WIDTH is the number of pixels wide the
+drawn region is, though I don't think it's actually being used
+currently.  You may wish to remove this field, eventually, though I
+suspect it will come in handy implementing horizontal scrolling.
+DISPLAYABLE_CHARS is the number of characters in the line actually
+drawn.  This may be less than the number of characters in the line
+when line wrapping is off (see below).  The bitflag WRAPS tells
+whether the next line is a continuation of this line.  START and END
+are the marks at the beginning and end of the line.  Note that END is
+the actual last character, not one past it, so the smallest line
+(containing, for example, one newline) has START == END.  TAB_CONT and
+TAB_CONT_NEXT are for computation of tab positions.  I will discuss
+them later.
+
+A point about the end of the buffer.  You may be tempted to consider
+working with the buffer as an array of length TEXT_LENGTH(TEXT), but
+you have to be careful that the editor allows you to position your
+cursor at the last index of the buffer, one past the last character.
+The macro LAST_INDEX(TEXT, MARK) returns true if MARK is positioned at
+this index.  If you see or add a special case in the code for this
+end-of-buffer case, make sure to use LAST_INDEX if you can.  Very
+often, the last index is treated as a newline.
+
+Tab stops are variable width.  A list of tab stops is contained in the
+GtkText structure:
+
+  GList *tab_stops;
+  gint default_tab_width;
+
+The elements of tab_stops are integers casted to gpointer.  This is a
+little bogus, but works.  For example:
+
+  text->default_tab_width = 4;
+  text->tab_stops = NULL;
+  text->tab_stops = g_list_prepend (text->tab_stops, (void*)8);
+  text->tab_stops = g_list_prepend (text->tab_stops, (void*)8);
+
+is how these fields are initialized, currently.  This means that the
+first two tabs occur at 8 and 16, and every 4 characters thereafter.
+Tab stops are used in the computation of line geometry (to fill in a
+LineParams structure), and the width of the space character in the
+current font is used.  The PrevTabCont structure, of which two are
+stored per line, is used to compute the geometry of lines which may
+have wrapped and carried part of a tab with them:
+
+  guint pixel_offset;
+  TabStopMark tab_start;
+
+PIXEL_OFFSET is the number of pixels at which the line should start,
+and tab_start is a tab stop mark, which is similar to a property mark,
+only it keeps track of the mapping between line position (column) and
+the next tab stop.  A TabStopMark contains:
+
+  GList* tab_stops;
+  gint to_next_tab;
+
+TAB_STOPS is a pointer into the TAB_STOPS field of the GtkText
+structure.  TO_NEXT_TAB is the number of characters before the next
+tab.  The functions ADVANCE_TAB_MARK and ADVANCE_TAB_MARK_N advance
+these marks.  The LineParams structure contains two PrevTabCont
+structures, which each contain a tab stop.  The first (TAB_CONT) is
+for computing the beginning pixel offset, as mentioned above.  The
+second (TAB_CONT_NEXT) is used to initialize the TAB_CONT field of the
+next line if it wraps.
+
+Since computing the parameters of a line are fairly complicated, I
+have one interface that should be all you ever need to figure out
+something about a line.  The function FIND_LINE_PARAMS computes the
+parameters of a single line.  The function LINE_PARAMS_ITERATE is used
+for computing the properties of some number (> 0) of sequential lines.
+
+void
+line_params_iterate (GtkText* text,
+		     const GtkPropertyMark* mark0,
+		     const PrevTabCont* tab_mark0,
+		     gboolean alloc,
+		     gpointer data,
+		     LineIteratorFunction iter);
+
+where LineIteratorFunction is:
+
+typedef gint (*LineIteratorFunction) (GtkText* text,
+                                      LineParams* lp,
+                                      gpointer data);
+
+The arguments are a text widget (TEXT), the property mark at the
+beginning of the first line (MARK0), the tab stop mark at the
+beginning of that line (TAB_MARK0), whether to heap-allocate the
+LineParams structure (ALLOC), some client data (DATA), and a function
+to call with the parameters of each line.  TAB_MARK0 may be NULL, but
+if so MARK0 MUST BE A REAL LINE START (not a continued line start; it
+is preceded by a newline).  If TAB_MARK0 is not NULL, MARK0 may be any
+line start (continued or not).  See the code for examples.  The
+function ITER is called with each LineParams computed.  If ALLOC was
+true, LINE_PARAMS_ITERATE heap-allocates the LineParams and does not
+free them.  Otherwise, no storage is permanently allocated.  ITER
+should return TRUE when it wishes to continue no longer.
+
+There are currently two uses of LINE_PARAMS_ITERATE:
+
+* Compute the total buffer height for setting the parameters of the
+  scroll bars.  This is done in SET_VERTICAL_SCROLL each time the
+  window is resized.  When horizontal scrolling is added, depending on
+  the policy chosen, the max line width can be computed here as well.
+
+* Computing geometry of some pixel height worth of lines.  This is
+  done in FETCH_LINES, FETCH_LINES_BACKWARD, FETCH_LINES_FORWARD, etc.
+
+The GtkText structure contains a cache of the LineParams data for all
+visible lines:
+
+  GList *current_line;
+  GList *line_start_cache;
+
+  guint first_line_start_index;
+  guint first_cut_pixels;
+  guint first_onscreen_hor_pixel;
+  guint first_onscreen_ver_pixel;
+
+LINE_START_CACHE is a doubly linked list of LineParams.  CURRENT_LINE
+is a transient piece of data which is set in varoius places such as
+the mouse click code.  Generally, it is the line on which the cursor
+property mark CURSOR_MARK is on.  LINE_START_CACHE points to the first
+visible line and may contain PREV pointers if the cached data of
+offscreen lines is kept around.  I haven't come up with a policy.  The
+cache can keep more lines than are visible if desired, but the result
+is that inserts and deletes will then become slower as the entire
+cache has to be "corrected".  Right now it doesn't delete from the
+cache (it should).  As a result, scrolling through the whole buffer
+once will fill the cache with an entry for each line, and subsequent
+modifications will be slower than they should
+be. FIRST_LINE_START_INDEX is the index of the *REAL* line start of
+the first line.  That is, if the first visible line is a continued
+line, this is the index of the real line start (preceded by a
+newline).  FIRST_CUT_PIXELS is the number of pixels which are not
+drawn on the first visible line.  If FIRST_CUT_PIXELS is zero, the
+whole line is visible.  FIRST_ONSCREEN_HOR_PIXEL is not used.
+FIRST_ONSCREEN_VER_PIXEL is the absolute pixel which starts the
+visible region.  This is used for setting the vertical scroll bar.
+
+Other miscellaneous things in the GtkText structure:
+
+Gtk specific things:
+
+  GtkWidget widget;
+
+  GdkWindow *text_area;
+
+  GtkAdjustment *hadj;
+  GtkAdjustment *vadj;
+
+  GdkGC *gc;
+
+  GdkPixmap* line_wrap_bitmap;
+  GdkPixmap* line_arrow_bitmap;
+
+These are pretty self explanatory, especially if you know Gtk.
+LINE_WRAP_BITMAP and LINE_ARROW_BITMAP are two bitmaps used to
+indicate that a line wraps and is continued offscreen, respectively.
+
+Some flags:
+
+  guint has_cursor : 1;
+  guint is_editable : 1;
+  guint line_wrap : 1;
+  guint freeze : 1;
+  guint has_selection : 1;
+  guint own_selection : 1;
+
+HAS_CURSOR is true iff the cursor is visible.  IS_EDITABLE is true iff
+the user is allowed to modify the buffer.  If IS_EDITABLE is false,
+HAS_CURSOR is guaranteed to be false.  If IS_EDITABLE is true,
+HAS_CURSOR starts out false and is set to true the first time the user
+clicks in the window.  LINE_WRAP is where the line-wrap policy is
+set.  True means wrap lines, false means continue lines offscreen,
+horizontally.
+
+The text properties list:
+
+  GList *text_properties;
+  GList *text_properties_end;
+
+A scratch area used for constructing a contiguous piece of the buffer
+which may otherwise span the gap.  It is not strictly neccesary
+but simplifies the drawing code because it does not need to deal with
+the gap.
+
+  guchar* scratch_buffer;
+  guint   scratch_buffer_len;
+
+The last vertical scrollbar position.  Currently this looks the same
+as FIRST_ONSCREEN_VER_PIXEL.  I can't remember why I have two values.
+Perhaps someone should clean this up.
+
+  gint last_ver_value;
+
+The cursor:
+
+  gint            cursor_pos_x;
+  gint            cursor_pos_y;
+  GtkPropertyMark cursor_mark;
+  gchar           cursor_char;
+  gchar           cursor_char_offset;
+  gint            cursor_virtual_x;
+  gint            cursor_drawn_level;
+
+CURSOR_POS_X and CURSOR_POS_Y are the screen coordinates of the
+cursor.  CURSOR_MARK is the buffer position.  CURSOR_CHAR is
+TEXT_INDEX (TEXT, CURSOR_MARK.INDEX) if a drawable character, or 0 if
+it is whitespace, which is treated specially.  CURSOR_CHAR_OFFSET is
+the pixel offset above the base of the line at which it should be
+drawn.  Note that the base of the line is not the "baseline" in the
+traditional font metric sense.  A line (LineParams) is
+FONT_ASCENT+FONT_DESCENT high (use the macro LINE_HEIGHT).  The
+"baseline" is FONT_DESCENT below the base of the line.  I think this
+requires a drawing.
+
+0                      AAAAAAA
+1                      AAAAAAA
+2                     AAAAAAAAA
+3                     AAAAAAAAA
+4                    AAAAA AAAAA
+5                    AAAAA AAAAA
+6                   AAAAA   AAAAA
+7                  AAAAA     AAAAA
+8                  AAAAA     AAAAA
+9                 AAAAAAAAAAAAAAAAA
+10                AAAAAAAAAAAAAAAAA
+11               AAAAA         AAAAA
+12               AAAAA         AAAAA
+13              AAAAAA         AAAAAA
+14______________AAAAA___________AAAAA__________________________________
+15
+16
+17
+18
+19
+20
+
+This line is 20 pixels high, has FONT_ASCENT=14, FONT_DESCENT=6.  It's
+"base" is at y=20.  Characters are drawn at y=14.  The LINE_START
+macro returns the pixel height.  The LINE_CONTAINS macro is true if
+the line contains a certain buffer index.  The LINE_STARTS_AT macro is
+true if the line starts at a certain buffer index.  The
+LINE_START_PIXEL is the pixel offset the line should be drawn at,
+according the the tab continuation of the previous line.
+
+Exposure and drawing:
+
+Exposure is handled from the EXPOSE_TEXT function.  It assumes that
+the LINE_START_CACHE and all it's parameters are accurate and simply
+exposes any line which is in the exposure region.  It calls the
+CLEAR_AREA function to clear the background and/or lay down a pixmap
+background.  The text widget has a scrollable pixmap background, which
+is implemented in CLEAR_AREA.  CLEAR_AREA does the math to figure out
+how to tile the pixmap itself so that it can scroll the text with a
+copy area call.  If the CURSOR argument to EXPOSE_TEXT is true, it
+also draws the cursor.
+
+The function DRAW_LINE draws a single line, doing all the tab and
+color computations neccesary.  The function DRAW_LINE_WRAP draws the
+line wrap bitmap at the end of the line if it wraps.  TEXT_EXPOSE will
+expand the cached line data list if it has to by calling
+FETCH_LINES_FORWARD.  The functions DRAW_CURSOR and UNDRAW_CURSOR draw
+and undraw the cursor.  They count the number of draws and undraws so
+that the cursor may be undrawn even if the cursor is already undrawn
+and the re-draw will not occur too early.  This is useful in handling
+scrolling.
+
+Handling of the cursor is a little messed up, I should add.  It has to
+be undrawn and drawn at various places.  Something better needs to be
+done about this, because it currently doesn't do the right thing in
+certain places.  I can't remember where very well.  Look for the calls
+to DRAW_CURSOR and UNDRAW_CURSOR.
+
+RECOMPUTE_GEOMETRY is called when the geometry of the window changes
+or when it is first drawn.  This is probably not done right.  My
+biggest weakness in writing this code is that I've never written a
+widget before so I got most of the event handling stuff wrong as far
+as Gtk is concerned.  Fortunatly, most of the code is unrelated and
+simply an exercise in data structure manipulation.
+
+Scrolling:
+
+Scrolling is fairly straighforward.  It looks at the top line, and
+advances it pixel by pixel until the FIRST_CUT_PIXELS equals the line
+height and then advances the LINE_START_CACHE.  When it runs out of
+lines it fetches more.  The function SCROLL_INT is used to scroll from
+inside the code, it calls the appropriate functions and handles
+updating the scroll bars.  It dispatches a change event which causes
+Gtk to call the correct scroll action, which then enters SCROLL_UP or
+SCROLL_DOWN.  Careful with the cursor during these changes.
+
+Insertion, deletion:
+
+There's some confusion right now over what to do with the cursor when
+it's offscreen due to scrolling.  This is a policy decision.  I don't
+know what's best.  Spencer criticized me for forcing it to stay
+onscreen.  It shouldn't be hard to make stuff work with the cursor
+offscreen.
+
+Currently I've got functions to do insertion and deletion of a single
+character.  It's fairly complicated.  In order to do efficient pasting
+into the buffer, or write code that modifies the buffer while the
+buffer is drawn, it needs to do multiple characters at at time.  This
+is the hardest part of what remains.  Currently, gtk_text_insert does
+not reexpose the modified lines.  It needs to.  Pete did this wrong at
+one point and I disabled modification completely, I don't know what
+the current state of things are.  The functions
+INSERT_CHAR_LINE_EXPOSE and DELETE_CHAR_LINE_EXPOSE do the work.
+Here's pseudo code for insert.  Delete is quite similar.
+
+  insert character into the buffer
+  update the text property list
+  move the point
+  undraw the cursor
+  correct all LineParams cache entries after the insertion point
+  compute the new height of the modified line
+  compare with the old height of the modified line
+  remove the old LineParams from the cache
+  insert the new LineParams into the cache
+  if the lines are of different height, do a copy area to move the
+    area below the insertion down
+  expose the current line
+  update the cursor mark
+  redraw the cursor
+
+What needs to be done:
+
+Horizintal scrolling, robustness, testing, selection handling.  If you
+want to work in the text widget pay attention to the debugging
+facilities I've written at the end of gtktext.c.  I'm sorry I waited
+so long to try and pass this off.  I'm super busy with school and
+work, and when I have free time my highest priority is another version
+of PRCS.
+
+Feel free to ask me questions.