Pileus Git - ~andy/gtk/blob - docs/text_widget_internals.txt

   1 This file documents how GtkTextView works, at least partially.  You
   2 probably want to read the text widget overview in the reference manual
   3 to get an application programmer overview of the public API before
   4 reading this. The overview in the reference manual documents
   5 GtkTextBuffer, GtkTextView, GtkTextMark, etc. from a public API
   6 standpoint.
   7
   8 The BTree
   9 ===
  10
  11 The heart of the text widget is a data structure called GtkTextBTree,
  12 which implements all the hard work of the public GtkTextBuffer object.
  13 The purpose of the btree is to make most operations at least O(log N),
  14 so application programmers can just use whatever API is convenient
  15 without worrying about O(N) performance pitfalls.
  16
  17 The BTree is a tree of paragraphs (newline-terminated lines).  The
  18 leaves of the tree are paragraphs, represented by a GtkTextLine. The
  19 nodes of the tree above the leaves are represented by
  20 GtkTextBTreeNode. The nodes are used to store aggregate data counts,
  21 so we can for example skip 100 paragraphs or 100 characters, without
  22 having to traverse 100 nodes in a list.
  23
  24 You might guess from this that many operations are O(N) where N is the
  25 number of bytes in a paragraph, and you would be right. The text
  26 widget is efficient for huge numbers of paragraphs, but will choke on
  27 extremely long blocks of text without intervening newlines.
  28
  29 ("newline" is a slight lie, we also honor \r, \r\n, and some funky
  30 Unicode characters for paragraph breaks. So this means annoyingly that
  31 the paragraph break char may be more than one byte.)
  32
  33 The idea of the btree is something like:
  34
  35
  36                ------ Node (lines = 6)
  37               /          Line 0
  38              /           Line 1
  39             /            Line 2
  40            /             Line 3
  41           /              Line 4
  42          /               Line 5
  43  Node (lines = 12)
  44          \
  45           \---------- Node (lines = 6)
  46                          Line 6
  47                          Line 7
  48                          Line 8
  49                          Line 9
  50                          Line 10
  51                          Line 11
  52
  53
  54 In addition to keeping aggregate line counts at each node, we count
  55 characters, and information about the tag toggles appearing below each
  56 node.
  57
  58 Structure of a GtkTextLine
  59 ===
  60
  61 A GtkTextLine contains a single paragraph of text. It should probably
  62 be renamed GtkTextPara someday but ah well.  GtkTextLine is used for
  63 the leaf nodes of the BTree.
  64
  65 A line is a list of GtkTextLineSegment. Line segments contain the
  66 actual data found in the text buffer.
  67
  68 Here are the types of line segment (see gtktextsegment.h,
  69 gtktextchild.h, etc.):
  70
  71   Character:         contains a block of UTF-8 text.
  72
  73   Mark:              marks a position in the buffer, such as a cursor.
  74
  75   Tag toggle:        indicates that a tag is toggled on or toggled off at
  76                      this point. when you apply a tag to a range of
  77                      text, we add a toggle on at the start of the
  78                      range, and a toggle off at the end.  (and do any
  79                      necessary merging with existing toggles, so we
  80                      always have the minimum number possible)
  81
  82   Child widget:      stores a child widget that behaves as a single
  83                      Unicode character from an editing perspective.
  84                      (well, stores a list of child widgets, one per
  85                      GtkTextView displaying the buffer)
  86
  87   Image:             stores a GdkPixbuf that behaves as a single
  88                      character from an editing perspective.
  89
  90
  91 Each line segment has a "class" which identifies its type, and also
  92 provides some virtual functions for handling that segment.
  93 The functions in the class are:
  94
  95  - SplitFunc, divides the segment so another segment can be inserted.
  96
  97  - DeleteFunc, finalizes the segment
  98
  99  - CleanupFunc, after modifying a line by adding/removing segments,
 100    this function is used to try merging segments that can be merged,
 101    e.g. two adjacent character segments with no marks or toggles
 102    in between.
 103
 104  - LineChangeFunc, called when a segment moves to a different line;
 105    according to comments in the code this function may not be needed
 106    anymore.
 107
 108  - SegCheckFunc, does sanity-checking when debugging is enabled.
 109    Basically equivalent to assert(segment is not broken).
 110
 111 The segment class also contains two data fields:
 112
 113  - the name of the segment type, used for debugging
 114
 115  - a boolean flag for whether the segment has right or left
 116    gravity. A segment with right gravity ends up on the right of a
 117    newly-inserted segment that's placed at the same character offset,
 118    and a segment with left gravity ends up on the left of a
 119    newly-inserted segment. For example the insertion cursor
 120    has right gravity, because as you type new text is inserted,
 121    and the cursor ends up on the right.
 122
 123 The segment itself contains contains a header, plus some
 124 variable-length data that depends on the type of the segment.
 125 The header contains the length of the segment in characters and in
 126 bytes. Some segments have a length of zero. Segments with nonzero
 127 length are referred to as "indexable" and would generally be
 128 user-visible; indexable segments include text, images, and widgets.
 129 Segments with zero length occupy positions between characters, and
 130 include marks and tag toggles.
 131
 132 The GtkText*Body structs are the type-specific portions of
 133 GtkTextSegment.
 134
 135 Character segments have the actual character data allocated in the
 136 same malloc() block as the GtkTextSegment, to save both malloc()
 137 overhead and the overhead of a pointer to the character data.
 138
 139 Storing and tracking tags in the BTree
 140 ===
 141
 142 A GtkTextTag is an object representing some text attributes.  A tag
 143 can affect zero attributes (for example one used only for internal
 144 application bookkeeping), a single attribute such as "bold", or any
 145 number of attributes (such as large and bold and centered for a
 146 "header" tag).
 147
 148 The tags that can be applied to a given buffer are stored in the
 149 GtkTextTagTable for that buffer. The tag table is just a collection of
 150 tags.
 151
 152 The real work of applying/removing tags happens in the function
 153 _gtk_text_btree_tag(). Essentially we remove all tag toggle segments
 154 that affect the tag being applied or removed from the given range;
 155 then we add a toggle-on and a toggle-off segment at either end of the
 156 range; then for any lines we modified, we call the CleanupFunc
 157 routines for the segments, to merge segments that can be merged.
 158
 159 This is complicated somewhat because we keep information about the tag
 160 toggles in the btree, allowing us to locate tagged regions or
 161 add/remove tags in O(log N) instead of O(N) time. Tag information is
 162 stored in "struct Summary" (that's a bad name, it could probably use
 163 renaming). Each BTreeNode has a list of Summary hanging off of it, one
 164 for each tag that's toggled somewhere below the node. The Summary
 165 simply contains a count of tag toggle segments found below the node.
 166
 167
 168 Views of the BTree (GtkTextLayout)
 169 ===
 170
 171 Each BTree has one or more views that display the tree.  Originally
 172 there was some idea that a view could be any object, so there are some
 173 "gpointer view_id" left in the code. However, at some point we decided
 174 that all views had to be a GtkTextLayout and so the btree does assume
 175 that from time to time.
 176
 177 The BTree maintains some per-line and per-node data that is specific
 178 to each view. The per-line data is in GtkTextLineData and the per-node
 179 data is in another badly-named struct called NodeData (should be
 180 PerViewNodeData or something). The purpose of these is to store:
 181
 182  - aggregate height, so we can calculate the Y position of each
 183    paragraph in O(log N) time, and can get the full height
 184    of the buffer in O(1) time. The height is per-view since
 185    each GtkTextView may have a different size allocation.
 186
 187  - maximum width (the longest line), so we can calculate the width of
 188    the entire buffer in O(1) time in order to properly set up the
 189    horizontal scrollbar.
 190
 191  - a flag for whether the line is "valid" - valid lines have not been
 192    modified since we last computed their width and height. Invalid
 193    lines need to have their width and height recomputed.
 194
 195 At all times, we have a width and height for each view that can be
 196 used. This starts out as 0x0. Lines can be incrementally revalidated,
 197 which causes the width and height of the buffer to grow. So if you
 198 open a new text widget with a lot of text in it, you can watch the
 199 scrollbar adjust as the height is computed in an idle handler.  Lines
 200 whose height has never been computed are taken to have a height of 0.
 201
 202 Iterators (GtkTextIter)
 203 ===
 204
 205 Iterators are fairly complex in order to avoid re-traversing the btree
 206 or a line in the btree each time the iterator is used. That is, they
 207 save a bunch of pointers - to the current segment, the current line,
 208 etc.
 209
 210 Two "validity stamps" are kept in the btree that are used to detect
 211 and handle possibly-invalid pointers in iterators. The
 212 "chars_changed_stamp" is incremented whenever a segment with
 213 char_count > 0 (an indexable segment) is added or removed. It is an
 214 application bug if the application uses an iterator with a
 215 chars_changed_stamp different from the current stamp of the BTree.
 216 That is, you can't use an iterator after adding/removing characters.
 217
 218 The "segments_changed_stamp" is incremented any time we change any
 219 segments, and tells outstanding iterators that any pointers to
 220 GtkTextSegment that they may be holding are now invalid. For example,
 221 if you are iterating over a character segment, and insert a mark in
 222 the middle of the segment, the character segment will be split in half
 223 and the original segment will be freed. This increments
 224 segments_changed_stamp, causing your iterator to drop its current
 225 segment pointer and count from the beginning of the line again to find
 226 the new segment.
 227
 228 Iterators also cache some random information such as the current line
 229 number, just because it's free to do so.
 230
 231 GtkTextLayout
 232 ===
 233
 234 If you think of GtkTextBTree as the backend for GtkTextBuffer,
 235 GtkTextLayout is the backend for GtkTextView. GtkTextLayout was also
 236 used for a canvas item at one point, which is why its methods are not
 237 underscore-prefixed and the header gets installed. But GtkTextLayout
 238 is really intended to be private.
 239
 240 The main task of GtkTextLayout is to validate lines (compute their
 241 width and height) by converting the lines to a PangoLayout and using
 242 Pango functions. GtkTextLayout is also used for visual iteration, and
 243 mapping visual locations to logical buffer positions.
 244
 245 Validating a line involves creating the GtkTextLineDisplay for that
 246 line. To save memory, GtkTextLineDisplay objects are always created
 247 transiently, we don't keep them around.
 248
 249 The layout has three signals:
 250
 251  - "invalidated" means some line was changed, so GtkTextView
 252    needs to install idle handlers to revalidate.
 253
 254  - "changed" means some lines were validated, so the aggregate
 255    width/height of the BTree is now different.
 256
 257  - "allocate_child" means we need to size allocate a
 258    child widget
 259
 260 gtk_text_layout_get_line_display() is sort of the "heart" of
 261 GtkTextLayout. This function validates a line.
 262
 263 Line validation involves:
 264
 265  - convert any GtkTextTag on the line to PangoAttrList
 266
 267  - add the preedit string
 268
 269  - keep track of "visible marks" (the cursor)
 270
 271 A given set of tags is composited to a GtkTextAttributes. (In the Tk
 272 code this was called a "style" and there are still relics of this in
 273 the code, such as "invalidate_cached_style()", that should be cleaned
 274 up.)
 275
 276 There's a single-GtkTextAttributes cache, "layout->one_style_cache",
 277 which is used to avoid recomputing the mapping from tags to attributes
 278 for every segment. The one_style_cache is stored in the GtkTextLayout
 279 instead of just a local variable in gtk_text_layout_get_line_display()
 280 so we can use it across multiple lines. Any time we see a segment that
 281 may change the current style (such as a tag toggle), the cache has to
 282 be dropped.
 283
 284 To compute a GtkTextAttributes from the GtkTextTag that apply to a
 285 given segment, the function is _gtk_text_attributes_fill_from_tags().
 286 This "mashes" a list of tags into a single set of text attributes.
 287 If no tags affect a given attribute, a default set of attributes are
 288 used. These defaults sometimes come from widget->style on the
 289 GtkTextView, and sometimes come from a property of the GtkTextView
 290 such as "pixels_above_lines"
 291
 292 GtkTextView
 293 ===
 294
 295 Once you get GtkTextLayout and GtkTextBTree the actual GtkTextView
 296 widget is not that complicated.
 297
 298 The main complexity is the interaction between scrolling and line
 299 validation, which is documented with a long comment in gtktextview.c.
 300
 301 The other thing to know about is just that the text view has "border
 302 windows" on the sides, used to draw line numbers and such; these
 303 scroll along with the main window.
 304
 305 Invisible text
 306 ===
 307
 308 Invisible text doesn't work yet. It is a property that can be set by a
 309 GtkTextTag; so you determine whether text is invisible using the same
 310 mechanism you would use to check whether the text is bold, or orange.
 311
 312 The intended behavior of invisible text is that it should vanish
 313 completely, as if it did not exist. The use-case we were thinking of
 314 was a code editor with function folding, where you can hide all
 315 function bodies. That could be implemented by creating a
 316 "function_body" GtkTextTag and toggling its "invisible" attribute to
 317 hide/show the function bodies.
 318
 319 Lines are normally validated in an idle handler, but as an exception,
 320 lines that are onscreen are always validated synchronously. Thus
 321 invisible text raises the danger that we might have a huge number of
 322 invisible lines "onscreen" - this needs to be handled efficiently.
 323
 324 At one point we were considering making "invisible" a per-paragraph
 325 attribute (meaning the invisibility state of the first character in
 326 the paragraph makes the whole paragraph visible or not
 327 visible). Several existing tag attributes work this way, such as the
 328 margin width. I don't remember why we were going to do this, but it
 329 may have been due to some implementation difficulty that will become
 330 clear if you try implementing invisible text. ;-)
 331
 332 To finish invisible text support, all the cursor navigation
 333 etc. functions (the _display_lines() stuff) will need to skip
 334 invisible text. Also, various functions with _visible in the name,
 335 such as gtk_text_iter_get_visible_text(), have to be audited to be
 336 sure they don't get invisible text. And user operations such as
 337 cut-and-paste need to copy only visible text.
 338