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

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