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