gtktextbtree.c 183 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
/*
 * gtktextbtree.c --
 *
 *      This file contains code that manages the B-tree representation
 *      of text for the text buffer and implements character and
 *      toggle segment types.
 *
 * Copyright (c) 1992-1994 The Regents of the University of California.
 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
 * Copyright (c) 2000      Red Hat, Inc.
 * Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
 *
 * This software is copyrighted by the Regents of the University of
 * California, Sun Microsystems, Inc., and other parties.  The
 * following terms apply to all files associated with the software
 * unless explicitly disclaimed in individual files.
17
 *
18 19 20 21 22 23 24 25 26
 * The authors hereby grant permission to use, copy, modify,
 * distribute, and license this software and its documentation for any
 * purpose, provided that existing copyright notices are retained in
 * all copies and that this notice is included verbatim in any
 * distributions. No written agreement, license, or royalty fee is
 * required for any of the authorized uses.  Modifications to this
 * software may be copyrighted by their authors and need not follow
 * the licensing terms described here, provided that the new terms are
 * clearly indicated on the first page of each file where they apply.
27
 *
28 29 30 31 32
 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
33
 *
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
 * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * GOVERNMENT USE: If you are acquiring this software on behalf of the
 * U.S. government, the Government shall have only "Restricted Rights"
 * in the software and related documentation as defined in the Federal
 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
 * are acquiring the software on behalf of the Department of Defense,
 * the software shall be classified as "Commercial Computer Software"
 * and the Government shall have only "Restricted Rights" as defined
 * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
 * foregoing, the authors grant the U.S. Government and others acting
 * in its behalf permission to use and distribute the software in
 * accordance with the terms specified in this license.
52
 *
53 54
 */

55
#define GTK_TEXT_USE_INTERNAL_UNSUPPORTED_API
56 57 58 59 60 61 62 63 64
#include "gtktextbtree.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include "gtktexttag.h"
#include "gtktexttagtable.h"
#include "gtktextlayout.h"
#include "gtktextiterprivate.h"
#include "gtkdebug.h"
65
#include "gtktextmarkprivate.h"
66 67 68 69 70 71 72 73

/*
 * Types
 */


/*
 * The structure below is used to pass information between
74
 * _gtk_text_btree_get_tags and inc_count:
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
 */

typedef struct TagInfo {
  int numTags;                  /* Number of tags for which there
                                 * is currently information in
                                 * tags and counts. */
  int arraySize;                        /* Number of entries allocated for
                                         * tags and counts. */
  GtkTextTag **tags;           /* Array of tags seen so far.
                                * Malloc-ed. */
  int *counts;                  /* Toggle count (so far) for each
                                 * entry in tags.  Malloc-ed. */
} TagInfo;


/*
 * This is used to store per-view width/height info at the tree nodes.
 */

typedef struct _NodeData NodeData;

struct _NodeData {
  gpointer view_id;
  NodeData *next;

  /* Height and width of this node */
  gint height;
102
  signed int width : 24;
103

104 105 106 107 108 109
  /* boolean indicating whether the lines below this node are in need of validation.
   * However, width/height should always represent the current total width and
   * max height for lines below this node; the valid flag indicates whether the
   * width/height on the lines needs recomputing, not whether the totals
   * need recomputing.
   */
110
  guint valid : 8;		/* Actually a boolean */
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
};


/*
 * The data structure below keeps summary information about one tag as part
 * of the tag information in a node.
 */

typedef struct Summary {
  GtkTextTagInfo *info;                     /* Handle for tag. */
  int toggle_count;                     /* Number of transitions into or
                                         * out of this tag that occur in
                                         * the subtree rooted at this node. */
  struct Summary *next;         /* Next in list of all tags for same
                                 * node, or NULL if at end of list. */
} Summary;

/*
 * The data structure below defines a node in the B-tree.
 */

struct _GtkTextBTreeNode {
  GtkTextBTreeNode *parent;         /* Pointer to parent node, or NULL if
                                     * this is the root. */
  GtkTextBTreeNode *next;           /* Next in list of siblings with the
                                     * same parent node, or NULL for end
                                     * of list. */
  Summary *summary;             /* First in malloc-ed list of info
                                 * about tags in this subtree (NULL if
                                 * no tag info in the subtree). */
  int level;                            /* Level of this node in the B-tree.
                                         * 0 refers to the bottom of the tree
                                         * (children are lines, not nodes). */
  union {                               /* First in linked list of children. */
    struct _GtkTextBTreeNode *node;         /* Used if level > 0. */
    GtkTextLine *line;         /* Used if level == 0. */
  } children;
  int num_children;                     /* Number of children of this node. */
  int num_lines;                        /* Total number of lines (leaves) in
                                         * the subtree rooted here. */
  int num_chars;                        /* Number of chars below here */

  NodeData *node_data;
};


/*
 * Used to store the list of views in our btree
 */

typedef struct _BTreeView BTreeView;

struct _BTreeView {
  gpointer view_id;
  GtkTextLayout *layout;
  BTreeView *next;
  BTreeView *prev;
};

/*
 * And the tree itself
 */

struct _GtkTextBTree {
  GtkTextBTreeNode *root_node;          /* Pointer to root of B-tree. */
  GtkTextTagTable *table;
  GHashTable *mark_table;
  guint refcount;
Havoc Pennington's avatar
Havoc Pennington committed
179 180
  GtkTextMark *insert_mark;
  GtkTextMark *selection_bound_mark;
181 182 183
  GtkTextBuffer *buffer;
  BTreeView *views;
  GSList *tag_infos;
184
  gulong tag_changed_handler;
185

186
  /* Incremented when a segment with a byte size > 0
187 188 189 190 191
   * is added to or removed from the tree (i.e. the
   * length of a line may have changed, and lines may
   * have been added or removed). This invalidates
   * all outstanding iterators.
   */
192 193
  guint chars_changed_stamp;
  /* Incremented when any segments are added or deleted;
194 195 196
   * this makes outstanding iterators recalculate their
   * pointed-to segment and segment offset.
   */
197
  guint segments_changed_stamp;
198

199 200 201
  /* Cache the last line in the buffer */
  GtkTextLine *last_line;
  guint last_line_stamp;
202

203 204 205 206 207 208 209
  /* Cache the next-to-last line in the buffer,
   * containing the end iterator
   */
  GtkTextLine *end_iter_line;
  GtkTextLineSegment *end_iter_segment;
  int end_iter_segment_byte_index;
  int end_iter_segment_char_offset;
210
  guint end_iter_line_stamp;
211 212
  guint end_iter_segment_stamp;
  
213
  GHashTable *child_anchor_table;
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
};


/*
 * Upper and lower bounds on how many children a node may have:
 * rebalance when either of these limits is exceeded.  MAX_CHILDREN
 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
 */

/* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
   shallow. It appears to be faster to locate a particular line number
   if the tree is narrow and deep, since it is more finely sorted.  I
   guess this may increase memory use though, and make it slower to
   walk the tree in order, or locate a particular byte index (which
   is done by walking the tree in order).
229

230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283
   There's basically a tradeoff here. However I'm thinking we want to
   add pixels, byte counts, and char counts to the tree nodes,
   at that point narrow and deep should speed up all operations,
   not just the line number searches.
*/

#if 1
#define MAX_CHILDREN 12
#define MIN_CHILDREN 6
#else
#define MAX_CHILDREN 6
#define MIN_CHILDREN 3
#endif

/*
 * Prototypes
 */

static BTreeView        *gtk_text_btree_get_view                 (GtkTextBTree     *tree,
                                                                  gpointer          view_id);
static void              gtk_text_btree_rebalance                (GtkTextBTree     *tree,
                                                                  GtkTextBTreeNode *node);
static GtkTextLine     * get_last_line                           (GtkTextBTree     *tree);
static void              post_insert_fixup                       (GtkTextBTree     *tree,
                                                                  GtkTextLine      *insert_line,
                                                                  gint              char_count_delta,
                                                                  gint              line_count_delta);
static void              gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
                                                                  GtkTextTagInfo   *info,
                                                                  gint              adjust);
static gboolean          gtk_text_btree_node_has_tag             (GtkTextBTreeNode *node,
                                                                  GtkTextTag       *tag);

static void             segments_changed                (GtkTextBTree     *tree);
static void             chars_changed                   (GtkTextBTree     *tree);
static void             summary_list_destroy            (Summary          *summary);
static GtkTextLine     *gtk_text_line_new               (void);
static void             gtk_text_line_destroy           (GtkTextBTree     *tree,
                                                         GtkTextLine      *line);
static void             gtk_text_line_set_parent        (GtkTextLine      *line,
                                                         GtkTextBTreeNode *node);
static void             gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
                                                         gpointer          view_id);


static NodeData         *node_data_new          (gpointer  view_id);
static void              node_data_destroy      (NodeData *nd);
static void              node_data_list_destroy (NodeData *nd);
static NodeData         *node_data_find         (NodeData *nd,
                                                 gpointer  view_id);

static GtkTextBTreeNode     *gtk_text_btree_node_new                  (void);
static void                  gtk_text_btree_node_invalidate_downward  (GtkTextBTreeNode *node);
static void                  gtk_text_btree_node_invalidate_upward    (GtkTextBTreeNode *node,
284
                                                                       gpointer          view_id);
285
static NodeData *            gtk_text_btree_node_check_valid          (GtkTextBTreeNode *node,
286
                                                                       gpointer          view_id);
287
static NodeData *            gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
288
                                                                       gpointer          view_id);
289
static void                  gtk_text_btree_node_check_valid_upward   (GtkTextBTreeNode *node,
290
                                                                       gpointer          view_id);
291 292 293 294 295 296

static void                  gtk_text_btree_node_remove_view         (BTreeView        *view,
                                                                      GtkTextBTreeNode *node,
                                                                      gpointer          view_id);
static void                  gtk_text_btree_node_destroy             (GtkTextBTree     *tree,
                                                                      GtkTextBTreeNode *node);
Havoc Pennington's avatar
Havoc Pennington committed
297 298
static void                  gtk_text_btree_node_free_empty          (GtkTextBTree *tree,
                                                                      GtkTextBTreeNode *node);
299 300 301 302 303 304 305 306 307
static NodeData         *    gtk_text_btree_node_ensure_data         (GtkTextBTreeNode *node,
                                                                      gpointer          view_id);
static void                  gtk_text_btree_node_remove_data         (GtkTextBTreeNode *node,
                                                                      gpointer          view_id);
static void                  gtk_text_btree_node_get_size            (GtkTextBTreeNode *node,
                                                                      gpointer          view_id,
                                                                      gint             *width,
                                                                      gint             *height);
static GtkTextBTreeNode *    gtk_text_btree_node_common_parent       (GtkTextBTreeNode *node1,
308
                                                                      GtkTextBTreeNode *node2);
309 310 311 312 313 314 315 316 317
static void get_tree_bounds       (GtkTextBTree     *tree,
                                   GtkTextIter      *start,
                                   GtkTextIter      *end);
static void tag_changed_cb        (GtkTextTagTable  *table,
                                   GtkTextTag       *tag,
                                   gboolean          size_changed,
                                   GtkTextBTree     *tree);
static void cleanup_line          (GtkTextLine      *line);
static void recompute_node_counts (GtkTextBTree     *tree,
318
                                   GtkTextBTreeNode *node);
319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338
static void inc_count             (GtkTextTag       *tag,
                                   int               inc,
                                   TagInfo          *tagInfoPtr);

static void summary_destroy       (Summary          *summary);

static void gtk_text_btree_link_segment   (GtkTextLineSegment *seg,
                                           const GtkTextIter  *iter);
static void gtk_text_btree_unlink_segment (GtkTextBTree       *tree,
                                           GtkTextLineSegment *seg,
                                           GtkTextLine        *line);


static GtkTextTagInfo *gtk_text_btree_get_tag_info          (GtkTextBTree   *tree,
                                                             GtkTextTag     *tag);
static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree   *tree,
                                                             GtkTextTag     *tag);
static void            gtk_text_btree_remove_tag_info       (GtkTextBTree   *tree,
                                                             GtkTextTag     *tag);

Havoc Pennington's avatar
Havoc Pennington committed
339 340 341
static void redisplay_region (GtkTextBTree      *tree,
                              const GtkTextIter *start,
                              const GtkTextIter *end);
342 343 344 345

/* Inline thingies */

static inline void
346
segments_changed (GtkTextBTree *tree)
347 348 349 350 351
{
  tree->segments_changed_stamp += 1;
}

static inline void
352
chars_changed (GtkTextBTree *tree)
353 354 355 356 357 358 359 360 361
{
  tree->chars_changed_stamp += 1;
}

/*
 * BTree operations
 */

GtkTextBTree*
362
_gtk_text_btree_new (GtkTextTagTable *table,
363
                     GtkTextBuffer *buffer)
364 365 366 367 368
{
  GtkTextBTree *tree;
  GtkTextBTreeNode *root_node;
  GtkTextLine *line, *line2;

369 370 371
  g_return_val_if_fail (GTK_IS_TEXT_TAG_TABLE (table), NULL);
  g_return_val_if_fail (GTK_IS_TEXT_BUFFER (buffer), NULL);

372 373 374 375 376 377 378 379
  /*
   * The tree will initially have two empty lines.  The second line
   * isn't actually part of the tree's contents, but its presence
   * makes several operations easier.  The tree will have one GtkTextBTreeNode,
   * which is also the root of the tree.
   */

  /* Create the root node. */
380 381 382 383 384

  root_node = gtk_text_btree_node_new ();

  line = gtk_text_line_new ();
  line2 = gtk_text_line_new ();
385 386 387 388 389 390 391 392 393

  root_node->parent = NULL;
  root_node->next = NULL;
  root_node->summary = NULL;
  root_node->level = 0;
  root_node->children.line = line;
  root_node->num_children = 2;
  root_node->num_lines = 2;
  root_node->num_chars = 2;
394

395 396 397
  line->parent = root_node;
  line->next = line2;

398
  line->segments = _gtk_char_segment_new ("\n", 1);
399 400 401

  line2->parent = root_node;
  line2->next = NULL;
402
  line2->segments = _gtk_char_segment_new ("\n", 1);
403 404

  /* Create the tree itself */
405

406 407 408 409 410 411
  tree = g_new0(GtkTextBTree, 1);
  tree->root_node = root_node;
  tree->table = table;
  tree->views = NULL;

  /* Set these to values that are unlikely to be found
412 413 414 415 416
   * in random memory garbage, and also avoid
   * duplicates between tree instances.
   */
  tree->chars_changed_stamp = g_random_int ();
  tree->segments_changed_stamp = g_random_int ();
417

418 419 420
  tree->last_line_stamp = tree->chars_changed_stamp - 1;
  tree->last_line = NULL;

421
  tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
422
  tree->end_iter_segment_stamp = tree->segments_changed_stamp - 1;
423
  tree->end_iter_line = NULL;
424 425 426
  tree->end_iter_segment_byte_index = 0;
  tree->end_iter_segment_char_offset = 0;
  
Manish Singh's avatar
Manish Singh committed
427
  g_object_ref (tree->table);
428

Manish Singh's avatar
Manish Singh committed
429
  tree->tag_changed_handler = g_signal_connect (tree->table,
430 431 432 433
						"tag_changed",
						G_CALLBACK (tag_changed_cb),
						tree);

434
  tree->mark_table = g_hash_table_new (g_str_hash, g_str_equal);
435 436
  tree->child_anchor_table = NULL;
  
437
  /* We don't ref the buffer, since the buffer owns us;
438 439 440
   * we'd have some circularity issues. The buffer always
   * lasts longer than the BTree
   */
441
  tree->buffer = buffer;
442

443 444
  {
    GtkTextIter start;
Havoc Pennington's avatar
Havoc Pennington committed
445
    GtkTextLineSegment *seg;
446

447
    _gtk_text_btree_get_iter_at_line_char (tree, &start, 0, 0);
448

449

450
    tree->insert_mark = _gtk_text_btree_set_mark (tree,
Havoc Pennington's avatar
Havoc Pennington committed
451 452 453 454 455 456 457
                                                 NULL,
                                                 "insert",
                                                 FALSE,
                                                 &start,
                                                 FALSE);

    seg = tree->insert_mark->segment;
458

Havoc Pennington's avatar
Havoc Pennington committed
459 460
    seg->body.mark.not_deleteable = TRUE;
    seg->body.mark.visible = TRUE;
461

462
    tree->selection_bound_mark = _gtk_text_btree_set_mark (tree,
Havoc Pennington's avatar
Havoc Pennington committed
463 464 465 466 467 468 469
                                                          NULL,
                                                          "selection_bound",
                                                          FALSE,
                                                          &start,
                                                          FALSE);

    seg = tree->selection_bound_mark->segment;
470

Havoc Pennington's avatar
Havoc Pennington committed
471 472
    seg->body.mark.not_deleteable = TRUE;

Manish Singh's avatar
Manish Singh committed
473 474
    g_object_ref (tree->insert_mark);
    g_object_ref (tree->selection_bound_mark);
475 476 477
  }

  tree->refcount = 1;
478

479 480 481 482
  return tree;
}

void
483
_gtk_text_btree_ref (GtkTextBTree *tree)
484
{
485 486 487
  g_return_if_fail (tree != NULL);
  g_return_if_fail (tree->refcount > 0);

488 489 490 491
  tree->refcount += 1;
}

void
492
_gtk_text_btree_unref (GtkTextBTree *tree)
493
{
494 495
  g_return_if_fail (tree != NULL);
  g_return_if_fail (tree->refcount > 0);
496 497 498 499

  tree->refcount -= 1;

  if (tree->refcount == 0)
500
    {      
Manish Singh's avatar
Manish Singh committed
501
      g_signal_handler_disconnect (tree->table,
502
                                   tree->tag_changed_handler);
503

Manish Singh's avatar
Manish Singh committed
504
      g_object_unref (tree->table);
505 506 507 508 509
      tree->table = NULL;
      
      gtk_text_btree_node_destroy (tree, tree->root_node);
      tree->root_node = NULL;
      
Havoc Pennington's avatar
Havoc Pennington committed
510
      g_assert (g_hash_table_size (tree->mark_table) == 0);
Havoc Pennington's avatar
Havoc Pennington committed
511
      g_hash_table_destroy (tree->mark_table);
512
      tree->mark_table = NULL;
513 514 515 516 517 518
      if (tree->child_anchor_table != NULL) 
	{
	  g_hash_table_destroy (tree->child_anchor_table);
	  tree->child_anchor_table = NULL;
	}

Manish Singh's avatar
Manish Singh committed
519
      g_object_unref (tree->insert_mark);
520
      tree->insert_mark = NULL;
Manish Singh's avatar
Manish Singh committed
521
      g_object_unref (tree->selection_bound_mark);
522
      tree->selection_bound_mark = NULL;
523

Havoc Pennington's avatar
Havoc Pennington committed
524
      g_free (tree);
525 526 527 528
    }
}

GtkTextBuffer*
529
_gtk_text_btree_get_buffer (GtkTextBTree *tree)
530 531 532 533 534
{
  return tree->buffer;
}

guint
535
_gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
536 537 538 539 540
{
  return tree->chars_changed_stamp;
}

guint
541
_gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
542 543 544 545 546
{
  return tree->segments_changed_stamp;
}

void
547
_gtk_text_btree_segments_changed (GtkTextBTree *tree)
548
{
549 550
  g_return_if_fail (tree != NULL);
  segments_changed (tree);
551 552 553 554 555 556 557
}

/*
 * Indexable segment mutation
 */

void
558
_gtk_text_btree_delete (GtkTextIter *start,
559
                        GtkTextIter *end)
560 561 562 563 564 565 566 567 568 569 570
{
  GtkTextLineSegment *prev_seg;             /* The segment just before the start
                                             * of the deletion range. */
  GtkTextLineSegment *last_seg;             /* The segment just after the end
                                             * of the deletion range. */
  GtkTextLineSegment *seg, *next;
  GtkTextLine *curline;
  GtkTextBTreeNode *curnode, *node;
  GtkTextBTree *tree;
  GtkTextLine *start_line;
  GtkTextLine *end_line;
571
  GtkTextLine *deleted_lines = NULL;        /* List of lines we've deleted */
572
  gint start_byte_offset;
573 574 575

  g_return_if_fail (start != NULL);
  g_return_if_fail (end != NULL);
576 577
  g_return_if_fail (_gtk_text_iter_get_btree (start) ==
                    _gtk_text_iter_get_btree (end));
578

579
  gtk_text_iter_order (start, end);
580

581
  tree = _gtk_text_iter_get_btree (start);
582 583 584 585
 
  if (gtk_debug_flags & GTK_DEBUG_TEXT)
    _gtk_text_btree_check (tree);
  
586
  /* Broadcast the need for redisplay before we break the iterators */
587
  DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
588
  _gtk_text_btree_invalidate_region (tree, start, end);
589 590

  /* Save the byte offset so we can reset the iterators */
591 592
  start_byte_offset = gtk_text_iter_get_line_index (start);

593 594
  start_line = _gtk_text_iter_get_text_line (start);
  end_line = _gtk_text_iter_get_text_line (end);
595

596 597 598 599 600 601 602 603 604
  /*
   * Split the start and end segments, so we have a place
   * to insert our new text.
   *
   * Tricky point:  split at end first;  otherwise the split
   * at end may invalidate seg and/or prev_seg. This allows
   * us to avoid invalidating segments for start.
   */

605
  last_seg = gtk_text_line_segment_split (end);
606 607 608 609 610
  if (last_seg != NULL)
    last_seg = last_seg->next;
  else
    last_seg = end_line->segments;

611
  prev_seg = gtk_text_line_segment_split (start);
612 613 614 615 616 617 618 619 620 621 622 623 624
  if (prev_seg != NULL)
    {
      seg = prev_seg->next;
      prev_seg->next = last_seg;
    }
  else
    {
      seg = start_line->segments;
      start_line->segments = last_seg;
    }

  /* notify iterators that their segments need recomputation,
     just for robustness. */
625 626
  segments_changed (tree);

627 628 629 630 631 632 633 634 635
  /*
   * Delete all of the segments between prev_seg and last_seg.
   */

  curline = start_line;
  curnode = curline->parent;
  while (seg != last_seg)
    {
      gint char_count = 0;
636

637 638 639 640 641 642 643 644 645 646
      if (seg == NULL)
        {
          GtkTextLine *nextline;

          /*
           * We just ran off the end of a line.  First find the
           * next line, then go back to the old line and delete it
           * (unless it's the starting line for the range).
           */

647
          nextline = _gtk_text_line_next (curline);
648 649 650 651 652 653
          if (curline != start_line)
            {
              if (curnode == start_line->parent)
                start_line->next = curline->next;
              else
                curnode->children.line = curline->next;
654

655 656 657
              for (node = curnode; node != NULL;
                   node = node->parent)
                {
658 659 660
                  /* Don't update node->num_chars, because
                   * that was done when we deleted the segments.
                   */
661 662
                  node->num_lines -= 1;
                }
663

664
              curnode->num_children -= 1;
665 666
              curline->next = deleted_lines;
              deleted_lines = curline;
667
            }
668

669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695
          curline = nextline;
          seg = curline->segments;

          /*
           * If the GtkTextBTreeNode is empty then delete it and its parents,
           * recursively upwards until a non-empty GtkTextBTreeNode is found.
           */

          while (curnode->num_children == 0)
            {
              GtkTextBTreeNode *parent;

              parent = curnode->parent;
              if (parent->children.node == curnode)
                {
                  parent->children.node = curnode->next;
                }
              else
                {
                  GtkTextBTreeNode *prevnode = parent->children.node;
                  while (prevnode->next != curnode)
                    {
                      prevnode = prevnode->next;
                    }
                  prevnode->next = curnode->next;
                }
              parent->num_children--;
Havoc Pennington's avatar
Havoc Pennington committed
696
              gtk_text_btree_node_free_empty (tree, curnode);
697 698 699 700 701 702 703 704
              curnode = parent;
            }
          curnode = curline->parent;
          continue;
        }

      next = seg->next;
      char_count = seg->char_count;
705

Havoc Pennington's avatar
Havoc Pennington committed
706
      if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
707 708 709 710 711
        {
          /*
           * This segment refuses to die.  Move it to prev_seg and
           * advance prev_seg if the segment has left gravity.
           */
712

713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737
          if (prev_seg == NULL)
            {
              seg->next = start_line->segments;
              start_line->segments = seg;
            }
          else
            {
              seg->next = prev_seg->next;
              prev_seg->next = seg;
            }
          if (seg->type->leftGravity)
            {
              prev_seg = seg;
            }
        }
      else
        {
          /* Segment is gone. Decrement the char count of the node and
             all its parents. */
          for (node = curnode; node != NULL;
               node = node->parent)
            {
              node->num_chars -= char_count;
            }
        }
738

739 740 741 742 743 744 745 746 747 748 749 750 751
      seg = next;
    }

  /*
   * If the beginning and end of the deletion range are in different
   * lines, join the two lines together and discard the ending line.
   */

  if (start_line != end_line)
    {
      BTreeView *view;
      GtkTextBTreeNode *ancestor_node;
      GtkTextLine *prevline;
752
      int chars_moved;      
753

754 755
      /* last_seg was appended to start_line up at the top of this function */
      chars_moved = 0;
756 757 758
      for (seg = last_seg; seg != NULL;
           seg = seg->next)
        {
759
          chars_moved += seg->char_count;
760 761 762 763 764
          if (seg->type->lineChangeFunc != NULL)
            {
              (*seg->type->lineChangeFunc)(seg, end_line);
            }
        }
765 766 767 768 769 770 771

      for (node = start_line->parent; node != NULL;
           node = node->parent)
        {
          node->num_chars += chars_moved;
        }
      
772 773 774 775
      curnode = end_line->parent;
      for (node = curnode; node != NULL;
           node = node->parent)
        {
776
          node->num_chars -= chars_moved;
777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802
          node->num_lines--;
        }
      curnode->num_children--;
      prevline = curnode->children.line;
      if (prevline == end_line)
        {
          curnode->children.line = end_line->next;
        }
      else
        {
          while (prevline->next != end_line)
            {
              prevline = prevline->next;
            }
          prevline->next = end_line->next;
        }
      end_line->next = deleted_lines;
      deleted_lines = end_line;

      /* We now fix up the per-view aggregates. We add all the height and
       * width for the deleted lines to the start line, so that when revalidation
       * occurs, the correct change in size is seen.
       */
      ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
      view = tree->views;
      while (view)
803 804 805 806 807 808 809 810 811 812 813
        {
          GtkTextLine *line;
          GtkTextLineData *ld;

          gint deleted_width = 0;
          gint deleted_height = 0;

          line = deleted_lines;
          while (line)
            {
              GtkTextLine *next_line = line->next;
814
              ld = _gtk_text_line_get_data (line, view->view_id);
815 816 817 818 819 820 821 822 823 824 825 826 827 828 829

              if (ld)
                {
                  deleted_width = MAX (deleted_width, ld->width);
                  deleted_height += ld->height;
                }

              if (!view->next)
                gtk_text_line_destroy (tree, line);

              line = next_line;
            }

          if (deleted_width > 0 || deleted_height > 0)
            {
830
              ld = _gtk_text_line_get_data (start_line, view->view_id);
831 832 833 834 835 836 837 838
              
              if (ld == NULL)
                {
                  /* This means that start_line has never been validated.
                   * We don't really want to do the validation here but
                   * we do need to store our temporary sizes. So we
                   * create the line data and assume a line w/h of 0.
                   */
839 840
                  ld = _gtk_text_line_data_new (view->layout, start_line);
                  _gtk_text_line_add_data (start_line, ld);
841 842 843 844 845
                  ld->width = 0;
                  ld->height = 0;
                  ld->valid = FALSE;
                }
              
846 847 848 849 850 851 852 853
              ld->width = MAX (deleted_width, ld->width);
              ld->height += deleted_height;
              ld->valid = FALSE;
            }

          gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
          if (ancestor_node->parent)
            gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
854

855 856 857
          view = view->next;
        }

858 859 860
      /* avoid dangling pointer */
      deleted_lines = NULL;
      
861
      gtk_text_btree_rebalance (tree, curnode);
862 863 864 865 866 867
    }

  /*
   * Cleanup the segments in the new line.
   */

868
  cleanup_line (start_line);
869 870 871 872 873

  /*
   * Lastly, rebalance the first GtkTextBTreeNode of the range.
   */

874 875
  gtk_text_btree_rebalance (tree, start_line->parent);

876 877
  /* Notify outstanding iterators that they
     are now hosed */
878 879
  chars_changed (tree);
  segments_changed (tree);
880 881

  if (gtk_debug_flags & GTK_DEBUG_TEXT)
882
    _gtk_text_btree_check (tree);
883 884

  /* Re-initialize our iterators */
885
  _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
886 887 888 889
  *end = *start;
}

void
890
_gtk_text_btree_insert (GtkTextIter *iter,
891 892
                        const gchar *text,
                        gint         len)
893 894 895 896 897
{
  GtkTextLineSegment *prev_seg;     /* The segment just before the first
                                     * new segment (NULL means new segment
                                     * is at beginning of line). */
  GtkTextLineSegment *cur_seg;              /* Current segment;  new characters
898
                                             * are inserted just after this one.
899 900 901 902 903 904
                                             * NULL means insert at beginning of
                                             * line. */
  GtkTextLine *line;           /* Current line (new segments are
                                * added to this line). */
  GtkTextLineSegment *seg;
  GtkTextLine *newline;
Havoc Pennington's avatar
Havoc Pennington committed
905 906 907 908 909 910
  int chunk_len;                        /* # characters in current chunk. */
  gint sol;                           /* start of line */
  gint eol;                           /* Pointer to character just after last
                                       * one in current chunk.
                                       */
  gint delim;                          /* index of paragraph delimiter */
911
  int line_count_delta;                /* Counts change to total number of
Havoc Pennington's avatar
Havoc Pennington committed
912 913
                                        * lines in file.
                                        */
914 915 916 917 918

  int char_count_delta;                /* change to number of chars */
  GtkTextBTree *tree;
  gint start_byte_index;
  GtkTextLine *start_line;
919 920 921 922

  g_return_if_fail (text != NULL);
  g_return_if_fail (iter != NULL);

923
  if (len < 0)
924
    len = strlen (text);
925 926

  /* extract iterator info */
927 928
  tree = _gtk_text_iter_get_btree (iter);
  line = _gtk_text_iter_get_text_line (iter);
929
  
930
  start_line = line;
931
  start_byte_index = gtk_text_iter_get_line_index (iter);
932

933 934 935 936 937
  /* Get our insertion segment split. Note this assumes line allows
   * char insertions, which isn't true of the "last" line. But iter
   * should not be on that line, as we assert here.
   */
  g_assert (!_gtk_text_line_is_last (line, tree));
938
  prev_seg = gtk_text_line_segment_split (iter);
939 940 941
  cur_seg = prev_seg;

  /* Invalidate all iterators */
942 943
  chars_changed (tree);
  segments_changed (tree);
944
  
945 946 947 948 949 950 951 952 953 954 955 956
  /*
   * Chop the text up into lines and create a new segment for
   * each line, plus a new line for the leftovers from the
   * previous line.
   */

  eol = 0;
  sol = 0;
  line_count_delta = 0;
  char_count_delta = 0;
  while (eol < len)
    {
957 958
      sol = eol;
      
Havoc Pennington's avatar
Havoc Pennington committed
959 960 961 962
      pango_find_paragraph_boundary (text + sol,
                                     len - sol,
                                     &delim,
                                     &eol);      
963

964 965 966
      /* make these relative to the start of the text */
      delim += sol;
      eol += sol;
967 968 969 970 971 972

      g_assert (eol >= sol);
      g_assert (delim >= sol);
      g_assert (eol >= delim);
      g_assert (sol >= 0);
      g_assert (eol <= len);
973
      
Havoc Pennington's avatar
Havoc Pennington committed
974
      chunk_len = eol - sol;
975 976

      g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
Havoc Pennington's avatar
Havoc Pennington committed
977
      seg = _gtk_char_segment_new (&text[sol], chunk_len);
978 979

      char_count_delta += seg->char_count;
980

981 982 983 984 985 986 987 988 989 990 991
      if (cur_seg == NULL)
        {
          seg->next = line->segments;
          line->segments = seg;
        }
      else
        {
          seg->next = cur_seg->next;
          cur_seg->next = seg;
        }

Havoc Pennington's avatar
Havoc Pennington committed
992
      if (delim == eol)
993 994 995 996 997
        {
          /* chunk didn't end with a paragraph separator */
          g_assert (eol == len);
          break;
        }
998 999 1000 1001 1002 1003

      /*
       * The chunk ended with a newline, so create a new GtkTextLine
       * and move the remainder of the old line to it.
       */

1004 1005
      newline = gtk_text_line_new ();
      gtk_text_line_set_parent (newline, line->parent);
1006 1007 1008 1009 1010 1011
      newline->next = line->next;
      line->next = newline;
      newline->segments = seg->next;
      seg->next = NULL;
      line = newline;
      cur_seg = NULL;
1012
      line_count_delta++;
1013 1014 1015 1016 1017 1018 1019
    }

  /*
   * Cleanup the starting line for the insertion, plus the ending
   * line if it's different.
   */

1020
  cleanup_line (start_line);
1021 1022
  if (line != start_line)
    {
1023
      cleanup_line (line);
1024 1025
    }

1026 1027
  post_insert_fixup (tree, line, line_count_delta, char_count_delta);

1028 1029 1030 1031 1032 1033 1034
  /* Invalidate our region, and reset the iterator the user
     passed in to point to the end of the inserted text. */
  {
    GtkTextIter start;
    GtkTextIter end;


1035
    _gtk_text_btree_get_iter_at_line (tree,
1036 1037 1038
                                      &start,
                                      start_line,
                                      start_byte_index);
1039 1040 1041 1042 1043
    end = start;

    /* We could almost certainly be more efficient here
       by saving the information from the insertion loop
       above. FIXME */
1044
    gtk_text_iter_forward_chars (&end, char_count_delta);
1045

1046
    DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1047
    _gtk_text_btree_invalidate_region (tree,
1048
                                      &start, &end);
1049 1050 1051 1052 1053 1054 1055


    /* Convenience for the user */
    *iter = end;
  }
}

1056 1057 1058 1059
static void
insert_pixbuf_or_widget_segment (GtkTextIter        *iter,
                                 GtkTextLineSegment *seg)

1060 1061 1062 1063 1064 1065
{
  GtkTextIter start;
  GtkTextLineSegment *prevPtr;
  GtkTextLine *line;
  GtkTextBTree *tree;
  gint start_byte_offset;
1066

1067 1068
  line = _gtk_text_iter_get_text_line (iter);
  tree = _gtk_text_iter_get_btree (iter);
1069 1070 1071
  start_byte_offset = gtk_text_iter_get_line_index (iter);

  prevPtr = gtk_text_line_segment_split (iter);
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082
  if (prevPtr == NULL)
    {
      seg->next = line->segments;
      line->segments = seg;
    }
  else
    {
      seg->next = prevPtr->next;
      prevPtr->next = seg;
    }

1083
  post_insert_fixup (tree, line, 0, seg->char_count);
1084

1085 1086
  chars_changed (tree);
  segments_changed (tree);
1087 1088

  /* reset *iter for the user, and invalidate tree nodes */
1089

1090
  _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1091 1092

  *iter = start;
1093
  gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1094

1095
  DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1096
  _gtk_text_btree_invalidate_region (tree, &start, iter);
1097
}
1098 1099
     
void
1100
_gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1101 1102 1103 1104 1105 1106 1107 1108 1109
                              GdkPixbuf   *pixbuf)
{
  GtkTextLineSegment *seg;
  
  seg = _gtk_pixbuf_segment_new (pixbuf);

  insert_pixbuf_or_widget_segment (iter, seg);
}

1110 1111 1112
void
_gtk_text_btree_insert_child_anchor (GtkTextIter        *iter,
                                     GtkTextChildAnchor *anchor)
1113 1114 1115
{
  GtkTextLineSegment *seg;
  GtkTextBTree *tree;
1116 1117 1118 1119 1120 1121

  if (anchor->segment != NULL)
    {
      g_warning (G_STRLOC": Same child anchor can't be inserted twice");
      return;
    }
1122
  
1123
  seg = _gtk_widget_segment_new (anchor);
1124

1125
  tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1126
  seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1127
  
1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138
  insert_pixbuf_or_widget_segment (iter, seg);

  if (tree->child_anchor_table == NULL)
    tree->child_anchor_table = g_hash_table_new (NULL, NULL);

  g_hash_table_insert (tree->child_anchor_table,
                       seg->body.child.obj,
                       seg->body.child.obj);
}

void
1139
_gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1140 1141
{
  GtkTextLineSegment *seg;
1142

1143 1144 1145 1146 1147
  seg = anchor->segment;
  
  g_hash_table_remove (seg->body.child.tree->child_anchor_table,
                       anchor);
}
1148 1149 1150 1151 1152 1153

/*
 * View stuff
 */

static GtkTextLine*
1154 1155 1156
find_line_by_y (GtkTextBTree *tree, BTreeView *view,
                GtkTextBTreeNode *node, gint y, gint *line_top,
                GtkTextLine *last_line)
1157 1158 1159 1160
{
  gint current_y = 0;

  if (gtk_debug_flags & GTK_DEBUG_TEXT)
1161
    _gtk_text_btree_check (tree);
1162

1163 1164 1165 1166 1167 1168 1169 1170 1171 1172
  if (node->level == 0)
    {
      GtkTextLine *line;

      line = node->children.line;

      while (line != NULL && line != last_line)
        {
          GtkTextLineData *ld;

1173
          ld = _gtk_text_line_get_data (line, view->view_id);
1174

1175 1176 1177 1178 1179 1180 1181 1182
          if (ld)
            {
              if (y < (current_y + (ld ? ld->height : 0)))
                return line;

              current_y += ld->height;
              *line_top += ld->height;
            }
1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198

          line = line->next;
        }
      return NULL;
    }
  else
    {
      GtkTextBTreeNode *child;

      child = node->children.node;

      while (child != NULL)
        {
          gint width;
          gint height;

1199 1200
          gtk_text_btree_node_get_size (child, view->view_id,
                                        &width, &height);
1201

1202 1203 1204 1205
          if (y < (current_y + height))
            return find_line_by_y (tree, view, child,
                                   y - current_y, line_top,
                                   last_line);
1206 1207 1208

          current_y <