gtktextbtree.c 188 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
#include <config.h>
57 58 59 60 61 62 63 64 65
#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"
66
#include "gtktextmarkprivate.h"
67 68 69 70 71 72 73 74

/*
 * Types
 */


/*
 * The structure below is used to pass information between
75
 * _gtk_text_btree_get_tags and inc_count:
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 102
 */

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;
103
  signed int width : 24;
104

105 106 107 108 109 110
  /* 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.
   */
111
  guint valid : 8;		/* Actually a boolean */
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 179
};


/*
 * 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
180 181
  GtkTextMark *insert_mark;
  GtkTextMark *selection_bound_mark;
182 183 184
  GtkTextBuffer *buffer;
  BTreeView *views;
  GSList *tag_infos;
185
  gulong tag_changed_handler;
186

187
  /* Incremented when a segment with a byte size > 0
188 189 190 191 192
   * 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.
   */
193 194
  guint chars_changed_stamp;
  /* Incremented when any segments are added or deleted;
195 196 197
   * this makes outstanding iterators recalculate their
   * pointed-to segment and segment offset.
   */
198
  guint segments_changed_stamp;
199

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

204 205 206 207 208 209 210
  /* 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;
211
  guint end_iter_line_stamp;
212 213
  guint end_iter_segment_stamp;
  
214
  GHashTable *child_anchor_table;
215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
};


/*
 * 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).
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 284
   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,
285
                                                                       gpointer          view_id);
286
static NodeData *            gtk_text_btree_node_check_valid          (GtkTextBTreeNode *node,
287
                                                                       gpointer          view_id);
288
static NodeData *            gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
289
                                                                       gpointer          view_id);
290
static void                  gtk_text_btree_node_check_valid_upward   (GtkTextBTreeNode *node,
291
                                                                       gpointer          view_id);
292 293 294 295 296 297

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
298 299
static void                  gtk_text_btree_node_free_empty          (GtkTextBTree *tree,
                                                                      GtkTextBTreeNode *node);
300 301 302 303 304 305 306 307 308
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,
309
                                                                      GtkTextBTreeNode *node2);
310 311 312 313 314 315 316 317 318
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,
319
                                   GtkTextBTreeNode *node);
320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339
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
340 341 342
static void redisplay_region (GtkTextBTree      *tree,
                              const GtkTextIter *start,
                              const GtkTextIter *end);
343 344 345 346

/* Inline thingies */

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

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

/*
 * BTree operations
 */

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

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

373 374 375 376 377 378 379 380
  /*
   * 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. */
381 382 383 384 385

  root_node = gtk_text_btree_node_new ();

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

  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;
395

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

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

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

  /* Create the tree itself */
406

407 408 409 410 411 412
  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
413 414 415 416 417
   * 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 ();
418

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

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

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

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

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

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

450

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

    seg = tree->insert_mark->segment;
459

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

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

    seg = tree->selection_bound_mark->segment;
471

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

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

  tree->refcount = 1;
479

480 481 482 483
  return tree;
}

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

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

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

  tree->refcount -= 1;

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

Manish Singh's avatar
Manish Singh committed
505
      g_object_unref (tree->table);
506 507 508 509 510
      tree->table = NULL;
      
      gtk_text_btree_node_destroy (tree, tree->root_node);
      tree->root_node = NULL;
      
Havoc Pennington's avatar
Havoc Pennington committed
511
      g_assert (g_hash_table_size (tree->mark_table) == 0);
Havoc Pennington's avatar
Havoc Pennington committed
512
      g_hash_table_destroy (tree->mark_table);
513
      tree->mark_table = NULL;
514 515 516 517 518 519
      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
520
      g_object_unref (tree->insert_mark);
521
      tree->insert_mark = NULL;
Manish Singh's avatar
Manish Singh committed
522
      g_object_unref (tree->selection_bound_mark);
523
      tree->selection_bound_mark = NULL;
524

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

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

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

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

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

/*
 * Indexable segment mutation
 */

558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 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 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725
/*
 *  The following function is responsible for resolving the bidi direction
 *  for the lines between start and end. But it also calculates any
 *  dependent bidi direction for surrounding lines that change as a result
 *  of the bidi direction decisions within the range. The function is
 *  trying to do as little propagation as is needed.
 */
static void
gtk_text_btree_resolve_bidi (GtkTextIter *start,
			     GtkTextIter *end)
{
  GtkTextBTree *tree = _gtk_text_iter_get_btree (start);
  GtkTextLine *start_line, *end_line, *start_line_prev, *end_line_next, *line;
  PangoDirection last_strong, dir_above_propagated, dir_below_propagated;

  /* Resolve the strong bidi direction for all lines between
   * start and end.
  */
  start_line = _gtk_text_iter_get_text_line (start);
  start_line_prev = _gtk_text_line_previous (start_line);
  end_line = _gtk_text_iter_get_text_line (end);
  end_line_next = _gtk_text_line_next (end_line);
  
  line = start_line;
  while (line && line != end_line_next)
    {
      /* Loop through the segments and search for a strong character
       */
      GtkTextLineSegment *seg = line->segments;
      line->dir_strong = PANGO_DIRECTION_NEUTRAL;
      
      while (seg)
        {
          if (seg->byte_count > 0)
            {
	      PangoDirection pango_dir;

              pango_dir = pango_find_base_dir (seg->body.chars,
					       seg->byte_count);
	      
              if (pango_dir != PANGO_DIRECTION_NEUTRAL)
                {
                  line->dir_strong = pango_dir;
                  break;
                }
            }
          seg = seg->next;
        }

      line = _gtk_text_line_next (line);
    }

  /* Sweep forward */

  /* The variable dir_above_propagated contains the forward propagated
   * direction before start. It is neutral if start is in the beginning
   * of the buffer.
   */
  dir_above_propagated = PANGO_DIRECTION_NEUTRAL;
  if (start_line_prev)
    dir_above_propagated = start_line_prev->dir_propagated_forward;

  /* Loop forward and propagate the direction of each paragraph 
   * to all neutral lines.
   */
  line = start_line;
  last_strong = dir_above_propagated;
  while (line != end_line_next)
    {
      if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
        last_strong = line->dir_strong;
      
      line->dir_propagated_forward = last_strong;
      
      line = _gtk_text_line_next (line);
    }

  /* Continue propagating as long as the previous resolved forward
   * is different from last_strong.
   */
  {
    GtkTextIter end_propagate;
    
    while (line &&
	   line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
	   line->dir_propagated_forward != last_strong)
      {
        GtkTextLine *prev = line;
        line->dir_propagated_forward = last_strong;
        
        line = _gtk_text_line_next(line);
        if (!line)
          {
            line = prev;
            break;
          }
      }

    /* The last line to invalidate is the last line before the
     * line with the strong character. Or in case of the end of the
     * buffer, the last line of the buffer. (There seems to be an
     * extra "virtual" last line in the buffer that must not be used
     * calling _gtk_text_btree_get_iter_at_line (causes crash). Thus the
     * _gtk_text_line_previous is ok in that case as well.)
     */
    line = _gtk_text_line_previous (line);
    _gtk_text_btree_get_iter_at_line (tree, &end_propagate, line, 0);
    _gtk_text_btree_invalidate_region (tree, end, &end_propagate);
  }
  
  /* Sweep backward */

  /* The variable dir_below_propagated contains the backward propagated
   * direction after end. It is neutral if end is at the end of
   * the buffer.
  */
  dir_below_propagated = PANGO_DIRECTION_NEUTRAL;
  if (end_line_next)
    dir_below_propagated = end_line_next->dir_propagated_back;

  /* Loop backward and propagate the direction of each paragraph 
   * to all neutral lines.
   */
  line = end_line;
  last_strong = dir_below_propagated;
  while (line != start_line_prev)
    {
      if (line->dir_strong != PANGO_DIRECTION_NEUTRAL)
        last_strong = line->dir_strong;

      line->dir_propagated_back = last_strong;

      line = _gtk_text_line_previous (line);
    }

  /* Continue propagating as long as the resolved backward dir
   * is different from last_strong.
   */
  {
    GtkTextIter start_propagate;

    while (line &&
	   line->dir_strong == PANGO_DIRECTION_NEUTRAL &&
	   line->dir_propagated_back != last_strong)
      {
        GtkTextLine *prev = line;
        line->dir_propagated_back = last_strong;

        line = _gtk_text_line_previous (line);
        if (!line)
          {
            line = prev;
            break;
          }
      }

    /* We only need to invalidate for backwards propagation if the
     * line we ended up on didn't get a direction from forwards
     * propagation.
     */
    if (line && line->dir_propagated_forward == PANGO_DIRECTION_NEUTRAL)
      {
        _gtk_text_btree_get_iter_at_line (tree, &start_propagate, line, 0);
        _gtk_text_btree_invalidate_region(tree, &start_propagate, start);
      }
  }
}

726
void
727
_gtk_text_btree_delete (GtkTextIter *start,
728
                        GtkTextIter *end)
729 730 731 732 733 734 735 736 737 738 739
{
  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;
740
  GtkTextLine *deleted_lines = NULL;        /* List of lines we've deleted */
741
  gint start_byte_offset;
742 743 744

  g_return_if_fail (start != NULL);
  g_return_if_fail (end != NULL);
745 746
  g_return_if_fail (_gtk_text_iter_get_btree (start) ==
                    _gtk_text_iter_get_btree (end));
747

748
  gtk_text_iter_order (start, end);
749

750
  tree = _gtk_text_iter_get_btree (start);
751 752 753 754
 
  if (gtk_debug_flags & GTK_DEBUG_TEXT)
    _gtk_text_btree_check (tree);
  
755
  /* Broadcast the need for redisplay before we break the iterators */
756
  DV (g_print ("invalidating due to deleting some text (%s)\n", G_STRLOC));
757
  _gtk_text_btree_invalidate_region (tree, start, end);
758 759

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

762 763
  start_line = _gtk_text_iter_get_text_line (start);
  end_line = _gtk_text_iter_get_text_line (end);
764

765 766 767 768 769 770 771 772 773
  /*
   * 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.
   */

774
  last_seg = gtk_text_line_segment_split (end);
775 776 777 778 779
  if (last_seg != NULL)
    last_seg = last_seg->next;
  else
    last_seg = end_line->segments;

780
  prev_seg = gtk_text_line_segment_split (start);
781 782 783 784 785 786 787 788 789 790 791 792 793
  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. */
794 795
  segments_changed (tree);

796 797 798 799 800 801 802 803 804
  /*
   * 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;
805

806 807 808 809 810 811 812 813 814 815
      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).
           */

816
          nextline = _gtk_text_line_next (curline);
817 818 819 820 821 822
          if (curline != start_line)
            {
              if (curnode == start_line->parent)
                start_line->next = curline->next;
              else
                curnode->children.line = curline->next;
823

824 825 826
              for (node = curnode; node != NULL;
                   node = node->parent)
                {
827 828 829
                  /* Don't update node->num_chars, because
                   * that was done when we deleted the segments.
                   */
830 831
                  node->num_lines -= 1;
                }
832

833
              curnode->num_children -= 1;
834 835
              curline->next = deleted_lines;
              deleted_lines = curline;
836
            }
837

838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864
          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
865
              gtk_text_btree_node_free_empty (tree, curnode);
866 867 868 869 870 871 872 873
              curnode = parent;
            }
          curnode = curline->parent;
          continue;
        }

      next = seg->next;
      char_count = seg->char_count;
874

Havoc Pennington's avatar
Havoc Pennington committed
875
      if ((*seg->type->deleteFunc)(seg, curline, FALSE) != 0)
876 877 878 879 880
        {
          /*
           * This segment refuses to die.  Move it to prev_seg and
           * advance prev_seg if the segment has left gravity.
           */
881

882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906
          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;
            }
        }
907

908 909 910 911 912 913 914 915 916 917 918 919 920
      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;
921
      int chars_moved;      
922

923 924
      /* last_seg was appended to start_line up at the top of this function */
      chars_moved = 0;
925 926 927
      for (seg = last_seg; seg != NULL;
           seg = seg->next)
        {
928
          chars_moved += seg->char_count;
929 930 931 932 933
          if (seg->type->lineChangeFunc != NULL)
            {
              (*seg->type->lineChangeFunc)(seg, end_line);
            }
        }
934 935 936 937 938 939 940

      for (node = start_line->parent; node != NULL;
           node = node->parent)
        {
          node->num_chars += chars_moved;
        }
      
941 942 943 944
      curnode = end_line->parent;
      for (node = curnode; node != NULL;
           node = node->parent)
        {
945
          node->num_chars -= chars_moved;
946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971
          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)
972 973 974 975 976 977 978 979 980 981 982
        {
          GtkTextLine *line;
          GtkTextLineData *ld;

          gint deleted_width = 0;
          gint deleted_height = 0;

          line = deleted_lines;
          while (line)
            {
              GtkTextLine *next_line = line->next;
983
              ld = _gtk_text_line_get_data (line, view->view_id);
984 985 986 987 988 989 990 991 992 993 994 995 996 997 998

              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)
            {
999
              ld = _gtk_text_line_get_data (start_line, view->view_id);
1000 1001 1002 1003 1004 1005 1006 1007
              
              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.
                   */
1008 1009
                  ld = _gtk_text_line_data_new (view->layout, start_line);
                  _gtk_text_line_add_data (start_line, ld);
1010 1011 1012 1013 1014
                  ld->width = 0;
                  ld->height = 0;
                  ld->valid = FALSE;
                }
              
1015 1016 1017 1018 1019 1020 1021 1022
              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);
1023

1024 1025 1026
          view = view->next;
        }

1027 1028 1029
      /* avoid dangling pointer */
      deleted_lines = NULL;
      
1030
      gtk_text_btree_rebalance (tree, curnode);
1031 1032 1033 1034 1035 1036
    }

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

1037
  cleanup_line (start_line);
1038 1039 1040 1041 1042

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

1043 1044
  gtk_text_btree_rebalance (tree, start_line->parent);

1045 1046
  /* Notify outstanding iterators that they
     are now hosed */
1047 1048
  chars_changed (tree);
  segments_changed (tree);
1049 1050

  if (gtk_debug_flags & GTK_DEBUG_TEXT)
1051
    _gtk_text_btree_check (tree);
1052 1053

  /* Re-initialize our iterators */
1054
  _gtk_text_btree_get_iter_at_line (tree, start, start_line, start_byte_offset);
1055
  *end = *start;
1056 1057

  gtk_text_btree_resolve_bidi (start, end);
1058 1059 1060
}

void
1061
_gtk_text_btree_insert (GtkTextIter *iter,
1062 1063
                        const gchar *text,
                        gint         len)
1064 1065 1066 1067 1068
{
  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
1069
                                             * are inserted just after this one.
1070 1071 1072 1073 1074 1075
                                             * 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
1076 1077 1078 1079 1080 1081
  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 */
1082
  int line_count_delta;                /* Counts change to total number of
Havoc Pennington's avatar
Havoc Pennington committed
1083 1084
                                        * lines in file.
                                        */
1085 1086 1087 1088 1089

  int char_count_delta;                /* change to number of chars */
  GtkTextBTree *tree;
  gint start_byte_index;
  GtkTextLine *start_line;
1090 1091 1092 1093

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

1094
  if (len < 0)
1095
    len = strlen (text);
1096 1097

  /* extract iterator info */
1098 1099
  tree = _gtk_text_iter_get_btree (iter);
  line = _gtk_text_iter_get_text_line (iter);
1100
  
1101
  start_line = line;
1102
  start_byte_index = gtk_text_iter_get_line_index (iter);
1103

1104 1105 1106 1107 1108
  /* 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));
1109
  prev_seg = gtk_text_line_segment_split (iter);
1110 1111 1112
  cur_seg = prev_seg;

  /* Invalidate all iterators */
1113 1114
  chars_changed (tree);
  segments_changed (tree);
1115
  
1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127
  /*
   * 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)
    {
1128 1129
      sol = eol;
      
Havoc Pennington's avatar
Havoc Pennington committed
1130 1131 1132 1133
      pango_find_paragraph_boundary (text + sol,
                                     len - sol,
                                     &delim,
                                     &eol);      
1134

1135 1136 1137
      /* make these relative to the start of the text */
      delim += sol;
      eol += sol;
1138 1139 1140 1141 1142 1143

      g_assert (eol >= sol);
      g_assert (delim >= sol);
      g_assert (eol >= delim);
      g_assert (sol >= 0);
      g_assert (eol <= len);
1144
      
Havoc Pennington's avatar
Havoc Pennington committed
1145
      chunk_len = eol - sol;
1146 1147

      g_assert (g_utf8_validate (&text[sol], chunk_len, NULL));
Havoc Pennington's avatar
Havoc Pennington committed
1148
      seg = _gtk_char_segment_new (&text[sol], chunk_len);
1149 1150

      char_count_delta += seg->char_count;
1151

1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162
      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
1163
      if (delim == eol)
1164 1165 1166 1167 1168
        {
          /* chunk didn't end with a paragraph separator */
          g_assert (eol == len);
          break;
        }
1169 1170 1171 1172 1173 1174

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

1175 1176
      newline = gtk_text_line_new ();
      gtk_text_line_set_parent (newline, line->parent);
1177 1178 1179 1180 1181 1182
      newline->next = line->next;
      line->next = newline;
      newline->segments = seg->next;
      seg->next = NULL;
      line = newline;
      cur_seg = NULL;
1183
      line_count_delta++;
1184 1185 1186 1187 1188 1189 1190
    }

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

1191
  cleanup_line (start_line);
1192 1193
  if (line != start_line)
    {
1194
      cleanup_line (line);
1195 1196
    }

1197 1198
  post_insert_fixup (tree, line, line_count_delta, char_count_delta);

1199 1200 1201 1202 1203 1204 1205
  /* Invalidate our region, and reset the iterator the user
     passed in to point to the end of the inserted text. */
  {
    GtkTextIter start;
    GtkTextIter end;


1206
    _gtk_text_btree_get_iter_at_line (tree,
1207 1208 1209
                                      &start,
                                      start_line,
                                      start_byte_index);
1210 1211 1212 1213 1214
    end = start;

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

1217
    DV (g_print ("invalidating due to inserting some text (%s)\n", G_STRLOC));
1218
    _gtk_text_btree_invalidate_region (tree,
1219
                                      &start, &end);
1220 1221 1222 1223


    /* Convenience for the user */
    *iter = end;
1224 1225

    gtk_text_btree_resolve_bidi (&start, &end);
1226 1227 1228
  }
}

1229 1230 1231 1232
static void
insert_pixbuf_or_widget_segment (GtkTextIter        *iter,
                                 GtkTextLineSegment *seg)

1233 1234 1235 1236 1237 1238
{
  GtkTextIter start;
  GtkTextLineSegment *prevPtr;
  GtkTextLine *line;
  GtkTextBTree *tree;
  gint start_byte_offset;
1239

1240 1241
  line = _gtk_text_iter_get_text_line (iter);
  tree = _gtk_text_iter_get_btree (iter);
1242 1243 1244
  start_byte_offset = gtk_text_iter_get_line_index (iter);

  prevPtr = gtk_text_line_segment_split (iter);
1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255
  if (prevPtr == NULL)
    {
      seg->next = line->segments;
      line->segments = seg;
    }
  else
    {
      seg->next = prevPtr->next;
      prevPtr->next = seg;
    }

1256
  post_insert_fixup (tree, line, 0, seg->char_count);
1257

1258 1259
  chars_changed (tree);
  segments_changed (tree);
1260 1261

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

1263
  _gtk_text_btree_get_iter_at_line (tree, &start, line, start_byte_offset);
1264 1265

  *iter = start;
1266
  gtk_text_iter_forward_char (iter); /* skip forward past the segment */
1267

1268
  DV (g_print ("invalidating due to inserting pixbuf/widget (%s)\n", G_STRLOC));
1269
  _gtk_text_btree_invalidate_region (tree, &start, iter);
1270
}
1271 1272
     
void
1273
_gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1274 1275 1276 1277 1278 1279 1280 1281 1282
                              GdkPixbuf   *pixbuf)
{
  GtkTextLineSegment *seg;
  
  seg = _gtk_pixbuf_segment_new (pixbuf);

  insert_pixbuf_or_widget_segment (iter, seg);
}

1283 1284 1285
void
_gtk_text_btree_insert_child_anchor (GtkTextIter        *iter,
                                     GtkTextChildAnchor *anchor)
1286 1287 1288
{
  GtkTextLineSegment *seg;
  GtkTextBTree *tree;
1289 1290 1291 1292 1293 1294

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

1298
  tree = seg->body.child.tree = _gtk_text_iter_get_btree (iter);
1299
  seg->body.child.line = _gtk_text_iter_get_text_line (iter);
1300
  
1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311
  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
1312
_gtk_text_btree_unregister_child_anchor (GtkTextChildAnchor *anchor)
1313 1314
{
  GtkTextLineSegment *seg;
1315

1316 1317 1318 1319 1320
  seg = anchor->segment;
  
  g_hash_table_remove (seg->body.child.tree->child_anchor_table,
                       anchor);
}
1321 1322 1323 1324 1325 1326

/*
 * View stuff
 */

static GtkTextLine*
1327 1328 1329
find_line_by_y (GtkTextBTree *tree, BTreeView *view,
                GtkTextBTreeNode *node, gint y, gint *line_top,
                GtkTextLine *last_line)
1330 1331 1332 1333
{
  gint current_y = 0;

  if (gtk_debug_flags & GTK_DEBUG_TEXT)
1334
    _gtk_text_btree_check (tree);
1335

1336 1337 1338 1339 1340 1341 1342 1343 1344 1345
  if (node->level == 0)
    {
      GtkTextLine *line;

      line = node->children.line;

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

1346
          ld = _gtk_text_line_get_data (line, view->view_id);
1347

1348 1349 1350 1351 1352 1353 1354 1355
          if (ld)
            {
              if (y < (current_y + (ld ? ld->height : 0)))
                return line;

              current_y += ld->height;
              *line_top += ld->height;
            }
1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371

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

      child = node->children.node;

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

1372 1373
          gtk_text_btree_node_get_size (child, view->view_id,
                                        &width, &height);
1374

1375 1376 1377 1378
          if (y < (current_y + height))
            return find_line_by_y (tree, view, child,
                                   y - current_y, line_top,
                                   last_line);
1379 1380 1381

          current_y += height;
          *line_top += height;
1382

1383 1384
          child = child->next;
        }
1385

1386 1387 1388 1389 1390
      return NULL;
    }
}

GtkTextLine *
1391
_gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1392 1393 1394
                                gpointer      view_id,
                                gint          ypixel,
                                gint         *line_top_out)
1395 1396 1397 1398 1399
{
  GtkTextLine *line;
  BTreeView *view;
  GtkTextLine *last_line;
  gint line_top = 0;
1400

1401 1402 1403 1404
  view = gtk_text_btree_get_view (tree, view_id);
  g_return_val_if_fail (view != NULL, NULL);

  last_line = get_last_line (tree);
1405

1406
  line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1407
                         last_line);
1408 1409 1410 1411 1412 1413 1414 1415

  if (line_top_out)
    *line_top_out = line_top;

  return line;
}

static gint
1416 1417 1418 1419 1420
find_line_top_in_line_list (GtkTextBTree *tree,
                            BTreeView *view,
                            GtkTextLine *line,
                            GtkTextLine *target_line,
                            gint y)
1421 1422 1423 1424
{
  while (line != NULL)
    {
      GtkTextLineData *ld;
1425

1426
      if (line == target_line)
1427
        return y;
1428

1429
      ld = _gtk_text_line_get_data (line, view->view_id);
1430
      if (ld)
1431 1432
        y += ld->height;

1433 1434
      line = line->next;
    }
1435 1436 1437 1438

  g_assert_not_reached (); /* If we get here, our
                              target line didn't exist
                              under its parent node */
1439 1440 1441 1442
  return 0;
}

gint
1443
_gtk_text_btree_find_line_top (GtkTextBTree *tree,
1444 1445 1446 1447 1448 1449 1450 1451 1452
                              GtkTextLine *target_line,
                              gpointer view_id)
{
  gint y = 0;
  BTreeView *view;
  GSList *nodes;
  GSList *iter;
  GtkTextBTreeNode *node;

1453 1454 1455
  view = gtk_text_btree_get_view (tree, view_id);

  g_return_val_if_fail (view != NULL, 0);
1456 1457 1458 1459 1460

  nodes = NULL;
  node = target_line->parent;
  while (node != NULL)
    {
1461
      nodes = g_slist_prepend (nodes, node);
1462 1463 1464 1465 1466
      node = node->parent;
    }

  iter = nodes;
  while (iter != NULL)
1467
    {
1468
      node = iter->data;
1469

1470 1471
      if (node->level == 0)
        {
1472 1473 1474 1475
          g_slist_free (nodes);
          return find_line_top_in_line_list (tree, view,
                                             node->children.line,
                                             target_line, y);
1476 1477 1478 1479 1480 1481
        }
      else
        {
          GtkTextBTreeNode *child;
          GtkTextBTreeNode *target_node;

1482
          g_assert (iter->next != NULL); /* not at level 0 */
1483
          target_node = iter->next->data;
1484

1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495
          child = node->children.node;

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

              if (child == target_node)
                break;
              else
                {
1496 1497
                  gtk_text_btree_node_get_size (child, view->view_id,
                                                &width, &height);
1498 1499 1500 1501
                  y += height;
                }
              child = child->next;
            }
1502 1503
          g_assert (child != NULL); /* should have broken out before we
                                       ran out of nodes */