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