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