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