1 /* Code for doing intervals.
2 Copyright (C) 1993 Free Software Foundation, Inc.
4 This file is part of GNU Emacs.
6 GNU Emacs is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Emacs is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Emacs; see the file COPYING. If not, write to
18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
23 Have to ensure that we can't put symbol nil on a plist, or some
24 functions may work incorrectly.
26 An idea: Have the owner of the tree keep count of splits and/or
27 insertion lengths (in intervals), and balance after every N.
29 Need to call *_left_hook when buffer is killed.
31 Scan for zero-length, or 0-length to see notes about handling
32 zero length interval-markers.
34 There are comments around about freeing intervals. It might be
35 faster to explicitly free them (put them on the free list) than
43 #include "intervals.h"
46 /* The rest of the file is within this conditional. */
47 #ifdef USE_TEXT_PROPERTIES
49 /* Factor for weight-balancing interval trees. */
50 Lisp_Object interval_balance_threshold
;
52 /* Utility functions for intervals. */
55 /* Create the root interval of some object, a buffer or string. */
58 create_root_interval (parent
)
61 INTERVAL
new = make_interval ();
63 if (XTYPE (parent
) == Lisp_Buffer
)
65 new->total_length
= (BUF_Z (XBUFFER (parent
))
66 - BUF_BEG (XBUFFER (parent
)));
67 XBUFFER (parent
)->intervals
= new;
69 else if (XTYPE (parent
) == Lisp_String
)
71 new->total_length
= XSTRING (parent
)->size
;
72 XSTRING (parent
)->intervals
= new;
75 new->parent
= (INTERVAL
) parent
;
81 /* Make the interval TARGET have exactly the properties of SOURCE */
84 copy_properties (source
, target
)
85 register INTERVAL source
, target
;
87 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
90 COPY_INTERVAL_CACHE (source
, target
);
91 target
->plist
= Fcopy_sequence (source
->plist
);
94 /* Merge the properties of interval SOURCE into the properties
95 of interval TARGET. That is to say, each property in SOURCE
96 is added to TARGET if TARGET has no such property as yet. */
99 merge_properties (source
, target
)
100 register INTERVAL source
, target
;
102 register Lisp_Object o
, sym
, val
;
104 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
107 MERGE_INTERVAL_CACHE (source
, target
);
110 while (! EQ (o
, Qnil
))
113 val
= Fmemq (sym
, target
->plist
);
119 target
->plist
= Fcons (sym
, Fcons (val
, target
->plist
));
127 /* Return 1 if the two intervals have the same properties,
131 intervals_equal (i0
, i1
)
134 register Lisp_Object i0_cdr
, i0_sym
, i1_val
;
137 if (DEFAULT_INTERVAL_P (i0
) && DEFAULT_INTERVAL_P (i1
))
140 if (DEFAULT_INTERVAL_P (i0
) || DEFAULT_INTERVAL_P (i1
))
143 i1_len
= XFASTINT (Flength (i1
->plist
));
144 if (i1_len
& 0x1) /* Paranoia -- plists are always even */
148 while (!NILP (i0_cdr
))
150 /* Lengths of the two plists were unequal. */
154 i0_sym
= Fcar (i0_cdr
);
155 i1_val
= Fmemq (i0_sym
, i1
->plist
);
157 /* i0 has something i1 doesn't. */
158 if (EQ (i1_val
, Qnil
))
161 /* i0 and i1 both have sym, but it has different values in each. */
162 i0_cdr
= Fcdr (i0_cdr
);
163 if (! EQ (Fcar (Fcdr (i1_val
)), Fcar (i0_cdr
)))
166 i0_cdr
= Fcdr (i0_cdr
);
170 /* Lengths of the two plists were unequal. */
179 static int zero_length
;
181 /* Traverse an interval tree TREE, performing FUNCTION on each node.
182 Pass FUNCTION two args: an interval, and ARG. */
185 traverse_intervals (tree
, position
, depth
, function
, arg
)
188 void (* function
) ();
191 if (NULL_INTERVAL_P (tree
))
194 traverse_intervals (tree
->left
, position
, depth
+ 1, function
, arg
);
195 position
+= LEFT_TOTAL_LENGTH (tree
);
196 tree
->position
= position
;
197 (*function
) (tree
, arg
);
198 position
+= LENGTH (tree
);
199 traverse_intervals (tree
->right
, position
, depth
+ 1, function
, arg
);
203 /* These functions are temporary, for debugging purposes only. */
205 INTERVAL search_interval
, found_interval
;
208 check_for_interval (i
)
211 if (i
== search_interval
)
219 search_for_interval (i
, tree
)
220 register INTERVAL i
, tree
;
224 found_interval
= NULL_INTERVAL
;
225 traverse_intervals (tree
, 1, 0, &check_for_interval
, Qnil
);
226 return found_interval
;
230 inc_interval_count (i
)
247 traverse_intervals (i
, 1, 0, &inc_interval_count
, Qnil
);
253 root_interval (interval
)
256 register INTERVAL i
= interval
;
258 while (! ROOT_INTERVAL_P (i
))
265 /* Assuming that a left child exists, perform the following operation:
275 rotate_right (interval
)
279 INTERVAL B
= interval
->left
;
280 int len
= LENGTH (interval
);
282 /* Deal with any Parent of A; make it point to B. */
283 if (! ROOT_INTERVAL_P (interval
))
284 if (AM_LEFT_CHILD (interval
))
285 interval
->parent
->left
= interval
->left
;
287 interval
->parent
->right
= interval
->left
;
288 interval
->left
->parent
= interval
->parent
;
290 /* B gets the same length as A, since it get A's position in the tree. */
291 interval
->left
->total_length
= interval
->total_length
;
293 /* B becomes the parent of A. */
294 i
= interval
->left
->right
;
295 interval
->left
->right
= interval
;
296 interval
->parent
= interval
->left
;
298 /* A gets c as left child. */
300 if (! NULL_INTERVAL_P (i
))
301 i
->parent
= interval
;
302 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
303 + RIGHT_TOTAL_LENGTH (interval
));
308 /* Assuming that a right child exists, perform the following operation:
318 rotate_left (interval
)
322 INTERVAL B
= interval
->right
;
323 int len
= LENGTH (interval
);
325 /* Deal with the parent of A. */
326 if (! ROOT_INTERVAL_P (interval
))
327 if (AM_LEFT_CHILD (interval
))
328 interval
->parent
->left
= interval
->right
;
330 interval
->parent
->right
= interval
->right
;
331 interval
->right
->parent
= interval
->parent
;
333 /* B must have the same total length of A. */
334 interval
->right
->total_length
= interval
->total_length
;
336 /* Make B the parent of A */
337 i
= interval
->right
->left
;
338 interval
->right
->left
= interval
;
339 interval
->parent
= interval
->right
;
341 /* Make A point to c */
343 if (! NULL_INTERVAL_P (i
))
344 i
->parent
= interval
;
345 interval
->total_length
= (len
+ LEFT_TOTAL_LENGTH (interval
)
346 + RIGHT_TOTAL_LENGTH (interval
));
351 /* Split INTERVAL into two pieces, starting the second piece at
352 character position OFFSET (counting from 0), relative to INTERVAL.
353 INTERVAL becomes the left-hand piece, and the right-hand piece
354 (second, lexicographically) is returned.
356 The size and position fields of the two intervals are set based upon
357 those of the original interval. The property list of the new interval
358 is reset, thus it is up to the caller to do the right thing with the
361 Note that this does not change the position of INTERVAL; if it is a root,
362 it is still a root after this operation. */
365 split_interval_right (interval
, offset
)
369 INTERVAL
new = make_interval ();
370 int position
= interval
->position
;
371 int new_length
= LENGTH (interval
) - offset
;
373 new->position
= position
+ offset
;
374 new->parent
= interval
;
376 if (LEAF_INTERVAL_P (interval
) || NULL_RIGHT_CHILD (interval
))
378 interval
->right
= new;
379 new->total_length
= new_length
;
384 /* Insert the new node between INTERVAL and its right child. */
385 new->right
= interval
->right
;
386 interval
->right
->parent
= new;
387 interval
->right
= new;
389 new->total_length
= new_length
+ new->right
->total_length
;
394 /* Split INTERVAL into two pieces, starting the second piece at
395 character position OFFSET (counting from 0), relative to INTERVAL.
396 INTERVAL becomes the right-hand piece, and the left-hand piece
397 (first, lexicographically) is returned.
399 The size and position fields of the two intervals are set based upon
400 those of the original interval. The property list of the new interval
401 is reset, thus it is up to the caller to do the right thing with the
404 Note that this does not change the position of INTERVAL; if it is a root,
405 it is still a root after this operation. */
408 split_interval_left (interval
, offset
)
412 INTERVAL
new = make_interval ();
413 int position
= interval
->position
;
414 int new_length
= offset
;
416 new->position
= interval
->position
;
417 interval
->position
= interval
->position
+ offset
;
418 new->parent
= interval
;
420 if (NULL_LEFT_CHILD (interval
))
422 interval
->left
= new;
423 new->total_length
= new_length
;
428 /* Insert the new node between INTERVAL and its left child. */
429 new->left
= interval
->left
;
430 new->left
->parent
= new;
431 interval
->left
= new;
432 new->total_length
= new_length
+ LEFT_TOTAL_LENGTH (new);
437 /* Find the interval containing text position POSITION in the text
438 represented by the interval tree TREE. POSITION is a buffer
439 position; the earliest position is 1. If POSITION is at the end of
440 the buffer, return the interval containing the last character.
442 The `position' field, which is a cache of an interval's position,
443 is updated in the interval found. Other functions (e.g., next_interval)
444 will update this cache based on the result of find_interval. */
447 find_interval (tree
, position
)
448 register INTERVAL tree
;
449 register int position
;
451 /* The distance from the left edge of the subtree at TREE
453 register int relative_position
= position
- BEG
;
455 if (NULL_INTERVAL_P (tree
))
456 return NULL_INTERVAL
;
458 if (relative_position
> TOTAL_LENGTH (tree
))
459 abort (); /* Paranoia */
463 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
467 else if (! NULL_RIGHT_CHILD (tree
)
468 && relative_position
>= (TOTAL_LENGTH (tree
)
469 - RIGHT_TOTAL_LENGTH (tree
)))
471 relative_position
-= (TOTAL_LENGTH (tree
)
472 - RIGHT_TOTAL_LENGTH (tree
));
478 (position
- relative_position
/* the left edge of *tree */
479 + LEFT_TOTAL_LENGTH (tree
)); /* the left edge of this interval */
486 /* Find the succeeding interval (lexicographically) to INTERVAL.
487 Sets the `position' field based on that of INTERVAL (see
491 next_interval (interval
)
492 register INTERVAL interval
;
494 register INTERVAL i
= interval
;
495 register int next_position
;
497 if (NULL_INTERVAL_P (i
))
498 return NULL_INTERVAL
;
499 next_position
= interval
->position
+ LENGTH (interval
);
501 if (! NULL_RIGHT_CHILD (i
))
504 while (! NULL_LEFT_CHILD (i
))
507 i
->position
= next_position
;
511 while (! NULL_PARENT (i
))
513 if (AM_LEFT_CHILD (i
))
516 i
->position
= next_position
;
523 return NULL_INTERVAL
;
526 /* Find the preceding interval (lexicographically) to INTERVAL.
527 Sets the `position' field based on that of INTERVAL (see
531 previous_interval (interval
)
532 register INTERVAL interval
;
535 register position_of_previous
;
537 if (NULL_INTERVAL_P (interval
))
538 return NULL_INTERVAL
;
540 if (! NULL_LEFT_CHILD (interval
))
543 while (! NULL_RIGHT_CHILD (i
))
546 i
->position
= interval
->position
- LENGTH (i
);
551 while (! NULL_PARENT (i
))
553 if (AM_RIGHT_CHILD (i
))
557 i
->position
= interval
->position
- LENGTH (i
);
563 return NULL_INTERVAL
;
567 /* Traverse a path down the interval tree TREE to the interval
568 containing POSITION, adjusting all nodes on the path for
569 an addition of LENGTH characters. Insertion between two intervals
570 (i.e., point == i->position, where i is second interval) means
571 text goes into second interval.
573 Modifications are needed to handle the hungry bits -- after simply
574 finding the interval at position (don't add length going down),
575 if it's the beginning of the interval, get the previous interval
576 and check the hugry bits of both. Then add the length going back up
580 adjust_intervals_for_insertion (tree
, position
, length
)
582 int position
, length
;
584 register int relative_position
;
585 register INTERVAL
this;
587 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
590 /* If inserting at point-max of a buffer, that position
591 will be out of range */
592 if (position
> TOTAL_LENGTH (tree
))
593 position
= TOTAL_LENGTH (tree
);
594 relative_position
= position
;
599 if (relative_position
<= LEFT_TOTAL_LENGTH (this))
601 this->total_length
+= length
;
604 else if (relative_position
> (TOTAL_LENGTH (this)
605 - RIGHT_TOTAL_LENGTH (this)))
607 relative_position
-= (TOTAL_LENGTH (this)
608 - RIGHT_TOTAL_LENGTH (this));
609 this->total_length
+= length
;
614 /* If we are to use zero-length intervals as buffer pointers,
615 then this code will have to change. */
616 this->total_length
+= length
;
617 this->position
= LEFT_TOTAL_LENGTH (this)
618 + position
- relative_position
+ 1;
625 /* Effect an adjustment corresponding to the addition of LENGTH characters
626 of text. Do this by finding the interval containing POSITION in the
627 interval tree TREE, and then adjusting all of it's ancestors by adding
630 If POSITION is the first character of an interval, meaning that point
631 is actually between the two intervals, make the new text belong to
632 the interval which is "sticky".
634 If both intervals are "sticky", then make them belong to the left-most
635 interval. Another possibility would be to create a new interval for
636 this text, and make it have the merged properties of both ends. */
639 adjust_intervals_for_insertion (tree
, position
, length
)
641 int position
, length
;
644 register INTERVAL temp
;
647 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
650 /* If inserting at point-max of a buffer, that position will be out
651 of range. Remember that buffer positions are 1-based. */
652 if (position
>= BEG
+ TOTAL_LENGTH (tree
)){
653 position
= BEG
+ TOTAL_LENGTH (tree
);
657 i
= find_interval (tree
, position
);
659 /* If in middle of an interval which is not sticky either way,
660 we must not just give its properties to the insertion.
661 So split this interval at the insertion point. */
662 if (! (position
== i
->position
|| eobp
)
663 && END_NONSTICKY_P (i
)
664 && ! FRONT_STICKY_P (i
))
666 temp
= split_interval_right (i
, position
- i
->position
);
667 copy_properties (i
, temp
);
671 /* If we are positioned between intervals, check the stickiness of
672 both of them. We have to do this too, if we are at BEG or Z. */
673 if (position
== i
->position
|| eobp
)
675 register INTERVAL prev
;
685 prev
= previous_interval (i
);
687 /* Even if we are positioned between intervals, we default
688 to the left one if it exists. We extend it now and split
689 off a part later, if stickyness demands it. */
690 for (temp
= prev
? prev
: i
; ! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
691 temp
->total_length
+= length
;
693 /* If at least one interval has sticky properties,
694 we check the stickyness property by property. */
695 if (END_NONSTICKY_P (prev
) || FRONT_STICKY_P (i
))
697 Lisp_Object pleft
= NULL_INTERVAL_P (prev
) ? Qnil
: prev
->plist
;
698 Lisp_Object pright
= NULL_INTERVAL_P (i
) ? Qnil
: i
->plist
;
699 struct interval newi
;
701 newi
.plist
= merge_properties_sticky (pleft
, pright
);
703 if(! prev
) /* i.e. position == BEG */
705 if (! intervals_equal (i
, &newi
))
707 i
= split_interval_left (i
, length
);
708 i
->plist
= newi
.plist
;
711 else if (! intervals_equal (prev
, &newi
))
713 prev
= split_interval_right (prev
,
714 position
- prev
->position
);
715 prev
->plist
= newi
.plist
;
716 if (! NULL_INTERVAL_P (i
)
717 && intervals_equal (prev
, i
))
718 merge_interval_right (prev
);
721 /* We will need to update the cache here later. */
723 else if (! prev
&& ! NILP (i
->plist
))
725 /* Just split off a new interval at the left.
726 Since I wasn't front-sticky, the empty plist is ok. */
727 i
= split_interval_left (i
, length
);
731 /* Otherwise just extend the interval. */
734 for (temp
= i
; ! NULL_INTERVAL_P (temp
); temp
= temp
->parent
)
735 temp
->total_length
+= length
;
742 merge_properties_sticky (pleft
, pright
)
743 Lisp_Object pleft
, pright
;
745 register Lisp_Object props
= Qnil
, front
= Qnil
, rear
= Qnil
;
747 Lisp_Object lfront
= textget (pleft
, Qfront_sticky
);
748 Lisp_Object lrear
= textget (pleft
, Qrear_nonsticky
);
749 Lisp_Object rfront
= textget (pright
, Qfront_sticky
);
750 Lisp_Object rrear
= textget (pright
, Qrear_nonsticky
);
752 register Lisp_Object tail1
, tail2
, sym
;
754 /* Go through each element of PLEFT. */
755 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
759 /* Sticky properties get special treatment. */
760 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
763 if (CONSP (lrear
) ? NILP (Fmemq (sym
, lrear
)) : NILP (lrear
))
765 /* rear-sticky is dominant, we needn't search in PRIGHT. */
767 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail1
)), props
));
768 if ((CONSP (lfront
) || NILP (lfront
))
769 && ! NILP (Fmemq (sym
, lfront
)))
770 front
= Fcons (sym
, front
);
774 /* Go through PRIGHT, looking for sym. */
775 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
776 if (EQ (sym
, Fcar (tail2
)))
780 ? ! NILP (Fmemq (sym
, rfront
)) : ! NILP (rfront
))
782 /* Nonsticky at the left and sticky at the right,
783 so take the right one. */
784 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
785 front
= Fcons (sym
, front
);
786 if ((CONSP (rrear
) || NILP (rrear
))
787 && ! NILP (Fmemq (sym
, rrear
)))
788 rear
= Fcons (sym
, rear
);
794 /* Now let's see what to keep from PRIGHT. */
795 for (tail2
= pright
; ! NILP (tail2
); tail2
= Fcdr (Fcdr (tail2
)))
799 /* Sticky properties get special treatment. */
800 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
803 /* If it ain't sticky, we don't take it. */
805 ? NILP (Fmemq (sym
, rfront
)) : NILP (rfront
))
808 /* If sym is in PLEFT we already got it. */
809 for (tail1
= pleft
; ! NILP (tail1
); tail1
= Fcdr (Fcdr (tail1
)))
810 if (EQ (sym
, Fcar (tail1
)))
815 props
= Fcons (sym
, Fcons (Fcar (Fcdr (tail2
)), props
));
816 front
= Fcons (sym
, front
);
817 if ((CONSP (rrear
) || NILP (rrear
))
818 && ! NILP (Fmemq (sym
, rrear
)))
819 rear
= Fcons (sym
, rear
);
823 props
= Fcons (Qfront_sticky
, Fcons (front
, props
));
825 props
= Fcons (Qrear_nonsticky
, Fcons (rear
, props
));
831 /* Delete an node I from its interval tree by merging its subtrees
832 into one subtree which is then returned. Caller is responsible for
833 storing the resulting subtree into its parent. */
839 register INTERVAL migrate
, this;
840 register int migrate_amt
;
842 if (NULL_INTERVAL_P (i
->left
))
844 if (NULL_INTERVAL_P (i
->right
))
848 migrate_amt
= i
->left
->total_length
;
850 this->total_length
+= migrate_amt
;
851 while (! NULL_INTERVAL_P (this->left
))
854 this->total_length
+= migrate_amt
;
856 this->left
= migrate
;
857 migrate
->parent
= this;
862 /* Delete interval I from its tree by calling `delete_node'
863 and properly connecting the resultant subtree.
865 I is presumed to be empty; that is, no adjustments are made
866 for the length of I. */
872 register INTERVAL parent
;
873 int amt
= LENGTH (i
);
875 if (amt
> 0) /* Only used on zero-length intervals now. */
878 if (ROOT_INTERVAL_P (i
))
880 Lisp_Object owner
= (Lisp_Object
) i
->parent
;
881 parent
= delete_node (i
);
882 if (! NULL_INTERVAL_P (parent
))
883 parent
->parent
= (INTERVAL
) owner
;
885 if (XTYPE (owner
) == Lisp_Buffer
)
886 XBUFFER (owner
)->intervals
= parent
;
887 else if (XTYPE (owner
) == Lisp_String
)
888 XSTRING (owner
)->intervals
= parent
;
896 if (AM_LEFT_CHILD (i
))
898 parent
->left
= delete_node (i
);
899 if (! NULL_INTERVAL_P (parent
->left
))
900 parent
->left
->parent
= parent
;
904 parent
->right
= delete_node (i
);
905 if (! NULL_INTERVAL_P (parent
->right
))
906 parent
->right
->parent
= parent
;
910 /* Find the interval in TREE corresponding to the relative position
911 FROM and delete as much as possible of AMOUNT from that interval.
912 Return the amount actually deleted, and if the interval was
913 zeroed-out, delete that interval node from the tree.
915 Note that FROM is actually origin zero, aka relative to the
916 leftmost edge of tree. This is appropriate since we call ourselves
917 recursively on subtrees.
919 Do this by recursing down TREE to the interval in question, and
920 deleting the appropriate amount of text. */
923 interval_deletion_adjustment (tree
, from
, amount
)
924 register INTERVAL tree
;
925 register int from
, amount
;
927 register int relative_position
= from
;
929 if (NULL_INTERVAL_P (tree
))
933 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
935 int subtract
= interval_deletion_adjustment (tree
->left
,
938 tree
->total_length
-= subtract
;
942 else if (relative_position
>= (TOTAL_LENGTH (tree
)
943 - RIGHT_TOTAL_LENGTH (tree
)))
947 relative_position
-= (tree
->total_length
948 - RIGHT_TOTAL_LENGTH (tree
));
949 subtract
= interval_deletion_adjustment (tree
->right
,
952 tree
->total_length
-= subtract
;
955 /* Here -- this node. */
958 /* How much can we delete from this interval? */
959 int my_amount
= ((tree
->total_length
960 - RIGHT_TOTAL_LENGTH (tree
))
961 - relative_position
);
963 if (amount
> my_amount
)
966 tree
->total_length
-= amount
;
967 if (LENGTH (tree
) == 0)
968 delete_interval (tree
);
973 /* Never reach here. */
976 /* Effect the adjustments necessary to the interval tree of BUFFER to
977 correspond to the deletion of LENGTH characters from that buffer
978 text. The deletion is effected at position START (which is a
979 buffer position, i.e. origin 1). */
982 adjust_intervals_for_deletion (buffer
, start
, length
)
983 struct buffer
*buffer
;
986 register int left_to_delete
= length
;
987 register INTERVAL tree
= buffer
->intervals
;
988 register int deleted
;
990 if (NULL_INTERVAL_P (tree
))
993 if (start
> BEG
+ TOTAL_LENGTH (tree
)
994 || start
+ length
> BEG
+ TOTAL_LENGTH (tree
))
997 if (length
== TOTAL_LENGTH (tree
))
999 buffer
->intervals
= NULL_INTERVAL
;
1003 if (ONLY_INTERVAL_P (tree
))
1005 tree
->total_length
-= length
;
1009 if (start
> BEG
+ TOTAL_LENGTH (tree
))
1010 start
= BEG
+ TOTAL_LENGTH (tree
);
1011 while (left_to_delete
> 0)
1013 left_to_delete
-= interval_deletion_adjustment (tree
, start
- 1,
1015 tree
= buffer
->intervals
;
1016 if (left_to_delete
== tree
->total_length
)
1018 buffer
->intervals
= NULL_INTERVAL
;
1024 /* Make the adjustments necessary to the interval tree of BUFFER to
1025 represent an addition or deletion of LENGTH characters starting
1026 at position START. Addition or deletion is indicated by the sign
1030 offset_intervals (buffer
, start
, length
)
1031 struct buffer
*buffer
;
1034 if (NULL_INTERVAL_P (buffer
->intervals
) || length
== 0)
1038 adjust_intervals_for_insertion (buffer
->intervals
, start
, length
);
1040 adjust_intervals_for_deletion (buffer
, start
, -length
);
1043 /* Merge interval I with its lexicographic successor. The resulting
1044 interval is returned, and has the properties of the original
1045 successor. The properties of I are lost. I is removed from the
1049 The caller must verify that this is not the last (rightmost)
1053 merge_interval_right (i
)
1054 register INTERVAL i
;
1056 register int absorb
= LENGTH (i
);
1057 register INTERVAL successor
;
1059 /* Zero out this interval. */
1060 i
->total_length
-= absorb
;
1062 /* Find the succeeding interval. */
1063 if (! NULL_RIGHT_CHILD (i
)) /* It's below us. Add absorb
1066 successor
= i
->right
;
1067 while (! NULL_LEFT_CHILD (successor
))
1069 successor
->total_length
+= absorb
;
1070 successor
= successor
->left
;
1073 successor
->total_length
+= absorb
;
1074 delete_interval (i
);
1079 while (! NULL_PARENT (successor
)) /* It's above us. Subtract as
1082 if (AM_LEFT_CHILD (successor
))
1084 successor
= successor
->parent
;
1085 delete_interval (i
);
1089 successor
= successor
->parent
;
1090 successor
->total_length
-= absorb
;
1093 /* This must be the rightmost or last interval and cannot
1094 be merged right. The caller should have known. */
1098 /* Merge interval I with its lexicographic predecessor. The resulting
1099 interval is returned, and has the properties of the original predecessor.
1100 The properties of I are lost. Interval node I is removed from the tree.
1103 The caller must verify that this is not the first (leftmost) interval. */
1106 merge_interval_left (i
)
1107 register INTERVAL i
;
1109 register int absorb
= LENGTH (i
);
1110 register INTERVAL predecessor
;
1112 /* Zero out this interval. */
1113 i
->total_length
-= absorb
;
1115 /* Find the preceding interval. */
1116 if (! NULL_LEFT_CHILD (i
)) /* It's below us. Go down,
1117 adding ABSORB as we go. */
1119 predecessor
= i
->left
;
1120 while (! NULL_RIGHT_CHILD (predecessor
))
1122 predecessor
->total_length
+= absorb
;
1123 predecessor
= predecessor
->right
;
1126 predecessor
->total_length
+= absorb
;
1127 delete_interval (i
);
1132 while (! NULL_PARENT (predecessor
)) /* It's above us. Go up,
1133 subtracting ABSORB. */
1135 if (AM_RIGHT_CHILD (predecessor
))
1137 predecessor
= predecessor
->parent
;
1138 delete_interval (i
);
1142 predecessor
= predecessor
->parent
;
1143 predecessor
->total_length
-= absorb
;
1146 /* This must be the leftmost or first interval and cannot
1147 be merged left. The caller should have known. */
1151 /* Make an exact copy of interval tree SOURCE which descends from
1152 PARENT. This is done by recursing through SOURCE, copying
1153 the current interval and its properties, and then adjusting
1154 the pointers of the copy. */
1157 reproduce_tree (source
, parent
)
1158 INTERVAL source
, parent
;
1160 register INTERVAL t
= make_interval ();
1162 bcopy (source
, t
, INTERVAL_SIZE
);
1163 copy_properties (source
, t
);
1165 if (! NULL_LEFT_CHILD (source
))
1166 t
->left
= reproduce_tree (source
->left
, t
);
1167 if (! NULL_RIGHT_CHILD (source
))
1168 t
->right
= reproduce_tree (source
->right
, t
);
1174 /* Nobody calls this. Perhaps it's a vestige of an earlier design. */
1176 /* Make a new interval of length LENGTH starting at START in the
1177 group of intervals INTERVALS, which is actually an interval tree.
1178 Returns the new interval.
1180 Generate an error if the new positions would overlap an existing
1184 make_new_interval (intervals
, start
, length
)
1190 slot
= find_interval (intervals
, start
);
1191 if (start
+ length
> slot
->position
+ LENGTH (slot
))
1192 error ("Interval would overlap");
1194 if (start
== slot
->position
&& length
== LENGTH (slot
))
1197 if (slot
->position
== start
)
1199 /* New right node. */
1200 split_interval_right (slot
, length
);
1204 if (slot
->position
+ LENGTH (slot
) == start
+ length
)
1206 /* New left node. */
1207 split_interval_left (slot
, LENGTH (slot
) - length
);
1211 /* Convert interval SLOT into three intervals. */
1212 split_interval_left (slot
, start
- slot
->position
);
1213 split_interval_right (slot
, length
);
1218 /* Insert the intervals of SOURCE into BUFFER at POSITION.
1220 This is used in insdel.c when inserting Lisp_Strings into the
1221 buffer. The text corresponding to SOURCE is already in the buffer
1222 when this is called. The intervals of new tree are a copy of those
1223 belonging to the string being inserted; intervals are never
1226 If the inserted text had no intervals associated, this function
1227 simply returns -- offset_intervals should handle placing the
1228 text in the correct interval, depending on the sticky bits.
1230 If the inserted text had properties (intervals), then there are two
1231 cases -- either insertion happened in the middle of some interval,
1232 or between two intervals.
1234 If the text goes into the middle of an interval, then new
1235 intervals are created in the middle with only the properties of
1236 the new text, *unless* the macro MERGE_INSERTIONS is true, in
1237 which case the new text has the union of its properties and those
1238 of the text into which it was inserted.
1240 If the text goes between two intervals, then if neither interval
1241 had its appropriate sticky property set (front_sticky, rear_sticky),
1242 the new text has only its properties. If one of the sticky properties
1243 is set, then the new text "sticks" to that region and its properties
1244 depend on merging as above. If both the preceding and succeeding
1245 intervals to the new text are "sticky", then the new text retains
1246 only its properties, as if neither sticky property were set. Perhaps
1247 we should consider merging all three sets of properties onto the new
1251 graft_intervals_into_buffer (source
, position
, buffer
)
1254 struct buffer
*buffer
;
1256 register INTERVAL under
, over
, this, prev
;
1257 register INTERVAL tree
= buffer
->intervals
;
1260 /* If the new text has no properties, it becomes part of whatever
1261 interval it was inserted into. */
1262 if (NULL_INTERVAL_P (source
))
1265 if (NULL_INTERVAL_P (tree
))
1267 /* The inserted text constitutes the whole buffer, so
1268 simply copy over the interval structure. */
1269 if ((BUF_Z (buffer
) - BUF_BEG (buffer
)) == TOTAL_LENGTH (source
))
1272 XSET (buf
, Lisp_Buffer
, buffer
);
1273 buffer
->intervals
= reproduce_tree (source
, buf
);
1274 /* Explicitly free the old tree here. */
1279 /* Create an interval tree in which to place a copy
1280 of the intervals of the inserted string. */
1283 XSET (buf
, Lisp_Buffer
, buffer
);
1284 tree
= create_root_interval (buf
);
1288 if (TOTAL_LENGTH (tree
) == TOTAL_LENGTH (source
))
1289 /* If the buffer contains only the new string, but
1290 there was already some interval tree there, then it may be
1291 some zero length intervals. Eventually, do something clever
1292 about inserting properly. For now, just waste the old intervals. */
1294 buffer
->intervals
= reproduce_tree (source
, tree
->parent
);
1295 /* Explicitly free the old tree here. */
1300 /* Paranoia -- the text has already been added, so this buffer
1301 should be of non-zero length. */
1302 if (TOTAL_LENGTH (tree
) == 0)
1305 this = under
= find_interval (tree
, position
);
1306 if (NULL_INTERVAL_P (under
)) /* Paranoia */
1308 over
= find_interval (source
, 1);
1310 /* Here for insertion in the middle of an interval.
1311 Split off an equivalent interval to the right,
1312 then don't bother with it any more. */
1314 if (position
> under
->position
)
1316 INTERVAL end_unchanged
1317 = split_interval_left (this, position
- under
->position
);
1318 copy_properties (under
, end_unchanged
);
1319 under
->position
= position
;
1325 prev
= previous_interval (under
);
1326 if (prev
&& !END_NONSTICKY_P (prev
))
1330 /* Insertion is now at beginning of UNDER. */
1332 /* The inserted text "sticks" to the interval `under',
1333 which means it gets those properties.
1334 The properties of under are the result of
1335 adjust_intervals_for_insertion, so stickyness has
1336 already been taken care of. */
1338 while (! NULL_INTERVAL_P (over
))
1340 if (LENGTH (over
) + 1 < LENGTH (under
))
1342 this = split_interval_left (under
, LENGTH (over
));
1343 copy_properties (under
, this);
1347 copy_properties (over
, this);
1348 if (MERGE_INSERTIONS (this))
1349 merge_properties (over
, this);
1351 copy_properties (over
, this);
1352 over
= next_interval (over
);
1355 buffer
->intervals
= balance_intervals (buffer
->intervals
);
1359 /* Get the value of property PROP from PLIST,
1360 which is the plist of an interval.
1361 We check for direct properties and for categories with property PROP. */
1364 textget (plist
, prop
)
1366 register Lisp_Object prop
;
1368 register Lisp_Object tail
, fallback
;
1371 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1373 register Lisp_Object tem
;
1376 return Fcar (Fcdr (tail
));
1377 if (EQ (tem
, Qcategory
))
1378 fallback
= Fget (Fcar (Fcdr (tail
)), prop
);
1384 /* Get the value of property PROP from PLIST,
1385 which is the plist of an interval.
1386 We check for direct properties only! */
1389 textget_direct (plist
, prop
)
1391 register Lisp_Object prop
;
1393 register Lisp_Object tail
;
1395 for (tail
= plist
; !NILP (tail
); tail
= Fcdr (Fcdr (tail
)))
1397 if (EQ (prop
, Fcar (tail
)))
1398 return Fcar (Fcdr (tail
));
1404 /* Set point in BUFFER to POSITION. If the target position is
1405 before an invisible character which is not displayed with a special glyph,
1406 move back to an ok place to display. */
1409 set_point (position
, buffer
)
1410 register int position
;
1411 register struct buffer
*buffer
;
1413 register INTERVAL to
, from
, toprev
, fromprev
, target
;
1415 register Lisp_Object obj
;
1416 int backwards
= (position
< BUF_PT (buffer
)) ? 1 : 0;
1417 int old_position
= buffer
->text
.pt
;
1419 if (position
== buffer
->text
.pt
)
1422 /* Check this now, before checking if the buffer has any intervals.
1423 That way, we can catch conditions which break this sanity check
1424 whether or not there are intervals in the buffer. */
1425 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1428 if (NULL_INTERVAL_P (buffer
->intervals
))
1430 buffer
->text
.pt
= position
;
1434 /* Set TO to the interval containing the char after POSITION,
1435 and TOPREV to the interval containing the char before POSITION.
1436 Either one may be null. They may be equal. */
1437 to
= find_interval (buffer
->intervals
, position
);
1438 if (position
== BUF_BEGV (buffer
))
1440 else if (to
->position
== position
)
1441 toprev
= previous_interval (to
);
1445 buffer_point
= (BUF_PT (buffer
) == BUF_ZV (buffer
)
1446 ? BUF_ZV (buffer
) - 1
1449 /* Set FROM to the interval containing the char after PT,
1450 and FROMPREV to the interval containing the char before PT.
1451 Either one may be null. They may be equal. */
1452 /* We could cache this and save time. */
1453 from
= find_interval (buffer
->intervals
, buffer_point
);
1454 if (buffer_point
== BUF_BEGV (buffer
))
1456 else if (from
->position
== BUF_PT (buffer
))
1457 fromprev
= previous_interval (from
);
1458 else if (buffer_point
!= BUF_PT (buffer
))
1459 fromprev
= from
, from
= 0;
1463 /* Moving within an interval. */
1464 if (to
== from
&& toprev
== fromprev
&& INTERVAL_VISIBLE_P (to
))
1466 buffer
->text
.pt
= position
;
1470 /* If the new position is before an invisible character
1471 that has an `invisible' property of value `hidden',
1472 move forward over all such. */
1473 while (! NULL_INTERVAL_P (to
)
1474 && EQ (textget (to
->plist
, Qinvisible
), Qhidden
)
1475 && ! DISPLAY_INVISIBLE_GLYPH (to
))
1478 to
= next_interval (to
);
1479 if (NULL_INTERVAL_P (to
))
1480 position
= BUF_ZV (buffer
);
1482 position
= to
->position
;
1485 buffer
->text
.pt
= position
;
1487 /* We run point-left and point-entered hooks here, iff the
1488 two intervals are not equivalent. These hooks take
1489 (old_point, new_point) as arguments. */
1490 if (NILP (Vinhibit_point_motion_hooks
)
1491 && (! intervals_equal (from
, to
)
1492 || ! intervals_equal (fromprev
, toprev
)))
1494 Lisp_Object leave_after
, leave_before
, enter_after
, enter_before
;
1497 leave_after
= textget (fromprev
->plist
, Qpoint_left
);
1501 leave_before
= textget (from
->plist
, Qpoint_left
);
1503 leave_before
= Qnil
;
1506 enter_after
= textget (toprev
->plist
, Qpoint_entered
);
1510 enter_before
= textget (to
->plist
, Qpoint_entered
);
1512 enter_before
= Qnil
;
1514 if (! EQ (leave_before
, enter_before
) && !NILP (leave_before
))
1515 call2 (leave_before
, old_position
, position
);
1516 if (! EQ (leave_after
, enter_after
) && !NILP (leave_after
))
1517 call2 (leave_after
, old_position
, position
);
1519 if (! EQ (enter_before
, leave_before
) && !NILP (enter_before
))
1520 call2 (enter_before
, old_position
, position
);
1521 if (! EQ (enter_after
, leave_after
) && !NILP (enter_after
))
1522 call2 (enter_after
, old_position
, position
);
1526 /* Set point temporarily, without checking any text properties. */
1529 temp_set_point (position
, buffer
)
1531 struct buffer
*buffer
;
1533 buffer
->text
.pt
= position
;
1536 /* Return the proper local map for position POSITION in BUFFER.
1537 Use the map specified by the local-map property, if any.
1538 Otherwise, use BUFFER's local map. */
1541 get_local_map (position
, buffer
)
1542 register int position
;
1543 register struct buffer
*buffer
;
1545 register INTERVAL interval
;
1546 Lisp_Object prop
, tem
;
1548 if (NULL_INTERVAL_P (buffer
->intervals
))
1549 return current_buffer
->keymap
;
1551 /* Perhaps we should just change `position' to the limit. */
1552 if (position
> BUF_Z (buffer
) || position
< BUF_BEG (buffer
))
1555 interval
= find_interval (buffer
->intervals
, position
);
1556 prop
= textget (interval
->plist
, Qlocal_map
);
1558 return current_buffer
->keymap
;
1560 /* Use the local map only if it is valid. */
1561 tem
= Fkeymapp (prop
);
1565 return current_buffer
->keymap
;
1568 /* Call the modification hook functions in LIST, each with START and END. */
1571 call_mod_hooks (list
, start
, end
)
1572 Lisp_Object list
, start
, end
;
1574 struct gcpro gcpro1
;
1576 while (!NILP (list
))
1578 call2 (Fcar (list
), start
, end
);
1584 /* Check for read-only intervals and signal an error if we find one.
1585 Then check for any modification hooks in the range START up to
1586 (but not including) TO. Create a list of all these hooks in
1587 lexicographic order, eliminating consecutive extra copies of the
1588 same hook. Then call those hooks in order, with START and END - 1
1592 verify_interval_modification (buf
, start
, end
)
1596 register INTERVAL intervals
= buf
->intervals
;
1597 register INTERVAL i
, prev
;
1599 register Lisp_Object prev_mod_hooks
;
1600 Lisp_Object mod_hooks
;
1601 struct gcpro gcpro1
;
1604 prev_mod_hooks
= Qnil
;
1607 if (NULL_INTERVAL_P (intervals
))
1617 /* For an insert operation, check the two chars around the position. */
1621 Lisp_Object before
, after
;
1623 /* Set I to the interval containing the char after START,
1624 and PREV to the interval containing the char before START.
1625 Either one may be null. They may be equal. */
1626 i
= find_interval (intervals
, start
);
1628 if (start
== BUF_BEGV (buf
))
1630 else if (i
->position
== start
)
1631 prev
= previous_interval (i
);
1632 else if (i
->position
< start
)
1634 if (start
== BUF_ZV (buf
))
1637 /* If Vinhibit_read_only is set and is not a list, we can
1638 skip the read_only checks. */
1639 if (NILP (Vinhibit_read_only
) || CONSP (Vinhibit_read_only
))
1641 /* If I and PREV differ we need to check for the read-only
1642 property together with its stickyness. If either I or
1643 PREV are 0, this check is all we need.
1644 We have to take special care, since read-only may be
1645 indirectly defined via the category property. */
1648 if (! NULL_INTERVAL_P (i
))
1650 after
= textget (i
->plist
, Qread_only
);
1652 /* If interval I is read-only and read-only is
1653 front-sticky, inhibit insertion.
1654 Check for read-only as well as category. */
1656 && NILP (Fmemq (after
, Vinhibit_read_only
))
1657 && (! NILP (Fmemq (Qread_only
,
1658 textget (i
->plist
, Qfront_sticky
)))
1659 || (NILP (textget_direct (i
->plist
, Qread_only
))
1660 && ! NILP (Fmemq (Qcategory
,
1663 error ("Attempt to insert within read-only text");
1667 if (! NULL_INTERVAL_P (prev
))
1669 before
= textget (prev
->plist
, Qread_only
);
1671 /* If interval PREV is read-only and read-only isn't
1672 rear-nonsticky, inhibit insertion.
1673 Check for read-only as well as category. */
1675 && NILP (Fmemq (before
, Vinhibit_read_only
))
1676 && NILP (Fmemq (Qread_only
,
1677 textget (prev
->plist
, Qrear_nonsticky
)))
1678 && (! NILP (textget_direct (prev
->plist
,Qread_only
))
1679 || NILP (Fmemq (Qcategory
,
1680 textget (prev
->plist
,
1681 Qrear_nonsticky
)))))
1682 error ("Attempt to insert within read-only text");
1687 else if (! NULL_INTERVAL_P (i
))
1688 before
= after
= textget (i
->plist
, Qread_only
);
1689 if (! NULL_INTERVAL_P (i
) && ! NULL_INTERVAL_P (prev
))
1691 /* If I and PREV differ, neither of them has a sticky
1692 read-only property. It only remains to check, whether
1693 they have a common read-only property. */
1694 if (! NILP (before
) && EQ (before
, after
))
1695 error ("Attempt to insert within read-only text");
1699 /* Run both insert hooks (just once if they're the same). */
1700 if (!NULL_INTERVAL_P (prev
))
1701 prev_mod_hooks
= textget (prev
->plist
, Qinsert_behind_hooks
);
1702 if (!NULL_INTERVAL_P (i
))
1703 mod_hooks
= textget (i
->plist
, Qinsert_in_front_hooks
);
1705 if (! NILP (prev_mod_hooks
))
1706 call_mod_hooks (prev_mod_hooks
, make_number (start
),
1709 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1710 call_mod_hooks (mod_hooks
, make_number (start
), make_number (end
));
1714 /* Loop over intervals on or next to START...END,
1715 collecting their hooks. */
1717 i
= find_interval (intervals
, start
);
1720 if (! INTERVAL_WRITABLE_P (i
))
1721 error ("Attempt to modify read-only text");
1723 mod_hooks
= textget (i
->plist
, Qmodification_hooks
);
1724 if (! NILP (mod_hooks
) && ! EQ (mod_hooks
, prev_mod_hooks
))
1726 hooks
= Fcons (mod_hooks
, hooks
);
1727 prev_mod_hooks
= mod_hooks
;
1730 i
= next_interval (i
);
1732 /* Keep going thru the interval containing the char before END. */
1733 while (! NULL_INTERVAL_P (i
) && i
->position
< end
);
1736 hooks
= Fnreverse (hooks
);
1737 while (! EQ (hooks
, Qnil
))
1739 call_mod_hooks (Fcar (hooks
), make_number (start
),
1741 hooks
= Fcdr (hooks
);
1747 /* Balance an interval node if the amount of text in its left and right
1748 subtrees differs by more than the percentage specified by
1749 `interval-balance-threshold'. */
1752 balance_an_interval (i
)
1755 register int total_children_size
= (LEFT_TOTAL_LENGTH (i
)
1756 + RIGHT_TOTAL_LENGTH (i
));
1757 register int threshold
= (XFASTINT (interval_balance_threshold
)
1758 * (total_children_size
/ 100));
1760 /* Balance within each side. */
1761 balance_intervals (i
->left
);
1762 balance_intervals (i
->right
);
1764 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1765 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1767 i
= rotate_right (i
);
1768 /* If that made it unbalanced the other way, take it back. */
1769 if (RIGHT_TOTAL_LENGTH (i
) > LEFT_TOTAL_LENGTH (i
)
1770 && (RIGHT_TOTAL_LENGTH (i
) - LEFT_TOTAL_LENGTH (i
)) > threshold
)
1771 return rotate_left (i
);
1775 if (RIGHT_TOTAL_LENGTH (i
) > LEFT_TOTAL_LENGTH (i
)
1776 && (RIGHT_TOTAL_LENGTH (i
) - LEFT_TOTAL_LENGTH (i
)) > threshold
)
1778 i
= rotate_left (i
);
1779 if (LEFT_TOTAL_LENGTH (i
) > RIGHT_TOTAL_LENGTH (i
)
1780 && (LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
)) > threshold
)
1781 return rotate_right (i
);
1788 /* Balance the interval tree TREE. Balancing is by weight
1789 (the amount of text). */
1792 balance_intervals (tree
)
1793 register INTERVAL tree
;
1795 register INTERVAL new_tree
;
1797 if (NULL_INTERVAL_P (tree
))
1798 return NULL_INTERVAL
;
1804 new_tree
= balance_an_interval (new_tree
);
1806 while (new_tree
!= tree
);
1811 /* Produce an interval tree reflecting the intervals in
1812 TREE from START to START + LENGTH. */
1815 copy_intervals (tree
, start
, length
)
1819 register INTERVAL i
, new, t
;
1820 register int got
, prevlen
;
1822 if (NULL_INTERVAL_P (tree
) || length
<= 0)
1823 return NULL_INTERVAL
;
1825 i
= find_interval (tree
, start
);
1826 if (NULL_INTERVAL_P (i
) || LENGTH (i
) == 0)
1829 /* If there is only one interval and it's the default, return nil. */
1830 if ((start
- i
->position
+ 1 + length
) < LENGTH (i
)
1831 && DEFAULT_INTERVAL_P (i
))
1832 return NULL_INTERVAL
;
1834 new = make_interval ();
1836 got
= (LENGTH (i
) - (start
- i
->position
));
1837 new->total_length
= length
;
1838 copy_properties (i
, new);
1842 while (got
< length
)
1844 i
= next_interval (i
);
1845 t
= split_interval_right (t
, prevlen
);
1846 copy_properties (i
, t
);
1847 prevlen
= LENGTH (i
);
1851 return balance_intervals (new);
1854 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
1857 copy_intervals_to_string (string
, buffer
, position
, length
)
1858 Lisp_Object string
, buffer
;
1859 int position
, length
;
1861 INTERVAL interval_copy
= copy_intervals (XBUFFER (buffer
)->intervals
,
1863 if (NULL_INTERVAL_P (interval_copy
))
1866 interval_copy
->parent
= (INTERVAL
) string
;
1867 XSTRING (string
)->intervals
= interval_copy
;
1870 #endif /* USE_TEXT_PROPERTIES */