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

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