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

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