intervals.c 68.1 KB
Newer Older
Joseph Arceneaux's avatar
Joseph Arceneaux committed
1
/* Code for doing intervals.
2
   Copyright (C) 1993-1995, 1997-1998, 2001-2012  Free Software Foundation, Inc.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
3 4 5

This file is part of GNU Emacs.

6
GNU Emacs is free software: you can redistribute it and/or modify
Joseph Arceneaux's avatar
Joseph Arceneaux committed
7
it under the terms of the GNU General Public License as published by
8 9
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
10 11 12 13 14 15 16

GNU Emacs is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
17
along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39


/* NOTES:

   Have to ensure that we can't put symbol nil on a plist, or some
   functions may work incorrectly.

   An idea:  Have the owner of the tree keep count of splits and/or
   insertion lengths (in intervals), and balance after every N.

   Need to call *_left_hook when buffer is killed.

   Scan for zero-length, or 0-length to see notes about handling
   zero length interval-markers.

   There are comments around about freeing intervals.  It might be
   faster to explicitly free them (put them on the free list) than
   to GC them.

*/


40
#include <config.h>
41 42 43

#define INTERVALS_INLINE EXTERN_INLINE

44
#include <setjmp.h>
45
#include <intprops.h>
Joseph Arceneaux's avatar
Joseph Arceneaux committed
46 47
#include "lisp.h"
#include "intervals.h"
48
#include "character.h"
Joseph Arceneaux's avatar
Joseph Arceneaux committed
49
#include "buffer.h"
Richard M. Stallman's avatar
Richard M. Stallman committed
50
#include "puresize.h"
Karl Heuer's avatar
Karl Heuer committed
51
#include "keyboard.h"
Stefan Monnier's avatar
Stefan Monnier committed
52
#include "keymap.h"
Joseph Arceneaux's avatar
Joseph Arceneaux committed
53

54 55 56 57 58
/* Test for membership, allowing for t (actually any non-cons) to mean the
   universal set.  */

#define TMEM(sym, set) (CONSP (set) ? ! NILP (Fmemq (sym, set)) : ! NILP (set))

59 60
static Lisp_Object merge_properties_sticky (Lisp_Object, Lisp_Object);
static INTERVAL merge_interval_right (INTERVAL);
61 62
static INTERVAL reproduce_tree (INTERVAL, INTERVAL);
static INTERVAL reproduce_tree_obj (INTERVAL, Lisp_Object);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
63

64
/* Utility functions for intervals.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
65 66


67
/* Create the root interval of some object, a buffer or string.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
68 69

INTERVAL
70
create_root_interval (Lisp_Object parent)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
71
{
Richard M. Stallman's avatar
Richard M. Stallman committed
72 73 74 75 76
  INTERVAL new;

  CHECK_IMPURE (parent);

  new = make_interval ();
Joseph Arceneaux's avatar
Joseph Arceneaux committed
77

78
  if (BUFFERP (parent))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
79
    {
80 81
      new->total_length = (BUF_Z (XBUFFER (parent))
			   - BUF_BEG (XBUFFER (parent)));
82
      eassert (0 <= TOTAL_LENGTH (new));
83
      buffer_set_intervals (XBUFFER (parent), new);
84
      new->position = BEG;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
85
    }
86
  else if (STRINGP (parent))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
87
    {
88
      new->total_length = SCHARS (parent);
89
      eassert (0 <= TOTAL_LENGTH (new));
90
      string_set_intervals (parent, new);
91
      new->position = 0;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
92 93
    }

94
  interval_set_object (new, parent);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
95 96 97 98 99 100 101

  return new;
}

/* Make the interval TARGET have exactly the properties of SOURCE */

void
102
copy_properties (register INTERVAL source, register INTERVAL target)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
103 104 105 106 107
{
  if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
    return;

  COPY_INTERVAL_CACHE (source, target);
108
  interval_set_plist (target, Fcopy_sequence (source->plist));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
109 110 111
}

/* Merge the properties of interval SOURCE into the properties
112 113
   of interval TARGET.  That is to say, each property in SOURCE
   is added to TARGET if TARGET has no such property as yet.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
114 115

static void
116
merge_properties (register INTERVAL source, register INTERVAL target)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
117 118 119 120 121 122 123 124 125
{
  register Lisp_Object o, sym, val;

  if (DEFAULT_INTERVAL_P (source) && DEFAULT_INTERVAL_P (target))
    return;

  MERGE_INTERVAL_CACHE (source, target);

  o = source->plist;
126
  while (CONSP (o))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
127
    {
128
      sym = XCAR (o);
129 130 131 132 133 134 135 136 137 138 139
      o = XCDR (o);
      CHECK_CONS (o);

      val = target->plist;
      while (CONSP (val) && !EQ (XCAR (val), sym))
	{
	  val = XCDR (val);
	  if (!CONSP (val))
	    break;
	  val = XCDR (val);
	}
Joseph Arceneaux's avatar
Joseph Arceneaux committed
140 141 142

      if (NILP (val))
	{
143
	  val = XCAR (o);
144
	  interval_set_plist (target, Fcons (sym, Fcons (val, target->plist)));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
145
	}
146
      o = XCDR (o);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
147 148 149 150
    }
}

/* Return 1 if the two intervals have the same properties,
151
   0 otherwise.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
152 153

int
154
intervals_equal (INTERVAL i0, INTERVAL i1)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
155
{
156 157
  register Lisp_Object i0_cdr, i0_sym;
  register Lisp_Object i1_cdr, i1_val;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
158 159 160 161

  if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
    return 1;

162 163 164
  if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1))
    return 0;

Joseph Arceneaux's avatar
Joseph Arceneaux committed
165
  i0_cdr = i0->plist;
166 167
  i1_cdr = i1->plist;
  while (CONSP (i0_cdr) && CONSP (i1_cdr))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
168
    {
169
      i0_sym = XCAR (i0_cdr);
170 171 172 173 174 175 176 177 178 179 180
      i0_cdr = XCDR (i0_cdr);
      if (!CONSP (i0_cdr))
	return 0;		/* abort (); */
      i1_val = i1->plist;
      while (CONSP (i1_val) && !EQ (XCAR (i1_val), i0_sym))
	{
	  i1_val = XCDR (i1_val);
	  if (!CONSP (i1_val))
	    return 0;		/* abort (); */
	  i1_val = XCDR (i1_val);
	}
Joseph Arceneaux's avatar
Joseph Arceneaux committed
181

182
      /* i0 has something i1 doesn't.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
183 184 185
      if (EQ (i1_val, Qnil))
	return 0;

186
      /* i0 and i1 both have sym, but it has different values in each.  */
187 188 189
      if (!CONSP (i1_val)
	  || (i1_val = XCDR (i1_val), !CONSP (i1_val))
	  || !EQ (XCAR (i1_val), XCAR (i0_cdr)))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
190 191
	return 0;

192
      i0_cdr = XCDR (i0_cdr);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
193

194 195 196 197 198
      i1_cdr = XCDR (i1_cdr);
      if (!CONSP (i1_cdr))
	return 0;		/* abort (); */
      i1_cdr = XCDR (i1_cdr);
    }
Joseph Arceneaux's avatar
Joseph Arceneaux committed
199

200 201
  /* Lengths of the two plists were equal.  */
  return (NILP (i0_cdr) && NILP (i1_cdr));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
202 203 204
}


205 206 207 208 209
/* Traverse an interval tree TREE, performing FUNCTION on each node.
   No guarantee is made about the order of traversal.
   Pass FUNCTION two args: an interval, and ARG.  */

void
210
traverse_intervals_noorder (INTERVAL tree, void (*function) (INTERVAL, Lisp_Object), Lisp_Object arg)
211 212
{
  /* Minimize stack usage.  */
Dmitry Antipov's avatar
Dmitry Antipov committed
213
  while (tree)
214 215
    {
      (*function) (tree, arg);
Dmitry Antipov's avatar
Dmitry Antipov committed
216
      if (!tree->right)
217 218 219 220 221 222 223 224 225
	tree = tree->left;
      else
	{
	  traverse_intervals_noorder (tree->left, function, arg);
	  tree = tree->right;
	}
    }
}

Joseph Arceneaux's avatar
Joseph Arceneaux committed
226
/* Traverse an interval tree TREE, performing FUNCTION on each node.
227
   Pass FUNCTION two args: an interval, and ARG.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
228 229

void
230
traverse_intervals (INTERVAL tree, ptrdiff_t position,
231
		    void (*function) (INTERVAL, Lisp_Object), Lisp_Object arg)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
232
{
Dmitry Antipov's avatar
Dmitry Antipov committed
233
  while (tree)
234
    {
235
      traverse_intervals (tree->left, position, function, arg);
236 237 238
      position += LEFT_TOTAL_LENGTH (tree);
      tree->position = position;
      (*function) (tree, arg);
239
      position += LENGTH (tree); tree = tree->right;
240
    }
Joseph Arceneaux's avatar
Joseph Arceneaux committed
241 242 243
}

#if 0
244 245 246 247 248

static int icount;
static int idepth;
static int zero_length;

249
/* These functions are temporary, for debugging purposes only.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
250 251 252 253

INTERVAL search_interval, found_interval;

void
Andreas Schwab's avatar
Andreas Schwab committed
254
check_for_interval (INTERVAL i)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
255 256 257 258 259 260 261 262 263
{
  if (i == search_interval)
    {
      found_interval = i;
      icount++;
    }
}

INTERVAL
Andreas Schwab's avatar
Andreas Schwab committed
264
search_for_interval (INTERVAL i, INTERVAL tree)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
265 266 267
{
  icount = 0;
  search_interval = i;
Dmitry Antipov's avatar
Dmitry Antipov committed
268
  found_interval = NULL;
269
  traverse_intervals_noorder (tree, &check_for_interval, Qnil);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
270 271 272 273
  return found_interval;
}

static void
Andreas Schwab's avatar
Andreas Schwab committed
274
inc_interval_count (INTERVAL i)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
275 276 277 278 279 280 281 282 283
{
  icount++;
  if (LENGTH (i) == 0)
    zero_length++;
  if (depth > idepth)
    idepth = depth;
}

int
Andreas Schwab's avatar
Andreas Schwab committed
284
count_intervals (INTERVAL i)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
285 286 287 288
{
  icount = 0;
  idepth = 0;
  zero_length = 0;
289
  traverse_intervals_noorder (i, &inc_interval_count, Qnil);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
290 291 292 293 294

  return icount;
}

static INTERVAL
Andreas Schwab's avatar
Andreas Schwab committed
295
root_interval (INTERVAL interval)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
296 297 298 299
{
  register INTERVAL i = interval;

  while (! ROOT_INTERVAL_P (i))
300
    i = INTERVAL_PARENT (i);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
301 302 303 304 305 306 307 308 309 310 311 312 313 314

  return i;
}
#endif

/* Assuming that a left child exists, perform the following operation:

     A		  B
    / \		 / \
   B       =>       A
  / \		   / \
     c		  c
*/

Paul Eggert's avatar
Paul Eggert committed
315
static inline INTERVAL
316
rotate_right (INTERVAL interval)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
317 318 319
{
  INTERVAL i;
  INTERVAL B = interval->left;
320
  ptrdiff_t old_total = interval->total_length;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
321

322
  /* Deal with any Parent of A;  make it point to B.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
323
  if (! ROOT_INTERVAL_P (interval))
324 325
    {
      if (AM_LEFT_CHILD (interval))
326
	interval_set_left (INTERVAL_PARENT (interval), B);
327
      else
328
	interval_set_right (INTERVAL_PARENT (interval), B);
329
    }
330
  interval_copy_parent (B, interval);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
331

332 333
  /* Make B the parent of A */
  i = B->right;
334 335
  interval_set_right (B, interval);
  interval_set_parent (interval, B);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
336

337
  /* Make A point to c */
338
  interval_set_left (interval, i);
Dmitry Antipov's avatar
Dmitry Antipov committed
339
  if (i)
340
    interval_set_parent (i, interval);
341

342
  /* A's total length is decreased by the length of B and its left child.  */
343
  interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);
344
  eassert (0 <= TOTAL_LENGTH (interval));
345 346 347

  /* B must have the same total length of A.  */
  B->total_length = old_total;
348
  eassert (0 <= TOTAL_LENGTH (B));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
349 350 351

  return B;
}
352

Joseph Arceneaux's avatar
Joseph Arceneaux committed
353 354
/* Assuming that a right child exists, perform the following operation:

Juanma Barranquero's avatar
Juanma Barranquero committed
355 356
    A               B
   / \	           / \
Joseph Arceneaux's avatar
Joseph Arceneaux committed
357
      B	   =>     A
Juanma Barranquero's avatar
Juanma Barranquero committed
358
     / \         / \
Joseph Arceneaux's avatar
Joseph Arceneaux committed
359 360 361
    c               c
*/

Paul Eggert's avatar
Paul Eggert committed
362
static inline INTERVAL
363
rotate_left (INTERVAL interval)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
364 365 366
{
  INTERVAL i;
  INTERVAL B = interval->right;
367
  ptrdiff_t old_total = interval->total_length;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
368

369
  /* Deal with any parent of A;  make it point to B.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
370
  if (! ROOT_INTERVAL_P (interval))
371 372
    {
      if (AM_LEFT_CHILD (interval))
373
	interval_set_left (INTERVAL_PARENT (interval), B);
374
      else
375
	interval_set_right (INTERVAL_PARENT (interval), B);
376
    }
377
  interval_copy_parent (B, interval);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
378 379

  /* Make B the parent of A */
380
  i = B->left;
381 382
  interval_set_left (B, interval);
  interval_set_parent (interval, B);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
383 384

  /* Make A point to c */
385
  interval_set_right (interval, i);
Dmitry Antipov's avatar
Dmitry Antipov committed
386
  if (i)
387
    interval_set_parent (i, interval);
388

389
  /* A's total length is decreased by the length of B and its right child.  */
390
  interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval);
391
  eassert (0 <= TOTAL_LENGTH (interval));
392 393 394

  /* B must have the same total length of A.  */
  B->total_length = old_total;
395
  eassert (0 <= TOTAL_LENGTH (B));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
396 397 398 399

  return B;
}

400 401 402 403
/* Balance an interval tree with the assumption that the subtrees
   themselves are already balanced.  */

static INTERVAL
404
balance_an_interval (INTERVAL i)
405
{
406
  register ptrdiff_t old_diff, new_diff;
407 408 409 410 411 412

  while (1)
    {
      old_diff = LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i);
      if (old_diff > 0)
	{
413
	  /* Since the left child is longer, there must be one.  */
414 415
	  new_diff = i->total_length - i->left->total_length
	    + RIGHT_TOTAL_LENGTH (i->left) - LEFT_TOTAL_LENGTH (i->left);
Eli Zaretskii's avatar
Eli Zaretskii committed
416
	  if (eabs (new_diff) >= old_diff)
417 418 419 420 421 422
	    break;
	  i = rotate_right (i);
	  balance_an_interval (i->right);
	}
      else if (old_diff < 0)
	{
423
	  /* Since the right child is longer, there must be one.  */
424 425
	  new_diff = i->total_length - i->right->total_length
	    + LEFT_TOTAL_LENGTH (i->right) - RIGHT_TOTAL_LENGTH (i->right);
Eli Zaretskii's avatar
Eli Zaretskii committed
426
	  if (eabs (new_diff) >= -old_diff)
427 428 429 430 431 432 433 434 435 436 437 438 439
	    break;
	  i = rotate_left (i);
	  balance_an_interval (i->left);
	}
      else
	break;
    }
  return i;
}

/* Balance INTERVAL, potentially stuffing it back into its parent
   Lisp Object.  */

Paul Eggert's avatar
Paul Eggert committed
440
static inline INTERVAL
441
balance_possible_root_interval (register INTERVAL interval)
442 443
{
  Lisp_Object parent;
444
  int have_parent = 0;
445

446
  if (!INTERVAL_HAS_OBJECT (interval) && !INTERVAL_HAS_PARENT (interval))
447 448
    return interval;

449 450 451 452 453
  if (INTERVAL_HAS_OBJECT (interval))
    {
      have_parent = 1;
      GET_INTERVAL_OBJECT (parent, interval);
    }
454 455
  interval = balance_an_interval (interval);

456 457 458
  if (have_parent)
    {
      if (BUFFERP (parent))
459
	buffer_set_intervals (XBUFFER (parent), interval);
460
      else if (STRINGP (parent))
461
	string_set_intervals (parent, interval);
462
    }
463 464 465 466 467 468 469 470

  return interval;
}

/* Balance the interval tree TREE.  Balancing is by weight
   (the amount of text).  */

static INTERVAL
471
balance_intervals_internal (register INTERVAL tree)
472 473 474
{
  /* Balance within each side.  */
  if (tree->left)
475
    balance_intervals_internal (tree->left);
476
  if (tree->right)
477
    balance_intervals_internal (tree->right);
478 479 480 481 482 483
  return balance_an_interval (tree);
}

/* Advertised interface to balance intervals.  */

INTERVAL
484
balance_intervals (INTERVAL tree)
485
{
Dmitry Antipov's avatar
Dmitry Antipov committed
486
  return tree ? balance_intervals_internal (tree) : NULL;
487
}
Dmitry Antipov's avatar
Dmitry Antipov committed
488

489 490 491 492 493 494 495 496 497 498 499 500 501
/* Rebalance text properties of B.  */

static void
buffer_balance_intervals (struct buffer *b)
{
  INTERVAL i;

  eassert (b != NULL);
  i = buffer_get_intervals (b);
  if (i)
    buffer_set_intervals (b, balance_an_interval (i));
}

502 503 504 505
/* Split INTERVAL into two pieces, starting the second piece at
   character position OFFSET (counting from 0), relative to INTERVAL.
   INTERVAL becomes the left-hand piece, and the right-hand piece
   (second, lexicographically) is returned.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
506 507 508 509 510

   The size and position fields of the two intervals are set based upon
   those of the original interval.  The property list of the new interval
   is reset, thus it is up to the caller to do the right thing with the
   result.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
511 512

   Note that this does not change the position of INTERVAL;  if it is a root,
513
   it is still a root after this operation.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
514 515

INTERVAL
516
split_interval_right (INTERVAL interval, ptrdiff_t offset)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
517 518
{
  INTERVAL new = make_interval ();
519 520
  ptrdiff_t position = interval->position;
  ptrdiff_t new_length = LENGTH (interval) - offset;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
521

522
  new->position = position + offset;
523
  interval_set_parent (new, interval);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
524

525
  if (NULL_RIGHT_CHILD (interval))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
526
    {
527
      interval_set_right (interval, new);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
528
      new->total_length = new_length;
529
      eassert (0 <= TOTAL_LENGTH (new));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
530
    }
531 532 533
  else
    {
      /* Insert the new node between INTERVAL and its right child.  */
534 535 536
      interval_set_right (new, interval->right);
      interval_set_parent (interval->right, new);
      interval_set_right (interval, new);
537
      new->total_length = new_length + new->right->total_length;
538
      eassert (0 <= TOTAL_LENGTH (new));
539 540
      balance_an_interval (new);
    }
Juanma Barranquero's avatar
Juanma Barranquero committed
541

542 543
  balance_possible_root_interval (interval);

Joseph Arceneaux's avatar
Joseph Arceneaux committed
544 545 546
  return new;
}

547 548 549 550
/* Split INTERVAL into two pieces, starting the second piece at
   character position OFFSET (counting from 0), relative to INTERVAL.
   INTERVAL becomes the right-hand piece, and the left-hand piece
   (first, lexicographically) is returned.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
551

Joseph Arceneaux's avatar
Joseph Arceneaux committed
552 553 554 555 556 557
   The size and position fields of the two intervals are set based upon
   those of the original interval.  The property list of the new interval
   is reset, thus it is up to the caller to do the right thing with the
   result.

   Note that this does not change the position of INTERVAL;  if it is a root,
558
   it is still a root after this operation.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
559 560

INTERVAL
561
split_interval_left (INTERVAL interval, ptrdiff_t offset)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
562 563
{
  INTERVAL new = make_interval ();
564
  ptrdiff_t new_length = offset;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
565 566

  new->position = interval->position;
567
  interval->position = interval->position + offset;
568
  interval_set_parent (new, interval);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
569 570 571

  if (NULL_LEFT_CHILD (interval))
    {
572
      interval_set_left (interval, new);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
573
      new->total_length = new_length;
574
      eassert (0 <= TOTAL_LENGTH (new));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
575
    }
576 577 578
  else
    {
      /* Insert the new node between INTERVAL and its left child.  */
579 580 581
      interval_set_left (new, interval->left);
      interval_set_parent (new->left, new);
      interval_set_left (interval, new);
582
      new->total_length = new_length + new->left->total_length;
583
      eassert (0 <= TOTAL_LENGTH (new));
584 585
      balance_an_interval (new);
    }
Juanma Barranquero's avatar
Juanma Barranquero committed
586

587
  balance_possible_root_interval (interval);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
588 589 590 591

  return new;
}

592 593 594 595 596 597 598 599
/* Return the proper position for the first character
   described by the interval tree SOURCE.
   This is 1 if the parent is a buffer,
   0 if the parent is a string or if there is no parent.

   Don't use this function on an interval which is the child
   of another interval!  */

600
static int
601
interval_start_pos (INTERVAL source)
602 603 604
{
  Lisp_Object parent;

Dmitry Antipov's avatar
Dmitry Antipov committed
605
  if (!source)
606 607
    return 0;

608 609
  if (! INTERVAL_HAS_OBJECT (source))
    return 0;
610
  GET_INTERVAL_OBJECT (parent, source);
611 612 613 614 615
  if (BUFFERP (parent))
    return BUF_BEG (XBUFFER (parent));
  return 0;
}

Joseph Arceneaux's avatar
Joseph Arceneaux committed
616
/* Find the interval containing text position POSITION in the text
617
   represented by the interval tree TREE.  POSITION is a buffer
618 619 620
   position (starting from 1) or a string index (starting from 0).
   If POSITION is at the end of the buffer or string,
   return the interval containing the last character.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
621

Joseph Arceneaux's avatar
Joseph Arceneaux committed
622 623
   The `position' field, which is a cache of an interval's position,
   is updated in the interval found.  Other functions (e.g., next_interval)
624
   will update this cache based on the result of find_interval.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
625

626
INTERVAL
627
find_interval (register INTERVAL tree, register ptrdiff_t position)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
628
{
629 630
  /* The distance from the left edge of the subtree at TREE
                    to POSITION.  */
631
  register ptrdiff_t relative_position;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
632

Dmitry Antipov's avatar
Dmitry Antipov committed
633 634
  if (!tree)
    return NULL;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
635

636
  relative_position = position;
637 638 639 640 641 642 643
  if (INTERVAL_HAS_OBJECT (tree))
    {
      Lisp_Object parent;
      GET_INTERVAL_OBJECT (parent, tree);
      if (BUFFERP (parent))
	relative_position -= BUF_BEG (XBUFFER (parent));
    }
644

645
  eassert (relative_position <= TOTAL_LENGTH (tree));
Joseph Arceneaux's avatar
Joseph Arceneaux committed
646

647 648
  if (!handling_signal)
    tree = balance_possible_root_interval (tree);
649

Joseph Arceneaux's avatar
Joseph Arceneaux committed
650 651
  while (1)
    {
652
      if (relative_position < LEFT_TOTAL_LENGTH (tree))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
653 654 655
	{
	  tree = tree->left;
	}
656 657 658
      else if (! NULL_RIGHT_CHILD (tree)
	       && relative_position >= (TOTAL_LENGTH (tree)
					- RIGHT_TOTAL_LENGTH (tree)))
Joseph Arceneaux's avatar
Joseph Arceneaux committed
659 660 661 662 663 664 665
	{
	  relative_position -= (TOTAL_LENGTH (tree)
				- RIGHT_TOTAL_LENGTH (tree));
	  tree = tree->right;
	}
      else
	{
666
	  tree->position
667 668
	    = (position - relative_position /* left edge of *tree.  */
	       + LEFT_TOTAL_LENGTH (tree)); /* left edge of this interval.  */
669

Joseph Arceneaux's avatar
Joseph Arceneaux committed
670 671 672 673 674 675
	  return tree;
	}
    }
}

/* Find the succeeding interval (lexicographically) to INTERVAL.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
676
   Sets the `position' field based on that of INTERVAL (see
677
   find_interval).  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
678 679

INTERVAL
680
next_interval (register INTERVAL interval)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
681 682
{
  register INTERVAL i = interval;
683
  register ptrdiff_t next_position;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
684

Dmitry Antipov's avatar
Dmitry Antipov committed
685 686
  if (!i)
    return NULL;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702
  next_position = interval->position + LENGTH (interval);

  if (! NULL_RIGHT_CHILD (i))
    {
      i = i->right;
      while (! NULL_LEFT_CHILD (i))
	i = i->left;

      i->position = next_position;
      return i;
    }

  while (! NULL_PARENT (i))
    {
      if (AM_LEFT_CHILD (i))
	{
703
	  i = INTERVAL_PARENT (i);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
704 705 706 707
	  i->position = next_position;
	  return i;
	}

708
      i = INTERVAL_PARENT (i);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
709 710
    }

Dmitry Antipov's avatar
Dmitry Antipov committed
711
  return NULL;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
712 713 714
}

/* Find the preceding interval (lexicographically) to INTERVAL.
Joseph Arceneaux's avatar
Joseph Arceneaux committed
715
   Sets the `position' field based on that of INTERVAL (see
716
   find_interval).  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
717 718

INTERVAL
719
previous_interval (register INTERVAL interval)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
720 721 722
{
  register INTERVAL i;

Dmitry Antipov's avatar
Dmitry Antipov committed
723 724
  if (!interval)
    return NULL;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740

  if (! NULL_LEFT_CHILD (interval))
    {
      i = interval->left;
      while (! NULL_RIGHT_CHILD (i))
	i = i->right;

      i->position = interval->position - LENGTH (i);
      return i;
    }

  i = interval;
  while (! NULL_PARENT (i))
    {
      if (AM_RIGHT_CHILD (i))
	{
741
	  i = INTERVAL_PARENT (i);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
742 743 744 745

	  i->position = interval->position - LENGTH (i);
	  return i;
	}
746
      i = INTERVAL_PARENT (i);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
747 748
    }

Dmitry Antipov's avatar
Dmitry Antipov committed
749
  return NULL;
Joseph Arceneaux's avatar
Joseph Arceneaux committed
750
}
751 752

/* Find the interval containing POS given some non-NULL INTERVAL
753
   in the same tree.  Note that we need to update interval->position
754 755 756
   if we go down the tree.
   To speed up the process, we assume that the ->position of
   I and all its parents is already uptodate.  */
757
INTERVAL
758
update_interval (register INTERVAL i, ptrdiff_t pos)
759
{
Dmitry Antipov's avatar
Dmitry Antipov committed
760 761
  if (!i)
    return NULL;
762

Juanma Barranquero's avatar
Juanma Barranquero committed
763
  while (1)
764
    {
Juanma Barranquero's avatar
Juanma Barranquero committed
765
      if (pos < i->position)
766 767
	{
	  /* Move left. */
Juanma Barranquero's avatar
Juanma Barranquero committed
768
	  if (pos >= i->position - TOTAL_LENGTH (i->left))
769 770 771 772 773
	    {
	      i->left->position = i->position - TOTAL_LENGTH (i->left)
		+ LEFT_TOTAL_LENGTH (i->left);
	      i = i->left;		/* Move to the left child */
	    }
Juanma Barranquero's avatar
Juanma Barranquero committed
774
	  else if (NULL_PARENT (i))
775
	    error ("Point before start of properties");
Juanma Barranquero's avatar
Juanma Barranquero committed
776
	  else
777
	      i = INTERVAL_PARENT (i);
778 779 780 781 782
	  continue;
	}
      else if (pos >= INTERVAL_LAST_POS (i))
	{
	  /* Move right. */
Juanma Barranquero's avatar
Juanma Barranquero committed
783
	  if (pos < INTERVAL_LAST_POS (i) + TOTAL_LENGTH (i->right))
784
	    {
785 786
	      i->right->position = INTERVAL_LAST_POS (i)
	        + LEFT_TOTAL_LENGTH (i->right);
787 788
	      i = i->right;		/* Move to the right child */
	    }
Juanma Barranquero's avatar
Juanma Barranquero committed
789
	  else if (NULL_PARENT (i))
790
	    error ("Point %"pD"d after end of properties", pos);
Juanma Barranquero's avatar
Juanma Barranquero committed
791
	  else
792
            i = INTERVAL_PARENT (i);
793 794
	  continue;
	}
Juanma Barranquero's avatar
Juanma Barranquero committed
795
      else
796 797 798 799
	return i;
    }
}

Joseph Arceneaux's avatar
Joseph Arceneaux committed
800 801
/* Effect an adjustment corresponding to the addition of LENGTH characters
   of text.  Do this by finding the interval containing POSITION in the
802
   interval tree TREE, and then adjusting all of its ancestors by adding
Joseph Arceneaux's avatar
Joseph Arceneaux committed
803 804 805 806 807 808
   LENGTH to them.

   If POSITION is the first character of an interval, meaning that point
   is actually between the two intervals, make the new text belong to
   the interval which is "sticky".

Joseph Arceneaux's avatar
Joseph Arceneaux committed
809
   If both intervals are "sticky", then make them belong to the left-most
Joseph Arceneaux's avatar
Joseph Arceneaux committed
810
   interval.  Another possibility would be to create a new interval for
811
   this text, and make it have the merged properties of both ends.  */
Joseph Arceneaux's avatar
Joseph Arceneaux committed
812 813

static INTERVAL
814
adjust_intervals_for_insertion (INTERVAL tree,
815
				ptrdiff_t position, ptrdiff_t length)
Joseph Arceneaux's avatar
Joseph Arceneaux committed
816 817
{
  register INTERVAL i;
818 819
  register INTERVAL temp;
  int eobp = 0;
820
  Lisp_Object parent;
821
  ptrdiff_t offset;
Juanma Barranquero's avatar
Juanma Barranquero committed
822

823
  eassert (TOTAL_LENGTH (tree) > 0);
Joseph Arceneaux's avatar
Joseph Arceneaux committed
824

825
  GET_INTERVAL_OBJECT (parent, tree);
826 827
  offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0);

828 829
  /* If inserting at point-max of a buffer, that position will be out
     of range.  Remember that buffer positions are 1-based.  */
830 831 832 833 834
  if (position >= TOTAL_LENGTH (tree) + offset)
    {
      position = TOTAL_LENGTH (tree) + offset;
      eobp = 1;
    }
Joseph Arceneaux's avatar
Joseph Arceneaux committed
835 836

  i = find_interval (tree, position);
837

838 839
  /* If in middle of an interval which is not sticky either way,
     we must not just give its properties to the insertion.
840 841 842 843 844 845 846 847 848 849
     So split this interval at the insertion point.

     Originally, the if condition here was this:
	(! (position == i->position || eobp)
	 && END_NONSTICKY_P (i)
	 && FRONT_NONSTICKY_P (i))
     But, these macros are now unreliable because of introduction of
     Vtext_property_default_nonsticky.  So, we always check properties
     one by one if POSITION is in middle of an interval.  */
  if (! (position == i->position || eobp))
850
    {
851 852 853
      Lisp_Object tail;
      Lisp_Object front, rear;

854 855 856 857 858 859 860 861 862 863 864
      tail = i->plist;

      /* Properties font-sticky and rear-nonsticky override
         Vtext_property_default_nonsticky.  So, if they are t, we can
         skip one by one checking of properties.  */
      rear = textget (i->plist, Qrear_nonsticky);
      if (! CONSP (rear) && ! NILP (rear))
	{
	  /* All properties are nonsticky.  We split the interval.  */
	  goto check_done;
	}
865
      front = textget (i->plist, Qfront_sticky);
866 867 868 869 870 871
      if (! CONSP (front) && ! NILP (front))
	{
	  /* All properties are sticky.  We don't split the interval.  */
	  tail = Qnil;
	  goto check_done;
	}
872

873 874 875
      /* Does any actual property pose an actual problem?  We break
         the loop if we find a nonsticky property.  */
      for (; CONSP (tail); tail = Fcdr (XCDR (tail)))
876
	{
877
	  Lisp_Object prop, tmp;
878
	  prop = XCAR (tail);
879

880
	  /* Is this particular property front-sticky?  */