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   gboolean cursor_only;
2664
2665   _gtk_text_btree_get_iter_at_mark (mark->body.mark.tree,
2666                                    &iter,
2667                                    mark->body.mark.obj);
2668
2669   end = iter;
2670   gtk_text_iter_forward_char (&end);
2671
2672   DV (g_print ("invalidating due to moving visible mark (%s)\n", G_STRLOC));
2673   cursor_only = mark == mark->body.mark.tree->insert_mark->segment;
2674   _gtk_text_btree_invalidate_region (mark->body.mark.tree, &iter, &end, cursor_only);
2675 }
2676
2677 static void
2678 redisplay_mark_if_visible (GtkTextLineSegment *mark)
2679 {
2680   if (!mark->body.mark.visible)
2681     return;
2682   else
2683     redisplay_mark (mark);
2684 }
2685
2686 static void
2687 ensure_not_off_end (GtkTextBTree *tree,
2688                     GtkTextLineSegment *mark,
2689                     GtkTextIter *iter)
2690 {
2691   if (gtk_text_iter_get_line (iter) == _gtk_text_btree_line_count (tree))
2692     gtk_text_iter_backward_char (iter);
2693 }
2694
2695 static GtkTextLineSegment*
2696 real_set_mark (GtkTextBTree      *tree,
2697                GtkTextMark       *existing_mark,
2698                const gchar       *name,
2699                gboolean           left_gravity,
2700                const GtkTextIter *where,
2701                gboolean           should_exist,
2702                gboolean           redraw_selections)
2703 {
2704   GtkTextLineSegment *mark;
2705   GtkTextIter iter;
2706
2707   g_return_val_if_fail (tree != NULL, NULL);
2708   g_return_val_if_fail (where != NULL, NULL);
2709   g_return_val_if_fail (_gtk_text_iter_get_btree (where) == tree, NULL);
2710
2711   if (existing_mark)
2712     {
2713       if (gtk_text_mark_get_buffer (existing_mark) != NULL)
2714         mark = existing_mark->segment;
2715       else
2716         mark = NULL;
2717     }
2718   else if (name != NULL)
2719     mark = g_hash_table_lookup (tree->mark_table,
2720                                 name);
2721   else
2722     mark = NULL;
2723
2724   if (should_exist && mark == NULL)
2725     {
2726       g_warning ("No mark `%s' exists!", name);
2727       return NULL;
2728     }
2729
2730   /* OK if !should_exist and it does already exist, in that case
2731    * we just move it.
2732    */
2733
2734   iter = *where;
2735
2736   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2737     _gtk_text_iter_check (&iter);
2738
2739   if (mark != NULL)
2740     {
2741       if (redraw_selections &&
2742           (mark == tree->insert_mark->segment ||
2743            mark == tree->selection_bound_mark->segment))
2744         {
2745           GtkTextIter old_pos;
2746
2747           _gtk_text_btree_get_iter_at_mark (tree, &old_pos,
2748                                            mark->body.mark.obj);
2749           redisplay_region (tree, &old_pos, where, TRUE);
2750         }
2751
2752       /*
2753        * don't let visible marks be after the final newline of the
2754        *  file.
2755        */
2756
2757       if (mark->body.mark.visible)
2758         {
2759           ensure_not_off_end (tree, mark, &iter);
2760         }
2761
2762       /* Redraw the mark's old location. */
2763       redisplay_mark_if_visible (mark);
2764
2765       /* Unlink mark from its current location.
2766          This could hose our iterator... */
2767       gtk_text_btree_unlink_segment (tree, mark,
2768                                      mark->body.mark.line);
2769       mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2770       g_assert (mark->body.mark.line == _gtk_text_iter_get_text_line (&iter));
2771
2772       segments_changed (tree); /* make sure the iterator recomputes its
2773                                   segment */
2774     }
2775   else
2776     {
2777       if (existing_mark)
2778         g_object_ref (existing_mark);
2779       else
2780         existing_mark = gtk_text_mark_new (name, left_gravity);
2781
2782       mark = existing_mark->segment;
2783       _gtk_mark_segment_set_tree (mark, tree);
2784
2785       mark->body.mark.line = _gtk_text_iter_get_text_line (&iter);
2786
2787       if (mark->body.mark.name)
2788         g_hash_table_insert (tree->mark_table,
2789                              mark->body.mark.name,
2790                              mark);
2791     }
2792
2793   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2794     _gtk_text_iter_check (&iter);
2795
2796   /* Link mark into new location */
2797   gtk_text_btree_link_segment (mark, &iter);
2798
2799   /* Invalidate some iterators. */
2800   segments_changed (tree);
2801
2802   /*
2803    * update the screen at the mark's new location.
2804    */
2805
2806   redisplay_mark_if_visible (mark);
2807
2808   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2809     _gtk_text_iter_check (&iter);
2810
2811   if (gtk_debug_flags & GTK_DEBUG_TEXT)
2812     _gtk_text_btree_check (tree);
2813
2814   return mark;
2815 }
2816
2817
2818 GtkTextMark*
2819 _gtk_text_btree_set_mark (GtkTextBTree *tree,
2820                          GtkTextMark  *existing_mark,
2821                          const gchar *name,
2822                          gboolean left_gravity,
2823                          const GtkTextIter *iter,
2824                          gboolean should_exist)
2825 {
2826   GtkTextLineSegment *seg;
2827
2828   seg = real_set_mark (tree, existing_mark,
2829                        name, left_gravity, iter, should_exist,
2830                        TRUE);
2831
2832   return seg ? seg->body.mark.obj : NULL;
2833 }
2834
2835 gboolean
2836 _gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2837                                      GtkTextIter  *start,
2838                                      GtkTextIter  *end)
2839 {
2840   GtkTextIter tmp_start, tmp_end;
2841
2842   _gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2843                                    tree->insert_mark);
2844   _gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2845                                    tree->selection_bound_mark);
2846
2847   if (gtk_text_iter_equal (&tmp_start, &tmp_end))
2848     {
2849       if (start)
2850         *start = tmp_start;
2851
2852       if (end)
2853         *end = tmp_end;
2854
2855       return FALSE;
2856     }
2857   else
2858     {
2859       gtk_text_iter_order (&tmp_start, &tmp_end);
2860
2861       if (start)
2862         *start = tmp_start;
2863
2864       if (end)
2865         *end = tmp_end;
2866
2867       return TRUE;
2868     }
2869 }
2870
2871 void
2872 _gtk_text_btree_place_cursor (GtkTextBTree      *tree,
2873                              const GtkTextIter *iter)
2874 {
2875   _gtk_text_btree_select_range (tree, iter, iter);
2876 }
2877
2878 void
2879 _gtk_text_btree_select_range (GtkTextBTree      *tree,
2880                               const GtkTextIter *ins,
2881                               const GtkTextIter *bound)
2882 {
2883   GtkTextIter old_ins, old_bound;
2884
2885   _gtk_text_btree_get_iter_at_mark (tree, &old_ins,
2886                                     tree->insert_mark);
2887   _gtk_text_btree_get_iter_at_mark (tree, &old_bound,
2888                                     tree->selection_bound_mark);
2889
2890   /* Check if it's no-op since gtk_text_buffer_place_cursor()
2891    * also calls this, and this will redraw the cursor line. */
2892   if (!gtk_text_iter_equal (&old_ins, ins) ||
2893       !gtk_text_iter_equal (&old_bound, bound))
2894     {
2895       redisplay_region (tree, &old_ins, &old_bound, TRUE);
2896
2897       /* Move insert AND selection_bound before we redisplay */
2898       real_set_mark (tree, tree->insert_mark,
2899                      "insert", FALSE, ins, TRUE, FALSE);
2900       real_set_mark (tree, tree->selection_bound_mark,
2901                      "selection_bound", FALSE, bound, TRUE, FALSE);
2902
2903       redisplay_region (tree, ins, bound, TRUE);
2904     }
2905 }
2906
2907
2908 void
2909 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2910                                     const gchar *name)
2911 {
2912   GtkTextMark *mark;
2913
2914   g_return_if_fail (tree != NULL);
2915   g_return_if_fail (name != NULL);
2916
2917   mark = g_hash_table_lookup (tree->mark_table,
2918                               name);
2919
2920   _gtk_text_btree_remove_mark (tree, mark);
2921 }
2922
2923 void
2924 _gtk_text_btree_release_mark_segment (GtkTextBTree       *tree,
2925                                       GtkTextLineSegment *segment)
2926 {
2927
2928   if (segment->body.mark.name)
2929     g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2930
2931   segment->body.mark.tree = NULL;
2932   segment->body.mark.line = NULL;
2933
2934   /* Remove the ref on the mark, which frees segment as a side effect
2935    * if this is the last reference.
2936    */
2937   g_object_unref (segment->body.mark.obj);
2938 }
2939
2940 void
2941 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2942                              GtkTextMark *mark)
2943 {
2944   GtkTextLineSegment *segment;
2945
2946   g_return_if_fail (mark != NULL);
2947   g_return_if_fail (tree != NULL);
2948
2949   segment = mark->segment;
2950
2951   if (segment->body.mark.not_deleteable)
2952     {
2953       g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2954       return;
2955     }
2956
2957   /* This calls cleanup_line and segments_changed */
2958   gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2959
2960   _gtk_text_btree_release_mark_segment (tree, segment);
2961 }
2962
2963 gboolean
2964 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2965                                 GtkTextMark *segment)
2966 {
2967   return segment == tree->insert_mark;
2968 }
2969
2970 gboolean
2971 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2972                                          GtkTextMark *segment)
2973 {
2974   return segment == tree->selection_bound_mark;
2975 }
2976
2977 GtkTextMark *
2978 _gtk_text_btree_get_insert (GtkTextBTree *tree)
2979 {
2980   return tree->insert_mark;
2981 }
2982
2983 GtkTextMark *
2984 _gtk_text_btree_get_selection_bound (GtkTextBTree *tree)
2985 {
2986   return tree->selection_bound_mark;
2987 }
2988
2989 GtkTextMark*
2990 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2991                                   const gchar *name)
2992 {
2993   GtkTextLineSegment *seg;
2994
2995   g_return_val_if_fail (tree != NULL, NULL);
2996   g_return_val_if_fail (name != NULL, NULL);
2997
2998   seg = g_hash_table_lookup (tree->mark_table, name);
2999
3000   return seg ? seg->body.mark.obj : NULL;
3001 }
3002
3003 /**
3004  * gtk_text_mark_set_visible:
3005  * @mark: a #GtkTextMark
3006  * @setting: visibility of mark
3007  *
3008  * Sets the visibility of @mark; the insertion point is normally
3009  * visible, i.e. you can see it as a vertical bar. Also, the text
3010  * widget uses a visible mark to indicate where a drop will occur when
3011  * dragging-and-dropping text. Most other marks are not visible.
3012  * Marks are not visible by default.
3013  *
3014  **/
3015 void
3016 gtk_text_mark_set_visible (GtkTextMark       *mark,
3017                            gboolean           setting)
3018 {
3019   GtkTextLineSegment *seg;
3020
3021   g_return_if_fail (mark != NULL);
3022
3023   seg = mark->segment;
3024
3025   if (seg->body.mark.visible == setting)
3026     return;
3027   else
3028     {
3029       seg->body.mark.visible = setting;
3030
3031       if (seg->body.mark.tree)
3032         redisplay_mark (seg);
3033     }
3034 }
3035
3036 GtkTextLine*
3037 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
3038                                         GtkTextTag *tag)
3039 {
3040   GtkTextBTreeNode *node;
3041   GtkTextTagInfo *info;
3042
3043   g_return_val_if_fail (tree != NULL, NULL);
3044
3045   if (tag != NULL)
3046     {
3047       info = gtk_text_btree_get_existing_tag_info (tree, tag);
3048
3049       if (info == NULL)
3050         return NULL;
3051
3052       if (info->tag_root == NULL)
3053         return NULL;
3054
3055       node = info->tag_root;
3056
3057       /* We know the tag root has instances of the given
3058          tag below it */
3059
3060     continue_outer_loop:
3061       g_assert (node != NULL);
3062       while (node->level > 0)
3063         {
3064           g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3065           node = node->children.node;
3066           while (node != NULL)
3067             {
3068               if (gtk_text_btree_node_has_tag (node, tag))
3069                 goto continue_outer_loop;
3070
3071               node = node->next;
3072             }
3073           g_assert (node != NULL);
3074         }
3075
3076       g_assert (node != NULL); /* The tag summaries said some node had
3077                                   tag toggles... */
3078
3079       g_assert (node->level == 0);
3080
3081       return node->children.line;
3082     }
3083   else
3084     {
3085       /* Looking for any tag at all (tag == NULL).
3086          Unfortunately this can't be done in a simple and efficient way
3087          right now; so I'm just going to return the
3088          first line in the btree. FIXME */
3089       return _gtk_text_btree_get_line (tree, 0, NULL);
3090     }
3091 }
3092
3093 GtkTextLine*
3094 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3095                                        GtkTextTag *tag)
3096 {
3097   GtkTextBTreeNode *node;
3098   GtkTextBTreeNode *last_node;
3099   GtkTextLine *line;
3100   GtkTextTagInfo *info;
3101
3102   g_return_val_if_fail (tree != NULL, NULL);
3103
3104   if (tag != NULL)
3105     {
3106       info = gtk_text_btree_get_existing_tag_info (tree, tag);
3107
3108       if (info->tag_root == NULL)
3109         return NULL;
3110
3111       node = info->tag_root;
3112       /* We know the tag root has instances of the given
3113          tag below it */
3114
3115       while (node->level > 0)
3116         {
3117           g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3118           last_node = NULL;
3119           node = node->children.node;
3120           while (node != NULL)
3121             {
3122               if (gtk_text_btree_node_has_tag (node, tag))
3123                 last_node = node;
3124               node = node->next;
3125             }
3126
3127           node = last_node;
3128         }
3129
3130       g_assert (node != NULL); /* The tag summaries said some node had
3131                                   tag toggles... */
3132
3133       g_assert (node->level == 0);
3134
3135       /* Find the last line in this node */
3136       line = node->children.line;
3137       while (line->next != NULL)
3138         line = line->next;
3139
3140       return line;
3141     }
3142   else
3143     {
3144       /* This search can't be done efficiently at the moment,
3145          at least not without complexity.
3146          So, we just return the last line.
3147       */
3148       return _gtk_text_btree_get_end_iter_line (tree);
3149     }
3150 }
3151
3152
3153 /*
3154  * Lines
3155  */
3156
3157 gint
3158 _gtk_text_line_get_number (GtkTextLine *line)
3159 {
3160   GtkTextLine *line2;
3161   GtkTextBTreeNode *node, *parent, *node2;
3162   int index;
3163
3164   /*
3165    * First count how many lines precede this one in its level-0
3166    * GtkTextBTreeNode.
3167    */
3168
3169   node = line->parent;
3170   index = 0;
3171   for (line2 = node->children.line; line2 != line;
3172        line2 = line2->next)
3173     {
3174       if (line2 == NULL)
3175         {
3176           g_error ("gtk_text_btree_line_number couldn't find line");
3177         }
3178       index += 1;
3179     }
3180
3181   /*
3182    * Now work up through the levels of the tree one at a time,
3183    * counting how many lines are in GtkTextBTreeNodes preceding the current
3184    * GtkTextBTreeNode.
3185    */
3186
3187   for (parent = node->parent ; parent != NULL;
3188        node = parent, parent = parent->parent)
3189     {
3190       for (node2 = parent->children.node; node2 != node;
3191            node2 = node2->next)
3192         {
3193           if (node2 == NULL)
3194             {
3195               g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3196             }
3197           index += node2->num_lines;
3198         }
3199     }
3200   return index;
3201 }
3202
3203 static GtkTextLineSegment*
3204 find_toggle_segment_before_char (GtkTextLine *line,
3205                                  gint char_in_line,
3206                                  GtkTextTag *tag)
3207 {
3208   GtkTextLineSegment *seg;
3209   GtkTextLineSegment *toggle_seg;
3210   int index;
3211
3212   toggle_seg = NULL;
3213   index = 0;
3214   seg = line->segments;
3215   while ( (index + seg->char_count) <= char_in_line )
3216     {
3217       if (((seg->type == &gtk_text_toggle_on_type)
3218            || (seg->type == &gtk_text_toggle_off_type))
3219           && (seg->body.toggle.info->tag == tag))
3220         toggle_seg = seg;
3221
3222       index += seg->char_count;
3223       seg = seg->next;
3224     }
3225
3226   return toggle_seg;
3227 }
3228
3229 static GtkTextLineSegment*
3230 find_toggle_segment_before_byte (GtkTextLine *line,
3231                                  gint byte_in_line,
3232                                  GtkTextTag *tag)
3233 {
3234   GtkTextLineSegment *seg;
3235   GtkTextLineSegment *toggle_seg;
3236   int index;
3237
3238   toggle_seg = NULL;
3239   index = 0;
3240   seg = line->segments;
3241   while ( (index + seg->byte_count) <= byte_in_line )
3242     {
3243       if (((seg->type == &gtk_text_toggle_on_type)
3244            || (seg->type == &gtk_text_toggle_off_type))
3245           && (seg->body.toggle.info->tag == tag))
3246         toggle_seg = seg;
3247
3248       index += seg->byte_count;
3249       seg = seg->next;
3250     }
3251
3252   return toggle_seg;
3253 }
3254
3255 static gboolean
3256 find_toggle_outside_current_line (GtkTextLine *line,
3257                                   GtkTextBTree *tree,
3258                                   GtkTextTag *tag)
3259 {
3260   GtkTextBTreeNode *node;
3261   GtkTextLine *sibling_line;
3262   GtkTextLineSegment *seg;
3263   GtkTextLineSegment *toggle_seg;
3264   int toggles;
3265   GtkTextTagInfo *info = NULL;
3266
3267   /*
3268    * No toggle in this line.  Look for toggles for the tag in lines
3269    * that are predecessors of line but under the same
3270    * level-0 GtkTextBTreeNode.
3271    */
3272   toggle_seg = NULL;
3273   sibling_line = line->parent->children.line;
3274   while (sibling_line != line)
3275     {
3276       seg = sibling_line->segments;
3277       while (seg != NULL)
3278         {
3279           if (((seg->type == &gtk_text_toggle_on_type)
3280                || (seg->type == &gtk_text_toggle_off_type))
3281               && (seg->body.toggle.info->tag == tag))
3282             toggle_seg = seg;
3283
3284           seg = seg->next;
3285         }
3286
3287       sibling_line = sibling_line->next;
3288     }
3289
3290   if (toggle_seg != NULL)
3291     return (toggle_seg->type == &gtk_text_toggle_on_type);
3292
3293   /*
3294    * No toggle in this GtkTextBTreeNode.  Scan upwards through the ancestors of
3295    * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3296    * siblings that precede that GtkTextBTreeNode.
3297    */
3298
3299   info = gtk_text_btree_get_existing_tag_info (tree, tag);
3300
3301   if (info == NULL)
3302     return FALSE;
3303
3304   toggles = 0;
3305   node = line->parent;
3306   while (node->parent != NULL)
3307     {
3308       GtkTextBTreeNode *sibling_node;
3309
3310       sibling_node = node->parent->children.node;
3311       while (sibling_node != node)
3312         {
3313           Summary *summary;
3314
3315           summary = sibling_node->summary;
3316           while (summary != NULL)
3317             {
3318               if (summary->info == info)
3319                 toggles += summary->toggle_count;
3320
3321               summary = summary->next;
3322             }
3323
3324           sibling_node = sibling_node->next;
3325         }
3326
3327       if (node == info->tag_root)
3328         break;
3329
3330       node = node->parent;
3331     }
3332
3333   /*
3334    * An odd number of toggles means that the tag is present at the
3335    * given point.
3336    */
3337
3338   return (toggles & 1) != 0;
3339 }
3340
3341 /* FIXME this function is far too slow, for no good reason. */
3342 gboolean
3343 _gtk_text_line_char_has_tag (GtkTextLine *line,
3344                              GtkTextBTree *tree,
3345                              gint char_in_line,
3346                              GtkTextTag *tag)
3347 {
3348   GtkTextLineSegment *toggle_seg;
3349
3350   g_return_val_if_fail (line != NULL, FALSE);
3351
3352   /*
3353    * Check for toggles for the tag in the line but before
3354    * the char.  If there is one, its type indicates whether or
3355    * not the character is tagged.
3356    */
3357
3358   toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3359
3360   if (toggle_seg != NULL)
3361     return (toggle_seg->type == &gtk_text_toggle_on_type);
3362   else
3363     return find_toggle_outside_current_line (line, tree, tag);
3364 }
3365
3366 gboolean
3367 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3368                              GtkTextBTree *tree,
3369                              gint byte_in_line,
3370                              GtkTextTag *tag)
3371 {
3372   GtkTextLineSegment *toggle_seg;
3373
3374   g_return_val_if_fail (line != NULL, FALSE);
3375
3376   /*
3377    * Check for toggles for the tag in the line but before
3378    * the char.  If there is one, its type indicates whether or
3379    * not the character is tagged.
3380    */
3381
3382   toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3383
3384   if (toggle_seg != NULL)
3385     return (toggle_seg->type == &gtk_text_toggle_on_type);
3386   else
3387     return find_toggle_outside_current_line (line, tree, tag);
3388 }
3389
3390 gboolean
3391 _gtk_text_line_is_last (GtkTextLine *line,
3392                         GtkTextBTree *tree)
3393 {
3394   return line == get_last_line (tree);
3395 }
3396
3397 static void
3398 ensure_end_iter_line (GtkTextBTree *tree)
3399 {
3400   if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3401     {
3402       gint real_line;
3403
3404        /* n_lines is without the magic line at the end */
3405       g_assert (_gtk_text_btree_line_count (tree) >= 1);
3406
3407       tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3408
3409       tree->end_iter_line_stamp = tree->chars_changed_stamp;
3410     }
3411 }
3412
3413 static void
3414 ensure_end_iter_segment (GtkTextBTree *tree)
3415 {
3416   if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3417     {
3418       GtkTextLineSegment *seg;
3419       GtkTextLineSegment *last_with_chars;
3420
3421       ensure_end_iter_line (tree);
3422
3423       last_with_chars = NULL;
3424
3425       seg = tree->end_iter_line->segments;
3426       while (seg != NULL)
3427         {
3428           if (seg->char_count > 0)
3429             last_with_chars = seg;
3430           seg = seg->next;
3431         }
3432
3433       tree->end_iter_segment = last_with_chars;
3434
3435       /* We know the last char in the last line is '\n' */
3436       tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3437       tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3438
3439       tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3440
3441       g_assert (tree->end_iter_segment->type == &gtk_text_char_type);
3442       g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3443     }
3444 }
3445
3446 gboolean
3447 _gtk_text_line_contains_end_iter (GtkTextLine  *line,
3448                                   GtkTextBTree *tree)
3449 {
3450   ensure_end_iter_line (tree);
3451
3452   return line == tree->end_iter_line;
3453 }
3454
3455 gboolean
3456 _gtk_text_btree_is_end (GtkTextBTree       *tree,
3457                         GtkTextLine        *line,
3458                         GtkTextLineSegment *seg,
3459                         int                 byte_index,
3460                         int                 char_offset)
3461 {
3462   g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3463
3464   /* Do this first to avoid walking segments in most cases */
3465   if (!_gtk_text_line_contains_end_iter (line, tree))
3466     return FALSE;
3467
3468   ensure_end_iter_segment (tree);
3469
3470   if (seg != tree->end_iter_segment)
3471     return FALSE;
3472
3473   if (byte_index >= 0)
3474     return byte_index == tree->end_iter_segment_byte_index;
3475   else
3476     return char_offset == tree->end_iter_segment_char_offset;
3477 }
3478
3479 GtkTextLine*
3480 _gtk_text_line_next (GtkTextLine *line)
3481 {
3482   GtkTextBTreeNode *node;
3483
3484   if (line->next != NULL)
3485     return line->next;
3486   else
3487     {
3488       /*
3489        * This was the last line associated with the particular parent
3490        * GtkTextBTreeNode.  Search up the tree for the next GtkTextBTreeNode,
3491        * then search down from that GtkTextBTreeNode to find the first
3492        * line.
3493        */
3494
3495       node = line->parent;
3496       while (node != NULL && node->next == NULL)
3497         node = node->parent;
3498
3499       if (node == NULL)
3500         return NULL;
3501
3502       node = node->next;
3503       while (node->level > 0)
3504         {
3505           node = node->children.node;
3506         }
3507
3508       g_assert (node->children.line != line);
3509
3510       return node->children.line;
3511     }
3512 }
3513
3514 GtkTextLine*
3515 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3516 {
3517   GtkTextLine *next;
3518
3519   next = _gtk_text_line_next (line);
3520
3521   /* If we were on the end iter line, we can't go to
3522    * the last line
3523    */
3524   if (next && next->next == NULL && /* these checks are optimization only */
3525       _gtk_text_line_next (next) == NULL)
3526     return NULL;
3527
3528   return next;
3529 }
3530
3531 GtkTextLine*
3532 _gtk_text_line_previous (GtkTextLine *line)
3533 {
3534   GtkTextBTreeNode *node;
3535   GtkTextBTreeNode *node2;
3536   GtkTextLine *prev;
3537
3538   /*
3539    * Find the line under this GtkTextBTreeNode just before the starting line.
3540    */
3541   prev = line->parent->children.line;        /* First line at leaf */
3542   while (prev != line)
3543     {
3544       if (prev->next == line)
3545         return prev;
3546
3547       prev = prev->next;
3548
3549       if (prev == NULL)
3550         g_error ("gtk_text_btree_previous_line ran out of lines");
3551     }
3552
3553   /*
3554    * This was the first line associated with the particular parent
3555    * GtkTextBTreeNode.  Search up the tree for the previous GtkTextBTreeNode,
3556    * then search down from that GtkTextBTreeNode to find its last line.
3557    */
3558   for (node = line->parent; ; node = node->parent)
3559     {
3560       if (node == NULL || node->parent == NULL)
3561         return NULL;
3562       else if (node != node->parent->children.node)
3563         break;
3564     }
3565
3566   for (node2 = node->parent->children.node; ;
3567        node2 = node2->children.node)
3568     {
3569       while (node2->next != node)
3570         node2 = node2->next;
3571
3572       if (node2->level == 0)
3573         break;
3574
3575       node = NULL;
3576     }
3577
3578   for (prev = node2->children.line ; ; prev = prev->next)
3579     {
3580       if (prev->next == NULL)
3581         return prev;
3582     }
3583
3584   g_assert_not_reached ();
3585   return NULL;
3586 }
3587
3588
3589 GtkTextLineData*
3590 _gtk_text_line_data_new (GtkTextLayout *layout,
3591                          GtkTextLine   *line)
3592 {
3593   GtkTextLineData *line_data;
3594
3595   line_data = g_new (GtkTextLineData, 1);
3596
3597   line_data->view_id = layout;
3598   line_data->next = NULL;
3599   line_data->width = 0;
3600   line_data->height = 0;
3601   line_data->valid = FALSE;
3602
3603   return line_data;
3604 }
3605
3606 void
3607 _gtk_text_line_add_data (GtkTextLine     *line,
3608                          GtkTextLineData *data)
3609 {
3610   g_return_if_fail (line != NULL);
3611   g_return_if_fail (data != NULL);
3612   g_return_if_fail (data->view_id != NULL);
3613
3614   if (line->views)
3615     {
3616       data->next = line->views;
3617       line->views = data;
3618     }
3619   else
3620     {
3621       line->views = data;
3622     }
3623 }
3624
3625 gpointer
3626 _gtk_text_line_remove_data (GtkTextLine *line,
3627                            gpointer view_id)
3628 {
3629   GtkTextLineData *prev;
3630   GtkTextLineData *iter;
3631
3632   g_return_val_if_fail (line != NULL, NULL);
3633   g_return_val_if_fail (view_id != NULL, NULL);
3634
3635   prev = NULL;
3636   iter = line->views;
3637   while (iter != NULL)
3638     {
3639       if (iter->view_id == view_id)
3640         break;
3641       prev = iter;
3642       iter = iter->next;
3643     }
3644
3645   if (iter)
3646     {
3647       if (prev)
3648         prev->next = iter->next;
3649       else
3650         line->views = iter->next;
3651
3652       return iter;
3653     }
3654   else
3655     return NULL;
3656 }
3657
3658 gpointer
3659 _gtk_text_line_get_data (GtkTextLine *line,
3660                          gpointer view_id)
3661 {
3662   GtkTextLineData *iter;
3663
3664   g_return_val_if_fail (line != NULL, NULL);
3665   g_return_val_if_fail (view_id != NULL, NULL);
3666
3667   iter = line->views;
3668   while (iter != NULL)
3669     {
3670       if (iter->view_id == view_id)
3671         break;
3672       iter = iter->next;
3673     }
3674
3675   return iter;
3676 }
3677
3678 void
3679 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3680                                 GtkTextLineData *ld)
3681 {
3682   /* For now this is totally unoptimized. FIXME?
3683
3684      We could probably optimize the case where the width removed
3685      is less than the max width for the parent node,
3686      and the case where the height is unchanged when we re-wrap.
3687   */
3688
3689   g_return_if_fail (ld != NULL);
3690
3691   ld->valid = FALSE;
3692   gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3693 }
3694
3695 gint
3696 _gtk_text_line_char_count (GtkTextLine *line)
3697 {
3698   GtkTextLineSegment *seg;
3699   gint size;
3700
3701   size = 0;
3702   seg = line->segments;
3703   while (seg != NULL)
3704     {
3705       size += seg->char_count;
3706       seg = seg->next;
3707     }
3708   return size;
3709 }
3710
3711 gint
3712 _gtk_text_line_byte_count (GtkTextLine *line)
3713 {
3714   GtkTextLineSegment *seg;
3715   gint size;
3716
3717   size = 0;
3718   seg = line->segments;
3719   while (seg != NULL)
3720     {
3721       size += seg->byte_count;
3722       seg = seg->next;
3723     }
3724
3725   return size;
3726 }
3727
3728 gint
3729 _gtk_text_line_char_index (GtkTextLine *target_line)
3730 {
3731   GSList *node_stack = NULL;
3732   GtkTextBTreeNode *iter;
3733   GtkTextLine *line;
3734   gint num_chars;
3735
3736   /* Push all our parent nodes onto a stack */
3737   iter = target_line->parent;
3738
3739   g_assert (iter != NULL);
3740
3741   while (iter != NULL)
3742     {
3743       node_stack = g_slist_prepend (node_stack, iter);
3744
3745       iter = iter->parent;
3746     }
3747
3748   /* Check that we have the root node on top of the stack. */
3749   g_assert (node_stack != NULL &&
3750             node_stack->data != NULL &&
3751             ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3752
3753   /* Add up chars in all nodes before the nodes in our stack.
3754    */
3755
3756   num_chars = 0;
3757   iter = node_stack->data;
3758   while (iter != NULL)
3759     {
3760       GtkTextBTreeNode *child_iter;
3761       GtkTextBTreeNode *next_node;
3762
3763       next_node = node_stack->next ?
3764         node_stack->next->data : NULL;
3765       node_stack = g_slist_remove (node_stack, node_stack->data);
3766
3767       if (iter->level == 0)
3768         {
3769           /* stack should be empty when we're on the last node */
3770           g_assert (node_stack == NULL);
3771           break; /* Our children are now lines */
3772         }
3773
3774       g_assert (next_node != NULL);
3775       g_assert (iter != NULL);
3776       g_assert (next_node->parent == iter);
3777
3778       /* Add up chars before us in the tree */
3779       child_iter = iter->children.node;
3780       while (child_iter != next_node)
3781         {
3782           g_assert (child_iter != NULL);
3783
3784           num_chars += child_iter->num_chars;
3785
3786           child_iter = child_iter->next;
3787         }
3788
3789       iter = next_node;
3790     }
3791
3792   g_assert (iter != NULL);
3793   g_assert (iter == target_line->parent);
3794
3795   /* Since we don't store char counts in lines, only in segments, we
3796      have to iterate over the lines adding up segment char counts
3797      until we find our line.  */
3798   line = iter->children.line;
3799   while (line != target_line)
3800     {
3801       g_assert (line != NULL);
3802
3803       num_chars += _gtk_text_line_char_count (line);
3804
3805       line = line->next;
3806     }
3807
3808   g_assert (line == target_line);
3809
3810   return num_chars;
3811 }
3812
3813 GtkTextLineSegment*
3814 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3815                                gint byte_offset,
3816                                gint *seg_offset)
3817 {
3818   GtkTextLineSegment *seg;
3819   int offset;
3820
3821   g_return_val_if_fail (line != NULL, NULL);
3822
3823   offset = byte_offset;
3824   seg = line->segments;
3825
3826   while (offset >= seg->byte_count)
3827     {
3828       offset -= seg->byte_count;
3829       seg = seg->next;
3830       g_assert (seg != NULL); /* means an invalid byte index */
3831     }
3832
3833   if (seg_offset)
3834     *seg_offset = offset;
3835
3836   return seg;
3837 }
3838
3839 GtkTextLineSegment*
3840 _gtk_text_line_char_to_segment (GtkTextLine *line,
3841                                gint char_offset,
3842                                gint *seg_offset)
3843 {
3844   GtkTextLineSegment *seg;
3845   int offset;
3846
3847   g_return_val_if_fail (line != NULL, NULL);
3848
3849   offset = char_offset;
3850   seg = line->segments;
3851
3852   while (offset >= seg->char_count)
3853     {
3854       offset -= seg->char_count;
3855       seg = seg->next;
3856       g_assert (seg != NULL); /* means an invalid char index */
3857     }
3858
3859   if (seg_offset)
3860     *seg_offset = offset;
3861
3862   return seg;
3863 }
3864
3865 GtkTextLineSegment*
3866 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3867                                    gint byte_offset,
3868                                    gint *seg_offset)
3869 {
3870   GtkTextLineSegment *seg;
3871   int offset;
3872
3873   g_return_val_if_fail (line != NULL, NULL);
3874
3875   offset = byte_offset;
3876   seg = line->segments;
3877
3878   while (offset > 0 && offset >= seg->byte_count)
3879     {
3880       offset -= seg->byte_count;
3881       seg = seg->next;
3882       g_assert (seg != NULL); /* means an invalid byte index */
3883     }
3884
3885   if (seg_offset)
3886     *seg_offset = offset;
3887
3888   return seg;
3889 }
3890
3891 GtkTextLineSegment*
3892 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3893                                    gint char_offset,
3894                                    gint *seg_offset)
3895 {
3896   GtkTextLineSegment *seg;
3897   int offset;
3898
3899   g_return_val_if_fail (line != NULL, NULL);
3900
3901   offset = char_offset;
3902   seg = line->segments;
3903
3904   while (offset > 0 && offset >= seg->char_count)
3905     {
3906       offset -= seg->char_count;
3907       seg = seg->next;
3908       g_assert (seg != NULL); /* means an invalid byte index */
3909     }
3910
3911   if (seg_offset)
3912     *seg_offset = offset;
3913
3914   return seg;
3915 }
3916
3917 gint
3918 _gtk_text_line_byte_to_char (GtkTextLine *line,
3919                             gint byte_offset)
3920 {
3921   gint char_offset;
3922   GtkTextLineSegment *seg;
3923
3924   g_return_val_if_fail (line != NULL, 0);
3925   g_return_val_if_fail (byte_offset >= 0, 0);
3926
3927   char_offset = 0;
3928   seg = line->segments;
3929   while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3930                                             the next segment) */
3931     {
3932       byte_offset -= seg->byte_count;
3933       char_offset += seg->char_count;
3934       seg = seg->next;
3935       g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3936     }
3937
3938   g_assert (seg != NULL);
3939
3940   /* Now byte_offset is the offset into the current segment,
3941      and char_offset is the start of the current segment.
3942      Optimize the case where no chars use > 1 byte */
3943   if (seg->byte_count == seg->char_count)
3944     return char_offset + byte_offset;
3945   else
3946     {
3947       if (seg->type == &gtk_text_char_type)
3948         return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3949       else
3950         {
3951           g_assert (seg->char_count == 1);
3952           g_assert (byte_offset == 0);
3953
3954           return char_offset;
3955         }
3956     }
3957 }
3958
3959 gint
3960 _gtk_text_line_char_to_byte (GtkTextLine *line,
3961                             gint         char_offset)
3962 {
3963   g_warning ("FIXME not implemented");
3964
3965   return 0;
3966 }
3967
3968 /* FIXME sync with char_locate (or figure out a clean
3969    way to merge the two functions) */
3970 gboolean
3971 _gtk_text_line_byte_locate (GtkTextLine *line,
3972                             gint byte_offset,
3973                             GtkTextLineSegment **segment,
3974                             GtkTextLineSegment **any_segment,
3975                             gint *seg_byte_offset,
3976                             gint *line_byte_offset)
3977 {
3978   GtkTextLineSegment *seg;
3979   GtkTextLineSegment *after_last_indexable;
3980   GtkTextLineSegment *last_indexable;
3981   gint offset;
3982   gint bytes_in_line;
3983
3984   g_return_val_if_fail (line != NULL, FALSE);
3985   g_return_val_if_fail (byte_offset >= 0, FALSE);
3986
3987   *segment = NULL;
3988   *any_segment = NULL;
3989   bytes_in_line = 0;
3990
3991   offset = byte_offset;
3992
3993   last_indexable = NULL;
3994   after_last_indexable = line->segments;
3995   seg = line->segments;
3996
3997   /* The loop ends when we're inside a segment;
3998      last_indexable refers to the last segment
3999      we passed entirely. */
4000   while (seg && offset >= seg->byte_count)
4001     {
4002       if (seg->char_count > 0)
4003         {
4004           offset -= seg->byte_count;
4005           bytes_in_line += seg->byte_count;
4006           last_indexable = seg;
4007           after_last_indexable = last_indexable->next;
4008         }
4009
4010       seg = seg->next;
4011     }
4012
4013   if (seg == NULL)
4014     {
4015       /* We went off the end of the line */
4016       if (offset != 0)
4017         g_warning ("%s: byte index off the end of the line", G_STRLOC);
4018
4019       return FALSE;
4020     }
4021   else
4022     {
4023       *segment = seg;
4024       if (after_last_indexable != NULL)
4025         *any_segment = after_last_indexable;
4026       else
4027         *any_segment = *segment;
4028     }
4029
4030   /* Override any_segment if we're in the middle of a segment. */
4031   if (offset > 0)
4032     *any_segment = *segment;
4033
4034   *seg_byte_offset = offset;
4035
4036   g_assert (*segment != NULL);
4037   g_assert (*any_segment != NULL);
4038   g_assert (*seg_byte_offset < (*segment)->byte_count);
4039
4040   *line_byte_offset = bytes_in_line + *seg_byte_offset;
4041
4042   return TRUE;
4043 }
4044
4045 /* FIXME sync with byte_locate (or figure out a clean
4046    way to merge the two functions) */
4047 gboolean
4048 _gtk_text_line_char_locate     (GtkTextLine     *line,
4049                                 gint              char_offset,
4050                                 GtkTextLineSegment **segment,
4051                                 GtkTextLineSegment **any_segment,
4052                                 gint             *seg_char_offset,
4053                                 gint             *line_char_offset)
4054 {
4055   GtkTextLineSegment *seg;
4056   GtkTextLineSegment *after_last_indexable;
4057   GtkTextLineSegment *last_indexable;
4058   gint offset;
4059   gint chars_in_line;
4060
4061   g_return_val_if_fail (line != NULL, FALSE);
4062   g_return_val_if_fail (char_offset >= 0, FALSE);
4063
4064   *segment = NULL;
4065   *any_segment = NULL;
4066   chars_in_line = 0;
4067
4068   offset = char_offset;
4069
4070   last_indexable = NULL;
4071   after_last_indexable = line->segments;
4072   seg = line->segments;
4073
4074   /* The loop ends when we're inside a segment;
4075      last_indexable refers to the last segment
4076      we passed entirely. */
4077   while (seg && offset >= seg->char_count)
4078     {
4079       if (seg->char_count > 0)
4080         {
4081           offset -= seg->char_count;
4082           chars_in_line += seg->char_count;
4083           last_indexable = seg;
4084           after_last_indexable = last_indexable->next;
4085         }
4086
4087       seg = seg->next;
4088     }
4089
4090   if (seg == NULL)
4091     {
4092       /* end of the line */
4093       if (offset != 0)
4094         g_warning ("%s: char offset off the end of the line", G_STRLOC);
4095
4096       return FALSE;
4097     }
4098   else
4099     {
4100       *segment = seg;
4101       if (after_last_indexable != NULL)
4102         *any_segment = after_last_indexable;
4103       else
4104         *any_segment = *segment;
4105     }
4106
4107   /* Override any_segment if we're in the middle of a segment. */
4108   if (offset > 0)
4109     *any_segment = *segment;
4110
4111   *seg_char_offset = offset;
4112
4113   g_assert (*segment != NULL);
4114   g_assert (*any_segment != NULL);
4115   g_assert (*seg_char_offset < (*segment)->char_count);
4116
4117   *line_char_offset = chars_in_line + *seg_char_offset;
4118
4119   return TRUE;
4120 }
4121
4122 void
4123 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4124                                     gint byte_offset,
4125                                     gint *line_char_offset,
4126                                     gint *seg_char_offset)
4127 {
4128   GtkTextLineSegment *seg;
4129   int offset;
4130
4131   g_return_if_fail (line != NULL);
4132   g_return_if_fail (byte_offset >= 0);
4133
4134   *line_char_offset = 0;
4135
4136   offset = byte_offset;
4137   seg = line->segments;
4138
4139   while (offset >= seg->byte_count)
4140     {
4141       offset -= seg->byte_count;
4142       *line_char_offset += seg->char_count;
4143       seg = seg->next;
4144       g_assert (seg != NULL); /* means an invalid char offset */
4145     }
4146
4147   g_assert (seg->char_count > 0); /* indexable. */
4148
4149   /* offset is now the number of bytes into the current segment we
4150    * want to go. Count chars into the current segment.
4151    */
4152
4153   if (seg->type == &gtk_text_char_type)
4154     {
4155       *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4156
4157       g_assert (*seg_char_offset < seg->char_count);
4158
4159       *line_char_offset += *seg_char_offset;
4160     }
4161   else
4162     {
4163       g_assert (offset == 0);
4164       *seg_char_offset = 0;
4165     }
4166 }
4167
4168 void
4169 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4170                                     gint char_offset,
4171                                     gint *line_byte_offset,
4172                                     gint *seg_byte_offset)
4173 {
4174   GtkTextLineSegment *seg;
4175   int offset;
4176
4177   g_return_if_fail (line != NULL);
4178   g_return_if_fail (char_offset >= 0);
4179
4180   *line_byte_offset = 0;
4181
4182   offset = char_offset;
4183   seg = line->segments;
4184
4185   while (offset >= seg->char_count)
4186     {
4187       offset -= seg->char_count;
4188       *line_byte_offset += seg->byte_count;
4189       seg = seg->next;
4190       g_assert (seg != NULL); /* means an invalid char offset */
4191     }
4192
4193   g_assert (seg->char_count > 0); /* indexable. */
4194
4195   /* offset is now the number of chars into the current segment we
4196      want to go. Count bytes into the current segment. */
4197
4198   if (seg->type == &gtk_text_char_type)
4199     {
4200       const char *p;
4201
4202       /* if in the last fourth of the segment walk backwards */
4203       if (seg->char_count - offset < seg->char_count / 4)
4204         p = g_utf8_offset_to_pointer (seg->body.chars + seg->byte_count,
4205                                       offset - seg->char_count);
4206       else
4207         p = g_utf8_offset_to_pointer (seg->body.chars, offset);
4208
4209       *seg_byte_offset = p - seg->body.chars;
4210
4211       g_assert (*seg_byte_offset < seg->byte_count);
4212
4213       *line_byte_offset += *seg_byte_offset;
4214     }
4215   else
4216     {
4217       g_assert (offset == 0);
4218       *seg_byte_offset = 0;
4219     }
4220 }
4221
4222 static gint
4223 node_compare (GtkTextBTreeNode *lhs,
4224               GtkTextBTreeNode *rhs)
4225 {
4226   GtkTextBTreeNode *iter;
4227   GtkTextBTreeNode *node;
4228   GtkTextBTreeNode *common_parent;
4229   GtkTextBTreeNode *parent_of_lower;
4230   GtkTextBTreeNode *parent_of_higher;
4231   gboolean lhs_is_lower;
4232   GtkTextBTreeNode *lower;
4233   GtkTextBTreeNode *higher;
4234
4235   /* This function assumes that lhs and rhs are not underneath each
4236    * other.
4237    */
4238
4239   if (lhs == rhs)
4240     return 0;
4241
4242   if (lhs->level < rhs->level)
4243     {
4244       lhs_is_lower = TRUE;
4245       lower = lhs;
4246       higher = rhs;
4247     }
4248   else
4249     {
4250       lhs_is_lower = FALSE;
4251       lower = rhs;
4252       higher = lhs;
4253     }
4254
4255   /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4256    * of the common parent we used to reach the common parent; the
4257    * ordering of these child nodes in the child list is the ordering
4258    * of lhs and rhs.
4259    */
4260
4261   /* Get on the same level (may be on same level already) */
4262   node = lower;
4263   while (node->level < higher->level)
4264     node = node->parent;
4265
4266   g_assert (node->level == higher->level);
4267
4268   g_assert (node != higher); /* Happens if lower is underneath higher */
4269
4270   /* Go up until we have two children with a common parent.
4271    */
4272   parent_of_lower = node;
4273   parent_of_higher = higher;
4274
4275   while (parent_of_lower->parent != parent_of_higher->parent)
4276     {
4277       parent_of_lower = parent_of_lower->parent;
4278       parent_of_higher = parent_of_higher->parent;
4279     }
4280
4281   g_assert (parent_of_lower->parent == parent_of_higher->parent);
4282
4283   common_parent = parent_of_lower->parent;
4284
4285   g_assert (common_parent != NULL);
4286
4287   /* See which is first in the list of common_parent's children */
4288   iter = common_parent->children.node;
4289   while (iter != NULL)
4290     {
4291       if (iter == parent_of_higher)
4292         {
4293           /* higher is less than lower */
4294
4295           if (lhs_is_lower)
4296             return 1; /* lhs > rhs */
4297           else
4298             return -1;
4299         }
4300       else if (iter == parent_of_lower)
4301         {
4302           /* lower is less than higher */
4303
4304           if (lhs_is_lower)
4305             return -1; /* lhs < rhs */
4306           else
4307             return 1;
4308         }
4309
4310       iter = iter->next;
4311     }
4312
4313   g_assert_not_reached ();
4314   return 0;
4315 }
4316
4317 /* remember that tag == NULL means "any tag" */
4318 GtkTextLine*
4319 _gtk_text_line_next_could_contain_tag (GtkTextLine  *line,
4320                                        GtkTextBTree *tree,
4321                                        GtkTextTag   *tag)
4322 {
4323   GtkTextBTreeNode *node;
4324   GtkTextTagInfo *info;
4325   gboolean below_tag_root;
4326
4327   g_return_val_if_fail (line != NULL, NULL);
4328
4329   if (gtk_debug_flags & GTK_DEBUG_TEXT)
4330     _gtk_text_btree_check (tree);
4331
4332   if (tag == NULL)
4333     {
4334       /* Right now we can only offer linear-search if the user wants
4335        * to know about any tag toggle at all.
4336        */
4337       return _gtk_text_line_next_excluding_last (line);
4338     }
4339
4340   /* Our tag summaries only have node precision, not line
4341    * precision. This means that if any line under a node could contain a
4342    * tag, then any of the others could also contain a tag.
4343    *
4344    * In the future we could have some mechanism to keep track of how
4345    * many toggles we've found under a node so far, since we have a
4346    * count of toggles under the node. But for now I'm going with KISS.
4347    */
4348
4349   /* return same-node line, if any. */
4350   if (line->next)
4351     return line->next;
4352
4353   info = gtk_text_btree_get_existing_tag_info (tree, tag);
4354   if (info == NULL)
4355     return NULL;
4356
4357   if (info->tag_root == NULL)
4358     return NULL;
4359
4360   if (info->tag_root == line->parent)
4361     return NULL; /* we were at the last line under the tag root */
4362
4363   /* We need to go up out of this node, and on to the next one with
4364      toggles for the target tag. If we're below the tag root, we need to
4365      find the next node below the tag root that has tag summaries. If
4366      we're not below the tag root, we need to see if the tag root is
4367      after us in the tree, and if so, return the first line underneath
4368      the tag root. */
4369
4370   node = line->parent;
4371   below_tag_root = FALSE;
4372   while (node != NULL)
4373     {
4374       if (node == info->tag_root)
4375         {
4376           below_tag_root = TRUE;
4377           break;
4378         }
4379
4380       node = node->parent;
4381     }
4382
4383   if (below_tag_root)
4384     {
4385       node = line->parent;
4386       while (node != info->tag_root)
4387         {
4388           if (node->next == NULL)
4389             node = node->parent;
4390           else
4391             {
4392               node = node->next;
4393
4394               if (gtk_text_btree_node_has_tag (node, tag))
4395                 goto found;
4396             }
4397         }
4398       return NULL;
4399     }
4400   else
4401     {
4402       gint ordering;
4403
4404       ordering = node_compare (line->parent, info->tag_root);
4405
4406       if (ordering < 0)
4407         {
4408           /* Tag root is ahead of us, so search there. */
4409           node = info->tag_root;
4410           goto found;
4411         }
4412       else
4413         {
4414           /* Tag root is after us, so no more lines that
4415            * could contain the tag.
4416            */
4417           return NULL;
4418         }
4419
4420       g_assert_not_reached ();
4421     }
4422
4423  found:
4424
4425   g_assert (node != NULL);
4426
4427   /* We have to find the first sub-node of this node that contains
4428    * the target tag.
4429    */
4430
4431   while (node->level > 0)
4432     {
4433       g_assert (node != NULL); /* If this fails, it likely means an
4434                                   incorrect tag summary led us on a
4435                                   wild goose chase down this branch of
4436                                   the tree. */
4437       node = node->children.node;
4438       while (node != NULL)
4439         {
4440           if (gtk_text_btree_node_has_tag (node, tag))
4441             break;
4442           node = node->next;
4443         }
4444     }
4445
4446   g_assert (node != NULL);
4447   g_assert (node->level == 0);
4448
4449   return node->children.line;
4450 }
4451
4452 static GtkTextLine*
4453 prev_line_under_node (GtkTextBTreeNode *node,
4454                       GtkTextLine      *line)
4455 {
4456   GtkTextLine *prev;
4457
4458   prev = node->children.line;
4459
4460   g_assert (prev);
4461
4462   if (prev != line)
4463     {
4464       while (prev->next != line)
4465         prev = prev->next;
4466
4467       return prev;
4468     }
4469
4470   return NULL;
4471 }
4472
4473 GtkTextLine*
4474 _gtk_text_line_previous_could_contain_tag (GtkTextLine  *line,
4475                                           GtkTextBTree *tree,
4476                                           GtkTextTag   *tag)
4477 {
4478   GtkTextBTreeNode *node;
4479   GtkTextBTreeNode *found_node = NULL;
4480   GtkTextTagInfo *info;
4481   gboolean below_tag_root;
4482   GtkTextLine *prev;
4483   GtkTextBTreeNode *line_ancestor;
4484   GtkTextBTreeNode *line_ancestor_parent;
4485
4486   /* See next_could_contain_tag () for more extensive comments
4487    * on what's going on here.
4488    */
4489
4490   g_return_val_if_fail (line != NULL, NULL);
4491
4492   if (gtk_debug_flags & GTK_DEBUG_TEXT)
4493     _gtk_text_btree_check (tree);
4494
4495   if (tag == NULL)
4496     {
4497       /* Right now we can only offer linear-search if the user wants
4498        * to know about any tag toggle at all.
4499        */
4500       return _gtk_text_line_previous (line);
4501     }
4502
4503   /* Return same-node line, if any. */
4504   prev = prev_line_under_node (line->parent, line);
4505   if (prev)
4506     return prev;
4507
4508   info = gtk_text_btree_get_existing_tag_info (tree, tag);
4509   if (info == NULL)
4510     return NULL;
4511
4512   if (info->tag_root == NULL)
4513     return NULL;
4514
4515   if (info->tag_root == line->parent)
4516     return NULL; /* we were at the first line under the tag root */
4517
4518   /* Are we below the tag root */
4519   node = line->parent;
4520   below_tag_root = FALSE;
4521   while (node != NULL)
4522     {
4523       if (node == info->tag_root)
4524         {
4525           below_tag_root = TRUE;
4526           break;
4527         }
4528
4529       node = node->parent;
4530     }
4531
4532   if (below_tag_root)
4533     {
4534       /* Look for a previous node under this tag root that has our
4535        * tag.
4536        */
4537
4538       /* this assertion holds because line->parent is not the
4539        * tag root, we are below the tag root, and the tag
4540        * root exists.
4541        */
4542       g_assert (line->parent->parent != NULL);
4543
4544       line_ancestor = line->parent;
4545       line_ancestor_parent = line->parent->parent;
4546
4547       while (line_ancestor != info->tag_root)
4548         {
4549           GSList *child_nodes = NULL;
4550           GSList *tmp;
4551
4552           /* Create reverse-order list of nodes before
4553            * line_ancestor
4554            */
4555           if (line_ancestor_parent != NULL)
4556             node = line_ancestor_parent->children.node;
4557           else
4558             node = line_ancestor;
4559
4560           while (node != line_ancestor && node != NULL)
4561             {
4562               child_nodes = g_slist_prepend (child_nodes, node);
4563
4564               node = node->next;
4565             }
4566
4567           /* Try to find a node with our tag on it in the list */
4568           tmp = child_nodes;
4569           while (tmp != NULL)
4570             {
4571               GtkTextBTreeNode *this_node = tmp->data;
4572
4573               g_assert (this_node != line_ancestor);
4574
4575               if (gtk_text_btree_node_has_tag (this_node, tag))
4576                 {
4577                   found_node = this_node;
4578                   g_slist_free (child_nodes);
4579                   goto found;
4580                 }
4581
4582               tmp = g_slist_next (tmp);
4583             }
4584
4585           g_slist_free (child_nodes);
4586
4587           /* Didn't find anything on this level; go up one level. */
4588           line_ancestor = line_ancestor_parent;
4589           line_ancestor_parent = line_ancestor->parent;
4590         }
4591
4592       /* No dice. */
4593       return NULL;
4594     }
4595   else
4596     {
4597       gint ordering;
4598
4599       ordering = node_compare (line->parent, info->tag_root);
4600
4601       if (ordering < 0)
4602         {
4603           /* Tag root is ahead of us, so no more lines
4604            * with this tag.
4605            */
4606           return NULL;
4607         }
4608       else
4609         {
4610           /* Tag root is after us, so grab last tagged
4611            * line underneath the tag root.
4612            */
4613           found_node = info->tag_root;
4614           goto found;
4615         }
4616
4617       g_assert_not_reached ();
4618     }
4619
4620  found:
4621
4622   g_assert (found_node != NULL);
4623
4624   /* We have to find the last sub-node of this node that contains
4625    * the target tag.
4626    */
4627   node = found_node;
4628
4629   while (node->level > 0)
4630     {
4631       GSList *child_nodes = NULL;
4632       GSList *iter;
4633       g_assert (node != NULL); /* If this fails, it likely means an
4634                                   incorrect tag summary led us on a
4635                                   wild goose chase down this branch of
4636                                   the tree. */
4637
4638       node = node->children.node;
4639       while (node != NULL)
4640         {
4641           child_nodes = g_slist_prepend (child_nodes, node);
4642           node = node->next;
4643         }
4644
4645       node = NULL; /* detect failure to find a child node. */
4646
4647       iter = child_nodes;
4648       while (iter != NULL)
4649         {
4650           if (gtk_text_btree_node_has_tag (iter->data, tag))
4651             {
4652               /* recurse into this node. */
4653               node = iter->data;
4654               break;
4655             }
4656
4657           iter = g_slist_next (iter);
4658         }
4659
4660       g_slist_free (child_nodes);
4661
4662       g_assert (node != NULL);
4663     }
4664
4665   g_assert (node != NULL);
4666   g_assert (node->level == 0);
4667
4668   /* this assertion is correct, but slow. */
4669   /* g_assert (node_compare (node, line->parent) < 0); */
4670
4671   /* Return last line in this node. */
4672
4673   prev = node->children.line;
4674   while (prev->next)
4675     prev = prev->next;
4676
4677   return prev;
4678 }
4679
4680 /*
4681  * Non-public function implementations
4682  */
4683
4684 static void
4685 summary_list_destroy (Summary *summary)
4686 {
4687   g_slice_free_chain (Summary, summary, next);
4688 }
4689
4690 static GtkTextLine*
4691 get_last_line (GtkTextBTree *tree)
4692 {
4693   if (tree->last_line_stamp != tree->chars_changed_stamp)
4694     {
4695       gint n_lines;
4696       GtkTextLine *line;
4697       gint real_line;
4698
4699       n_lines = _gtk_text_btree_line_count (tree);
4700
4701       g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4702
4703       line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4704
4705       tree->last_line_stamp = tree->chars_changed_stamp;
4706       tree->last_line = line;
4707     }
4708
4709   return tree->last_line;
4710 }
4711
4712 /*
4713  * Lines
4714  */
4715
4716 static GtkTextLine*
4717 gtk_text_line_new (void)
4718 {
4719   GtkTextLine *line;
4720
4721   line = g_new0(GtkTextLine, 1);
4722   line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4723   line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4724   line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4725
4726   return line;
4727 }
4728
4729 static void
4730 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4731 {
4732   GtkTextLineData *ld;
4733   GtkTextLineData *next;
4734
4735   g_return_if_fail (line != NULL);
4736
4737   ld = line->views;
4738   while (ld != NULL)
4739     {
4740       BTreeView *view;
4741
4742       view = gtk_text_btree_get_view (tree, ld->view_id);
4743
4744       g_assert (view != NULL);
4745
4746       next = ld->next;
4747       gtk_text_layout_free_line_data (view->layout, line, ld);
4748
4749       ld = next;
4750     }
4751
4752   g_free (line);
4753 }
4754
4755 static void
4756 gtk_text_line_set_parent (GtkTextLine *line,
4757                           GtkTextBTreeNode *node)
4758 {
4759   if (line->parent == node)
4760     return;
4761   line->parent = node;
4762   gtk_text_btree_node_invalidate_upward (node, NULL);
4763 }
4764
4765 static void
4766 cleanup_line (GtkTextLine *line)
4767 {
4768   GtkTextLineSegment *seg, **prev_p;
4769   gboolean changed;
4770
4771   /*
4772    * Make a pass over all of the segments in the line, giving each
4773    * a chance to clean itself up.  This could potentially change
4774    * the structure of the line, e.g. by merging two segments
4775    * together or having two segments cancel themselves;  if so,
4776    * then repeat the whole process again, since the first structure
4777    * change might make other structure changes possible.  Repeat
4778    * until eventually there are no changes.
4779    */
4780
4781   changed = TRUE;
4782   while (changed)
4783     {
4784       changed = FALSE;
4785       prev_p = &line->segments;
4786       for (seg = *prev_p; seg != NULL; seg = *prev_p)
4787         {
4788           if (seg->type->cleanupFunc != NULL)
4789             {
4790               *prev_p = (*seg->type->cleanupFunc)(seg, line);
4791               if (seg != *prev_p)
4792                 {
4793                   changed = TRUE;
4794                   continue;
4795                 }
4796             }
4797
4798           prev_p = &(*prev_p)->next;
4799         }
4800     }
4801 }
4802
4803 /*
4804  * Nodes
4805  */
4806
4807 static NodeData*
4808 node_data_new (gpointer view_id)
4809 {
4810   NodeData *nd;
4811
4812   nd = g_slice_new (NodeData);
4813
4814   nd->view_id = view_id;
4815   nd->next = NULL;
4816   nd->width = 0;
4817   nd->height = 0;
4818   nd->valid = FALSE;
4819
4820   return nd;
4821 }
4822
4823 static void
4824 node_data_destroy (NodeData *nd)
4825 {
4826   g_slice_free (NodeData, nd);
4827 }
4828
4829 static void
4830 node_data_list_destroy (NodeData *nd)
4831 {
4832   g_slice_free_chain (NodeData, nd, next);
4833 }
4834
4835 static NodeData*
4836 node_data_find (NodeData *nd,
4837                 gpointer  view_id)
4838 {
4839   while (nd != NULL)
4840     {
4841       if (nd->view_id == view_id)
4842         break;
4843       nd = nd->next;
4844     }
4845   return nd;
4846 }
4847
4848 static void
4849 summary_destroy (Summary *summary)
4850 {
4851   /* Fill with error-triggering garbage */
4852   summary->info = (void*)0x1;
4853   summary->toggle_count = 567;
4854   summary->next = (void*)0x1;
4855   g_slice_free (Summary, summary);
4856 }
4857
4858 static GtkTextBTreeNode*
4859 gtk_text_btree_node_new (void)
4860 {
4861   GtkTextBTreeNode *node;
4862
4863   node = g_new (GtkTextBTreeNode, 1);
4864
4865   node->node_data = NULL;
4866
4867   return node;
4868 }
4869
4870 static void
4871 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode  *node,
4872                                          GtkTextTagInfo  *info,
4873                                          gint adjust)
4874 {
4875   Summary *summary;
4876
4877   summary = node->summary;
4878   while (summary != NULL)
4879     {
4880       if (summary->info == info)
4881         {
4882           summary->toggle_count += adjust;
4883           break;
4884         }
4885
4886       summary = summary->next;
4887     }
4888
4889   if (summary == NULL)
4890     {
4891       /* didn't find a summary for our tag. */
4892       g_return_if_fail (adjust > 0);
4893       summary = g_slice_new (Summary);
4894       summary->info = info;
4895       summary->toggle_count = adjust;
4896       summary->next = node->summary;
4897       node->summary = summary;
4898     }
4899 }
4900
4901 /* Note that the tag root and above do not have summaries
4902    for the tag; only nodes below the tag root have
4903    the summaries. */
4904 static gboolean
4905 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4906 {
4907   Summary *summary;
4908
4909   summary = node->summary;
4910   while (summary != NULL)
4911     {
4912       if (tag == NULL ||
4913           summary->info->tag == tag)
4914         return TRUE;
4915
4916       summary = summary->next;
4917     }
4918
4919   return FALSE;
4920 }
4921
4922 /* Add node and all children to the damage region. */
4923 static void
4924 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4925 {
4926   NodeData *nd;
4927
4928   nd = node->node_data;
4929   while (nd != NULL)
4930     {
4931       nd->valid = FALSE;
4932       nd = nd->next;
4933     }
4934
4935   if (node->level == 0)
4936     {
4937       GtkTextLine *line;
4938
4939       line = node->children.line;
4940       while (line != NULL)
4941         {
4942           GtkTextLineData *ld;
4943
4944           ld = line->views;
4945           while (ld != NULL)
4946             {
4947               ld->valid = FALSE;
4948               ld = ld->next;
4949             }
4950
4951           line = line->next;
4952         }
4953     }
4954   else
4955     {
4956       GtkTextBTreeNode *child;
4957
4958       child = node->children.node;
4959
4960       while (child != NULL)
4961         {
4962           gtk_text_btree_node_invalidate_downward (child);
4963
4964           child = child->next;
4965         }
4966     }
4967 }
4968
4969 static void
4970 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4971 {
4972   GtkTextBTreeNode *iter;
4973
4974   iter = node;
4975   while (iter != NULL)
4976     {
4977       NodeData *nd;
4978
4979       if (view_id)
4980         {
4981           nd = node_data_find (iter->node_data, view_id);
4982
4983           if (nd == NULL || !nd->valid)
4984             break; /* Once a node is invalid, we know its parents are as well. */
4985
4986           nd->valid = FALSE;
4987         }
4988       else
4989         {
4990           gboolean should_continue = FALSE;
4991
4992           nd = iter->node_data;
4993           while (nd != NULL)
4994             {
4995               if (nd->valid)
4996                 {
4997                   should_continue = TRUE;
4998                   nd->valid = FALSE;
4999                 }
5000
5001               nd = nd->next;
5002             }
5003
5004           if (!should_continue)
5005             break; /* This node was totally invalidated, so are its
5006                       parents */
5007         }
5008
5009       iter = iter->parent;
5010     }
5011 }
5012
5013
5014 /**
5015  * _gtk_text_btree_is_valid:
5016  * @tree: a #GtkTextBTree
5017  * @view_id: ID for the view
5018  *
5019  * Check to see if the entire #GtkTextBTree is valid or not for
5020  * the given view.
5021  *
5022  * Return value: %TRUE if the entire #GtkTextBTree is valid
5023  **/
5024 gboolean
5025 _gtk_text_btree_is_valid (GtkTextBTree *tree,
5026                          gpointer      view_id)
5027 {
5028   NodeData *nd;
5029   g_return_val_if_fail (tree != NULL, FALSE);
5030
5031   nd = node_data_find (tree->root_node->node_data, view_id);
5032   return (nd && nd->valid);
5033 }
5034
5035 typedef struct _ValidateState ValidateState;
5036
5037 struct _ValidateState
5038 {
5039   gint remaining_pixels;
5040   gboolean in_validation;
5041   gint y;
5042   gint old_height;
5043   gint new_height;
5044 };
5045
5046 static void
5047 gtk_text_btree_node_validate (BTreeView         *view,
5048                               GtkTextBTreeNode  *node,
5049                               gpointer           view_id,
5050                               ValidateState     *state)
5051 {
5052   gint node_valid = TRUE;
5053   gint node_width = 0;
5054   gint node_height = 0;
5055
5056   NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5057   g_return_if_fail (!nd->valid);
5058
5059   if (node->level == 0)
5060     {
5061       GtkTextLine *line = node->children.line;
5062       GtkTextLineData *ld;
5063
5064       /* Iterate over leading valid lines */
5065       while (line != NULL)
5066         {
5067           ld = _gtk_text_line_get_data (line, view_id);
5068
5069           if (!ld || !ld->valid)
5070             break;
5071           else if (state->in_validation)
5072             {
5073               state->in_validation = FALSE;
5074               return;
5075             }
5076           else
5077             {
5078               state->y += ld->height;
5079               node_width = MAX (ld->width, node_width);
5080               node_height += ld->height;
5081             }
5082
5083           line = line->next;
5084         }
5085
5086       state->in_validation = TRUE;
5087
5088       /* Iterate over invalid lines */
5089       while (line != NULL)
5090         {
5091           ld = _gtk_text_line_get_data (line, view_id);
5092
5093           if (ld && ld->valid)
5094             break;
5095           else
5096             {
5097               if (ld)
5098                 state->old_height += ld->height;
5099               ld = gtk_text_layout_wrap (view->layout, line, ld);
5100               state->new_height += ld->height;
5101
5102               node_width = MAX (ld->width, node_width);
5103               node_height += ld->height;
5104
5105               state->remaining_pixels -= ld->height;
5106               if (state->remaining_pixels <= 0)
5107                 {
5108                   line = line->next;
5109                   break;
5110                 }
5111             }
5112
5113           line = line->next;
5114         }
5115
5116       /* Iterate over the remaining lines */
5117       while (line != NULL)
5118         {
5119           ld = _gtk_text_line_get_data (line, view_id);
5120           state->in_validation = FALSE;
5121
5122           if (!ld || !ld->valid)
5123             node_valid = FALSE;
5124
5125           if (ld)
5126             {
5127               node_width = MAX (ld->width, node_width);
5128               node_height += ld->height;
5129             }
5130
5131           line = line->next;
5132         }
5133     }
5134   else
5135     {
5136       GtkTextBTreeNode *child;
5137       NodeData *child_nd;
5138
5139       child = node->children.node;
5140
5141       /* Iterate over leading valid nodes */
5142       while (child)
5143         {
5144           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5145
5146           if (!child_nd->valid)
5147             break;
5148           else if (state->in_validation)
5149             {
5150               state->in_validation = FALSE;
5151               return;
5152             }
5153           else
5154             {
5155               state->y += child_nd->height;
5156               node_width = MAX (node_width, child_nd->width);
5157               node_height += child_nd->height;
5158             }
5159
5160           child = child->next;
5161         }
5162
5163       /* Iterate over invalid nodes */
5164       while (child)
5165         {
5166           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5167
5168           if (child_nd->valid)
5169             break;
5170           else
5171             {
5172               gtk_text_btree_node_validate (view, child, view_id, state);
5173
5174               if (!child_nd->valid)
5175                 node_valid = FALSE;
5176               node_width = MAX (node_width, child_nd->width);
5177               node_height += child_nd->height;
5178
5179               if (!state->in_validation || state->remaining_pixels <= 0)
5180                 {
5181                   child = child->next;
5182                   break;
5183                 }
5184             }
5185
5186           child = child->next;
5187         }
5188
5189       /* Iterate over the remaining lines */
5190       while (child)
5191         {
5192           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5193           state->in_validation = FALSE;
5194
5195           if (!child_nd->valid)
5196             node_valid = FALSE;
5197
5198           node_width = MAX (child_nd->width, node_width);
5199           node_height += child_nd->height;
5200
5201           child = child->next;
5202         }
5203     }
5204
5205   nd->width = node_width;
5206   nd->height = node_height;
5207   nd->valid = node_valid;
5208 }
5209
5210 /**
5211  * _gtk_text_btree_validate:
5212  * @tree: a #GtkTextBTree
5213  * @view_id: view id
5214  * @max_pixels: the maximum number of pixels to validate. (No more
5215  *              than one paragraph beyond this limit will be validated)
5216  * @y: location to store starting y coordinate of validated region
5217  * @old_height: location to store old height of validated region
5218  * @new_height: location to store new height of validated region
5219  *
5220  * Validate a single contiguous invalid region of a #GtkTextBTree for
5221  * a given view.
5222  *
5223  * Return value: %TRUE if a region has been validated, %FALSE if the
5224  * entire tree was already valid.
5225  **/
5226 gboolean
5227 _gtk_text_btree_validate (GtkTextBTree *tree,
5228                          gpointer      view_id,
5229                          gint          max_pixels,
5230                          gint         *y,
5231                          gint         *old_height,
5232                          gint         *new_height)
5233 {
5234   BTreeView *view;
5235
5236   g_return_val_if_fail (tree != NULL, FALSE);
5237
5238   view = gtk_text_btree_get_view (tree, view_id);
5239   g_return_val_if_fail (view != NULL, FALSE);
5240
5241   if (!_gtk_text_btree_is_valid (tree, view_id))
5242     {
5243       ValidateState state;
5244
5245       state.remaining_pixels = max_pixels;
5246       state.in_validation = FALSE;
5247       state.y = 0;
5248       state.old_height = 0;
5249       state.new_height = 0;
5250
5251       gtk_text_btree_node_validate (view,
5252                                     tree->root_node,
5253                                     view_id, &state);
5254
5255       if (y)
5256         *y = state.y;
5257       if (old_height)
5258         *old_height = state.old_height;
5259       if (new_height)
5260         *new_height = state.new_height;
5261
5262       if (gtk_debug_flags & GTK_DEBUG_TEXT)
5263         _gtk_text_btree_check (tree);
5264
5265       return TRUE;
5266     }
5267   else
5268     return FALSE;
5269 }
5270
5271 static void
5272 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5273                                              gpointer          view_id,
5274                                              gint             *width_out,
5275                                              gint             *height_out,
5276                                              gboolean         *valid_out)
5277 {
5278   gint width = 0;
5279   gint height = 0;
5280   gboolean valid = TRUE;
5281
5282   if (node->level == 0)
5283     {
5284       GtkTextLine *line = node->children.line;
5285
5286       while (line != NULL)
5287         {
5288           GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5289
5290           if (!ld || !ld->valid)
5291             valid = FALSE;
5292
5293           if (ld)
5294             {
5295               width = MAX (ld->width, width);
5296               height += ld->height;
5297             }
5298
5299           line = line->next;
5300         }
5301     }
5302   else
5303     {
5304       GtkTextBTreeNode *child = node->children.node;
5305
5306       while (child)
5307         {
5308           NodeData *child_nd = node_data_find (child->node_data, view_id);
5309
5310           if (!child_nd || !child_nd->valid)
5311             valid = FALSE;
5312
5313           if (child_nd)
5314             {
5315               width = MAX (child_nd->width, width);
5316               height += child_nd->height;
5317             }
5318
5319           child = child->next;
5320         }
5321     }
5322
5323   *width_out = width;
5324   *height_out = height;
5325   *valid_out = valid;
5326 }
5327
5328
5329 /* Recompute the validity and size of the view data for a given
5330  * view at this node from the immediate children of the node
5331  */
5332 static NodeData *
5333 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5334                                  gpointer          view_id)
5335 {
5336   NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5337   gboolean valid;
5338   gint width;
5339   gint height;
5340
5341   gtk_text_btree_node_compute_view_aggregates (node, view_id,
5342                                                &width, &height, &valid);
5343   nd->width = width;
5344   nd->height = height;
5345   nd->valid = valid;
5346
5347   return nd;
5348 }
5349
5350 static void
5351 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5352                                         gpointer          view_id)
5353 {
5354   while (node)
5355     {
5356       gtk_text_btree_node_check_valid (node, view_id);
5357       node = node->parent;
5358     }
5359 }
5360
5361 static NodeData *
5362 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5363                                           gpointer          view_id)
5364 {
5365   if (node->level == 0)
5366     {
5367       return gtk_text_btree_node_check_valid (node, view_id);
5368     }
5369   else
5370     {
5371       GtkTextBTreeNode *child = node->children.node;
5372
5373       NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5374
5375       nd->valid = TRUE;
5376       nd->width = 0;
5377       nd->height = 0;
5378
5379       while (child)
5380         {
5381           NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5382
5383           if (!child_nd->valid)
5384             nd->valid = FALSE;
5385           nd->width = MAX (child_nd->width, nd->width);
5386           nd->height += child_nd->height;
5387
5388           child = child->next;
5389         }
5390       return nd;
5391     }
5392 }
5393
5394
5395
5396 /**
5397  * _gtk_text_btree_validate_line:
5398  * @tree: a #GtkTextBTree
5399  * @line: line to validate
5400  * @view_id: view ID for the view to validate
5401  *
5402  * Revalidate a single line of the btree for the given view, propagate
5403  * results up through the entire tree.
5404  **/
5405 void
5406 _gtk_text_btree_validate_line (GtkTextBTree     *tree,
5407                                GtkTextLine      *line,
5408                                gpointer          view_id)
5409 {
5410   GtkTextLineData *ld;
5411   BTreeView *view;
5412
5413   g_return_if_fail (tree != NULL);
5414   g_return_if_fail (line != NULL);
5415
5416   view = gtk_text_btree_get_view (tree, view_id);
5417   g_return_if_fail (view != NULL);
5418
5419   ld = _gtk_text_line_get_data (line, view_id);
5420   if (!ld || !ld->valid)
5421     {
5422       ld = gtk_text_layout_wrap (view->layout, line, ld);
5423
5424       gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5425     }
5426 }
5427
5428 static void
5429 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5430 {
5431   if (node->level == 0)
5432     {
5433       GtkTextLine *line;
5434
5435       line = node->children.line;
5436       while (line != NULL)
5437         {
5438           GtkTextLineData *ld;
5439
5440           ld = _gtk_text_line_remove_data (line, view_id);
5441
5442           if (ld)
5443             gtk_text_layout_free_line_data (view->layout, line, ld);
5444
5445           line = line->next;
5446         }
5447     }
5448   else
5449     {
5450       GtkTextBTreeNode *child;
5451
5452       child = node->children.node;
5453
5454       while (child != NULL)
5455         {
5456           /* recurse */
5457           gtk_text_btree_node_remove_view (view, child, view_id);
5458
5459           child = child->next;
5460         }
5461     }
5462
5463   gtk_text_btree_node_remove_data (node, view_id);
5464 }
5465
5466 static void
5467 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5468 {
5469   if (node->level == 0)
5470     {
5471       GtkTextLine *line;
5472       GtkTextLineSegment *seg;
5473
5474       while (node->children.line != NULL)
5475         {
5476           line = node->children.line;
5477           node->children.line = line->next;
5478           while (line->segments != NULL)
5479             {
5480               seg = line->segments;
5481               line->segments = seg->next;
5482
5483               (*seg->type->deleteFunc) (seg, line, TRUE);
5484             }
5485           gtk_text_line_destroy (tree, line);
5486         }
5487     }
5488   else
5489     {
5490       GtkTextBTreeNode *childPtr;
5491
5492       while (node->children.node != NULL)
5493         {
5494           childPtr = node->children.node;
5495           node->children.node = childPtr->next;
5496           gtk_text_btree_node_destroy (tree, childPtr);
5497         }
5498     }
5499
5500   gtk_text_btree_node_free_empty (tree, node);
5501 }
5502
5503 static void
5504 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5505                                 GtkTextBTreeNode *node)
5506 {
5507   g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5508                     (node->level == 0 && node->children.line == NULL));
5509
5510   summary_list_destroy (node->summary);
5511   node_data_list_destroy (node->node_data);
5512   g_free (node);
5513 }
5514
5515 static NodeData*
5516 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5517 {
5518   NodeData *nd;
5519
5520   nd = node->node_data;
5521   while (nd != NULL)
5522     {
5523       if (nd->view_id == view_id)
5524         break;
5525
5526       nd = nd->next;
5527     }
5528
5529   if (nd == NULL)
5530     {
5531       nd = node_data_new (view_id);
5532
5533       if (node->node_data)
5534         nd->next = node->node_data;
5535
5536       node->node_data = nd;
5537     }
5538
5539   return nd;
5540 }
5541
5542 static void
5543 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5544 {
5545   NodeData *nd;
5546   NodeData *prev;
5547
5548   prev = NULL;
5549   nd = node->node_data;
5550   while (nd != NULL)
5551     {
5552       if (nd->view_id == view_id)
5553         break;
5554
5555       prev = nd;
5556       nd = nd->next;
5557     }
5558
5559   if (nd == NULL)
5560     return;
5561
5562   if (prev != NULL)
5563     prev->next = nd->next;
5564
5565   if (node->node_data == nd)
5566     node->node_data = nd->next;
5567
5568   nd->next = NULL;
5569
5570   node_data_destroy (nd);
5571 }
5572
5573 static void
5574 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5575                               gint *width, gint *height)
5576 {
5577   NodeData *nd;
5578
5579   g_return_if_fail (width != NULL);
5580   g_return_if_fail (height != NULL);
5581
5582   nd = gtk_text_btree_node_ensure_data (node, view_id);
5583
5584   if (width)
5585     *width = nd->width;
5586   if (height)
5587     *height = nd->height;
5588 }
5589
5590 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5591  * here isn't quite right, since for a lot of operations we want to
5592  * know which children of the common parent correspond to the two nodes
5593  * (e.g., when computing the order of two iters)
5594  */
5595 static GtkTextBTreeNode *
5596 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5597                                    GtkTextBTreeNode *node2)
5598 {
5599   while (node1->level < node2->level)
5600     node1 = node1->parent;
5601   while (node2->level < node1->level)
5602     node2 = node2->parent;
5603   while (node1 != node2)
5604     {
5605       node1 = node1->parent;
5606       node2 = node2->parent;
5607     }
5608
5609   return node1;
5610 }
5611
5612 /*
5613  * BTree
5614  */
5615
5616 static BTreeView*
5617 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5618 {
5619   BTreeView *view;
5620
5621   view = tree->views;
5622   while (view != NULL)
5623     {
5624       if (view->view_id == view_id)
5625         break;
5626       view = view->next;
5627     }
5628
5629   return view;
5630 }
5631
5632 static void
5633 get_tree_bounds (GtkTextBTree *tree,
5634                  GtkTextIter *start,
5635                  GtkTextIter *end)
5636 {
5637   _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5638   _gtk_text_btree_get_end_iter (tree, end);
5639 }
5640
5641 static void
5642 tag_changed_cb (GtkTextTagTable *table,
5643                 GtkTextTag      *tag,
5644                 gboolean         size_changed,
5645                 GtkTextBTree    *tree)
5646 {
5647   if (size_changed)
5648     {
5649       /* We need to queue a relayout on all regions that are tagged with
5650        * this tag.
5651        */
5652
5653       GtkTextIter start;
5654       GtkTextIter end;
5655
5656       if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5657         {
5658           /* Must be a last toggle if there was a first one. */
5659           _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5660           DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5661           _gtk_text_btree_invalidate_region (tree, &start, &end, FALSE);
5662
5663         }
5664     }
5665   else
5666     {
5667       /* We only need to queue a redraw, not a relayout */
5668       BTreeView *view;
5669
5670       view = tree->views;
5671
5672       while (view != NULL)
5673         {
5674           gint width, height;
5675
5676           _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5677           gtk_text_layout_changed (view->layout, 0, height, height);
5678
5679           view = view->next;
5680         }
5681     }
5682 }
5683
5684 void
5685 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree    *tree,
5686                                         GtkTextTag      *tag)
5687 {
5688   /* Remove the tag from the tree */
5689
5690   GtkTextIter start;
5691   GtkTextIter end;
5692
5693   get_tree_bounds (tree, &start, &end);
5694
5695   _gtk_text_btree_tag (&start, &end, tag, FALSE);
5696   gtk_text_btree_remove_tag_info (tree, tag);
5697 }
5698
5699
5700 /* Rebalance the out-of-whack node "node" */
5701 static void
5702 gtk_text_btree_rebalance (GtkTextBTree *tree,
5703                           GtkTextBTreeNode *node)
5704 {
5705   /*
5706    * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5707    * up through the tree one GtkTextBTreeNode at a time until the root
5708    * GtkTextBTreeNode has been processed.
5709    */
5710
5711   while (node != NULL)
5712     {
5713       GtkTextBTreeNode *new_node, *child;
5714       GtkTextLine *line;
5715       int i;
5716
5717       /*
5718        * Check to see if the GtkTextBTreeNode has too many children.  If it does,
5719        * then split off all but the first MIN_CHILDREN into a separate
5720        * GtkTextBTreeNode following the original one.  Then repeat until the
5721        * GtkTextBTreeNode has a decent size.
5722        */
5723
5724       if (node->num_children > MAX_CHILDREN)
5725         {
5726           while (1)
5727             {
5728               /*
5729                * If the GtkTextBTreeNode being split is the root
5730                * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5731                * it first.
5732                */
5733
5734               if (node->parent == NULL)
5735                 {
5736                   new_node = gtk_text_btree_node_new ();
5737                   new_node->parent = NULL;
5738                   new_node->next = NULL;
5739                   new_node->summary = NULL;
5740                   new_node->level = node->level + 1;
5741                   new_node->children.node = node;
5742                   recompute_node_counts (tree, new_node);
5743                   tree->root_node = new_node;
5744                 }
5745               new_node = gtk_text_btree_node_new ();
5746               new_node->parent = node->parent;
5747               new_node->next = node->next;
5748               node->next = new_node;
5749               new_node->summary = NULL;
5750               new_node->level = node->level;
5751               new_node->num_children = node->num_children - MIN_CHILDREN;
5752               if (node->level == 0)
5753                 {
5754                   for (i = MIN_CHILDREN-1,
5755                          line = node->children.line;
5756                        i > 0; i--, line = line->next)
5757                     {
5758                       /* Empty loop body. */
5759                     }
5760                   new_node->children.line = line->next;
5761                   line->next = NULL;
5762                 }
5763               else
5764                 {
5765                   for (i = MIN_CHILDREN-1,
5766                          child = node->children.node;
5767                        i > 0; i--, child = child->next)
5768                     {
5769                       /* Empty loop body. */
5770                     }
5771                   new_node->children.node = child->next;
5772                   child->next = NULL;
5773                 }
5774               recompute_node_counts (tree, node);
5775               node->parent->num_children++;
5776               node = new_node;
5777               if (node->num_children <= MAX_CHILDREN)
5778                 {
5779                   recompute_node_counts (tree, node);
5780                   break;
5781                 }
5782             }
5783         }
5784
5785       while (node->num_children < MIN_CHILDREN)
5786         {
5787           GtkTextBTreeNode *other;
5788           GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5789           GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5790           int total_children, first_children, i;
5791
5792           /*
5793            * Too few children for this GtkTextBTreeNode.  If this is the root then,
5794            * it's OK for it to have less than MIN_CHILDREN children
5795            * as long as it's got at least two.  If it has only one
5796            * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5797            * the tree and use its child as the new root.
5798            */
5799
5800           if (node->parent == NULL)
5801             {
5802               if ((node->num_children == 1) && (node->level > 0))
5803                 {
5804                   tree->root_node = node->children.node;
5805                   tree->root_node->parent = NULL;
5806
5807                   node->children.node = NULL;
5808                   gtk_text_btree_node_free_empty (tree, node);
5809                 }
5810               return;
5811             }
5812
5813           /*
5814            * Not the root.  Make sure that there are siblings to
5815            * balance with.
5816            */
5817
5818           if (node->parent->num_children < 2)
5819             {
5820               gtk_text_btree_rebalance (tree, node->parent);
5821               continue;
5822             }
5823
5824           /*
5825            * Find a sibling neighbor to borrow from, and arrange for
5826            * node to be the earlier of the pair.
5827            */
5828
5829           if (node->next == NULL)
5830             {
5831               for (other = node->parent->children.node;
5832                    other->next != node;
5833                    other = other->next)
5834                 {
5835                   /* Empty loop body. */
5836                 }
5837               node = other;
5838             }
5839           other = node->next;
5840
5841           /*
5842            * We're going to either merge the two siblings together
5843            * into one GtkTextBTreeNode or redivide the children among them to
5844            * balance their loads.  As preparation, join their two
5845            * child lists into a single list and remember the half-way
5846            * point in the list.
5847            */
5848
5849           total_children = node->num_children + other->num_children;
5850           first_children = total_children/2;
5851           if (node->children.node == NULL)
5852             {
5853               node->children = other->children;
5854               other->children.node = NULL;
5855               other->children.line = NULL;
5856             }
5857           if (node->level == 0)
5858             {
5859               GtkTextLine *line;
5860
5861               for (line = node->children.line, i = 1;
5862                    line->next != NULL;
5863                    line = line->next, i++)
5864                 {
5865                   if (i == first_children)
5866                     {
5867                       halfwayline = line;
5868                     }
5869                 }
5870               line->next = other->children.line;
5871               while (i <= first_children)
5872                 {
5873                   halfwayline = line;
5874                   line = line->next;
5875                   i++;
5876                 }
5877             }
5878           else
5879             {
5880               GtkTextBTreeNode *child;
5881
5882               for (child = node->children.node, i = 1;
5883                    child->next != NULL;
5884                    child = child->next, i++)
5885                 {
5886                   if (i <= first_children)
5887                     {
5888                       if (i == first_children)
5889                         {
5890                           halfwaynode = child;
5891                         }
5892                     }
5893                 }
5894               child->next = other->children.node;
5895               while (i <= first_children)
5896                 {
5897                   halfwaynode = child;
5898                   child = child->next;
5899                   i++;
5900                 }
5901             }
5902
5903           /*
5904            * If the two siblings can simply be merged together, do it.
5905            */
5906
5907           if (total_children <= MAX_CHILDREN)
5908             {
5909               recompute_node_counts (tree, node);
5910               node->next = other->next;
5911               node->parent->num_children--;
5912
5913               other->children.node = NULL;
5914               other->children.line = NULL;
5915               gtk_text_btree_node_free_empty (tree, other);
5916               continue;
5917             }
5918
5919           /*
5920            * The siblings can't be merged, so just divide their
5921            * children evenly between them.
5922            */
5923
5924           if (node->level == 0)
5925             {
5926               other->children.line = halfwayline->next;
5927               halfwayline->next = NULL;
5928             }
5929           else
5930             {
5931               other->children.node = halfwaynode->next;
5932               halfwaynode->next = NULL;
5933             }
5934
5935           recompute_node_counts (tree, node);
5936           recompute_node_counts (tree, other);
5937         }
5938
5939       node = node->parent;
5940     }
5941 }
5942
5943 static void
5944 post_insert_fixup (GtkTextBTree *tree,
5945                    GtkTextLine *line,
5946                    gint line_count_delta,
5947                    gint char_count_delta)
5948
5949 {
5950   GtkTextBTreeNode *node;
5951
5952   /*
5953    * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5954    * point, then rebalance the tree if necessary.
5955    */
5956
5957   for (node = line->parent ; node != NULL;
5958        node = node->parent)
5959     {
5960       node->num_lines += line_count_delta;
5961       node->num_chars += char_count_delta;
5962     }
5963   node = line->parent;
5964   node->num_children += line_count_delta;
5965
5966   if (node->num_children > MAX_CHILDREN)
5967     {
5968       gtk_text_btree_rebalance (tree, node);
5969     }
5970
5971   if (gtk_debug_flags & GTK_DEBUG_TEXT)
5972     _gtk_text_btree_check (tree);
5973 }
5974
5975 static GtkTextTagInfo*
5976 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5977                                       GtkTextTag   *tag)
5978 {
5979   GtkTextTagInfo *info;
5980   GSList *list;
5981
5982
5983   list = tree->tag_infos;
5984   while (list != NULL)
5985     {
5986       info = list->data;
5987       if (info->tag == tag)
5988         return info;
5989
5990       list = g_slist_next (list);
5991     }
5992
5993   return NULL;
5994 }
5995
5996 static GtkTextTagInfo*
5997 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5998                              GtkTextTag   *tag)
5999 {
6000   GtkTextTagInfo *info;
6001
6002   info = gtk_text_btree_get_existing_tag_info (tree, tag);
6003
6004   if (info == NULL)
6005     {
6006       /* didn't find it, create. */
6007
6008       info = g_slice_new (GtkTextTagInfo);
6009
6010       info->tag = tag;
6011       g_object_ref (tag);
6012       info->tag_root = NULL;
6013       info->toggle_count = 0;
6014
6015       tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
6016
6017 #if 0
6018       g_print ("Created tag info %p for tag %s(%p)\n",
6019                info, info->tag->name ? info->tag->name : "anon",
6020                info->tag);
6021 #endif
6022     }
6023
6024   return info;
6025 }
6026
6027 static void
6028 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
6029                                 GtkTextTag   *tag)
6030 {
6031   GtkTextTagInfo *info;
6032   GSList *list;
6033   GSList *prev;
6034
6035   prev = NULL;
6036   list = tree->tag_infos;
6037   while (list != NULL)
6038     {
6039       info = list->data;
6040       if (info->tag == tag)
6041         {
6042 #if 0
6043           g_print ("Removing tag info %p for tag %s(%p)\n",
6044                    info, info->tag->name ? info->tag->name : "anon",
6045                    info->tag);
6046 #endif
6047
6048           if (prev != NULL)
6049             {
6050               prev->next = list->next;
6051             }
6052           else
6053             {
6054               tree->tag_infos = list->next;
6055             }
6056           list->next = NULL;
6057           g_slist_free (list);
6058
6059           g_object_unref (info->tag);
6060
6061           g_slice_free (GtkTextTagInfo, info);
6062           return;
6063         }
6064
6065       prev = list;
6066       list = g_slist_next (list);
6067     }
6068 }
6069
6070 static void
6071 recompute_level_zero_counts (GtkTextBTreeNode *node)
6072 {
6073   GtkTextLine *line;
6074   GtkTextLineSegment *seg;
6075
6076   g_assert (node->level == 0);
6077
6078   line = node->children.line;
6079   while (line != NULL)
6080     {
6081       node->num_children++;
6082       node->num_lines++;
6083
6084       if (line->parent != node)
6085         gtk_text_line_set_parent (line, node);
6086
6087       seg = line->segments;
6088       while (seg != NULL)
6089         {
6090
6091           node->num_chars += seg->char_count;
6092
6093           if (((seg->type != &gtk_text_toggle_on_type)
6094                && (seg->type != &gtk_text_toggle_off_type))
6095               || !(seg->body.toggle.inNodeCounts))
6096             {
6097               ; /* nothing */
6098             }
6099           else
6100             {
6101               GtkTextTagInfo *info;
6102
6103               info = seg->body.toggle.info;
6104
6105               gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6106             }
6107
6108           seg = seg->next;
6109         }
6110
6111       line = line->next;
6112     }
6113 }
6114
6115 static void
6116 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6117 {
6118   Summary *summary;
6119   GtkTextBTreeNode *child;
6120
6121   g_assert (node->level > 0);
6122
6123   child = node->children.node;
6124   while (child != NULL)
6125     {
6126       node->num_children += 1;
6127       node->num_lines += child->num_lines;
6128       node->num_chars += child->num_chars;
6129
6130       if (child->parent != node)
6131         {
6132           child->parent = node;
6133           gtk_text_btree_node_invalidate_upward (node, NULL);
6134         }
6135
6136       summary = child->summary;
6137       while (summary != NULL)
6138         {
6139           gtk_text_btree_node_adjust_toggle_count (node,
6140                                                    summary->info,
6141                                                    summary->toggle_count);
6142
6143           summary = summary->next;
6144         }
6145
6146       child = child->next;
6147     }
6148 }
6149
6150 /*
6151  *----------------------------------------------------------------------
6152  *
6153  * recompute_node_counts --
6154  *
6155  *      This procedure is called to recompute all the counts in a GtkTextBTreeNode
6156  *      (tags, child information, etc.) by scanning the information in
6157  *      its descendants.  This procedure is called during rebalancing
6158  *      when a GtkTextBTreeNode's child structure has changed.
6159  *
6160  * Results:
6161  *      None.
6162  *
6163  * Side effects:
6164  *      The tag counts for node are modified to reflect its current
6165  *      child structure, as are its num_children, num_lines, num_chars fields.
6166  *      Also, all of the childrens' parent fields are made to point
6167  *      to node.
6168  *
6169  *----------------------------------------------------------------------
6170  */
6171
6172 static void
6173 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6174 {
6175   BTreeView *view;
6176   Summary *summary, *summary2;
6177
6178   /*
6179    * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6180    * the existing Summary records (most of them will probably be reused).
6181    */
6182
6183   summary = node->summary;
6184   while (summary != NULL)
6185     {
6186       summary->toggle_count = 0;
6187       summary = summary->next;
6188     }
6189
6190   node->num_children = 0;
6191   node->num_lines = 0;
6192   node->num_chars = 0;
6193
6194   /*
6195    * Scan through the children, adding the childrens' tag counts into
6196    * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6197    * necessary.
6198    */
6199
6200   if (node->level == 0)
6201     recompute_level_zero_counts (node);
6202   else
6203     recompute_level_nonzero_counts (node);
6204
6205   view = tree->views;
6206   while (view)
6207     {
6208       gtk_text_btree_node_check_valid (node, view->view_id);
6209       view = view->next;
6210     }
6211
6212   /*
6213    * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6214    * records that still have a zero count, or that have all the toggles.
6215    * The GtkTextBTreeNode with the children that account for all the tags toggles
6216    * have no summary information, and they become the tag_root for the tag.
6217    */
6218
6219   summary2 = NULL;
6220   for (summary = node->summary; summary != NULL; )
6221     {
6222       if (summary->toggle_count > 0 &&
6223           summary->toggle_count < summary->info->toggle_count)
6224         {
6225           if (node->level == summary->info->tag_root->level)
6226             {
6227               /*
6228                * The tag's root GtkTextBTreeNode split and some toggles left.
6229                * The tag root must move up a level.
6230                */
6231               summary->info->tag_root = node->parent;
6232             }
6233           summary2 = summary;
6234           summary = summary->next;
6235           continue;
6236         }
6237       if (summary->toggle_count == summary->info->toggle_count)
6238         {
6239           /*
6240            * A GtkTextBTreeNode merge has collected all the toggles under
6241            * one GtkTextBTreeNode.  Push the root down to this level.
6242            */
6243           summary->info->tag_root = node;
6244         }
6245       if (summary2 != NULL)
6246         {
6247           summary2->next = summary->next;
6248           summary_destroy (summary);
6249           summary = summary2->next;
6250         }
6251       else
6252         {
6253           node->summary = summary->next;
6254           summary_destroy (summary);
6255           summary = node->summary;
6256         }
6257     }
6258 }
6259
6260 void
6261 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6262                                GtkTextTagInfo   *info,
6263                                gint              delta) /* may be negative */
6264 {
6265   Summary *summary, *prevPtr;
6266   GtkTextBTreeNode *node2Ptr;
6267   int rootLevel;                        /* Level of original tag root */
6268
6269   info->toggle_count += delta;
6270
6271   if (info->tag_root == (GtkTextBTreeNode *) NULL)
6272     {
6273       info->tag_root = node;
6274       return;
6275     }
6276
6277   /*
6278    * Note the level of the existing root for the tag so we can detect
6279    * if it needs to be moved because of the toggle count change.
6280    */
6281
6282   rootLevel = info->tag_root->level;
6283
6284   /*
6285    * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6286    * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6287    * necessary.
6288    */
6289
6290   for ( ; node != info->tag_root; node = node->parent)
6291     {
6292       /*
6293        * See if there's already an entry for this tag for this GtkTextBTreeNode.  If so,
6294        * perhaps all we have to do is adjust its count.
6295        */
6296
6297       for (prevPtr = NULL, summary = node->summary;
6298            summary != NULL;
6299            prevPtr = summary, summary = summary->next)
6300         {
6301           if (summary->info == info)
6302             {
6303               break;
6304             }
6305         }
6306       if (summary != NULL)
6307         {
6308           summary->toggle_count += delta;
6309           if (summary->toggle_count > 0 &&
6310               summary->toggle_count < info->toggle_count)
6311             {
6312               continue;
6313             }
6314           if (summary->toggle_count != 0)
6315             {
6316               /*
6317                * Should never find a GtkTextBTreeNode with max toggle count at this
6318                * point (there shouldn't have been a summary entry in the
6319                * first place).
6320                */
6321
6322               g_error ("%s: bad toggle count (%d) max (%d)",
6323                        G_STRLOC, summary->toggle_count, info->toggle_count);
6324             }
6325
6326           /*
6327            * Zero toggle count;  must remove this tag from the list.
6328            */
6329
6330           if (prevPtr == NULL)
6331             {
6332               node->summary = summary->next;
6333             }
6334           else
6335             {
6336               prevPtr->next = summary->next;
6337             }
6338           summary_destroy (summary);
6339         }
6340       else
6341         {
6342           /*
6343            * This tag isn't currently in the summary information list.
6344            */
6345
6346           if (rootLevel == node->level)
6347             {
6348
6349               /*
6350                * The old tag root is at the same level in the tree as this
6351                * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode.  Move the tag root up
6352                * a level, in the hopes that it will now cover this GtkTextBTreeNode
6353                * as well as the old root (if not, we'll move it up again
6354                * the next time through the loop).  To push it up one level
6355                * we copy the original toggle count into the summary
6356                * information at the old root and change the root to its
6357                * parent GtkTextBTreeNode.
6358                */
6359
6360               GtkTextBTreeNode *rootnode = info->tag_root;
6361               summary = g_slice_new (Summary);
6362               summary->info = info;
6363               summary->toggle_count = info->toggle_count - delta;
6364               summary->next = rootnode->summary;
6365               rootnode->summary = summary;
6366               rootnode = rootnode->parent;
6367               rootLevel = rootnode->level;
6368               info->tag_root = rootnode;
6369             }
6370           summary = g_slice_new (Summary);
6371           summary->info = info;
6372           summary->toggle_count = delta;
6373           summary->next = node->summary;
6374           node->summary = summary;
6375         }
6376     }
6377
6378   /*
6379    * If we've decremented the toggle count, then it may be necessary
6380    * to push the tag root down one or more levels.
6381    */
6382
6383   if (delta >= 0)
6384     {
6385       return;
6386     }
6387   if (info->toggle_count == 0)
6388     {
6389       info->tag_root = (GtkTextBTreeNode *) NULL;
6390       return;
6391     }
6392   node = info->tag_root;
6393   while (node->level > 0)
6394     {
6395       /*
6396        * See if a single child GtkTextBTreeNode accounts for all of the tag's
6397        * toggles.  If so, push the root down one level.
6398        */
6399
6400       for (node2Ptr = node->children.node;
6401            node2Ptr != (GtkTextBTreeNode *)NULL ;
6402            node2Ptr = node2Ptr->next)
6403         {
6404           for (prevPtr = NULL, summary = node2Ptr->summary;
6405                summary != NULL;
6406                prevPtr = summary, summary = summary->next)
6407             {
6408               if (summary->info == info)
6409                 {
6410                   break;
6411                 }
6412             }
6413           if (summary == NULL)
6414             {
6415               continue;
6416             }
6417           if (summary->toggle_count != info->toggle_count)
6418             {
6419               /*
6420                * No GtkTextBTreeNode has all toggles, so the root is still valid.
6421                */
6422
6423               return;
6424             }
6425
6426           /*
6427            * This GtkTextBTreeNode has all the toggles, so push down the root.
6428            */
6429
6430           if (prevPtr == NULL)
6431             {
6432               node2Ptr->summary = summary->next;
6433             }
6434           else
6435             {
6436               prevPtr->next = summary->next;
6437             }
6438           summary_destroy (summary);
6439           info->tag_root = node2Ptr;
6440           break;
6441         }
6442       node = info->tag_root;
6443     }
6444 }
6445
6446 /*
6447  *----------------------------------------------------------------------
6448  *
6449  * inc_count --
6450  *
6451  *      This is a utility procedure used by _gtk_text_btree_get_tags.  It
6452  *      increments the count for a particular tag, adding a new
6453  *      entry for that tag if there wasn't one previously.
6454  *
6455  * Results:
6456  *      None.
6457  *
6458  * Side effects:
6459  *      The information at *tagInfoPtr may be modified, and the arrays
6460  *      may be reallocated to make them larger.
6461  *
6462  *----------------------------------------------------------------------
6463  */
6464
6465 static void
6466 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6467 {
6468   GtkTextTag **tag_p;
6469   int count;
6470
6471   for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6472        count > 0; tag_p++, count--)
6473     {
6474       if (*tag_p == tag)
6475         {
6476           tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6477           return;
6478         }
6479     }
6480
6481   /*
6482    * There isn't currently an entry for this tag, so we have to
6483    * make a new one.  If the arrays are full, then enlarge the
6484    * arrays first.
6485    */
6486
6487   if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6488     {
6489       GtkTextTag **newTags;
6490       int *newCounts, newSize;
6491
6492       newSize = 2*tagInfoPtr->arraySize;
6493       newTags = (GtkTextTag **) g_malloc ((unsigned)
6494                                           (newSize*sizeof (GtkTextTag *)));
6495       memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6496               tagInfoPtr->arraySize  *sizeof (GtkTextTag *));
6497       g_free ((char *) tagInfoPtr->tags);
6498       tagInfoPtr->tags = newTags;
6499       newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6500       memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6501               tagInfoPtr->arraySize  *sizeof (int));
6502       g_free ((char *) tagInfoPtr->counts);
6503       tagInfoPtr->counts = newCounts;
6504       tagInfoPtr->arraySize = newSize;
6505     }
6506
6507   tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6508   tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6509   tagInfoPtr->numTags++;
6510 }
6511
6512 static void
6513 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6514                              const GtkTextIter *iter)
6515 {
6516   GtkTextLineSegment *prev;
6517   GtkTextLine *line;
6518   GtkTextBTree *tree;
6519
6520   line = _gtk_text_iter_get_text_line (iter);
6521   tree = _gtk_text_iter_get_btree (iter);
6522
6523   prev = gtk_text_line_segment_split (iter);
6524   if (prev == NULL)
6525     {
6526       seg->next = line->segments;
6527       line->segments = seg;
6528     }
6529   else
6530     {
6531       seg->next = prev->next;
6532       prev->next = seg;
6533     }
6534   cleanup_line (line);
6535   segments_changed (tree);
6536
6537   if (gtk_debug_flags & GTK_DEBUG_TEXT)
6538     _gtk_text_btree_check (tree);
6539 }
6540
6541 static void
6542 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6543                                GtkTextLineSegment *seg,
6544                                GtkTextLine *line)
6545 {
6546   GtkTextLineSegment *prev;
6547
6548   if (line->segments == seg)
6549     {
6550       line->segments = seg->next;
6551     }
6552   else
6553     {
6554       for (prev = line->segments; prev->next != seg;
6555            prev = prev->next)
6556         {
6557           /* Empty loop body. */
6558         }
6559       prev->next = seg->next;
6560     }
6561   cleanup_line (line);
6562   segments_changed (tree);
6563 }
6564
6565 /*
6566  * This is here because it requires BTree internals, it logically
6567  * belongs in gtktextsegment.c
6568  */
6569
6570
6571 /*
6572  *--------------------------------------------------------------
6573  *
6574  * _gtk_toggle_segment_check_func --
6575  *
6576  *      This procedure is invoked to perform consistency checks
6577  *      on toggle segments.
6578  *
6579  * Results:
6580  *      None.
6581  *
6582  * Side effects:
6583  *      If a consistency problem is found the procedure g_errors.
6584  *
6585  *--------------------------------------------------------------
6586  */
6587
6588 void
6589 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6590                                 GtkTextLine *line)
6591 {
6592   Summary *summary;
6593   int needSummary;
6594
6595   if (segPtr->byte_count != 0)
6596     {
6597       g_error ("toggle_segment_check_func: segment had non-zero size");
6598     }
6599   if (!segPtr->body.toggle.inNodeCounts)
6600     {
6601       g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6602     }
6603   needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6604   for (summary = line->parent->summary; ;
6605        summary = summary->next)
6606     {
6607       if (summary == NULL)
6608         {
6609           if (needSummary)
6610             {
6611               g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6612             }
6613           else
6614             {
6615               break;
6616             }
6617         }
6618       if (summary->info == segPtr->body.toggle.info)
6619         {
6620           if (!needSummary)
6621             {
6622               g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6623             }
6624           break;
6625         }
6626     }
6627 }
6628
6629 /*
6630  * Debug
6631  */
6632
6633 static void
6634 gtk_text_btree_node_view_check_consistency (GtkTextBTree     *tree,
6635                                             GtkTextBTreeNode *node,
6636                                             NodeData         *nd)
6637 {
6638   gint width;
6639   gint height;
6640   gboolean valid;
6641   BTreeView *view;
6642
6643   view = tree->views;
6644
6645   while (view != NULL)
6646     {
6647       if (view->view_id == nd->view_id)
6648         break;
6649
6650       view = view->next;
6651     }
6652
6653   if (view == NULL)
6654     g_error ("Node has data for a view %p no longer attached to the tree",
6655              nd->view_id);
6656
6657   gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6658                                                &width, &height, &valid);
6659
6660   /* valid aggregate not checked the same as width/height, because on
6661    * btree rebalance we can have invalid nodes where all lines below
6662    * them are actually valid, due to moving lines around between
6663    * nodes.
6664    *
6665    * The guarantee is that if there are invalid lines the node is
6666    * invalid - we don't guarantee that if the node is invalid there
6667    * are invalid lines.
6668    */
6669
6670   if (nd->width != width ||
6671       nd->height != height ||
6672       (nd->valid && !valid))
6673     {
6674       g_error ("Node aggregates for view %p are invalid:\n"
6675                "Are (%d,%d,%s), should be (%d,%d,%s)",
6676                nd->view_id,
6677                nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6678                width, height, valid ? "TRUE" : "FALSE");
6679     }
6680 }
6681
6682 static void
6683 gtk_text_btree_node_check_consistency (GtkTextBTree     *tree,
6684                                        GtkTextBTreeNode *node)
6685 {
6686   GtkTextBTreeNode *childnode;
6687   Summary *summary, *summary2;
6688   GtkTextLine *line;
6689   GtkTextLineSegment *segPtr;
6690   int num_children, num_lines, num_chars, toggle_count, min_children;
6691   GtkTextLineData *ld;
6692   NodeData *nd;
6693
6694   if (node->parent != NULL)
6695     {
6696       min_children = MIN_CHILDREN;
6697     }
6698   else if (node->level > 0)
6699     {
6700       min_children = 2;
6701     }
6702   else  {
6703     min_children = 1;
6704   }
6705   if ((node->num_children < min_children)
6706       || (node->num_children > MAX_CHILDREN))
6707     {
6708       g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6709                node->num_children);
6710     }
6711
6712   nd = node->node_data;
6713   while (nd != NULL)
6714     {
6715       gtk_text_btree_node_view_check_consistency (tree, node, nd);
6716       nd = nd->next;
6717     }
6718
6719   num_children = 0;
6720   num_lines = 0;
6721   num_chars = 0;
6722   if (node->level == 0)
6723     {
6724       for (line = node->children.line; line != NULL;
6725            line = line->next)
6726         {
6727           if (line->parent != node)
6728             {
6729               g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6730             }
6731           if (line->segments == NULL)
6732             {
6733               g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6734             }
6735
6736           ld = line->views;
6737           while (ld != NULL)
6738             {
6739               /* Just ensuring we don't segv while doing this loop */
6740
6741               ld = ld->next;
6742             }
6743
6744           for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6745             {
6746               if (segPtr->type->checkFunc != NULL)
6747                 {
6748                   (*segPtr->type->checkFunc)(segPtr, line);
6749                 }
6750               if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6751                   && (segPtr->next != NULL)
6752                   && (segPtr->next->byte_count == 0)
6753                   && (segPtr->next->type->leftGravity))
6754                 {
6755                   g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6756                 }
6757               if ((segPtr->next == NULL)
6758                   && (segPtr->type != &gtk_text_char_type))
6759                 {
6760                   g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6761                 }
6762
6763               num_chars += segPtr->char_count;
6764             }
6765
6766           num_children++;
6767           num_lines++;
6768         }
6769     }
6770   else
6771     {
6772       for (childnode = node->children.node; childnode != NULL;
6773            childnode = childnode->next)
6774         {
6775           if (childnode->parent != node)
6776             {
6777               g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6778             }
6779           if (childnode->level != (node->level-1))
6780             {
6781               g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6782                        node->level, childnode->level);
6783             }
6784           gtk_text_btree_node_check_consistency (tree, childnode);
6785           for (summary = childnode->summary; summary != NULL;
6786                summary = summary->next)
6787             {
6788               for (summary2 = node->summary; ;
6789                    summary2 = summary2->next)
6790                 {
6791                   if (summary2 == NULL)
6792                     {
6793                       if (summary->info->tag_root == node)
6794                         {
6795                           break;
6796                         }
6797                       g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6798                                summary->info->tag->name,
6799                                "present in parent summaries");
6800                     }
6801                   if (summary->info == summary2->info)
6802                     {
6803                       break;
6804                     }
6805                 }
6806             }
6807           num_children++;
6808           num_lines += childnode->num_lines;
6809           num_chars += childnode->num_chars;
6810         }
6811     }
6812   if (num_children != node->num_children)
6813     {
6814       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6815                num_children, node->num_children);
6816     }
6817   if (num_lines != node->num_lines)
6818     {
6819       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6820                num_lines, node->num_lines);
6821     }
6822   if (num_chars != node->num_chars)
6823     {
6824       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6825                num_chars, node->num_chars);
6826     }
6827
6828   for (summary = node->summary; summary != NULL;
6829        summary = summary->next)
6830     {
6831       if (summary->info->toggle_count == summary->toggle_count)
6832         {
6833           g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6834                    summary->info->tag->name);
6835         }
6836       toggle_count = 0;
6837       if (node->level == 0)
6838         {
6839           for (line = node->children.line; line != NULL;
6840                line = line->next)
6841             {
6842               for (segPtr = line->segments; segPtr != NULL;
6843                    segPtr = segPtr->next)
6844                 {
6845                   if ((segPtr->type != &gtk_text_toggle_on_type)
6846                       && (segPtr->type != &gtk_text_toggle_off_type))
6847                     {
6848                       continue;
6849                     }
6850                   if (segPtr->body.toggle.info == summary->info)
6851                     {
6852                       if (!segPtr->body.toggle.inNodeCounts)
6853                         g_error ("Toggle segment not in the node counts");
6854
6855                       toggle_count ++;
6856                     }
6857                 }
6858             }
6859         }
6860       else
6861         {
6862           for (childnode = node->children.node;
6863                childnode != NULL;
6864                childnode = childnode->next)
6865             {
6866               for (summary2 = childnode->summary;
6867                    summary2 != NULL;
6868                    summary2 = summary2->next)
6869                 {
6870                   if (summary2->info == summary->info)
6871                     {
6872                       toggle_count += summary2->toggle_count;
6873                     }
6874                 }
6875             }
6876         }
6877       if (toggle_count != summary->toggle_count)
6878         {
6879           g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6880                    toggle_count, summary->toggle_count);
6881         }
6882       for (summary2 = summary->next; summary2 != NULL;
6883            summary2 = summary2->next)
6884         {
6885           if (summary2->info == summary->info)
6886             {
6887               g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6888                        summary->info->tag->name);
6889             }
6890         }
6891     }
6892 }
6893
6894 static void
6895 listify_foreach (GtkTextTag *tag, gpointer user_data)
6896 {
6897   GSList** listp = user_data;
6898
6899   *listp = g_slist_prepend (*listp, tag);
6900 }
6901
6902 static GSList*
6903 list_of_tags (GtkTextTagTable *table)
6904 {
6905   GSList *list = NULL;
6906
6907   gtk_text_tag_table_foreach (table, listify_foreach, &list);
6908
6909   return list;
6910 }
6911
6912 void
6913 _gtk_text_btree_check (GtkTextBTree *tree)
6914 {
6915   Summary *summary;
6916   GtkTextBTreeNode *node;
6917   GtkTextLine *line;
6918   GtkTextLineSegment *seg;
6919   GtkTextTag *tag;
6920   GSList *all_tags, *taglist = NULL;
6921   int count;
6922   GtkTextTagInfo *info;
6923
6924   /*
6925    * Make sure that the tag toggle counts and the tag root pointers are OK.
6926    */
6927   all_tags = list_of_tags (tree->table);
6928   for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6929     {
6930       tag = taglist->data;
6931       info = gtk_text_btree_get_existing_tag_info (tree, tag);
6932       if (info != NULL)
6933         {
6934           node = info->tag_root;
6935           if (node == NULL)
6936             {
6937               if (info->toggle_count != 0)
6938                 {
6939                   g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6940                            tag->name, info->toggle_count);
6941                 }
6942               continue;         /* no ranges for the tag */
6943             }
6944           else if (info->toggle_count == 0)
6945             {
6946               g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6947                        tag->name);
6948             }
6949           else if (info->toggle_count & 1)
6950             {
6951               g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6952                        tag->name, info->toggle_count);
6953             }
6954           for (summary = node->summary; summary != NULL;
6955                summary = summary->next)
6956             {
6957               if (summary->info->tag == tag)
6958                 {
6959                   g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6960                 }
6961             }
6962           count = 0;
6963           if (node->level > 0)
6964             {
6965               for (node = node->children.node ; node != NULL ;
6966                    node = node->next)
6967                 {
6968                   for (summary = node->summary; summary != NULL;
6969                        summary = summary->next)
6970                     {
6971                       if (summary->info->tag == tag)
6972                         {
6973                           count += summary->toggle_count;
6974                         }
6975                     }
6976                 }
6977             }
6978           else
6979             {
6980               const GtkTextLineSegmentClass *last = NULL;
6981
6982               for (line = node->children.line ; line != NULL ;
6983                    line = line->next)
6984                 {
6985                   for (seg = line->segments; seg != NULL;
6986                        seg = seg->next)
6987                     {
6988                       if ((seg->type == &gtk_text_toggle_on_type ||
6989                            seg->type == &gtk_text_toggle_off_type) &&
6990                           seg->body.toggle.info->tag == tag)
6991                         {
6992                           if (last == seg->type)
6993                             g_error ("Two consecutive toggles on or off weren't merged");
6994                           if (!seg->body.toggle.inNodeCounts)
6995                             g_error ("Toggle segment not in the node counts");
6996
6997                           last = seg->type;
6998
6999                           count++;
7000                         }
7001                     }
7002                 }
7003             }
7004           if (count != info->toggle_count)
7005             {
7006               g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
7007                        info->toggle_count, tag->name, count);
7008             }
7009         }
7010     }
7011
7012   g_slist_free (all_tags);
7013
7014   /*
7015    * Call a recursive procedure to do the main body of checks.
7016    */
7017
7018   node = tree->root_node;
7019   gtk_text_btree_node_check_consistency (tree, tree->root_node);
7020
7021   /*
7022    * Make sure that there are at least two lines in the text and
7023    * that the last line has no characters except a newline.
7024    */
7025
7026   if (node->num_lines < 2)
7027     {
7028       g_error ("_gtk_text_btree_check: less than 2 lines in tree");
7029     }
7030   if (node->num_chars < 2)
7031     {
7032       g_error ("_gtk_text_btree_check: less than 2 chars in tree");
7033     }
7034   while (node->level > 0)
7035     {
7036       node = node->children.node;
7037       while (node->next != NULL)
7038         {
7039           node = node->next;
7040         }
7041     }
7042   line = node->children.line;
7043   while (line->next != NULL)
7044     {
7045       line = line->next;
7046     }
7047   seg = line->segments;
7048   while ((seg->type == &gtk_text_toggle_off_type)
7049          || (seg->type == &gtk_text_right_mark_type)
7050          || (seg->type == &gtk_text_left_mark_type))
7051     {
7052       /*
7053        * It's OK to toggle a tag off in the last line, but
7054        * not to start a new range.  It's also OK to have marks
7055        * in the last line.
7056        */
7057
7058       seg = seg->next;
7059     }
7060   if (seg->type != &gtk_text_char_type)
7061     {
7062       g_error ("_gtk_text_btree_check: last line has bogus segment type");
7063     }
7064   if (seg->next != NULL)
7065     {
7066       g_error ("_gtk_text_btree_check: last line has too many segments");
7067     }
7068   if (seg->byte_count != 1)
7069     {
7070       g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7071                seg->byte_count);
7072     }
7073   if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7074     {
7075       g_error ("_gtk_text_btree_check: last line had bad value: %s",
7076                seg->body.chars);
7077     }
7078 }
7079
7080 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7081 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7082 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7083 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7084
7085 void
7086 _gtk_text_btree_spew (GtkTextBTree *tree)
7087 {
7088   GtkTextLine * line;
7089   int real_line;
7090
7091   printf ("%d lines in tree %p\n",
7092           _gtk_text_btree_line_count (tree), tree);
7093
7094   line = _gtk_text_btree_get_line (tree, 0, &real_line);
7095
7096   while (line != NULL)
7097     {
7098       _gtk_text_btree_spew_line (tree, line);
7099       line = _gtk_text_line_next (line);
7100     }
7101
7102   printf ("=================== Tag information\n");
7103
7104   {
7105     GSList * list;
7106
7107     list = tree->tag_infos;
7108
7109     while (list != NULL)
7110       {
7111         GtkTextTagInfo *info;
7112
7113         info = list->data;
7114
7115         printf ("  tag `%s': root at %p, toggle count %d\n",
7116                 info->tag->name, info->tag_root, info->toggle_count);
7117
7118         list = g_slist_next (list);
7119       }
7120
7121     if (tree->tag_infos == NULL)
7122       {
7123         printf ("  (no tags in the tree)\n");
7124       }
7125   }
7126
7127   printf ("=================== Tree nodes\n");
7128
7129   {
7130     _gtk_text_btree_spew_node (tree->root_node, 0);
7131   }
7132 }
7133
7134 void
7135 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7136 {
7137   gchar * spaces;
7138   GtkTextLineSegment *seg;
7139
7140   spaces = g_strnfill (indent, ' ');
7141
7142   printf ("%sline %p chars %d bytes %d\n",
7143           spaces, line,
7144           _gtk_text_line_char_count (line),
7145           _gtk_text_line_byte_count (line));
7146
7147   seg = line->segments;
7148   while (seg != NULL)
7149     {
7150       if (seg->type == &gtk_text_char_type)
7151         {
7152           gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7153           gchar* s;
7154           s = str;
7155           while (*s)
7156             {
7157               if (*s == '\n' || *s == '\r')
7158                 *s = '\\';
7159               ++s;
7160             }
7161           printf ("%s chars `%s'...\n", spaces, str);
7162           g_free (str);
7163         }
7164       else if (seg->type == &gtk_text_right_mark_type)
7165         {
7166           printf ("%s right mark `%s' visible: %d\n",
7167                   spaces,
7168                   seg->body.mark.name,
7169                   seg->body.mark.visible);
7170         }
7171       else if (seg->type == &gtk_text_left_mark_type)
7172         {
7173           printf ("%s left mark `%s' visible: %d\n",
7174                   spaces,
7175                   seg->body.mark.name,
7176                   seg->body.mark.visible);
7177         }
7178       else if (seg->type == &gtk_text_toggle_on_type ||
7179                seg->type == &gtk_text_toggle_off_type)
7180         {
7181           printf ("%s tag `%s' %s\n",
7182                   spaces, seg->body.toggle.info->tag->name,
7183                   seg->type == &gtk_text_toggle_off_type ? "off" : "on");
7184         }
7185
7186       seg = seg->next;
7187     }
7188
7189   g_free (spaces);
7190 }
7191
7192 void
7193 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7194 {
7195   gchar * spaces;
7196   GtkTextBTreeNode *iter;
7197   Summary *s;
7198
7199   spaces = g_strnfill (indent, ' ');
7200
7201   printf ("%snode %p level %d children %d lines %d chars %d\n",
7202           spaces, node, node->level,
7203           node->num_children, node->num_lines, node->num_chars);
7204
7205   s = node->summary;
7206   while (s)
7207     {
7208       printf ("%s %d toggles of `%s' below this node\n",
7209               spaces, s->toggle_count, s->info->tag->name);
7210       s = s->next;
7211     }
7212
7213   g_free (spaces);
7214
7215   if (node->level > 0)
7216     {
7217       iter = node->children.node;
7218       while (iter != NULL)
7219         {
7220           _gtk_text_btree_spew_node (iter, indent + 2);
7221
7222           iter = iter->next;
7223         }
7224     }
7225   else
7226     {
7227       GtkTextLine *line = node->children.line;
7228       while (line != NULL)
7229         {
7230           _gtk_text_btree_spew_line_short (line, indent + 2);
7231
7232           line = line->next;
7233         }
7234     }
7235 }
7236
7237 void
7238 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7239 {
7240   GtkTextLineSegment * seg;
7241
7242   printf ("%4d| line: %p parent: %p next: %p\n",
7243           _gtk_text_line_get_number (line), line, line->parent, line->next);
7244
7245   seg = line->segments;
7246
7247   while (seg != NULL)
7248     {
7249       _gtk_text_btree_spew_segment (tree, seg);
7250       seg = seg->next;
7251     }
7252 }
7253
7254 void
7255 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7256 {
7257   printf ("     segment: %p type: %s bytes: %d chars: %d\n",
7258           seg, seg->type->name, seg->byte_count, seg->char_count);
7259
7260   if (seg->type == &gtk_text_char_type)
7261     {
7262       gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7263       printf ("       `%s'\n", str);
7264       g_free (str);
7265     }
7266   else if (seg->type == &gtk_text_right_mark_type)
7267     {
7268       printf ("       right mark `%s' visible: %d not_deleteable: %d\n",
7269               seg->body.mark.name,
7270               seg->body.mark.visible,
7271               seg->body.mark.not_deleteable);
7272     }
7273   else if (seg->type == &gtk_text_left_mark_type)
7274     {
7275       printf ("       left mark `%s' visible: %d not_deleteable: %d\n",
7276               seg->body.mark.name,
7277               seg->body.mark.visible,
7278               seg->body.mark.not_deleteable);
7279     }
7280   else if (seg->type == &gtk_text_toggle_on_type ||
7281            seg->type == &gtk_text_toggle_off_type)
7282     {
7283       printf ("       tag `%s' priority %d\n",
7284               seg->body.toggle.info->tag->name,
7285               seg->body.toggle.info->tag->priority);
7286     }
7287 }
7288
7289 #define __GTK_TEXT_BTREE_C__
7290 #include "gtkaliasdef.c"