Pileus Git - ~andy/gtk/blob - gtk/gtktextbtree.c

   1 /*
   2  * Gtktextbtree.c --
   3  *
   4  *      This file contains code that manages the B-tree representation
   5  *      of text for the text buffer and implements character and
   6  *      toggle segment types.
   7  *
   8  * Copyright (c) 1992-1994 The Regents of the University of California.
   9  * Copyright (c) 1994-1995 Sun Microsystems, Inc.
  10  * Copyright (c) 2000      Red Hat, Inc.
  11  * Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
  12  *
  13  * This software is copyrighted by the Regents of the University of
  14  * California, Sun Microsystems, Inc., and other parties.  The
  15  * following terms apply to all files associated with the software
  16  * unless explicitly disclaimed in individual files.
  17  *
  18  * The authors hereby grant permission to use, copy, modify,
  19  * distribute, and license this software and its documentation for any
  20  * purpose, provided that existing copyright notices are retained in
  21  * all copies and that this notice is included verbatim in any
  22  * distributions. No written agreement, license, or royalty fee is
  23  * required for any of the authorized uses.  Modifications to this
  24  * software may be copyrighted by their authors and need not follow
  25  * the licensing terms described here, provided that the new terms are
  26  * clearly indicated on the first page of each file where they apply.
  27  *
  28  * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
  29  * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
  30  * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
  31  * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
  32  * OF THE POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
  35  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
  37  * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
  38  * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
  39  * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  40  *
  41  * GOVERNMENT USE: If you are acquiring this software on behalf of the
  42  * U.S. government, the Government shall have only "Restricted Rights"
  43  * in the software and related documentation as defined in the Federal
  44  * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
  45  * are acquiring the software on behalf of the Department of Defense,
  46  * the software shall be classified as "Commercial Computer Software"
  47  * and the Government shall have only "Restricted Rights" as defined
  48  * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
  49  * foregoing, the authors grant the U.S. Government and others acting
  50  * in its behalf permission to use and distribute the software in
  51  * accordance with the terms specified in this license.
  52  *
  53  */
  54
  55 #define GTK_TEXT_USE_INTERNAL_UNSUPPORTED_API
  56 #include <config.h>
  57 #include "gtktextbtree.h"
  58 #include <string.h>
  59 #include <stdlib.h>
  60 #include <stdio.h>
  61 #include "gtktexttag.h"
  62 #include "gtktexttagtable.h"
  63 #include "gtktextlayout.h"
  64 #include "gtktextiterprivate.h"
  65 #include "gtkdebug.h"
  66 #include "gtktextmarkprivate.h"
  67 #include "gtkalias.h"
  68
  69 /*
  70  * Types
  71  */
  72
  73
  74 /*
  75  * The structure below is used to pass information between
  76  * _gtk_text_btree_get_tags and inc_count:
  77  */
  78
  79 typedef struct TagInfo {
  80   int numTags;                  /* Number of tags for which there
  81                                  * is currently information in
  82                                  * tags and counts. */
  83   int arraySize;                        /* Number of entries allocated for
  84                                          * tags and counts. */
  85   GtkTextTag **tags;           /* Array of tags seen so far.
  86                                 * Malloc-ed. */
  87   int *counts;                  /* Toggle count (so far) for each
  88                                  * entry in tags.  Malloc-ed. */
  89 } TagInfo;
  90
  91
  92 /*
  93  * This is used to store per-view width/height info at the tree nodes.
  94  */
  95
  96 typedef struct _NodeData NodeData;
  97
  98 struct _NodeData {
  99   gpointer view_id;
 100   NodeData *next;
 101
 102   /* Height and width of this node */
 103   gint height;
 104   signed int width : 24;
 105
 106   /* boolean indicating whether the lines below this node are in need of validation.
 107    * However, width/height should always represent the current total width and
 108    * max height for lines below this node; the valid flag indicates whether the
 109    * width/height on the lines needs recomputing, not whether the totals
 110    * need recomputing.
 111    */
 112   guint valid : 8;              /* Actually a boolean */
 113 };
 114
 115
 116 /*
 117  * The data structure below keeps summary information about one tag as part
 118  * of the tag information in a node.
 119  */
 120
 121 typedef struct Summary {
 122   GtkTextTagInfo *info;                     /* Handle for tag. */
 123   int toggle_count;                     /* Number of transitions into or
 124                                          * out of this tag that occur in
 125                                          * the subtree rooted at this node. */
 126   struct Summary *next;         /* Next in list of all tags for same
 127                                  * node, or NULL if at end of list. */
 128 } Summary;
 129
 130 /*
 131  * The data structure below defines a node in the B-tree.
 132  */
 133
 134 struct _GtkTextBTreeNode {
 135   GtkTextBTreeNode *parent;         /* Pointer to parent node, or NULL if
 136                                      * this is the root. */
 137   GtkTextBTreeNode *next;           /* Next in list of siblings with the
 138                                      * same parent node, or NULL for end
 139                                      * of list. */
 140   Summary *summary;             /* First in malloc-ed list of info
 141                                  * about tags in this subtree (NULL if
 142                                  * no tag info in the subtree). */
 143   int level;                            /* Level of this node in the B-tree.
 144                                          * 0 refers to the bottom of the tree
 145                                          * (children are lines, not nodes). */
 146   union {                               /* First in linked list of children. */
 147     struct _GtkTextBTreeNode *node;         /* Used if level > 0. */
 148     GtkTextLine *line;         /* Used if level == 0. */
 149   } children;
 150   int num_children;                     /* Number of children of this node. */
 151   int num_lines;                        /* Total number of lines (leaves) in
 152                                          * the subtree rooted here. */
 153   int num_chars;                        /* Number of chars below here */
 154
 155   NodeData *node_data;
 156 };
 157
 158
 159 /*
 160  * Used to store the list of views in our btree
 161  */
 162
 163 typedef struct _BTreeView BTreeView;
 164
 165 struct _BTreeView {
 166   gpointer view_id;
 167   GtkTextLayout *layout;
 168   BTreeView *next;
 169   BTreeView *prev;
 170 };
 171
 172 /*
 173  * And the tree itself
 174  */
 175
 176 struct _GtkTextBTree {
 177   GtkTextBTreeNode *root_node;          /* Pointer to root of B-tree. */
 178   GtkTextTagTable *table;
 179   GHashTable *mark_table;
 180   guint refcount;
 181   GtkTextMark *insert_mark;
 182   GtkTextMark *selection_bound_mark;
 183   GtkTextBuffer *buffer;
 184   BTreeView *views;
 185   GSList *tag_infos;
 186   gulong tag_changed_handler;
 187
 188   /* Incremented when a segment with a byte size > 0
 189    * is added to or removed from the tree (i.e. the
 190    * length of a line may have changed, and lines may
 191    * have been added or removed). This invalidates
 192    * all outstanding iterators.
 193    */
 194   guint chars_changed_stamp;
 195   /* Incremented when any segments are added or deleted;
 196    * this makes outstanding iterators recalculate their
 197    * pointed-to segment and segment offset.
 198    */
 199   guint segments_changed_stamp;
 200
 201   /* Cache the last line in the buffer */
 202   GtkTextLine *last_line;
 203   guint last_line_stamp;
 204
 205   /* Cache the next-to-last line in the buffer,
 206    * containing the end iterator
 207    */
 208   GtkTextLine *end_iter_line;
 209   GtkTextLineSegment *end_iter_segment;
 210   int end_iter_segment_byte_index;
 211   int end_iter_segment_char_offset;
 212   guint end_iter_line_stamp;
 213   guint end_iter_segment_stamp;
 214
 215   GHashTable *child_anchor_table;
 216 };
 217
 218
 219 /*
 220  * Upper and lower bounds on how many children a node may have:
 221  * rebalance when either of these limits is exceeded.  MAX_CHILDREN
 222  * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
 223  */
 224
 225 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
 226    shallow. It appears to be faster to locate a particular line number
 227    if the tree is narrow and deep, since it is more finely sorted.  I
 228    guess this may increase memory use though, and make it slower to
 229    walk the tree in order, or locate a particular byte index (which
 230    is done by walking the tree in order).
 231
 232    There's basically a tradeoff here. However I'm thinking we want to
 233    add pixels, byte counts, and char counts to the tree nodes,
 234    at that point narrow and deep should speed up all operations,
 235    not just the line number searches.
 236 */
 237
 238 #if 1
 239 #define MAX_CHILDREN 12
 240 #define MIN_CHILDREN 6
 241 #else
 242 #define MAX_CHILDREN 6
 243 #define MIN_CHILDREN 3
 244 #endif
 245
 246 /*
 247  * Prototypes
 248  */
 249
 250 static BTreeView        *gtk_text_btree_get_view                 (GtkTextBTree     *tree,
 251                                                                   gpointer          view_id);
 252 static void              gtk_text_btree_rebalance                (GtkTextBTree     *tree,
 253                                                                   GtkTextBTreeNode *node);
 254 static GtkTextLine     * get_last_line                           (GtkTextBTree     *tree);
 255 static void              post_insert_fixup                       (GtkTextBTree     *tree,
 256                                                                   GtkTextLine      *insert_line,
 257                                                                   gint              char_count_delta,
 258                                                                   gint              line_count_delta);
 259 static void              gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
 260                                                                   GtkTextTagInfo   *info,
 261                                                                   gint              adjust);
 262 static gboolean          gtk_text_btree_node_has_tag             (GtkTextBTreeNode *node,
 263                                                                   GtkTextTag       *tag);
 264
 265 static void             segments_changed                (GtkTextBTree     *tree);
 266 static void             chars_changed                   (GtkTextBTree     *tree);
 267 static void             summary_list_destroy            (Summary          *summary);
 268 static GtkTextLine     *gtk_text_line_new               (void);
 269 static void             gtk_text_line_destroy           (GtkTextBTree     *tree,
 270                                                          GtkTextLine      *line);
 271 static void             gtk_text_line_set_parent        (GtkTextLine      *line,
 272                                                          GtkTextBTreeNode *node);
 273 static void             gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
 274                                                          gpointer          view_id);
 275
 276
 277 static NodeData         *node_data_new          (gpointer  view_id);
 278 static void              node_data_destroy      (NodeData *nd);
 279 static void              node_data_list_destroy (NodeData *nd);
 280 static NodeData         *node_data_find         (NodeData *nd,
 281                                                  gpointer  view_id);
 282
 283 static GtkTextBTreeNode     *gtk_text_btree_node_new                  (void);
 284 static void                  gtk_text_btree_node_invalidate_downward  (GtkTextBTreeNode *node);
 285 static void                  gtk_text_btree_node_invalidate_upward    (GtkTextBTreeNode *node,
 286                                                                        gpointer          view_id);
 287 static NodeData *            gtk_text_btree_node_check_valid          (GtkTextBTreeNode *node,
 288                                                                        gpointer          view_id);
 289 static NodeData *            gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
 290                                                                        gpointer          view_id);
 291 static void                  gtk_text_btree_node_check_valid_upward   (GtkTextBTreeNode *node,
 292                                                                        gpointer          view_id);
 293
 294 static void                  gtk_text_btree_node_remove_view         (BTreeView        *view,
 295                                                                       GtkTextBTreeNode *node,
 296                                                                       gpointer          view_id);
 297 static void                  gtk_text_btree_node_destroy             (GtkTextBTree     *tree,
 298                                                                       GtkTextBTreeNode *node);
 299 static void                  gtk_text_btree_node_free_empty          (GtkTextBTree *tree,
 300                                                                       GtkTextBTreeNode *node);
 301 static NodeData         *    gtk_text_btree_node_ensure_data         (GtkTextBTreeNode *node,
 302                                                                       gpointer          view_id);
 303 static void                  gtk_text_btree_node_remove_data         (GtkTextBTreeNode *node,
 304                                                                       gpointer          view_id);
 305 static void                  gtk_text_btree_node_get_size            (GtkTextBTreeNode *node,
 306                                                                       gpointer          view_id,
 307                                                                       gint             *width,
 308                                                                       gint             *height);
 309 static GtkTextBTreeNode *    gtk_text_btree_node_common_parent       (GtkTextBTreeNode *node1,
 310                                                                       GtkTextBTreeNode *node2);
 311 static void get_tree_bounds       (GtkTextBTree     *tree,
 312                                    GtkTextIter      *start,
 313                                    GtkTextIter      *end);
 314 static void tag_changed_cb        (GtkTextTagTable  *table,
 315                                    GtkTextTag       *tag,
 316                                    gboolean          size_changed,
 317                                    GtkTextBTree     *tree);
 318 static void cleanup_line          (GtkTextLine      *line);
 319 static void recompute_node_counts (GtkTextBTree     *tree,
 320                                    GtkTextBTreeNode *node);
 321 static void inc_count             (GtkTextTag       *tag,
 322                                    int               inc,
 323                                    TagInfo          *tagInfoPtr);
 324
 325 static void summary_destroy       (Summary          *summary);
 326
 327 static void gtk_text_btree_link_segment   (GtkTextLineSegment *seg,
 328                                            const GtkTextIter  *iter);
 329 static void gtk_text_btree_unlink_segment (GtkTextBTree       *tree,
 330                                            GtkTextLineSegment *seg,
 331                                            GtkTextLine        *line);
 332
 333
 334 static GtkTextTagInfo *gtk_text_btree_get_tag_info          (GtkTextBTree   *tree,
 335                                                              GtkTextTag     *tag);
 336 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree   *tree,
 337                                                              GtkTextTag     *tag);
 338 static void            gtk_text_btree_remove_tag_info       (GtkTextBTree   *tree,
 339                                                              GtkTextTag     *tag);
 340
 341 static void redisplay_region (GtkTextBTree      *tree,
 342                               const GtkTextIter *start,
 343                               const GtkTextIter *end);
 344
 345 /* Inline thingies */
 346
 347 static inline void
 348 segments_changed (GtkTextBTree *tree)
 349 {
 350   tree->segments_changed_stamp += 1;
 351 }
 352
 353 static inline void
 354 chars_changed (GtkTextBTree *tree)
 355 {
 356   tree->chars_changed_stamp += 1;
 357 }
 358
 359 /*
 360  * BTree operations
 361  */
 362
 363 GtkTextBTree*
 364 _gtk_text_btree_new (GtkTextTagTable *table,
 365                      GtkTextBuffer *buffer)
 366 {
 367   GtkTextBTree *tree;
 368   GtkTextBTreeNode *root_node;
 369   GtkTextLine *line, *line2;
 370
 371   g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
 372   g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
 373
 374   /*
 375    * The tree will initially have two empty lines.  The second line
 376    * isn't actually part of the tree's contents, but its presence
 377    * makes several operations easier.  The tree will have one GtkTextBTreeNode,
 378    * which is also the root of the tree.
 379    */
 380
 381   /* Create the root node. */
 382
 383   root_node = gtk_text_btree_node_new ();
 384
 385   line = gtk_text_line_new ();
 386   line2 = gtk_text_line_new ();
 387
 388   root_node->parent = NULL;
 389   root_node->next = NULL;
 390   root_node->summary = NULL;
 391   root_node->level = 0;
 392   root_node->children.line = line;
 393   root_node->num_children = 2;
 394   root_node->num_lines = 2;
 395   root_node->num_chars = 2;
 396
 397   line->parent = root_node;
 398   line->next = line2;
 399
 400   line->segments = _gtk_char_segment_new ("\n", 1);
 401
 402   line2->parent = root_node;
 403   line2->next = NULL;
 404   line2->segments = _gtk_char_segment_new ("\n", 1);
 405
 406   /* Create the tree itself */
 407
 408   tree = g_new0(GtkTextBTree, 1);
 409   tree->root_node = root_node;
 410   tree->table = table;
 411   tree->views = NULL;
 412
 413   /* Set these to values that are unlikely to be found
 414    * in random memory garbage, and also avoid
 415    * duplicates between tree instances.
 416    */
 417   tree->chars_changed_stamp = g_random_int ();
 418   tree->segments_changed_stamp = g_random_int ();
 419
 420   tree->last_line_stamp = tree->chars_changed_stamp - 1;
 421   tree->last_line = NULL;
 422
 423   tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
 424   tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
 425   tree->end_iter_line = NULL;
 426   tree->end_iter_segment_byte_index = 0;
 427   tree->end_iter_segment_char_offset = 0;
 428
 429   g_object_ref (tree->table);
 430
 431   tree->tag_changed_handler = g_signal_connect (tree->table,
 432                                                 "tag_changed",
 433                                                 G_CALLBACK (tag_changed_cb),
 434                                                 tree);
 435
 436   tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
 437   tree->child_anchor_table = NULL;
 438
 439   /* We don't ref the buffer, since the buffer owns us;
 440    * we'd have some circularity issues. The buffer always
 441    * lasts longer than the BTree
 442    */
 443   tree->buffer = buffer;
 444
 445   {
 446     GtkTextIter start;
 447     GtkTextLineSegment *seg;
 448
 449     _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
 450
 451
 452     tree->insert_mark = _gtk_text_btree_set_mark (tree,
 453                                                  NULL,
 454                                                  "insert",
 455                                                  FALSE,
 456                                                  &start,
 457                                                  FALSE);
 458
 459     seg = tree->insert_mark->segment;
 460
 461     seg->body.mark.not_deleteable = TRUE;
 462     seg->body.mark.visible = TRUE;
 463
 464     tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
 465                                                           NULL,
 466                                                           "selection_bound",
 467                                                           FALSE,
 468                                                           &start,
 469                                                           FALSE);
 470
 471     seg = tree->selection_bound_mark->segment;
 472
 473     seg->body.mark.not_deleteable = TRUE;
 474
 475     g_object_ref (tree->insert_mark);
 476     g_object_ref (tree->selection_bound_mark);
 477   }
 478
 479   tree->refcount = 1;
 480
 481   return tree;
 482 }
 483
 484 void
 485 _gtk_text_btree_ref (GtkTextBTree *tree)
 486 {
 487   g_return_if_fail (tree != NULL);
 488   g_return_if_fail (tree->refcount > 0);
 489
 490   tree->refcount += 1;
 491 }
 492
 493 void
 494 _gtk_text_btree_unref (GtkTextBTree *tree)
 495 {
 496   g_return_if_fail (tree != NULL);
 497   g_return_if_fail (tree->refcount > 0);
 498
 499   tree->refcount -= 1;
 500
 501   if (tree->refcount == 0)
 502     {
 503       g_signal_handler_disconnect (tree->table,
 504                                    tree->tag_changed_handler);
 505
 506       g_object_unref (tree->table);
 507       tree->table = NULL;
 508
 509       gtk_text_btree_node_destroy (tree, tree->root_node);
 510       tree->root_node = NULL;
 511
 512       g_assert (g_hash_table_size (tree->mark_table) == 0);
 513       g_hash_table_destroy (tree->mark_table);
 514       tree->mark_table = NULL;
 515       if (tree->child_anchor_table != NULL)
 516         {
 517           g_hash_table_destroy (tree->child_anchor_table);
 518           tree->child_anchor_table = NULL;
 519         }
 520
 521       g_object_unref (tree->insert_mark);
 522       tree->insert_mark = NULL;
 523       g_object_unref (tree->selection_bound_mark);
 524       tree->selection_bound_mark = NULL;
 525
 526       g_free (tree);
 527     }
 528 }
 529
 530 GtkTextBuffer*
 531 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
 532 {
 533   return tree->buffer;
 534 }
 535
 536 guint
 537 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
 538 {
 539   return tree->chars_changed_stamp;
 540 }
 541
 542 guint
 543 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
 544 {
 545   return tree->segments_changed_stamp;
 546 }
 547
 548 void
 549 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
 550 {
 551   g_return_if_fail (tree != NULL);
 552   segments_changed (tree);
 553 }
 554
 555 /*
 556  * Indexable segment mutation
 557  */
 558
 559 /*
 560  *  The following function is responsible for resolving the bidi direction
 561  *  for the lines between start and end. But it also calculates any
 562  *  dependent bidi direction for surrounding lines that change as a result
 563  *  of the bidi direction decisions within the range. The function is
 564  *  trying to do as little propagation as is needed.
 565  */
 566 static void
 567 gtk_text_btree_resolve_bidi (GtkTextIter *start,
 568                              GtkTextIter *end)
 569 {
 570   GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
 571   GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
 572   PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
 573
 574   /* Resolve the strong bidi direction for all lines between
 575    * start and end.
 576   */
 577   start_line = _gtk_text_iter_get_text_line (start);
 578   start_line_prev = _gtk_text_line_previous (start_line);
 579   end_line = _gtk_text_iter_get_text_line (end);
 580   end_line_next = _gtk_text_line_next (end_line);
 581
 582   line = start_line;
 583   while (line && line != end_line_next)
 584     {
 585       /* Loop through the segments and search for a strong character
 586        */
 587       GtkTextLineSegment *seg = line->segments;
 588       line->dir_strong = PANGO_DIRECTION_NEUTRAL;
 589
 590       while (seg)
 591         {
 592           if (seg->type == &gtk_text_char_type && seg->byte_count > 0)
 593             {
 594               PangoDirection pango_dir;
 595
 596               pango_dir = pango_find_base_dir (seg->body.chars,
 597                                                seg->byte_count);
 598
 599               if (pango_dir != PANGO_DIRECTION_NEUTRAL)
 600                 {
 601                   line->dir_strong = pango_dir;
 602                   break;
 603                 }
 604             }
 605           seg = seg->next;
 606         }
 607
 608       line = _gtk_text_line_next (line);
 609     }
 610
 611   /* Sweep forward */
 612
 613   /* The variable dir_above_propagated contains the forward propagated
 614    * direction before start. It is neutral if start is in the beginning
 615    * of the buffer.
 616    */
 617   dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
 618   if (start_line_prev)
 619     dir_above_propagated = start_line_prev->dir_propagated_forward;
 620
 621   /* Loop forward and propagate the direction of each paragraph
 622    * to all neutral lines.
 623    */
 624   line = start_line;
 625   last_strong = dir_above_propagated;
 626   while (line != end_line_next)
 627     {
 628       if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
 629         last_strong = line->dir_strong;
 630
 631       line->dir_propagated_forward = last_strong;
 632
 633       line = _gtk_text_line_next (line);
 634     }
 635
 636   /* Continue propagating as long as the previous resolved forward
 637    * is different from last_strong.
 638    */
 639   {
 640     GtkTextIter end_propagate;
 641
 642     while (line &&
 643            line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
 644            line->dir_propagated_forward != last_strong)
 645       {
 646         GtkTextLine *prev = line;
 647         line->dir_propagated_forward = last_strong;
 648
 649         line = _gtk_text_line_next(line);
 650         if (!line)
 651           {
 652             line = prev;
 653             break;
 654           }
 655       }
 656
 657     /* The last line to invalidate is the last line before the
 658      * line with the strong character. Or in case of the end of the
 659      * buffer, the last line of the buffer. (There seems to be an
 660      * extra "virtual" last line in the buffer that must not be used
 661      * calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
 662      * _gtk_text_line_previous is ok in that case as well.)
 663      */
 664     line = _gtk_text_line_previous (line);
 665     _gtk_text_btree_get_iter_at_line (tree, &end_propagate, line, 0);
 666     _gtk_text_btree_invalidate_region (tree, end, &end_propagate);
 667   }
 668
 669   /* Sweep backward */
 670
 671   /* The variable dir_below_propagated contains the backward propagated
 672    * direction after end. It is neutral if end is at the end of
 673    * the buffer.
 674   */
 675   dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
 676   if (end_line_next)
 677     dir_below_propagated = end_line_next->dir_propagated_back;
 678
 679   /* Loop backward and propagate the direction of each paragraph
 680    * to all neutral lines.
 681    */
 682   line = end_line;
 683   last_strong = dir_below_propagated;
 684   while (line != start_line_prev)
 685     {
 686       if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
 687         last_strong = line->dir_strong;
 688
 689       line->dir_propagated_back = last_strong;
 690
 691       line = _gtk_text_line_previous (line);
 692     }
 693
 694   /* Continue propagating as long as the resolved backward dir
 695    * is different from last_strong.
 696    */
 697   {
 698     GtkTextIter start_propagate;
 699
 700     while (line &&
 701            line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
 702            line->dir_propagated_back != last_strong)
 703       {
 704         GtkTextLine *prev = line;
 705         line->dir_propagated_back = last_strong;
 706
 707         line = _gtk_text_line_previous (line);
 708         if (!line)
 709           {
 710             line = prev;
 711             break;
 712           }
 713       }
 714
 715     /* We only need to invalidate for backwards propagation if the
 716      * line we ended up on didn't get a direction from forwards
 717      * propagation.
 718      */
 719     if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
 720       {
 721         _gtk_text_btree_get_iter_at_line (tree, &start_propagate, line, 0);
 722         _gtk_text_btree_invalidate_region(tree, &start_propagate, start);
 723       }
 724   }
 725 }
 726
 727 void
 728 _gtk_text_btree_delete (GtkTextIter *start,
 729                         GtkTextIter *end)
 730 {
 731   GtkTextLineSegment *prev_seg;             /* The segment just before the start
 732                                              * of the deletion range. */
 733   GtkTextLineSegment *last_seg;             /* The segment just after the end
 734                                              * of the deletion range. */
 735   GtkTextLineSegment *seg, *next, *next2;
 736   GtkTextLine *curline;
 737   GtkTextBTreeNode *curnode, *node;
 738   GtkTextBTree *tree;
 739   GtkTextLine *start_line;
 740   GtkTextLine *end_line;
 741   GtkTextLine *deleted_lines = NULL;        /* List of lines we've deleted */
 742   gint start_byte_offset;
 743
 744   g_return_if_fail (start != NULL);
 745   g_return_if_fail (end != NULL);
 746   g_return_if_fail (_gtk_text_iter_get_btree (start) ==
 747                     _gtk_text_iter_get_btree (end));
 748
 749   gtk_text_iter_order (start, end);
 750
 751   tree = _gtk_text_iter_get_btree (start);
 752
 753   if (gtk_debug_flags & GTK_DEBUG_TEXT)
 754     _gtk_text_btree_check (tree);
 755
 756   /* Broadcast the need for redisplay before we break the iterators */
 757   DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
 758   _gtk_text_btree_invalidate_region (tree, start, end);
 759
 760   /* Save the byte offset so we can reset the iterators */
 761   start_byte_offset = gtk_text_iter_get_line_index (start);
 762
 763   start_line = _gtk_text_iter_get_text_line (start);
 764   end_line = _gtk_text_iter_get_text_line (end);
 765
 766   /*
 767    * Split the start and end segments, so we have a place
 768    * to insert our new text.
 769    *
 770    * Tricky point:  split at end first;  otherwise the split
 771    * at end may invalidate seg and/or prev_seg. This allows
 772    * us to avoid invalidating segments for start.
 773    */
 774
 775   last_seg = gtk_text_line_segment_split (end);
 776   if (last_seg != NULL)
 777     last_seg = last_seg->next;
 778   else
 779     last_seg = end_line->segments;
 780
 781   prev_seg = gtk_text_line_segment_split (start);
 782   if (prev_seg != NULL)
 783     {
 784       seg = prev_seg->next;
 785       prev_seg->next = last_seg;
 786     }
 787   else
 788     {
 789       seg = start_line->segments;
 790       start_line->segments = last_seg;
 791     }
 792
 793   /* notify iterators that their segments need recomputation,
 794      just for robustness. */
 795   segments_changed (tree);
 796
 797   /*
 798    * Delete all of the segments between prev_seg and last_seg.
 799    */
 800
 801   curline = start_line;
 802   curnode = curline->parent;
 803   while (seg != last_seg)
 804     {
 805       gint char_count = 0;
 806
 807       if (seg == NULL)
 808         {
 809           GtkTextLine *nextline;
 810
 811           /*
 812            * We just ran off the end of a line.  First find the
 813            * next line, then go back to the old line and delete it
 814            * (unless it's the starting line for the range).
 815            */
 816
 817           nextline = _gtk_text_line_next (curline);
 818           if (curline != start_line)
 819             {
 820               if (curnode == start_line->parent)
 821                 start_line->next = curline->next;
 822               else
 823                 curnode->children.line = curline->next;
 824
 825               for (node = curnode; node != NULL;
 826                    node = node->parent)
 827                 {
 828                   /* Don't update node->num_chars, because
 829                    * that was done when we deleted the segments.
 830                    */
 831                   node->num_lines -= 1;
 832                 }
 833
 834               curnode->num_children -= 1;
 835               curline->next = deleted_lines;
 836               deleted_lines = curline;
 837             }
 838
 839           curline = nextline;
 840           seg = curline->segments;
 841
 842           /*
 843            * If the GtkTextBTreeNode is empty then delete it and its parents,
 844            * recursively upwards until a non-empty GtkTextBTreeNode is found.
 845            */
 846
 847           while (curnode->num_children == 0)
 848             {
 849               GtkTextBTreeNode *parent;
 850
 851               parent = curnode->parent;
 852               if (parent->children.node == curnode)
 853                 {
 854                   parent->children.node = curnode->next;
 855                 }
 856               else
 857                 {
 858                   GtkTextBTreeNode *prevnode = parent->children.node;
 859                   while (prevnode->next != curnode)
 860                     {
 861                       prevnode = prevnode->next;
 862                     }
 863                   prevnode->next = curnode->next;
 864                 }
 865               parent->num_children--;
 866               gtk_text_btree_node_free_empty (tree, curnode);
 867               curnode = parent;
 868             }
 869           curnode = curline->parent;
 870           continue;
 871         }
 872
 873       next = seg->next;
 874       char_count = seg->char_count;
 875
 876       if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
 877         {
 878           /*
 879            * This segment refuses to die.  Move it to prev_seg and
 880            * advance prev_seg if the segment has left gravity.
 881            */
 882
 883           if (prev_seg == NULL)
 884             {
 885               seg->next = start_line->segments;
 886               start_line->segments = seg;
 887             }
 888           else if (prev_seg->next &&
 889                    seg->type == &gtk_text_toggle_off_type &&
 890                    prev_seg->next->type == &gtk_text_toggle_on_type &&
 891                    seg->body.toggle.info == prev_seg->next->body.toggle.info)
 892             {
 893               /* Try to match an off toggle with the matching on toggle
 894                * if it immediately follows. This is a common case, and
 895                * handling it here prevents quadratic blowup in
 896                * cleanup_line() below. See bug 317125.
 897                */
 898               next2 = prev_seg->next->next;
 899               g_free ((char *)prev_seg->next);
 900               prev_seg->next = next2;
 901               g_free ((char *)seg);
 902               seg = NULL;
 903             }
 904           else
 905             {
 906               seg->next = prev_seg->next;
 907               prev_seg->next = seg;
 908             }
 909
 910           if (seg && seg->type->leftGravity)
 911             {
 912               prev_seg = seg;
 913             }
 914         }
 915       else
 916         {
 917           /* Segment is gone. Decrement the char count of the node and
 918              all its parents. */
 919           for (node = curnode; node != NULL;
 920                node = node->parent)
 921             {
 922               node->num_chars -= char_count;
 923             }
 924         }
 925
 926       seg = next;
 927     }
 928
 929   /*
 930    * If the beginning and end of the deletion range are in different
 931    * lines, join the two lines together and discard the ending line.
 932    */
 933
 934   if (start_line != end_line)
 935     {
 936       BTreeView *view;
 937       GtkTextBTreeNode *ancestor_node;
 938       GtkTextLine *prevline;
 939       int chars_moved;
 940
 941       /* last_seg was appended to start_line up at the top of this function */
 942       chars_moved = 0;
 943       for (seg = last_seg; seg != NULL;
 944            seg = seg->next)
 945         {
 946           chars_moved += seg->char_count;
 947           if (seg->type->lineChangeFunc != NULL)
 948             {
 949               (*seg->type->lineChangeFunc)(seg, end_line);
 950             }
 951         }
 952
 953       for (node = start_line->parent; node != NULL;
 954            node = node->parent)
 955         {
 956           node->num_chars += chars_moved;
 957         }
 958
 959       curnode = end_line->parent;
 960       for (node = curnode; node != NULL;
 961            node = node->parent)
 962         {
 963           node->num_chars -= chars_moved;
 964           node->num_lines--;
 965         }
 966       curnode->num_children--;
 967       prevline = curnode->children.line;
 968       if (prevline == end_line)
 969         {
 970           curnode->children.line = end_line->next;
 971         }
 972       else
 973         {
 974           while (prevline->next != end_line)
 975             {
 976               prevline = prevline->next;
 977             }
 978           prevline->next = end_line->next;
 979         }
 980       end_line->next = deleted_lines;
 981       deleted_lines = end_line;
 982
 983       /* We now fix up the per-view aggregates. We add all the height and
 984        * width for the deleted lines to the start line, so that when revalidation
 985        * occurs, the correct change in size is seen.
 986        */
 987       ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
 988       view = tree->views;
 989       while (view)
 990         {
 991           GtkTextLine *line;
 992           GtkTextLineData *ld;
 993
 994           gint deleted_width = 0;
 995           gint deleted_height = 0;
 996
 997           line = deleted_lines;
 998           while (line)
 999             {
1000               GtkTextLine *next_line = line->next;
1001               ld = _gtk_text_line_get_data (line, view->view_id);
1002
1003               if (ld)
1004                 {
1005                   deleted_width = MAX (deleted_width, ld->width);
1006                   deleted_height += ld->height;
1007                 }
1008
1009               if (!view->next)
1010                 gtk_text_line_destroy (tree, line);
1011
1012               line = next_line;
1013             }
1014
1015           if (deleted_width > 0 || deleted_height > 0)
1016             {
1017               ld = _gtk_text_line_get_data (start_line, view->view_id);
1018
1019               if (ld == NULL)
1020                 {
1021                   /* This means that start_line has never been validated.
1022                    * We don't really want to do the validation here but
1023                    * we do need to store our temporary sizes. So we
1024                    * create the line data and assume a line w/h of 0.
1025                    */
1026                   ld = _gtk_text_line_data_new (view->layout, start_line);
1027                   _gtk_text_line_add_data (start_line, ld);
1028                   ld->width = 0;
1029                   ld->height = 0;
1030                   ld->valid = FALSE;
1031                 }
1032
1033               ld->width = MAX (deleted_width, ld->width);
1034               ld->height += deleted_height;
1035               ld->valid = FALSE;
1036             }
1037
1038           gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
1039           if (ancestor_node->parent)
1040             gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
1041
1042           view = view->next;
1043         }
1044
1045       /* avoid dangling pointer */
1046       deleted_lines = NULL;
1047
1048       gtk_text_btree_rebalance (tree, curnode);
1049     }
1050
1051   /*
1052    * Cleanup the segments in the new line.
1053    */
1054
1055   cleanup_line (start_line);
1056
1057   /*
1058    * Lastly, rebalance the first GtkTextBTreeNode of the range.
1059    */
1060
1061   gtk_text_btree_rebalance (tree, start_line->parent);
1062
1063   /* Notify outstanding iterators that they
1064      are now hosed */
1065   chars_changed (tree);
1066   segments_changed (tree);
1067
1068   if (gtk_debug_flags & GTK_DEBUG_TEXT)
1069     _gtk_text_btree_check (tree);
1070
1071   /* Re-initialize our iterators */
1072   _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
1073   *end = *start;
1074
1075   gtk_text_btree_resolve_bidi (start, end);
1076 }
1077
1078 void
1079 _gtk_text_btree_insert (GtkTextIter *iter,
1080                         const gchar *text,
1081                         gint         len)
1082 {
1083   GtkTextLineSegment *prev_seg;     /* The segment just before the first
1084                                      * new segment (NULL means new segment
1085                                      * is at beginning of line). */
1086   GtkTextLineSegment *cur_seg;              /* Current segment;  new characters
1087                                              * are inserted just after this one.
1088                                              * NULL means insert at beginning of
1089                                              * line. */
1090   GtkTextLine *line;           /* Current line (new segments are
1091                                 * added to this line). */
1092   GtkTextLineSegment *seg;
1093   GtkTextLine *newline;
1094   int chunk_len;                        /* # characters in current chunk. */
1095   gint sol;                           /* start of line */
1096   gint eol;                           /* Pointer to character just after last
1097                                        * one in current chunk.
1098                                        */
1099   gint delim;                          /* index of paragraph delimiter */
1100   int line_count_delta;                /* Counts change to total number of
1101                                         * lines in file.
1102                                         */
1103
1104   int char_count_delta;                /* change to number of chars */
1105   GtkTextBTree *tree;
1106   gint start_byte_index;
1107   GtkTextLine *start_line;
1108
1109   g_return_if_fail (text != NULL);
1110   g_return_if_fail (iter != NULL);
1111
1112   if (len < 0)
1113     len = strlen (text);
1114
1115   /* extract iterator info */
1116   tree = _gtk_text_iter_get_btree (iter);
1117   line = _gtk_text_iter_get_text_line (iter);
1118
1119   start_line = line;
1120   start_byte_index = gtk_text_iter_get_line_index (iter);
1121
1122   /* Get our insertion segment split. Note this assumes line allows
1123    * char insertions, which isn't true of the "last" line. But iter
1124    * should not be on that line, as we assert here.
1125    */
1126   g_assert (!_gtk_text_line_is_last (line, tree));
1127   prev_seg = gtk_text_line_segment_split (iter);
1128   cur_seg = prev_seg;
1129
1130   /* Invalidate all iterators */
1131   chars_changed (tree);
1132   segments_changed (tree);
1133
1134   /*
1135    * Chop the text up into lines and create a new segment for
1136    * each line, plus a new line for the leftovers from the
1137    * previous line.
1138    */
1139
1140   eol = 0;
1141   sol = 0;
1142   line_count_delta = 0;
1143   char_count_delta = 0;
1144   while (eol < len)
1145     {
1146       sol = eol;
1147
1148       pango_find_paragraph_boundary (text + sol,
1149                                      len - sol,
1150                                      &delim,
1151                                      &eol);
1152
1153       /* make these relative to the start of the text */
1154       delim += sol;
1155       eol += sol;
1156
1157       g_assert (eol >= sol);
1158       g_assert (delim >= sol);
1159       g_assert (eol >= delim);
1160       g_assert (sol >= 0);
1161       g_assert (eol <= len);
1162
1163       chunk_len = eol - sol;
1164
1165       g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
1166       seg = _gtk_char_segment_new (&text[sol], chunk_len);
1167
1168       char_count_delta += seg->char_count;
1169
1170       if (cur_seg == NULL)
1171         {
1172           seg->next = line->segments;
1173           line->segments = seg;
1174         }
1175       else
1176         {
1177           seg->next = cur_seg->next;
1178           cur_seg->next = seg;
1179         }
1180
1181       if (delim == eol)
1182         {
1183           /* chunk didn't end with a paragraph separator */
1184           g_assert (eol == len);
1185           break;
1186         }
1187
1188       /*
1189        * The chunk ended with a newline, so create a new GtkTextLine
1190        * and move the remainder of the old line to it.
1191        */
1192
1193       newline = gtk_text_line_new ();
1194       gtk_text_line_set_parent (newline, line->parent);
1195       newline->next = line->next;
1196       line->next = newline;
1197       newline->segments = seg->next;
1198       seg->next = NULL;
1199       line = newline;
1200       cur_seg = NULL;
1201       line_count_delta++;
1202     }
1203
1204   /*
1205    * Cleanup the starting line for the insertion, plus the ending
1206    * line if it's different.
1207    */
1208
1209   cleanup_line (start_line);
1210   if (line != start_line)
1211     {
1212       cleanup_line (line);
1213     }
1214
1215   post_insert_fixup (tree, line, line_count_delta, char_count_delta);
1216
1217   /* Invalidate our region, and reset the iterator the user
1218      passed in to point to the end of the inserted text. */
1219   {
1220     GtkTextIter start;
1221     GtkTextIter end;
1222
1223
1224     _gtk_text_btree_get_iter_at_line (tree,
1225                                       &start,
1226                                       start_line,
1227                                       start_byte_index);
1228     end = start;
1229
1230     /* We could almost certainly be more efficient here
1231        by saving the information from the insertion loop
1232        above. FIXME */
1233     gtk_text_iter_forward_chars (&end, char_count_delta);
1234
1235     DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1236     _gtk_text_btree_invalidate_region (tree,
1237                                       &start, &end);
1238
1239
1240     /* Convenience for the user */
1241     *iter = end;
1242
1243     gtk_text_btree_resolve_bidi (&start, &end);
1244   }
1245 }
1246
1247 static void
1248 insert_pixbuf_or_widget_segment (GtkTextIter        *iter,
1249                                  GtkTextLineSegment *seg)
1250
1251 {
1252   GtkTextIter start;
1253   GtkTextLineSegment *prevPtr;
1254   GtkTextLine *line;
1255   GtkTextBTree *tree;
1256   gint start_byte_offset;
1257
1258   line = _gtk_text_iter_get_text_line (iter);
1259   tree = _gtk_text_iter_get_btree (iter);
1260   start_byte_offset = gtk_text_iter_get_line_index (iter);
1261
1262   prevPtr = gtk_text_line_segment_split (iter);
1263   if (prevPtr == NULL)
1264     {
1265       seg->next = line->segments;
1266       line->segments = seg;
1267     }
1268   else
1269     {
1270       seg->next = prevPtr->next;
1271       prevPtr->next = seg;
1272     }
1273
1274   post_insert_fixup (tree, line, 0, seg->char_count);
1275
1276   chars_changed (tree);
1277   segments_changed (tree);
1278
1279   /* reset *iter for the user, and invalidate tree nodes */
1280
1281   _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1282
1283   *iter = start;
1284   gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1285
1286   DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1287   _gtk_text_btree_invalidate_region (tree, &start, iter);
1288 }
1289
1290 void
1291 _gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1292                               GdkPixbuf   *pixbuf)
1293 {
1294   GtkTextLineSegment *seg;
1295
1296   seg = _gtk_pixbuf_segment_new (pixbuf);
1297
1298   insert_pixbuf_or_widget_segment (iter, seg);
1299 }
1300
1301 void
1302 _gtk_text_btree_insert_child_anchor (GtkTextIter        *iter,
1303                                      GtkTextChildAnchor *anchor)
1304 {
1305   GtkTextLineSegment *seg;
1306   GtkTextBTree *tree;
1307
1308   if (anchor->segment != NULL)
1309     {
1310       g_warning (G_STRLOC": Same child anchor can't be inserted twice");
1311       return;
1312     }
1313
1314   seg = _gtk_widget_segment_new (anchor);
1315
1316   tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1317   seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1318
1319   insert_pixbuf_or_widget_segment (iter, seg);
1320
1321   if (tree->child_anchor_table == NULL)
1322     tree->child_anchor_table = g_hash_table_new (NULL, NULL);
1323
1324   g_hash_table_insert (tree->child_anchor_table,
1325                        seg->body.child.obj,
1326                        seg->body.child.obj);
1327 }
1328
1329 void
1330 _gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1331 {
1332   GtkTextLineSegment *seg;
1333
1334   seg = anchor->segment;
1335
1336   g_hash_table_remove (seg->body.child.tree->child_anchor_table,
1337                        anchor);
1338 }
1339
1340 /*
1341  * View stuff
1342  */
1343
1344 static GtkTextLine*
1345 find_line_by_y (GtkTextBTree *tree, BTreeView *view,
1346                 GtkTextBTreeNode *node, gint y, gint *line_top,
1347                 GtkTextLine *last_line)
1348 {
1349   gint current_y = 0;
1350
1351   if (gtk_debug_flags & GTK_DEBUG_TEXT)
1352     _gtk_text_btree_check (tree);
1353
1354   if (node->level == 0)
1355     {
1356       GtkTextLine *line;
1357
1358       line = node->children.line;
1359
1360       while (line != NULL && line != last_line)
1361         {
1362           GtkTextLineData *ld;
1363
1364           ld = _gtk_text_line_get_data (line, view->view_id);
1365
1366           if (ld)
1367             {
1368               if (y < (current_y + (ld ? ld->height : 0)))
1369                 return line;
1370
1371               current_y += ld->height;
1372               *line_top += ld->height;
1373             }
1374
1375           line = line->next;
1376         }
1377       return NULL;
1378     }
1379   else
1380     {
1381       GtkTextBTreeNode *child;
1382
1383       child = node->children.node;
1384
1385       while (child != NULL)
1386         {
1387           gint width;
1388           gint height;
1389
1390           gtk_text_btree_node_get_size (child, view->view_id,
1391                                         &width, &height);
1392
1393           if (y < (current_y + height))
1394             return find_line_by_y (tree, view, child,
1395                                    y - current_y, line_top,
1396                                    last_line);
1397
1398           current_y += height;
1399           *line_top += height;
1400
1401           child = child->next;
1402         }
1403
1404       return NULL;
1405     }
1406 }
1407
1408 GtkTextLine *
1409 _gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1410                                 gpointer      view_id,
1411                                 gint          ypixel,
1412                                 gint         *line_top_out)
1413 {
1414   GtkTextLine *line;
1415   BTreeView *view;
1416   GtkTextLine *last_line;
1417   gint line_top = 0;
1418
1419   view = gtk_text_btree_get_view (tree, view_id);
1420   g_return_val_if_fail (view != NULL, NULL);
1421
1422   last_line = get_last_line (tree);
1423
1424   line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1425                          last_line);
1426
1427   if (line_top_out)
1428     *line_top_out = line_top;
1429
1430   return line;
1431 }
1432
1433 static gint
1434 find_line_top_in_line_list (GtkTextBTree *tree,
1435                             BTreeView *view,
1436                             GtkTextLine *line,
1437                             GtkTextLine *target_line,
1438                             gint y)
1439 {
1440   while (line != NULL)
1441     {
1442       GtkTextLineData *ld;
1443
1444       if (line == target_line)
1445         return y;
1446
1447       ld = _gtk_text_line_get_data (line, view->view_id);
1448       if (ld)
1449         y += ld->height;
1450
1451       line = line->next;
1452     }
1453
1454   g_assert_not_reached (); /* If we get here, our
1455                               target line didn't exist
1456                               under its parent node */
1457   return 0;
1458 }
1459
1460 gint
1461 _gtk_text_btree_find_line_top (GtkTextBTree *tree,
1462                               GtkTextLine *target_line,
1463                               gpointer view_id)
1464 {
1465   gint y = 0;
1466   BTreeView *view;
1467   GSList *nodes;
1468   GSList *iter;
1469   GtkTextBTreeNode *node;
1470
1471   view = gtk_text_btree_get_view (tree, view_id);
1472
1473   g_return_val_if_fail (view != NULL, 0);
1474
1475   nodes = NULL;
1476   node = target_line->parent;
1477   while (node != NULL)
1478     {
1479       nodes = g_slist_prepend (nodes, node);
1480       node = node->parent;
1481     }
1482
1483   iter = nodes;
1484   while (iter != NULL)
1485     {
1486       node = iter->data;
1487
1488       if (node->level == 0)
1489         {
1490           g_slist_free (nodes);
1491           return find_line_top_in_line_list (tree, view,
1492                                              node->children.line,
1493                                              target_line, y);
1494         }
1495       else
1496         {
1497           GtkTextBTreeNode *child;
1498           GtkTextBTreeNode *target_node;
1499
1500           g_assert (iter->next != NULL); /* not at level 0 */
1501           target_node = iter->next->data;
1502
1503           child = node->children.node;
1504
1505           while (child != NULL)
1506             {
1507               gint width;
1508               gint height;
1509
1510               if (child == target_node)
1511                 break;
1512               else
1513                 {
1514                   gtk_text_btree_node_get_size (child, view->view_id,
1515                                                 &width, &height);
1516                   y += height;
1517                 }
1518               child = child->next;
1519             }
1520           g_assert (child != NULL); /* should have broken out before we
1521                                        ran out of nodes */
1522         }
1523
1524       iter = g_slist_next (iter);
1525     }
1526
1527   g_assert_not_reached (); /* we return when we find the target line */
1528   return 0;
1529 }
1530
1531 void
1532 _gtk_text_btree_add_view (GtkTextBTree *tree,
1533                          GtkTextLayout *layout)
1534 {
1535   BTreeView *view;
1536   GtkTextLine *last_line;
1537   GtkTextLineData *line_data;
1538
1539   g_return_if_fail (tree != NULL);
1540
1541   view = g_new (BTreeView, 1);
1542
1543   view->view_id = layout;
1544   view->layout = layout;
1545
1546   view->next = tree->views;
1547   view->prev = NULL;
1548
1549   if (tree->views)
1550     {
1551       g_assert (tree->views->prev == NULL);
1552       tree->views->prev = view;
1553     }
1554
1555   tree->views = view;
1556
1557   /* The last line in the buffer has identity values for the per-view
1558    * data so that we can avoid special case checks for it in a large
1559    * number of loops
1560    */
1561   last_line = get_last_line (tree);
1562
1563   line_data = g_new (GtkTextLineData, 1);
1564   line_data->view_id = layout;
1565   line_data->next = NULL;
1566   line_data->width = 0;
1567   line_data->height = 0;
1568   line_data->valid = TRUE;
1569
1570   _gtk_text_line_add_data (last_line, line_data);
1571 }
1572
1573 void
1574 _gtk_text_btree_remove_view (GtkTextBTree *tree,
1575                              gpointer      view_id)
1576 {
1577   BTreeView *view;
1578   GtkTextLine *last_line;
1579   GtkTextLineData *line_data;
1580
1581   g_return_if_fail (tree != NULL);
1582
1583   view = tree->views;
1584
1585   while (view != NULL)
1586     {
1587       if (view->view_id == view_id)
1588         break;
1589
1590       view = view->next;
1591     }
1592
1593   g_return_if_fail (view != NULL);
1594
1595   if (view->next)
1596     view->next->prev = view->prev;
1597
1598   if (view->prev)
1599     view->prev->next = view->next;
1600
1601   if (view == tree->views)
1602     tree->views = view->next;
1603
1604   /* Remove the line data for the last line which we added ourselves.
1605    * (Do this first, so that we don't try to call the view's line data destructor on it.)
1606    */
1607   last_line = get_last_line (tree);
1608   line_data = _gtk_text_line_remove_data (last_line, view_id);
1609   g_free (line_data);
1610
1611   gtk_text_btree_node_remove_view (view, tree->root_node, view_id);
1612
1613   view->layout = (gpointer) 0xdeadbeef;
1614   view->view_id = (gpointer) 0xdeadbeef;
1615
1616   g_free (view);
1617 }
1618
1619 void
1620 _gtk_text_btree_invalidate_region (GtkTextBTree      *tree,
1621                                    const GtkTextIter *start,
1622                                    const GtkTextIter *end)
1623 {
1624   BTreeView *view;
1625
1626   view = tree->views;
1627
1628   while (view != NULL)
1629     {
1630       gtk_text_layout_invalidate (view->layout, start, end);
1631
1632       view = view->next;
1633     }
1634 }
1635
1636 void
1637 _gtk_text_btree_get_view_size (GtkTextBTree *tree,
1638                               gpointer view_id,
1639                               gint *width,
1640                               gint *height)
1641 {
1642   g_return_if_fail (tree != NULL);
1643   g_return_if_fail (view_id != NULL);
1644
1645   gtk_text_btree_node_get_size (tree->root_node, view_id,
1646                                 width, height);
1647 }
1648
1649 /*
1650  * Tag
1651  */
1652
1653 typedef struct {
1654   GtkTextIter *iters;
1655   guint count;
1656   guint alloced;
1657 } IterStack;
1658
1659 static IterStack*
1660 iter_stack_new (void)
1661 {
1662   IterStack *stack;
1663   stack = g_slice_new (IterStack);
1664   stack->iters = NULL;
1665   stack->count = 0;
1666   stack->alloced = 0;
1667   return stack;
1668 }
1669
1670 static void
1671 iter_stack_push (IterStack         *stack,
1672                  const GtkTextIter *iter)
1673 {
1674   stack->count += 1;
1675   if (stack->count > stack->alloced)
1676     {
1677       stack->alloced = stack->count*2;
1678       stack->iters = g_realloc (stack->iters,
1679                                 stack->alloced * sizeof (GtkTextIter));
1680     }
1681   stack->iters[stack->count-1] = *iter;
1682 }
1683
1684 static gboolean
1685 iter_stack_pop (IterStack   *stack,
1686                 GtkTextIter *iter)
1687 {
1688   if (stack->count == 0)
1689     return FALSE;
1690   else
1691     {
1692       stack->count -= 1;
1693       *iter = stack->iters[stack->count];
1694       return TRUE;
1695     }
1696 }
1697
1698 static void
1699 iter_stack_free (IterStack *stack)
1700 {
1701   g_free (stack->iters);
1702   g_slice_free (IterStack, stack);
1703 }
1704
1705 static void
1706 iter_stack_invert (IterStack *stack)
1707 {
1708   if (stack->count > 0)
1709     {
1710       guint i = 0;
1711       guint j = stack->count - 1;
1712       while (i < j)
1713         {
1714           GtkTextIter tmp;
1715
1716           tmp = stack->iters[i];
1717           stack->iters[i] = stack->iters[j];
1718           stack->iters[j] = tmp;
1719
1720           ++i;
1721           --j;
1722         }
1723     }
1724 }
1725
1726 static void
1727 queue_tag_redisplay (GtkTextBTree      *tree,
1728                      GtkTextTag        *tag,
1729                      const GtkTextIter *start,
1730                      const GtkTextIter *end)
1731 {
1732   if (_gtk_text_tag_affects_size (tag))
1733     {
1734       DV (g_print ("invalidating due to size-affecting tag (%s)\n", G_STRLOC));
1735       _gtk_text_btree_invalidate_region (tree, start, end);
1736     }
1737   else if (_gtk_text_tag_affects_nonsize_appearance (tag))
1738     {
1739       /* We only need to queue a redraw, not a relayout */
1740       redisplay_region (tree, start, end);
1741     }
1742
1743   /* We don't need to do anything if the tag doesn't affect display */
1744 }
1745
1746 void
1747 _gtk_text_btree_tag (const GtkTextIter *start_orig,
1748                      const GtkTextIter *end_orig,
1749                      GtkTextTag        *tag,
1750                      gboolean           add)
1751 {
1752   GtkTextLineSegment *seg, *prev;
1753   GtkTextLine *cleanupline;
1754   gboolean toggled_on;
1755   GtkTextLine *start_line;
1756   GtkTextLine *end_line;
1757   GtkTextIter iter;
1758   GtkTextIter start, end;
1759   GtkTextBTree *tree;
1760   IterStack *stack;
1761   GtkTextTagInfo *info;
1762
1763   g_return_if_fail (start_orig != NULL);
1764   g_return_if_fail (end_orig != NULL);
1765   g_return_if_fail (GTK_IS_TEXT_TAG (tag));
1766   g_return_if_fail (_gtk_text_iter_get_btree (start_orig) ==
1767                     _gtk_text_iter_get_btree (end_orig));
1768   g_return_if_fail (tag->table == _gtk_text_iter_get_btree (start_orig)->table);
1769
1770 #if 0
1771   printf ("%s tag %s from %d to %d\n",
1772           add ? "Adding" : "Removing",
1773           tag->name,
1774           gtk_text_buffer_get_offset (start_orig),
1775           gtk_text_buffer_get_offset (end_orig));
1776 #endif
1777
1778   if (gtk_text_iter_equal (start_orig, end_orig))
1779     return;
1780
1781   start = *start_orig;
1782   end = *end_orig;
1783
1784   gtk_text_iter_order (&start, &end);
1785
1786   tree = _gtk_text_iter_get_btree (&start);
1787
1788   queue_tag_redisplay (tree, tag, &start, &end);
1789
1790   info = gtk_text_btree_get_tag_info (tree, tag);
1791
1792   start_line = _gtk_text_iter_get_text_line (&start);
1793   end_line = _gtk_text_iter_get_text_line (&end);
1794
1795   /* Find all tag toggles in the region; we are going to delete them.
1796      We need to find them in advance, because
1797      forward_find_tag_toggle () won't work once we start playing around
1798      with the tree. */
1799   stack = iter_stack_new ();
1800   iter = start;
1801
1802   /* forward_to_tag_toggle() skips a toggle at the start iterator,
1803    * which is deliberate - we don't want to delete a toggle at the
1804    * start.
1805    */
1806   while (gtk_text_iter_forward_to_tag_toggle (&iter, tag))
1807     {
1808       if (gtk_text_iter_compare (&iter, &end) >= 0)
1809         break;
1810       else
1811         iter_stack_push (stack, &iter);
1812     }
1813
1814   /* We need to traverse the toggles in order. */
1815   iter_stack_invert (stack);
1816
1817   /*
1818    * See whether the tag is present at the start of the range.  If
1819    * the state doesn't already match what we want then add a toggle
1820    * there.
1821    */
1822
1823   toggled_on = gtk_text_iter_has_tag (&start, tag);
1824   if ( (add && !toggled_on) ||
1825        (!add && toggled_on) )
1826     {
1827       /* This could create a second toggle at the start position;
1828          cleanup_line () will remove it if so. */
1829       seg = _gtk_toggle_segment_new (info, add);
1830
1831       prev = gtk_text_line_segment_split (&start);
1832       if (prev == NULL)
1833         {
1834           seg->next = start_line->segments;
1835           start_line->segments = seg;
1836         }
1837       else
1838         {
1839           seg->next = prev->next;
1840           prev->next = seg;
1841         }
1842
1843       /* cleanup_line adds the new toggle to the node counts. */
1844 #if 0
1845       printf ("added toggle at start\n");
1846 #endif
1847       /* we should probably call segments_changed, but in theory
1848          any still-cached segments in the iters we are about to
1849          use are still valid, since they're in front
1850          of this spot. */
1851     }
1852
1853   /*
1854    *
1855    * Scan the range of characters and delete any internal tag
1856    * transitions.  Keep track of what the old state was at the end
1857    * of the range, and add a toggle there if it's needed.
1858    *
1859    */
1860
1861   cleanupline = start_line;
1862   while (iter_stack_pop (stack, &iter))
1863     {
1864       GtkTextLineSegment *indexable_seg;
1865       GtkTextLine *line;
1866
1867       line = _gtk_text_iter_get_text_line (&iter);
1868       seg = _gtk_text_iter_get_any_segment (&iter);
1869       indexable_seg = _gtk_text_iter_get_indexable_segment (&iter);
1870
1871       g_assert (seg != NULL);
1872       g_assert (indexable_seg != NULL);
1873       g_assert (seg != indexable_seg);
1874
1875       prev = line->segments;
1876
1877       /* Find the segment that actually toggles this tag. */
1878       while (seg != indexable_seg)
1879         {
1880           g_assert (seg != NULL);
1881           g_assert (indexable_seg != NULL);
1882           g_assert (seg != indexable_seg);
1883
1884           if ( (seg->type == &gtk_text_toggle_on_type ||
1885                 seg->type == &gtk_text_toggle_off_type) &&
1886                (seg->body.toggle.info == info) )
1887             break;
1888           else
1889             seg = seg->next;
1890         }
1891
1892       g_assert (seg != NULL);
1893       g_assert (indexable_seg != NULL);
1894
1895       g_assert (seg != indexable_seg); /* If this happens, then
1896                                           forward_to_tag_toggle was
1897                                           full of shit. */
1898       g_assert (seg->body.toggle.info->tag == tag);
1899
1900       /* If this happens, when previously tagging we didn't merge
1901          overlapping tags. */
1902       g_assert ( (toggled_on && seg->type == &gtk_text_toggle_off_type) ||
1903                  (!toggled_on && seg->type == &gtk_text_toggle_on_type) );
1904
1905       toggled_on = !toggled_on;
1906
1907 #if 0
1908       printf ("deleting %s toggle\n",
1909               seg->type == &gtk_text_toggle_on_type ? "on" : "off");
1910 #endif
1911       /* Remove toggle segment from the list. */
1912       if (prev == seg)
1913         {
1914           line->segments = seg->next;
1915         }
1916       else
1917         {
1918           while (prev->next != seg)
1919             {
1920               prev = prev->next;
1921             }
1922           prev->next = seg->next;
1923         }
1924
1925       /* Inform iterators we've hosed them. This actually reflects a
1926          bit of inefficiency; if you have the same tag toggled on and
1927          off a lot in a single line, we keep having the rescan from
1928          the front of the line. Of course we have to do that to get
1929          "prev" anyway, but here we are doing it an additional
1930          time. FIXME */
1931       segments_changed (tree);
1932
1933       /* Update node counts */
1934       if (seg->body.toggle.inNodeCounts)
1935         {
1936           _gtk_change_node_toggle_count (line->parent,
1937                                          info, -1);
1938           seg->body.toggle.inNodeCounts = FALSE;
1939         }
1940
1941       g_free (seg);
1942
1943       /* We only clean up lines when we're done with them, saves some
1944          gratuitous line-segment-traversals */
1945
1946       if (cleanupline != line)
1947         {
1948           cleanup_line (cleanupline);
1949           cleanupline = line;
1950         }
1951     }
1952
1953   iter_stack_free (stack);
1954
1955   /* toggled_on now reflects the toggle state _just before_ the
1956      end iterator. The end iterator could already have a toggle
1957      on or a toggle off. */
1958   if ( (add && !toggled_on) ||
1959        (!add && toggled_on) )
1960     {
1961       /* This could create a second toggle at the start position;
1962          cleanup_line () will remove it if so. */
1963
1964       seg = _gtk_toggle_segment_new (info, !add);
1965
1966       prev = gtk_text_line_segment_split (&end);
1967       if (prev == NULL)
1968         {
1969           seg->next = end_line->segments;
1970           end_line->segments = seg;
1971         }
1972       else
1973         {
1974           seg->next = prev->next;
1975           prev->next = seg;
1976         }
1977       /* cleanup_line adds the new toggle to the node counts. */
1978       g_assert (seg->body.toggle.inNodeCounts == FALSE);
1979 #if 0
1980       printf ("added toggle at end\n");
1981 #endif
1982     }
1983
1984   /*
1985    * Cleanup cleanupline and the last line of the range, if
1986    * these are different.
1987    */
1988
1989   cleanup_line (cleanupline);
1990   if (cleanupline != end_line)
1991     {
1992       cleanup_line (end_line);
1993     }
1994
1995   segments_changed (tree);
1996
1997   queue_tag_redisplay (tree, tag, &start, &end);
1998
1999   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2000     _gtk_text_btree_check (tree);
2001 }
2002
2003
2004 /*
2005  * "Getters"
2006  */
2007
2008 static GtkTextLine*
2009 get_line_internal (GtkTextBTree *tree,
2010                    gint          line_number,
2011                    gint         *real_line_number,
2012                    gboolean      include_last)
2013 {
2014   GtkTextBTreeNode *node;
2015   GtkTextLine *line;
2016   int lines_left;
2017   int line_count;
2018
2019   line_count = _gtk_text_btree_line_count (tree);
2020   if (!include_last)
2021     line_count -= 1;
2022
2023   if (line_number < 0)
2024     {
2025       line_number = line_count;
2026     }
2027   else if (line_number > line_count)
2028     {
2029       line_number = line_count;
2030     }
2031
2032   if (real_line_number)
2033     *real_line_number = line_number;
2034
2035   node = tree->root_node;
2036   lines_left = line_number;
2037
2038   /*
2039    * Work down through levels of the tree until a GtkTextBTreeNode is found at
2040    * level 0.
2041    */
2042
2043   while (node->level != 0)
2044     {
2045       for (node = node->children.node;
2046            node->num_lines <= lines_left;
2047            node = node->next)
2048         {
2049 #if 0
2050           if (node == NULL)
2051             {
2052               g_error ("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
2053             }
2054 #endif
2055           lines_left -= node->num_lines;
2056         }
2057     }
2058
2059   /*
2060    * Work through the lines attached to the level-0 GtkTextBTreeNode.
2061    */
2062
2063   for (line = node->children.line; lines_left > 0;
2064        line = line->next)
2065     {
2066 #if 0
2067       if (line == NULL)
2068         {
2069           g_error ("gtk_text_btree_find_line ran out of lines");
2070         }
2071 #endif
2072       lines_left -= 1;
2073     }
2074   return line;
2075 }
2076
2077 GtkTextLine*
2078 _gtk_text_btree_get_end_iter_line (GtkTextBTree *tree)
2079 {
2080   return
2081     _gtk_text_btree_get_line (tree,
2082                               _gtk_text_btree_line_count (tree) - 1,
2083                               NULL);
2084 }
2085
2086 GtkTextLine*
2087 _gtk_text_btree_get_line (GtkTextBTree *tree,
2088                           gint          line_number,
2089                           gint         *real_line_number)
2090 {
2091   return get_line_internal (tree, line_number, real_line_number, TRUE);
2092 }
2093
2094 GtkTextLine*
2095 _gtk_text_btree_get_line_no_last (GtkTextBTree      *tree,
2096                                   gint               line_number,
2097                                   gint              *real_line_number)
2098 {
2099   return get_line_internal (tree, line_number, real_line_number, FALSE);
2100 }
2101
2102 GtkTextLine*
2103 _gtk_text_btree_get_line_at_char (GtkTextBTree      *tree,
2104                                   gint               char_index,
2105                                   gint              *line_start_index,
2106                                   gint              *real_char_index)
2107 {
2108   GtkTextBTreeNode *node;
2109   GtkTextLine *line;
2110   GtkTextLineSegment *seg;
2111   int chars_left;
2112   int chars_in_line;
2113
2114   node = tree->root_node;
2115
2116   /* Clamp to valid indexes (-1 is magic for "highest index"),
2117    * node->num_chars includes the two newlines that aren't really
2118    * in the buffer.
2119    */
2120   if (char_index < 0 || char_index >= (node->num_chars - 1))
2121     {
2122       char_index = node->num_chars - 2;
2123     }
2124
2125   *real_char_index = char_index;
2126
2127   /*
2128    * Work down through levels of the tree until a GtkTextBTreeNode is found at
2129    * level 0.
2130    */
2131
2132   chars_left = char_index;
2133   while (node->level != 0)
2134     {
2135       for (node = node->children.node;
2136            chars_left >= node->num_chars;
2137            node = node->next)
2138         {
2139           chars_left -= node->num_chars;
2140
2141           g_assert (chars_left >= 0);
2142         }
2143     }
2144
2145   if (chars_left == 0)
2146     {
2147       /* Start of a line */
2148
2149       *line_start_index = char_index;
2150       return node->children.line;
2151     }
2152
2153   /*
2154    * Work through the lines attached to the level-0 GtkTextBTreeNode.
2155    */
2156
2157   chars_in_line = 0;
2158   seg = NULL;
2159   for (line = node->children.line; line != NULL; line = line->next)
2160     {
2161       seg = line->segments;
2162       while (seg != NULL)
2163         {
2164           if (chars_in_line + seg->char_count > chars_left)
2165             goto found; /* found our line/segment */
2166
2167           chars_in_line += seg->char_count;
2168
2169           seg = seg->next;
2170         }
2171
2172       chars_left -= chars_in_line;
2173
2174       chars_in_line = 0;
2175       seg = NULL;
2176     }
2177
2178  found:
2179
2180   g_assert (line != NULL); /* hosage, ran out of lines */
2181   g_assert (seg != NULL);
2182
2183   *line_start_index = char_index - chars_left;
2184   return line;
2185 }
2186
2187 GtkTextTag**
2188 _gtk_text_btree_get_tags (const GtkTextIter *iter,
2189                          gint *num_tags)
2190 {
2191   GtkTextBTreeNode *node;
2192   GtkTextLine *siblingline;
2193   GtkTextLineSegment *seg;
2194   int src, dst, index;
2195   TagInfo tagInfo;
2196   GtkTextLine *line;
2197   gint byte_index;
2198
2199 #define NUM_TAG_INFOS 10
2200
2201   line = _gtk_text_iter_get_text_line (iter);
2202   byte_index = gtk_text_iter_get_line_index (iter);
2203
2204   tagInfo.numTags = 0;
2205   tagInfo.arraySize = NUM_TAG_INFOS;
2206   tagInfo.tags = g_new (GtkTextTag*, NUM_TAG_INFOS);
2207   tagInfo.counts = g_new (int, NUM_TAG_INFOS);
2208
2209   /*
2210    * Record tag toggles within the line of indexPtr but preceding
2211    * indexPtr. Note that if this loop segfaults, your
2212    * byte_index probably points past the sum of all
2213    * seg->byte_count */
2214
2215   for (index = 0, seg = line->segments;
2216        (index + seg->byte_count) <= byte_index;
2217        index += seg->byte_count, seg = seg->next)
2218     {
2219       if ((seg->type == &gtk_text_toggle_on_type)
2220           || (seg->type == &gtk_text_toggle_off_type))
2221         {
2222           inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2223         }
2224     }
2225
2226   /*
2227    * Record toggles for tags in lines that are predecessors of
2228    * line but under the same level-0 GtkTextBTreeNode.
2229    */
2230
2231   for (siblingline = line->parent->children.line;
2232        siblingline != line;
2233        siblingline = siblingline->next)
2234     {
2235       for (seg = siblingline->segments; seg != NULL;
2236            seg = seg->next)
2237         {
2238           if ((seg->type == &gtk_text_toggle_on_type)
2239               || (seg->type == &gtk_text_toggle_off_type))
2240             {
2241               inc_count (seg->body.toggle.info->tag, 1, &tagInfo);
2242             }
2243         }
2244     }
2245
2246   /*
2247    * For each GtkTextBTreeNode in the ancestry of this line, record tag
2248    * toggles for all siblings that precede that GtkTextBTreeNode.
2249    */
2250
2251   for (node = line->parent; node->parent != NULL;
2252        node = node->parent)
2253     {
2254       GtkTextBTreeNode *siblingPtr;
2255       Summary *summary;
2256
2257       for (siblingPtr = node->parent->children.node;
2258            siblingPtr != node; siblingPtr = siblingPtr->next)
2259         {
2260           for (summary = siblingPtr->summary; summary != NULL;
2261                summary = summary->next)
2262             {
2263               if (summary->toggle_count & 1)
2264                 {
2265                   inc_count (summary->info->tag, summary->toggle_count,
2266                              &tagInfo);
2267                 }
2268             }
2269         }
2270     }
2271
2272   /*
2273    * Go through the tag information and squash out all of the tags
2274    * that have even toggle counts (these tags exist before the point
2275    * of interest, but not at the desired character itself).
2276    */
2277
2278   for (src = 0, dst = 0; src < tagInfo.numTags; src++)
2279     {
2280       if (tagInfo.counts[src] & 1)
2281         {
2282           g_assert (GTK_IS_TEXT_TAG (tagInfo.tags[src]));
2283           tagInfo.tags[dst] = tagInfo.tags[src];
2284           dst++;
2285         }
2286     }
2287
2288   *num_tags = dst;
2289   g_free (tagInfo.counts);
2290   if (dst == 0)
2291     {
2292       g_free (tagInfo.tags);
2293       return NULL;
2294     }
2295   return tagInfo.tags;
2296 }
2297
2298 static void
2299 copy_segment (GString *string,
2300               gboolean include_hidden,
2301               gboolean include_nonchars,
2302               const GtkTextIter *start,
2303               const GtkTextIter *end)
2304 {
2305   GtkTextLineSegment *end_seg;
2306   GtkTextLineSegment *seg;
2307
2308   if (gtk_text_iter_equal (start, end))
2309     return;
2310
2311   seg = _gtk_text_iter_get_indexable_segment (start);
2312   end_seg = _gtk_text_iter_get_indexable_segment (end);
2313
2314   if (seg->type == &gtk_text_char_type)
2315     {
2316       gboolean copy = TRUE;
2317       gint copy_bytes = 0;
2318       gint copy_start = 0;
2319
2320       /* Don't copy if we're invisible; segments are invisible/not
2321          as a whole, no need to check each char */
2322       if (!include_hidden &&
2323           _gtk_text_btree_char_is_invisible (start))
2324         {
2325           copy = FALSE;
2326           /* printf (" <invisible>\n"); */
2327         }
2328
2329       copy_start = _gtk_text_iter_get_segment_byte (start);
2330
2331       if (seg == end_seg)
2332         {
2333           /* End is in the same segment; need to copy fewer bytes. */
2334           gint end_byte = _gtk_text_iter_get_segment_byte (end);
2335
2336           copy_bytes = end_byte - copy_start;
2337         }
2338       else
2339         copy_bytes = seg->byte_count - copy_start;
2340
2341       g_assert (copy_bytes != 0); /* Due to iter equality check at
2342                                      front of this function. */
2343
2344       if (copy)
2345         {
2346           g_assert ((copy_start + copy_bytes) <= seg->byte_count);
2347
2348           g_string_append_len (string,
2349                                seg->body.chars + copy_start,
2350                                copy_bytes);
2351         }
2352
2353       /* printf ("  :%s\n", string->str); */
2354     }
2355   else if (seg->type == &gtk_text_pixbuf_type ||
2356            seg->type == &gtk_text_child_type)
2357     {
2358       gboolean copy = TRUE;
2359
2360       if (!include_nonchars)
2361         {
2362           copy = FALSE;
2363         }
2364       else if (!include_hidden &&
2365                _gtk_text_btree_char_is_invisible (start))
2366         {
2367           copy = FALSE;
2368         }
2369
2370       if (copy)
2371         {
2372           g_string_append_len (string,
2373                                gtk_text_unknown_char_utf8,
2374                                3);
2375
2376         }
2377     }
2378 }
2379
2380 gchar*
2381 _gtk_text_btree_get_text (const GtkTextIter *start_orig,
2382                          const GtkTextIter *end_orig,
2383                          gboolean include_hidden,
2384                          gboolean include_nonchars)
2385 {
2386   GtkTextLineSegment *seg;
2387   GtkTextLineSegment *end_seg;
2388   GString *retval;
2389   gchar *str;
2390   GtkTextIter iter;
2391   GtkTextIter start;
2392   GtkTextIter end;
2393
2394   g_return_val_if_fail (start_orig != NULL, NULL);
2395   g_return_val_if_fail (end_orig != NULL, NULL);
2396   g_return_val_if_fail (_gtk_text_iter_get_btree (start_orig) ==
2397                         _gtk_text_iter_get_btree (end_orig), NULL);
2398
2399   start = *start_orig;
2400   end = *end_orig;
2401
2402   gtk_text_iter_order (&start, &end);
2403
2404   retval = g_string_new (NULL);
2405
2406   end_seg = _gtk_text_iter_get_indexable_segment (&end);
2407   iter = start;
2408   seg = _gtk_text_iter_get_indexable_segment (&iter);
2409   while (seg != end_seg)
2410     {
2411       copy_segment (retval, include_hidden, include_nonchars,
2412                     &iter, &end);
2413
2414       _gtk_text_iter_forward_indexable_segment (&iter);
2415
2416       seg = _gtk_text_iter_get_indexable_segment (&iter);
2417     }
2418
2419   copy_segment (retval, include_hidden, include_nonchars, &iter, &end);
2420
2421   str = retval->str;
2422   g_string_free (retval, FALSE);
2423   return str;
2424 }
2425
2426 gint
2427 _gtk_text_btree_line_count (GtkTextBTree *tree)
2428 {
2429   /* Subtract bogus line at the end; we return a count
2430      of usable lines. */
2431   return tree->root_node->num_lines - 1;
2432 }
2433
2434 gint
2435 _gtk_text_btree_char_count (GtkTextBTree *tree)
2436 {
2437   /* Exclude newline in bogus last line and the
2438    * one in the last line that is after the end iterator
2439    */
2440   return tree->root_node->num_chars - 2;
2441 }
2442
2443 #define LOTSA_TAGS 1000
2444 gboolean
2445 _gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2446 {
2447   gboolean invisible = FALSE;  /* if nobody says otherwise, it's visible */
2448
2449   int deftagCnts[LOTSA_TAGS] = { 0, };
2450   int *tagCnts = deftagCnts;
2451   GtkTextTag *deftags[LOTSA_TAGS];
2452   GtkTextTag **tags = deftags;
2453   int numTags;
2454   GtkTextBTreeNode *node;
2455   GtkTextLine *siblingline;
2456   GtkTextLineSegment *seg;
2457   GtkTextTag *tag;
2458   int i, index;
2459   GtkTextLine *line;
2460   GtkTextBTree *tree;
2461   gint byte_index;
2462
2463   line = _gtk_text_iter_get_text_line (iter);
2464   tree = _gtk_text_iter_get_btree (iter);
2465   byte_index = gtk_text_iter_get_line_index (iter);
2466
2467   numTags = gtk_text_tag_table_get_size (tree->table);
2468
2469   /* almost always avoid malloc, so stay out of system calls */
2470   if (LOTSA_TAGS < numTags)
2471     {
2472       tagCnts = g_new0 (int, numTags);
2473       tags = g_new (GtkTextTag*, numTags);
2474     }
2475
2476   /*
2477    * Record tag toggles within the line of indexPtr but preceding
2478    * indexPtr.
2479    */
2480
2481   for (index = 0, seg = line->segments;
2482        (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2483        index += seg->byte_count, seg = seg->next)
2484     {
2485       if ((seg->type == &gtk_text_toggle_on_type)
2486           || (seg->type == &gtk_text_toggle_off_type))
2487         {
2488           tag = seg->body.toggle.info->tag;
2489           if (tag->invisible_set && tag->values->invisible)
2490             {
2491               tags[tag->priority] = tag;
2492               tagCnts[tag->priority]++;
2493             }
2494         }
2495     }
2496
2497   /*
2498    * Record toggles for tags in lines that are predecessors of
2499    * line but under the same level-0 GtkTextBTreeNode.
2500    */
2501
2502   for (siblingline = line->parent->children.line;
2503        siblingline != line;
2504        siblingline = siblingline->next)
2505     {
2506       for (seg = siblingline->segments; seg != NULL;
2507            seg = seg->next)
2508         {
2509           if ((seg->type == &gtk_text_toggle_on_type)
2510               || (seg->type == &gtk_text_toggle_off_type))
2511             {
2512               tag = seg->body.toggle.info->tag;
2513               if (tag->invisible_set && tag->values->invisible)
2514                 {
2515                   tags[tag->priority] = tag;
2516                   tagCnts[tag->priority]++;
2517                 }
2518             }
2519         }
2520     }
2521
2522   /*
2523    * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2524    * for all siblings that precede that GtkTextBTreeNode.
2525    */
2526
2527   for (node = line->parent; node->parent != NULL;
2528        node = node->parent)
2529     {
2530       GtkTextBTreeNode *siblingPtr;
2531       Summary *summary;
2532
2533       for (siblingPtr = node->parent->children.node;
2534            siblingPtr != node; siblingPtr = siblingPtr->next)
2535         {
2536           for (summary = siblingPtr->summary; summary != NULL;
2537                summary = summary->next)
2538             {
2539               if (summary->toggle_count & 1)
2540                 {
2541                   tag = summary->info->tag;
2542                   if (tag->invisible_set && tag->values->invisible)
2543                     {
2544                       tags[tag->priority] = tag;
2545                       tagCnts[tag->priority] += summary->toggle_count;
2546                     }
2547                 }
2548             }
2549         }
2550     }
2551
2552   /*
2553    * Now traverse from highest priority to lowest,
2554    * take invisible value from first odd count (= on)
2555    */
2556
2557   for (i = numTags-1; i >=0; i--)
2558     {
2559       if (tagCnts[i] & 1)
2560         {
2561           /* FIXME not sure this should be if 0 */
2562 #if 0
2563 #ifndef ALWAYS_SHOW_SELECTION
2564           /* who would make the selection invisible? */
2565           if ((tag == tkxt->seltag)
2566               && !(tkxt->flags & GOT_FOCUS))
2567             {
2568               continue;
2569             }
2570 #endif
2571 #endif
2572           invisible = tags[i]->values->invisible;
2573           break;
2574         }
2575     }
2576
2577   if (LOTSA_TAGS < numTags)
2578     {
2579       g_free (tagCnts);
2580       g_free (tags);
2581     }
2582
2583   return invisible;
2584 }
2585
2586
2587 /*
2588  * Manipulate marks
2589  */
2590
2591 static void
2592 redisplay_region (GtkTextBTree      *tree,
2593                   const GtkTextIter *start,
2594                   const GtkTextIter *end)
2595 {
2596   BTreeView *view;
2597   GtkTextLine *start_line, *end_line;
2598
2599   if (gtk_text_iter_compare (start, end) > 0)
2600     {
2601       const GtkTextIter *tmp = start;
2602       start = end;
2603       end = tmp;
2604     }
2605
2606   start_line = _gtk_text_iter_get_text_line (start);
2607   end_line = _gtk_text_iter_get_text_line (end);
2608
2609   view = tree->views;
2610   while (view != NULL)
2611     {
2612       gint start_y, end_y;
2613       GtkTextLineData *ld;
2614
2615       start_y = _gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2616
2617       if (end_line == start_line)
2618         end_y = start_y;
2619       else
2620         end_y = _gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2621
2622       ld = _gtk_text_line_get_data (end_line, view->view_id);
2623       if (ld)
2624         end_y += ld->height;
2625
2626       gtk_text_layout_changed (view->layout, start_y,
2627                                end_y - start_y,
2628                                end_y - start_y);
2629
2630       view = view->next;
2631     }
2632 }
2633
2634 static void
2635 redisplay_mark (GtkTextLineSegment *mark)
2636 {
2637   GtkTextIter iter;
2638   GtkTextIter end;
2639
2640   _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2641                                    &iter,
2642                                    mark->body.mark.obj);
2643
2644   end = iter;
2645   gtk_text_iter_forward_char (&end);
2646
2647   DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2648   _gtk_text_btree_invalidate_region (mark->body.mark.tree,
2649                                     &iter, &end);
2650 }
2651
2652 static void
2653 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2654 {
2655   if (!mark->body.mark.visible)
2656     return;
2657   else
2658     redisplay_mark (mark);
2659 }
2660
2661 static void
2662 ensure_not_off_end (GtkTextBTree *tree,
2663                     GtkTextLineSegment *mark,
2664                     GtkTextIter *iter)
2665 {
2666   if (gtk_text_iter_get_line (iter) ==
2667       _gtk_text_btree_line_count (tree))
2668     gtk_text_iter_backward_char (iter);
2669 }
2670
2671 static GtkTextLineSegment*
2672 real_set_mark (GtkTextBTree      *tree,
2673                GtkTextMark       *existing_mark,
2674                const gchar       *name,
2675                gboolean           left_gravity,
2676                const GtkTextIter *where,
2677                gboolean           should_exist,
2678                gboolean           redraw_selections)
2679 {
2680   GtkTextLineSegment *mark;
2681   GtkTextIter iter;
2682
2683   g_return_val_if_fail (tree != NULL, NULL);
2684   g_return_val_if_fail (where != NULL, NULL);
2685   g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2686
2687   if (existing_mark)
2688     mark = existing_mark->segment;
2689   else if (name != NULL)
2690     mark = g_hash_table_lookup (tree->mark_table,
2691                                 name);
2692   else
2693     mark = NULL;
2694
2695   if (should_exist && mark == NULL)
2696     {
2697       g_warning ("No mark `%s' exists!", name);
2698       return NULL;
2699     }
2700
2701   /* OK if !should_exist and it does already exist, in that case
2702    * we just move it.
2703    */
2704
2705   iter = *where;
2706
2707   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2708     _gtk_text_iter_check (&iter);
2709
2710   if (mark != NULL)
2711     {
2712       if (redraw_selections &&
2713           (mark == tree->insert_mark->segment ||
2714            mark == tree->selection_bound_mark->segment))
2715         {
2716           GtkTextIter old_pos;
2717
2718           _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2719                                            mark->body.mark.obj);
2720           redisplay_region (tree, &old_pos, where);
2721         }
2722
2723       /*
2724        * don't let visible marks be after the final newline of the
2725        *  file.
2726        */
2727
2728       if (mark->body.mark.visible)
2729         {
2730           ensure_not_off_end (tree, mark, &iter);
2731         }
2732
2733       /* Redraw the mark's old location. */
2734       redisplay_mark_if_visible (mark);
2735
2736       /* Unlink mark from its current location.
2737          This could hose our iterator... */
2738       gtk_text_btree_unlink_segment (tree, mark,
2739                                      mark->body.mark.line);
2740       mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2741       g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2742
2743       segments_changed (tree); /* make sure the iterator recomputes its
2744                                   segment */
2745     }
2746   else
2747     {
2748       mark = _gtk_mark_segment_new (tree,
2749                                     left_gravity,
2750                                     name);
2751
2752       mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2753
2754       if (mark->body.mark.name)
2755         g_hash_table_insert (tree->mark_table,
2756                              mark->body.mark.name,
2757                              mark);
2758     }
2759
2760   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2761     _gtk_text_iter_check (&iter);
2762
2763   /* Link mark into new location */
2764   gtk_text_btree_link_segment (mark, &iter);
2765
2766   /* Invalidate some iterators. */
2767   segments_changed (tree);
2768
2769   /*
2770    * update the screen at the mark's new location.
2771    */
2772
2773   redisplay_mark_if_visible (mark);
2774
2775   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2776     _gtk_text_iter_check (&iter);
2777
2778   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2779     _gtk_text_btree_check (tree);
2780
2781   return mark;
2782 }
2783
2784
2785 GtkTextMark*
2786 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2787                          GtkTextMark  *existing_mark,
2788                          const gchar *name,
2789                          gboolean left_gravity,
2790                          const GtkTextIter *iter,
2791                          gboolean should_exist)
2792 {
2793   GtkTextLineSegment *seg;
2794
2795   seg = real_set_mark (tree, existing_mark,
2796                        name, left_gravity, iter, should_exist,
2797                        TRUE);
2798
2799   return seg ? seg->body.mark.obj : NULL;
2800 }
2801
2802 gboolean
2803 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2804                                      GtkTextIter  *start,
2805                                      GtkTextIter  *end)
2806 {
2807   GtkTextIter tmp_start, tmp_end;
2808
2809   _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2810                                    tree->insert_mark);
2811   _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2812                                    tree->selection_bound_mark);
2813
2814   if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2815     {
2816       if (start)
2817         *start = tmp_start;
2818
2819       if (end)
2820         *end = tmp_end;
2821
2822       return FALSE;
2823     }
2824   else
2825     {
2826       gtk_text_iter_order (&tmp_start, &tmp_end);
2827
2828       if (start)
2829         *start = tmp_start;
2830
2831       if (end)
2832         *end = tmp_end;
2833
2834       return TRUE;
2835     }
2836 }
2837
2838 void
2839 _gtk_text_btree_place_cursor (GtkTextBTree      *tree,
2840                              const GtkTextIter *iter)
2841 {
2842   _gtk_text_btree_select_range (tree, iter, iter);
2843 }
2844
2845 void
2846 _gtk_text_btree_select_range (GtkTextBTree      *tree,
2847                               const GtkTextIter *ins,
2848                               const GtkTextIter *bound)
2849 {
2850   GtkTextIter start, end;
2851
2852   if (_gtk_text_btree_get_selection_bounds (tree, &start, &end))
2853     redisplay_region (tree, &start, &end);
2854
2855   /* Move insert AND selection_bound before we redisplay */
2856   real_set_mark (tree, tree->insert_mark,
2857                  "insert", FALSE, ins, TRUE, FALSE);
2858   real_set_mark (tree, tree->selection_bound_mark,
2859                  "selection_bound", FALSE, bound, TRUE, FALSE);
2860
2861   redisplay_region (tree, ins, bound);
2862 }
2863
2864
2865 void
2866 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2867                                     const gchar *name)
2868 {
2869   GtkTextMark *mark;
2870
2871   g_return_if_fail (tree != NULL);
2872   g_return_if_fail (name != NULL);
2873
2874   mark = g_hash_table_lookup (tree->mark_table,
2875                               name);
2876
2877   _gtk_text_btree_remove_mark (tree, mark);
2878 }
2879
2880 void
2881 _gtk_text_btree_release_mark_segment (GtkTextBTree       *tree,
2882                                       GtkTextLineSegment *segment)
2883 {
2884
2885   if (segment->body.mark.name)
2886     g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2887
2888   segment->body.mark.tree = NULL;
2889   segment->body.mark.line = NULL;
2890
2891   /* Remove the ref on the mark, which frees segment as a side effect
2892    * if this is the last reference.
2893    */
2894   g_object_unref (segment->body.mark.obj);
2895 }
2896
2897 void
2898 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2899                              GtkTextMark *mark)
2900 {
2901   GtkTextLineSegment *segment;
2902
2903   g_return_if_fail (mark != NULL);
2904   g_return_if_fail (tree != NULL);
2905
2906   segment = mark->segment;
2907
2908   if (segment->body.mark.not_deleteable)
2909     {
2910       g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2911       return;
2912     }
2913
2914   /* This calls cleanup_line and segments_changed */
2915   gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2916
2917   _gtk_text_btree_release_mark_segment (tree, segment);
2918 }
2919
2920 gboolean
2921 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2922                                 GtkTextMark *segment)
2923 {
2924   return segment == tree->insert_mark;
2925 }
2926
2927 gboolean
2928 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2929                                          GtkTextMark *segment)
2930 {
2931   return segment == tree->selection_bound_mark;
2932 }
2933
2934 GtkTextMark*
2935 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2936                                   const gchar *name)
2937 {
2938   GtkTextLineSegment *seg;
2939
2940   g_return_val_if_fail (tree != NULL, NULL);
2941   g_return_val_if_fail (name != NULL, NULL);
2942
2943   seg = g_hash_table_lookup (tree->mark_table, name);
2944
2945   return seg ? seg->body.mark.obj : NULL;
2946 }
2947
2948 /**
2949  * gtk_text_mark_set_visible:
2950  * @mark: a #GtkTextMark
2951  * @setting: visibility of mark
2952  *
2953  * Sets the visibility of @mark; the insertion point is normally
2954  * visible, i.e. you can see it as a vertical bar. Also, the text
2955  * widget uses a visible mark to indicate where a drop will occur when
2956  * dragging-and-dropping text. Most other marks are not visible.
2957  * Marks are not visible by default.
2958  *
2959  **/
2960 void
2961 gtk_text_mark_set_visible (GtkTextMark       *mark,
2962                            gboolean           setting)
2963 {
2964   GtkTextLineSegment *seg;
2965
2966   g_return_if_fail (mark != NULL);
2967
2968   seg = mark->segment;
2969
2970   if (seg->body.mark.visible == setting)
2971     return;
2972   else
2973     {
2974       seg->body.mark.visible = setting;
2975
2976       redisplay_mark (seg);
2977     }
2978 }
2979
2980 GtkTextLine*
2981 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2982                                         GtkTextTag *tag)
2983 {
2984   GtkTextBTreeNode *node;
2985   GtkTextTagInfo *info;
2986
2987   g_return_val_if_fail (tree != NULL, NULL);
2988
2989   if (tag != NULL)
2990     {
2991       info = gtk_text_btree_get_existing_tag_info (tree, tag);
2992
2993       if (info == NULL)
2994         return NULL;
2995
2996       if (info->tag_root == NULL)
2997         return NULL;
2998
2999       node = info->tag_root;
3000
3001       /* We know the tag root has instances of the given
3002          tag below it */
3003
3004     continue_outer_loop:
3005       g_assert (node != NULL);
3006       while (node->level > 0)
3007         {
3008           g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3009           node = node->children.node;
3010           while (node != NULL)
3011             {
3012               if (gtk_text_btree_node_has_tag (node, tag))
3013                 goto continue_outer_loop;
3014
3015               node = node->next;
3016             }
3017           g_assert (node != NULL);
3018         }
3019
3020       g_assert (node != NULL); /* The tag summaries said some node had
3021                                   tag toggles... */
3022
3023       g_assert (node->level == 0);
3024
3025       return node->children.line;
3026     }
3027   else
3028     {
3029       /* Looking for any tag at all (tag == NULL).
3030          Unfortunately this can't be done in a simple and efficient way
3031          right now; so I'm just going to return the
3032          first line in the btree. FIXME */
3033       return _gtk_text_btree_get_line (tree, 0, NULL);
3034     }
3035 }
3036
3037 GtkTextLine*
3038 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3039                                        GtkTextTag *tag)
3040 {
3041   GtkTextBTreeNode *node;
3042   GtkTextBTreeNode *last_node;
3043   GtkTextLine *line;
3044   GtkTextTagInfo *info;
3045
3046   g_return_val_if_fail (tree != NULL, NULL);
3047
3048   if (tag != NULL)
3049     {
3050       info = gtk_text_btree_get_existing_tag_info (tree, tag);
3051
3052       if (info->tag_root == NULL)
3053         return NULL;
3054
3055       node = info->tag_root;
3056       /* We know the tag root has instances of the given
3057          tag below it */
3058
3059       while (node->level > 0)
3060         {
3061           g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3062           last_node = NULL;
3063           node = node->children.node;
3064           while (node != NULL)
3065             {
3066               if (gtk_text_btree_node_has_tag (node, tag))
3067                 last_node = node;
3068               node = node->next;
3069             }
3070
3071           node = last_node;
3072         }
3073
3074       g_assert (node != NULL); /* The tag summaries said some node had
3075                                   tag toggles... */
3076
3077       g_assert (node->level == 0);
3078
3079       /* Find the last line in this node */
3080       line = node->children.line;
3081       while (line->next != NULL)
3082         line = line->next;
3083
3084       return line;
3085     }
3086   else
3087     {
3088       /* This search can't be done efficiently at the moment,
3089          at least not without complexity.
3090          So, we just return the last line.
3091       */
3092       return _gtk_text_btree_get_end_iter_line (tree);
3093     }
3094 }
3095
3096
3097 /*
3098  * Lines
3099  */
3100
3101 gint
3102 _gtk_text_line_get_number (GtkTextLine *line)
3103 {
3104   GtkTextLine *line2;
3105   GtkTextBTreeNode *node, *parent, *node2;
3106   int index;
3107
3108   /*
3109    * First count how many lines precede this one in its level-0
3110    * GtkTextBTreeNode.
3111    */
3112
3113   node = line->parent;
3114   index = 0;
3115   for (line2 = node->children.line; line2 != line;
3116        line2 = line2->next)
3117     {
3118       if (line2 == NULL)
3119         {
3120           g_error ("gtk_text_btree_line_number couldn't find line");
3121         }
3122       index += 1;
3123     }
3124
3125   /*
3126    * Now work up through the levels of the tree one at a time,
3127    * counting how many lines are in GtkTextBTreeNodes preceding the current
3128    * GtkTextBTreeNode.
3129    */
3130
3131   for (parent = node->parent ; parent != NULL;
3132        node = parent, parent = parent->parent)
3133     {
3134       for (node2 = parent->children.node; node2 != node;
3135            node2 = node2->next)
3136         {
3137           if (node2 == NULL)
3138             {
3139               g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3140             }
3141           index += node2->num_lines;
3142         }
3143     }
3144   return index;
3145 }
3146
3147 static GtkTextLineSegment*
3148 find_toggle_segment_before_char (GtkTextLine *line,
3149                                  gint char_in_line,
3150                                  GtkTextTag *tag)
3151 {
3152   GtkTextLineSegment *seg;
3153   GtkTextLineSegment *toggle_seg;
3154   int index;
3155
3156   toggle_seg = NULL;
3157   index = 0;
3158   seg = line->segments;
3159   while ( (index + seg->char_count) <= char_in_line )
3160     {
3161       if (((seg->type == &gtk_text_toggle_on_type)
3162            || (seg->type == &gtk_text_toggle_off_type))
3163           && (seg->body.toggle.info->tag == tag))
3164         toggle_seg = seg;
3165
3166       index += seg->char_count;
3167       seg = seg->next;
3168     }
3169
3170   return toggle_seg;
3171 }
3172
3173 static GtkTextLineSegment*
3174 find_toggle_segment_before_byte (GtkTextLine *line,
3175                                  gint byte_in_line,
3176                                  GtkTextTag *tag)
3177 {
3178   GtkTextLineSegment *seg;
3179   GtkTextLineSegment *toggle_seg;
3180   int index;
3181
3182   toggle_seg = NULL;
3183   index = 0;
3184   seg = line->segments;
3185   while ( (index + seg->byte_count) <= byte_in_line )
3186     {
3187       if (((seg->type == &gtk_text_toggle_on_type)
3188            || (seg->type == &gtk_text_toggle_off_type))
3189           && (seg->body.toggle.info->tag == tag))
3190         toggle_seg = seg;
3191
3192       index += seg->byte_count;
3193       seg = seg->next;
3194     }
3195
3196   return toggle_seg;
3197 }
3198
3199 static gboolean
3200 find_toggle_outside_current_line (GtkTextLine *line,
3201                                   GtkTextBTree *tree,
3202                                   GtkTextTag *tag)
3203 {
3204   GtkTextBTreeNode *node;
3205   GtkTextLine *sibling_line;
3206   GtkTextLineSegment *seg;
3207   GtkTextLineSegment *toggle_seg;
3208   int toggles;
3209   GtkTextTagInfo *info = NULL;
3210
3211   /*
3212    * No toggle in this line.  Look for toggles for the tag in lines
3213    * that are predecessors of line but under the same
3214    * level-0 GtkTextBTreeNode.
3215    */
3216   toggle_seg = NULL;
3217   sibling_line = line->parent->children.line;
3218   while (sibling_line != line)
3219     {
3220       seg = sibling_line->segments;
3221       while (seg != NULL)
3222         {
3223           if (((seg->type == &gtk_text_toggle_on_type)
3224                || (seg->type == &gtk_text_toggle_off_type))
3225               && (seg->body.toggle.info->tag == tag))
3226             toggle_seg = seg;
3227
3228           seg = seg->next;
3229         }
3230
3231       sibling_line = sibling_line->next;
3232     }
3233
3234   if (toggle_seg != NULL)
3235     return (toggle_seg->type == &gtk_text_toggle_on_type);
3236
3237   /*
3238    * No toggle in this GtkTextBTreeNode.  Scan upwards through the ancestors of
3239    * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3240    * siblings that precede that GtkTextBTreeNode.
3241    */
3242
3243   info = gtk_text_btree_get_existing_tag_info (tree, tag);
3244
3245   if (info == NULL)
3246     return FALSE;
3247
3248   toggles = 0;
3249   node = line->parent;
3250   while (node->parent != NULL)
3251     {
3252       GtkTextBTreeNode *sibling_node;
3253
3254       sibling_node = node->parent->children.node;
3255       while (sibling_node != node)
3256         {
3257           Summary *summary;
3258
3259           summary = sibling_node->summary;
3260           while (summary != NULL)
3261             {
3262               if (summary->info == info)
3263                 toggles += summary->toggle_count;
3264
3265               summary = summary->next;
3266             }
3267
3268           sibling_node = sibling_node->next;
3269         }
3270
3271       if (node == info->tag_root)
3272         break;
3273
3274       node = node->parent;
3275     }
3276
3277   /*
3278    * An odd number of toggles means that the tag is present at the
3279    * given point.
3280    */
3281
3282   return (toggles & 1) != 0;
3283 }
3284
3285 /* FIXME this function is far too slow, for no good reason. */
3286 gboolean
3287 _gtk_text_line_char_has_tag (GtkTextLine *line,
3288                              GtkTextBTree *tree,
3289                              gint char_in_line,
3290                              GtkTextTag *tag)
3291 {
3292   GtkTextLineSegment *toggle_seg;
3293
3294   g_return_val_if_fail (line != NULL, FALSE);
3295
3296   /*
3297    * Check for toggles for the tag in the line but before
3298    * the char.  If there is one, its type indicates whether or
3299    * not the character is tagged.
3300    */
3301
3302   toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3303
3304   if (toggle_seg != NULL)
3305     return (toggle_seg->type == &gtk_text_toggle_on_type);
3306   else
3307     return find_toggle_outside_current_line (line, tree, tag);
3308 }
3309
3310 gboolean
3311 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3312                              GtkTextBTree *tree,
3313                              gint byte_in_line,
3314                              GtkTextTag *tag)
3315 {
3316   GtkTextLineSegment *toggle_seg;
3317
3318   g_return_val_if_fail (line != NULL, FALSE);
3319
3320   /*
3321    * Check for toggles for the tag in the line but before
3322    * the char.  If there is one, its type indicates whether or
3323    * not the character is tagged.
3324    */
3325
3326   toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3327
3328   if (toggle_seg != NULL)
3329     return (toggle_seg->type == &gtk_text_toggle_on_type);
3330   else
3331     return find_toggle_outside_current_line (line, tree, tag);
3332 }
3333
3334 gboolean
3335 _gtk_text_line_is_last (GtkTextLine *line,
3336                         GtkTextBTree *tree)
3337 {
3338   return line == get_last_line (tree);
3339 }
3340
3341 static void
3342 ensure_end_iter_line (GtkTextBTree *tree)
3343 {
3344   if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3345     {
3346       int n_lines;
3347       int real_line;
3348
3349       /* n_lines is without the magic line at the end */
3350       n_lines = _gtk_text_btree_line_count (tree);
3351
3352       g_assert (n_lines >= 1);
3353
3354       tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3355
3356       tree->end_iter_line_stamp = tree->chars_changed_stamp;
3357     }
3358 }
3359
3360 static void
3361 ensure_end_iter_segment (GtkTextBTree *tree)
3362 {
3363   if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3364     {
3365       GtkTextLineSegment *seg;
3366       GtkTextLineSegment *last_with_chars;
3367
3368       ensure_end_iter_line (tree);
3369
3370       last_with_chars = NULL;
3371
3372       seg = tree->end_iter_line->segments;
3373       while (seg != NULL)
3374         {
3375           if (seg->char_count > 0)
3376             last_with_chars = seg;
3377           seg = seg->next;
3378         }
3379
3380       tree->end_iter_segment = last_with_chars;
3381
3382       /* We know the last char in the last line is '\n' */
3383       tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3384       tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3385
3386       tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3387
3388       g_assert (tree->end_iter_segment->type == &gtk_text_char_type);
3389       g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3390     }
3391 }
3392
3393 gboolean
3394 _gtk_text_line_contains_end_iter (GtkTextLine  *line,
3395                                   GtkTextBTree *tree)
3396 {
3397   ensure_end_iter_line (tree);
3398
3399   return line == tree->end_iter_line;
3400 }
3401
3402 gboolean
3403 _gtk_text_btree_is_end (GtkTextBTree       *tree,
3404                         GtkTextLine        *line,
3405                         GtkTextLineSegment *seg,
3406                         int                 byte_index,
3407                         int                 char_offset)
3408 {
3409   g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3410
3411   /* Do this first to avoid walking segments in most cases */
3412   if (!_gtk_text_line_contains_end_iter (line, tree))
3413     return FALSE;
3414
3415   ensure_end_iter_segment (tree);
3416
3417   if (seg != tree->end_iter_segment)
3418     return FALSE;
3419
3420   if (byte_index >= 0)
3421     return byte_index == tree->end_iter_segment_byte_index;
3422   else
3423     return char_offset == tree->end_iter_segment_char_offset;
3424 }
3425
3426 GtkTextLine*
3427 _gtk_text_line_next (GtkTextLine *line)
3428 {
3429   GtkTextBTreeNode *node;
3430
3431   if (line->next != NULL)
3432     return line->next;
3433   else
3434     {
3435       /*
3436        * This was the last line associated with the particular parent
3437        * GtkTextBTreeNode.  Search up the tree for the next GtkTextBTreeNode,
3438        * then search down from that GtkTextBTreeNode to find the first
3439        * line.
3440        */
3441
3442       node = line->parent;
3443       while (node != NULL && node->next == NULL)
3444         node = node->parent;
3445
3446       if (node == NULL)
3447         return NULL;
3448
3449       node = node->next;
3450       while (node->level > 0)
3451         {
3452           node = node->children.node;
3453         }
3454
3455       g_assert (node->children.line != line);
3456
3457       return node->children.line;
3458     }
3459 }
3460
3461 GtkTextLine*
3462 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3463 {
3464   GtkTextLine *next;
3465
3466   next = _gtk_text_line_next (line);
3467
3468   /* If we were on the end iter line, we can't go to
3469    * the last line
3470    */
3471   if (next && next->next == NULL && /* these checks are optimization only */
3472       _gtk_text_line_next (next) == NULL)
3473     return NULL;
3474
3475   return next;
3476 }
3477
3478 GtkTextLine*
3479 _gtk_text_line_previous (GtkTextLine *line)
3480 {
3481   GtkTextBTreeNode *node;
3482   GtkTextBTreeNode *node2;
3483   GtkTextLine *prev;
3484
3485   /*
3486    * Find the line under this GtkTextBTreeNode just before the starting line.
3487    */
3488   prev = line->parent->children.line;        /* First line at leaf */
3489   while (prev != line)
3490     {
3491       if (prev->next == line)
3492         return prev;
3493
3494       prev = prev->next;
3495
3496       if (prev == NULL)
3497         g_error ("gtk_text_btree_previous_line ran out of lines");
3498     }
3499
3500   /*
3501    * This was the first line associated with the particular parent
3502    * GtkTextBTreeNode.  Search up the tree for the previous GtkTextBTreeNode,
3503    * then search down from that GtkTextBTreeNode to find its last line.
3504    */
3505   for (node = line->parent; ; node = node->parent)
3506     {
3507       if (node == NULL || node->parent == NULL)
3508         return NULL;
3509       else if (node != node->parent->children.node)
3510         break;
3511     }
3512
3513   for (node2 = node->parent->children.node; ;
3514        node2 = node2->children.node)
3515     {
3516       while (node2->next != node)
3517         node2 = node2->next;
3518
3519       if (node2->level == 0)
3520         break;
3521
3522       node = NULL;
3523     }
3524
3525   for (prev = node2->children.line ; ; prev = prev->next)
3526     {
3527       if (prev->next == NULL)
3528         return prev;
3529     }
3530
3531   g_assert_not_reached ();
3532   return NULL;
3533 }
3534
3535
3536 GtkTextLineData*
3537 _gtk_text_line_data_new (GtkTextLayout *layout,
3538                          GtkTextLine   *line)
3539 {
3540   GtkTextLineData *line_data;
3541
3542   line_data = g_new (GtkTextLineData, 1);
3543
3544   line_data->view_id = layout;
3545   line_data->next = NULL;
3546   line_data->width = 0;
3547   line_data->height = 0;
3548   line_data->valid = FALSE;
3549
3550   return line_data;
3551 }
3552
3553 void
3554 _gtk_text_line_add_data (GtkTextLine     *line,
3555                          GtkTextLineData *data)
3556 {
3557   g_return_if_fail (line != NULL);
3558   g_return_if_fail (data != NULL);
3559   g_return_if_fail (data->view_id != NULL);
3560
3561   if (line->views)
3562     {
3563       data->next = line->views;
3564       line->views = data;
3565     }
3566   else
3567     {
3568       line->views = data;
3569     }
3570 }
3571
3572 gpointer
3573 _gtk_text_line_remove_data (GtkTextLine *line,
3574                            gpointer view_id)
3575 {
3576   GtkTextLineData *prev;
3577   GtkTextLineData *iter;
3578
3579   g_return_val_if_fail (line != NULL, NULL);
3580   g_return_val_if_fail (view_id != NULL, NULL);
3581
3582   prev = NULL;
3583   iter = line->views;
3584   while (iter != NULL)
3585     {
3586       if (iter->view_id == view_id)
3587         break;
3588       prev = iter;
3589       iter = iter->next;
3590     }
3591
3592   if (iter)
3593     {
3594       if (prev)
3595         prev->next = iter->next;
3596       else
3597         line->views = iter->next;
3598
3599       return iter;
3600     }
3601   else
3602     return NULL;
3603 }
3604
3605 gpointer
3606 _gtk_text_line_get_data (GtkTextLine *line,
3607                          gpointer view_id)
3608 {
3609   GtkTextLineData *iter;
3610
3611   g_return_val_if_fail (line != NULL, NULL);
3612   g_return_val_if_fail (view_id != NULL, NULL);
3613
3614   iter = line->views;
3615   while (iter != NULL)
3616     {
3617       if (iter->view_id == view_id)
3618         break;
3619       iter = iter->next;
3620     }
3621
3622   return iter;
3623 }
3624
3625 void
3626 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3627                                 GtkTextLineData *ld)
3628 {
3629   /* For now this is totally unoptimized. FIXME?
3630
3631      We could probably optimize the case where the width removed
3632      is less than the max width for the parent node,
3633      and the case where the height is unchanged when we re-wrap.
3634   */
3635
3636   g_return_if_fail (ld != NULL);
3637
3638   ld->valid = FALSE;
3639   gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3640 }
3641
3642 gint
3643 _gtk_text_line_char_count (GtkTextLine *line)
3644 {
3645   GtkTextLineSegment *seg;
3646   gint size;
3647
3648   size = 0;
3649   seg = line->segments;
3650   while (seg != NULL)
3651     {
3652       size += seg->char_count;
3653       seg = seg->next;
3654     }
3655   return size;
3656 }
3657
3658 gint
3659 _gtk_text_line_byte_count (GtkTextLine *line)
3660 {
3661   GtkTextLineSegment *seg;
3662   gint size;
3663
3664   size = 0;
3665   seg = line->segments;
3666   while (seg != NULL)
3667     {
3668       size += seg->byte_count;
3669       seg = seg->next;
3670     }
3671
3672   return size;
3673 }
3674
3675 gint
3676 _gtk_text_line_char_index (GtkTextLine *target_line)
3677 {
3678   GSList *node_stack = NULL;
3679   GtkTextBTreeNode *iter;
3680   GtkTextLine *line;
3681   gint num_chars;
3682
3683   /* Push all our parent nodes onto a stack */
3684   iter = target_line->parent;
3685
3686   g_assert (iter != NULL);
3687
3688   while (iter != NULL)
3689     {
3690       node_stack = g_slist_prepend (node_stack, iter);
3691
3692       iter = iter->parent;
3693     }
3694
3695   /* Check that we have the root node on top of the stack. */
3696   g_assert (node_stack != NULL &&
3697             node_stack->data != NULL &&
3698             ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3699
3700   /* Add up chars in all nodes before the nodes in our stack.
3701    */
3702
3703   num_chars = 0;
3704   iter = node_stack->data;
3705   while (iter != NULL)
3706     {
3707       GtkTextBTreeNode *child_iter;
3708       GtkTextBTreeNode *next_node;
3709
3710       next_node = node_stack->next ?
3711         node_stack->next->data : NULL;
3712       node_stack = g_slist_remove (node_stack, node_stack->data);
3713
3714       if (iter->level == 0)
3715         {
3716           /* stack should be empty when we're on the last node */
3717           g_assert (node_stack == NULL);
3718           break; /* Our children are now lines */
3719         }
3720
3721       g_assert (next_node != NULL);
3722       g_assert (iter != NULL);
3723       g_assert (next_node->parent == iter);
3724
3725       /* Add up chars before us in the tree */
3726       child_iter = iter->children.node;
3727       while (child_iter != next_node)
3728         {
3729           g_assert (child_iter != NULL);
3730
3731           num_chars += child_iter->num_chars;
3732
3733           child_iter = child_iter->next;
3734         }
3735
3736       iter = next_node;
3737     }
3738
3739   g_assert (iter != NULL);
3740   g_assert (iter == target_line->parent);
3741
3742   /* Since we don't store char counts in lines, only in segments, we
3743      have to iterate over the lines adding up segment char counts
3744      until we find our line.  */
3745   line = iter->children.line;
3746   while (line != target_line)
3747     {
3748       g_assert (line != NULL);
3749
3750       num_chars += _gtk_text_line_char_count (line);
3751
3752       line = line->next;
3753     }
3754
3755   g_assert (line == target_line);
3756
3757   return num_chars;
3758 }
3759
3760 GtkTextLineSegment*
3761 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3762                                gint byte_offset,
3763                                gint *seg_offset)
3764 {
3765   GtkTextLineSegment *seg;
3766   int offset;
3767
3768   g_return_val_if_fail (line != NULL, NULL);
3769
3770   offset = byte_offset;
3771   seg = line->segments;
3772
3773   while (offset >= seg->byte_count)
3774     {
3775       g_assert (seg != NULL); /* means an invalid byte index */
3776       offset -= seg->byte_count;
3777       seg = seg->next;
3778     }
3779
3780   if (seg_offset)
3781     *seg_offset = offset;
3782
3783   return seg;
3784 }
3785
3786 GtkTextLineSegment*
3787 _gtk_text_line_char_to_segment (GtkTextLine *line,
3788                                gint char_offset,
3789                                gint *seg_offset)
3790 {
3791   GtkTextLineSegment *seg;
3792   int offset;
3793
3794   g_return_val_if_fail (line != NULL, NULL);
3795
3796   offset = char_offset;
3797   seg = line->segments;
3798
3799   while (offset >= seg->char_count)
3800     {
3801       g_assert (seg != NULL); /* means an invalid char index */
3802       offset -= seg->char_count;
3803       seg = seg->next;
3804     }
3805
3806   if (seg_offset)
3807     *seg_offset = offset;
3808
3809   return seg;
3810 }
3811
3812 GtkTextLineSegment*
3813 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3814                                    gint byte_offset,
3815                                    gint *seg_offset)
3816 {
3817   GtkTextLineSegment *seg;
3818   int offset;
3819
3820   g_return_val_if_fail (line != NULL, NULL);
3821
3822   offset = byte_offset;
3823   seg = line->segments;
3824
3825   while (offset > 0 && offset >= seg->byte_count)
3826     {
3827       g_assert (seg != NULL); /* means an invalid byte index */
3828       offset -= seg->byte_count;
3829       seg = seg->next;
3830     }
3831
3832   if (seg_offset)
3833     *seg_offset = offset;
3834
3835   return seg;
3836 }
3837
3838 GtkTextLineSegment*
3839 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3840                                    gint char_offset,
3841                                    gint *seg_offset)
3842 {
3843   GtkTextLineSegment *seg;
3844   int offset;
3845
3846   g_return_val_if_fail (line != NULL, NULL);
3847
3848   offset = char_offset;
3849   seg = line->segments;
3850
3851   while (offset > 0 && offset >= seg->char_count)
3852     {
3853       g_assert (seg != NULL); /* means an invalid byte index */
3854       offset -= seg->char_count;
3855       seg = seg->next;
3856     }
3857
3858   if (seg_offset)
3859     *seg_offset = offset;
3860
3861   return seg;
3862 }
3863
3864 gint
3865 _gtk_text_line_byte_to_char (GtkTextLine *line,
3866                             gint byte_offset)
3867 {
3868   gint char_offset;
3869   GtkTextLineSegment *seg;
3870
3871   g_return_val_if_fail (line != NULL, 0);
3872   g_return_val_if_fail (byte_offset >= 0, 0);
3873
3874   char_offset = 0;
3875   seg = line->segments;
3876   while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3877                                             the next segment) */
3878     {
3879       g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3880
3881       byte_offset -= seg->byte_count;
3882       char_offset += seg->char_count;
3883
3884       seg = seg->next;
3885     }
3886
3887   g_assert (seg != NULL);
3888
3889   /* Now byte_offset is the offset into the current segment,
3890      and char_offset is the start of the current segment.
3891      Optimize the case where no chars use > 1 byte */
3892   if (seg->byte_count == seg->char_count)
3893     return char_offset + byte_offset;
3894   else
3895     {
3896       if (seg->type == &gtk_text_char_type)
3897         return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3898       else
3899         {
3900           g_assert (seg->char_count == 1);
3901           g_assert (byte_offset == 0);
3902
3903           return char_offset;
3904         }
3905     }
3906 }
3907
3908 gint
3909 _gtk_text_line_char_to_byte (GtkTextLine *line,
3910                             gint         char_offset)
3911 {
3912   g_warning ("FIXME not implemented");
3913
3914   return 0;
3915 }
3916
3917 /* FIXME sync with char_locate (or figure out a clean
3918    way to merge the two functions) */
3919 gboolean
3920 _gtk_text_line_byte_locate (GtkTextLine *line,
3921                             gint byte_offset,
3922                             GtkTextLineSegment **segment,
3923                             GtkTextLineSegment **any_segment,
3924                             gint *seg_byte_offset,
3925                             gint *line_byte_offset)
3926 {
3927   GtkTextLineSegment *seg;
3928   GtkTextLineSegment *after_last_indexable;
3929   GtkTextLineSegment *last_indexable;
3930   gint offset;
3931   gint bytes_in_line;
3932
3933   g_return_val_if_fail (line != NULL, FALSE);
3934   g_return_val_if_fail (byte_offset >= 0, FALSE);
3935
3936   *segment = NULL;
3937   *any_segment = NULL;
3938   bytes_in_line = 0;
3939
3940   offset = byte_offset;
3941
3942   last_indexable = NULL;
3943   after_last_indexable = line->segments;
3944   seg = line->segments;
3945
3946   /* The loop ends when we're inside a segment;
3947      last_indexable refers to the last segment
3948      we passed entirely. */
3949   while (seg && offset >= seg->byte_count)
3950     {
3951       if (seg->char_count > 0)
3952         {
3953           offset -= seg->byte_count;
3954           bytes_in_line += seg->byte_count;
3955           last_indexable = seg;
3956           after_last_indexable = last_indexable->next;
3957         }
3958
3959       seg = seg->next;
3960     }
3961
3962   if (seg == NULL)
3963     {
3964       /* We went off the end of the line */
3965       if (offset != 0)
3966         g_warning ("%s: byte index off the end of the line", G_STRLOC);
3967
3968       return FALSE;
3969     }
3970   else
3971     {
3972       *segment = seg;
3973       if (after_last_indexable != NULL)
3974         *any_segment = after_last_indexable;
3975       else
3976         *any_segment = *segment;
3977     }
3978
3979   /* Override any_segment if we're in the middle of a segment. */
3980   if (offset > 0)
3981     *any_segment = *segment;
3982
3983   *seg_byte_offset = offset;
3984
3985   g_assert (*segment != NULL);
3986   g_assert (*any_segment != NULL);
3987   g_assert (*seg_byte_offset < (*segment)->byte_count);
3988
3989   *line_byte_offset = bytes_in_line + *seg_byte_offset;
3990
3991   return TRUE;
3992 }
3993
3994 /* FIXME sync with byte_locate (or figure out a clean
3995    way to merge the two functions) */
3996 gboolean
3997 _gtk_text_line_char_locate     (GtkTextLine     *line,
3998                                 gint              char_offset,
3999                                 GtkTextLineSegment **segment,
4000                                 GtkTextLineSegment **any_segment,
4001                                 gint             *seg_char_offset,
4002                                 gint             *line_char_offset)
4003 {
4004   GtkTextLineSegment *seg;
4005   GtkTextLineSegment *after_last_indexable;
4006   GtkTextLineSegment *last_indexable;
4007   gint offset;
4008   gint chars_in_line;
4009
4010   g_return_val_if_fail (line != NULL, FALSE);
4011   g_return_val_if_fail (char_offset >= 0, FALSE);
4012
4013   *segment = NULL;
4014   *any_segment = NULL;
4015   chars_in_line = 0;
4016
4017   offset = char_offset;
4018
4019   last_indexable = NULL;
4020   after_last_indexable = line->segments;
4021   seg = line->segments;
4022
4023   /* The loop ends when we're inside a segment;
4024      last_indexable refers to the last segment
4025      we passed entirely. */
4026   while (seg && offset >= seg->char_count)
4027     {
4028       if (seg->char_count > 0)
4029         {
4030           offset -= seg->char_count;
4031           chars_in_line += seg->char_count;
4032           last_indexable = seg;
4033           after_last_indexable = last_indexable->next;
4034         }
4035
4036       seg = seg->next;
4037     }
4038
4039   if (seg == NULL)
4040     {
4041       /* end of the line */
4042       if (offset != 0)
4043         g_warning ("%s: char offset off the end of the line", G_STRLOC);
4044
4045       return FALSE;
4046     }
4047   else
4048     {
4049       *segment = seg;
4050       if (after_last_indexable != NULL)
4051         *any_segment = after_last_indexable;
4052       else
4053         *any_segment = *segment;
4054     }
4055
4056   /* Override any_segment if we're in the middle of a segment. */
4057   if (offset > 0)
4058     *any_segment = *segment;
4059
4060   *seg_char_offset = offset;
4061
4062   g_assert (*segment != NULL);
4063   g_assert (*any_segment != NULL);
4064   g_assert (*seg_char_offset < (*segment)->char_count);
4065
4066   *line_char_offset = chars_in_line + *seg_char_offset;
4067
4068   return TRUE;
4069 }
4070
4071 void
4072 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4073                                     gint byte_offset,
4074                                     gint *line_char_offset,
4075                                     gint *seg_char_offset)
4076 {
4077   GtkTextLineSegment *seg;
4078   int offset;
4079
4080   g_return_if_fail (line != NULL);
4081   g_return_if_fail (byte_offset >= 0);
4082
4083   *line_char_offset = 0;
4084
4085   offset = byte_offset;
4086   seg = line->segments;
4087
4088   while (offset >= seg->byte_count)
4089     {
4090       offset -= seg->byte_count;
4091       *line_char_offset += seg->char_count;
4092       seg = seg->next;
4093       g_assert (seg != NULL); /* means an invalid char offset */
4094     }
4095
4096   g_assert (seg->char_count > 0); /* indexable. */
4097
4098   /* offset is now the number of bytes into the current segment we
4099    * want to go. Count chars into the current segment.
4100    */
4101
4102   if (seg->type == &gtk_text_char_type)
4103     {
4104       *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4105
4106       g_assert (*seg_char_offset < seg->char_count);
4107
4108       *line_char_offset += *seg_char_offset;
4109     }
4110   else
4111     {
4112       g_assert (offset == 0);
4113       *seg_char_offset = 0;
4114     }
4115 }
4116
4117 void
4118 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4119                                     gint char_offset,
4120                                     gint *line_byte_offset,
4121                                     gint *seg_byte_offset)
4122 {
4123   GtkTextLineSegment *seg;
4124   int offset;
4125
4126   g_return_if_fail (line != NULL);
4127   g_return_if_fail (char_offset >= 0);
4128
4129   *line_byte_offset = 0;
4130
4131   offset = char_offset;
4132   seg = line->segments;
4133
4134   while (offset >= seg->char_count)
4135     {
4136       offset -= seg->char_count;
4137       *line_byte_offset += seg->byte_count;
4138       seg = seg->next;
4139       g_assert (seg != NULL); /* means an invalid char offset */
4140     }
4141
4142   g_assert (seg->char_count > 0); /* indexable. */
4143
4144   /* offset is now the number of chars into the current segment we
4145      want to go. Count bytes into the current segment. */
4146
4147   if (seg->type == &gtk_text_char_type)
4148     {
4149       const char *p;
4150
4151       /* if in the last fourth of the segment walk backwards */
4152       if (seg->char_count - offset < seg->char_count / 4)
4153         p = g_utf8_offset_to_pointer (seg->body.chars + seg->byte_count,
4154                                       offset - seg->char_count);
4155       else
4156         p = g_utf8_offset_to_pointer (seg->body.chars, offset);
4157
4158       *seg_byte_offset = p - seg->body.chars;
4159
4160       g_assert (*seg_byte_offset < seg->byte_count);
4161
4162       *line_byte_offset += *seg_byte_offset;
4163     }
4164   else
4165     {
4166       g_assert (offset == 0);
4167       *seg_byte_offset = 0;
4168     }
4169 }
4170
4171 static gint
4172 node_compare (GtkTextBTreeNode *lhs,
4173               GtkTextBTreeNode *rhs)
4174 {
4175   GtkTextBTreeNode *iter;
4176   GtkTextBTreeNode *node;
4177   GtkTextBTreeNode *common_parent;
4178   GtkTextBTreeNode *parent_of_lower;
4179   GtkTextBTreeNode *parent_of_higher;
4180   gboolean lhs_is_lower;
4181   GtkTextBTreeNode *lower;
4182   GtkTextBTreeNode *higher;
4183
4184   /* This function assumes that lhs and rhs are not underneath each
4185    * other.
4186    */
4187
4188   if (lhs == rhs)
4189     return 0;
4190
4191   if (lhs->level < rhs->level)
4192     {
4193       lhs_is_lower = TRUE;
4194       lower = lhs;
4195       higher = rhs;
4196     }
4197   else
4198     {
4199       lhs_is_lower = FALSE;
4200       lower = rhs;
4201       higher = lhs;
4202     }
4203
4204   /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4205    * of the common parent we used to reach the common parent; the
4206    * ordering of these child nodes in the child list is the ordering
4207    * of lhs and rhs.
4208    */
4209
4210   /* Get on the same level (may be on same level already) */
4211   node = lower;
4212   while (node->level < higher->level)
4213     node = node->parent;
4214
4215   g_assert (node->level == higher->level);
4216
4217   g_assert (node != higher); /* Happens if lower is underneath higher */
4218
4219   /* Go up until we have two children with a common parent.
4220    */
4221   parent_of_lower = node;
4222   parent_of_higher = higher;
4223
4224   while (parent_of_lower->parent != parent_of_higher->parent)
4225     {
4226       parent_of_lower = parent_of_lower->parent;
4227       parent_of_higher = parent_of_higher->parent;
4228     }
4229
4230   g_assert (parent_of_lower->parent == parent_of_higher->parent);
4231
4232   common_parent = parent_of_lower->parent;
4233
4234   g_assert (common_parent != NULL);
4235
4236   /* See which is first in the list of common_parent's children */
4237   iter = common_parent->children.node;
4238   while (iter != NULL)
4239     {
4240       if (iter == parent_of_higher)
4241         {
4242           /* higher is less than lower */
4243
4244           if (lhs_is_lower)
4245             return 1; /* lhs > rhs */
4246           else
4247             return -1;
4248         }
4249       else if (iter == parent_of_lower)
4250         {
4251           /* lower is less than higher */
4252
4253           if (lhs_is_lower)
4254             return -1; /* lhs < rhs */
4255           else
4256             return 1;
4257         }
4258
4259       iter = iter->next;
4260     }
4261
4262   g_assert_not_reached ();
4263   return 0;
4264 }
4265
4266 /* remember that tag == NULL means "any tag" */
4267 GtkTextLine*
4268 _gtk_text_line_next_could_contain_tag (GtkTextLine  *line,
4269                                        GtkTextBTree *tree,
4270                                        GtkTextTag   *tag)
4271 {
4272   GtkTextBTreeNode *node;
4273   GtkTextTagInfo *info;
4274   gboolean below_tag_root;
4275
4276   g_return_val_if_fail (line != NULL, NULL);
4277
4278   if (gtk_debug_flags & GTK_DEBUG_TEXT)
4279     _gtk_text_btree_check (tree);
4280
4281   if (tag == NULL)
4282     {
4283       /* Right now we can only offer linear-search if the user wants
4284        * to know about any tag toggle at all.
4285        */
4286       return _gtk_text_line_next_excluding_last (line);
4287     }
4288
4289   /* Our tag summaries only have node precision, not line
4290    * precision. This means that if any line under a node could contain a
4291    * tag, then any of the others could also contain a tag.
4292    *
4293    * In the future we could have some mechanism to keep track of how
4294    * many toggles we've found under a node so far, since we have a
4295    * count of toggles under the node. But for now I'm going with KISS.
4296    */
4297
4298   /* return same-node line, if any. */
4299   if (line->next)
4300     return line->next;
4301
4302   info = gtk_text_btree_get_existing_tag_info (tree, tag);
4303   if (info == NULL)
4304     return NULL;
4305
4306   if (info->tag_root == NULL)
4307     return NULL;
4308
4309   if (info->tag_root == line->parent)
4310     return NULL; /* we were at the last line under the tag root */
4311
4312   /* We need to go up out of this node, and on to the next one with
4313      toggles for the target tag. If we're below the tag root, we need to
4314      find the next node below the tag root that has tag summaries. If
4315      we're not below the tag root, we need to see if the tag root is
4316      after us in the tree, and if so, return the first line underneath
4317      the tag root. */
4318
4319   node = line->parent;
4320   below_tag_root = FALSE;
4321   while (node != NULL)
4322     {
4323       if (node == info->tag_root)
4324         {
4325           below_tag_root = TRUE;
4326           break;
4327         }
4328
4329       node = node->parent;
4330     }
4331
4332   if (below_tag_root)
4333     {
4334       node = line->parent;
4335       while (node != info->tag_root)
4336         {
4337           if (node->next == NULL)
4338             node = node->parent;
4339           else
4340             {
4341               node = node->next;
4342
4343               if (gtk_text_btree_node_has_tag (node, tag))
4344                 goto found;
4345             }
4346         }
4347       return NULL;
4348     }
4349   else
4350     {
4351       gint ordering;
4352
4353       ordering = node_compare (line->parent, info->tag_root);
4354
4355       if (ordering < 0)
4356         {
4357           /* Tag root is ahead of us, so search there. */
4358           node = info->tag_root;
4359           goto found;
4360         }
4361       else
4362         {
4363           /* Tag root is after us, so no more lines that
4364            * could contain the tag.
4365            */
4366           return NULL;
4367         }
4368
4369       g_assert_not_reached ();
4370     }
4371
4372  found:
4373
4374   g_assert (node != NULL);
4375
4376   /* We have to find the first sub-node of this node that contains
4377    * the target tag.
4378    */
4379
4380   while (node->level > 0)
4381     {
4382       g_assert (node != NULL); /* If this fails, it likely means an
4383                                   incorrect tag summary led us on a
4384                                   wild goose chase down this branch of
4385                                   the tree. */
4386       node = node->children.node;
4387       while (node != NULL)
4388         {
4389           if (gtk_text_btree_node_has_tag (node, tag))
4390             break;
4391           node = node->next;
4392         }
4393     }
4394
4395   g_assert (node != NULL);
4396   g_assert (node->level == 0);
4397
4398   return node->children.line;
4399 }
4400
4401 static GtkTextLine*
4402 prev_line_under_node (GtkTextBTreeNode *node,
4403                       GtkTextLine      *line)
4404 {
4405   GtkTextLine *prev;
4406
4407   prev = node->children.line;
4408
4409   g_assert (prev);
4410
4411   if (prev != line)
4412     {
4413       while (prev->next != line)
4414         prev = prev->next;
4415
4416       return prev;
4417     }
4418
4419   return NULL;
4420 }
4421
4422 GtkTextLine*
4423 _gtk_text_line_previous_could_contain_tag (GtkTextLine  *line,
4424                                           GtkTextBTree *tree,
4425                                           GtkTextTag   *tag)
4426 {
4427   GtkTextBTreeNode *node;
4428   GtkTextBTreeNode *found_node = NULL;
4429   GtkTextTagInfo *info;
4430   gboolean below_tag_root;
4431   GtkTextLine *prev;
4432   GtkTextBTreeNode *line_ancestor;
4433   GtkTextBTreeNode *line_ancestor_parent;
4434
4435   /* See next_could_contain_tag () for more extensive comments
4436    * on what's going on here.
4437    */
4438
4439   g_return_val_if_fail (line != NULL, NULL);
4440
4441   if (gtk_debug_flags & GTK_DEBUG_TEXT)
4442     _gtk_text_btree_check (tree);
4443
4444   if (tag == NULL)
4445     {
4446       /* Right now we can only offer linear-search if the user wants
4447        * to know about any tag toggle at all.
4448        */
4449       return _gtk_text_line_previous (line);
4450     }
4451
4452   /* Return same-node line, if any. */
4453   prev = prev_line_under_node (line->parent, line);
4454   if (prev)
4455     return prev;
4456
4457   info = gtk_text_btree_get_existing_tag_info (tree, tag);
4458   if (info == NULL)
4459     return NULL;
4460
4461   if (info->tag_root == NULL)
4462     return NULL;
4463
4464   if (info->tag_root == line->parent)
4465     return NULL; /* we were at the first line under the tag root */
4466
4467   /* Are we below the tag root */
4468   node = line->parent;
4469   below_tag_root = FALSE;
4470   while (node != NULL)
4471     {
4472       if (node == info->tag_root)
4473         {
4474           below_tag_root = TRUE;
4475           break;
4476         }
4477
4478       node = node->parent;
4479     }
4480
4481   if (below_tag_root)
4482     {
4483       /* Look for a previous node under this tag root that has our
4484        * tag.
4485        */
4486
4487       /* this assertion holds because line->parent is not the
4488        * tag root, we are below the tag root, and the tag
4489        * root exists.
4490        */
4491       g_assert (line->parent->parent != NULL);
4492
4493       line_ancestor = line->parent;
4494       line_ancestor_parent = line->parent->parent;
4495
4496       while (line_ancestor != info->tag_root)
4497         {
4498           GSList *child_nodes = NULL;
4499           GSList *tmp;
4500
4501           /* Create reverse-order list of nodes before
4502            * line_ancestor
4503            */
4504           if (line_ancestor_parent != NULL)
4505             node = line_ancestor_parent->children.node;
4506           else
4507             node = line_ancestor;
4508
4509           while (node != line_ancestor && node != NULL)
4510             {
4511               child_nodes = g_slist_prepend (child_nodes, node);
4512
4513               node = node->next;
4514             }
4515
4516           /* Try to find a node with our tag on it in the list */
4517           tmp = child_nodes;
4518           while (tmp != NULL)
4519             {
4520               GtkTextBTreeNode *this_node = tmp->data;
4521
4522               g_assert (this_node != line_ancestor);
4523
4524               if (gtk_text_btree_node_has_tag (this_node, tag))
4525                 {
4526                   found_node = this_node;
4527                   g_slist_free (child_nodes);
4528                   goto found;
4529                 }
4530
4531               tmp = g_slist_next (tmp);
4532             }
4533
4534           g_slist_free (child_nodes);
4535
4536           /* Didn't find anything on this level; go up one level. */
4537           line_ancestor = line_ancestor_parent;
4538           line_ancestor_parent = line_ancestor->parent;
4539         }
4540
4541       /* No dice. */
4542       return NULL;
4543     }
4544   else
4545     {
4546       gint ordering;
4547
4548       ordering = node_compare (line->parent, info->tag_root);
4549
4550       if (ordering < 0)
4551         {
4552           /* Tag root is ahead of us, so no more lines
4553            * with this tag.
4554            */
4555           return NULL;
4556         }
4557       else
4558         {
4559           /* Tag root is after us, so grab last tagged
4560            * line underneath the tag root.
4561            */
4562           found_node = info->tag_root;
4563           goto found;
4564         }
4565
4566       g_assert_not_reached ();
4567     }
4568
4569  found:
4570
4571   g_assert (found_node != NULL);
4572
4573   /* We have to find the last sub-node of this node that contains
4574    * the target tag.
4575    */
4576   node = found_node;
4577
4578   while (node->level > 0)
4579     {
4580       GSList *child_nodes = NULL;
4581       GSList *iter;
4582       g_assert (node != NULL); /* If this fails, it likely means an
4583                                   incorrect tag summary led us on a
4584                                   wild goose chase down this branch of
4585                                   the tree. */
4586
4587       node = node->children.node;
4588       while (node != NULL)
4589         {
4590           child_nodes = g_slist_prepend (child_nodes, node);
4591           node = node->next;
4592         }
4593
4594       node = NULL; /* detect failure to find a child node. */
4595
4596       iter = child_nodes;
4597       while (iter != NULL)
4598         {
4599           if (gtk_text_btree_node_has_tag (iter->data, tag))
4600             {
4601               /* recurse into this node. */
4602               node = iter->data;
4603               break;
4604             }
4605
4606           iter = g_slist_next (iter);
4607         }
4608
4609       g_slist_free (child_nodes);
4610
4611       g_assert (node != NULL);
4612     }
4613
4614   g_assert (node != NULL);
4615   g_assert (node->level == 0);
4616
4617   /* this assertion is correct, but slow. */
4618   /* g_assert (node_compare (node, line->parent) < 0); */
4619
4620   /* Return last line in this node. */
4621
4622   prev = node->children.line;
4623   while (prev->next)
4624     prev = prev->next;
4625
4626   return prev;
4627 }
4628
4629 /*
4630  * Non-public function implementations
4631  */
4632
4633 static void
4634 summary_list_destroy (Summary *summary)
4635 {
4636   g_slice_free_chain (Summary, summary, next);
4637 }
4638
4639 static GtkTextLine*
4640 get_last_line (GtkTextBTree *tree)
4641 {
4642   if (tree->last_line_stamp != tree->chars_changed_stamp)
4643     {
4644       gint n_lines;
4645       GtkTextLine *line;
4646       gint real_line;
4647
4648       n_lines = _gtk_text_btree_line_count (tree);
4649
4650       g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4651
4652       line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4653
4654       tree->last_line_stamp = tree->chars_changed_stamp;
4655       tree->last_line = line;
4656     }
4657
4658   return tree->last_line;
4659 }
4660
4661 /*
4662  * Lines
4663  */
4664
4665 static GtkTextLine*
4666 gtk_text_line_new (void)
4667 {
4668   GtkTextLine *line;
4669
4670   line = g_new0(GtkTextLine, 1);
4671   line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4672   line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4673   line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4674
4675   return line;
4676 }
4677
4678 static void
4679 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4680 {
4681   GtkTextLineData *ld;
4682   GtkTextLineData *next;
4683
4684   g_return_if_fail (line != NULL);
4685
4686   ld = line->views;
4687   while (ld != NULL)
4688     {
4689       BTreeView *view;
4690
4691       view = gtk_text_btree_get_view (tree, ld->view_id);
4692
4693       g_assert (view != NULL);
4694
4695       next = ld->next;
4696       gtk_text_layout_free_line_data (view->layout, line, ld);
4697
4698       ld = next;
4699     }
4700
4701   g_free (line);
4702 }
4703
4704 static void
4705 gtk_text_line_set_parent (GtkTextLine *line,
4706                           GtkTextBTreeNode *node)
4707 {
4708   if (line->parent == node)
4709     return;
4710   line->parent = node;
4711   gtk_text_btree_node_invalidate_upward (node, NULL);
4712 }
4713
4714 static void
4715 cleanup_line (GtkTextLine *line)
4716 {
4717   GtkTextLineSegment *seg, **prev_p;
4718   gboolean changed;
4719
4720   /*
4721    * Make a pass over all of the segments in the line, giving each
4722    * a chance to clean itself up.  This could potentially change
4723    * the structure of the line, e.g. by merging two segments
4724    * together or having two segments cancel themselves;  if so,
4725    * then repeat the whole process again, since the first structure
4726    * change might make other structure changes possible.  Repeat
4727    * until eventually there are no changes.
4728    */
4729
4730   changed = TRUE;
4731   while (changed)
4732     {
4733       changed = FALSE;
4734       prev_p = &line->segments;
4735       for (seg = *prev_p; seg != NULL; seg = *prev_p)
4736         {
4737           if (seg->type->cleanupFunc != NULL)
4738             {
4739               *prev_p = (*seg->type->cleanupFunc)(seg, line);
4740               if (seg != *prev_p)
4741                 {
4742                   changed = TRUE;
4743                   continue;
4744                 }
4745             }
4746
4747           prev_p = &(*prev_p)->next;
4748         }
4749     }
4750 }
4751
4752 /*
4753  * Nodes
4754  */
4755
4756 static NodeData*
4757 node_data_new (gpointer view_id)
4758 {
4759   NodeData *nd;
4760
4761   nd = g_slice_new (NodeData);
4762
4763   nd->view_id = view_id;
4764   nd->next = NULL;
4765   nd->width = 0;
4766   nd->height = 0;
4767   nd->valid = FALSE;
4768
4769   return nd;
4770 }
4771
4772 static void
4773 node_data_destroy (NodeData *nd)
4774 {
4775   g_slice_free (NodeData, nd);
4776 }
4777
4778 static void
4779 node_data_list_destroy (NodeData *nd)
4780 {
4781   g_slice_free_chain (NodeData, nd, next);
4782 }
4783
4784 static NodeData*
4785 node_data_find (NodeData *nd,
4786                 gpointer  view_id)
4787 {
4788   while (nd != NULL)
4789     {
4790       if (nd->view_id == view_id)
4791         break;
4792       nd = nd->next;
4793     }
4794   return nd;
4795 }
4796
4797 static void
4798 summary_destroy (Summary *summary)
4799 {
4800   /* Fill with error-triggering garbage */
4801   summary->info = (void*)0x1;
4802   summary->toggle_count = 567;
4803   summary->next = (void*)0x1;
4804   g_slice_free (Summary, summary);
4805 }
4806
4807 static GtkTextBTreeNode*
4808 gtk_text_btree_node_new (void)
4809 {
4810   GtkTextBTreeNode *node;
4811
4812   node = g_new (GtkTextBTreeNode, 1);
4813
4814   node->node_data = NULL;
4815
4816   return node;
4817 }
4818
4819 static void
4820 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode  *node,
4821                                          GtkTextTagInfo  *info,
4822                                          gint adjust)
4823 {
4824   Summary *summary;
4825
4826   summary = node->summary;
4827   while (summary != NULL)
4828     {
4829       if (summary->info == info)
4830         {
4831           summary->toggle_count += adjust;
4832           break;
4833         }
4834
4835       summary = summary->next;
4836     }
4837
4838   if (summary == NULL)
4839     {
4840       /* didn't find a summary for our tag. */
4841       g_return_if_fail (adjust > 0);
4842       summary = g_slice_new (Summary);
4843       summary->info = info;
4844       summary->toggle_count = adjust;
4845       summary->next = node->summary;
4846       node->summary = summary;
4847     }
4848 }
4849
4850 /* Note that the tag root and above do not have summaries
4851    for the tag; only nodes below the tag root have
4852    the summaries. */
4853 static gboolean
4854 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4855 {
4856   Summary *summary;
4857
4858   summary = node->summary;
4859   while (summary != NULL)
4860     {
4861       if (tag == NULL ||
4862           summary->info->tag == tag)
4863         return TRUE;
4864
4865       summary = summary->next;
4866     }
4867
4868   return FALSE;
4869 }
4870
4871 /* Add node and all children to the damage region. */
4872 static void
4873 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4874 {
4875   NodeData *nd;
4876
4877   nd = node->node_data;
4878   while (nd != NULL)
4879     {
4880       nd->valid = FALSE;
4881       nd = nd->next;
4882     }
4883
4884   if (node->level == 0)
4885     {
4886       GtkTextLine *line;
4887
4888       line = node->children.line;
4889       while (line != NULL)
4890         {
4891           GtkTextLineData *ld;
4892
4893           ld = line->views;
4894           while (ld != NULL)
4895             {
4896               ld->valid = FALSE;
4897               ld = ld->next;
4898             }
4899
4900           line = line->next;
4901         }
4902     }
4903   else
4904     {
4905       GtkTextBTreeNode *child;
4906
4907       child = node->children.node;
4908
4909       while (child != NULL)
4910         {
4911           gtk_text_btree_node_invalidate_downward (child);
4912
4913           child = child->next;
4914         }
4915     }
4916 }
4917
4918 static void
4919 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4920 {
4921   GtkTextBTreeNode *iter;
4922
4923   iter = node;
4924   while (iter != NULL)
4925     {
4926       NodeData *nd;
4927
4928       if (view_id)
4929         {
4930           nd = node_data_find (iter->node_data, view_id);
4931
4932           if (nd == NULL || !nd->valid)
4933             break; /* Once a node is invalid, we know its parents are as well. */
4934
4935           nd->valid = FALSE;
4936         }
4937       else
4938         {
4939           gboolean should_continue = FALSE;
4940
4941           nd = iter->node_data;
4942           while (nd != NULL)
4943             {
4944               if (nd->valid)
4945                 {
4946                   should_continue = TRUE;
4947                   nd->valid = FALSE;
4948                 }
4949
4950               nd = nd->next;
4951             }
4952
4953           if (!should_continue)
4954             break; /* This node was totally invalidated, so are its
4955                       parents */
4956         }
4957
4958       iter = iter->parent;
4959     }
4960 }
4961
4962
4963 /**
4964  * _gtk_text_btree_is_valid:
4965  * @tree: a #GtkTextBTree
4966  * @view_id: ID for the view
4967  *
4968  * Check to see if the entire #GtkTextBTree is valid or not for
4969  * the given view.
4970  *
4971  * Return value: %TRUE if the entire #GtkTextBTree is valid
4972  **/
4973 gboolean
4974 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4975                          gpointer      view_id)
4976 {
4977   NodeData *nd;
4978   g_return_val_if_fail (tree != NULL, FALSE);
4979
4980   nd = node_data_find (tree->root_node->node_data, view_id);
4981   return (nd && nd->valid);
4982 }
4983
4984 typedef struct _ValidateState ValidateState;
4985
4986 struct _ValidateState
4987 {
4988   gint remaining_pixels;
4989   gboolean in_validation;
4990   gint y;
4991   gint old_height;
4992   gint new_height;
4993 };
4994
4995 static void
4996 gtk_text_btree_node_validate (BTreeView         *view,
4997                               GtkTextBTreeNode  *node,
4998                               gpointer           view_id,
4999                               ValidateState     *state)
5000 {
5001   gint node_valid = TRUE;
5002   gint node_width = 0;
5003   gint node_height = 0;
5004
5005   NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5006   g_return_if_fail (!nd->valid);
5007
5008   if (node->level == 0)
5009     {
5010       GtkTextLine *line = node->children.line;
5011       GtkTextLineData *ld;
5012
5013       /* Iterate over leading valid lines */
5014       while (line != NULL)
5015         {
5016           ld = _gtk_text_line_get_data (line, view_id);
5017
5018           if (!ld || !ld->valid)
5019             break;
5020           else if (state->in_validation)
5021             {
5022               state->in_validation = FALSE;
5023               return;
5024             }
5025           else
5026             {
5027               state->y += ld->height;
5028               node_width = MAX (ld->width, node_width);
5029               node_height += ld->height;
5030             }
5031
5032           line = line->next;
5033         }
5034
5035       state->in_validation = TRUE;
5036
5037       /* Iterate over invalid lines */
5038       while (line != NULL)
5039         {
5040           ld = _gtk_text_line_get_data (line, view_id);
5041
5042           if (ld && ld->valid)
5043             break;
5044           else
5045             {
5046               if (ld)
5047                 state->old_height += ld->height;
5048               ld = gtk_text_layout_wrap (view->layout, line, ld);
5049               state->new_height += ld->height;
5050
5051               node_width = MAX (ld->width, node_width);
5052               node_height += ld->height;
5053
5054               state->remaining_pixels -= ld->height;
5055               if (state->remaining_pixels <= 0)
5056                 {
5057                   line = line->next;
5058                   break;
5059                 }
5060             }
5061
5062           line = line->next;
5063         }
5064
5065       /* Iterate over the remaining lines */
5066       while (line != NULL)
5067         {
5068           ld = _gtk_text_line_get_data (line, view_id);
5069           state->in_validation = FALSE;
5070
5071           if (!ld || !ld->valid)
5072             node_valid = FALSE;
5073
5074           if (ld)
5075             {
5076               node_width = MAX (ld->width, node_width);
5077               node_height += ld->height;
5078             }
5079
5080           line = line->next;
5081         }
5082     }
5083   else
5084     {
5085       GtkTextBTreeNode *child;
5086       NodeData *child_nd;
5087
5088       child = node->children.node;
5089
5090       /* Iterate over leading valid nodes */
5091       while (child)
5092         {
5093           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5094
5095           if (!child_nd->valid)
5096             break;
5097           else if (state->in_validation)
5098             {
5099               state->in_validation = FALSE;
5100               return;
5101             }
5102           else
5103             {
5104               state->y += child_nd->height;
5105               node_width = MAX (node_width, child_nd->width);
5106               node_height += child_nd->height;
5107             }
5108
5109           child = child->next;
5110         }
5111
5112       /* Iterate over invalid nodes */
5113       while (child)
5114         {
5115           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5116
5117           if (child_nd->valid)
5118             break;
5119           else
5120             {
5121               gtk_text_btree_node_validate (view, child, view_id, state);
5122
5123               if (!child_nd->valid)
5124                 node_valid = FALSE;
5125               node_width = MAX (node_width, child_nd->width);
5126               node_height += child_nd->height;
5127
5128               if (!state->in_validation || state->remaining_pixels <= 0)
5129                 {
5130                   child = child->next;
5131                   break;
5132                 }
5133             }
5134
5135           child = child->next;
5136         }
5137
5138       /* Iterate over the remaining lines */
5139       while (child)
5140         {
5141           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5142           state->in_validation = FALSE;
5143
5144           if (!child_nd->valid)
5145             node_valid = FALSE;
5146
5147           node_width = MAX (child_nd->width, node_width);
5148           node_height += child_nd->height;
5149
5150           child = child->next;
5151         }
5152     }
5153
5154   nd->width = node_width;
5155   nd->height = node_height;
5156   nd->valid = node_valid;
5157 }
5158
5159 /**
5160  * _gtk_text_btree_validate:
5161  * @tree: a #GtkTextBTree
5162  * @view_id: view id
5163  * @max_pixels: the maximum number of pixels to validate. (No more
5164  *              than one paragraph beyond this limit will be validated)
5165  * @y: location to store starting y coordinate of validated region
5166  * @old_height: location to store old height of validated region
5167  * @new_height: location to store new height of validated region
5168  *
5169  * Validate a single contiguous invalid region of a #GtkTextBTree for
5170  * a given view.
5171  *
5172  * Return value: %TRUE if a region has been validated, %FALSE if the
5173  * entire tree was already valid.
5174  **/
5175 gboolean
5176 _gtk_text_btree_validate (GtkTextBTree *tree,
5177                          gpointer      view_id,
5178                          gint          max_pixels,
5179                          gint         *y,
5180                          gint         *old_height,
5181                          gint         *new_height)
5182 {
5183   BTreeView *view;
5184
5185   g_return_val_if_fail (tree != NULL, FALSE);
5186
5187   view = gtk_text_btree_get_view (tree, view_id);
5188   g_return_val_if_fail (view != NULL, FALSE);
5189
5190   if (!_gtk_text_btree_is_valid (tree, view_id))
5191     {
5192       ValidateState state;
5193
5194       state.remaining_pixels = max_pixels;
5195       state.in_validation = FALSE;
5196       state.y = 0;
5197       state.old_height = 0;
5198       state.new_height = 0;
5199
5200       gtk_text_btree_node_validate (view,
5201                                     tree->root_node,
5202                                     view_id, &state);
5203
5204       if (y)
5205         *y = state.y;
5206       if (old_height)
5207         *old_height = state.old_height;
5208       if (new_height)
5209         *new_height = state.new_height;
5210
5211       if (gtk_debug_flags & GTK_DEBUG_TEXT)
5212         _gtk_text_btree_check (tree);
5213
5214       return TRUE;
5215     }
5216   else
5217     return FALSE;
5218 }
5219
5220 static void
5221 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5222                                              gpointer          view_id,
5223                                              gint             *width_out,
5224                                              gint             *height_out,
5225                                              gboolean         *valid_out)
5226 {
5227   gint width = 0;
5228   gint height = 0;
5229   gboolean valid = TRUE;
5230
5231   if (node->level == 0)
5232     {
5233       GtkTextLine *line = node->children.line;
5234
5235       while (line != NULL)
5236         {
5237           GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5238
5239           if (!ld || !ld->valid)
5240             valid = FALSE;
5241
5242           if (ld)
5243             {
5244               width = MAX (ld->width, width);
5245               height += ld->height;
5246             }
5247
5248           line = line->next;
5249         }
5250     }
5251   else
5252     {
5253       GtkTextBTreeNode *child = node->children.node;
5254
5255       while (child)
5256         {
5257           NodeData *child_nd = node_data_find (child->node_data, view_id);
5258
5259           if (!child_nd || !child_nd->valid)
5260             valid = FALSE;
5261
5262           if (child_nd)
5263             {
5264               width = MAX (child_nd->width, width);
5265               height += child_nd->height;
5266             }
5267
5268           child = child->next;
5269         }
5270     }
5271
5272   *width_out = width;
5273   *height_out = height;
5274   *valid_out = valid;
5275 }
5276
5277
5278 /* Recompute the validity and size of the view data for a given
5279  * view at this node from the immediate children of the node
5280  */
5281 static NodeData *
5282 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5283                                  gpointer          view_id)
5284 {
5285   NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5286   gboolean valid;
5287   gint width;
5288   gint height;
5289
5290   gtk_text_btree_node_compute_view_aggregates (node, view_id,
5291                                                &width, &height, &valid);
5292   nd->width = width;
5293   nd->height = height;
5294   nd->valid = valid;
5295
5296   return nd;
5297 }
5298
5299 static void
5300 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5301                                         gpointer          view_id)
5302 {
5303   while (node)
5304     {
5305       gtk_text_btree_node_check_valid (node, view_id);
5306       node = node->parent;
5307     }
5308 }
5309
5310 static NodeData *
5311 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5312                                           gpointer          view_id)
5313 {
5314   if (node->level == 0)
5315     {
5316       return gtk_text_btree_node_check_valid (node, view_id);
5317     }
5318   else
5319     {
5320       GtkTextBTreeNode *child = node->children.node;
5321
5322       NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5323
5324       nd->valid = TRUE;
5325       nd->width = 0;
5326       nd->height = 0;
5327
5328       while (child)
5329         {
5330           NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5331
5332           if (!child_nd->valid)
5333             nd->valid = FALSE;
5334           nd->width = MAX (child_nd->width, nd->width);
5335           nd->height += child_nd->height;
5336
5337           child = child->next;
5338         }
5339       return nd;
5340     }
5341 }
5342
5343
5344
5345 /**
5346  * _gtk_text_btree_validate_line:
5347  * @tree: a #GtkTextBTree
5348  * @line: line to validate
5349  * @view_id: view ID for the view to validate
5350  *
5351  * Revalidate a single line of the btree for the given view, propagate
5352  * results up through the entire tree.
5353  **/
5354 void
5355 _gtk_text_btree_validate_line (GtkTextBTree     *tree,
5356                                GtkTextLine      *line,
5357                                gpointer          view_id)
5358 {
5359   GtkTextLineData *ld;
5360   BTreeView *view;
5361
5362   g_return_if_fail (tree != NULL);
5363   g_return_if_fail (line != NULL);
5364
5365   view = gtk_text_btree_get_view (tree, view_id);
5366   g_return_if_fail (view != NULL);
5367
5368   ld = _gtk_text_line_get_data (line, view_id);
5369   if (!ld || !ld->valid)
5370     {
5371       ld = gtk_text_layout_wrap (view->layout, line, ld);
5372
5373       gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5374     }
5375 }
5376
5377 static void
5378 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5379 {
5380   if (node->level == 0)
5381     {
5382       GtkTextLine *line;
5383
5384       line = node->children.line;
5385       while (line != NULL)
5386         {
5387           GtkTextLineData *ld;
5388
5389           ld = _gtk_text_line_remove_data (line, view_id);
5390
5391           if (ld)
5392             gtk_text_layout_free_line_data (view->layout, line, ld);
5393
5394           line = line->next;
5395         }
5396     }
5397   else
5398     {
5399       GtkTextBTreeNode *child;
5400
5401       child = node->children.node;
5402
5403       while (child != NULL)
5404         {
5405           /* recurse */
5406           gtk_text_btree_node_remove_view (view, child, view_id);
5407
5408           child = child->next;
5409         }
5410     }
5411
5412   gtk_text_btree_node_remove_data (node, view_id);
5413 }
5414
5415 static void
5416 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5417 {
5418   if (node->level == 0)
5419     {
5420       GtkTextLine *line;
5421       GtkTextLineSegment *seg;
5422
5423       while (node->children.line != NULL)
5424         {
5425           line = node->children.line;
5426           node->children.line = line->next;
5427           while (line->segments != NULL)
5428             {
5429               seg = line->segments;
5430               line->segments = seg->next;
5431
5432               (*seg->type->deleteFunc) (seg, line, TRUE);
5433             }
5434           gtk_text_line_destroy (tree, line);
5435         }
5436     }
5437   else
5438     {
5439       GtkTextBTreeNode *childPtr;
5440
5441       while (node->children.node != NULL)
5442         {
5443           childPtr = node->children.node;
5444           node->children.node = childPtr->next;
5445           gtk_text_btree_node_destroy (tree, childPtr);
5446         }
5447     }
5448
5449   gtk_text_btree_node_free_empty (tree, node);
5450 }
5451
5452 static void
5453 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5454                                 GtkTextBTreeNode *node)
5455 {
5456   g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5457                     (node->level == 0 && node->children.line == NULL));
5458
5459   summary_list_destroy (node->summary);
5460   node_data_list_destroy (node->node_data);
5461   g_free (node);
5462 }
5463
5464 static NodeData*
5465 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5466 {
5467   NodeData *nd;
5468
5469   nd = node->node_data;
5470   while (nd != NULL)
5471     {
5472       if (nd->view_id == view_id)
5473         break;
5474
5475       nd = nd->next;
5476     }
5477
5478   if (nd == NULL)
5479     {
5480       nd = node_data_new (view_id);
5481
5482       if (node->node_data)
5483         nd->next = node->node_data;
5484
5485       node->node_data = nd;
5486     }
5487
5488   return nd;
5489 }
5490
5491 static void
5492 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5493 {
5494   NodeData *nd;
5495   NodeData *prev;
5496
5497   prev = NULL;
5498   nd = node->node_data;
5499   while (nd != NULL)
5500     {
5501       if (nd->view_id == view_id)
5502         break;
5503
5504       prev = nd;
5505       nd = nd->next;
5506     }
5507
5508   if (nd == NULL)
5509     return;
5510
5511   if (prev != NULL)
5512     prev->next = nd->next;
5513
5514   if (node->node_data == nd)
5515     node->node_data = nd->next;
5516
5517   nd->next = NULL;
5518
5519   node_data_destroy (nd);
5520 }
5521
5522 static void
5523 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5524                               gint *width, gint *height)
5525 {
5526   NodeData *nd;
5527
5528   g_return_if_fail (width != NULL);
5529   g_return_if_fail (height != NULL);
5530
5531   nd = gtk_text_btree_node_ensure_data (node, view_id);
5532
5533   if (width)
5534     *width = nd->width;
5535   if (height)
5536     *height = nd->height;
5537 }
5538
5539 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5540  * here isn't quite right, since for a lot of operations we want to
5541  * know which children of the common parent correspond to the two nodes
5542  * (e.g., when computing the order of two iters)
5543  */
5544 static GtkTextBTreeNode *
5545 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5546                                    GtkTextBTreeNode *node2)
5547 {
5548   while (node1->level < node2->level)
5549     node1 = node1->parent;
5550   while (node2->level < node1->level)
5551     node2 = node2->parent;
5552   while (node1 != node2)
5553     {
5554       node1 = node1->parent;
5555       node2 = node2->parent;
5556     }
5557
5558   return node1;
5559 }
5560
5561 /*
5562  * BTree
5563  */
5564
5565 static BTreeView*
5566 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5567 {
5568   BTreeView *view;
5569
5570   view = tree->views;
5571   while (view != NULL)
5572     {
5573       if (view->view_id == view_id)
5574         break;
5575       view = view->next;
5576     }
5577
5578   return view;
5579 }
5580
5581 static void
5582 get_tree_bounds (GtkTextBTree *tree,
5583                  GtkTextIter *start,
5584                  GtkTextIter *end)
5585 {
5586   _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5587   _gtk_text_btree_get_end_iter (tree, end);
5588 }
5589
5590 static void
5591 tag_changed_cb (GtkTextTagTable *table,
5592                 GtkTextTag      *tag,
5593                 gboolean         size_changed,
5594                 GtkTextBTree    *tree)
5595 {
5596   if (size_changed)
5597     {
5598       /* We need to queue a relayout on all regions that are tagged with
5599        * this tag.
5600        */
5601
5602       GtkTextIter start;
5603       GtkTextIter end;
5604
5605       if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5606         {
5607           /* Must be a last toggle if there was a first one. */
5608           _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5609           DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5610           _gtk_text_btree_invalidate_region (tree,
5611                                             &start, &end);
5612
5613         }
5614     }
5615   else
5616     {
5617       /* We only need to queue a redraw, not a relayout */
5618       BTreeView *view;
5619
5620       view = tree->views;
5621
5622       while (view != NULL)
5623         {
5624           gint width, height;
5625
5626           _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5627           gtk_text_layout_changed (view->layout, 0, height, height);
5628
5629           view = view->next;
5630         }
5631     }
5632 }
5633
5634 void
5635 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree    *tree,
5636                                         GtkTextTag      *tag)
5637 {
5638   /* Remove the tag from the tree */
5639
5640   GtkTextIter start;
5641   GtkTextIter end;
5642
5643   get_tree_bounds (tree, &start, &end);
5644
5645   _gtk_text_btree_tag (&start, &end, tag, FALSE);
5646   gtk_text_btree_remove_tag_info (tree, tag);
5647 }
5648
5649
5650 /* Rebalance the out-of-whack node "node" */
5651 static void
5652 gtk_text_btree_rebalance (GtkTextBTree *tree,
5653                           GtkTextBTreeNode *node)
5654 {
5655   /*
5656    * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5657    * up through the tree one GtkTextBTreeNode at a time until the root
5658    * GtkTextBTreeNode has been processed.
5659    */
5660
5661   while (node != NULL)
5662     {
5663       GtkTextBTreeNode *new_node, *child;
5664       GtkTextLine *line;
5665       int i;
5666
5667       /*
5668        * Check to see if the GtkTextBTreeNode has too many children.  If it does,
5669        * then split off all but the first MIN_CHILDREN into a separate
5670        * GtkTextBTreeNode following the original one.  Then repeat until the
5671        * GtkTextBTreeNode has a decent size.
5672        */
5673
5674       if (node->num_children > MAX_CHILDREN)
5675         {
5676           while (1)
5677             {
5678               /*
5679                * If the GtkTextBTreeNode being split is the root
5680                * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5681                * it first.
5682                */
5683
5684               if (node->parent == NULL)
5685                 {
5686                   new_node = gtk_text_btree_node_new ();
5687                   new_node->parent = NULL;
5688                   new_node->next = NULL;
5689                   new_node->summary = NULL;
5690                   new_node->level = node->level + 1;
5691                   new_node->children.node = node;
5692                   recompute_node_counts (tree, new_node);
5693                   tree->root_node = new_node;
5694                 }
5695               new_node = gtk_text_btree_node_new ();
5696               new_node->parent = node->parent;
5697               new_node->next = node->next;
5698               node->next = new_node;
5699               new_node->summary = NULL;
5700               new_node->level = node->level;
5701               new_node->num_children = node->num_children - MIN_CHILDREN;
5702               if (node->level == 0)
5703                 {
5704                   for (i = MIN_CHILDREN-1,
5705                          line = node->children.line;
5706                        i > 0; i--, line = line->next)
5707                     {
5708                       /* Empty loop body. */
5709                     }
5710                   new_node->children.line = line->next;
5711                   line->next = NULL;
5712                 }
5713               else
5714                 {
5715                   for (i = MIN_CHILDREN-1,
5716                          child = node->children.node;
5717                        i > 0; i--, child = child->next)
5718                     {
5719                       /* Empty loop body. */
5720                     }
5721                   new_node->children.node = child->next;
5722                   child->next = NULL;
5723                 }
5724               recompute_node_counts (tree, node);
5725               node->parent->num_children++;
5726               node = new_node;
5727               if (node->num_children <= MAX_CHILDREN)
5728                 {
5729                   recompute_node_counts (tree, node);
5730                   break;
5731                 }
5732             }
5733         }
5734
5735       while (node->num_children < MIN_CHILDREN)
5736         {
5737           GtkTextBTreeNode *other;
5738           GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5739           GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5740           int total_children, first_children, i;
5741
5742           /*
5743            * Too few children for this GtkTextBTreeNode.  If this is the root then,
5744            * it's OK for it to have less than MIN_CHILDREN children
5745            * as long as it's got at least two.  If it has only one
5746            * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5747            * the tree and use its child as the new root.
5748            */
5749
5750           if (node->parent == NULL)
5751             {
5752               if ((node->num_children == 1) && (node->level > 0))
5753                 {
5754                   tree->root_node = node->children.node;
5755                   tree->root_node->parent = NULL;
5756
5757                   node->children.node = NULL;
5758                   gtk_text_btree_node_free_empty (tree, node);
5759                 }
5760               return;
5761             }
5762
5763           /*
5764            * Not the root.  Make sure that there are siblings to
5765            * balance with.
5766            */
5767
5768           if (node->parent->num_children < 2)
5769             {
5770               gtk_text_btree_rebalance (tree, node->parent);
5771               continue;
5772             }
5773
5774           /*
5775            * Find a sibling neighbor to borrow from, and arrange for
5776            * node to be the earlier of the pair.
5777            */
5778
5779           if (node->next == NULL)
5780             {
5781               for (other = node->parent->children.node;
5782                    other->next != node;
5783                    other = other->next)
5784                 {
5785                   /* Empty loop body. */
5786                 }
5787               node = other;
5788             }
5789           other = node->next;
5790
5791           /*
5792            * We're going to either merge the two siblings together
5793            * into one GtkTextBTreeNode or redivide the children among them to
5794            * balance their loads.  As preparation, join their two
5795            * child lists into a single list and remember the half-way
5796            * point in the list.
5797            */
5798
5799           total_children = node->num_children + other->num_children;
5800           first_children = total_children/2;
5801           if (node->children.node == NULL)
5802             {
5803               node->children = other->children;
5804               other->children.node = NULL;
5805               other->children.line = NULL;
5806             }
5807           if (node->level == 0)
5808             {
5809               GtkTextLine *line;
5810
5811               for (line = node->children.line, i = 1;
5812                    line->next != NULL;
5813                    line = line->next, i++)
5814                 {
5815                   if (i == first_children)
5816                     {
5817                       halfwayline = line;
5818                     }
5819                 }
5820               line->next = other->children.line;
5821               while (i <= first_children)
5822                 {
5823                   halfwayline = line;
5824                   line = line->next;
5825                   i++;
5826                 }
5827             }
5828           else
5829             {
5830               GtkTextBTreeNode *child;
5831
5832               for (child = node->children.node, i = 1;
5833                    child->next != NULL;
5834                    child = child->next, i++)
5835                 {
5836                   if (i <= first_children)
5837                     {
5838                       if (i == first_children)
5839                         {
5840                           halfwaynode = child;
5841                         }
5842                     }
5843                 }
5844               child->next = other->children.node;
5845               while (i <= first_children)
5846                 {
5847                   halfwaynode = child;
5848                   child = child->next;
5849                   i++;
5850                 }
5851             }
5852
5853           /*
5854            * If the two siblings can simply be merged together, do it.
5855            */
5856
5857           if (total_children <= MAX_CHILDREN)
5858             {
5859               recompute_node_counts (tree, node);
5860               node->next = other->next;
5861               node->parent->num_children--;
5862
5863               other->children.node = NULL;
5864               other->children.line = NULL;
5865               gtk_text_btree_node_free_empty (tree, other);
5866               continue;
5867             }
5868
5869           /*
5870            * The siblings can't be merged, so just divide their
5871            * children evenly between them.
5872            */
5873
5874           if (node->level == 0)
5875             {
5876               other->children.line = halfwayline->next;
5877               halfwayline->next = NULL;
5878             }
5879           else
5880             {
5881               other->children.node = halfwaynode->next;
5882               halfwaynode->next = NULL;
5883             }
5884
5885           recompute_node_counts (tree, node);
5886           recompute_node_counts (tree, other);
5887         }
5888
5889       node = node->parent;
5890     }
5891 }
5892
5893 static void
5894 post_insert_fixup (GtkTextBTree *tree,
5895                    GtkTextLine *line,
5896                    gint line_count_delta,
5897                    gint char_count_delta)
5898
5899 {
5900   GtkTextBTreeNode *node;
5901
5902   /*
5903    * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5904    * point, then rebalance the tree if necessary.
5905    */
5906
5907   for (node = line->parent ; node != NULL;
5908        node = node->parent)
5909     {
5910       node->num_lines += line_count_delta;
5911       node->num_chars += char_count_delta;
5912     }
5913   node = line->parent;
5914   node->num_children += line_count_delta;
5915
5916   if (node->num_children > MAX_CHILDREN)
5917     {
5918       gtk_text_btree_rebalance (tree, node);
5919     }
5920
5921   if (gtk_debug_flags & GTK_DEBUG_TEXT)
5922     _gtk_text_btree_check (tree);
5923 }
5924
5925 static GtkTextTagInfo*
5926 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5927                                       GtkTextTag   *tag)
5928 {
5929   GtkTextTagInfo *info;
5930   GSList *list;
5931
5932
5933   list = tree->tag_infos;
5934   while (list != NULL)
5935     {
5936       info = list->data;
5937       if (info->tag == tag)
5938         return info;
5939
5940       list = g_slist_next (list);
5941     }
5942
5943   return NULL;
5944 }
5945
5946 static GtkTextTagInfo*
5947 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5948                              GtkTextTag   *tag)
5949 {
5950   GtkTextTagInfo *info;
5951
5952   info = gtk_text_btree_get_existing_tag_info (tree, tag);
5953
5954   if (info == NULL)
5955     {
5956       /* didn't find it, create. */
5957
5958       info = g_slice_new (GtkTextTagInfo);
5959
5960       info->tag = tag;
5961       g_object_ref (tag);
5962       info->tag_root = NULL;
5963       info->toggle_count = 0;
5964
5965       tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5966
5967 #if 0
5968       g_print ("Created tag info %p for tag %s(%p)\n",
5969                info, info->tag->name ? info->tag->name : "anon",
5970                info->tag);
5971 #endif
5972     }
5973
5974   return info;
5975 }
5976
5977 static void
5978 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5979                                 GtkTextTag   *tag)
5980 {
5981   GtkTextTagInfo *info;
5982   GSList *list;
5983   GSList *prev;
5984
5985   prev = NULL;
5986   list = tree->tag_infos;
5987   while (list != NULL)
5988     {
5989       info = list->data;
5990       if (info->tag == tag)
5991         {
5992 #if 0
5993           g_print ("Removing tag info %p for tag %s(%p)\n",
5994                    info, info->tag->name ? info->tag->name : "anon",
5995                    info->tag);
5996 #endif
5997
5998           if (prev != NULL)
5999             {
6000               prev->next = list->next;
6001             }
6002           else
6003             {
6004               tree->tag_infos = list->next;
6005             }
6006           list->next = NULL;
6007           g_slist_free (list);
6008
6009           g_object_unref (info->tag);
6010
6011           g_slice_free (GtkTextTagInfo, info);
6012           return;
6013         }
6014
6015       prev = list;
6016       list = g_slist_next (list);
6017     }
6018 }
6019
6020 static void
6021 recompute_level_zero_counts (GtkTextBTreeNode *node)
6022 {
6023   GtkTextLine *line;
6024   GtkTextLineSegment *seg;
6025
6026   g_assert (node->level == 0);
6027
6028   line = node->children.line;
6029   while (line != NULL)
6030     {
6031       node->num_children++;
6032       node->num_lines++;
6033
6034       if (line->parent != node)
6035         gtk_text_line_set_parent (line, node);
6036
6037       seg = line->segments;
6038       while (seg != NULL)
6039         {
6040
6041           node->num_chars += seg->char_count;
6042
6043           if (((seg->type != &gtk_text_toggle_on_type)
6044                && (seg->type != &gtk_text_toggle_off_type))
6045               || !(seg->body.toggle.inNodeCounts))
6046             {
6047               ; /* nothing */
6048             }
6049           else
6050             {
6051               GtkTextTagInfo *info;
6052
6053               info = seg->body.toggle.info;
6054
6055               gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6056             }
6057
6058           seg = seg->next;
6059         }
6060
6061       line = line->next;
6062     }
6063 }
6064
6065 static void
6066 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6067 {
6068   Summary *summary;
6069   GtkTextBTreeNode *child;
6070
6071   g_assert (node->level > 0);
6072
6073   child = node->children.node;
6074   while (child != NULL)
6075     {
6076       node->num_children += 1;
6077       node->num_lines += child->num_lines;
6078       node->num_chars += child->num_chars;
6079
6080       if (child->parent != node)
6081         {
6082           child->parent = node;
6083           gtk_text_btree_node_invalidate_upward (node, NULL);
6084         }
6085
6086       summary = child->summary;
6087       while (summary != NULL)
6088         {
6089           gtk_text_btree_node_adjust_toggle_count (node,
6090                                                    summary->info,
6091                                                    summary->toggle_count);
6092
6093           summary = summary->next;
6094         }
6095
6096       child = child->next;
6097     }
6098 }
6099
6100 /*
6101  *----------------------------------------------------------------------
6102  *
6103  * recompute_node_counts --
6104  *
6105  *      This procedure is called to recompute all the counts in a GtkTextBTreeNode
6106  *      (tags, child information, etc.) by scanning the information in
6107  *      its descendants.  This procedure is called during rebalancing
6108  *      when a GtkTextBTreeNode's child structure has changed.
6109  *
6110  * Results:
6111  *      None.
6112  *
6113  * Side effects:
6114  *      The tag counts for node are modified to reflect its current
6115  *      child structure, as are its num_children, num_lines, num_chars fields.
6116  *      Also, all of the childrens' parent fields are made to point
6117  *      to node.
6118  *
6119  *----------------------------------------------------------------------
6120  */
6121
6122 static void
6123 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6124 {
6125   BTreeView *view;
6126   Summary *summary, *summary2;
6127
6128   /*
6129    * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6130    * the existing Summary records (most of them will probably be reused).
6131    */
6132
6133   summary = node->summary;
6134   while (summary != NULL)
6135     {
6136       summary->toggle_count = 0;
6137       summary = summary->next;
6138     }
6139
6140   node->num_children = 0;
6141   node->num_lines = 0;
6142   node->num_chars = 0;
6143
6144   /*
6145    * Scan through the children, adding the childrens' tag counts into
6146    * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6147    * necessary.
6148    */
6149
6150   if (node->level == 0)
6151     recompute_level_zero_counts (node);
6152   else
6153     recompute_level_nonzero_counts (node);
6154
6155   view = tree->views;
6156   while (view)
6157     {
6158       gtk_text_btree_node_check_valid (node, view->view_id);
6159       view = view->next;
6160     }
6161
6162   /*
6163    * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6164    * records that still have a zero count, or that have all the toggles.
6165    * The GtkTextBTreeNode with the children that account for all the tags toggles
6166    * have no summary information, and they become the tag_root for the tag.
6167    */
6168
6169   summary2 = NULL;
6170   for (summary = node->summary; summary != NULL; )
6171     {
6172       if (summary->toggle_count > 0 &&
6173           summary->toggle_count < summary->info->toggle_count)
6174         {
6175           if (node->level == summary->info->tag_root->level)
6176             {
6177               /*
6178                * The tag's root GtkTextBTreeNode split and some toggles left.
6179                * The tag root must move up a level.
6180                */
6181               summary->info->tag_root = node->parent;
6182             }
6183           summary2 = summary;
6184           summary = summary->next;
6185           continue;
6186         }
6187       if (summary->toggle_count == summary->info->toggle_count)
6188         {
6189           /*
6190            * A GtkTextBTreeNode merge has collected all the toggles under
6191            * one GtkTextBTreeNode.  Push the root down to this level.
6192            */
6193           summary->info->tag_root = node;
6194         }
6195       if (summary2 != NULL)
6196         {
6197           summary2->next = summary->next;
6198           summary_destroy (summary);
6199           summary = summary2->next;
6200         }
6201       else
6202         {
6203           node->summary = summary->next;
6204           summary_destroy (summary);
6205           summary = node->summary;
6206         }
6207     }
6208 }
6209
6210 void
6211 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6212                                GtkTextTagInfo   *info,
6213                                gint              delta) /* may be negative */
6214 {
6215   Summary *summary, *prevPtr;
6216   GtkTextBTreeNode *node2Ptr;
6217   int rootLevel;                        /* Level of original tag root */
6218
6219   info->toggle_count += delta;
6220
6221   if (info->tag_root == (GtkTextBTreeNode *) NULL)
6222     {
6223       info->tag_root = node;
6224       return;
6225     }
6226
6227   /*
6228    * Note the level of the existing root for the tag so we can detect
6229    * if it needs to be moved because of the toggle count change.
6230    */
6231
6232   rootLevel = info->tag_root->level;
6233
6234   /*
6235    * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6236    * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6237    * necessary.
6238    */
6239
6240   for ( ; node != info->tag_root; node = node->parent)
6241     {
6242       /*
6243        * See if there's already an entry for this tag for this GtkTextBTreeNode.  If so,
6244        * perhaps all we have to do is adjust its count.
6245        */
6246
6247       for (prevPtr = NULL, summary = node->summary;
6248            summary != NULL;
6249            prevPtr = summary, summary = summary->next)
6250         {
6251           if (summary->info == info)
6252             {
6253               break;
6254             }
6255         }
6256       if (summary != NULL)
6257         {
6258           summary->toggle_count += delta;
6259           if (summary->toggle_count > 0 &&
6260               summary->toggle_count < info->toggle_count)
6261             {
6262               continue;
6263             }
6264           if (summary->toggle_count != 0)
6265             {
6266               /*
6267                * Should never find a GtkTextBTreeNode with max toggle count at this
6268                * point (there shouldn't have been a summary entry in the
6269                * first place).
6270                */
6271
6272               g_error ("%s: bad toggle count (%d) max (%d)",
6273                        G_STRLOC, summary->toggle_count, info->toggle_count);
6274             }
6275
6276           /*
6277            * Zero toggle count;  must remove this tag from the list.
6278            */
6279
6280           if (prevPtr == NULL)
6281             {
6282               node->summary = summary->next;
6283             }
6284           else
6285             {
6286               prevPtr->next = summary->next;
6287             }
6288           summary_destroy (summary);
6289         }
6290       else
6291         {
6292           /*
6293            * This tag isn't currently in the summary information list.
6294            */
6295
6296           if (rootLevel == node->level)
6297             {
6298
6299               /*
6300                * The old tag root is at the same level in the tree as this
6301                * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode.  Move the tag root up
6302                * a level, in the hopes that it will now cover this GtkTextBTreeNode
6303                * as well as the old root (if not, we'll move it up again
6304                * the next time through the loop).  To push it up one level
6305                * we copy the original toggle count into the summary
6306                * information at the old root and change the root to its
6307                * parent GtkTextBTreeNode.
6308                */
6309
6310               GtkTextBTreeNode *rootnode = info->tag_root;
6311               summary = g_slice_new (Summary);
6312               summary->info = info;
6313               summary->toggle_count = info->toggle_count - delta;
6314               summary->next = rootnode->summary;
6315               rootnode->summary = summary;
6316               rootnode = rootnode->parent;
6317               rootLevel = rootnode->level;
6318               info->tag_root = rootnode;
6319             }
6320           summary = g_slice_new (Summary);
6321           summary->info = info;
6322           summary->toggle_count = delta;
6323           summary->next = node->summary;
6324           node->summary = summary;
6325         }
6326     }
6327
6328   /*
6329    * If we've decremented the toggle count, then it may be necessary
6330    * to push the tag root down one or more levels.
6331    */
6332
6333   if (delta >= 0)
6334     {
6335       return;
6336     }
6337   if (info->toggle_count == 0)
6338     {
6339       info->tag_root = (GtkTextBTreeNode *) NULL;
6340       return;
6341     }
6342   node = info->tag_root;
6343   while (node->level > 0)
6344     {
6345       /*
6346        * See if a single child GtkTextBTreeNode accounts for all of the tag's
6347        * toggles.  If so, push the root down one level.
6348        */
6349
6350       for (node2Ptr = node->children.node;
6351            node2Ptr != (GtkTextBTreeNode *)NULL ;
6352            node2Ptr = node2Ptr->next)
6353         {
6354           for (prevPtr = NULL, summary = node2Ptr->summary;
6355                summary != NULL;
6356                prevPtr = summary, summary = summary->next)
6357             {
6358               if (summary->info == info)
6359                 {
6360                   break;
6361                 }
6362             }
6363           if (summary == NULL)
6364             {
6365               continue;
6366             }
6367           if (summary->toggle_count != info->toggle_count)
6368             {
6369               /*
6370                * No GtkTextBTreeNode has all toggles, so the root is still valid.
6371                */
6372
6373               return;
6374             }
6375
6376           /*
6377            * This GtkTextBTreeNode has all the toggles, so push down the root.
6378            */
6379
6380           if (prevPtr == NULL)
6381             {
6382               node2Ptr->summary = summary->next;
6383             }
6384           else
6385             {
6386               prevPtr->next = summary->next;
6387             }
6388           summary_destroy (summary);
6389           info->tag_root = node2Ptr;
6390           break;
6391         }
6392       node = info->tag_root;
6393     }
6394 }
6395
6396 /*
6397  *----------------------------------------------------------------------
6398  *
6399  * inc_count --
6400  *
6401  *      This is a utility procedure used by _gtk_text_btree_get_tags.  It
6402  *      increments the count for a particular tag, adding a new
6403  *      entry for that tag if there wasn't one previously.
6404  *
6405  * Results:
6406  *      None.
6407  *
6408  * Side effects:
6409  *      The information at *tagInfoPtr may be modified, and the arrays
6410  *      may be reallocated to make them larger.
6411  *
6412  *----------------------------------------------------------------------
6413  */
6414
6415 static void
6416 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6417 {
6418   GtkTextTag **tag_p;
6419   int count;
6420
6421   for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6422        count > 0; tag_p++, count--)
6423     {
6424       if (*tag_p == tag)
6425         {
6426           tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6427           return;
6428         }
6429     }
6430
6431   /*
6432    * There isn't currently an entry for this tag, so we have to
6433    * make a new one.  If the arrays are full, then enlarge the
6434    * arrays first.
6435    */
6436
6437   if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6438     {
6439       GtkTextTag **newTags;
6440       int *newCounts, newSize;
6441
6442       newSize = 2*tagInfoPtr->arraySize;
6443       newTags = (GtkTextTag **) g_malloc ((unsigned)
6444                                           (newSize*sizeof (GtkTextTag *)));
6445       memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6446               tagInfoPtr->arraySize  *sizeof (GtkTextTag *));
6447       g_free ((char *) tagInfoPtr->tags);
6448       tagInfoPtr->tags = newTags;
6449       newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6450       memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6451               tagInfoPtr->arraySize  *sizeof (int));
6452       g_free ((char *) tagInfoPtr->counts);
6453       tagInfoPtr->counts = newCounts;
6454       tagInfoPtr->arraySize = newSize;
6455     }
6456
6457   tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6458   tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6459   tagInfoPtr->numTags++;
6460 }
6461
6462 static void
6463 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6464                              const GtkTextIter *iter)
6465 {
6466   GtkTextLineSegment *prev;
6467   GtkTextLine *line;
6468   GtkTextBTree *tree;
6469
6470   line = _gtk_text_iter_get_text_line (iter);
6471   tree = _gtk_text_iter_get_btree (iter);
6472
6473   prev = gtk_text_line_segment_split (iter);
6474   if (prev == NULL)
6475     {
6476       seg->next = line->segments;
6477       line->segments = seg;
6478     }
6479   else
6480     {
6481       seg->next = prev->next;
6482       prev->next = seg;
6483     }
6484   cleanup_line (line);
6485   segments_changed (tree);
6486
6487   if (gtk_debug_flags & GTK_DEBUG_TEXT)
6488     _gtk_text_btree_check (tree);
6489 }
6490
6491 static void
6492 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6493                                GtkTextLineSegment *seg,
6494                                GtkTextLine *line)
6495 {
6496   GtkTextLineSegment *prev;
6497
6498   if (line->segments == seg)
6499     {
6500       line->segments = seg->next;
6501     }
6502   else
6503     {
6504       for (prev = line->segments; prev->next != seg;
6505            prev = prev->next)
6506         {
6507           /* Empty loop body. */
6508         }
6509       prev->next = seg->next;
6510     }
6511   cleanup_line (line);
6512   segments_changed (tree);
6513 }
6514
6515 /*
6516  * This is here because it requires BTree internals, it logically
6517  * belongs in gtktextsegment.c
6518  */
6519
6520
6521 /*
6522  *--------------------------------------------------------------
6523  *
6524  * _gtk_toggle_segment_check_func --
6525  *
6526  *      This procedure is invoked to perform consistency checks
6527  *      on toggle segments.
6528  *
6529  * Results:
6530  *      None.
6531  *
6532  * Side effects:
6533  *      If a consistency problem is found the procedure g_errors.
6534  *
6535  *--------------------------------------------------------------
6536  */
6537
6538 void
6539 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6540                                 GtkTextLine *line)
6541 {
6542   Summary *summary;
6543   int needSummary;
6544
6545   if (segPtr->byte_count != 0)
6546     {
6547       g_error ("toggle_segment_check_func: segment had non-zero size");
6548     }
6549   if (!segPtr->body.toggle.inNodeCounts)
6550     {
6551       g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6552     }
6553   needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6554   for (summary = line->parent->summary; ;
6555        summary = summary->next)
6556     {
6557       if (summary == NULL)
6558         {
6559           if (needSummary)
6560             {
6561               g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6562             }
6563           else
6564             {
6565               break;
6566             }
6567         }
6568       if (summary->info == segPtr->body.toggle.info)
6569         {
6570           if (!needSummary)
6571             {
6572               g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6573             }
6574           break;
6575         }
6576     }
6577 }
6578
6579 /*
6580  * Debug
6581  */
6582
6583 static void
6584 gtk_text_btree_node_view_check_consistency (GtkTextBTree     *tree,
6585                                             GtkTextBTreeNode *node,
6586                                             NodeData         *nd)
6587 {
6588   gint width;
6589   gint height;
6590   gboolean valid;
6591   BTreeView *view;
6592
6593   view = tree->views;
6594
6595   while (view != NULL)
6596     {
6597       if (view->view_id == nd->view_id)
6598         break;
6599
6600       view = view->next;
6601     }
6602
6603   if (view == NULL)
6604     g_error ("Node has data for a view %p no longer attached to the tree",
6605              nd->view_id);
6606
6607   gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6608                                                &width, &height, &valid);
6609
6610   /* valid aggregate not checked the same as width/height, because on
6611    * btree rebalance we can have invalid nodes where all lines below
6612    * them are actually valid, due to moving lines around between
6613    * nodes.
6614    *
6615    * The guarantee is that if there are invalid lines the node is
6616    * invalid - we don't guarantee that if the node is invalid there
6617    * are invalid lines.
6618    */
6619
6620   if (nd->width != width ||
6621       nd->height != height ||
6622       (nd->valid && !valid))
6623     {
6624       g_error ("Node aggregates for view %p are invalid:\n"
6625                "Are (%d,%d,%s), should be (%d,%d,%s)",
6626                nd->view_id,
6627                nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6628                width, height, valid ? "TRUE" : "FALSE");
6629     }
6630 }
6631
6632 static void
6633 gtk_text_btree_node_check_consistency (GtkTextBTree     *tree,
6634                                        GtkTextBTreeNode *node)
6635 {
6636   GtkTextBTreeNode *childnode;
6637   Summary *summary, *summary2;
6638   GtkTextLine *line;
6639   GtkTextLineSegment *segPtr;
6640   int num_children, num_lines, num_chars, toggle_count, min_children;
6641   GtkTextLineData *ld;
6642   NodeData *nd;
6643
6644   if (node->parent != NULL)
6645     {
6646       min_children = MIN_CHILDREN;
6647     }
6648   else if (node->level > 0)
6649     {
6650       min_children = 2;
6651     }
6652   else  {
6653     min_children = 1;
6654   }
6655   if ((node->num_children < min_children)
6656       || (node->num_children > MAX_CHILDREN))
6657     {
6658       g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6659                node->num_children);
6660     }
6661
6662   nd = node->node_data;
6663   while (nd != NULL)
6664     {
6665       gtk_text_btree_node_view_check_consistency (tree, node, nd);
6666       nd = nd->next;
6667     }
6668
6669   num_children = 0;
6670   num_lines = 0;
6671   num_chars = 0;
6672   if (node->level == 0)
6673     {
6674       for (line = node->children.line; line != NULL;
6675            line = line->next)
6676         {
6677           if (line->parent != node)
6678             {
6679               g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6680             }
6681           if (line->segments == NULL)
6682             {
6683               g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6684             }
6685
6686           ld = line->views;
6687           while (ld != NULL)
6688             {
6689               /* Just ensuring we don't segv while doing this loop */
6690
6691               ld = ld->next;
6692             }
6693
6694           for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6695             {
6696               if (segPtr->type->checkFunc != NULL)
6697                 {
6698                   (*segPtr->type->checkFunc)(segPtr, line);
6699                 }
6700               if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6701                   && (segPtr->next != NULL)
6702                   && (segPtr->next->byte_count == 0)
6703                   && (segPtr->next->type->leftGravity))
6704                 {
6705                   g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6706                 }
6707               if ((segPtr->next == NULL)
6708                   && (segPtr->type != &gtk_text_char_type))
6709                 {
6710                   g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6711                 }
6712
6713               num_chars += segPtr->char_count;
6714             }
6715
6716           num_children++;
6717           num_lines++;
6718         }
6719     }
6720   else
6721     {
6722       for (childnode = node->children.node; childnode != NULL;
6723            childnode = childnode->next)
6724         {
6725           if (childnode->parent != node)
6726             {
6727               g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6728             }
6729           if (childnode->level != (node->level-1))
6730             {
6731               g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6732                        node->level, childnode->level);
6733             }
6734           gtk_text_btree_node_check_consistency (tree, childnode);
6735           for (summary = childnode->summary; summary != NULL;
6736                summary = summary->next)
6737             {
6738               for (summary2 = node->summary; ;
6739                    summary2 = summary2->next)
6740                 {
6741                   if (summary2 == NULL)
6742                     {
6743                       if (summary->info->tag_root == node)
6744                         {
6745                           break;
6746                         }
6747                       g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6748                                summary->info->tag->name,
6749                                "present in parent summaries");
6750                     }
6751                   if (summary->info == summary2->info)
6752                     {
6753                       break;
6754                     }
6755                 }
6756             }
6757           num_children++;
6758           num_lines += childnode->num_lines;
6759           num_chars += childnode->num_chars;
6760         }
6761     }
6762   if (num_children != node->num_children)
6763     {
6764       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6765                num_children, node->num_children);
6766     }
6767   if (num_lines != node->num_lines)
6768     {
6769       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6770                num_lines, node->num_lines);
6771     }
6772   if (num_chars != node->num_chars)
6773     {
6774       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6775                num_chars, node->num_chars);
6776     }
6777
6778   for (summary = node->summary; summary != NULL;
6779        summary = summary->next)
6780     {
6781       if (summary->info->toggle_count == summary->toggle_count)
6782         {
6783           g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6784                    summary->info->tag->name);
6785         }
6786       toggle_count = 0;
6787       if (node->level == 0)
6788         {
6789           for (line = node->children.line; line != NULL;
6790                line = line->next)
6791             {
6792               for (segPtr = line->segments; segPtr != NULL;
6793                    segPtr = segPtr->next)
6794                 {
6795                   if ((segPtr->type != &gtk_text_toggle_on_type)
6796                       && (segPtr->type != &gtk_text_toggle_off_type))
6797                     {
6798                       continue;
6799                     }
6800                   if (segPtr->body.toggle.info == summary->info)
6801                     {
6802                       if (!segPtr->body.toggle.inNodeCounts)
6803                         g_error ("Toggle segment not in the node counts");
6804
6805                       toggle_count ++;
6806                     }
6807                 }
6808             }
6809         }
6810       else
6811         {
6812           for (childnode = node->children.node;
6813                childnode != NULL;
6814                childnode = childnode->next)
6815             {
6816               for (summary2 = childnode->summary;
6817                    summary2 != NULL;
6818                    summary2 = summary2->next)
6819                 {
6820                   if (summary2->info == summary->info)
6821                     {
6822                       toggle_count += summary2->toggle_count;
6823                     }
6824                 }
6825             }
6826         }
6827       if (toggle_count != summary->toggle_count)
6828         {
6829           g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6830                    toggle_count, summary->toggle_count);
6831         }
6832       for (summary2 = summary->next; summary2 != NULL;
6833            summary2 = summary2->next)
6834         {
6835           if (summary2->info == summary->info)
6836             {
6837               g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6838                        summary->info->tag->name);
6839             }
6840         }
6841     }
6842 }
6843
6844 static void
6845 listify_foreach (GtkTextTag *tag, gpointer user_data)
6846 {
6847   GSList** listp = user_data;
6848
6849   *listp = g_slist_prepend (*listp, tag);
6850 }
6851
6852 static GSList*
6853 list_of_tags (GtkTextTagTable *table)
6854 {
6855   GSList *list = NULL;
6856
6857   gtk_text_tag_table_foreach (table, listify_foreach, &list);
6858
6859   return list;
6860 }
6861
6862 void
6863 _gtk_text_btree_check (GtkTextBTree *tree)
6864 {
6865   Summary *summary;
6866   GtkTextBTreeNode *node;
6867   GtkTextLine *line;
6868   GtkTextLineSegment *seg;
6869   GtkTextTag *tag;
6870   GSList *all_tags, *taglist = NULL;
6871   int count;
6872   GtkTextTagInfo *info;
6873
6874   /*
6875    * Make sure that the tag toggle counts and the tag root pointers are OK.
6876    */
6877   all_tags = list_of_tags (tree->table);
6878   for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6879     {
6880       tag = taglist->data;
6881       info = gtk_text_btree_get_existing_tag_info (tree, tag);
6882       if (info != NULL)
6883         {
6884           node = info->tag_root;
6885           if (node == NULL)
6886             {
6887               if (info->toggle_count != 0)
6888                 {
6889                   g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6890                            tag->name, info->toggle_count);
6891                 }
6892               continue;         /* no ranges for the tag */
6893             }
6894           else if (info->toggle_count == 0)
6895             {
6896               g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6897                        tag->name);
6898             }
6899           else if (info->toggle_count & 1)
6900             {
6901               g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6902                        tag->name, info->toggle_count);
6903             }
6904           for (summary = node->summary; summary != NULL;
6905                summary = summary->next)
6906             {
6907               if (summary->info->tag == tag)
6908                 {
6909                   g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6910                 }
6911             }
6912           count = 0;
6913           if (node->level > 0)
6914             {
6915               for (node = node->children.node ; node != NULL ;
6916                    node = node->next)
6917                 {
6918                   for (summary = node->summary; summary != NULL;
6919                        summary = summary->next)
6920                     {
6921                       if (summary->info->tag == tag)
6922                         {
6923                           count += summary->toggle_count;
6924                         }
6925                     }
6926                 }
6927             }
6928           else
6929             {
6930               GtkTextLineSegmentClass * last = NULL;
6931
6932               for (line = node->children.line ; line != NULL ;
6933                    line = line->next)
6934                 {
6935                   for (seg = line->segments; seg != NULL;
6936                        seg = seg->next)
6937                     {
6938                       if ((seg->type == &gtk_text_toggle_on_type ||
6939                            seg->type == &gtk_text_toggle_off_type) &&
6940                           seg->body.toggle.info->tag == tag)
6941                         {
6942                           if (last == seg->type)
6943                             g_error ("Two consecutive toggles on or off weren't merged");
6944                           if (!seg->body.toggle.inNodeCounts)
6945                             g_error ("Toggle segment not in the node counts");
6946
6947                           last = seg->type;
6948
6949                           count++;
6950                         }
6951                     }
6952                 }
6953             }
6954           if (count != info->toggle_count)
6955             {
6956               g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6957                        info->toggle_count, tag->name, count);
6958             }
6959         }
6960     }
6961
6962   g_slist_free (all_tags);
6963
6964   /*
6965    * Call a recursive procedure to do the main body of checks.
6966    */
6967
6968   node = tree->root_node;
6969   gtk_text_btree_node_check_consistency (tree, tree->root_node);
6970
6971   /*
6972    * Make sure that there are at least two lines in the text and
6973    * that the last line has no characters except a newline.
6974    */
6975
6976   if (node->num_lines < 2)
6977     {
6978       g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6979     }
6980   if (node->num_chars < 2)
6981     {
6982       g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6983     }
6984   while (node->level > 0)
6985     {
6986       node = node->children.node;
6987       while (node->next != NULL)
6988         {
6989           node = node->next;
6990         }
6991     }
6992   line = node->children.line;
6993   while (line->next != NULL)
6994     {
6995       line = line->next;
6996     }
6997   seg = line->segments;
6998   while ((seg->type == &gtk_text_toggle_off_type)
6999          || (seg->type == &gtk_text_right_mark_type)
7000          || (seg->type == &gtk_text_left_mark_type))
7001     {
7002       /*
7003        * It's OK to toggle a tag off in the last line, but
7004        * not to start a new range.  It's also OK to have marks
7005        * in the last line.
7006        */
7007
7008       seg = seg->next;
7009     }
7010   if (seg->type != &gtk_text_char_type)
7011     {
7012       g_error ("_gtk_text_btree_check: last line has bogus segment type");
7013     }
7014   if (seg->next != NULL)
7015     {
7016       g_error ("_gtk_text_btree_check: last line has too many segments");
7017     }
7018   if (seg->byte_count != 1)
7019     {
7020       g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7021                seg->byte_count);
7022     }
7023   if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7024     {
7025       g_error ("_gtk_text_btree_check: last line had bad value: %s",
7026                seg->body.chars);
7027     }
7028 }
7029
7030 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7031 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7032 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7033 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7034
7035 void
7036 _gtk_text_btree_spew (GtkTextBTree *tree)
7037 {
7038   GtkTextLine * line;
7039   int real_line;
7040
7041   printf ("%d lines in tree %p\n",
7042           _gtk_text_btree_line_count (tree), tree);
7043
7044   line = _gtk_text_btree_get_line (tree, 0, &real_line);
7045
7046   while (line != NULL)
7047     {
7048       _gtk_text_btree_spew_line (tree, line);
7049       line = _gtk_text_line_next (line);
7050     }
7051
7052   printf ("=================== Tag information\n");
7053
7054   {
7055     GSList * list;
7056
7057     list = tree->tag_infos;
7058
7059     while (list != NULL)
7060       {
7061         GtkTextTagInfo *info;
7062
7063         info = list->data;
7064
7065         printf ("  tag `%s': root at %p, toggle count %d\n",
7066                 info->tag->name, info->tag_root, info->toggle_count);
7067
7068         list = g_slist_next (list);
7069       }
7070
7071     if (tree->tag_infos == NULL)
7072       {
7073         printf ("  (no tags in the tree)\n");
7074       }
7075   }
7076
7077   printf ("=================== Tree nodes\n");
7078
7079   {
7080     _gtk_text_btree_spew_node (tree->root_node, 0);
7081   }
7082 }
7083
7084 void
7085 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7086 {
7087   gchar * spaces;
7088   GtkTextLineSegment *seg;
7089
7090   spaces = g_strnfill (indent, ' ');
7091
7092   printf ("%sline %p chars %d bytes %d\n",
7093           spaces, line,
7094           _gtk_text_line_char_count (line),
7095           _gtk_text_line_byte_count (line));
7096
7097   seg = line->segments;
7098   while (seg != NULL)
7099     {
7100       if (seg->type == &gtk_text_char_type)
7101         {
7102           gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7103           gchar* s;
7104           s = str;
7105           while (*s)
7106             {
7107               if (*s == '\n' || *s == '\r')
7108                 *s = '\\';
7109               ++s;
7110             }
7111           printf ("%s chars `%s'...\n", spaces, str);
7112           g_free (str);
7113         }
7114       else if (seg->type == &gtk_text_right_mark_type)
7115         {
7116           printf ("%s right mark `%s' visible: %d\n",
7117                   spaces,
7118                   seg->body.mark.name,
7119                   seg->body.mark.visible);
7120         }
7121       else if (seg->type == &gtk_text_left_mark_type)
7122         {
7123           printf ("%s left mark `%s' visible: %d\n",
7124                   spaces,
7125                   seg->body.mark.name,
7126                   seg->body.mark.visible);
7127         }
7128       else if (seg->type == &gtk_text_toggle_on_type ||
7129                seg->type == &gtk_text_toggle_off_type)
7130         {
7131           printf ("%s tag `%s' %s\n",
7132                   spaces, seg->body.toggle.info->tag->name,
7133                   seg->type == &gtk_text_toggle_off_type ? "off" : "on");
7134         }
7135
7136       seg = seg->next;
7137     }
7138
7139   g_free (spaces);
7140 }
7141
7142 void
7143 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7144 {
7145   gchar * spaces;
7146   GtkTextBTreeNode *iter;
7147   Summary *s;
7148
7149   spaces = g_strnfill (indent, ' ');
7150
7151   printf ("%snode %p level %d children %d lines %d chars %d\n",
7152           spaces, node, node->level,
7153           node->num_children, node->num_lines, node->num_chars);
7154
7155   s = node->summary;
7156   while (s)
7157     {
7158       printf ("%s %d toggles of `%s' below this node\n",
7159               spaces, s->toggle_count, s->info->tag->name);
7160       s = s->next;
7161     }
7162
7163   g_free (spaces);
7164
7165   if (node->level > 0)
7166     {
7167       iter = node->children.node;
7168       while (iter != NULL)
7169         {
7170           _gtk_text_btree_spew_node (iter, indent + 2);
7171
7172           iter = iter->next;
7173         }
7174     }
7175   else
7176     {
7177       GtkTextLine *line = node->children.line;
7178       while (line != NULL)
7179         {
7180           _gtk_text_btree_spew_line_short (line, indent + 2);
7181
7182           line = line->next;
7183         }
7184     }
7185 }
7186
7187 void
7188 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7189 {
7190   GtkTextLineSegment * seg;
7191
7192   printf ("%4d| line: %p parent: %p next: %p\n",
7193           _gtk_text_line_get_number (line), line, line->parent, line->next);
7194
7195   seg = line->segments;
7196
7197   while (seg != NULL)
7198     {
7199       _gtk_text_btree_spew_segment (tree, seg);
7200       seg = seg->next;
7201     }
7202 }
7203
7204 void
7205 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7206 {
7207   printf ("     segment: %p type: %s bytes: %d chars: %d\n",
7208           seg, seg->type->name, seg->byte_count, seg->char_count);
7209
7210   if (seg->type == &gtk_text_char_type)
7211     {
7212       gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7213       printf ("       `%s'\n", str);
7214       g_free (str);
7215     }
7216   else if (seg->type == &gtk_text_right_mark_type)
7217     {
7218       printf ("       right mark `%s' visible: %d not_deleteable: %d\n",
7219               seg->body.mark.name,
7220               seg->body.mark.visible,
7221               seg->body.mark.not_deleteable);
7222     }
7223   else if (seg->type == &gtk_text_left_mark_type)
7224     {
7225       printf ("       left mark `%s' visible: %d not_deleteable: %d\n",
7226               seg->body.mark.name,
7227               seg->body.mark.visible,
7228               seg->body.mark.not_deleteable);
7229     }
7230   else if (seg->type == &gtk_text_toggle_on_type ||
7231            seg->type == &gtk_text_toggle_off_type)
7232     {
7233       printf ("       tag `%s' priority %d\n",
7234               seg->body.toggle.info->tag->name,
7235               seg->body.toggle.info->tag->priority);
7236     }
7237 }
7238
7239 #define __GTK_TEXT_BTREE_C__
7240 #include "gtkaliasdef.c"