1 /* Code for doing intervals.
2 Copyright (C) 1993-1995, 1997-1998, 2001-2011 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 3 of the License, or
9 (at your option) any later version.
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. If not, see <http://www.gnu.org/licenses/>. */
22 Have to ensure that we can't put symbol nil on a plist, or some
23 functions may work incorrectly.
25 An idea: Have the owner of the tree keep count of splits and/or
26 insertion lengths (in intervals), and balance after every N.
28 Need to call *_left_hook when buffer is killed.
30 Scan for zero-length, or 0-length to see notes about handling
31 zero length interval-markers.
33 There are comments around about freeing intervals. It might be
34 faster to explicitly free them (put them on the free list) than
44 #include "intervals.h"
50 /* Test for membership, allowing for t (actually any non-cons) to mean the
53 #define TMEM(sym, set) (CONSP (set) ? ! NILP (Fmemq (sym, set)) : ! NILP (set))
55 static Lisp_Object
merge_properties_sticky (Lisp_Object
, Lisp_Object
);
56 static INTERVAL
merge_interval_right (INTERVAL
);
57 static INTERVAL
reproduce_tree (INTERVAL
, INTERVAL
);
58 static INTERVAL
reproduce_tree_obj (INTERVAL
, Lisp_Object
);
60 /* Utility functions for intervals. */
63 /* Create the root interval of some object, a buffer or string. */
66 create_root_interval (Lisp_Object parent
)
70 CHECK_IMPURE (parent
);
72 new = make_interval ();
76 new->total_length
= (BUF_Z (XBUFFER (parent
))
77 - BUF_BEG (XBUFFER (parent
)));
78 CHECK_TOTAL_LENGTH (new);
79 BUF_INTERVALS (XBUFFER (parent
)) = new;
82 else if (STRINGP (parent
))
84 new->total_length
= SCHARS (parent
);
85 CHECK_TOTAL_LENGTH (new);
86 STRING_SET_INTERVALS (parent
, new);
90 SET_INTERVAL_OBJECT (new, parent
);
95 /* Make the interval TARGET have exactly the properties of SOURCE */
98 copy_properties (register INTERVAL source
, register INTERVAL target
)
100 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
103 COPY_INTERVAL_CACHE (source
, target
);
104 target
->plist
= Fcopy_sequence (source
->plist
);
107 /* Merge the properties of interval SOURCE into the properties
108 of interval TARGET. That is to say, each property in SOURCE
109 is added to TARGET if TARGET has no such property as yet. */
112 merge_properties (register INTERVAL source
, register INTERVAL target
)
114 register Lisp_Object o
, sym
, val
;
116 if (DEFAULT_INTERVAL_P (source
) && DEFAULT_INTERVAL_P (target
))
119 MERGE_INTERVAL_CACHE (source
, target
);
129 while (CONSP (val
) && !EQ (XCAR (val
), sym
))
140 target
->plist
= Fcons (sym
, Fcons (val
, target
->plist
));
146 /* Return 1 if the two intervals have the same properties,
150 intervals_equal (INTERVAL i0
, INTERVAL i1
)
152 register Lisp_Object i0_cdr
, i0_sym
;
153 register Lisp_Object i1_cdr
, i1_val
;
155 if (DEFAULT_INTERVAL_P (i0
) && DEFAULT_INTERVAL_P (i1
))
158 if (DEFAULT_INTERVAL_P (i0
) || DEFAULT_INTERVAL_P (i1
))
163 while (CONSP (i0_cdr
) && CONSP (i1_cdr
))
165 i0_sym
= XCAR (i0_cdr
);
166 i0_cdr
= XCDR (i0_cdr
);
168 return 0; /* abort (); */
170 while (CONSP (i1_val
) && !EQ (XCAR (i1_val
), i0_sym
))
172 i1_val
= XCDR (i1_val
);
174 return 0; /* abort (); */
175 i1_val
= XCDR (i1_val
);
178 /* i0 has something i1 doesn't. */
179 if (EQ (i1_val
, Qnil
))
182 /* i0 and i1 both have sym, but it has different values in each. */
184 || (i1_val
= XCDR (i1_val
), !CONSP (i1_val
))
185 || !EQ (XCAR (i1_val
), XCAR (i0_cdr
)))
188 i0_cdr
= XCDR (i0_cdr
);
190 i1_cdr
= XCDR (i1_cdr
);
192 return 0; /* abort (); */
193 i1_cdr
= XCDR (i1_cdr
);
196 /* Lengths of the two plists were equal. */
197 return (NILP (i0_cdr
) && NILP (i1_cdr
));
201 /* Traverse an interval tree TREE, performing FUNCTION on each node.
202 No guarantee is made about the order of traversal.
203 Pass FUNCTION two args: an interval, and ARG. */
206 traverse_intervals_noorder (INTERVAL tree
, void (*function
) (INTERVAL
, Lisp_Object
), Lisp_Object arg
)
208 /* Minimize stack usage. */
209 while (!NULL_INTERVAL_P (tree
))
211 (*function
) (tree
, arg
);
212 if (NULL_INTERVAL_P (tree
->right
))
216 traverse_intervals_noorder (tree
->left
, function
, arg
);
222 /* Traverse an interval tree TREE, performing FUNCTION on each node.
223 Pass FUNCTION two args: an interval, and ARG. */
226 traverse_intervals (INTERVAL tree
, EMACS_INT position
,
227 void (*function
) (INTERVAL
, Lisp_Object
), Lisp_Object arg
)
229 while (!NULL_INTERVAL_P (tree
))
231 traverse_intervals (tree
->left
, position
, function
, arg
);
232 position
+= LEFT_TOTAL_LENGTH (tree
);
233 tree
->position
= position
;
234 (*function
) (tree
, arg
);
235 position
+= LENGTH (tree
); tree
= tree
->right
;
243 static int zero_length
;
245 /* These functions are temporary, for debugging purposes only. */
247 INTERVAL search_interval
, found_interval
;
250 check_for_interval (INTERVAL i
)
252 if (i
== search_interval
)
260 search_for_interval (INTERVAL i
, INTERVAL tree
)
264 found_interval
= NULL_INTERVAL
;
265 traverse_intervals_noorder (tree
, &check_for_interval
, Qnil
);
266 return found_interval
;
270 inc_interval_count (INTERVAL i
)
280 count_intervals (INTERVAL i
)
285 traverse_intervals_noorder (i
, &inc_interval_count
, Qnil
);
291 root_interval (INTERVAL interval
)
293 register INTERVAL i
= interval
;
295 while (! ROOT_INTERVAL_P (i
))
296 i
= INTERVAL_PARENT (i
);
302 /* Assuming that a left child exists, perform the following operation:
311 static inline INTERVAL
312 rotate_right (INTERVAL interval
)
315 INTERVAL B
= interval
->left
;
316 EMACS_INT old_total
= interval
->total_length
;
318 /* Deal with any Parent of A; make it point to B. */
319 if (! ROOT_INTERVAL_P (interval
))
321 if (AM_LEFT_CHILD (interval
))
322 INTERVAL_PARENT (interval
)->left
= B
;
324 INTERVAL_PARENT (interval
)->right
= B
;
326 COPY_INTERVAL_PARENT (B
, interval
);
328 /* Make B the parent of A */
331 SET_INTERVAL_PARENT (interval
, B
);
333 /* Make A point to c */
335 if (! NULL_INTERVAL_P (i
))
336 SET_INTERVAL_PARENT (i
, interval
);
338 /* A's total length is decreased by the length of B and its left child. */
339 interval
->total_length
-= B
->total_length
- LEFT_TOTAL_LENGTH (interval
);
340 CHECK_TOTAL_LENGTH (interval
);
342 /* B must have the same total length of A. */
343 B
->total_length
= old_total
;
344 CHECK_TOTAL_LENGTH (B
);
349 /* Assuming that a right child exists, perform the following operation:
358 static inline INTERVAL
359 rotate_left (INTERVAL interval
)
362 INTERVAL B
= interval
->right
;
363 EMACS_INT old_total
= interval
->total_length
;
365 /* Deal with any parent of A; make it point to B. */
366 if (! ROOT_INTERVAL_P (interval
))
368 if (AM_LEFT_CHILD (interval
))
369 INTERVAL_PARENT (interval
)->left
= B
;
371 INTERVAL_PARENT (interval
)->right
= B
;
373 COPY_INTERVAL_PARENT (B
, interval
);
375 /* Make B the parent of A */
378 SET_INTERVAL_PARENT (interval
, B
);
380 /* Make A point to c */
382 if (! NULL_INTERVAL_P (i
))
383 SET_INTERVAL_PARENT (i
, interval
);
385 /* A's total length is decreased by the length of B and its right child. */
386 interval
->total_length
-= B
->total_length
- RIGHT_TOTAL_LENGTH (interval
);
387 CHECK_TOTAL_LENGTH (interval
);
389 /* B must have the same total length of A. */
390 B
->total_length
= old_total
;
391 CHECK_TOTAL_LENGTH (B
);
396 /* Balance an interval tree with the assumption that the subtrees
397 themselves are already balanced. */
400 balance_an_interval (INTERVAL i
)
402 register EMACS_INT old_diff
, new_diff
;
406 old_diff
= LEFT_TOTAL_LENGTH (i
) - RIGHT_TOTAL_LENGTH (i
);
409 /* Since the left child is longer, there must be one. */
410 new_diff
= i
->total_length
- i
->left
->total_length
411 + RIGHT_TOTAL_LENGTH (i
->left
) - LEFT_TOTAL_LENGTH (i
->left
);
412 if (eabs (new_diff
) >= old_diff
)
414 i
= rotate_right (i
);
415 balance_an_interval (i
->right
);
417 else if (old_diff
< 0)
419 /* Since the right child is longer, there must be one. */
420 new_diff
= i
->total_length
- i
->right
->total_length
421 + LEFT_TOTAL_LENGTH (i
->right
) - RIGHT_TOTAL_LENGTH (i
->right
);
422 if (eabs (new_diff
) >= -old_diff
)
425 balance_an_interval (i
->left
);
433 /* Balance INTERVAL, potentially stuffing it back into its parent
436 static inline INTERVAL
437 balance_possible_root_interval (register INTERVAL interval
)
442 if (!INTERVAL_HAS_OBJECT (interval
) && !INTERVAL_HAS_PARENT (interval
))
445 if (INTERVAL_HAS_OBJECT (interval
))
448 GET_INTERVAL_OBJECT (parent
, interval
);
450 interval
= balance_an_interval (interval
);
454 if (BUFFERP (parent
))
455 BUF_INTERVALS (XBUFFER (parent
)) = interval
;
456 else if (STRINGP (parent
))
457 STRING_SET_INTERVALS (parent
, interval
);
463 /* Balance the interval tree TREE. Balancing is by weight
464 (the amount of text). */
467 balance_intervals_internal (register INTERVAL tree
)
469 /* Balance within each side. */
471 balance_intervals_internal (tree
->left
);
473 balance_intervals_internal (tree
->right
);
474 return balance_an_interval (tree
);
477 /* Advertised interface to balance intervals. */
480 balance_intervals (INTERVAL tree
)
482 if (tree
== NULL_INTERVAL
)
483 return NULL_INTERVAL
;
485 return balance_intervals_internal (tree
);
488 /* Split INTERVAL into two pieces, starting the second piece at
489 character position OFFSET (counting from 0), relative to INTERVAL.
490 INTERVAL becomes the left-hand piece, and the right-hand piece
491 (second, lexicographically) is returned.
493 The size and position fields of the two intervals are set based upon
494 those of the original interval. The property list of the new interval
495 is reset, thus it is up to the caller to do the right thing with the
498 Note that this does not change the position of INTERVAL; if it is a root,
499 it is still a root after this operation. */
502 split_interval_right (INTERVAL interval
, EMACS_INT offset
)
504 INTERVAL
new = make_interval ();
505 EMACS_INT position
= interval
->position
;
506 EMACS_INT new_length
= LENGTH (interval
) - offset
;
508 new->position
= position
+ offset
;
509 SET_INTERVAL_PARENT (new, interval
);
511 if (NULL_RIGHT_CHILD (interval
))
513 interval
->right
= new;
514 new->total_length
= new_length
;
515 CHECK_TOTAL_LENGTH (new);
519 /* Insert the new node between INTERVAL and its right child. */
520 new->right
= interval
->right
;
521 SET_INTERVAL_PARENT (interval
->right
, new);
522 interval
->right
= new;
523 new->total_length
= new_length
+ new->right
->total_length
;
524 CHECK_TOTAL_LENGTH (new);
525 balance_an_interval (new);
528 balance_possible_root_interval (interval
);
533 /* Split INTERVAL into two pieces, starting the second piece at
534 character position OFFSET (counting from 0), relative to INTERVAL.
535 INTERVAL becomes the right-hand piece, and the left-hand piece
536 (first, lexicographically) is returned.
538 The size and position fields of the two intervals are set based upon
539 those of the original interval. The property list of the new interval
540 is reset, thus it is up to the caller to do the right thing with the
543 Note that this does not change the position of INTERVAL; if it is a root,
544 it is still a root after this operation. */
547 split_interval_left (INTERVAL interval
, EMACS_INT offset
)
549 INTERVAL
new = make_interval ();
550 EMACS_INT new_length
= offset
;
552 new->position
= interval
->position
;
553 interval
->position
= interval
->position
+ offset
;
554 SET_INTERVAL_PARENT (new, interval
);
556 if (NULL_LEFT_CHILD (interval
))
558 interval
->left
= new;
559 new->total_length
= new_length
;
560 CHECK_TOTAL_LENGTH (new);
564 /* Insert the new node between INTERVAL and its left child. */
565 new->left
= interval
->left
;
566 SET_INTERVAL_PARENT (new->left
, new);
567 interval
->left
= new;
568 new->total_length
= new_length
+ new->left
->total_length
;
569 CHECK_TOTAL_LENGTH (new);
570 balance_an_interval (new);
573 balance_possible_root_interval (interval
);
578 /* Return the proper position for the first character
579 described by the interval tree SOURCE.
580 This is 1 if the parent is a buffer,
581 0 if the parent is a string or if there is no parent.
583 Don't use this function on an interval which is the child
584 of another interval! */
587 interval_start_pos (INTERVAL source
)
591 if (NULL_INTERVAL_P (source
))
594 if (! INTERVAL_HAS_OBJECT (source
))
596 GET_INTERVAL_OBJECT (parent
, source
);
597 if (BUFFERP (parent
))
598 return BUF_BEG (XBUFFER (parent
));
602 /* Find the interval containing text position POSITION in the text
603 represented by the interval tree TREE. POSITION is a buffer
604 position (starting from 1) or a string index (starting from 0).
605 If POSITION is at the end of the buffer or string,
606 return the interval containing the last character.
608 The `position' field, which is a cache of an interval's position,
609 is updated in the interval found. Other functions (e.g., next_interval)
610 will update this cache based on the result of find_interval. */
613 find_interval (register INTERVAL tree
, register EMACS_INT position
)
615 /* The distance from the left edge of the subtree at TREE
617 register EMACS_INT relative_position
;
619 if (NULL_INTERVAL_P (tree
))
620 return NULL_INTERVAL
;
622 relative_position
= position
;
623 if (INTERVAL_HAS_OBJECT (tree
))
626 GET_INTERVAL_OBJECT (parent
, tree
);
627 if (BUFFERP (parent
))
628 relative_position
-= BUF_BEG (XBUFFER (parent
));
631 if (relative_position
> TOTAL_LENGTH (tree
))
632 abort (); /* Paranoia */
634 if (!handling_signal
)
635 tree
= balance_possible_root_interval (tree
);
639 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
643 else if (! NULL_RIGHT_CHILD (tree
)
644 && relative_position
>= (TOTAL_LENGTH (tree
)
645 - RIGHT_TOTAL_LENGTH (tree
)))
647 relative_position
-= (TOTAL_LENGTH (tree
)
648 - RIGHT_TOTAL_LENGTH (tree
));
654 = (position
- relative_position
/* left edge of *tree. */
655 + LEFT_TOTAL_LENGTH (tree
)); /* left edge of this interval. */
662 /* Find the succeeding interval (lexicographically) to INTERVAL.
663 Sets the `position' field based on that of INTERVAL (see
667 next_interval (register INTERVAL interval
)
669 register INTERVAL i
= interval
;
670 register EMACS_INT next_position
;
672 if (NULL_INTERVAL_P (i
))
673 return NULL_INTERVAL
;
674 next_position
= interval
->position
+ LENGTH (interval
);
676 if (! NULL_RIGHT_CHILD (i
))
679 while (! NULL_LEFT_CHILD (i
))
682 i
->position
= next_position
;
686 while (! NULL_PARENT (i
))
688 if (AM_LEFT_CHILD (i
))
690 i
= INTERVAL_PARENT (i
);
691 i
->position
= next_position
;
695 i
= INTERVAL_PARENT (i
);
698 return NULL_INTERVAL
;
701 /* Find the preceding interval (lexicographically) to INTERVAL.
702 Sets the `position' field based on that of INTERVAL (see
706 previous_interval (register INTERVAL interval
)
710 if (NULL_INTERVAL_P (interval
))
711 return NULL_INTERVAL
;
713 if (! NULL_LEFT_CHILD (interval
))
716 while (! NULL_RIGHT_CHILD (i
))
719 i
->position
= interval
->position
- LENGTH (i
);
724 while (! NULL_PARENT (i
))
726 if (AM_RIGHT_CHILD (i
))
728 i
= INTERVAL_PARENT (i
);
730 i
->position
= interval
->position
- LENGTH (i
);
733 i
= INTERVAL_PARENT (i
);
736 return NULL_INTERVAL
;
739 /* Find the interval containing POS given some non-NULL INTERVAL
740 in the same tree. Note that we need to update interval->position
741 if we go down the tree.
742 To speed up the process, we assume that the ->position of
743 I and all its parents is already uptodate. */
745 update_interval (register INTERVAL i
, EMACS_INT pos
)
747 if (NULL_INTERVAL_P (i
))
748 return NULL_INTERVAL
;
752 if (pos
< i
->position
)
755 if (pos
>= i
->position
- TOTAL_LENGTH (i
->left
))
757 i
->left
->position
= i
->position
- TOTAL_LENGTH (i
->left
)
758 + LEFT_TOTAL_LENGTH (i
->left
);
759 i
= i
->left
; /* Move to the left child */
761 else if (NULL_PARENT (i
))
762 error ("Point before start of properties");
764 i
= INTERVAL_PARENT (i
);
767 else if (pos
>= INTERVAL_LAST_POS (i
))
770 if (pos
< INTERVAL_LAST_POS (i
) + TOTAL_LENGTH (i
->right
))
772 i
->right
->position
= INTERVAL_LAST_POS (i
)
773 + LEFT_TOTAL_LENGTH (i
->right
);
774 i
= i
->right
; /* Move to the right child */
776 else if (NULL_PARENT (i
))
777 error ("Point %"pI
"d after end of properties", pos
);
779 i
= INTERVAL_PARENT (i
);
789 /* Traverse a path down the interval tree TREE to the interval
790 containing POSITION, adjusting all nodes on the path for
791 an addition of LENGTH characters. Insertion between two intervals
792 (i.e., point == i->position, where i is second interval) means
793 text goes into second interval.
795 Modifications are needed to handle the hungry bits -- after simply
796 finding the interval at position (don't add length going down),
797 if it's the beginning of the interval, get the previous interval
798 and check the hungry bits of both. Then add the length going back up
802 adjust_intervals_for_insertion (INTERVAL tree
, EMACS_INT position
,
805 register EMACS_INT relative_position
;
806 register INTERVAL
this;
808 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
811 /* If inserting at point-max of a buffer, that position
812 will be out of range */
813 if (position
> TOTAL_LENGTH (tree
))
814 position
= TOTAL_LENGTH (tree
);
815 relative_position
= position
;
820 if (relative_position
<= LEFT_TOTAL_LENGTH (this))
822 this->total_length
+= length
;
823 CHECK_TOTAL_LENGTH (this);
826 else if (relative_position
> (TOTAL_LENGTH (this)
827 - RIGHT_TOTAL_LENGTH (this)))
829 relative_position
-= (TOTAL_LENGTH (this)
830 - RIGHT_TOTAL_LENGTH (this));
831 this->total_length
+= length
;
832 CHECK_TOTAL_LENGTH (this);
837 /* If we are to use zero-length intervals as buffer pointers,
838 then this code will have to change. */
839 this->total_length
+= length
;
840 CHECK_TOTAL_LENGTH (this);
841 this->position
= LEFT_TOTAL_LENGTH (this)
842 + position
- relative_position
+ 1;
849 /* Effect an adjustment corresponding to the addition of LENGTH characters
850 of text. Do this by finding the interval containing POSITION in the
851 interval tree TREE, and then adjusting all of its ancestors by adding
854 If POSITION is the first character of an interval, meaning that point
855 is actually between the two intervals, make the new text belong to
856 the interval which is "sticky".
858 If both intervals are "sticky", then make them belong to the left-most
859 interval. Another possibility would be to create a new interval for
860 this text, and make it have the merged properties of both ends. */
863 adjust_intervals_for_insertion (INTERVAL tree
,
864 EMACS_INT position
, EMACS_INT length
)
867 register INTERVAL temp
;
872 if (TOTAL_LENGTH (tree
) == 0) /* Paranoia */
875 GET_INTERVAL_OBJECT (parent
, tree
);
876 offset
= (BUFFERP (parent
) ? BUF_BEG (XBUFFER (parent
)) : 0);
878 /* If inserting at point-max of a buffer, that position will be out
879 of range. Remember that buffer positions are 1-based. */
880 if (position
>= TOTAL_LENGTH (tree
) + offset
)
882 position
= TOTAL_LENGTH (tree
) + offset
;
886 i
= find_interval (tree
, position
);
888 /* If in middle of an interval which is not sticky either way,
889 we must not just give its properties to the insertion.
890 So split this interval at the insertion point.
892 Originally, the if condition here was this:
893 (! (position == i->position || eobp)
894 && END_NONSTICKY_P (i)
895 && FRONT_NONSTICKY_P (i))
896 But, these macros are now unreliable because of introduction of
897 Vtext_property_default_nonsticky. So, we always check properties
898 one by one if POSITION is in middle of an interval. */
899 if (! (position
== i
->position
|| eobp
))
902 Lisp_Object front
, rear
;
906 /* Properties font-sticky and rear-nonsticky override
907 Vtext_property_default_nonsticky. So, if they are t, we can
908 skip one by one checking of properties. */
909 rear
= textget (i
->plist
, Qrear_nonsticky
);
910 if (! CONSP (rear
) && ! NILP (rear
))
912 /* All properties are nonsticky. We split the interval. */
915 front
= textget (i
->plist
, Qfront_sticky
);
916 if (! CONSP (front
) && ! NILP (front
))
918 /* All properties are sticky. We don't split the interval. */
923 /* Does any actual property pose an actual problem? We break
924 the loop if we find a nonsticky property. */
925 for (; CONSP (tail
); tail
= Fcdr (XCDR (tail
)))
927 Lisp_Object prop
, tmp
;
930 /* Is this particular property front-sticky? */
931 if (CONSP (front
) && ! NILP (Fmemq (prop
, front
)))
934 /* Is this particular property rear-nonsticky? */
935 if (CONSP (rear
) && ! NILP (Fmemq (prop
, rear
)))
938 /* Is this particular property recorded as sticky or
939 nonsticky in Vtext_property_default_nonsticky? */
940 tmp
= Fassq (prop
, Vtext_property_default_nonsticky
);
948 /* By default, a text property is rear-sticky, thus we
949 continue the loop. */
953 /* If any property is a real problem, split the interval. */
956 temp
= split_interval_right (i
, position
- i
->position
);
957 copy_properties (i
, temp
);
962 /* If we are positioned between intervals, check the stickiness of
963 both of them. We have to do this too, if we are at BEG or Z. */
964 if (position
== i
->position
|| eobp
)
966 register INTERVAL prev
;
976 prev
= previous_interval (i
);
978 /* Even if we are positioned between intervals, we default
979 to the left one if it exists. We extend it now and split
980 off a part later, if stickiness demands it. */
981 for (temp
= prev
? prev
: i
; temp
; temp
= INTERVAL_PARENT_OR_NULL (temp
))
983 temp
->total_length
+= length
;
984 CHECK_TOTAL_LENGTH (temp
);
985 temp
= balance_possible_root_interval (temp
);
988 /* If at least one interval has sticky properties,
989 we check the stickiness property by property.
991 Originally, the if condition here was this:
992 (END_NONSTICKY_P (prev) || FRONT_STICKY_P (i))
993 But, these macros are now unreliable because of introduction
994 of Vtext_property_default_nonsticky. So, we always have to
995 check stickiness of properties one by one. If cache of
996 stickiness is implemented in the future, we may be able to
997 use those macros again. */
1000 Lisp_Object pleft
, pright
;
1001 struct interval newi
;
1003 pleft
= NULL_INTERVAL_P (prev
) ? Qnil
: prev
->plist
;
1004 pright
= NULL_INTERVAL_P (i
) ? Qnil
: i
->plist
;
1005 newi
.plist
= merge_properties_sticky (pleft
, pright
);
1007 if (! prev
) /* i.e. position == BEG */
1009 if (! intervals_equal (i
, &newi
))
1011 i
= split_interval_left (i
, length
);
1012 i
->plist
= newi
.plist
;
1015 else if (! intervals_equal (prev
, &newi
))
1017 prev
= split_interval_right (prev
,
1018 position
- prev
->position
);
1019 prev
->plist
= newi
.plist
;
1020 if (! NULL_INTERVAL_P (i
)
1021 && intervals_equal (prev
, i
))
1022 merge_interval_right (prev
);
1025 /* We will need to update the cache here later. */
1027 else if (! prev
&& ! NILP (i
->plist
))
1029 /* Just split off a new interval at the left.
1030 Since I wasn't front-sticky, the empty plist is ok. */
1031 i
= split_interval_left (i
, length
);
1035 /* Otherwise just extend the interval. */
1038 for (temp
= i
; temp
; temp
= INTERVAL_PARENT_OR_NULL (temp
))
1040 temp
->total_length
+= length
;
1041 CHECK_TOTAL_LENGTH (temp
);
1042 temp
= balance_possible_root_interval (temp
);
1049 /* Any property might be front-sticky on the left, rear-sticky on the left,
1050 front-sticky on the right, or rear-sticky on the right; the 16 combinations
1051 can be arranged in a matrix with rows denoting the left conditions and
1052 columns denoting the right conditions:
1060 left-props = '(front-sticky (p8 p9 pa pb pc pd pe pf)
1061 rear-nonsticky (p4 p5 p6 p7 p8 p9 pa pb)
1062 p0 L p1 L p2 L p3 L p4 L p5 L p6 L p7 L
1063 p8 L p9 L pa L pb L pc L pd L pe L pf L)
1064 right-props = '(front-sticky (p2 p3 p6 p7 pa pb pe pf)
1065 rear-nonsticky (p1 p2 p5 p6 p9 pa pd pe)
1066 p0 R p1 R p2 R p3 R p4 R p5 R p6 R p7 R
1067 p8 R p9 R pa R pb R pc R pd R pe R pf R)
1069 We inherit from whoever has a sticky side facing us. If both sides
1070 do (cases 2, 3, E, and F), then we inherit from whichever side has a
1071 non-nil value for the current property. If both sides do, then we take
1074 When we inherit a property, we get its stickiness as well as its value.
1075 So, when we merge the above two lists, we expect to get this:
1077 result = '(front-sticky (p6 p7 pa pb pc pd pe pf)
1078 rear-nonsticky (p6 pa)
1079 p0 L p1 L p2 L p3 L p6 R p7 R
1080 pa R pb R pc L pd L pe L pf L)
1082 The optimizable special cases are:
1083 left rear-nonsticky = nil, right front-sticky = nil (inherit left)
1084 left rear-nonsticky = t, right front-sticky = t (inherit right)
1085 left rear-nonsticky = t, right front-sticky = nil (inherit none)
1089 merge_properties_sticky (Lisp_Object pleft
, Lisp_Object pright
)
1091 register Lisp_Object props
, front
, rear
;
1092 Lisp_Object lfront
, lrear
, rfront
, rrear
;
1093 register Lisp_Object tail1
, tail2
, sym
, lval
, rval
, cat
;
1094 int use_left
, use_right
;
1100 lfront
= textget (pleft
, Qfront_sticky
);
1101 lrear
= textget (pleft
, Qrear_nonsticky
);
1102 rfront
= textget (pright
, Qfront_sticky
);
1103 rrear
= textget (pright
, Qrear_nonsticky
);
1105 /* Go through each element of PRIGHT. */
1106 for (tail1
= pright
; CONSP (tail1
); tail1
= Fcdr (XCDR (tail1
)))
1112 /* Sticky properties get special treatment. */
1113 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
1116 rval
= Fcar (XCDR (tail1
));
1117 for (tail2
= pleft
; CONSP (tail2
); tail2
= Fcdr (XCDR (tail2
)))
1118 if (EQ (sym
, XCAR (tail2
)))
1121 /* Indicate whether the property is explicitly defined on the left.
1122 (We know it is defined explicitly on the right
1123 because otherwise we don't get here.) */
1124 lpresent
= ! NILP (tail2
);
1125 lval
= (NILP (tail2
) ? Qnil
: Fcar (Fcdr (tail2
)));
1127 /* Even if lrear or rfront say nothing about the stickiness of
1128 SYM, Vtext_property_default_nonsticky may give default
1129 stickiness to SYM. */
1130 tmp
= Fassq (sym
, Vtext_property_default_nonsticky
);
1131 use_left
= (lpresent
1132 && ! (TMEM (sym
, lrear
)
1133 || (CONSP (tmp
) && ! NILP (XCDR (tmp
)))));
1134 use_right
= (TMEM (sym
, rfront
)
1135 || (CONSP (tmp
) && NILP (XCDR (tmp
))));
1136 if (use_left
&& use_right
)
1140 else if (NILP (rval
))
1145 /* We build props as (value sym ...) rather than (sym value ...)
1146 because we plan to nreverse it when we're done. */
1147 props
= Fcons (lval
, Fcons (sym
, props
));
1148 if (TMEM (sym
, lfront
))
1149 front
= Fcons (sym
, front
);
1150 if (TMEM (sym
, lrear
))
1151 rear
= Fcons (sym
, rear
);
1155 props
= Fcons (rval
, Fcons (sym
, props
));
1156 if (TMEM (sym
, rfront
))
1157 front
= Fcons (sym
, front
);
1158 if (TMEM (sym
, rrear
))
1159 rear
= Fcons (sym
, rear
);
1163 /* Now go through each element of PLEFT. */
1164 for (tail2
= pleft
; CONSP (tail2
); tail2
= Fcdr (XCDR (tail2
)))
1170 /* Sticky properties get special treatment. */
1171 if (EQ (sym
, Qrear_nonsticky
) || EQ (sym
, Qfront_sticky
))
1174 /* If sym is in PRIGHT, we've already considered it. */
1175 for (tail1
= pright
; CONSP (tail1
); tail1
= Fcdr (XCDR (tail1
)))
1176 if (EQ (sym
, XCAR (tail1
)))
1181 lval
= Fcar (XCDR (tail2
));
1183 /* Even if lrear or rfront say nothing about the stickiness of
1184 SYM, Vtext_property_default_nonsticky may give default
1185 stickiness to SYM. */
1186 tmp
= Fassq (sym
, Vtext_property_default_nonsticky
);
1188 /* Since rval is known to be nil in this loop, the test simplifies. */
1189 if (! (TMEM (sym
, lrear
) || (CONSP (tmp
) && ! NILP (XCDR (tmp
)))))
1191 props
= Fcons (lval
, Fcons (sym
, props
));
1192 if (TMEM (sym
, lfront
))
1193 front
= Fcons (sym
, front
);
1195 else if (TMEM (sym
, rfront
) || (CONSP (tmp
) && NILP (XCDR (tmp
))))
1197 /* The value is nil, but we still inherit the stickiness
1199 front
= Fcons (sym
, front
);
1200 if (TMEM (sym
, rrear
))
1201 rear
= Fcons (sym
, rear
);
1204 props
= Fnreverse (props
);
1206 props
= Fcons (Qrear_nonsticky
, Fcons (Fnreverse (rear
), props
));
1208 cat
= textget (props
, Qcategory
);
1211 /* If we have inherited a front-stick category property that is t,
1212 we don't need to set up a detailed one. */
1213 ! (! NILP (cat
) && SYMBOLP (cat
)
1214 && EQ (Fget (cat
, Qfront_sticky
), Qt
)))
1215 props
= Fcons (Qfront_sticky
, Fcons (Fnreverse (front
), props
));
1220 /* Delete a node I from its interval tree by merging its subtrees
1221 into one subtree which is then returned. Caller is responsible for
1222 storing the resulting subtree into its parent. */
1225 delete_node (register INTERVAL i
)
1227 register INTERVAL migrate
, this;
1228 register EMACS_INT migrate_amt
;
1230 if (NULL_INTERVAL_P (i
->left
))
1232 if (NULL_INTERVAL_P (i
->right
))
1236 migrate_amt
= i
->left
->total_length
;
1238 this->total_length
+= migrate_amt
;
1239 while (! NULL_INTERVAL_P (this->left
))
1242 this->total_length
+= migrate_amt
;
1244 CHECK_TOTAL_LENGTH (this);
1245 this->left
= migrate
;
1246 SET_INTERVAL_PARENT (migrate
, this);
1251 /* Delete interval I from its tree by calling `delete_node'
1252 and properly connecting the resultant subtree.
1254 I is presumed to be empty; that is, no adjustments are made
1255 for the length of I. */
1258 delete_interval (register INTERVAL i
)
1260 register INTERVAL parent
;
1261 EMACS_INT amt
= LENGTH (i
);
1263 if (amt
> 0) /* Only used on zero-length intervals now. */
1266 if (ROOT_INTERVAL_P (i
))
1269 GET_INTERVAL_OBJECT (owner
, i
);
1270 parent
= delete_node (i
);
1271 if (! NULL_INTERVAL_P (parent
))
1272 SET_INTERVAL_OBJECT (parent
, owner
);
1274 if (BUFFERP (owner
))
1275 BUF_INTERVALS (XBUFFER (owner
)) = parent
;
1276 else if (STRINGP (owner
))
1277 STRING_SET_INTERVALS (owner
, parent
);
1284 parent
= INTERVAL_PARENT (i
);
1285 if (AM_LEFT_CHILD (i
))
1287 parent
->left
= delete_node (i
);
1288 if (! NULL_INTERVAL_P (parent
->left
))
1289 SET_INTERVAL_PARENT (parent
->left
, parent
);
1293 parent
->right
= delete_node (i
);
1294 if (! NULL_INTERVAL_P (parent
->right
))
1295 SET_INTERVAL_PARENT (parent
->right
, parent
);
1299 /* Find the interval in TREE corresponding to the relative position
1300 FROM and delete as much as possible of AMOUNT from that interval.
1301 Return the amount actually deleted, and if the interval was
1302 zeroed-out, delete that interval node from the tree.
1304 Note that FROM is actually origin zero, aka relative to the
1305 leftmost edge of tree. This is appropriate since we call ourselves
1306 recursively on subtrees.
1308 Do this by recursing down TREE to the interval in question, and
1309 deleting the appropriate amount of text. */
1312 interval_deletion_adjustment (register INTERVAL tree
, register EMACS_INT from
,
1313 register EMACS_INT amount
)
1315 register EMACS_INT relative_position
= from
;
1317 if (NULL_INTERVAL_P (tree
))
1321 if (relative_position
< LEFT_TOTAL_LENGTH (tree
))
1323 EMACS_INT subtract
= interval_deletion_adjustment (tree
->left
,
1326 tree
->total_length
-= subtract
;
1327 CHECK_TOTAL_LENGTH (tree
);
1331 else if (relative_position
>= (TOTAL_LENGTH (tree
)
1332 - RIGHT_TOTAL_LENGTH (tree
)))
1336 relative_position
-= (tree
->total_length
1337 - RIGHT_TOTAL_LENGTH (tree
));
1338 subtract
= interval_deletion_adjustment (tree
->right
,
1341 tree
->total_length
-= subtract
;
1342 CHECK_TOTAL_LENGTH (tree
);
1345 /* Here -- this node. */
1348 /* How much can we delete from this interval? */
1349 EMACS_INT my_amount
= ((tree
->total_length
1350 - RIGHT_TOTAL_LENGTH (tree
))
1351 - relative_position
);
1353 if (amount
> my_amount
)
1356 tree
->total_length
-= amount
;
1357 CHECK_TOTAL_LENGTH (tree
);
1358 if (LENGTH (tree
) == 0)
1359 delete_interval (tree
);
1364 /* Never reach here. */
1367 /* Effect the adjustments necessary to the interval tree of BUFFER to
1368 correspond to the deletion of LENGTH characters from that buffer
1369 text. The deletion is effected at position START (which is a
1370 buffer position, i.e. origin 1). */
1373 adjust_intervals_for_deletion (struct buffer
*buffer
,
1374 EMACS_INT start
, EMACS_INT length
)
1376 register EMACS_INT left_to_delete
= length
;
1377 register INTERVAL tree
= BUF_INTERVALS (buffer
);
1381 GET_INTERVAL_OBJECT (parent
, tree
);
1382 offset
= (BUFFERP (parent
) ? BUF_BEG (XBUFFER (parent
)) : 0);
1384 if (NULL_INTERVAL_P (tree
))
1387 if (start
> offset
+ TOTAL_LENGTH (tree
)
1388 || start
+ length
> offset
+ TOTAL_LENGTH (tree
))
1391 if (length
== TOTAL_LENGTH (tree
))
1393 BUF_INTERVALS (buffer
) = NULL_INTERVAL
;
1397 if (ONLY_INTERVAL_P (tree
))
1399 tree
->total_length
-= length
;
1400 CHECK_TOTAL_LENGTH (tree
);
1404 if (start
> offset
+ TOTAL_LENGTH (tree
))
1405 start
= offset
+ TOTAL_LENGTH (tree
);
1406 while (left_to_delete
> 0)
1408 left_to_delete
-= interval_deletion_adjustment (tree
, start
- offset
,
1410 tree
= BUF_INTERVALS (buffer
);
1411 if (left_to_delete
== tree
->total_length
)
1413 BUF_INTERVALS (buffer
) = NULL_INTERVAL
;
1419 /* Make the adjustments necessary to the interval tree of BUFFER to
1420 represent an addition or deletion of LENGTH characters starting
1421 at position START. Addition or deletion is indicated by the sign
1424 The two inline functions (one static) pacify Sun C 5.8, a pre-C99
1425 compiler that does not allow calling a static function (here,
1426 adjust_intervals_for_deletion) from a non-static inline function. */
1429 offset_intervals (struct buffer
*buffer
, EMACS_INT start
, EMACS_INT length
)
1431 if (NULL_INTERVAL_P (BUF_INTERVALS (buffer
)) || length
== 0)
1435 adjust_intervals_for_insertion (BUF_INTERVALS (buffer
), start
, length
);
1438 IF_LINT (if (length
< - TYPE_MAXIMUM (EMACS_INT
)) abort ();)
1439 adjust_intervals_for_deletion (buffer
, start
, -length
);
1443 /* Merge interval I with its lexicographic successor. The resulting
1444 interval is returned, and has the properties of the original
1445 successor. The properties of I are lost. I is removed from the
1449 The caller must verify that this is not the last (rightmost)
1453 merge_interval_right (register INTERVAL i
)
1455 register EMACS_INT absorb
= LENGTH (i
);
1456 register INTERVAL successor
;
1458 /* Zero out this interval. */
1459 i
->total_length
-= absorb
;
1460 CHECK_TOTAL_LENGTH (i
);
1462 /* Find the succeeding interval. */
1463 if (! NULL_RIGHT_CHILD (i
)) /* It's below us. Add absorb
1466 successor
= i
->right
;
1467 while (! NULL_LEFT_CHILD (successor
))
1469 successor
->total_length
+= absorb
;
1470 CHECK_TOTAL_LENGTH (successor
);
1471 successor
= successor
->left
;
1474 successor
->total_length
+= absorb
;
1475 CHECK_TOTAL_LENGTH (successor
);
1476 delete_interval (i
);
1481 while (! NULL_PARENT (successor
)) /* It's above us. Subtract as
1484 if (AM_LEFT_CHILD (successor
))
1486 successor
= INTERVAL_PARENT (successor
);
1487 delete_interval (i
);
1491 successor
= INTERVAL_PARENT (successor
);
1492 successor
->total_length
-= absorb
;
1493 CHECK_TOTAL_LENGTH (successor
);
1496 /* This must be the rightmost or last interval and cannot
1497 be merged right. The caller should have known. */
1501 /* Merge interval I with its lexicographic predecessor. The resulting
1502 interval is returned, and has the properties of the original predecessor.
1503 The properties of I are lost. Interval node I is removed from the tree.
1506 The caller must verify that this is not the first (leftmost) interval. */
1509 merge_interval_left (register INTERVAL i
)
1511 register EMACS_INT absorb
= LENGTH (i
);
1512 register INTERVAL predecessor
;
1514 /* Zero out this interval. */
1515 i
->total_length
-= absorb
;
1516 CHECK_TOTAL_LENGTH (i
);
1518 /* Find the preceding interval. */
1519 if (! NULL_LEFT_CHILD (i
)) /* It's below us. Go down,
1520 adding ABSORB as we go. */
1522 predecessor
= i
->left
;
1523 while (! NULL_RIGHT_CHILD (predecessor
))
1525 predecessor
->total_length
+= absorb
;
1526 CHECK_TOTAL_LENGTH (predecessor
);
1527 predecessor
= predecessor
->right
;
1530 predecessor
->total_length
+= absorb
;
1531 CHECK_TOTAL_LENGTH (predecessor
);
1532 delete_interval (i
);
1537 while (! NULL_PARENT (predecessor
)) /* It's above us. Go up,
1538 subtracting ABSORB. */
1540 if (AM_RIGHT_CHILD (predecessor
))
1542 predecessor
= INTERVAL_PARENT (predecessor
);
1543 delete_interval (i
);
1547 predecessor
= INTERVAL_PARENT (predecessor
);
1548 predecessor
->total_length
-= absorb
;
1549 CHECK_TOTAL_LENGTH (predecessor
);
1552 /* This must be the leftmost or first interval and cannot
1553 be merged left. The caller should have known. */
1557 /* Make an exact copy of interval tree SOURCE which descends from
1558 PARENT. This is done by recursing through SOURCE, copying
1559 the current interval and its properties, and then adjusting
1560 the pointers of the copy. */
1563 reproduce_tree (INTERVAL source
, INTERVAL parent
)
1565 register INTERVAL t
= make_interval ();
1567 memcpy (t
, source
, INTERVAL_SIZE
);
1568 copy_properties (source
, t
);
1569 SET_INTERVAL_PARENT (t
, parent
);
1570 if (! NULL_LEFT_CHILD (source
))
1571 t
->left
= reproduce_tree (source
->left
, t
);
1572 if (! NULL_RIGHT_CHILD (source
))
1573 t
->right
= reproduce_tree (source
->right
, t
);
1579 reproduce_tree_obj (INTERVAL source
, Lisp_Object parent
)
1581 register INTERVAL t
= make_interval ();
1583 memcpy (t
, source
, INTERVAL_SIZE
);
1584 copy_properties (source
, t
);
1585 SET_INTERVAL_OBJECT (t
, parent
);
1586 if (! NULL_LEFT_CHILD (source
))
1587 t
->left
= reproduce_tree (source
->left
, t
);
1588 if (! NULL_RIGHT_CHILD (source
))
1589 t
->right
= reproduce_tree (source
->right
, t
);
1595 /* Nobody calls this. Perhaps it's a vestige of an earlier design. */
1597 /* Make a new interval of length LENGTH starting at START in the
1598 group of intervals INTERVALS, which is actually an interval tree.
1599 Returns the new interval.
1601 Generate an error if the new positions would overlap an existing
1605 make_new_interval (INTERVAL intervals
, EMACS_INT start
, EMACS_INT length
)
1609 slot
= find_interval (intervals
, start
);
1610 if (start
+ length
> slot
->position
+ LENGTH (slot
))
1611 error ("Interval would overlap");
1613 if (start
== slot
->position
&& length
== LENGTH (slot
))
1616 if (slot
->position
== start
)
1618 /* New right node. */
1619 split_interval_right (slot
, length
);
1623 if (slot
->position
+ LENGTH (slot
) == start
+ length
)
1625 /* New left node. */
1626 split_interval_left (slot
, LENGTH (slot
) - length
);
1630 /* Convert interval SLOT into three intervals. */
1631 split_interval_left (slot
, start
- slot
->position
);
1632 split_interval_right (slot
, length
);
1637 /* Insert the intervals of SOURCE into BUFFER at POSITION.
1638 LENGTH is the length of the text in SOURCE.
1640 The `position' field of the SOURCE intervals is assumed to be
1641 consistent with its parent; therefore, SOURCE must be an
1642 interval tree made with copy_interval or must be the whole
1643 tree of a buffer or a string.
1645 This is used in insdel.c when inserting Lisp_Strings into the
1646 buffer. The text corresponding to SOURCE is already in the buffer
1647 when this is called. The intervals of new tree are a copy of those
1648 belonging to the string being inserted; intervals are never
1651 If the inserted text had no intervals associated, and we don't
1652 want to inherit the surrounding text's properties, this function
1653 simply returns -- offset_intervals should handle placing the
1654 text in the correct interval, depending on the sticky bits.
1656 If the inserted text had properties (intervals), then there are two
1657 cases -- either insertion happened in the middle of some interval,
1658 or between two intervals.
1660 If the text goes into the middle of an interval, then new
1661 intervals are created in the middle with only the properties of
1662 the new text, *unless* the macro MERGE_INSERTIONS is true, in
1663 which case the new text has the union of its properties and those
1664 of the text into which it was inserted.
1666 If the text goes between two intervals, then if neither interval
1667 had its appropriate sticky property set (front_sticky, rear_sticky),
1668 the new text has only its properties. If one of the sticky properties
1669 is set, then the new text "sticks" to that region and its properties
1670 depend on merging as above. If both the preceding and succeeding
1671 intervals to the new text are "sticky", then the new text retains
1672 only its properties, as if neither sticky property were set. Perhaps
1673 we should consider merging all three sets of properties onto the new
1677 graft_intervals_into_buffer (INTERVAL source
, EMACS_INT position
,
1678 EMACS_INT length
, struct buffer
*buffer
,
1681 register INTERVAL under
, over
, this;
1682 register INTERVAL tree
;
1683 EMACS_INT over_used
;
1685 tree
= BUF_INTERVALS (buffer
);
1687 /* If the new text has no properties, then with inheritance it
1688 becomes part of whatever interval it was inserted into.
1689 To prevent inheritance, we must clear out the properties
1690 of the newly inserted text. */
1691 if (NULL_INTERVAL_P (source
))
1694 if (!inherit
&& !NULL_INTERVAL_P (tree
) && length
> 0)
1696 XSETBUFFER (buf
, buffer
);
1697 set_text_properties_1 (make_number (position
),
1698 make_number (position
+ length
),
1701 if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer
)))
1702 /* Shouldn't be necessary. -stef */
1703 BUF_INTERVALS (buffer
) = balance_an_interval (BUF_INTERVALS (buffer
));
1707 if (NULL_INTERVAL_P (tree
))
1709 /* The inserted text constitutes the whole buffer, so
1710 simply copy over the interval structure. */
1711 if ((BUF_Z (buffer
) - BUF_BEG (buffer
)) == TOTAL_LENGTH (source
))
1714 XSETBUFFER (buf
, buffer
);
1715 BUF_INTERVALS (buffer
) = reproduce_tree_obj (source
, buf
);
1716 BUF_INTERVALS (buffer
)->position
= BEG
;
1717 BUF_INTERVALS (buffer
)->up_obj
= 1;
1722 /* Create an interval tree in which to place a copy
1723 of the intervals of the inserted string. */
1726 XSETBUFFER (buf
, buffer
);
1727 tree
= create_root_interval (buf
);
1730 else if (TOTAL_LENGTH (tree
) == TOTAL_LENGTH (source
))
1731 /* If the buffer contains only the new string, but
1732 there was already some interval tree there, then it may be
1733 some zero length intervals. Eventually, do something clever
1734 about inserting properly. For now, just waste the old intervals. */
1736 BUF_INTERVALS (buffer
) = reproduce_tree (source
, INTERVAL_PARENT (tree
));
1737 BUF_INTERVALS (buffer
)->position
= BEG
;
1738 BUF_INTERVALS (buffer
)->up_obj
= 1;
1739 /* Explicitly free the old tree here. */
1743 /* Paranoia -- the text has already been added, so this buffer
1744 should be of non-zero length. */
1745 else if (TOTAL_LENGTH (tree
) == 0)
1748 this = under
= find_interval (tree
, position
);
1749 if (NULL_INTERVAL_P (under
)) /* Paranoia */
1751 over
= find_interval (source
, interval_start_pos (source
));
1753 /* Here for insertion in the middle of an interval.
1754 Split off an equivalent interval to the right,
1755 then don't bother with it any more. */
1757 if (position
> under
->position
)
1759 INTERVAL end_unchanged
1760 = split_interval_left (this, position
- under
->position
);
1761 copy_properties (under
, end_unchanged
);
1762 under
->position
= position
;
1766 /* This call may have some effect because previous_interval may
1767 update `position' fields of intervals. Thus, don't ignore it
1768 for the moment. Someone please tell me the truth (K.Handa). */
1769 INTERVAL prev
= previous_interval (under
);
1772 /* But, this code surely has no effect. And, anyway,
1773 END_NONSTICKY_P is unreliable now. */
1774 if (prev
&& !END_NONSTICKY_P (prev
))
1779 /* Insertion is now at beginning of UNDER. */
1781 /* The inserted text "sticks" to the interval `under',
1782 which means it gets those properties.
1783 The properties of under are the result of
1784 adjust_intervals_for_insertion, so stickiness has
1785 already been taken care of. */
1787 /* OVER is the interval we are copying from next.
1788 OVER_USED says how many characters' worth of OVER
1789 have already been copied into target intervals.
1790 UNDER is the next interval in the target. */
1792 while (! NULL_INTERVAL_P (over
))
1794 /* If UNDER is longer than OVER, split it. */
1795 if (LENGTH (over
) - over_used
< LENGTH (under
))
1797 this = split_interval_left (under
, LENGTH (over
) - over_used
);
1798 copy_properties (under
, this);
1803 /* THIS is now the interval to copy or merge into.
1804 OVER covers all of it. */
1806 merge_properties (over
, this);
1808 copy_properties (over
, this);
1810 /* If THIS and OVER end at the same place,
1811 advance OVER to a new source interval. */
1812 if (LENGTH (this) == LENGTH (over
) - over_used
)
1814 over
= next_interval (over
);
1818 /* Otherwise just record that more of OVER has been used. */
1819 over_used
+= LENGTH (this);
1821 /* Always advance to a new target interval. */
1822 under
= next_interval (this);
1825 if (! NULL_INTERVAL_P (BUF_INTERVALS (buffer
)))
1826 BUF_INTERVALS (buffer
) = balance_an_interval (BUF_INTERVALS (buffer
));
1830 /* Get the value of property PROP from PLIST,
1831 which is the plist of an interval.
1832 We check for direct properties, for categories with property PROP,
1833 and for PROP appearing on the default-text-properties list. */
1836 textget (Lisp_Object plist
, register Lisp_Object prop
)
1838 return lookup_char_property (plist
, prop
, 1);
1842 lookup_char_property (Lisp_Object plist
, register Lisp_Object prop
, int textprop
)
1844 register Lisp_Object tail
, fallback
= Qnil
;
1846 for (tail
= plist
; CONSP (tail
); tail
= Fcdr (XCDR (tail
)))
1848 register Lisp_Object tem
;
1851 return Fcar (XCDR (tail
));
1852 if (EQ (tem
, Qcategory
))
1854 tem
= Fcar (XCDR (tail
));
1856 fallback
= Fget (tem
, prop
);
1860 if (! NILP (fallback
))
1862 /* Check for alternative properties */
1863 tail
= Fassq (prop
, Vchar_property_alias_alist
);
1867 for (; NILP (fallback
) && CONSP (tail
); tail
= XCDR (tail
))
1868 fallback
= Fplist_get (plist
, XCAR (tail
));
1871 if (textprop
&& NILP (fallback
) && CONSP (Vdefault_text_properties
))
1872 fallback
= Fplist_get (Vdefault_text_properties
, prop
);
1877 /* Set point in BUFFER "temporarily" to CHARPOS, which corresponds to
1878 byte position BYTEPOS. */
1881 temp_set_point_both (struct buffer
*buffer
,
1882 EMACS_INT charpos
, EMACS_INT bytepos
)
1884 /* In a single-byte buffer, the two positions must be equal. */
1885 if (BUF_ZV (buffer
) == BUF_ZV_BYTE (buffer
)
1886 && charpos
!= bytepos
)
1889 if (charpos
> bytepos
)
1892 if (charpos
> BUF_ZV (buffer
) || charpos
< BUF_BEGV (buffer
))
1895 SET_BUF_PT_BOTH (buffer
, charpos
, bytepos
);
1898 /* Set point "temporarily", without checking any text properties. */
1901 temp_set_point (struct buffer
*buffer
, EMACS_INT charpos
)
1903 temp_set_point_both (buffer
, charpos
,
1904 buf_charpos_to_bytepos (buffer
, charpos
));
1907 /* Set point in BUFFER to CHARPOS. If the target position is
1908 before an intangible character, move to an ok place. */
1911 set_point (EMACS_INT charpos
)
1913 set_point_both (charpos
, buf_charpos_to_bytepos (current_buffer
, charpos
));
1916 /* If there's an invisible character at position POS + TEST_OFFS in the
1917 current buffer, and the invisible property has a `stickiness' such that
1918 inserting a character at position POS would inherit the property it,
1919 return POS + ADJ, otherwise return POS. If TEST_INTANG is non-zero,
1920 then intangibility is required as well as invisibleness.
1922 TEST_OFFS should be either 0 or -1, and ADJ should be either 1 or -1.
1924 Note that `stickiness' is determined by overlay marker insertion types,
1925 if the invisible property comes from an overlay. */
1928 adjust_for_invis_intang (EMACS_INT pos
, EMACS_INT test_offs
, EMACS_INT adj
,
1931 Lisp_Object invis_propval
, invis_overlay
;
1932 Lisp_Object test_pos
;
1934 if ((adj
< 0 && pos
+ adj
< BEGV
) || (adj
> 0 && pos
+ adj
> ZV
))
1935 /* POS + ADJ would be beyond the buffer bounds, so do no adjustment. */
1938 test_pos
= make_number (pos
+ test_offs
);
1941 = get_char_property_and_overlay (test_pos
, Qinvisible
, Qnil
,
1945 || ! NILP (Fget_char_property (test_pos
, Qintangible
, Qnil
)))
1946 && TEXT_PROP_MEANS_INVISIBLE (invis_propval
)
1947 /* This next test is true if the invisible property has a stickiness
1948 such that an insertion at POS would inherit it. */
1949 && (NILP (invis_overlay
)
1950 /* Invisible property is from a text-property. */
1951 ? (text_property_stickiness (Qinvisible
, make_number (pos
), Qnil
)
1952 == (test_offs
== 0 ? 1 : -1))
1953 /* Invisible property is from an overlay. */
1955 ? XMARKER (OVERLAY_START (invis_overlay
))->insertion_type
== 0
1956 : XMARKER (OVERLAY_END (invis_overlay
))->insertion_type
== 1)))
1962 /* Set point in BUFFER to CHARPOS, which corresponds to byte
1963 position BYTEPOS. If the target position is
1964 before an intangible character, move to an ok place. */
1967 set_point_both (EMACS_INT charpos
, EMACS_INT bytepos
)
1969 register INTERVAL to
, from
, toprev
, fromprev
;
1970 EMACS_INT buffer_point
;
1971 EMACS_INT old_position
= PT
;
1972 /* This ensures that we move forward past intangible text when the
1973 initial position is the same as the destination, in the rare
1974 instances where this is important, e.g. in line-move-finish
1976 int backwards
= (charpos
< old_position
? 1 : 0);
1978 EMACS_INT original_position
;
1980 BVAR (current_buffer
, point_before_scroll
) = Qnil
;
1985 /* In a single-byte buffer, the two positions must be equal. */
1986 eassert (ZV
!= ZV_BYTE
|| charpos
== bytepos
);
1988 /* Check this now, before checking if the buffer has any intervals.
1989 That way, we can catch conditions which break this sanity check
1990 whether or not there are intervals in the buffer. */
1991 eassert (charpos
<= ZV
&& charpos
>= BEGV
);
1993 have_overlays
= (current_buffer
->overlays_before
1994 || current_buffer
->overlays_after
);
1996 /* If we have no text properties and overlays,
1997 then we can do it quickly. */
1998 if (NULL_INTERVAL_P (BUF_INTERVALS (current_buffer
)) && ! have_overlays
)
2000 temp_set_point_both (current_buffer
, charpos
, bytepos
);
2004 /* Set TO to the interval containing the char after CHARPOS,
2005 and TOPREV to the interval containing the char before CHARPOS.
2006 Either one may be null. They may be equal. */
2007 to
= find_interval (BUF_INTERVALS (current_buffer
), charpos
);
2008 if (charpos
== BEGV
)
2010 else if (to
&& to
->position
== charpos
)
2011 toprev
= previous_interval (to
);
2015 buffer_point
= (PT
== ZV
? ZV
- 1 : PT
);
2017 /* Set FROM to the interval containing the char after PT,
2018 and FROMPREV to the interval containing the char before PT.
2019 Either one may be null. They may be equal. */
2020 /* We could cache this and save time. */
2021 from
= find_interval (BUF_INTERVALS (current_buffer
), buffer_point
);
2022 if (buffer_point
== BEGV
)
2024 else if (from
&& from
->position
== PT
)
2025 fromprev
= previous_interval (from
);
2026 else if (buffer_point
!= PT
)
2027 fromprev
= from
, from
= 0;
2031 /* Moving within an interval. */
2032 if (to
== from
&& toprev
== fromprev
&& INTERVAL_VISIBLE_P (to
)
2035 temp_set_point_both (current_buffer
, charpos
, bytepos
);
2039 original_position
= charpos
;
2041 /* If the new position is between two intangible characters
2042 with the same intangible property value,
2043 move forward or backward until a change in that property. */
2044 if (NILP (Vinhibit_point_motion_hooks
)
2045 && ((! NULL_INTERVAL_P (to
) && ! NULL_INTERVAL_P (toprev
))
2047 /* Intangibility never stops us from positioning at the beginning
2048 or end of the buffer, so don't bother checking in that case. */
2049 && charpos
!= BEGV
&& charpos
!= ZV
)
2052 Lisp_Object intangible_propval
;
2056 /* If the preceding character is both intangible and invisible,
2057 and the invisible property is `rear-sticky', perturb it so
2058 that the search starts one character earlier -- this ensures
2059 that point can never move to the end of an invisible/
2060 intangible/rear-sticky region. */
2061 charpos
= adjust_for_invis_intang (charpos
, -1, -1, 1);
2063 XSETINT (pos
, charpos
);
2065 /* If following char is intangible,
2066 skip back over all chars with matching intangible property. */
2068 intangible_propval
= Fget_char_property (pos
, Qintangible
, Qnil
);
2070 if (! NILP (intangible_propval
))
2072 while (XINT (pos
) > BEGV
2073 && EQ (Fget_char_property (make_number (XINT (pos
) - 1),
2075 intangible_propval
))
2076 pos
= Fprevious_char_property_change (pos
, Qnil
);
2078 /* Set CHARPOS from POS, and if the final intangible character
2079 that we skipped over is also invisible, and the invisible
2080 property is `front-sticky', perturb it to be one character
2081 earlier -- this ensures that point can never move to the
2082 beginning of an invisible/intangible/front-sticky region. */
2083 charpos
= adjust_for_invis_intang (XINT (pos
), 0, -1, 0);
2088 /* If the following character is both intangible and invisible,
2089 and the invisible property is `front-sticky', perturb it so
2090 that the search starts one character later -- this ensures
2091 that point can never move to the beginning of an
2092 invisible/intangible/front-sticky region. */
2093 charpos
= adjust_for_invis_intang (charpos
, 0, 1, 1);
2095 XSETINT (pos
, charpos
);
2097 /* If preceding char is intangible,
2098 skip forward over all chars with matching intangible property. */
2100 intangible_propval
= Fget_char_property (make_number (charpos
- 1),
2103 if (! NILP (intangible_propval
))
2105 while (XINT (pos
) < ZV
2106 && EQ (Fget_char_property (pos
, Qintangible
, Qnil
),
2107 intangible_propval
))
2108 pos
= Fnext_char_property_change (pos
, Qnil
);
2110 /* Set CHARPOS from POS, and if the final intangible character
2111 that we skipped over is also invisible, and the invisible
2112 property is `rear-sticky', perturb it to be one character
2113 later -- this ensures that point can never move to the
2114 end of an invisible/intangible/rear-sticky region. */
2115 charpos
= adjust_for_invis_intang (XINT (pos
), -1, 1, 0);
2119 bytepos
= buf_charpos_to_bytepos (current_buffer
, charpos
);
2122 if (charpos
!= original_position
)
2124 /* Set TO to the interval containing the char after CHARPOS,
2125 and TOPREV to the interval containing the char before CHARPOS.
2126 Either one may be null. They may be equal. */
2127 to
= find_interval (BUF_INTERVALS (current_buffer
), charpos
);
2128 if (charpos
== BEGV
)
2130 else if (to
&& to
->position
== charpos
)
2131 toprev
= previous_interval (to
);
2136 /* Here TO is the interval after the stopping point
2137 and TOPREV is the interval before the stopping point.
2138 One or the other may be null. */
2140 temp_set_point_both (current_buffer
, charpos
, bytepos
);
2142 /* We run point-left and point-entered hooks here, if the
2143 two intervals are not equivalent. These hooks take
2144 (old_point, new_point) as arguments. */
2145 if (NILP (Vinhibit_point_motion_hooks
)
2146 && (! intervals_equal (from
, to
)
2147 || ! intervals_equal (fromprev
, toprev
)))
2149 Lisp_Object leave_after
, leave_before
, enter_after
, enter_before
;
2152 leave_before
= textget (fromprev
->plist
, Qpoint_left
);
2154 leave_before
= Qnil
;
2157 leave_after
= textget (from
->plist
, Qpoint_left
);
2162 enter_before
= textget (toprev
->plist
, Qpoint_entered
);
2164 enter_before
= Qnil
;
2167 enter_after
= textget (to
->plist
, Qpoint_entered
);
2171 if (! EQ (leave_before
, enter_before
) && !NILP (leave_before
))
2172 call2 (leave_before
, make_number (old_position
),
2173 make_number (charpos
));
2174 if (! EQ (leave_after
, enter_after
) && !NILP (leave_after
))
2175 call2 (leave_after
, make_number (old_position
),
2176 make_number (charpos
));
2178 if (! EQ (enter_before
, leave_before
) && !NILP (enter_before
))
2179 call2 (enter_before
, make_number (old_position
),
2180 make_number (charpos
));
2181 if (! EQ (enter_after
, leave_after
) && !NILP (enter_after
))
2182 call2 (enter_after
, make_number (old_position
),
2183 make_number (charpos
));
2187 /* Move point to POSITION, unless POSITION is inside an intangible
2188 segment that reaches all the way to point. */
2191 move_if_not_intangible (EMACS_INT position
)
2194 Lisp_Object intangible_propval
;
2196 XSETINT (pos
, position
);
2198 if (! NILP (Vinhibit_point_motion_hooks
))
2199 /* If intangible is inhibited, always move point to POSITION. */
2201 else if (PT
< position
&& XINT (pos
) < ZV
)
2203 /* We want to move forward, so check the text before POSITION. */
2205 intangible_propval
= Fget_char_property (pos
,
2208 /* If following char is intangible,
2209 skip back over all chars with matching intangible property. */
2210 if (! NILP (intangible_propval
))
2211 while (XINT (pos
) > BEGV
2212 && EQ (Fget_char_property (make_number (XINT (pos
) - 1),
2214 intangible_propval
))
2215 pos
= Fprevious_char_property_change (pos
, Qnil
);
2217 else if (XINT (pos
) > BEGV
)
2219 /* We want to move backward, so check the text after POSITION. */
2221 intangible_propval
= Fget_char_property (make_number (XINT (pos
) - 1),
2224 /* If following char is intangible,
2225 skip forward over all chars with matching intangible property. */
2226 if (! NILP (intangible_propval
))
2227 while (XINT (pos
) < ZV
2228 && EQ (Fget_char_property (pos
, Qintangible
, Qnil
),
2229 intangible_propval
))
2230 pos
= Fnext_char_property_change (pos
, Qnil
);
2233 else if (position
< BEGV
)
2235 else if (position
> ZV
)
2238 /* If the whole stretch between PT and POSITION isn't intangible,
2239 try moving to POSITION (which means we actually move farther
2240 if POSITION is inside of intangible text). */
2242 if (XINT (pos
) != PT
)
2246 /* If text at position POS has property PROP, set *VAL to the property
2247 value, *START and *END to the beginning and end of a region that
2248 has the same property, and return 1. Otherwise return 0.
2250 OBJECT is the string or buffer to look for the property in;
2251 nil means the current buffer. */
2254 get_property_and_range (EMACS_INT pos
, Lisp_Object prop
, Lisp_Object
*val
,
2255 EMACS_INT
*start
, EMACS_INT
*end
, Lisp_Object object
)
2257 INTERVAL i
, prev
, next
;
2260 i
= find_interval (BUF_INTERVALS (current_buffer
), pos
);
2261 else if (BUFFERP (object
))
2262 i
= find_interval (BUF_INTERVALS (XBUFFER (object
)), pos
);
2263 else if (STRINGP (object
))
2264 i
= find_interval (STRING_INTERVALS (object
), pos
);
2268 if (NULL_INTERVAL_P (i
) || (i
->position
+ LENGTH (i
) <= pos
))
2270 *val
= textget (i
->plist
, prop
);
2274 next
= i
; /* remember it in advance */
2275 prev
= previous_interval (i
);
2276 while (! NULL_INTERVAL_P (prev
)
2277 && EQ (*val
, textget (prev
->plist
, prop
)))
2278 i
= prev
, prev
= previous_interval (prev
);
2279 *start
= i
->position
;
2281 next
= next_interval (i
);
2282 while (! NULL_INTERVAL_P (next
)
2283 && EQ (*val
, textget (next
->plist
, prop
)))
2284 i
= next
, next
= next_interval (next
);
2285 *end
= i
->position
+ LENGTH (i
);
2290 /* Return the proper local keymap TYPE for position POSITION in
2291 BUFFER; TYPE should be one of `keymap' or `local-map'. Use the map
2292 specified by the PROP property, if any. Otherwise, if TYPE is
2293 `local-map' use BUFFER's local map.
2295 POSITION must be in the accessible part of BUFFER. */
2298 get_local_map (register EMACS_INT position
, register struct buffer
*buffer
,
2301 Lisp_Object prop
, lispy_position
, lispy_buffer
;
2302 EMACS_INT old_begv
, old_zv
, old_begv_byte
, old_zv_byte
;
2304 /* Perhaps we should just change `position' to the limit. */
2305 if (position
> BUF_ZV (buffer
) || position
< BUF_BEGV (buffer
))
2308 /* Ignore narrowing, so that a local map continues to be valid even if
2309 the visible region contains no characters and hence no properties. */
2310 old_begv
= BUF_BEGV (buffer
);
2311 old_zv
= BUF_ZV (buffer
);
2312 old_begv_byte
= BUF_BEGV_BYTE (buffer
);
2313 old_zv_byte
= BUF_ZV_BYTE (buffer
);
2315 SET_BUF_BEGV_BOTH (buffer
, BUF_BEG (buffer
), BUF_BEG_BYTE (buffer
));
2316 SET_BUF_ZV_BOTH (buffer
, BUF_Z (buffer
), BUF_Z_BYTE (buffer
));
2318 XSETFASTINT (lispy_position
, position
);
2319 XSETBUFFER (lispy_buffer
, buffer
);
2320 /* First check if the CHAR has any property. This is because when
2321 we click with the mouse, the mouse pointer is really pointing
2322 to the CHAR after POS. */
2323 prop
= Fget_char_property (lispy_position
, type
, lispy_buffer
);
2324 /* If not, look at the POS's properties. This is necessary because when
2325 editing a field with a `local-map' property, we want insertion at the end
2326 to obey the `local-map' property. */
2328 prop
= get_pos_property (lispy_position
, type
, lispy_buffer
);
2330 SET_BUF_BEGV_BOTH (buffer
, old_begv
, old_begv_byte
);
2331 SET_BUF_ZV_BOTH (buffer
, old_zv
, old_zv_byte
);
2333 /* Use the local map only if it is valid. */
2334 prop
= get_keymap (prop
, 0, 0);
2338 if (EQ (type
, Qkeymap
))
2341 return BVAR (buffer
, keymap
);
2344 /* Produce an interval tree reflecting the intervals in
2345 TREE from START to START + LENGTH.
2346 The new interval tree has no parent and has a starting-position of 0. */
2349 copy_intervals (INTERVAL tree
, EMACS_INT start
, EMACS_INT length
)
2351 register INTERVAL i
, new, t
;
2352 register EMACS_INT got
, prevlen
;
2354 if (NULL_INTERVAL_P (tree
) || length
<= 0)
2355 return NULL_INTERVAL
;
2357 i
= find_interval (tree
, start
);
2358 if (NULL_INTERVAL_P (i
) || LENGTH (i
) == 0)
2361 /* If there is only one interval and it's the default, return nil. */
2362 if ((start
- i
->position
+ 1 + length
) < LENGTH (i
)
2363 && DEFAULT_INTERVAL_P (i
))
2364 return NULL_INTERVAL
;
2366 new = make_interval ();
2368 got
= (LENGTH (i
) - (start
- i
->position
));
2369 new->total_length
= length
;
2370 CHECK_TOTAL_LENGTH (new);
2371 copy_properties (i
, new);
2375 while (got
< length
)
2377 i
= next_interval (i
);
2378 t
= split_interval_right (t
, prevlen
);
2379 copy_properties (i
, t
);
2380 prevlen
= LENGTH (i
);
2384 return balance_an_interval (new);
2387 /* Give STRING the properties of BUFFER from POSITION to LENGTH. */
2390 copy_intervals_to_string (Lisp_Object string
, struct buffer
*buffer
,
2391 EMACS_INT position
, EMACS_INT length
)
2393 INTERVAL interval_copy
= copy_intervals (BUF_INTERVALS (buffer
),
2395 if (NULL_INTERVAL_P (interval_copy
))
2398 SET_INTERVAL_OBJECT (interval_copy
, string
);
2399 STRING_SET_INTERVALS (string
, interval_copy
);
2402 /* Return 1 if strings S1 and S2 have identical properties; 0 otherwise.
2403 Assume they have identical characters. */
2406 compare_string_intervals (Lisp_Object s1
, Lisp_Object s2
)
2410 EMACS_INT end
= SCHARS (s1
);
2412 i1
= find_interval (STRING_INTERVALS (s1
), 0);
2413 i2
= find_interval (STRING_INTERVALS (s2
), 0);
2417 /* Determine how far we can go before we reach the end of I1 or I2. */
2418 EMACS_INT len1
= (i1
!= 0 ? INTERVAL_LAST_POS (i1
) : end
) - pos
;
2419 EMACS_INT len2
= (i2
!= 0 ? INTERVAL_LAST_POS (i2
) : end
) - pos
;
2420 EMACS_INT distance
= min (len1
, len2
);
2422 /* If we ever find a mismatch between the strings,
2424 if (! intervals_equal (i1
, i2
))
2427 /* Advance POS till the end of the shorter interval,
2428 and advance one or both interval pointers for the new position. */
2430 if (len1
== distance
)
2431 i1
= next_interval (i1
);
2432 if (len2
== distance
)
2433 i2
= next_interval (i2
);
2438 /* Recursively adjust interval I in the current buffer
2439 for setting enable_multibyte_characters to MULTI_FLAG.
2440 The range of interval I is START ... END in characters,
2441 START_BYTE ... END_BYTE in bytes. */
2444 set_intervals_multibyte_1 (INTERVAL i
, int multi_flag
,
2445 EMACS_INT start
, EMACS_INT start_byte
,
2446 EMACS_INT end
, EMACS_INT end_byte
)
2448 /* Fix the length of this interval. */
2450 i
->total_length
= end
- start
;
2452 i
->total_length
= end_byte
- start_byte
;
2453 CHECK_TOTAL_LENGTH (i
);
2455 if (TOTAL_LENGTH (i
) == 0)
2457 delete_interval (i
);
2461 /* Recursively fix the length of the subintervals. */
2464 EMACS_INT left_end
, left_end_byte
;
2469 left_end_byte
= start_byte
+ LEFT_TOTAL_LENGTH (i
);
2470 left_end
= BYTE_TO_CHAR (left_end_byte
);
2472 temp
= CHAR_TO_BYTE (left_end
);
2474 /* If LEFT_END_BYTE is in the middle of a character,
2475 adjust it and LEFT_END to a char boundary. */
2476 if (left_end_byte
> temp
)
2478 left_end_byte
= temp
;
2480 if (left_end_byte
< temp
)
2483 left_end_byte
= CHAR_TO_BYTE (left_end
);
2488 left_end
= start
+ LEFT_TOTAL_LENGTH (i
);
2489 left_end_byte
= CHAR_TO_BYTE (left_end
);
2492 set_intervals_multibyte_1 (i
->left
, multi_flag
, start
, start_byte
,
2493 left_end
, left_end_byte
);
2497 EMACS_INT right_start_byte
, right_start
;
2503 right_start_byte
= end_byte
- RIGHT_TOTAL_LENGTH (i
);
2504 right_start
= BYTE_TO_CHAR (right_start_byte
);
2506 /* If RIGHT_START_BYTE is in the middle of a character,
2507 adjust it and RIGHT_START to a char boundary. */
2508 temp
= CHAR_TO_BYTE (right_start
);
2510 if (right_start_byte
< temp
)
2512 right_start_byte
= temp
;
2514 if (right_start_byte
> temp
)
2517 right_start_byte
= CHAR_TO_BYTE (right_start
);
2522 right_start
= end
- RIGHT_TOTAL_LENGTH (i
);
2523 right_start_byte
= CHAR_TO_BYTE (right_start
);
2526 set_intervals_multibyte_1 (i
->right
, multi_flag
,
2527 right_start
, right_start_byte
,
2531 /* Rounding to char boundaries can theoretically ake this interval
2532 spurious. If so, delete one child, and copy its property list
2533 to this interval. */
2534 if (LEFT_TOTAL_LENGTH (i
) + RIGHT_TOTAL_LENGTH (i
) >= TOTAL_LENGTH (i
))
2538 (i
)->plist
= (i
)->left
->plist
;
2539 (i
)->left
->total_length
= 0;
2540 delete_interval ((i
)->left
);
2544 (i
)->plist
= (i
)->right
->plist
;
2545 (i
)->right
->total_length
= 0;
2546 delete_interval ((i
)->right
);
2551 /* Update the intervals of the current buffer
2552 to fit the contents as multibyte (if MULTI_FLAG is 1)
2553 or to fit them as non-multibyte (if MULTI_FLAG is 0). */
2556 set_intervals_multibyte (int multi_flag
)
2558 if (BUF_INTERVALS (current_buffer
))
2559 set_intervals_multibyte_1 (BUF_INTERVALS (current_buffer
), multi_flag
,
2560 BEG
, BEG_BYTE
, Z
, Z_BYTE
);