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