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