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

   1 /*
   2  * gtktextbtree.c --
   3  *
   4  *      This file contains code that manages the B-tree representation
   5  *      of text for the text buffer and implements character and
   6  *      toggle segment types.
   7  *
   8  * Copyright (c) 1992-1994 The Regents of the University of California.
   9  * Copyright (c) 1994-1995 Sun Microsystems, Inc.
  10  * Copyright (c) 2000      Red Hat, Inc.
  11  * Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
  12  *
  13  * This software is copyrighted by the Regents of the University of
  14  * California, Sun Microsystems, Inc., and other parties.  The
  15  * following terms apply to all files associated with the software
  16  * unless explicitly disclaimed in individual files.
  17  *
  18  * The authors hereby grant permission to use, copy, modify,
  19  * distribute, and license this software and its documentation for any
  20  * purpose, provided that existing copyright notices are retained in
  21  * all copies and that this notice is included verbatim in any
  22  * distributions. No written agreement, license, or royalty fee is
  23  * required for any of the authorized uses.  Modifications to this
  24  * software may be copyrighted by their authors and need not follow
  25  * the licensing terms described here, provided that the new terms are
  26  * clearly indicated on the first page of each file where they apply.
  27  *
  28  * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
  29  * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
  30  * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
  31  * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
  32  * OF THE POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
  35  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
  37  * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
  38  * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
  39  * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  40  *
  41  * GOVERNMENT USE: If you are acquiring this software on behalf of the
  42  * U.S. government, the Government shall have only "Restricted Rights"
  43  * in the software and related documentation as defined in the Federal
  44  * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
  45  * are acquiring the software on behalf of the Department of Defense,
  46  * the software shall be classified as "Commercial Computer Software"
  47  * and the Government shall have only "Restricted Rights" as defined
  48  * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
  49  * foregoing, the authors grant the U.S. Government and others acting
  50  * in its behalf permission to use and distribute the software in
  51  * accordance with the terms specified in this license.
  52  *
  53  */
  54
  55 #define GTK_TEXT_USE_INTERNAL_UNSUPPORTED_API
  56 #include <config.h>
  57 #include "gtktextbtree.h"
  58 #include <string.h>
  59 #include <stdlib.h>
  60 #include <stdio.h>
  61 #include "gtktexttag.h"
  62 #include "gtktexttagtable.h"
  63 #include "gtktextlayout.h"
  64 #include "gtktextiterprivate.h"
  65 #include "gtkdebug.h"
  66 #include "gtktextmarkprivate.h"
  67 #include "gtkalias.h"
  68
  69 /*
  70  * Types
  71  */
  72
  73
  74 /*
  75  * The structure below is used to pass information between
  76  * _gtk_text_btree_get_tags and inc_count:
  77  */
  78
  79 typedef struct TagInfo {
  80   int numTags;                  /* Number of tags for which there
  81                                  * is currently information in
  82                                  * tags and counts. */
  83   int arraySize;                        /* Number of entries allocated for
  84                                          * tags and counts. */
  85   GtkTextTag **tags;           /* Array of tags seen so far.
  86                                 * Malloc-ed. */
  87   int *counts;                  /* Toggle count (so far) for each
  88                                  * entry in tags.  Malloc-ed. */
  89 } TagInfo;
  90
  91
  92 /*
  93  * This is used to store per-view width/height info at the tree nodes.
  94  */
  95
  96 typedef struct _NodeData NodeData;
  97
  98 struct _NodeData {
  99   gpointer view_id;
 100   NodeData *next;
 101
 102   /* Height and width of this node */
 103   gint height;
 104   signed int width : 24;
 105
 106   /* boolean indicating whether the lines below this node are in need of validation.
 107    * However, width/height should always represent the current total width and
 108    * max height for lines below this node; the valid flag indicates whether the
 109    * width/height on the lines needs recomputing, not whether the totals
 110    * need recomputing.
 111    */
 112   guint valid : 8;              /* Actually a boolean */
 113 };
 114
 115
 116 /*
 117  * The data structure below keeps summary information about one tag as part
 118  * of the tag information in a node.
 119  */
 120
 121 typedef struct Summary {
 122   GtkTextTagInfo *info;                     /* Handle for tag. */
 123   int toggle_count;                     /* Number of transitions into or
 124                                          * out of this tag that occur in
 125                                          * the subtree rooted at this node. */
 126   struct Summary *next;         /* Next in list of all tags for same
 127                                  * node, or NULL if at end of list. */
 128 } Summary;
 129
 130 /*
 131  * The data structure below defines a node in the B-tree.
 132  */
 133
 134 struct _GtkTextBTreeNode {
 135   GtkTextBTreeNode *parent;         /* Pointer to parent node, or NULL if
 136                                      * this is the root. */
 137   GtkTextBTreeNode *next;           /* Next in list of siblings with the
 138                                      * same parent node, or NULL for end
 139                                      * of list. */
 140   Summary *summary;             /* First in malloc-ed list of info
 141                                  * about tags in this subtree (NULL if
 142                                  * no tag info in the subtree). */
 143   int level;                            /* Level of this node in the B-tree.
 144                                          * 0 refers to the bottom of the tree
 145                                          * (children are lines, not nodes). */
 146   union {                               /* First in linked list of children. */
 147     struct _GtkTextBTreeNode *node;         /* Used if level > 0. */
 148     GtkTextLine *line;         /* Used if level == 0. */
 149   } children;
 150   int num_children;                     /* Number of children of this node. */
 151   int num_lines;                        /* Total number of lines (leaves) in
 152                                          * the subtree rooted here. */
 153   int num_chars;                        /* Number of chars below here */
 154
 155   NodeData *node_data;
 156 };
 157
 158
 159 /*
 160  * Used to store the list of views in our btree
 161  */
 162
 163 typedef struct _BTreeView BTreeView;
 164
 165 struct _BTreeView {
 166   gpointer view_id;
 167   GtkTextLayout *layout;
 168   BTreeView *next;
 169   BTreeView *prev;
 170 };
 171
 172 /*
 173  * And the tree itself
 174  */
 175
 176 struct _GtkTextBTree {
 177   GtkTextBTreeNode *root_node;          /* Pointer to root of B-tree. */
 178   GtkTextTagTable *table;
 179   GHashTable *mark_table;
 180   guint refcount;
 181   GtkTextMark *insert_mark;
 182   GtkTextMark *selection_bound_mark;
 183   GtkTextBuffer *buffer;
 184   BTreeView *views;
 185   GSList *tag_infos;
 186   gulong tag_changed_handler;
 187
 188   /* Incremented when a segment with a byte size > 0
 189    * is added to or removed from the tree (i.e. the
 190    * length of a line may have changed, and lines may
 191    * have been added or removed). This invalidates
 192    * all outstanding iterators.
 193    */
 194   guint chars_changed_stamp;
 195   /* Incremented when any segments are added or deleted;
 196    * this makes outstanding iterators recalculate their
 197    * pointed-to segment and segment offset.
 198    */
 199   guint segments_changed_stamp;
 200
 201   /* Cache the last line in the buffer */
 202   GtkTextLine *last_line;
 203   guint last_line_stamp;
 204
 205   /* Cache the next-to-last line in the buffer,
 206    * containing the end iterator
 207    */
 208   GtkTextLine *end_iter_line;
 209   GtkTextLineSegment *end_iter_segment;
 210   int end_iter_segment_byte_index;
 211   int end_iter_segment_char_offset;
 212   guint end_iter_line_stamp;
 213   guint end_iter_segment_stamp;
 214
 215   GHashTable *child_anchor_table;
 216 };
 217
 218
 219 /*
 220  * Upper and lower bounds on how many children a node may have:
 221  * rebalance when either of these limits is exceeded.  MAX_CHILDREN
 222  * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
 223  */
 224
 225 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
 226    shallow. It appears to be faster to locate a particular line number
 227    if the tree is narrow and deep, since it is more finely sorted.  I
 228    guess this may increase memory use though, and make it slower to
 229    walk the tree in order, or locate a particular byte index (which
 230    is done by walking the tree in order).
 231
 232    There's basically a tradeoff here. However I'm thinking we want to
 233    add pixels, byte counts, and char counts to the tree nodes,
 234    at that point narrow and deep should speed up all operations,
 235    not just the line number searches.
 236 */
 237
 238 #if 1
 239 #define MAX_CHILDREN 12
 240 #define MIN_CHILDREN 6
 241 #else
 242 #define MAX_CHILDREN 6
 243 #define MIN_CHILDREN 3
 244 #endif
 245
 246 /*
 247  * Prototypes
 248  */
 249
 250 static BTreeView        *gtk_text_btree_get_view                 (GtkTextBTree     *tree,
 251                                                                   gpointer          view_id);
 252 static void              gtk_text_btree_rebalance                (GtkTextBTree     *tree,
 253                                                                   GtkTextBTreeNode *node);
 254 static GtkTextLine     * get_last_line                           (GtkTextBTree     *tree);
 255 static void              post_insert_fixup                       (GtkTextBTree     *tree,
 256                                                                   GtkTextLine      *insert_line,
 257                                                                   gint              char_count_delta,
 258                                                                   gint              line_count_delta);
 259 static void              gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
 260                                                                   GtkTextTagInfo   *info,
 261                                                                   gint              adjust);
 262 static gboolean          gtk_text_btree_node_has_tag             (GtkTextBTreeNode *node,
 263                                                                   GtkTextTag       *tag);
 264
 265 static void             segments_changed                (GtkTextBTree     *tree);
 266 static void             chars_changed                   (GtkTextBTree     *tree);
 267 static void             summary_list_destroy            (Summary          *summary);
 268 static GtkTextLine     *gtk_text_line_new               (void);
 269 static void             gtk_text_line_destroy           (GtkTextBTree     *tree,
 270                                                          GtkTextLine      *line);
 271 static void             gtk_text_line_set_parent        (GtkTextLine      *line,
 272                                                          GtkTextBTreeNode *node);
 273 static void             gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
 274                                                          gpointer          view_id);
 275
 276
 277 static NodeData         *node_data_new          (gpointer  view_id);
 278 static void              node_data_destroy      (NodeData *nd);
 279 static void              node_data_list_destroy (NodeData *nd);
 280 static NodeData         *node_data_find         (NodeData *nd,
 281                                                  gpointer  view_id);
 282
 283 static GtkTextBTreeNode     *gtk_text_btree_node_new                  (void);
 284 static void                  gtk_text_btree_node_invalidate_downward  (GtkTextBTreeNode *node);
 285 static void                  gtk_text_btree_node_invalidate_upward    (GtkTextBTreeNode *node,
 286                                                                        gpointer          view_id);
 287 static NodeData *            gtk_text_btree_node_check_valid          (GtkTextBTreeNode *node,
 288                                                                        gpointer          view_id);
 289 static NodeData *            gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
 290                                                                        gpointer          view_id);
 291 static void                  gtk_text_btree_node_check_valid_upward   (GtkTextBTreeNode *node,
 292                                                                        gpointer          view_id);
 293
 294 static void                  gtk_text_btree_node_remove_view         (BTreeView        *view,
 295                                                                       GtkTextBTreeNode *node,
 296                                                                       gpointer          view_id);
 297 static void                  gtk_text_btree_node_destroy             (GtkTextBTree     *tree,
 298                                                                       GtkTextBTreeNode *node);
 299 static void                  gtk_text_btree_node_free_empty          (GtkTextBTree *tree,
 300                                                                       GtkTextBTreeNode *node);
 301 static NodeData         *    gtk_text_btree_node_ensure_data         (GtkTextBTreeNode *node,
 302                                                                       gpointer          view_id);
 303 static void                  gtk_text_btree_node_remove_data         (GtkTextBTreeNode *node,
 304                                                                       gpointer          view_id);
 305 static void                  gtk_text_btree_node_get_size            (GtkTextBTreeNode *node,
 306                                                                       gpointer          view_id,
 307                                                                       gint             *width,
 308                                                                       gint             *height);
 309 static GtkTextBTreeNode *    gtk_text_btree_node_common_parent       (GtkTextBTreeNode *node1,
 310                                                                       GtkTextBTreeNode *node2);
 311 static void get_tree_bounds       (GtkTextBTree     *tree,
 312                                    GtkTextIter      *start,
 313                                    GtkTextIter      *end);
 314 static void tag_changed_cb        (GtkTextTagTable  *table,
 315                                    GtkTextTag       *tag,
 316                                    gboolean          size_changed,
 317                                    GtkTextBTree     *tree);
 318 static void cleanup_line          (GtkTextLine      *line);
 319 static void recompute_node_counts (GtkTextBTree     *tree,
 320                                    GtkTextBTreeNode *node);
 321 static void inc_count             (GtkTextTag       *tag,
 322                                    int               inc,
 323                                    TagInfo          *tagInfoPtr);
 324
 325 static void summary_destroy       (Summary          *summary);
 326
 327 static void gtk_text_btree_link_segment   (GtkTextLineSegment *seg,
 328                                            const GtkTextIter  *iter);
 329 static void gtk_text_btree_unlink_segment (GtkTextBTree       *tree,
 330                                            GtkTextLineSegment *seg,
 331                                            GtkTextLine        *line);
 332
 333
 334 static GtkTextTagInfo *gtk_text_btree_get_tag_info          (GtkTextBTree   *tree,
 335                                                              GtkTextTag     *tag);
 336 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree   *tree,
 337                                                              GtkTextTag     *tag);
 338 static void            gtk_text_btree_remove_tag_info       (GtkTextBTree   *tree,
 339                                                              GtkTextTag     *tag);
 340
 341 static void redisplay_region (GtkTextBTree      *tree,
 342                               const GtkTextIter *start,
 343                               const GtkTextIter *end);
 344
 345 /* Inline thingies */
 346
 347 static inline void
 348 segments_changed (GtkTextBTree *tree)
 349 {
 350   tree->segments_changed_stamp += 1;
 351 }
 352
 353 static inline void
 354 chars_changed (GtkTextBTree *tree)
 355 {
 356   tree->chars_changed_stamp += 1;
 357 }
 358
 359 /*
 360  * BTree operations
 361  */
 362
 363 GtkTextBTree*
 364 _gtk_text_btree_new (GtkTextTagTable *table,
 365                      GtkTextBuffer *buffer)
 366 {
 367   GtkTextBTree *tree;
 368   GtkTextBTreeNode *root_node;
 369   GtkTextLine *line, *line2;
 370
 371   g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
 372   g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);
 373
 374   /*
 375    * The tree will initially have two empty lines.  The second line
 376    * isn't actually part of the tree's contents, but its presence
 377    * makes several operations easier.  The tree will have one GtkTextBTreeNode,
 378    * which is also the root of the tree.
 379    */
 380
 381   /* Create the root node. */
 382
 383   root_node = gtk_text_btree_node_new ();
 384
 385   line = gtk_text_line_new ();
 386   line2 = gtk_text_line_new ();
 387
 388   root_node->parent = NULL;
 389   root_node->next = NULL;
 390   root_node->summary = NULL;
 391   root_node->level = 0;
 392   root_node->children.line = line;
 393   root_node->num_children = 2;
 394   root_node->num_lines = 2;
 395   root_node->num_chars = 2;
 396
 397   line->parent = root_node;
 398   line->next = line2;
 399
 400   line->segments = _gtk_char_segment_new ("\n", 1);
 401
 402   line2->parent = root_node;
 403   line2->next = NULL;
 404   line2->segments = _gtk_char_segment_new ("\n", 1);
 405
 406   /* Create the tree itself */
 407
 408   tree = g_new0(GtkTextBTree, 1);
 409   tree->root_node = root_node;
 410   tree->table = table;
 411   tree->views = NULL;
 412
 413   /* Set these to values that are unlikely to be found
 414    * in random memory garbage, and also avoid
 415    * duplicates between tree instances.
 416    */
 417   tree->chars_changed_stamp = g_random_int ();
 418   tree->segments_changed_stamp = g_random_int ();
 419
 420   tree->last_line_stamp = tree->chars_changed_stamp - 1;
 421   tree->last_line = NULL;
 422
 423   tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
 424   tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
 425   tree->end_iter_line = NULL;
 426   tree->end_iter_segment_byte_index = 0;
 427   tree->end_iter_segment_char_offset = 0;
 428
 429   g_object_ref (tree->table);
 430
 431   tree->tag_changed_handler = g_signal_connect (tree->table,
 432                                                 "tag_changed",
 433                                                 G_CALLBACK (tag_changed_cb),
 434                                                 tree);
 435
 436   tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
 437   tree->child_anchor_table = NULL;
 438
 439   /* We don't ref the buffer, since the buffer owns us;
 440    * we'd have some circularity issues. The buffer always
 441    * lasts longer than the BTree
 442    */
 443   tree->buffer = buffer;
 444
 445   {
 446     GtkTextIter start;
 447     GtkTextLineSegment *seg;
 448
 449     _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
 450
 451
 452     tree->insert_mark = _gtk_text_btree_set_mark (tree,
 453                                                  NULL,
 454                                                  "insert",
 455                                                  FALSE,
 456                                                  &start,
 457                                                  FALSE);
 458
 459     seg = tree->insert_mark->segment;
 460
 461     seg->body.mark.not_deleteable = TRUE;
 462     seg->body.mark.visible = TRUE;
 463
 464     tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
 465                                                           NULL,
 466                                                           "selection_bound",
 467                                                           FALSE,
 468                                                           &start,
 469                                                           FALSE);
 470
 471     seg = tree->selection_bound_mark->segment;
 472
 473     seg->body.mark.not_deleteable = TRUE;
 474
 475     g_object_ref (tree->insert_mark);
 476     g_object_ref (tree->selection_bound_mark);
 477   }
 478
 479   tree->refcount = 1;
 480
 481   return tree;
 482 }
 483
 484 void
 485 _gtk_text_btree_ref (GtkTextBTree *tree)
 486 {
 487   g_return_if_fail (tree != NULL);
 488   g_return_if_fail (tree->refcount > 0);
 489
 490   tree->refcount += 1;
 491 }
 492
 493 void
 494 _gtk_text_btree_unref (GtkTextBTree *tree)
 495 {
 496   g_return_if_fail (tree != NULL);
 497   g_return_if_fail (tree->refcount > 0);
 498
 499   tree->refcount -= 1;
 500
 501   if (tree->refcount == 0)
 502     {
 503       g_signal_handler_disconnect (tree->table,
 504                                    tree->tag_changed_handler);
 505
 506       g_object_unref (tree->table);
 507       tree->table = NULL;
 508
 509       gtk_text_btree_node_destroy (tree, tree->root_node);
 510       tree->root_node = NULL;
 511
 512       g_assert (g_hash_table_size (tree->mark_table) == 0);
 513       g_hash_table_destroy (tree->mark_table);
 514       tree->mark_table = NULL;
 515       if (tree->child_anchor_table != NULL)
 516         {
 517           g_hash_table_destroy (tree->child_anchor_table);
 518           tree->child_anchor_table = NULL;
 519         }
 520
 521       g_object_unref (tree->insert_mark);
 522       tree->insert_mark = NULL;
 523       g_object_unref (tree->selection_bound_mark);
 524       tree->selection_bound_mark = NULL;
 525
 526       g_free (tree);
 527     }
 528 }
 529
 530 GtkTextBuffer*
 531 _gtk_text_btree_get_buffer (GtkTextBTree *tree)
 532 {
 533   return tree->buffer;
 534 }
 535
 536 guint
 537 _gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
 538 {
 539   return tree->chars_changed_stamp;
 540 }
 541
 542 guint
 543 _gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
 544 {
 545   return tree->segments_changed_stamp;
 546 }
 547
 548 void
 549 _gtk_text_btree_segments_changed (GtkTextBTree *tree)
 550 {
 551   g_return_if_fail (tree != NULL);
 552   segments_changed (tree);
 553 }
 554
 555 /*
 556  * Indexable segment mutation
 557  */
 558
 559 /*
 560  *  The following function is responsible for resolving the bidi direction
 561  *  for the lines between start and end. But it also calculates any
 562  *  dependent bidi direction for surrounding lines that change as a result
 563  *  of the bidi direction decisions within the range. The function is
 564  *  trying to do as little propagation as is needed.
 565  */
 566 static void
 567 gtk_text_btree_resolve_bidi (GtkTextIter *start,
 568                              GtkTextIter *end)
 569 {
 570   GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
 571   GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
 572   PangoDirection last_strong, dir_above_propagated, dir_below_propagated;
 573
 574   /* Resolve the strong bidi direction for all lines between
 575    * start and end.
 576   */
 577   start_line = _gtk_text_iter_get_text_line (start);
 578   start_line_prev = _gtk_text_line_previous (start_line);
 579   end_line = _gtk_text_iter_get_text_line (end);
 580   end_line_next = _gtk_text_line_next (end_line);
 581
 582   line = start_line;
 583   while (line && line != end_line_next)
 584     {
 585       /* Loop through the segments and search for a strong character
 586        */
 587       GtkTextLineSegment *seg = line->segments;
 588       line->dir_strong = PANGO_DIRECTION_NEUTRAL;
 589
 590       while (seg)
 591         {
 592           if (seg->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   redisplay_region (tree, ins, bound);
2853 }
2854
2855
2856 void
2857 _gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2858                                     const gchar *name)
2859 {
2860   GtkTextMark *mark;
2861
2862   g_return_if_fail (tree != NULL);
2863   g_return_if_fail (name != NULL);
2864
2865   mark = g_hash_table_lookup (tree->mark_table,
2866                               name);
2867
2868   _gtk_text_btree_remove_mark (tree, mark);
2869 }
2870
2871 void
2872 _gtk_text_btree_release_mark_segment (GtkTextBTree       *tree,
2873                                       GtkTextLineSegment *segment)
2874 {
2875
2876   if (segment->body.mark.name)
2877     g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2878
2879   segment->body.mark.tree = NULL;
2880   segment->body.mark.line = NULL;
2881
2882   /* Remove the ref on the mark, which frees segment as a side effect
2883    * if this is the last reference.
2884    */
2885   g_object_unref (segment->body.mark.obj);
2886 }
2887
2888 void
2889 _gtk_text_btree_remove_mark (GtkTextBTree *tree,
2890                              GtkTextMark *mark)
2891 {
2892   GtkTextLineSegment *segment;
2893
2894   g_return_if_fail (mark != NULL);
2895   g_return_if_fail (tree != NULL);
2896
2897   segment = mark->segment;
2898
2899   if (segment->body.mark.not_deleteable)
2900     {
2901       g_warning ("Can't delete special mark `%s'", segment->body.mark.name);
2902       return;
2903     }
2904
2905   /* This calls cleanup_line and segments_changed */
2906   gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2907
2908   _gtk_text_btree_release_mark_segment (tree, segment);
2909 }
2910
2911 gboolean
2912 _gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2913                                 GtkTextMark *segment)
2914 {
2915   return segment == tree->insert_mark;
2916 }
2917
2918 gboolean
2919 _gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2920                                          GtkTextMark *segment)
2921 {
2922   return segment == tree->selection_bound_mark;
2923 }
2924
2925 GtkTextMark*
2926 _gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2927                                   const gchar *name)
2928 {
2929   GtkTextLineSegment *seg;
2930
2931   g_return_val_if_fail (tree != NULL, NULL);
2932   g_return_val_if_fail (name != NULL, NULL);
2933
2934   seg = g_hash_table_lookup (tree->mark_table, name);
2935
2936   return seg ? seg->body.mark.obj : NULL;
2937 }
2938
2939 /**
2940  * gtk_text_mark_set_visible:
2941  * @mark: a #GtkTextMark
2942  * @setting: visibility of mark
2943  *
2944  * Sets the visibility of @mark; the insertion point is normally
2945  * visible, i.e. you can see it as a vertical bar. Also, the text
2946  * widget uses a visible mark to indicate where a drop will occur when
2947  * dragging-and-dropping text. Most other marks are not visible.
2948  * Marks are not visible by default.
2949  *
2950  **/
2951 void
2952 gtk_text_mark_set_visible (GtkTextMark       *mark,
2953                            gboolean           setting)
2954 {
2955   GtkTextLineSegment *seg;
2956
2957   g_return_if_fail (mark != NULL);
2958
2959   seg = mark->segment;
2960
2961   if (seg->body.mark.visible == setting)
2962     return;
2963   else
2964     {
2965       seg->body.mark.visible = setting;
2966
2967       redisplay_mark (seg);
2968     }
2969 }
2970
2971 GtkTextLine*
2972 _gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2973                                         GtkTextTag *tag)
2974 {
2975   GtkTextBTreeNode *node;
2976   GtkTextTagInfo *info;
2977
2978   g_return_val_if_fail (tree != NULL, NULL);
2979
2980   if (tag != NULL)
2981     {
2982       info = gtk_text_btree_get_existing_tag_info (tree, tag);
2983
2984       if (info == NULL)
2985         return NULL;
2986
2987       if (info->tag_root == NULL)
2988         return NULL;
2989
2990       node = info->tag_root;
2991
2992       /* We know the tag root has instances of the given
2993          tag below it */
2994
2995     continue_outer_loop:
2996       g_assert (node != NULL);
2997       while (node->level > 0)
2998         {
2999           g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3000           node = node->children.node;
3001           while (node != NULL)
3002             {
3003               if (gtk_text_btree_node_has_tag (node, tag))
3004                 goto continue_outer_loop;
3005
3006               node = node->next;
3007             }
3008           g_assert (node != NULL);
3009         }
3010
3011       g_assert (node != NULL); /* The tag summaries said some node had
3012                                   tag toggles... */
3013
3014       g_assert (node->level == 0);
3015
3016       return node->children.line;
3017     }
3018   else
3019     {
3020       /* Looking for any tag at all (tag == NULL).
3021          Unfortunately this can't be done in a simple and efficient way
3022          right now; so I'm just going to return the
3023          first line in the btree. FIXME */
3024       return _gtk_text_btree_get_line (tree, 0, NULL);
3025     }
3026 }
3027
3028 GtkTextLine*
3029 _gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
3030                                        GtkTextTag *tag)
3031 {
3032   GtkTextBTreeNode *node;
3033   GtkTextBTreeNode *last_node;
3034   GtkTextLine *line;
3035   GtkTextTagInfo *info;
3036
3037   g_return_val_if_fail (tree != NULL, NULL);
3038
3039   if (tag != NULL)
3040     {
3041       info = gtk_text_btree_get_existing_tag_info (tree, tag);
3042
3043       if (info->tag_root == NULL)
3044         return NULL;
3045
3046       node = info->tag_root;
3047       /* We know the tag root has instances of the given
3048          tag below it */
3049
3050       while (node->level > 0)
3051         {
3052           g_assert (node != NULL); /* Failure probably means bad tag summaries. */
3053           last_node = NULL;
3054           node = node->children.node;
3055           while (node != NULL)
3056             {
3057               if (gtk_text_btree_node_has_tag (node, tag))
3058                 last_node = node;
3059               node = node->next;
3060             }
3061
3062           node = last_node;
3063         }
3064
3065       g_assert (node != NULL); /* The tag summaries said some node had
3066                                   tag toggles... */
3067
3068       g_assert (node->level == 0);
3069
3070       /* Find the last line in this node */
3071       line = node->children.line;
3072       while (line->next != NULL)
3073         line = line->next;
3074
3075       return line;
3076     }
3077   else
3078     {
3079       /* This search can't be done efficiently at the moment,
3080          at least not without complexity.
3081          So, we just return the last line.
3082       */
3083       return _gtk_text_btree_get_end_iter_line (tree);
3084     }
3085 }
3086
3087
3088 /*
3089  * Lines
3090  */
3091
3092 gint
3093 _gtk_text_line_get_number (GtkTextLine *line)
3094 {
3095   GtkTextLine *line2;
3096   GtkTextBTreeNode *node, *parent, *node2;
3097   int index;
3098
3099   /*
3100    * First count how many lines precede this one in its level-0
3101    * GtkTextBTreeNode.
3102    */
3103
3104   node = line->parent;
3105   index = 0;
3106   for (line2 = node->children.line; line2 != line;
3107        line2 = line2->next)
3108     {
3109       if (line2 == NULL)
3110         {
3111           g_error ("gtk_text_btree_line_number couldn't find line");
3112         }
3113       index += 1;
3114     }
3115
3116   /*
3117    * Now work up through the levels of the tree one at a time,
3118    * counting how many lines are in GtkTextBTreeNodes preceding the current
3119    * GtkTextBTreeNode.
3120    */
3121
3122   for (parent = node->parent ; parent != NULL;
3123        node = parent, parent = parent->parent)
3124     {
3125       for (node2 = parent->children.node; node2 != node;
3126            node2 = node2->next)
3127         {
3128           if (node2 == NULL)
3129             {
3130               g_error ("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
3131             }
3132           index += node2->num_lines;
3133         }
3134     }
3135   return index;
3136 }
3137
3138 static GtkTextLineSegment*
3139 find_toggle_segment_before_char (GtkTextLine *line,
3140                                  gint char_in_line,
3141                                  GtkTextTag *tag)
3142 {
3143   GtkTextLineSegment *seg;
3144   GtkTextLineSegment *toggle_seg;
3145   int index;
3146
3147   toggle_seg = NULL;
3148   index = 0;
3149   seg = line->segments;
3150   while ( (index + seg->char_count) <= char_in_line )
3151     {
3152       if (((seg->type == &gtk_text_toggle_on_type)
3153            || (seg->type == &gtk_text_toggle_off_type))
3154           && (seg->body.toggle.info->tag == tag))
3155         toggle_seg = seg;
3156
3157       index += seg->char_count;
3158       seg = seg->next;
3159     }
3160
3161   return toggle_seg;
3162 }
3163
3164 static GtkTextLineSegment*
3165 find_toggle_segment_before_byte (GtkTextLine *line,
3166                                  gint byte_in_line,
3167                                  GtkTextTag *tag)
3168 {
3169   GtkTextLineSegment *seg;
3170   GtkTextLineSegment *toggle_seg;
3171   int index;
3172
3173   toggle_seg = NULL;
3174   index = 0;
3175   seg = line->segments;
3176   while ( (index + seg->byte_count) <= byte_in_line )
3177     {
3178       if (((seg->type == &gtk_text_toggle_on_type)
3179            || (seg->type == &gtk_text_toggle_off_type))
3180           && (seg->body.toggle.info->tag == tag))
3181         toggle_seg = seg;
3182
3183       index += seg->byte_count;
3184       seg = seg->next;
3185     }
3186
3187   return toggle_seg;
3188 }
3189
3190 static gboolean
3191 find_toggle_outside_current_line (GtkTextLine *line,
3192                                   GtkTextBTree *tree,
3193                                   GtkTextTag *tag)
3194 {
3195   GtkTextBTreeNode *node;
3196   GtkTextLine *sibling_line;
3197   GtkTextLineSegment *seg;
3198   GtkTextLineSegment *toggle_seg;
3199   int toggles;
3200   GtkTextTagInfo *info = NULL;
3201
3202   /*
3203    * No toggle in this line.  Look for toggles for the tag in lines
3204    * that are predecessors of line but under the same
3205    * level-0 GtkTextBTreeNode.
3206    */
3207   toggle_seg = NULL;
3208   sibling_line = line->parent->children.line;
3209   while (sibling_line != line)
3210     {
3211       seg = sibling_line->segments;
3212       while (seg != NULL)
3213         {
3214           if (((seg->type == &gtk_text_toggle_on_type)
3215                || (seg->type == &gtk_text_toggle_off_type))
3216               && (seg->body.toggle.info->tag == tag))
3217             toggle_seg = seg;
3218
3219           seg = seg->next;
3220         }
3221
3222       sibling_line = sibling_line->next;
3223     }
3224
3225   if (toggle_seg != NULL)
3226     return (toggle_seg->type == &gtk_text_toggle_on_type);
3227
3228   /*
3229    * No toggle in this GtkTextBTreeNode.  Scan upwards through the ancestors of
3230    * this GtkTextBTreeNode, counting the number of toggles of the given tag in
3231    * siblings that precede that GtkTextBTreeNode.
3232    */
3233
3234   info = gtk_text_btree_get_existing_tag_info (tree, tag);
3235
3236   if (info == NULL)
3237     return FALSE;
3238
3239   toggles = 0;
3240   node = line->parent;
3241   while (node->parent != NULL)
3242     {
3243       GtkTextBTreeNode *sibling_node;
3244
3245       sibling_node = node->parent->children.node;
3246       while (sibling_node != node)
3247         {
3248           Summary *summary;
3249
3250           summary = sibling_node->summary;
3251           while (summary != NULL)
3252             {
3253               if (summary->info == info)
3254                 toggles += summary->toggle_count;
3255
3256               summary = summary->next;
3257             }
3258
3259           sibling_node = sibling_node->next;
3260         }
3261
3262       if (node == info->tag_root)
3263         break;
3264
3265       node = node->parent;
3266     }
3267
3268   /*
3269    * An odd number of toggles means that the tag is present at the
3270    * given point.
3271    */
3272
3273   return (toggles & 1) != 0;
3274 }
3275
3276 /* FIXME this function is far too slow, for no good reason. */
3277 gboolean
3278 _gtk_text_line_char_has_tag (GtkTextLine *line,
3279                              GtkTextBTree *tree,
3280                              gint char_in_line,
3281                              GtkTextTag *tag)
3282 {
3283   GtkTextLineSegment *toggle_seg;
3284
3285   g_return_val_if_fail (line != NULL, FALSE);
3286
3287   /*
3288    * Check for toggles for the tag in the line but before
3289    * the char.  If there is one, its type indicates whether or
3290    * not the character is tagged.
3291    */
3292
3293   toggle_seg = find_toggle_segment_before_char (line, char_in_line, tag);
3294
3295   if (toggle_seg != NULL)
3296     return (toggle_seg->type == &gtk_text_toggle_on_type);
3297   else
3298     return find_toggle_outside_current_line (line, tree, tag);
3299 }
3300
3301 gboolean
3302 _gtk_text_line_byte_has_tag (GtkTextLine *line,
3303                              GtkTextBTree *tree,
3304                              gint byte_in_line,
3305                              GtkTextTag *tag)
3306 {
3307   GtkTextLineSegment *toggle_seg;
3308
3309   g_return_val_if_fail (line != NULL, FALSE);
3310
3311   /*
3312    * Check for toggles for the tag in the line but before
3313    * the char.  If there is one, its type indicates whether or
3314    * not the character is tagged.
3315    */
3316
3317   toggle_seg = find_toggle_segment_before_byte (line, byte_in_line, tag);
3318
3319   if (toggle_seg != NULL)
3320     return (toggle_seg->type == &gtk_text_toggle_on_type);
3321   else
3322     return find_toggle_outside_current_line (line, tree, tag);
3323 }
3324
3325 gboolean
3326 _gtk_text_line_is_last (GtkTextLine *line,
3327                         GtkTextBTree *tree)
3328 {
3329   return line == get_last_line (tree);
3330 }
3331
3332 static void
3333 ensure_end_iter_line (GtkTextBTree *tree)
3334 {
3335   if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3336     {
3337       int n_lines;
3338       int real_line;
3339
3340       /* n_lines is without the magic line at the end */
3341       n_lines = _gtk_text_btree_line_count (tree);
3342
3343       g_assert (n_lines >= 1);
3344
3345       tree->end_iter_line = _gtk_text_btree_get_line_no_last (tree, -1, &real_line);
3346
3347       tree->end_iter_line_stamp = tree->chars_changed_stamp;
3348     }
3349 }
3350
3351 static void
3352 ensure_end_iter_segment (GtkTextBTree *tree)
3353 {
3354   if (tree->end_iter_segment_stamp != tree->segments_changed_stamp)
3355     {
3356       GtkTextLineSegment *seg;
3357       GtkTextLineSegment *last_with_chars;
3358
3359       ensure_end_iter_line (tree);
3360
3361       last_with_chars = NULL;
3362
3363       seg = tree->end_iter_line->segments;
3364       while (seg != NULL)
3365         {
3366           if (seg->char_count > 0)
3367             last_with_chars = seg;
3368           seg = seg->next;
3369         }
3370
3371       tree->end_iter_segment = last_with_chars;
3372
3373       /* We know the last char in the last line is '\n' */
3374       tree->end_iter_segment_byte_index = last_with_chars->byte_count - 1;
3375       tree->end_iter_segment_char_offset = last_with_chars->char_count - 1;
3376
3377       tree->end_iter_segment_stamp = tree->segments_changed_stamp;
3378
3379       g_assert (tree->end_iter_segment->type == &gtk_text_char_type);
3380       g_assert (tree->end_iter_segment->body.chars[tree->end_iter_segment_byte_index] == '\n');
3381     }
3382 }
3383
3384 gboolean
3385 _gtk_text_line_contains_end_iter (GtkTextLine  *line,
3386                                   GtkTextBTree *tree)
3387 {
3388   ensure_end_iter_line (tree);
3389
3390   return line == tree->end_iter_line;
3391 }
3392
3393 gboolean
3394 _gtk_text_btree_is_end (GtkTextBTree       *tree,
3395                         GtkTextLine        *line,
3396                         GtkTextLineSegment *seg,
3397                         int                 byte_index,
3398                         int                 char_offset)
3399 {
3400   g_return_val_if_fail (byte_index >= 0 || char_offset >= 0, FALSE);
3401
3402   /* Do this first to avoid walking segments in most cases */
3403   if (!_gtk_text_line_contains_end_iter (line, tree))
3404     return FALSE;
3405
3406   ensure_end_iter_segment (tree);
3407
3408   if (seg != tree->end_iter_segment)
3409     return FALSE;
3410
3411   if (byte_index >= 0)
3412     return byte_index == tree->end_iter_segment_byte_index;
3413   else
3414     return char_offset == tree->end_iter_segment_char_offset;
3415 }
3416
3417 GtkTextLine*
3418 _gtk_text_line_next (GtkTextLine *line)
3419 {
3420   GtkTextBTreeNode *node;
3421
3422   if (line->next != NULL)
3423     return line->next;
3424   else
3425     {
3426       /*
3427        * This was the last line associated with the particular parent
3428        * GtkTextBTreeNode.  Search up the tree for the next GtkTextBTreeNode,
3429        * then search down from that GtkTextBTreeNode to find the first
3430        * line.
3431        */
3432
3433       node = line->parent;
3434       while (node != NULL && node->next == NULL)
3435         node = node->parent;
3436
3437       if (node == NULL)
3438         return NULL;
3439
3440       node = node->next;
3441       while (node->level > 0)
3442         {
3443           node = node->children.node;
3444         }
3445
3446       g_assert (node->children.line != line);
3447
3448       return node->children.line;
3449     }
3450 }
3451
3452 GtkTextLine*
3453 _gtk_text_line_next_excluding_last (GtkTextLine *line)
3454 {
3455   GtkTextLine *next;
3456
3457   next = _gtk_text_line_next (line);
3458
3459   /* If we were on the end iter line, we can't go to
3460    * the last line
3461    */
3462   if (next && next->next == NULL && /* these checks are optimization only */
3463       _gtk_text_line_next (next) == NULL)
3464     return NULL;
3465
3466   return next;
3467 }
3468
3469 GtkTextLine*
3470 _gtk_text_line_previous (GtkTextLine *line)
3471 {
3472   GtkTextBTreeNode *node;
3473   GtkTextBTreeNode *node2;
3474   GtkTextLine *prev;
3475
3476   /*
3477    * Find the line under this GtkTextBTreeNode just before the starting line.
3478    */
3479   prev = line->parent->children.line;        /* First line at leaf */
3480   while (prev != line)
3481     {
3482       if (prev->next == line)
3483         return prev;
3484
3485       prev = prev->next;
3486
3487       if (prev == NULL)
3488         g_error ("gtk_text_btree_previous_line ran out of lines");
3489     }
3490
3491   /*
3492    * This was the first line associated with the particular parent
3493    * GtkTextBTreeNode.  Search up the tree for the previous GtkTextBTreeNode,
3494    * then search down from that GtkTextBTreeNode to find its last line.
3495    */
3496   for (node = line->parent; ; node = node->parent)
3497     {
3498       if (node == NULL || node->parent == NULL)
3499         return NULL;
3500       else if (node != node->parent->children.node)
3501         break;
3502     }
3503
3504   for (node2 = node->parent->children.node; ;
3505        node2 = node2->children.node)
3506     {
3507       while (node2->next != node)
3508         node2 = node2->next;
3509
3510       if (node2->level == 0)
3511         break;
3512
3513       node = NULL;
3514     }
3515
3516   for (prev = node2->children.line ; ; prev = prev->next)
3517     {
3518       if (prev->next == NULL)
3519         return prev;
3520     }
3521
3522   g_assert_not_reached ();
3523   return NULL;
3524 }
3525
3526
3527 GtkTextLineData*
3528 _gtk_text_line_data_new (GtkTextLayout *layout,
3529                          GtkTextLine   *line)
3530 {
3531   GtkTextLineData *line_data;
3532
3533   line_data = g_new (GtkTextLineData, 1);
3534
3535   line_data->view_id = layout;
3536   line_data->next = NULL;
3537   line_data->width = 0;
3538   line_data->height = 0;
3539   line_data->valid = FALSE;
3540
3541   return line_data;
3542 }
3543
3544 void
3545 _gtk_text_line_add_data (GtkTextLine     *line,
3546                          GtkTextLineData *data)
3547 {
3548   g_return_if_fail (line != NULL);
3549   g_return_if_fail (data != NULL);
3550   g_return_if_fail (data->view_id != NULL);
3551
3552   if (line->views)
3553     {
3554       data->next = line->views;
3555       line->views = data;
3556     }
3557   else
3558     {
3559       line->views = data;
3560     }
3561 }
3562
3563 gpointer
3564 _gtk_text_line_remove_data (GtkTextLine *line,
3565                            gpointer view_id)
3566 {
3567   GtkTextLineData *prev;
3568   GtkTextLineData *iter;
3569
3570   g_return_val_if_fail (line != NULL, NULL);
3571   g_return_val_if_fail (view_id != NULL, NULL);
3572
3573   prev = NULL;
3574   iter = line->views;
3575   while (iter != NULL)
3576     {
3577       if (iter->view_id == view_id)
3578         break;
3579       prev = iter;
3580       iter = iter->next;
3581     }
3582
3583   if (iter)
3584     {
3585       if (prev)
3586         prev->next = iter->next;
3587       else
3588         line->views = iter->next;
3589
3590       return iter;
3591     }
3592   else
3593     return NULL;
3594 }
3595
3596 gpointer
3597 _gtk_text_line_get_data (GtkTextLine *line,
3598                          gpointer view_id)
3599 {
3600   GtkTextLineData *iter;
3601
3602   g_return_val_if_fail (line != NULL, NULL);
3603   g_return_val_if_fail (view_id != NULL, NULL);
3604
3605   iter = line->views;
3606   while (iter != NULL)
3607     {
3608       if (iter->view_id == view_id)
3609         break;
3610       iter = iter->next;
3611     }
3612
3613   return iter;
3614 }
3615
3616 void
3617 _gtk_text_line_invalidate_wrap (GtkTextLine *line,
3618                                 GtkTextLineData *ld)
3619 {
3620   /* For now this is totally unoptimized. FIXME?
3621
3622      We could probably optimize the case where the width removed
3623      is less than the max width for the parent node,
3624      and the case where the height is unchanged when we re-wrap.
3625   */
3626
3627   g_return_if_fail (ld != NULL);
3628
3629   ld->valid = FALSE;
3630   gtk_text_btree_node_invalidate_upward (line->parent, ld->view_id);
3631 }
3632
3633 gint
3634 _gtk_text_line_char_count (GtkTextLine *line)
3635 {
3636   GtkTextLineSegment *seg;
3637   gint size;
3638
3639   size = 0;
3640   seg = line->segments;
3641   while (seg != NULL)
3642     {
3643       size += seg->char_count;
3644       seg = seg->next;
3645     }
3646   return size;
3647 }
3648
3649 gint
3650 _gtk_text_line_byte_count (GtkTextLine *line)
3651 {
3652   GtkTextLineSegment *seg;
3653   gint size;
3654
3655   size = 0;
3656   seg = line->segments;
3657   while (seg != NULL)
3658     {
3659       size += seg->byte_count;
3660       seg = seg->next;
3661     }
3662
3663   return size;
3664 }
3665
3666 gint
3667 _gtk_text_line_char_index (GtkTextLine *target_line)
3668 {
3669   GSList *node_stack = NULL;
3670   GtkTextBTreeNode *iter;
3671   GtkTextLine *line;
3672   gint num_chars;
3673
3674   /* Push all our parent nodes onto a stack */
3675   iter = target_line->parent;
3676
3677   g_assert (iter != NULL);
3678
3679   while (iter != NULL)
3680     {
3681       node_stack = g_slist_prepend (node_stack, iter);
3682
3683       iter = iter->parent;
3684     }
3685
3686   /* Check that we have the root node on top of the stack. */
3687   g_assert (node_stack != NULL &&
3688             node_stack->data != NULL &&
3689             ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3690
3691   /* Add up chars in all nodes before the nodes in our stack.
3692    */
3693
3694   num_chars = 0;
3695   iter = node_stack->data;
3696   while (iter != NULL)
3697     {
3698       GtkTextBTreeNode *child_iter;
3699       GtkTextBTreeNode *next_node;
3700
3701       next_node = node_stack->next ?
3702         node_stack->next->data : NULL;
3703       node_stack = g_slist_remove (node_stack, node_stack->data);
3704
3705       if (iter->level == 0)
3706         {
3707           /* stack should be empty when we're on the last node */
3708           g_assert (node_stack == NULL);
3709           break; /* Our children are now lines */
3710         }
3711
3712       g_assert (next_node != NULL);
3713       g_assert (iter != NULL);
3714       g_assert (next_node->parent == iter);
3715
3716       /* Add up chars before us in the tree */
3717       child_iter = iter->children.node;
3718       while (child_iter != next_node)
3719         {
3720           g_assert (child_iter != NULL);
3721
3722           num_chars += child_iter->num_chars;
3723
3724           child_iter = child_iter->next;
3725         }
3726
3727       iter = next_node;
3728     }
3729
3730   g_assert (iter != NULL);
3731   g_assert (iter == target_line->parent);
3732
3733   /* Since we don't store char counts in lines, only in segments, we
3734      have to iterate over the lines adding up segment char counts
3735      until we find our line.  */
3736   line = iter->children.line;
3737   while (line != target_line)
3738     {
3739       g_assert (line != NULL);
3740
3741       num_chars += _gtk_text_line_char_count (line);
3742
3743       line = line->next;
3744     }
3745
3746   g_assert (line == target_line);
3747
3748   return num_chars;
3749 }
3750
3751 GtkTextLineSegment*
3752 _gtk_text_line_byte_to_segment (GtkTextLine *line,
3753                                gint byte_offset,
3754                                gint *seg_offset)
3755 {
3756   GtkTextLineSegment *seg;
3757   int offset;
3758
3759   g_return_val_if_fail (line != NULL, NULL);
3760
3761   offset = byte_offset;
3762   seg = line->segments;
3763
3764   while (offset >= seg->byte_count)
3765     {
3766       g_assert (seg != NULL); /* means an invalid byte index */
3767       offset -= seg->byte_count;
3768       seg = seg->next;
3769     }
3770
3771   if (seg_offset)
3772     *seg_offset = offset;
3773
3774   return seg;
3775 }
3776
3777 GtkTextLineSegment*
3778 _gtk_text_line_char_to_segment (GtkTextLine *line,
3779                                gint char_offset,
3780                                gint *seg_offset)
3781 {
3782   GtkTextLineSegment *seg;
3783   int offset;
3784
3785   g_return_val_if_fail (line != NULL, NULL);
3786
3787   offset = char_offset;
3788   seg = line->segments;
3789
3790   while (offset >= seg->char_count)
3791     {
3792       g_assert (seg != NULL); /* means an invalid char index */
3793       offset -= seg->char_count;
3794       seg = seg->next;
3795     }
3796
3797   if (seg_offset)
3798     *seg_offset = offset;
3799
3800   return seg;
3801 }
3802
3803 GtkTextLineSegment*
3804 _gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3805                                    gint byte_offset,
3806                                    gint *seg_offset)
3807 {
3808   GtkTextLineSegment *seg;
3809   int offset;
3810
3811   g_return_val_if_fail (line != NULL, NULL);
3812
3813   offset = byte_offset;
3814   seg = line->segments;
3815
3816   while (offset > 0 && offset >= seg->byte_count)
3817     {
3818       g_assert (seg != NULL); /* means an invalid byte index */
3819       offset -= seg->byte_count;
3820       seg = seg->next;
3821     }
3822
3823   if (seg_offset)
3824     *seg_offset = offset;
3825
3826   return seg;
3827 }
3828
3829 GtkTextLineSegment*
3830 _gtk_text_line_char_to_any_segment (GtkTextLine *line,
3831                                    gint char_offset,
3832                                    gint *seg_offset)
3833 {
3834   GtkTextLineSegment *seg;
3835   int offset;
3836
3837   g_return_val_if_fail (line != NULL, NULL);
3838
3839   offset = char_offset;
3840   seg = line->segments;
3841
3842   while (offset > 0 && offset >= seg->char_count)
3843     {
3844       g_assert (seg != NULL); /* means an invalid byte index */
3845       offset -= seg->char_count;
3846       seg = seg->next;
3847     }
3848
3849   if (seg_offset)
3850     *seg_offset = offset;
3851
3852   return seg;
3853 }
3854
3855 gint
3856 _gtk_text_line_byte_to_char (GtkTextLine *line,
3857                             gint byte_offset)
3858 {
3859   gint char_offset;
3860   GtkTextLineSegment *seg;
3861
3862   g_return_val_if_fail (line != NULL, 0);
3863   g_return_val_if_fail (byte_offset >= 0, 0);
3864
3865   char_offset = 0;
3866   seg = line->segments;
3867   while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3868                                             the next segment) */
3869     {
3870       g_assert (seg != NULL); /* our byte_index was bogus if this happens */
3871
3872       byte_offset -= seg->byte_count;
3873       char_offset += seg->char_count;
3874
3875       seg = seg->next;
3876     }
3877
3878   g_assert (seg != NULL);
3879
3880   /* Now byte_offset is the offset into the current segment,
3881      and char_offset is the start of the current segment.
3882      Optimize the case where no chars use > 1 byte */
3883   if (seg->byte_count == seg->char_count)
3884     return char_offset + byte_offset;
3885   else
3886     {
3887       if (seg->type == &gtk_text_char_type)
3888         return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3889       else
3890         {
3891           g_assert (seg->char_count == 1);
3892           g_assert (byte_offset == 0);
3893
3894           return char_offset;
3895         }
3896     }
3897 }
3898
3899 gint
3900 _gtk_text_line_char_to_byte (GtkTextLine *line,
3901                             gint         char_offset)
3902 {
3903   g_warning ("FIXME not implemented");
3904
3905   return 0;
3906 }
3907
3908 /* FIXME sync with char_locate (or figure out a clean
3909    way to merge the two functions) */
3910 gboolean
3911 _gtk_text_line_byte_locate (GtkTextLine *line,
3912                             gint byte_offset,
3913                             GtkTextLineSegment **segment,
3914                             GtkTextLineSegment **any_segment,
3915                             gint *seg_byte_offset,
3916                             gint *line_byte_offset)
3917 {
3918   GtkTextLineSegment *seg;
3919   GtkTextLineSegment *after_prev_indexable;
3920   GtkTextLineSegment *after_last_indexable;
3921   GtkTextLineSegment *last_indexable;
3922   gint offset;
3923   gint bytes_in_line;
3924
3925   g_return_val_if_fail (line != NULL, FALSE);
3926   g_return_val_if_fail (byte_offset >= 0, FALSE);
3927
3928   *segment = NULL;
3929   *any_segment = NULL;
3930   bytes_in_line = 0;
3931
3932   offset = byte_offset;
3933
3934   last_indexable = NULL;
3935   after_last_indexable = line->segments;
3936   after_prev_indexable = line->segments;
3937   seg = line->segments;
3938
3939   /* The loop ends when we're inside a segment;
3940      last_indexable refers to the last segment
3941      we passed entirely. */
3942   while (seg && offset >= seg->byte_count)
3943     {
3944       if (seg->char_count > 0)
3945         {
3946           offset -= seg->byte_count;
3947           bytes_in_line += seg->byte_count;
3948           last_indexable = seg;
3949           after_prev_indexable = after_last_indexable;
3950           after_last_indexable = last_indexable->next;
3951         }
3952
3953       seg = seg->next;
3954     }
3955
3956   if (seg == NULL)
3957     {
3958       /* We went off the end of the line */
3959       if (offset != 0)
3960         g_warning ("%s: byte index off the end of the line", G_STRLOC);
3961
3962       return FALSE;
3963     }
3964   else
3965     {
3966       *segment = seg;
3967       if (after_last_indexable != NULL)
3968         *any_segment = after_last_indexable;
3969       else
3970         *any_segment = *segment;
3971     }
3972
3973   /* Override any_segment if we're in the middle of a segment. */
3974   if (offset > 0)
3975     *any_segment = *segment;
3976
3977   *seg_byte_offset = offset;
3978
3979   g_assert (*segment != NULL);
3980   g_assert (*any_segment != NULL);
3981   g_assert (*seg_byte_offset < (*segment)->byte_count);
3982
3983   *line_byte_offset = bytes_in_line + *seg_byte_offset;
3984
3985   return TRUE;
3986 }
3987
3988 /* FIXME sync with byte_locate (or figure out a clean
3989    way to merge the two functions) */
3990 gboolean
3991 _gtk_text_line_char_locate     (GtkTextLine     *line,
3992                                 gint              char_offset,
3993                                 GtkTextLineSegment **segment,
3994                                 GtkTextLineSegment **any_segment,
3995                                 gint             *seg_char_offset,
3996                                 gint             *line_char_offset)
3997 {
3998   GtkTextLineSegment *seg;
3999   GtkTextLineSegment *after_prev_indexable;
4000   GtkTextLineSegment *after_last_indexable;
4001   GtkTextLineSegment *last_indexable;
4002   gint offset;
4003   gint chars_in_line;
4004
4005   g_return_val_if_fail (line != NULL, FALSE);
4006   g_return_val_if_fail (char_offset >= 0, FALSE);
4007
4008   *segment = NULL;
4009   *any_segment = NULL;
4010   chars_in_line = 0;
4011
4012   offset = char_offset;
4013
4014   last_indexable = NULL;
4015   after_last_indexable = line->segments;
4016   after_prev_indexable = line->segments;
4017   seg = line->segments;
4018
4019   /* The loop ends when we're inside a segment;
4020      last_indexable refers to the last segment
4021      we passed entirely. */
4022   while (seg && offset >= seg->char_count)
4023     {
4024       if (seg->char_count > 0)
4025         {
4026           offset -= seg->char_count;
4027           chars_in_line += seg->char_count;
4028           last_indexable = seg;
4029           after_prev_indexable = after_last_indexable;
4030           after_last_indexable = last_indexable->next;
4031         }
4032
4033       seg = seg->next;
4034     }
4035
4036   if (seg == NULL)
4037     {
4038       /* end of the line */
4039       if (offset != 0)
4040         g_warning ("%s: char offset off the end of the line", G_STRLOC);
4041
4042       return FALSE;
4043     }
4044   else
4045     {
4046       *segment = seg;
4047       if (after_last_indexable != NULL)
4048         *any_segment = after_last_indexable;
4049       else
4050         *any_segment = *segment;
4051     }
4052
4053   /* Override any_segment if we're in the middle of a segment. */
4054   if (offset > 0)
4055     *any_segment = *segment;
4056
4057   *seg_char_offset = offset;
4058
4059   g_assert (*segment != NULL);
4060   g_assert (*any_segment != NULL);
4061   g_assert (*seg_char_offset < (*segment)->char_count);
4062
4063   *line_char_offset = chars_in_line + *seg_char_offset;
4064
4065   return TRUE;
4066 }
4067
4068 void
4069 _gtk_text_line_byte_to_char_offsets (GtkTextLine *line,
4070                                     gint byte_offset,
4071                                     gint *line_char_offset,
4072                                     gint *seg_char_offset)
4073 {
4074   GtkTextLineSegment *seg;
4075   int offset;
4076
4077   g_return_if_fail (line != NULL);
4078   g_return_if_fail (byte_offset >= 0);
4079
4080   *line_char_offset = 0;
4081
4082   offset = byte_offset;
4083   seg = line->segments;
4084
4085   while (offset >= seg->byte_count)
4086     {
4087       offset -= seg->byte_count;
4088       *line_char_offset += seg->char_count;
4089       seg = seg->next;
4090       g_assert (seg != NULL); /* means an invalid char offset */
4091     }
4092
4093   g_assert (seg->char_count > 0); /* indexable. */
4094
4095   /* offset is now the number of bytes into the current segment we
4096    * want to go. Count chars into the current segment.
4097    */
4098
4099   if (seg->type == &gtk_text_char_type)
4100     {
4101       *seg_char_offset = g_utf8_strlen (seg->body.chars, offset);
4102
4103       g_assert (*seg_char_offset < seg->char_count);
4104
4105       *line_char_offset += *seg_char_offset;
4106     }
4107   else
4108     {
4109       g_assert (offset == 0);
4110       *seg_char_offset = 0;
4111     }
4112 }
4113
4114 void
4115 _gtk_text_line_char_to_byte_offsets (GtkTextLine *line,
4116                                     gint char_offset,
4117                                     gint *line_byte_offset,
4118                                     gint *seg_byte_offset)
4119 {
4120   GtkTextLineSegment *seg;
4121   int offset;
4122
4123   g_return_if_fail (line != NULL);
4124   g_return_if_fail (char_offset >= 0);
4125
4126   *line_byte_offset = 0;
4127
4128   offset = char_offset;
4129   seg = line->segments;
4130
4131   while (offset >= seg->char_count)
4132     {
4133       offset -= seg->char_count;
4134       *line_byte_offset += seg->byte_count;
4135       seg = seg->next;
4136       g_assert (seg != NULL); /* means an invalid char offset */
4137     }
4138
4139   g_assert (seg->char_count > 0); /* indexable. */
4140
4141   /* offset is now the number of chars into the current segment we
4142      want to go. Count bytes into the current segment. */
4143
4144   if (seg->type == &gtk_text_char_type)
4145     {
4146       *seg_byte_offset = 0;
4147       while (offset > 0)
4148         {
4149           gint bytes;
4150           const char * start = seg->body.chars + *seg_byte_offset;
4151
4152           bytes = g_utf8_next_char (start) - start;
4153           *seg_byte_offset += bytes;
4154           offset -= 1;
4155         }
4156
4157       g_assert (*seg_byte_offset < seg->byte_count);
4158
4159       *line_byte_offset += *seg_byte_offset;
4160     }
4161   else
4162     {
4163       g_assert (offset == 0);
4164       *seg_byte_offset = 0;
4165     }
4166 }
4167
4168 static gint
4169 node_compare (GtkTextBTreeNode *lhs,
4170               GtkTextBTreeNode *rhs)
4171 {
4172   GtkTextBTreeNode *iter;
4173   GtkTextBTreeNode *node;
4174   GtkTextBTreeNode *common_parent;
4175   GtkTextBTreeNode *parent_of_lower;
4176   GtkTextBTreeNode *parent_of_higher;
4177   gboolean lhs_is_lower;
4178   GtkTextBTreeNode *lower;
4179   GtkTextBTreeNode *higher;
4180
4181   /* This function assumes that lhs and rhs are not underneath each
4182    * other.
4183    */
4184
4185   if (lhs == rhs)
4186     return 0;
4187
4188   if (lhs->level < rhs->level)
4189     {
4190       lhs_is_lower = TRUE;
4191       lower = lhs;
4192       higher = rhs;
4193     }
4194   else
4195     {
4196       lhs_is_lower = FALSE;
4197       lower = rhs;
4198       higher = lhs;
4199     }
4200
4201   /* Algorithm: find common parent of lhs/rhs. Save the child nodes
4202    * of the common parent we used to reach the common parent; the
4203    * ordering of these child nodes in the child list is the ordering
4204    * of lhs and rhs.
4205    */
4206
4207   /* Get on the same level (may be on same level already) */
4208   node = lower;
4209   while (node->level < higher->level)
4210     node = node->parent;
4211
4212   g_assert (node->level == higher->level);
4213
4214   g_assert (node != higher); /* Happens if lower is underneath higher */
4215
4216   /* Go up until we have two children with a common parent.
4217    */
4218   parent_of_lower = node;
4219   parent_of_higher = higher;
4220
4221   while (parent_of_lower->parent != parent_of_higher->parent)
4222     {
4223       parent_of_lower = parent_of_lower->parent;
4224       parent_of_higher = parent_of_higher->parent;
4225     }
4226
4227   g_assert (parent_of_lower->parent == parent_of_higher->parent);
4228
4229   common_parent = parent_of_lower->parent;
4230
4231   g_assert (common_parent != NULL);
4232
4233   /* See which is first in the list of common_parent's children */
4234   iter = common_parent->children.node;
4235   while (iter != NULL)
4236     {
4237       if (iter == parent_of_higher)
4238         {
4239           /* higher is less than lower */
4240
4241           if (lhs_is_lower)
4242             return 1; /* lhs > rhs */
4243           else
4244             return -1;
4245         }
4246       else if (iter == parent_of_lower)
4247         {
4248           /* lower is less than higher */
4249
4250           if (lhs_is_lower)
4251             return -1; /* lhs < rhs */
4252           else
4253             return 1;
4254         }
4255
4256       iter = iter->next;
4257     }
4258
4259   g_assert_not_reached ();
4260   return 0;
4261 }
4262
4263 /* remember that tag == NULL means "any tag" */
4264 GtkTextLine*
4265 _gtk_text_line_next_could_contain_tag (GtkTextLine  *line,
4266                                        GtkTextBTree *tree,
4267                                        GtkTextTag   *tag)
4268 {
4269   GtkTextBTreeNode *node;
4270   GtkTextTagInfo *info;
4271   gboolean below_tag_root;
4272
4273   g_return_val_if_fail (line != NULL, NULL);
4274
4275   if (gtk_debug_flags & GTK_DEBUG_TEXT)
4276     _gtk_text_btree_check (tree);
4277
4278   if (tag == NULL)
4279     {
4280       /* Right now we can only offer linear-search if the user wants
4281        * to know about any tag toggle at all.
4282        */
4283       return _gtk_text_line_next_excluding_last (line);
4284     }
4285
4286   /* Our tag summaries only have node precision, not line
4287    * precision. This means that if any line under a node could contain a
4288    * tag, then any of the others could also contain a tag.
4289    *
4290    * In the future we could have some mechanism to keep track of how
4291    * many toggles we've found under a node so far, since we have a
4292    * count of toggles under the node. But for now I'm going with KISS.
4293    */
4294
4295   /* return same-node line, if any. */
4296   if (line->next)
4297     return line->next;
4298
4299   info = gtk_text_btree_get_existing_tag_info (tree, tag);
4300   if (info == NULL)
4301     return NULL;
4302
4303   if (info->tag_root == NULL)
4304     return NULL;
4305
4306   if (info->tag_root == line->parent)
4307     return NULL; /* we were at the last line under the tag root */
4308
4309   /* We need to go up out of this node, and on to the next one with
4310      toggles for the target tag. If we're below the tag root, we need to
4311      find the next node below the tag root that has tag summaries. If
4312      we're not below the tag root, we need to see if the tag root is
4313      after us in the tree, and if so, return the first line underneath
4314      the tag root. */
4315
4316   node = line->parent;
4317   below_tag_root = FALSE;
4318   while (node != NULL)
4319     {
4320       if (node == info->tag_root)
4321         {
4322           below_tag_root = TRUE;
4323           break;
4324         }
4325
4326       node = node->parent;
4327     }
4328
4329   if (below_tag_root)
4330     {
4331       node = line->parent;
4332       while (node != info->tag_root)
4333         {
4334           if (node->next == NULL)
4335             node = node->parent;
4336           else
4337             {
4338               node = node->next;
4339
4340               if (gtk_text_btree_node_has_tag (node, tag))
4341                 goto found;
4342             }
4343         }
4344       return NULL;
4345     }
4346   else
4347     {
4348       gint ordering;
4349
4350       ordering = node_compare (line->parent, info->tag_root);
4351
4352       if (ordering < 0)
4353         {
4354           /* Tag root is ahead of us, so search there. */
4355           node = info->tag_root;
4356           goto found;
4357         }
4358       else
4359         {
4360           /* Tag root is after us, so no more lines that
4361            * could contain the tag.
4362            */
4363           return NULL;
4364         }
4365
4366       g_assert_not_reached ();
4367     }
4368
4369  found:
4370
4371   g_assert (node != NULL);
4372
4373   /* We have to find the first sub-node of this node that contains
4374    * the target tag.
4375    */
4376
4377   while (node->level > 0)
4378     {
4379       g_assert (node != NULL); /* If this fails, it likely means an
4380                                   incorrect tag summary led us on a
4381                                   wild goose chase down this branch of
4382                                   the tree. */
4383       node = node->children.node;
4384       while (node != NULL)
4385         {
4386           if (gtk_text_btree_node_has_tag (node, tag))
4387             break;
4388           node = node->next;
4389         }
4390     }
4391
4392   g_assert (node != NULL);
4393   g_assert (node->level == 0);
4394
4395   return node->children.line;
4396 }
4397
4398 static GtkTextLine*
4399 prev_line_under_node (GtkTextBTreeNode *node,
4400                       GtkTextLine      *line)
4401 {
4402   GtkTextLine *prev;
4403
4404   prev = node->children.line;
4405
4406   g_assert (prev);
4407
4408   if (prev != line)
4409     {
4410       while (prev->next != line)
4411         prev = prev->next;
4412
4413       return prev;
4414     }
4415
4416   return NULL;
4417 }
4418
4419 GtkTextLine*
4420 _gtk_text_line_previous_could_contain_tag (GtkTextLine  *line,
4421                                           GtkTextBTree *tree,
4422                                           GtkTextTag   *tag)
4423 {
4424   GtkTextBTreeNode *node;
4425   GtkTextBTreeNode *found_node = NULL;
4426   GtkTextTagInfo *info;
4427   gboolean below_tag_root;
4428   GtkTextLine *prev;
4429   GtkTextBTreeNode *line_ancestor;
4430   GtkTextBTreeNode *line_ancestor_parent;
4431
4432   /* See next_could_contain_tag () for more extensive comments
4433    * on what's going on here.
4434    */
4435
4436   g_return_val_if_fail (line != NULL, NULL);
4437
4438   if (gtk_debug_flags & GTK_DEBUG_TEXT)
4439     _gtk_text_btree_check (tree);
4440
4441   if (tag == NULL)
4442     {
4443       /* Right now we can only offer linear-search if the user wants
4444        * to know about any tag toggle at all.
4445        */
4446       return _gtk_text_line_previous (line);
4447     }
4448
4449   /* Return same-node line, if any. */
4450   prev = prev_line_under_node (line->parent, line);
4451   if (prev)
4452     return prev;
4453
4454   info = gtk_text_btree_get_existing_tag_info (tree, tag);
4455   if (info == NULL)
4456     return NULL;
4457
4458   if (info->tag_root == NULL)
4459     return NULL;
4460
4461   if (info->tag_root == line->parent)
4462     return NULL; /* we were at the first line under the tag root */
4463
4464   /* Are we below the tag root */
4465   node = line->parent;
4466   below_tag_root = FALSE;
4467   while (node != NULL)
4468     {
4469       if (node == info->tag_root)
4470         {
4471           below_tag_root = TRUE;
4472           break;
4473         }
4474
4475       node = node->parent;
4476     }
4477
4478   if (below_tag_root)
4479     {
4480       /* Look for a previous node under this tag root that has our
4481        * tag.
4482        */
4483
4484       /* this assertion holds because line->parent is not the
4485        * tag root, we are below the tag root, and the tag
4486        * root exists.
4487        */
4488       g_assert (line->parent->parent != NULL);
4489
4490       line_ancestor = line->parent;
4491       line_ancestor_parent = line->parent->parent;
4492
4493       while (line_ancestor != info->tag_root)
4494         {
4495           GSList *child_nodes = NULL;
4496           GSList *tmp;
4497
4498           /* Create reverse-order list of nodes before
4499            * line_ancestor
4500            */
4501           if (line_ancestor_parent != NULL)
4502             node = line_ancestor_parent->children.node;
4503           else
4504             node = line_ancestor;
4505
4506           while (node != line_ancestor && node != NULL)
4507             {
4508               child_nodes = g_slist_prepend (child_nodes, node);
4509
4510               node = node->next;
4511             }
4512
4513           /* Try to find a node with our tag on it in the list */
4514           tmp = child_nodes;
4515           while (tmp != NULL)
4516             {
4517               GtkTextBTreeNode *this_node = tmp->data;
4518
4519               g_assert (this_node != line_ancestor);
4520
4521               if (gtk_text_btree_node_has_tag (this_node, tag))
4522                 {
4523                   found_node = this_node;
4524                   g_slist_free (child_nodes);
4525                   goto found;
4526                 }
4527
4528               tmp = g_slist_next (tmp);
4529             }
4530
4531           g_slist_free (child_nodes);
4532
4533           /* Didn't find anything on this level; go up one level. */
4534           line_ancestor = line_ancestor_parent;
4535           line_ancestor_parent = line_ancestor->parent;
4536         }
4537
4538       /* No dice. */
4539       return NULL;
4540     }
4541   else
4542     {
4543       gint ordering;
4544
4545       ordering = node_compare (line->parent, info->tag_root);
4546
4547       if (ordering < 0)
4548         {
4549           /* Tag root is ahead of us, so no more lines
4550            * with this tag.
4551            */
4552           return NULL;
4553         }
4554       else
4555         {
4556           /* Tag root is after us, so grab last tagged
4557            * line underneath the tag root.
4558            */
4559           found_node = info->tag_root;
4560           goto found;
4561         }
4562
4563       g_assert_not_reached ();
4564     }
4565
4566  found:
4567
4568   g_assert (found_node != NULL);
4569
4570   /* We have to find the last sub-node of this node that contains
4571    * the target tag.
4572    */
4573   node = found_node;
4574
4575   while (node->level > 0)
4576     {
4577       GSList *child_nodes = NULL;
4578       GSList *iter;
4579       g_assert (node != NULL); /* If this fails, it likely means an
4580                                   incorrect tag summary led us on a
4581                                   wild goose chase down this branch of
4582                                   the tree. */
4583
4584       node = node->children.node;
4585       while (node != NULL)
4586         {
4587           child_nodes = g_slist_prepend (child_nodes, node);
4588           node = node->next;
4589         }
4590
4591       node = NULL; /* detect failure to find a child node. */
4592
4593       iter = child_nodes;
4594       while (iter != NULL)
4595         {
4596           if (gtk_text_btree_node_has_tag (iter->data, tag))
4597             {
4598               /* recurse into this node. */
4599               node = iter->data;
4600               break;
4601             }
4602
4603           iter = g_slist_next (iter);
4604         }
4605
4606       g_slist_free (child_nodes);
4607
4608       g_assert (node != NULL);
4609     }
4610
4611   g_assert (node != NULL);
4612   g_assert (node->level == 0);
4613
4614   /* this assertion is correct, but slow. */
4615   /* g_assert (node_compare (node, line->parent) < 0); */
4616
4617   /* Return last line in this node. */
4618
4619   prev = node->children.line;
4620   while (prev->next)
4621     prev = prev->next;
4622
4623   return prev;
4624 }
4625
4626 /*
4627  * Non-public function implementations
4628  */
4629
4630 static void
4631 summary_list_destroy (Summary *summary)
4632 {
4633   Summary *next;
4634   while (summary != NULL)
4635     {
4636       next = summary->next;
4637       summary_destroy (summary);
4638       summary = next;
4639     }
4640 }
4641
4642 static GtkTextLine*
4643 get_last_line (GtkTextBTree *tree)
4644 {
4645   if (tree->last_line_stamp != tree->chars_changed_stamp)
4646     {
4647       gint n_lines;
4648       GtkTextLine *line;
4649       gint real_line;
4650
4651       n_lines = _gtk_text_btree_line_count (tree);
4652
4653       g_assert (n_lines >= 1); /* num_lines doesn't return bogus last line. */
4654
4655       line = _gtk_text_btree_get_line (tree, n_lines, &real_line);
4656
4657       tree->last_line_stamp = tree->chars_changed_stamp;
4658       tree->last_line = line;
4659     }
4660
4661   return tree->last_line;
4662 }
4663
4664 /*
4665  * Lines
4666  */
4667
4668 static GtkTextLine*
4669 gtk_text_line_new (void)
4670 {
4671   GtkTextLine *line;
4672
4673   line = g_new0(GtkTextLine, 1);
4674   line->dir_strong = PANGO_DIRECTION_NEUTRAL;
4675   line->dir_propagated_forward = PANGO_DIRECTION_NEUTRAL;
4676   line->dir_propagated_back = PANGO_DIRECTION_NEUTRAL;
4677
4678   return line;
4679 }
4680
4681 static void
4682 gtk_text_line_destroy (GtkTextBTree *tree, GtkTextLine *line)
4683 {
4684   GtkTextLineData *ld;
4685   GtkTextLineData *next;
4686
4687   g_return_if_fail (line != NULL);
4688
4689   ld = line->views;
4690   while (ld != NULL)
4691     {
4692       BTreeView *view;
4693
4694       view = gtk_text_btree_get_view (tree, ld->view_id);
4695
4696       g_assert (view != NULL);
4697
4698       next = ld->next;
4699       gtk_text_layout_free_line_data (view->layout, line, ld);
4700
4701       ld = next;
4702     }
4703
4704   g_free (line);
4705 }
4706
4707 static void
4708 gtk_text_line_set_parent (GtkTextLine *line,
4709                           GtkTextBTreeNode *node)
4710 {
4711   if (line->parent == node)
4712     return;
4713   line->parent = node;
4714   gtk_text_btree_node_invalidate_upward (node, NULL);
4715 }
4716
4717 static void
4718 cleanup_line (GtkTextLine *line)
4719 {
4720   GtkTextLineSegment *seg, **prev_p;
4721   gboolean changed;
4722
4723   /*
4724    * Make a pass over all of the segments in the line, giving each
4725    * a chance to clean itself up.  This could potentially change
4726    * the structure of the line, e.g. by merging two segments
4727    * together or having two segments cancel themselves;  if so,
4728    * then repeat the whole process again, since the first structure
4729    * change might make other structure changes possible.  Repeat
4730    * until eventually there are no changes.
4731    */
4732
4733   changed = TRUE;
4734   while (changed)
4735     {
4736       changed = FALSE;
4737       for (prev_p = &line->segments, seg = *prev_p;
4738            seg != NULL;
4739            prev_p = &(*prev_p)->next, seg = *prev_p)
4740         {
4741           if (seg->type->cleanupFunc != NULL)
4742             {
4743               *prev_p = (*seg->type->cleanupFunc)(seg, line);
4744               if (seg != *prev_p)
4745                 changed = TRUE;
4746             }
4747         }
4748     }
4749 }
4750
4751 /*
4752  * Nodes
4753  */
4754
4755 static NodeData*
4756 node_data_new (gpointer view_id)
4757 {
4758   NodeData *nd;
4759
4760   nd = g_new (NodeData, 1);
4761
4762   nd->view_id = view_id;
4763   nd->next = NULL;
4764   nd->width = 0;
4765   nd->height = 0;
4766   nd->valid = FALSE;
4767
4768   return nd;
4769 }
4770
4771 static void
4772 node_data_destroy (NodeData *nd)
4773 {
4774   g_free (nd);
4775 }
4776
4777 static void
4778 node_data_list_destroy (NodeData *nd)
4779 {
4780   NodeData *iter;
4781   NodeData *next;
4782
4783   iter = nd;
4784   while (iter != NULL)
4785     {
4786       next = iter->next;
4787       node_data_destroy (iter);
4788       iter = next;
4789     }
4790 }
4791
4792 static NodeData*
4793 node_data_find (NodeData *nd, gpointer view_id)
4794 {
4795   while (nd != NULL)
4796     {
4797       if (nd->view_id == view_id)
4798         break;
4799       nd = nd->next;
4800     }
4801   return nd;
4802 }
4803
4804 static void
4805 summary_destroy (Summary *summary)
4806 {
4807   /* Fill with error-triggering garbage */
4808   summary->info = (void*)0x1;
4809   summary->toggle_count = 567;
4810   summary->next = (void*)0x1;
4811   g_free (summary);
4812 }
4813
4814 static GtkTextBTreeNode*
4815 gtk_text_btree_node_new (void)
4816 {
4817   GtkTextBTreeNode *node;
4818
4819   node = g_new (GtkTextBTreeNode, 1);
4820
4821   node->node_data = NULL;
4822
4823   return node;
4824 }
4825
4826 static void
4827 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode  *node,
4828                                          GtkTextTagInfo  *info,
4829                                          gint adjust)
4830 {
4831   Summary *summary;
4832
4833   summary = node->summary;
4834   while (summary != NULL)
4835     {
4836       if (summary->info == info)
4837         {
4838           summary->toggle_count += adjust;
4839           break;
4840         }
4841
4842       summary = summary->next;
4843     }
4844
4845   if (summary == NULL)
4846     {
4847       /* didn't find a summary for our tag. */
4848       g_return_if_fail (adjust > 0);
4849       summary = g_new (Summary, 1);
4850       summary->info = info;
4851       summary->toggle_count = adjust;
4852       summary->next = node->summary;
4853       node->summary = summary;
4854     }
4855 }
4856
4857 /* Note that the tag root and above do not have summaries
4858    for the tag; only nodes below the tag root have
4859    the summaries. */
4860 static gboolean
4861 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4862 {
4863   Summary *summary;
4864
4865   summary = node->summary;
4866   while (summary != NULL)
4867     {
4868       if (tag == NULL ||
4869           summary->info->tag == tag)
4870         return TRUE;
4871
4872       summary = summary->next;
4873     }
4874
4875   return FALSE;
4876 }
4877
4878 /* Add node and all children to the damage region. */
4879 static void
4880 gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node)
4881 {
4882   NodeData *nd;
4883
4884   nd = node->node_data;
4885   while (nd != NULL)
4886     {
4887       nd->valid = FALSE;
4888       nd = nd->next;
4889     }
4890
4891   if (node->level == 0)
4892     {
4893       GtkTextLine *line;
4894
4895       line = node->children.line;
4896       while (line != NULL)
4897         {
4898           GtkTextLineData *ld;
4899
4900           ld = line->views;
4901           while (ld != NULL)
4902             {
4903               ld->valid = FALSE;
4904               ld = ld->next;
4905             }
4906
4907           line = line->next;
4908         }
4909     }
4910   else
4911     {
4912       GtkTextBTreeNode *child;
4913
4914       child = node->children.node;
4915
4916       while (child != NULL)
4917         {
4918           gtk_text_btree_node_invalidate_downward (child);
4919
4920           child = child->next;
4921         }
4922     }
4923 }
4924
4925 static void
4926 gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node, gpointer view_id)
4927 {
4928   GtkTextBTreeNode *iter;
4929
4930   iter = node;
4931   while (iter != NULL)
4932     {
4933       NodeData *nd;
4934
4935       if (view_id)
4936         {
4937           nd = node_data_find (iter->node_data, view_id);
4938
4939           if (nd == NULL || !nd->valid)
4940             break; /* Once a node is invalid, we know its parents are as well. */
4941
4942           nd->valid = FALSE;
4943         }
4944       else
4945         {
4946           gboolean should_continue = FALSE;
4947
4948           nd = iter->node_data;
4949           while (nd != NULL)
4950             {
4951               if (nd->valid)
4952                 {
4953                   should_continue = TRUE;
4954                   nd->valid = FALSE;
4955                 }
4956
4957               nd = nd->next;
4958             }
4959
4960           if (!should_continue)
4961             break; /* This node was totally invalidated, so are its
4962                       parents */
4963         }
4964
4965       iter = iter->parent;
4966     }
4967 }
4968
4969
4970 /**
4971  * _gtk_text_btree_is_valid:
4972  * @tree: a #GtkTextBTree
4973  * @view_id: ID for the view
4974  *
4975  * Check to see if the entire #GtkTextBTree is valid or not for
4976  * the given view.
4977  *
4978  * Return value: %TRUE if the entire #GtkTextBTree is valid
4979  **/
4980 gboolean
4981 _gtk_text_btree_is_valid (GtkTextBTree *tree,
4982                          gpointer      view_id)
4983 {
4984   NodeData *nd;
4985   g_return_val_if_fail (tree != NULL, FALSE);
4986
4987   nd = node_data_find (tree->root_node->node_data, view_id);
4988   return (nd && nd->valid);
4989 }
4990
4991 typedef struct _ValidateState ValidateState;
4992
4993 struct _ValidateState
4994 {
4995   gint remaining_pixels;
4996   gboolean in_validation;
4997   gint y;
4998   gint old_height;
4999   gint new_height;
5000 };
5001
5002 static void
5003 gtk_text_btree_node_validate (BTreeView         *view,
5004                               GtkTextBTreeNode  *node,
5005                               gpointer           view_id,
5006                               ValidateState     *state)
5007 {
5008   gint node_valid = TRUE;
5009   gint node_width = 0;
5010   gint node_height = 0;
5011
5012   NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5013   g_return_if_fail (!nd->valid);
5014
5015   if (node->level == 0)
5016     {
5017       GtkTextLine *line = node->children.line;
5018       GtkTextLineData *ld;
5019
5020       /* Iterate over leading valid lines */
5021       while (line != NULL)
5022         {
5023           ld = _gtk_text_line_get_data (line, view_id);
5024
5025           if (!ld || !ld->valid)
5026             break;
5027           else if (state->in_validation)
5028             {
5029               state->in_validation = FALSE;
5030               return;
5031             }
5032           else
5033             {
5034               state->y += ld->height;
5035               node_width = MAX (ld->width, node_width);
5036               node_height += ld->height;
5037             }
5038
5039           line = line->next;
5040         }
5041
5042       state->in_validation = TRUE;
5043
5044       /* Iterate over invalid lines */
5045       while (line != NULL)
5046         {
5047           ld = _gtk_text_line_get_data (line, view_id);
5048
5049           if (ld && ld->valid)
5050             break;
5051           else
5052             {
5053               if (ld)
5054                 state->old_height += ld->height;
5055               ld = gtk_text_layout_wrap (view->layout, line, ld);
5056               state->new_height += ld->height;
5057
5058               node_width = MAX (ld->width, node_width);
5059               node_height += ld->height;
5060
5061               state->remaining_pixels -= ld->height;
5062               if (state->remaining_pixels <= 0)
5063                 {
5064                   line = line->next;
5065                   break;
5066                 }
5067             }
5068
5069           line = line->next;
5070         }
5071
5072       /* Iterate over the remaining lines */
5073       while (line != NULL)
5074         {
5075           ld = _gtk_text_line_get_data (line, view_id);
5076           state->in_validation = FALSE;
5077
5078           if (!ld || !ld->valid)
5079             node_valid = FALSE;
5080
5081           if (ld)
5082             {
5083               node_width = MAX (ld->width, node_width);
5084               node_height += ld->height;
5085             }
5086
5087           line = line->next;
5088         }
5089     }
5090   else
5091     {
5092       GtkTextBTreeNode *child;
5093       NodeData *child_nd;
5094
5095       child = node->children.node;
5096
5097       /* Iterate over leading valid nodes */
5098       while (child)
5099         {
5100           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5101
5102           if (!child_nd->valid)
5103             break;
5104           else if (state->in_validation)
5105             {
5106               state->in_validation = FALSE;
5107               return;
5108             }
5109           else
5110             {
5111               state->y += child_nd->height;
5112               node_width = MAX (node_width, child_nd->width);
5113               node_height += child_nd->height;
5114             }
5115
5116           child = child->next;
5117         }
5118
5119       /* Iterate over invalid nodes */
5120       while (child)
5121         {
5122           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5123
5124           if (child_nd->valid)
5125             break;
5126           else
5127             {
5128               gtk_text_btree_node_validate (view, child, view_id, state);
5129
5130               if (!child_nd->valid)
5131                 node_valid = FALSE;
5132               node_width = MAX (node_width, child_nd->width);
5133               node_height += child_nd->height;
5134
5135               if (!state->in_validation || state->remaining_pixels <= 0)
5136                 {
5137                   child = child->next;
5138                   break;
5139                 }
5140             }
5141
5142           child = child->next;
5143         }
5144
5145       /* Iterate over the remaining lines */
5146       while (child)
5147         {
5148           child_nd = gtk_text_btree_node_ensure_data (child, view_id);
5149           state->in_validation = FALSE;
5150
5151           if (!child_nd->valid)
5152             node_valid = FALSE;
5153
5154           node_width = MAX (child_nd->width, node_width);
5155           node_height += child_nd->height;
5156
5157           child = child->next;
5158         }
5159     }
5160
5161   nd->width = node_width;
5162   nd->height = node_height;
5163   nd->valid = node_valid;
5164 }
5165
5166 /**
5167  * _gtk_text_btree_validate:
5168  * @tree: a #GtkTextBTree
5169  * @view_id: view id
5170  * @max_pixels: the maximum number of pixels to validate. (No more
5171  *              than one paragraph beyond this limit will be validated)
5172  * @y: location to store starting y coordinate of validated region
5173  * @old_height: location to store old height of validated region
5174  * @new_height: location to store new height of validated region
5175  *
5176  * Validate a single contiguous invalid region of a #GtkTextBTree for
5177  * a given view.
5178  *
5179  * Return value: %TRUE if a region has been validated, %FALSE if the
5180  * entire tree was already valid.
5181  **/
5182 gboolean
5183 _gtk_text_btree_validate (GtkTextBTree *tree,
5184                          gpointer      view_id,
5185                          gint          max_pixels,
5186                          gint         *y,
5187                          gint         *old_height,
5188                          gint         *new_height)
5189 {
5190   BTreeView *view;
5191
5192   g_return_val_if_fail (tree != NULL, FALSE);
5193
5194   view = gtk_text_btree_get_view (tree, view_id);
5195   g_return_val_if_fail (view != NULL, FALSE);
5196
5197   if (!_gtk_text_btree_is_valid (tree, view_id))
5198     {
5199       ValidateState state;
5200
5201       state.remaining_pixels = max_pixels;
5202       state.in_validation = FALSE;
5203       state.y = 0;
5204       state.old_height = 0;
5205       state.new_height = 0;
5206
5207       gtk_text_btree_node_validate (view,
5208                                     tree->root_node,
5209                                     view_id, &state);
5210
5211       if (y)
5212         *y = state.y;
5213       if (old_height)
5214         *old_height = state.old_height;
5215       if (new_height)
5216         *new_height = state.new_height;
5217
5218       if (gtk_debug_flags & GTK_DEBUG_TEXT)
5219         _gtk_text_btree_check (tree);
5220
5221       return TRUE;
5222     }
5223   else
5224     return FALSE;
5225 }
5226
5227 static void
5228 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
5229                                              gpointer          view_id,
5230                                              gint             *width_out,
5231                                              gint             *height_out,
5232                                              gboolean         *valid_out)
5233 {
5234   gint width = 0;
5235   gint height = 0;
5236   gboolean valid = TRUE;
5237
5238   if (node->level == 0)
5239     {
5240       GtkTextLine *line = node->children.line;
5241
5242       while (line != NULL)
5243         {
5244           GtkTextLineData *ld = _gtk_text_line_get_data (line, view_id);
5245
5246           if (!ld || !ld->valid)
5247             valid = FALSE;
5248
5249           if (ld)
5250             {
5251               width = MAX (ld->width, width);
5252               height += ld->height;
5253             }
5254
5255           line = line->next;
5256         }
5257     }
5258   else
5259     {
5260       GtkTextBTreeNode *child = node->children.node;
5261
5262       while (child)
5263         {
5264           NodeData *child_nd = node_data_find (child->node_data, view_id);
5265
5266           if (!child_nd || !child_nd->valid)
5267             valid = FALSE;
5268
5269           if (child_nd)
5270             {
5271               width = MAX (child_nd->width, width);
5272               height += child_nd->height;
5273             }
5274
5275           child = child->next;
5276         }
5277     }
5278
5279   *width_out = width;
5280   *height_out = height;
5281   *valid_out = valid;
5282 }
5283
5284
5285 /* Recompute the validity and size of the view data for a given
5286  * view at this node from the immediate children of the node
5287  */
5288 static NodeData *
5289 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
5290                                  gpointer          view_id)
5291 {
5292   NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5293   gboolean valid;
5294   gint width;
5295   gint height;
5296
5297   gtk_text_btree_node_compute_view_aggregates (node, view_id,
5298                                                &width, &height, &valid);
5299   nd->width = width;
5300   nd->height = height;
5301   nd->valid = valid;
5302
5303   return nd;
5304 }
5305
5306 static void
5307 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
5308                                         gpointer          view_id)
5309 {
5310   while (node)
5311     {
5312       gtk_text_btree_node_check_valid (node, view_id);
5313       node = node->parent;
5314     }
5315 }
5316
5317 static NodeData *
5318 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
5319                                           gpointer          view_id)
5320 {
5321   if (node->level == 0)
5322     {
5323       return gtk_text_btree_node_check_valid (node, view_id);
5324     }
5325   else
5326     {
5327       GtkTextBTreeNode *child = node->children.node;
5328
5329       NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
5330
5331       nd->valid = TRUE;
5332       nd->width = 0;
5333       nd->height = 0;
5334
5335       while (child)
5336         {
5337           NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
5338
5339           if (!child_nd->valid)
5340             nd->valid = FALSE;
5341           nd->width = MAX (child_nd->width, nd->width);
5342           nd->height += child_nd->height;
5343
5344           child = child->next;
5345         }
5346       return nd;
5347     }
5348 }
5349
5350
5351
5352 /**
5353  * _gtk_text_btree_validate_line:
5354  * @tree: a #GtkTextBTree
5355  * @line: line to validate
5356  * @view_id: view ID for the view to validate
5357  *
5358  * Revalidate a single line of the btree for the given view, propagate
5359  * results up through the entire tree.
5360  **/
5361 void
5362 _gtk_text_btree_validate_line (GtkTextBTree     *tree,
5363                                GtkTextLine      *line,
5364                                gpointer          view_id)
5365 {
5366   GtkTextLineData *ld;
5367   BTreeView *view;
5368
5369   g_return_if_fail (tree != NULL);
5370   g_return_if_fail (line != NULL);
5371
5372   view = gtk_text_btree_get_view (tree, view_id);
5373   g_return_if_fail (view != NULL);
5374
5375   ld = _gtk_text_line_get_data (line, view_id);
5376   if (!ld || !ld->valid)
5377     {
5378       ld = gtk_text_layout_wrap (view->layout, line, ld);
5379
5380       gtk_text_btree_node_check_valid_upward (line->parent, view_id);
5381     }
5382 }
5383
5384 static void
5385 gtk_text_btree_node_remove_view (BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
5386 {
5387   if (node->level == 0)
5388     {
5389       GtkTextLine *line;
5390
5391       line = node->children.line;
5392       while (line != NULL)
5393         {
5394           GtkTextLineData *ld;
5395
5396           ld = _gtk_text_line_remove_data (line, view_id);
5397
5398           if (ld)
5399             gtk_text_layout_free_line_data (view->layout, line, ld);
5400
5401           line = line->next;
5402         }
5403     }
5404   else
5405     {
5406       GtkTextBTreeNode *child;
5407
5408       child = node->children.node;
5409
5410       while (child != NULL)
5411         {
5412           /* recurse */
5413           gtk_text_btree_node_remove_view (view, child, view_id);
5414
5415           child = child->next;
5416         }
5417     }
5418
5419   gtk_text_btree_node_remove_data (node, view_id);
5420 }
5421
5422 static void
5423 gtk_text_btree_node_destroy (GtkTextBTree *tree, GtkTextBTreeNode *node)
5424 {
5425   if (node->level == 0)
5426     {
5427       GtkTextLine *line;
5428       GtkTextLineSegment *seg;
5429
5430       while (node->children.line != NULL)
5431         {
5432           line = node->children.line;
5433           node->children.line = line->next;
5434           while (line->segments != NULL)
5435             {
5436               seg = line->segments;
5437               line->segments = seg->next;
5438
5439               (*seg->type->deleteFunc) (seg, line, TRUE);
5440             }
5441           gtk_text_line_destroy (tree, line);
5442         }
5443     }
5444   else
5445     {
5446       GtkTextBTreeNode *childPtr;
5447
5448       while (node->children.node != NULL)
5449         {
5450           childPtr = node->children.node;
5451           node->children.node = childPtr->next;
5452           gtk_text_btree_node_destroy (tree, childPtr);
5453         }
5454     }
5455
5456   gtk_text_btree_node_free_empty (tree, node);
5457 }
5458
5459 static void
5460 gtk_text_btree_node_free_empty (GtkTextBTree *tree,
5461                                 GtkTextBTreeNode *node)
5462 {
5463   g_return_if_fail ((node->level > 0 && node->children.node == NULL) ||
5464                     (node->level == 0 && node->children.line == NULL));
5465
5466   summary_list_destroy (node->summary);
5467   node_data_list_destroy (node->node_data);
5468   g_free (node);
5469 }
5470
5471 static NodeData*
5472 gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node, gpointer view_id)
5473 {
5474   NodeData *nd;
5475
5476   nd = node->node_data;
5477   while (nd != NULL)
5478     {
5479       if (nd->view_id == view_id)
5480         break;
5481
5482       nd = nd->next;
5483     }
5484
5485   if (nd == NULL)
5486     {
5487       nd = node_data_new (view_id);
5488
5489       if (node->node_data)
5490         nd->next = node->node_data;
5491
5492       node->node_data = nd;
5493     }
5494
5495   return nd;
5496 }
5497
5498 static void
5499 gtk_text_btree_node_remove_data (GtkTextBTreeNode *node, gpointer view_id)
5500 {
5501   NodeData *nd;
5502   NodeData *prev;
5503
5504   prev = NULL;
5505   nd = node->node_data;
5506   while (nd != NULL)
5507     {
5508       if (nd->view_id == view_id)
5509         break;
5510
5511       prev = nd;
5512       nd = nd->next;
5513     }
5514
5515   if (nd == NULL)
5516     return;
5517
5518   if (prev != NULL)
5519     prev->next = nd->next;
5520
5521   if (node->node_data == nd)
5522     node->node_data = nd->next;
5523
5524   nd->next = NULL;
5525
5526   node_data_destroy (nd);
5527 }
5528
5529 static void
5530 gtk_text_btree_node_get_size (GtkTextBTreeNode *node, gpointer view_id,
5531                               gint *width, gint *height)
5532 {
5533   NodeData *nd;
5534
5535   g_return_if_fail (width != NULL);
5536   g_return_if_fail (height != NULL);
5537
5538   nd = gtk_text_btree_node_ensure_data (node, view_id);
5539
5540   if (width)
5541     *width = nd->width;
5542   if (height)
5543     *height = nd->height;
5544 }
5545
5546 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5547  * here isn't quite right, since for a lot of operations we want to
5548  * know which children of the common parent correspond to the two nodes
5549  * (e.g., when computing the order of two iters)
5550  */
5551 static GtkTextBTreeNode *
5552 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5553                                    GtkTextBTreeNode *node2)
5554 {
5555   while (node1->level < node2->level)
5556     node1 = node1->parent;
5557   while (node2->level < node1->level)
5558     node2 = node2->parent;
5559   while (node1 != node2)
5560     {
5561       node1 = node1->parent;
5562       node2 = node2->parent;
5563     }
5564
5565   return node1;
5566 }
5567
5568 /*
5569  * BTree
5570  */
5571
5572 static BTreeView*
5573 gtk_text_btree_get_view (GtkTextBTree *tree, gpointer view_id)
5574 {
5575   BTreeView *view;
5576
5577   view = tree->views;
5578   while (view != NULL)
5579     {
5580       if (view->view_id == view_id)
5581         break;
5582       view = view->next;
5583     }
5584
5585   return view;
5586 }
5587
5588 static void
5589 get_tree_bounds (GtkTextBTree *tree,
5590                  GtkTextIter *start,
5591                  GtkTextIter *end)
5592 {
5593   _gtk_text_btree_get_iter_at_line_char (tree, start, 0, 0);
5594   _gtk_text_btree_get_end_iter (tree, end);
5595 }
5596
5597 static void
5598 tag_changed_cb (GtkTextTagTable *table,
5599                 GtkTextTag      *tag,
5600                 gboolean         size_changed,
5601                 GtkTextBTree    *tree)
5602 {
5603   if (size_changed)
5604     {
5605       /* We need to queue a relayout on all regions that are tagged with
5606        * this tag.
5607        */
5608
5609       GtkTextIter start;
5610       GtkTextIter end;
5611
5612       if (_gtk_text_btree_get_iter_at_first_toggle (tree, &start, tag))
5613         {
5614           /* Must be a last toggle if there was a first one. */
5615           _gtk_text_btree_get_iter_at_last_toggle (tree, &end, tag);
5616           DV (g_print ("invalidating due to tag change (%s)\n", G_STRLOC));
5617           _gtk_text_btree_invalidate_region (tree,
5618                                             &start, &end);
5619
5620         }
5621     }
5622   else
5623     {
5624       /* We only need to queue a redraw, not a relayout */
5625       BTreeView *view;
5626
5627       view = tree->views;
5628
5629       while (view != NULL)
5630         {
5631           gint width, height;
5632
5633           _gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5634           gtk_text_layout_changed (view->layout, 0, height, height);
5635
5636           view = view->next;
5637         }
5638     }
5639 }
5640
5641 void
5642 _gtk_text_btree_notify_will_remove_tag (GtkTextBTree    *tree,
5643                                         GtkTextTag      *tag)
5644 {
5645   /* Remove the tag from the tree */
5646
5647   GtkTextIter start;
5648   GtkTextIter end;
5649
5650   get_tree_bounds (tree, &start, &end);
5651
5652   _gtk_text_btree_tag (&start, &end, tag, FALSE);
5653   gtk_text_btree_remove_tag_info (tree, tag);
5654 }
5655
5656
5657 /* Rebalance the out-of-whack node "node" */
5658 static void
5659 gtk_text_btree_rebalance (GtkTextBTree *tree,
5660                           GtkTextBTreeNode *node)
5661 {
5662   /*
5663    * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5664    * up through the tree one GtkTextBTreeNode at a time until the root
5665    * GtkTextBTreeNode has been processed.
5666    */
5667
5668   while (node != NULL)
5669     {
5670       GtkTextBTreeNode *new_node, *child;
5671       GtkTextLine *line;
5672       int i;
5673
5674       /*
5675        * Check to see if the GtkTextBTreeNode has too many children.  If it does,
5676        * then split off all but the first MIN_CHILDREN into a separate
5677        * GtkTextBTreeNode following the original one.  Then repeat until the
5678        * GtkTextBTreeNode has a decent size.
5679        */
5680
5681       if (node->num_children > MAX_CHILDREN)
5682         {
5683           while (1)
5684             {
5685               /*
5686                * If the GtkTextBTreeNode being split is the root
5687                * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5688                * it first.
5689                */
5690
5691               if (node->parent == NULL)
5692                 {
5693                   new_node = gtk_text_btree_node_new ();
5694                   new_node->parent = NULL;
5695                   new_node->next = NULL;
5696                   new_node->summary = NULL;
5697                   new_node->level = node->level + 1;
5698                   new_node->children.node = node;
5699                   recompute_node_counts (tree, new_node);
5700                   tree->root_node = new_node;
5701                 }
5702               new_node = gtk_text_btree_node_new ();
5703               new_node->parent = node->parent;
5704               new_node->next = node->next;
5705               node->next = new_node;
5706               new_node->summary = NULL;
5707               new_node->level = node->level;
5708               new_node->num_children = node->num_children - MIN_CHILDREN;
5709               if (node->level == 0)
5710                 {
5711                   for (i = MIN_CHILDREN-1,
5712                          line = node->children.line;
5713                        i > 0; i--, line = line->next)
5714                     {
5715                       /* Empty loop body. */
5716                     }
5717                   new_node->children.line = line->next;
5718                   line->next = NULL;
5719                 }
5720               else
5721                 {
5722                   for (i = MIN_CHILDREN-1,
5723                          child = node->children.node;
5724                        i > 0; i--, child = child->next)
5725                     {
5726                       /* Empty loop body. */
5727                     }
5728                   new_node->children.node = child->next;
5729                   child->next = NULL;
5730                 }
5731               recompute_node_counts (tree, node);
5732               node->parent->num_children++;
5733               node = new_node;
5734               if (node->num_children <= MAX_CHILDREN)
5735                 {
5736                   recompute_node_counts (tree, node);
5737                   break;
5738                 }
5739             }
5740         }
5741
5742       while (node->num_children < MIN_CHILDREN)
5743         {
5744           GtkTextBTreeNode *other;
5745           GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5746           GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5747           int total_children, first_children, i;
5748
5749           /*
5750            * Too few children for this GtkTextBTreeNode.  If this is the root then,
5751            * it's OK for it to have less than MIN_CHILDREN children
5752            * as long as it's got at least two.  If it has only one
5753            * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5754            * the tree and use its child as the new root.
5755            */
5756
5757           if (node->parent == NULL)
5758             {
5759               if ((node->num_children == 1) && (node->level > 0))
5760                 {
5761                   tree->root_node = node->children.node;
5762                   tree->root_node->parent = NULL;
5763
5764                   node->children.node = NULL;
5765                   gtk_text_btree_node_free_empty (tree, node);
5766                 }
5767               return;
5768             }
5769
5770           /*
5771            * Not the root.  Make sure that there are siblings to
5772            * balance with.
5773            */
5774
5775           if (node->parent->num_children < 2)
5776             {
5777               gtk_text_btree_rebalance (tree, node->parent);
5778               continue;
5779             }
5780
5781           /*
5782            * Find a sibling neighbor to borrow from, and arrange for
5783            * node to be the earlier of the pair.
5784            */
5785
5786           if (node->next == NULL)
5787             {
5788               for (other = node->parent->children.node;
5789                    other->next != node;
5790                    other = other->next)
5791                 {
5792                   /* Empty loop body. */
5793                 }
5794               node = other;
5795             }
5796           other = node->next;
5797
5798           /*
5799            * We're going to either merge the two siblings together
5800            * into one GtkTextBTreeNode or redivide the children among them to
5801            * balance their loads.  As preparation, join their two
5802            * child lists into a single list and remember the half-way
5803            * point in the list.
5804            */
5805
5806           total_children = node->num_children + other->num_children;
5807           first_children = total_children/2;
5808           if (node->children.node == NULL)
5809             {
5810               node->children = other->children;
5811               other->children.node = NULL;
5812               other->children.line = NULL;
5813             }
5814           if (node->level == 0)
5815             {
5816               GtkTextLine *line;
5817
5818               for (line = node->children.line, i = 1;
5819                    line->next != NULL;
5820                    line = line->next, i++)
5821                 {
5822                   if (i == first_children)
5823                     {
5824                       halfwayline = line;
5825                     }
5826                 }
5827               line->next = other->children.line;
5828               while (i <= first_children)
5829                 {
5830                   halfwayline = line;
5831                   line = line->next;
5832                   i++;
5833                 }
5834             }
5835           else
5836             {
5837               GtkTextBTreeNode *child;
5838
5839               for (child = node->children.node, i = 1;
5840                    child->next != NULL;
5841                    child = child->next, i++)
5842                 {
5843                   if (i <= first_children)
5844                     {
5845                       if (i == first_children)
5846                         {
5847                           halfwaynode = child;
5848                         }
5849                     }
5850                 }
5851               child->next = other->children.node;
5852               while (i <= first_children)
5853                 {
5854                   halfwaynode = child;
5855                   child = child->next;
5856                   i++;
5857                 }
5858             }
5859
5860           /*
5861            * If the two siblings can simply be merged together, do it.
5862            */
5863
5864           if (total_children <= MAX_CHILDREN)
5865             {
5866               recompute_node_counts (tree, node);
5867               node->next = other->next;
5868               node->parent->num_children--;
5869
5870               other->children.node = NULL;
5871               other->children.line = NULL;
5872               gtk_text_btree_node_free_empty (tree, other);
5873               continue;
5874             }
5875
5876           /*
5877            * The siblings can't be merged, so just divide their
5878            * children evenly between them.
5879            */
5880
5881           if (node->level == 0)
5882             {
5883               other->children.line = halfwayline->next;
5884               halfwayline->next = NULL;
5885             }
5886           else
5887             {
5888               other->children.node = halfwaynode->next;
5889               halfwaynode->next = NULL;
5890             }
5891
5892           recompute_node_counts (tree, node);
5893           recompute_node_counts (tree, other);
5894         }
5895
5896       node = node->parent;
5897     }
5898 }
5899
5900 static void
5901 post_insert_fixup (GtkTextBTree *tree,
5902                    GtkTextLine *line,
5903                    gint line_count_delta,
5904                    gint char_count_delta)
5905
5906 {
5907   GtkTextBTreeNode *node;
5908
5909   /*
5910    * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5911    * point, then rebalance the tree if necessary.
5912    */
5913
5914   for (node = line->parent ; node != NULL;
5915        node = node->parent)
5916     {
5917       node->num_lines += line_count_delta;
5918       node->num_chars += char_count_delta;
5919     }
5920   node = line->parent;
5921   node->num_children += line_count_delta;
5922
5923   if (node->num_children > MAX_CHILDREN)
5924     {
5925       gtk_text_btree_rebalance (tree, node);
5926     }
5927
5928   if (gtk_debug_flags & GTK_DEBUG_TEXT)
5929     _gtk_text_btree_check (tree);
5930 }
5931
5932 static GtkTextTagInfo*
5933 gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
5934                                       GtkTextTag   *tag)
5935 {
5936   GtkTextTagInfo *info;
5937   GSList *list;
5938
5939
5940   list = tree->tag_infos;
5941   while (list != NULL)
5942     {
5943       info = list->data;
5944       if (info->tag == tag)
5945         return info;
5946
5947       list = g_slist_next (list);
5948     }
5949
5950   return NULL;
5951 }
5952
5953 static GtkTextTagInfo*
5954 gtk_text_btree_get_tag_info (GtkTextBTree *tree,
5955                              GtkTextTag   *tag)
5956 {
5957   GtkTextTagInfo *info;
5958
5959   info = gtk_text_btree_get_existing_tag_info (tree, tag);
5960
5961   if (info == NULL)
5962     {
5963       /* didn't find it, create. */
5964
5965       info = g_new (GtkTextTagInfo, 1);
5966
5967       info->tag = tag;
5968       g_object_ref (tag);
5969       info->tag_root = NULL;
5970       info->toggle_count = 0;
5971
5972       tree->tag_infos = g_slist_prepend (tree->tag_infos, info);
5973
5974 #if 0
5975       g_print ("Created tag info %p for tag %s(%p)\n",
5976                info, info->tag->name ? info->tag->name : "anon",
5977                info->tag);
5978 #endif
5979     }
5980
5981   return info;
5982 }
5983
5984 static void
5985 gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
5986                                 GtkTextTag   *tag)
5987 {
5988   GtkTextTagInfo *info;
5989   GSList *list;
5990   GSList *prev;
5991
5992   prev = NULL;
5993   list = tree->tag_infos;
5994   while (list != NULL)
5995     {
5996       info = list->data;
5997       if (info->tag == tag)
5998         {
5999 #if 0
6000           g_print ("Removing tag info %p for tag %s(%p)\n",
6001                    info, info->tag->name ? info->tag->name : "anon",
6002                    info->tag);
6003 #endif
6004
6005           if (prev != NULL)
6006             {
6007               prev->next = list->next;
6008             }
6009           else
6010             {
6011               tree->tag_infos = list->next;
6012             }
6013           list->next = NULL;
6014           g_slist_free (list);
6015
6016           g_object_unref (info->tag);
6017
6018           g_free (info);
6019           return;
6020         }
6021
6022       prev = list;
6023       list = g_slist_next (list);
6024     }
6025 }
6026
6027 static void
6028 recompute_level_zero_counts (GtkTextBTreeNode *node)
6029 {
6030   GtkTextLine *line;
6031   GtkTextLineSegment *seg;
6032
6033   g_assert (node->level == 0);
6034
6035   line = node->children.line;
6036   while (line != NULL)
6037     {
6038       node->num_children++;
6039       node->num_lines++;
6040
6041       if (line->parent != node)
6042         gtk_text_line_set_parent (line, node);
6043
6044       seg = line->segments;
6045       while (seg != NULL)
6046         {
6047
6048           node->num_chars += seg->char_count;
6049
6050           if (((seg->type != &gtk_text_toggle_on_type)
6051                && (seg->type != &gtk_text_toggle_off_type))
6052               || !(seg->body.toggle.inNodeCounts))
6053             {
6054               ; /* nothing */
6055             }
6056           else
6057             {
6058               GtkTextTagInfo *info;
6059
6060               info = seg->body.toggle.info;
6061
6062               gtk_text_btree_node_adjust_toggle_count (node, info, 1);
6063             }
6064
6065           seg = seg->next;
6066         }
6067
6068       line = line->next;
6069     }
6070 }
6071
6072 static void
6073 recompute_level_nonzero_counts (GtkTextBTreeNode *node)
6074 {
6075   Summary *summary;
6076   GtkTextBTreeNode *child;
6077
6078   g_assert (node->level > 0);
6079
6080   child = node->children.node;
6081   while (child != NULL)
6082     {
6083       node->num_children += 1;
6084       node->num_lines += child->num_lines;
6085       node->num_chars += child->num_chars;
6086
6087       if (child->parent != node)
6088         {
6089           child->parent = node;
6090           gtk_text_btree_node_invalidate_upward (node, NULL);
6091         }
6092
6093       summary = child->summary;
6094       while (summary != NULL)
6095         {
6096           gtk_text_btree_node_adjust_toggle_count (node,
6097                                                    summary->info,
6098                                                    summary->toggle_count);
6099
6100           summary = summary->next;
6101         }
6102
6103       child = child->next;
6104     }
6105 }
6106
6107 /*
6108  *----------------------------------------------------------------------
6109  *
6110  * recompute_node_counts --
6111  *
6112  *      This procedure is called to recompute all the counts in a GtkTextBTreeNode
6113  *      (tags, child information, etc.) by scanning the information in
6114  *      its descendants.  This procedure is called during rebalancing
6115  *      when a GtkTextBTreeNode's child structure has changed.
6116  *
6117  * Results:
6118  *      None.
6119  *
6120  * Side effects:
6121  *      The tag counts for node are modified to reflect its current
6122  *      child structure, as are its num_children, num_lines, num_chars fields.
6123  *      Also, all of the childrens' parent fields are made to point
6124  *      to node.
6125  *
6126  *----------------------------------------------------------------------
6127  */
6128
6129 static void
6130 recompute_node_counts (GtkTextBTree *tree, GtkTextBTreeNode *node)
6131 {
6132   BTreeView *view;
6133   Summary *summary, *summary2;
6134
6135   /*
6136    * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
6137    * the existing Summary records (most of them will probably be reused).
6138    */
6139
6140   summary = node->summary;
6141   while (summary != NULL)
6142     {
6143       summary->toggle_count = 0;
6144       summary = summary->next;
6145     }
6146
6147   node->num_children = 0;
6148   node->num_lines = 0;
6149   node->num_chars = 0;
6150
6151   /*
6152    * Scan through the children, adding the childrens' tag counts into
6153    * the GtkTextBTreeNode's tag counts and adding new Summary structures if
6154    * necessary.
6155    */
6156
6157   if (node->level == 0)
6158     recompute_level_zero_counts (node);
6159   else
6160     recompute_level_nonzero_counts (node);
6161
6162   view = tree->views;
6163   while (view)
6164     {
6165       gtk_text_btree_node_check_valid (node, view->view_id);
6166       view = view->next;
6167     }
6168
6169   /*
6170    * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
6171    * records that still have a zero count, or that have all the toggles.
6172    * The GtkTextBTreeNode with the children that account for all the tags toggles
6173    * have no summary information, and they become the tag_root for the tag.
6174    */
6175
6176   summary2 = NULL;
6177   for (summary = node->summary; summary != NULL; )
6178     {
6179       if (summary->toggle_count > 0 &&
6180           summary->toggle_count < summary->info->toggle_count)
6181         {
6182           if (node->level == summary->info->tag_root->level)
6183             {
6184               /*
6185                * The tag's root GtkTextBTreeNode split and some toggles left.
6186                * The tag root must move up a level.
6187                */
6188               summary->info->tag_root = node->parent;
6189             }
6190           summary2 = summary;
6191           summary = summary->next;
6192           continue;
6193         }
6194       if (summary->toggle_count == summary->info->toggle_count)
6195         {
6196           /*
6197            * A GtkTextBTreeNode merge has collected all the toggles under
6198            * one GtkTextBTreeNode.  Push the root down to this level.
6199            */
6200           summary->info->tag_root = node;
6201         }
6202       if (summary2 != NULL)
6203         {
6204           summary2->next = summary->next;
6205           summary_destroy (summary);
6206           summary = summary2->next;
6207         }
6208       else
6209         {
6210           node->summary = summary->next;
6211           summary_destroy (summary);
6212           summary = node->summary;
6213         }
6214     }
6215 }
6216
6217 void
6218 _gtk_change_node_toggle_count (GtkTextBTreeNode *node,
6219                                GtkTextTagInfo   *info,
6220                                gint              delta) /* may be negative */
6221 {
6222   Summary *summary, *prevPtr;
6223   GtkTextBTreeNode *node2Ptr;
6224   int rootLevel;                        /* Level of original tag root */
6225
6226   info->toggle_count += delta;
6227
6228   if (info->tag_root == (GtkTextBTreeNode *) NULL)
6229     {
6230       info->tag_root = node;
6231       return;
6232     }
6233
6234   /*
6235    * Note the level of the existing root for the tag so we can detect
6236    * if it needs to be moved because of the toggle count change.
6237    */
6238
6239   rootLevel = info->tag_root->level;
6240
6241   /*
6242    * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
6243    * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
6244    * necessary.
6245    */
6246
6247   for ( ; node != info->tag_root; node = node->parent)
6248     {
6249       /*
6250        * See if there's already an entry for this tag for this GtkTextBTreeNode.  If so,
6251        * perhaps all we have to do is adjust its count.
6252        */
6253
6254       for (prevPtr = NULL, summary = node->summary;
6255            summary != NULL;
6256            prevPtr = summary, summary = summary->next)
6257         {
6258           if (summary->info == info)
6259             {
6260               break;
6261             }
6262         }
6263       if (summary != NULL)
6264         {
6265           summary->toggle_count += delta;
6266           if (summary->toggle_count > 0 &&
6267               summary->toggle_count < info->toggle_count)
6268             {
6269               continue;
6270             }
6271           if (summary->toggle_count != 0)
6272             {
6273               /*
6274                * Should never find a GtkTextBTreeNode with max toggle count at this
6275                * point (there shouldn't have been a summary entry in the
6276                * first place).
6277                */
6278
6279               g_error ("%s: bad toggle count (%d) max (%d)",
6280                        G_STRLOC, summary->toggle_count, info->toggle_count);
6281             }
6282
6283           /*
6284            * Zero toggle count;  must remove this tag from the list.
6285            */
6286
6287           if (prevPtr == NULL)
6288             {
6289               node->summary = summary->next;
6290             }
6291           else
6292             {
6293               prevPtr->next = summary->next;
6294             }
6295           summary_destroy (summary);
6296         }
6297       else
6298         {
6299           /*
6300            * This tag isn't currently in the summary information list.
6301            */
6302
6303           if (rootLevel == node->level)
6304             {
6305
6306               /*
6307                * The old tag root is at the same level in the tree as this
6308                * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode.  Move the tag root up
6309                * a level, in the hopes that it will now cover this GtkTextBTreeNode
6310                * as well as the old root (if not, we'll move it up again
6311                * the next time through the loop).  To push it up one level
6312                * we copy the original toggle count into the summary
6313                * information at the old root and change the root to its
6314                * parent GtkTextBTreeNode.
6315                */
6316
6317               GtkTextBTreeNode *rootnode = info->tag_root;
6318               summary = (Summary *) g_malloc (sizeof (Summary));
6319               summary->info = info;
6320               summary->toggle_count = info->toggle_count - delta;
6321               summary->next = rootnode->summary;
6322               rootnode->summary = summary;
6323               rootnode = rootnode->parent;
6324               rootLevel = rootnode->level;
6325               info->tag_root = rootnode;
6326             }
6327           summary = (Summary *) g_malloc (sizeof (Summary));
6328           summary->info = info;
6329           summary->toggle_count = delta;
6330           summary->next = node->summary;
6331           node->summary = summary;
6332         }
6333     }
6334
6335   /*
6336    * If we've decremented the toggle count, then it may be necessary
6337    * to push the tag root down one or more levels.
6338    */
6339
6340   if (delta >= 0)
6341     {
6342       return;
6343     }
6344   if (info->toggle_count == 0)
6345     {
6346       info->tag_root = (GtkTextBTreeNode *) NULL;
6347       return;
6348     }
6349   node = info->tag_root;
6350   while (node->level > 0)
6351     {
6352       /*
6353        * See if a single child GtkTextBTreeNode accounts for all of the tag's
6354        * toggles.  If so, push the root down one level.
6355        */
6356
6357       for (node2Ptr = node->children.node;
6358            node2Ptr != (GtkTextBTreeNode *)NULL ;
6359            node2Ptr = node2Ptr->next)
6360         {
6361           for (prevPtr = NULL, summary = node2Ptr->summary;
6362                summary != NULL;
6363                prevPtr = summary, summary = summary->next)
6364             {
6365               if (summary->info == info)
6366                 {
6367                   break;
6368                 }
6369             }
6370           if (summary == NULL)
6371             {
6372               continue;
6373             }
6374           if (summary->toggle_count != info->toggle_count)
6375             {
6376               /*
6377                * No GtkTextBTreeNode has all toggles, so the root is still valid.
6378                */
6379
6380               return;
6381             }
6382
6383           /*
6384            * This GtkTextBTreeNode has all the toggles, so push down the root.
6385            */
6386
6387           if (prevPtr == NULL)
6388             {
6389               node2Ptr->summary = summary->next;
6390             }
6391           else
6392             {
6393               prevPtr->next = summary->next;
6394             }
6395           summary_destroy (summary);
6396           info->tag_root = node2Ptr;
6397           break;
6398         }
6399       node = info->tag_root;
6400     }
6401 }
6402
6403 /*
6404  *----------------------------------------------------------------------
6405  *
6406  * inc_count --
6407  *
6408  *      This is a utility procedure used by _gtk_text_btree_get_tags.  It
6409  *      increments the count for a particular tag, adding a new
6410  *      entry for that tag if there wasn't one previously.
6411  *
6412  * Results:
6413  *      None.
6414  *
6415  * Side effects:
6416  *      The information at *tagInfoPtr may be modified, and the arrays
6417  *      may be reallocated to make them larger.
6418  *
6419  *----------------------------------------------------------------------
6420  */
6421
6422 static void
6423 inc_count (GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
6424 {
6425   GtkTextTag **tag_p;
6426   int count;
6427
6428   for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
6429        count > 0; tag_p++, count--)
6430     {
6431       if (*tag_p == tag)
6432         {
6433           tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
6434           return;
6435         }
6436     }
6437
6438   /*
6439    * There isn't currently an entry for this tag, so we have to
6440    * make a new one.  If the arrays are full, then enlarge the
6441    * arrays first.
6442    */
6443
6444   if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
6445     {
6446       GtkTextTag **newTags;
6447       int *newCounts, newSize;
6448
6449       newSize = 2*tagInfoPtr->arraySize;
6450       newTags = (GtkTextTag **) g_malloc ((unsigned)
6451                                           (newSize*sizeof (GtkTextTag *)));
6452       memcpy ((void *) newTags, (void *) tagInfoPtr->tags,
6453               tagInfoPtr->arraySize  *sizeof (GtkTextTag *));
6454       g_free ((char *) tagInfoPtr->tags);
6455       tagInfoPtr->tags = newTags;
6456       newCounts = (int *) g_malloc ((unsigned) (newSize*sizeof (int)));
6457       memcpy ((void *) newCounts, (void *) tagInfoPtr->counts,
6458               tagInfoPtr->arraySize  *sizeof (int));
6459       g_free ((char *) tagInfoPtr->counts);
6460       tagInfoPtr->counts = newCounts;
6461       tagInfoPtr->arraySize = newSize;
6462     }
6463
6464   tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
6465   tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
6466   tagInfoPtr->numTags++;
6467 }
6468
6469 static void
6470 gtk_text_btree_link_segment (GtkTextLineSegment *seg,
6471                              const GtkTextIter *iter)
6472 {
6473   GtkTextLineSegment *prev;
6474   GtkTextLine *line;
6475   GtkTextBTree *tree;
6476
6477   line = _gtk_text_iter_get_text_line (iter);
6478   tree = _gtk_text_iter_get_btree (iter);
6479
6480   prev = gtk_text_line_segment_split (iter);
6481   if (prev == NULL)
6482     {
6483       seg->next = line->segments;
6484       line->segments = seg;
6485     }
6486   else
6487     {
6488       seg->next = prev->next;
6489       prev->next = seg;
6490     }
6491   cleanup_line (line);
6492   segments_changed (tree);
6493
6494   if (gtk_debug_flags & GTK_DEBUG_TEXT)
6495     _gtk_text_btree_check (tree);
6496 }
6497
6498 static void
6499 gtk_text_btree_unlink_segment (GtkTextBTree *tree,
6500                                GtkTextLineSegment *seg,
6501                                GtkTextLine *line)
6502 {
6503   GtkTextLineSegment *prev;
6504
6505   if (line->segments == seg)
6506     {
6507       line->segments = seg->next;
6508     }
6509   else
6510     {
6511       for (prev = line->segments; prev->next != seg;
6512            prev = prev->next)
6513         {
6514           /* Empty loop body. */
6515         }
6516       prev->next = seg->next;
6517     }
6518   cleanup_line (line);
6519   segments_changed (tree);
6520 }
6521
6522 /*
6523  * This is here because it requires BTree internals, it logically
6524  * belongs in gtktextsegment.c
6525  */
6526
6527
6528 /*
6529  *--------------------------------------------------------------
6530  *
6531  * _gtk_toggle_segment_check_func --
6532  *
6533  *      This procedure is invoked to perform consistency checks
6534  *      on toggle segments.
6535  *
6536  * Results:
6537  *      None.
6538  *
6539  * Side effects:
6540  *      If a consistency problem is found the procedure g_errors.
6541  *
6542  *--------------------------------------------------------------
6543  */
6544
6545 void
6546 _gtk_toggle_segment_check_func (GtkTextLineSegment *segPtr,
6547                                 GtkTextLine *line)
6548 {
6549   Summary *summary;
6550   int needSummary;
6551
6552   if (segPtr->byte_count != 0)
6553     {
6554       g_error ("toggle_segment_check_func: segment had non-zero size");
6555     }
6556   if (!segPtr->body.toggle.inNodeCounts)
6557     {
6558       g_error ("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6559     }
6560   needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6561   for (summary = line->parent->summary; ;
6562        summary = summary->next)
6563     {
6564       if (summary == NULL)
6565         {
6566           if (needSummary)
6567             {
6568               g_error ("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6569             }
6570           else
6571             {
6572               break;
6573             }
6574         }
6575       if (summary->info == segPtr->body.toggle.info)
6576         {
6577           if (!needSummary)
6578             {
6579               g_error ("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6580             }
6581           break;
6582         }
6583     }
6584 }
6585
6586 /*
6587  * Debug
6588  */
6589
6590 static void
6591 gtk_text_btree_node_view_check_consistency (GtkTextBTree     *tree,
6592                                             GtkTextBTreeNode *node,
6593                                             NodeData         *nd)
6594 {
6595   gint width;
6596   gint height;
6597   gboolean valid;
6598   BTreeView *view;
6599
6600   view = tree->views;
6601
6602   while (view != NULL)
6603     {
6604       if (view->view_id == nd->view_id)
6605         break;
6606
6607       view = view->next;
6608     }
6609
6610   if (view == NULL)
6611     g_error ("Node has data for a view %p no longer attached to the tree",
6612              nd->view_id);
6613
6614   gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6615                                                &width, &height, &valid);
6616
6617   /* valid aggregate not checked the same as width/height, because on
6618    * btree rebalance we can have invalid nodes where all lines below
6619    * them are actually valid, due to moving lines around between
6620    * nodes.
6621    *
6622    * The guarantee is that if there are invalid lines the node is
6623    * invalid - we don't guarantee that if the node is invalid there
6624    * are invalid lines.
6625    */
6626
6627   if (nd->width != width ||
6628       nd->height != height ||
6629       (nd->valid && !valid))
6630     {
6631       g_error ("Node aggregates for view %p are invalid:\n"
6632                "Are (%d,%d,%s), should be (%d,%d,%s)",
6633                nd->view_id,
6634                nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6635                width, height, valid ? "TRUE" : "FALSE");
6636     }
6637 }
6638
6639 static void
6640 gtk_text_btree_node_check_consistency (GtkTextBTree     *tree,
6641                                        GtkTextBTreeNode *node)
6642 {
6643   GtkTextBTreeNode *childnode;
6644   Summary *summary, *summary2;
6645   GtkTextLine *line;
6646   GtkTextLineSegment *segPtr;
6647   int num_children, num_lines, num_chars, toggle_count, min_children;
6648   GtkTextLineData *ld;
6649   NodeData *nd;
6650
6651   if (node->parent != NULL)
6652     {
6653       min_children = MIN_CHILDREN;
6654     }
6655   else if (node->level > 0)
6656     {
6657       min_children = 2;
6658     }
6659   else  {
6660     min_children = 1;
6661   }
6662   if ((node->num_children < min_children)
6663       || (node->num_children > MAX_CHILDREN))
6664     {
6665       g_error ("gtk_text_btree_node_check_consistency: bad child count (%d)",
6666                node->num_children);
6667     }
6668
6669   nd = node->node_data;
6670   while (nd != NULL)
6671     {
6672       gtk_text_btree_node_view_check_consistency (tree, node, nd);
6673       nd = nd->next;
6674     }
6675
6676   num_children = 0;
6677   num_lines = 0;
6678   num_chars = 0;
6679   if (node->level == 0)
6680     {
6681       for (line = node->children.line; line != NULL;
6682            line = line->next)
6683         {
6684           if (line->parent != node)
6685             {
6686               g_error ("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6687             }
6688           if (line->segments == NULL)
6689             {
6690               g_error ("gtk_text_btree_node_check_consistency: line has no segments");
6691             }
6692
6693           ld = line->views;
6694           while (ld != NULL)
6695             {
6696               /* Just ensuring we don't segv while doing this loop */
6697
6698               ld = ld->next;
6699             }
6700
6701           for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6702             {
6703               if (segPtr->type->checkFunc != NULL)
6704                 {
6705                   (*segPtr->type->checkFunc)(segPtr, line);
6706                 }
6707               if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6708                   && (segPtr->next != NULL)
6709                   && (segPtr->next->byte_count == 0)
6710                   && (segPtr->next->type->leftGravity))
6711                 {
6712                   g_error ("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6713                 }
6714               if ((segPtr->next == NULL)
6715                   && (segPtr->type != &gtk_text_char_type))
6716                 {
6717                   g_error ("gtk_text_btree_node_check_consistency: line ended with wrong type");
6718                 }
6719
6720               num_chars += segPtr->char_count;
6721             }
6722
6723           num_children++;
6724           num_lines++;
6725         }
6726     }
6727   else
6728     {
6729       for (childnode = node->children.node; childnode != NULL;
6730            childnode = childnode->next)
6731         {
6732           if (childnode->parent != node)
6733             {
6734               g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6735             }
6736           if (childnode->level != (node->level-1))
6737             {
6738               g_error ("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6739                        node->level, childnode->level);
6740             }
6741           gtk_text_btree_node_check_consistency (tree, childnode);
6742           for (summary = childnode->summary; summary != NULL;
6743                summary = summary->next)
6744             {
6745               for (summary2 = node->summary; ;
6746                    summary2 = summary2->next)
6747                 {
6748                   if (summary2 == NULL)
6749                     {
6750                       if (summary->info->tag_root == node)
6751                         {
6752                           break;
6753                         }
6754                       g_error ("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6755                                summary->info->tag->name,
6756                                "present in parent summaries");
6757                     }
6758                   if (summary->info == summary2->info)
6759                     {
6760                       break;
6761                     }
6762                 }
6763             }
6764           num_children++;
6765           num_lines += childnode->num_lines;
6766           num_chars += childnode->num_chars;
6767         }
6768     }
6769   if (num_children != node->num_children)
6770     {
6771       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6772                num_children, node->num_children);
6773     }
6774   if (num_lines != node->num_lines)
6775     {
6776       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6777                num_lines, node->num_lines);
6778     }
6779   if (num_chars != node->num_chars)
6780     {
6781       g_error ("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6782                num_chars, node->num_chars);
6783     }
6784
6785   for (summary = node->summary; summary != NULL;
6786        summary = summary->next)
6787     {
6788       if (summary->info->toggle_count == summary->toggle_count)
6789         {
6790           g_error ("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6791                    summary->info->tag->name);
6792         }
6793       toggle_count = 0;
6794       if (node->level == 0)
6795         {
6796           for (line = node->children.line; line != NULL;
6797                line = line->next)
6798             {
6799               for (segPtr = line->segments; segPtr != NULL;
6800                    segPtr = segPtr->next)
6801                 {
6802                   if ((segPtr->type != &gtk_text_toggle_on_type)
6803                       && (segPtr->type != &gtk_text_toggle_off_type))
6804                     {
6805                       continue;
6806                     }
6807                   if (segPtr->body.toggle.info == summary->info)
6808                     {
6809                       if (!segPtr->body.toggle.inNodeCounts)
6810                         g_error ("Toggle segment not in the node counts");
6811
6812                       toggle_count ++;
6813                     }
6814                 }
6815             }
6816         }
6817       else
6818         {
6819           for (childnode = node->children.node;
6820                childnode != NULL;
6821                childnode = childnode->next)
6822             {
6823               for (summary2 = childnode->summary;
6824                    summary2 != NULL;
6825                    summary2 = summary2->next)
6826                 {
6827                   if (summary2->info == summary->info)
6828                     {
6829                       toggle_count += summary2->toggle_count;
6830                     }
6831                 }
6832             }
6833         }
6834       if (toggle_count != summary->toggle_count)
6835         {
6836           g_error ("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6837                    toggle_count, summary->toggle_count);
6838         }
6839       for (summary2 = summary->next; summary2 != NULL;
6840            summary2 = summary2->next)
6841         {
6842           if (summary2->info == summary->info)
6843             {
6844               g_error ("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6845                        summary->info->tag->name);
6846             }
6847         }
6848     }
6849 }
6850
6851 static void
6852 listify_foreach (GtkTextTag *tag, gpointer user_data)
6853 {
6854   GSList** listp = user_data;
6855
6856   *listp = g_slist_prepend (*listp, tag);
6857 }
6858
6859 static GSList*
6860 list_of_tags (GtkTextTagTable *table)
6861 {
6862   GSList *list = NULL;
6863
6864   gtk_text_tag_table_foreach (table, listify_foreach, &list);
6865
6866   return list;
6867 }
6868
6869 void
6870 _gtk_text_btree_check (GtkTextBTree *tree)
6871 {
6872   Summary *summary;
6873   GtkTextBTreeNode *node;
6874   GtkTextLine *line;
6875   GtkTextLineSegment *seg;
6876   GtkTextTag *tag;
6877   GSList *all_tags, *taglist = NULL;
6878   int count;
6879   GtkTextTagInfo *info;
6880
6881   /*
6882    * Make sure that the tag toggle counts and the tag root pointers are OK.
6883    */
6884   all_tags = list_of_tags (tree->table);
6885   for (taglist = all_tags; taglist != NULL ; taglist = taglist->next)
6886     {
6887       tag = taglist->data;
6888       info = gtk_text_btree_get_existing_tag_info (tree, tag);
6889       if (info != NULL)
6890         {
6891           node = info->tag_root;
6892           if (node == NULL)
6893             {
6894               if (info->toggle_count != 0)
6895                 {
6896                   g_error ("_gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6897                            tag->name, info->toggle_count);
6898                 }
6899               continue;         /* no ranges for the tag */
6900             }
6901           else if (info->toggle_count == 0)
6902             {
6903               g_error ("_gtk_text_btree_check found root for \"%s\" with no toggles",
6904                        tag->name);
6905             }
6906           else if (info->toggle_count & 1)
6907             {
6908               g_error ("_gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6909                        tag->name, info->toggle_count);
6910             }
6911           for (summary = node->summary; summary != NULL;
6912                summary = summary->next)
6913             {
6914               if (summary->info->tag == tag)
6915                 {
6916                   g_error ("_gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6917                 }
6918             }
6919           count = 0;
6920           if (node->level > 0)
6921             {
6922               for (node = node->children.node ; node != NULL ;
6923                    node = node->next)
6924                 {
6925                   for (summary = node->summary; summary != NULL;
6926                        summary = summary->next)
6927                     {
6928                       if (summary->info->tag == tag)
6929                         {
6930                           count += summary->toggle_count;
6931                         }
6932                     }
6933                 }
6934             }
6935           else
6936             {
6937               GtkTextLineSegmentClass * last = NULL;
6938
6939               for (line = node->children.line ; line != NULL ;
6940                    line = line->next)
6941                 {
6942                   for (seg = line->segments; seg != NULL;
6943                        seg = seg->next)
6944                     {
6945                       if ((seg->type == &gtk_text_toggle_on_type ||
6946                            seg->type == &gtk_text_toggle_off_type) &&
6947                           seg->body.toggle.info->tag == tag)
6948                         {
6949                           if (last == seg->type)
6950                             g_error ("Two consecutive toggles on or off weren't merged");
6951                           if (!seg->body.toggle.inNodeCounts)
6952                             g_error ("Toggle segment not in the node counts");
6953
6954                           last = seg->type;
6955
6956                           count++;
6957                         }
6958                     }
6959                 }
6960             }
6961           if (count != info->toggle_count)
6962             {
6963               g_error ("_gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6964                        info->toggle_count, tag->name, count);
6965             }
6966         }
6967     }
6968
6969   g_slist_free (all_tags);
6970
6971   /*
6972    * Call a recursive procedure to do the main body of checks.
6973    */
6974
6975   node = tree->root_node;
6976   gtk_text_btree_node_check_consistency (tree, tree->root_node);
6977
6978   /*
6979    * Make sure that there are at least two lines in the text and
6980    * that the last line has no characters except a newline.
6981    */
6982
6983   if (node->num_lines < 2)
6984     {
6985       g_error ("_gtk_text_btree_check: less than 2 lines in tree");
6986     }
6987   if (node->num_chars < 2)
6988     {
6989       g_error ("_gtk_text_btree_check: less than 2 chars in tree");
6990     }
6991   while (node->level > 0)
6992     {
6993       node = node->children.node;
6994       while (node->next != NULL)
6995         {
6996           node = node->next;
6997         }
6998     }
6999   line = node->children.line;
7000   while (line->next != NULL)
7001     {
7002       line = line->next;
7003     }
7004   seg = line->segments;
7005   while ((seg->type == &gtk_text_toggle_off_type)
7006          || (seg->type == &gtk_text_right_mark_type)
7007          || (seg->type == &gtk_text_left_mark_type))
7008     {
7009       /*
7010        * It's OK to toggle a tag off in the last line, but
7011        * not to start a new range.  It's also OK to have marks
7012        * in the last line.
7013        */
7014
7015       seg = seg->next;
7016     }
7017   if (seg->type != &gtk_text_char_type)
7018     {
7019       g_error ("_gtk_text_btree_check: last line has bogus segment type");
7020     }
7021   if (seg->next != NULL)
7022     {
7023       g_error ("_gtk_text_btree_check: last line has too many segments");
7024     }
7025   if (seg->byte_count != 1)
7026     {
7027       g_error ("_gtk_text_btree_check: last line has wrong # characters: %d",
7028                seg->byte_count);
7029     }
7030   if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
7031     {
7032       g_error ("_gtk_text_btree_check: last line had bad value: %s",
7033                seg->body.chars);
7034     }
7035 }
7036
7037 void _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line);
7038 void _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment* seg);
7039 void _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent);
7040 void _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
7041
7042 void
7043 _gtk_text_btree_spew (GtkTextBTree *tree)
7044 {
7045   GtkTextLine * line;
7046   int real_line;
7047
7048   printf ("%d lines in tree %p\n",
7049           _gtk_text_btree_line_count (tree), tree);
7050
7051   line = _gtk_text_btree_get_line (tree, 0, &real_line);
7052
7053   while (line != NULL)
7054     {
7055       _gtk_text_btree_spew_line (tree, line);
7056       line = _gtk_text_line_next (line);
7057     }
7058
7059   printf ("=================== Tag information\n");
7060
7061   {
7062     GSList * list;
7063
7064     list = tree->tag_infos;
7065
7066     while (list != NULL)
7067       {
7068         GtkTextTagInfo *info;
7069
7070         info = list->data;
7071
7072         printf ("  tag `%s': root at %p, toggle count %d\n",
7073                 info->tag->name, info->tag_root, info->toggle_count);
7074
7075         list = g_slist_next (list);
7076       }
7077
7078     if (tree->tag_infos == NULL)
7079       {
7080         printf ("  (no tags in the tree)\n");
7081       }
7082   }
7083
7084   printf ("=================== Tree nodes\n");
7085
7086   {
7087     _gtk_text_btree_spew_node (tree->root_node, 0);
7088   }
7089 }
7090
7091 void
7092 _gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
7093 {
7094   gchar * spaces;
7095   GtkTextLineSegment *seg;
7096
7097   spaces = g_strnfill (indent, ' ');
7098
7099   printf ("%sline %p chars %d bytes %d\n",
7100           spaces, line,
7101           _gtk_text_line_char_count (line),
7102           _gtk_text_line_byte_count (line));
7103
7104   seg = line->segments;
7105   while (seg != NULL)
7106     {
7107       if (seg->type == &gtk_text_char_type)
7108         {
7109           gchar* str = g_strndup (seg->body.chars, MIN (seg->byte_count, 10));
7110           gchar* s;
7111           s = str;
7112           while (*s)
7113             {
7114               if (*s == '\n' || *s == '\r')
7115                 *s = '\\';
7116               ++s;
7117             }
7118           printf ("%s chars `%s'...\n", spaces, str);
7119           g_free (str);
7120         }
7121       else if (seg->type == &gtk_text_right_mark_type)
7122         {
7123           printf ("%s right mark `%s' visible: %d\n",
7124                   spaces,
7125                   seg->body.mark.name,
7126                   seg->body.mark.visible);
7127         }
7128       else if (seg->type == &gtk_text_left_mark_type)
7129         {
7130           printf ("%s left mark `%s' visible: %d\n",
7131                   spaces,
7132                   seg->body.mark.name,
7133                   seg->body.mark.visible);
7134         }
7135       else if (seg->type == &gtk_text_toggle_on_type ||
7136                seg->type == &gtk_text_toggle_off_type)
7137         {
7138           printf ("%s tag `%s' %s\n",
7139                   spaces, seg->body.toggle.info->tag->name,
7140                   seg->type == &gtk_text_toggle_off_type ? "off" : "on");
7141         }
7142
7143       seg = seg->next;
7144     }
7145
7146   g_free (spaces);
7147 }
7148
7149 void
7150 _gtk_text_btree_spew_node (GtkTextBTreeNode *node, int indent)
7151 {
7152   gchar * spaces;
7153   GtkTextBTreeNode *iter;
7154   Summary *s;
7155
7156   spaces = g_strnfill (indent, ' ');
7157
7158   printf ("%snode %p level %d children %d lines %d chars %d\n",
7159           spaces, node, node->level,
7160           node->num_children, node->num_lines, node->num_chars);
7161
7162   s = node->summary;
7163   while (s)
7164     {
7165       printf ("%s %d toggles of `%s' below this node\n",
7166               spaces, s->toggle_count, s->info->tag->name);
7167       s = s->next;
7168     }
7169
7170   g_free (spaces);
7171
7172   if (node->level > 0)
7173     {
7174       iter = node->children.node;
7175       while (iter != NULL)
7176         {
7177           _gtk_text_btree_spew_node (iter, indent + 2);
7178
7179           iter = iter->next;
7180         }
7181     }
7182   else
7183     {
7184       GtkTextLine *line = node->children.line;
7185       while (line != NULL)
7186         {
7187           _gtk_text_btree_spew_line_short (line, indent + 2);
7188
7189           line = line->next;
7190         }
7191     }
7192 }
7193
7194 void
7195 _gtk_text_btree_spew_line (GtkTextBTree* tree, GtkTextLine* line)
7196 {
7197   GtkTextLineSegment * seg;
7198
7199   printf ("%4d| line: %p parent: %p next: %p\n",
7200           _gtk_text_line_get_number (line), line, line->parent, line->next);
7201
7202   seg = line->segments;
7203
7204   while (seg != NULL)
7205     {
7206       _gtk_text_btree_spew_segment (tree, seg);
7207       seg = seg->next;
7208     }
7209 }
7210
7211 void
7212 _gtk_text_btree_spew_segment (GtkTextBTree* tree, GtkTextLineSegment * seg)
7213 {
7214   printf ("     segment: %p type: %s bytes: %d chars: %d\n",
7215           seg, seg->type->name, seg->byte_count, seg->char_count);
7216
7217   if (seg->type == &gtk_text_char_type)
7218     {
7219       gchar* str = g_strndup (seg->body.chars, seg->byte_count);
7220       printf ("       `%s'\n", str);
7221       g_free (str);
7222     }
7223   else if (seg->type == &gtk_text_right_mark_type)
7224     {
7225       printf ("       right mark `%s' visible: %d not_deleteable: %d\n",
7226               seg->body.mark.name,
7227               seg->body.mark.visible,
7228               seg->body.mark.not_deleteable);
7229     }
7230   else if (seg->type == &gtk_text_left_mark_type)
7231     {
7232       printf ("       left mark `%s' visible: %d not_deleteable: %d\n",
7233               seg->body.mark.name,
7234               seg->body.mark.visible,
7235               seg->body.mark.not_deleteable);
7236     }
7237   else if (seg->type == &gtk_text_toggle_on_type ||
7238            seg->type == &gtk_text_toggle_off_type)
7239     {
7240       printf ("       tag `%s' priority %d\n",
7241               seg->body.toggle.info->tag->name,
7242               seg->body.toggle.info->tag->priority);
7243     }
7244 }
7245
7246 #define __GTK_TEXT_BTREE_C__
7247 #include "gtkaliasdef.c"