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