1 ;;; implentation of an interval tree
5 (defvar *text-property-default-nonsticky
* nil
6 "Alist of properties vs the corresponding non-stickinesses.
7 Each element has the form (PROPERTY . NONSTICKINESS).
9 If a character in a buffer has PROPERTY, new text inserted adjacent to
10 the character doesn't inherit PROPERTY if NONSTICKINESS is non-nil,
11 inherits it if NONSTICKINESS is nil. The front-sticky and
12 rear-nonsticky properties of the character overrides NONSTICKINESS.")
14 (defvar *char-property-alias-alist
* nil
15 "Alist of alternative properties for properties without a value.
16 Each element should look like (PROPERTY ALTERNATIVE1 ALTERNATIVE2...).
17 If a piece of text has no direct value for a particular property, then
18 this alist is consulted. If that property appears in the alist, then
19 the first non-nil value from the associated alternative properties is
22 (defvar *default-text-properties
* nil
23 "Property-list used as default values.
24 The value of a property in this list is seen as the value for every
25 character that does not have its own value for that property.")
27 (defmacro doplist
((sym val plist
&optional ret
) &body body
)
28 "Loop through each symbol value pair in PLIST executing BODY."
29 (let ((csym (gensym)))
30 `(do* ((,csym
,plist
(cddr ,csym
)))
32 (let ((,sym
(car ,csym
))
36 ;; interval node is a list: (key left right &rest plist)
38 (defun print-interval (i s d
)
40 (format s
"#S(interval ~s ~s ~s | ~s ~s)"
48 (:print-function print-interval
))
53 (parent nil
:type
(or null pstring buffer interval
))
54 (plist nil
:type list
))
56 ;; MOVITZ's defstruct doesn't create copy-interval
58 (defun copy-interval (interval)
59 (make-interval :pt
(interval-pt interval
)
60 :length
(interval-length interval
)
61 :left
(interval-left interval
)
62 :right
(interval-right interval
)
63 :parent
(interval-parent interval
)
64 :plist
(interval-plist interval
)))
66 (defun interval-has-object (interval)
67 (and (interval-parent interval
)
68 (not (typep (interval-parent interval
) 'interval
))))
70 (defun interval-has-parent (interval)
71 (and (interval-parent interval
)
72 (typep (interval-parent interval
) 'interval
)))
74 (defun check-total-length (interval)
75 (when (< (interval-length interval
) 0)
76 (error "Interval length < 0 ~a" interval
)))
78 (defun create-root-interval (object)
79 "Return a fresh interval for OBJECT."
80 (let ((i (make-interval :pt
0 :length
0 :parent object
81 :left nil
:right nil
:plist nil
)))
83 ((typep object
'buffer
)
84 (setf (intervals object
) i
85 ;; XXX: are buffer-max buffer-min the right functions to use?
86 (interval-length i
) (- (buffer-max object
) (buffer-min object
))
87 (interval-pt i
) (buffer-min object
)))
88 ((typep object
'pstring
)
89 (setf (intervals object
) i
90 (interval-length i
) (pstring-length object
))))
93 (defun plists-equal (p1 p2
)
94 "Return 1 if the two properties lists are equal, 0 otherwise."
97 (doplist (sym val p1 t
)
98 (unless (eql val
(getf p2 sym
))
99 (return-from plists-equal nil
)))))
101 (defun intervals-equal (i1 i2
)
102 "Return T if the two intervals have the same properties, NIL otherwise."
103 (plists-equal (interval-plist i1
) (interval-plist i2
)))
105 (defun lookup-char-property (plist prop textprop
)
106 (let* ((val (getf plist prop
))
107 (cat (getf plist
'category
)))
109 (return-from lookup-char-property val
))
110 ;; This is what GNU emacs does...
111 (when (and (symbolp cat
)
113 (return-from lookup-char-property
(get cat prop
)))
114 ;; Check for alternative properties
115 (let ((tail (assoc prop
*char-property-alias-alist
*)))
117 (or (find-if (lambda (p)
121 (consp *default-text-properties
*)
122 (getf *default-text-properties
* prop
)))))))
124 (defun textget (plist sym
)
125 "Get the value of property PROP from PLIST,
126 which is the plist of an interval.
127 We check for direct properties, for categories with property PROP,
128 and for PROP appearing on the default-text-properties list."
129 (lookup-char-property plist sym t
))
131 (defun split-interval-left (interval offset
)
132 (let* ((new-length offset
)
133 (new (make-interval :pt
(interval-pt interval
)
136 (incf (interval-pt interval
) offset
)
137 (if (interval-left interval
)
139 (setf (interval-left new
) (interval-left interval
)
140 (interval-parent (interval-left new
)) new
141 (interval-left interval
) new
142 (interval-length new
) (+ new-length
(interval-length (interval-left new
))))
143 (check-total-length new
)
144 (balance-an-interval new
))
146 (setf (interval-left interval
) new
147 (interval-length new
) new-length
)
148 (check-total-length new
)))
149 (balance-possible-root-interval interval
)
152 (defun split-interval-right (interval offset
)
153 (let* ((position (interval-pt interval
))
154 (new-length (- (interval-text-length interval
) offset
))
155 (new (make-interval :pt
(+ position offset
)
158 (setf (interval-parent new
) interval
)
159 (if (interval-right interval
)
161 (setf (interval-right new
) (interval-right interval
)
162 (interval-parent (interval-right interval
)) new
163 (interval-right interval
) new
164 (interval-length new
) (+ new-length
(interval-length (interval-right new
))))
165 (check-total-length new
)
166 (balance-an-interval new
))
168 (setf (interval-right interval
) new
169 (interval-length new
) new-length
)
170 (check-total-length new
)))
171 (balance-possible-root-interval interval
)
174 (defun right-child-p (root)
175 (eq root
(interval-right (interval-parent root
))))
177 (defun left-child-p (root)
178 (eq root
(interval-left (interval-parent root
))))
180 (defun interval-past-top-p (interval)
181 "Return t if INTERVAL is not an interval. Used to check when we've
182 climbed past the root interval."
183 (not (typep (interval-parent interval
) 'interval
)))
185 (defun rotate-right (interval)
186 "Assuming that a left child exists, perform the following operation:
194 (let ((old-total (interval-length interval
))
195 (b (interval-left interval
))
197 ;; Change interval's parent to point b.
198 (unless (root-interval-p interval
)
199 (if (left-child-p interval
)
200 (setf (interval-left (interval-parent interval
)) b
)
201 (setf (interval-right (interval-parent interval
)) b
)))
202 (setf (interval-parent b
) (interval-parent interval
))
203 ;; Make b the parent of a
204 (setf i
(interval-right b
)
205 (interval-right b
) interval
206 (interval-parent interval
) b
)
208 (setf (interval-left interval
) i
)
210 (setf (interval-parent i
) interval
))
211 ;; A's total length is decreased by the length of B and its left child.
212 (decf (interval-length interval
) (- (interval-length b
)
213 (left-total-length interval
)))
214 (check-total-length interval
)
215 ;; B must have the same total length of A.
216 (setf (interval-length b
) old-total
)
217 (check-total-length b
)
220 (defun rotate-left (interval)
221 "Assuming that a right child exists, perform the following operation:
229 (let ((old-total (interval-length interval
))
230 (b (interval-right interval
))
232 ;; Change interval's parent to point b.
233 (unless (root-interval-p interval
)
234 (if (left-child-p interval
)
235 (setf (interval-left (interval-parent interval
)) b
)
236 (setf (interval-right (interval-parent interval
)) b
)))
237 (setf (interval-parent b
) (interval-parent interval
))
238 ;; Make b the parent of a
239 (setf i
(interval-left b
)
240 (interval-left b
) interval
241 (interval-parent interval
) b
)
243 (setf (interval-right interval
) i
)
245 (setf (interval-parent i
) interval
))
246 ;; A's total length is decreased by the length of B and its left child.
247 (decf (interval-length interval
) (- (interval-length b
)
248 (right-total-length interval
)))
249 (check-total-length interval
)
250 ;; B must have the same total length of A.
251 (setf (interval-length b
) old-total
)
252 (check-total-length b
)
255 (defun total-length (root)
258 (interval-length root
)
261 (defun left-total-length (root)
262 (if (interval-left root
)
263 (interval-length (interval-left root
))
266 (defun right-total-length (root)
267 (if (interval-right root
)
268 (interval-length (interval-right root
))
271 (defun interval-text-length (root)
272 "The size of text represented by this interval alone. LENGTH."
274 (- (total-length root
)
275 (total-length (interval-right root
))
276 (total-length (interval-left root
)))
279 (defun balance-an-interval (i)
283 (setf old-diff
(- (left-total-length i
) (right-total-length i
)))
284 (cond ((> old-diff
0)
285 ;; Since the left child is longer, there must be one.
286 (setf new-diff
(+ (- (interval-length i
)
287 (interval-length (interval-left i
)))
288 (- (right-total-length (interval-left i
))
289 (left-total-length (interval-left i
)))))
290 (when (>= (abs new-diff
) old-diff
)
291 (return-from balance-an-interval i
))
292 (setf i
(rotate-right i
))
293 (balance-an-interval (interval-right i
)))
295 (setf new-diff
(+ (- (interval-length i
)
296 (interval-length (interval-right i
)))
297 (- (left-total-length (interval-right i
))
298 (right-total-length (interval-right i
)))))
299 (when (>= (abs new-diff
) (- old-diff
))
300 (return-from balance-an-interval i
))
301 (setf i
(rotate-left i
))
302 (balance-an-interval (interval-left i
)))
303 (t (return-from balance-an-interval i
))))))
305 (defun balance-possible-root-interval (interval)
306 (let ((has-parent nil
)
308 (when (null (interval-parent interval
))
309 (return-from balance-possible-root-interval interval
))
310 (when (interval-has-object interval
)
311 (setf parent
(interval-parent interval
)
313 (setf interval
(balance-intervals interval
))
315 (setf (intervals parent
) interval
))
318 (defun balance-intervals (tree)
319 "Balance the interval tree TREE. Balancing is by weight: the amount
321 (labels ((balance (tree)
322 (when (interval-left tree
)
323 (balance (interval-left tree
)))
324 (when (interval-right tree
)
325 (balance (interval-right tree
)))
326 (balance-an-interval tree
)))
330 (defun find-interval (tree position
)
331 (let ((relative-position position
))
333 (return-from find-interval nil
))
334 (assert (<= relative-position
(total-length tree
)))
335 (balance-possible-root-interval tree
)
337 (cond ((< relative-position
(left-total-length tree
))
338 (setf tree
(interval-left tree
)))
339 ((and (interval-right tree
)
340 (>= relative-position
(- (total-length tree
)
341 (right-total-length tree
))))
342 (decf relative-position
(- (total-length tree
)
343 (right-total-length tree
)))
344 (setf tree
(interval-right tree
)))
346 (setf (interval-pt tree
) (+ (- position relative-position
)
347 (left-total-length tree
)))
348 (return-from find-interval tree
))))))
350 (defun next-interval (interval)
351 (unless (null interval
)
353 (next-position (+ (interval-pt interval
)
354 (interval-text-length interval
))))
355 (when (interval-right interval
)
356 (setf i
(interval-right i
))
357 (loop while
(interval-left i
)
358 do
(setf i
(interval-left i
)))
359 (setf (interval-pt i
) next-position
)
360 (return-from next-interval i
))
361 (loop until
(interval-past-top-p i
)
364 (setf i
(interval-parent i
)
365 (interval-pt i
) next-position
)
366 (return-from next-interval i
))
367 do
(setf i
(interval-parent i
))))))
369 (defun previous-interval (interval)
370 (unless (null interval
)
372 (when (interval-left interval
)
373 (setf i
(interval-left i
))
374 (loop while
(interval-right i
)
375 do
(setf i
(interval-right i
)))
376 (setf (interval-pt i
) (- (interval-pt interval
)
377 (interval-text-length i
)))
378 (return-from previous-interval i
))
379 (loop until
(interval-past-top-p i
)
382 (setf i
(interval-parent i
)
383 (interval-pt i
) (- (interval-pt interval
)
384 (interval-text-length i
)))
385 (return-from previous-interval i
))
386 do
(setf i
(interval-parent i
))))))
388 (defun merge-interval-right (i)
389 (let ((absorb (interval-text-length i
))
391 (decf (interval-length i
) absorb
)
392 (check-total-length i
)
393 (when (interval-right i
)
394 (setf successor
(interval-right i
))
395 (loop while
(interval-left successor
)
397 (incf (interval-length successor
) absorb
)
398 (check-total-length successor
)
399 (setf successor
(interval-left successor
))))
400 (incf (interval-length successor
) absorb
)
401 (check-total-length successor
)
403 (return-from merge-interval-right successor
))
405 (loop while
(interval-parent successor
)
406 do
(if (left-child-p successor
)
408 (setf successor
(interval-parent successor
))
410 (return-from merge-interval-right successor
))
412 (setf successor
(interval-parent successor
))
413 (decf (interval-length successor
) absorb
)
414 (check-total-length successor
))))
415 (error "merge-interval-right: gak")))
417 (defun merge-interval-left (i)
418 (let ((absorb (interval-text-length i
))
420 (decf (interval-length i
) absorb
)
421 (check-total-length i
)
422 (when (interval-left i
)
423 (setf predecessor
(interval-left i
))
424 (loop while
(interval-right predecessor
)
425 do
(incf (interval-length predecessor
) absorb
)
426 (check-total-length predecessor
)
427 do
(setf predecessor
(interval-right predecessor
)))
428 (incf (interval-length predecessor
) absorb
)
429 (check-total-length predecessor
)
431 (return-from merge-interval-left predecessor
))
433 (loop while
(interval-parent predecessor
)
434 do
(when (interval-right predecessor
)
435 (setf predecessor
(interval-parent predecessor
))
437 (return-from merge-interval-left predecessor
))
438 do
(setf predecessor
(interval-parent predecessor
))
439 do
(decf (interval-length predecessor
) absorb
)
440 (check-total-length predecessor
)
442 (error "merge-interval-left: gak")))
445 ;; adjust_intervals_for_insertion (tree, position, length)
447 (defun adjust-intervals-for-insertion (tree position length
)
448 "Effect an adjustment corresponding to the addition of LENGTH characters
449 of text. Do this by finding the interval containing POSITION in the
450 interval tree TREE, and then adjusting all of its ancestors by adding
453 If POSITION is the first character of an interval, meaning that point
454 is actually between the two intervals, make the new text belong to
455 the interval which is \"sticky\".
457 If both intervals are \"sticky\", then make them belong to the left-most
458 interval. Another possibility would be to create a new interval for
459 this text, and make it have the merged properties of both ends."
460 (let* ((parent (interval-parent tree
))
461 (offset (if (typep parent
'buffer
)
465 ;; If inserting at point-max of a buffer, that position will be out
466 ;; of range. Remember that buffer positions are 1-based.
467 (when (>= position
(+ (total-length tree
) offset
))
468 (setf position
(+ (total-length tree
) offset
)
470 (setf i
(find-interval tree position
))
471 ;; If in middle of an interval which is not sticky either way,
472 ;; we must not just give its properties to the insertion.
473 ;; So split this interval at the insertion point.
475 ;; Originally, the if condition here was this:
476 ;; (! (position == i->position || eobp)
477 ;; && END_NONSTICKY_P (i)
478 ;; && FRONT_NONSTICKY_P (i))
479 ;; But, these macros are now unreliable because of introduction of
480 ;; Vtext_property_default_nonsticky. So, we always check properties
481 ;; one by one if POSITION is in middle of an interval.
482 (unless (or (= position
(interval-pt i
))
484 (let* ((rear (getf (interval-plist i
) 'rear-nonsticky
))
485 (front (getf (interval-plist i
) 'front-sticky
))
487 (when (or (and (not (consp rear
)) rear
)
488 (and (not (consp front
)) front
))
489 ;; All properties are nonsticky. We split the interval.
492 ;; Does any actual property pose an actual problem? We break
493 ;; the loop if we find a nonsticky property.
495 (setf problem
(do* ((tail (interval-plist i
) (cddr tail
))
496 (prop (cdr tail
) (cdr tail
)))
498 (and (not (and (consp front
)
499 (not (find prop front
))))
500 (or (and (consp rear
)
501 (not (find prop rear
)))
502 (let ((tmp (assoc prop
*text-property-default-nonsticky
*)))
503 (and (consp tmp
) tmp
)))))
505 ;; If any property is a real problem, split the interval.
507 (setf temp
(split-interval-right i
(- position
(interval-pt i
))))
508 (copy-properties i temp
)
510 ;; If we are positioned between intervals, check the stickiness of
511 ;; both of them. We have to do this too, if we are at BEG or Z.
512 (if (or (= position
(interval-pt i
))
514 (let ((prev (cond ((= position
+beg
+) nil
)
516 (t (previous-interval i
)))))
519 ;; Even if we are positioned between intervals, we default
520 ;; to the left one if it exists. We extend it now and split
521 ;; off a part later, if stickiness demands it.
522 (do ((tmp (or prev i
) (when (interval-has-parent tmp
)
523 (interval-parent tmp
))))
525 (incf (interval-length tmp
) length
)
526 ;; CHECK_TOTAL_LENGTH (temp);
527 (setf tmp
(balance-possible-root-interval tmp
)))
528 ;; If at least one interval has sticky properties, we check
529 ;; the stickiness property by property.
531 ;; Originally, the if condition here was this:
532 ;; (END_NONSTICKY_P (prev) || FRONT_STICKY_P (i))
533 ;; But, these macros are now unreliable because of introduction
534 ;; of Vtext_property_default_nonsticky. So, we always have to
535 ;; check stickiness of properties one by one. If cache of
536 ;; stickiness is implemented in the future, we may be able to
537 ;; use those macros again.
538 (let* ((pleft (when prev
539 (interval-plist prev
)))
542 (new-props (merge-properties-sticky pleft pright
)))
544 ;; /* i.e. position == BEG */
545 (unless (plists-equal (interval-plist i
) new-props
)
546 (setf i
(split-interval-left i length
)
547 (interval-plist i
) new-props
)))
548 ((not (plists-equal (interval-plist prev
) new-props
))
549 (setf prev
(split-interval-right prev
(- position
(interval-pt prev
)))
550 (interval-plist prev
) new-props
)
552 (plists-equal (interval-plist prev
) (interval-plist i
)))
553 (merge-interval-right prev
)))
555 (not (null (interval-plist i
))))
556 ;; Just split off a new interval at the left.
557 ;; Since I wasn't front-sticky, the empty plist is ok.
558 (setf i
(split-interval-left i length
))))))
559 ;; Otherwise just extend the interval.
560 (do ((tmp i
(when (interval-has-parent tmp
)
561 (interval-parent tmp
))))
563 (incf (interval-length tmp
) length
)
564 ;; CHECK_TOTAL_LENGTH (temp);
565 (setf tmp
(balance-possible-root-interval tmp
))))
568 (defun interval-deletion-adjustment (tree from amount
)
569 "Find the interval in TREE corresponding to the relative position
570 FROM and delete as much as possible of AMOUNT from that interval.
571 Return the amount actually deleted, and if the interval was
572 zeroed-out, delete that interval node from the tree.
574 Note that FROM is actually origin zero, aka relative to the
575 leftmost edge of tree. This is appropriate since we call ourselves
576 recursively on subtrees.
578 Do this by recursing down TREE to the interval in question, and
579 deleting the appropriate amount of text."
580 (let ((relative-position from
))
585 ((< relative-position
(left-total-length tree
))
586 (let ((subtract (interval-deletion-adjustment (interval-left tree
)
589 (decf (interval-length tree
) subtract
)
590 ;; CHECK_TOTAL_LENGTH
593 ((>= relative-position
(- (total-length tree
)
594 (right-total-length tree
)))
595 (decf relative-position
(- (interval-length tree
)
596 (right-total-length tree
)))
597 (let ((subtract (interval-deletion-adjustment (interval-right tree
)
600 (decf (interval-length tree
) subtract
)
601 ;; CHECK_TOTAL_LENGTH
605 ;; How much can we delete from this interval?
606 (let ((my-amount (- (interval-length tree
)
607 (right-total-length tree
)
609 (when (> amount my-amount
)
610 (setf amount my-amount
))
611 (decf (interval-length tree
) amount
)
612 ;; CHECK_TOTAL_LENGTH
613 (when (zerop (total-length tree
))
614 (delete-interval tree
))
617 (defun adjust-intervals-for-deletion (buffer start length
)
618 "Effect the adjustments necessary to the interval tree of BUFFER to
619 correspond to the deletion of LENGTH characters from that buffer
620 text. The deletion is effected at position START (which is a
621 buffer position, i.e. origin 1)."
622 (let ((left-to-delete length
)
623 (tree (intervals buffer
))
624 (offset (buffer-min buffer
)))
627 ((or (> start
(+ offset
(total-length tree
)))
628 (> (+ start length
) (+ offset
(total-length tree
))))
629 (error "gak ~a ~a ~a ~a" tree offset
(total-length tree
) length
))
630 ((= length
(total-length tree
))
631 (setf (intervals buffer
) nil
))
632 ((only-interval-p tree
)
633 (decf (interval-length tree
) length
)) ;; CHECK_TOTAL_LENGTH
635 (when (> start
(+ offset
(total-length tree
)))
636 (setf start
(+ offset
(total-length tree
))))
637 (loop while
(> left-to-delete
0) do
640 (interval-deletion-adjustment tree
(- start offset
) left-to-delete
))
641 (setf tree
(intervals buffer
))
642 (when (= left-to-delete
(interval-length tree
))
643 (setf (intervals buffer
) nil
)
646 (defun interval-start-pos (source)
647 (if (or (null source
)
648 (not (typep (interval-parent source
) 'buffer
)))
650 (buffer-min (interval-parent source
))))
652 (defun graft-intervals-into-buffer (source position length buffer inherit
)
653 "Insert the intervals of SOURCE into BUFFER at POSITION.
654 LENGTH is the length of the text in SOURCE.
656 The `position' field of the SOURCE intervals is assumed to be
657 consistent with its parent; therefore, SOURCE must be an
658 interval tree made with copy_interval or must be the whole
659 tree of a buffer or a string.
661 This is used in insdel.c when inserting Lisp_Strings into the
662 buffer. The text corresponding to SOURCE is already in the buffer
663 when this is called. The intervals of new tree are a copy of those
664 belonging to the string being inserted; intervals are never
667 If the inserted text had no intervals associated, and we don't
668 want to inherit the surrounding text's properties, this function
669 simply returns -- offset_intervals should handle placing the
670 text in the correct interval, depending on the sticky bits.
672 If the inserted text had properties (intervals), then there are two
673 cases -- either insertion happened in the middle of some interval,
674 or between two intervals.
676 If the text goes into the middle of an interval, then new
677 intervals are created in the middle with only the properties of
678 the new text, *unless* the macro MERGE_INSERTIONS is true, in
679 which case the new text has the union of its properties and those
680 of the text into which it was inserted.
682 If the text goes between two intervals, then if neither interval
683 had its appropriate sticky property set (front_sticky, rear_sticky),
684 the new text has only its properties. If one of the sticky properties
685 is set, then the new text \"sticks\" to that region and its properties
686 depend on merging as above. If both the preceding and succeeding
687 intervals to the new text are \"sticky\", then the new text retains
688 only its properties, as if neither sticky property were set. Perhaps
689 we should consider merging all three sets of properties onto the new
691 (let ((tree (intervals buffer
))
693 under over this prev
)
694 ;; /* If the new text has no properties, then with inheritance it
695 ;; becomes part of whatever interval it was inserted into.
696 ;; To prevent inheritance, we must clear out the properties
697 ;; of the newly inserted text. */
699 (when (and (not inherit
)
702 ;; XSETBUFFER (buf, buffer);
703 (set-text-properties-1 position
(+ position length
) nil buffer
0))
704 (when (intervals buffer
)
705 (setf (intervals buffer
) (balance-an-interval (intervals buffer
))))
706 (return-from graft-intervals-into-buffer
))
708 ;; /* The inserted text constitutes the whole buffer, so
709 ;; simply copy over the interval structure. */
710 (when (= (- (buffer-size buffer
) (buffer-min buffer
))
711 (total-length source
))
712 (setf (intervals buffer
) (reproduce-tree source buffer
)
713 (interval-pt (intervals buffer
)) (buffer-min buffer
))
714 (return-from graft-intervals-into-buffer
))
715 ;; /* Create an interval tree in which to place a copy
716 ;; of the intervals of the inserted string. */
717 (setf tree
(create-root-interval buffer
)))
718 ((= (total-length tree
)
719 (total-length source
))
720 ;; /* If the buffer contains only the new string, but
721 ;; there was already some interval tree there, then it may be
722 ;; some zero length intervals. Eventually, do something clever
723 ;; about inserting properly. For now, just waste the old intervals. */
724 (setf (intervals buffer
) (reproduce-tree source
(interval-parent tree
))
725 (interval-pt (intervals buffer
)) (buffer-min buffer
))
726 (return-from graft-intervals-into-buffer
))
727 ((zerop (total-length tree
))
729 (setf under
(find-interval tree position
)
731 over
(find-interval source
(interval-start-pos source
)))
732 (if (> position
(interval-pt under
))
733 (let ((end-unchanged (split-interval-left this
(- position
(interval-pt under
)))))
734 (copy-properties under end-unchanged
)
735 (setf (interval-pt under
) position
))
736 (setf prev
(previous-interval under
)))
739 (if (< (- (interval-text-length over
) over-used
)
740 (interval-text-length under
))
742 (setf this
(split-interval-left under
(- (interval-text-length over
)
744 (copy-properties under this
))
746 ;; /* THIS is now the interval to copy or merge into.
747 ;; OVER covers all of it. */
749 (merge-properties over this
)
750 (copy-properties over this
))
751 ;; /* If THIS and OVER end at the same place,
752 ;; advance OVER to a new source interval. */
753 (if (= (interval-text-length this
)
754 (- (interval-text-length over
) over-used
))
756 (setf over
(next-interval over
)
758 ;; /* Otherwise just record that more of OVER has been used. */
759 (incf over-used
(interval-text-length this
)))
760 ;; /* Always advance to a new target interval. */
761 (setf under
(next-interval this
)))
762 (when (intervals buffer
)
763 (setf (intervals buffer
) (balance-an-interval (intervals buffer
))))))
765 (defun root-interval-p (i)
766 "Return true if i is the root interval node."
767 (or (null (interval-parent i
))
768 (not (typep (interval-parent i
) 'interval
))))
770 (defun root-interval (interval)
771 "Return the root of interval."
772 (do ((i interval
(interval-parent i
)))
773 ((root-interval-p i
) i
)))
775 (defun leaf-interval-p (i)
776 "Return T if this interval has no children."
777 (and (null (interval-left i
))
778 (null (interval-right i
))))
780 (defun only-interval-p (i)
781 "Return T if this interval is the only interval in the interval tree."
782 (and (root-interval-p i
)
783 (leaf-interval-p i
)))
786 (defun delete-node (i)
788 (when (null (interval-left i
))
789 (return-from delete-node
(interval-right i
)))
790 (when (null (interval-right i
))
791 (return-from delete-node
(interval-left i
)))
793 (let ((migrate (interval-left i
))
794 (this (interval-right i
))
795 (migrate-amt (interval-length (interval-left i
))))
796 (loop while
(interval-left this
)
797 do
(setf this
(interval-left this
))
798 do
(incf (interval-length this
) migrate-amt
))
799 (check-total-length this
)
800 (setf (interval-left this
) migrate
)
801 (setf (interval-parent migrate
) this
)
804 (defun delete-interval (i)
805 (let ((amt (interval-text-length i
))
808 (error "only used on zero length intervals."))
809 (when (root-interval-p i
)
810 (let ((owner (interval-parent i
)))
811 (setf parent
(delete-node i
))
812 (when (interval-parent parent
)
813 (setf (interval-parent parent
) owner
))
814 (setf (intervals owner
) parent
)
815 (return-from delete-interval
)))
816 (setf parent
(interval-parent i
))
819 (setf (interval-left parent
) (delete-node i
))
820 (when (interval-left parent
)
821 (setf (interval-parent (interval-left parent
)) parent
)))
823 (setf (interval-right parent
) (delete-node i
))
824 (when (interval-right parent
)
825 (setf (interval-parent (interval-right parent
)) parent
))))))
827 (defun default-interval-p (i)
829 (null (interval-plist i
))))
831 (defun reproduce-tree (source parent
)
832 (let ((tree (copy-interval source
)))
833 (setf (interval-plist tree
) (copy-list (interval-plist source
))
834 (interval-parent tree
) parent
)
835 (when (interval-left source
)
836 (setf (interval-left tree
) (reproduce-tree (interval-left source
) tree
)))
837 (when (interval-right source
)
838 (setf (interval-right tree
) (reproduce-tree (interval-right source
) tree
)))
841 (defun merge-properties (source target
)
842 "/* Merge the properties of interval SOURCE into the properties of
843 interval TARGET. That is to say, each property in SOURCE is added to
844 TARGET if TARGET has no such property as yet. */"
845 (unless (and (default-interval-p source
)
846 (default-interval-p target
))
847 (doplist (sym val
(interval-plist source
))
848 (let ((found (getf (interval-plist target
) sym
)))
850 (setf (getf (interval-plist target
) sym
) val
))))))
852 (defun merge-properties-sticky (pleft pright
)
853 "Any property might be front-sticky on the left, rear-sticky on the left,
854 front-sticky on the right, or rear-sticky on the right; the 16 combinations
855 can be arranged in a matrix with rows denoting the left conditions and
856 columns denoting the right conditions:
864 left-props = '(front-sticky (p8 p9 pa pb pc pd pe pf)
865 rear-nonsticky (p4 p5 p6 p7 p8 p9 pa pb)
866 p0 L p1 L p2 L p3 L p4 L p5 L p6 L p7 L
867 p8 L p9 L pa L pb L pc L pd L pe L pf L)
868 right-props = '(front-sticky (p2 p3 p6 p7 pa pb pe pf)
869 rear-nonsticky (p1 p2 p5 p6 p9 pa pd pe)
870 p0 R p1 R p2 R p3 R p4 R p5 R p6 R p7 R
871 p8 R p9 R pa R pb R pc R pd R pe R pf R)
873 We inherit from whoever has a sticky side facing us. If both sides
874 do (cases 2, 3, E, and F), then we inherit from whichever side has a
875 non-nil value for the current property. If both sides do, then we take
878 When we inherit a property, we get its stickiness as well as its value.
879 So, when we merge the above two lists, we expect to get this:
881 result = '(front-sticky (p6 p7 pa pb pc pd pe pf)
882 rear-nonsticky (p6 pa)
883 p0 L p1 L p2 L p3 L p6 R p7 R
884 pa R pb R pc L pd L pe L pf L)
886 The optimizable special cases are:
887 left rear-nonsticky = nil, right front-sticky = nil (inherit left)
888 left rear-nonsticky = t, right front-sticky = t (inherit right)
889 left rear-nonsticky = t, right front-sticky = nil (inherit none)"
890 (labels ((tmem (sym set
)
891 ;; Test for membership, allowing for t (actually any
892 ;; non-cons) to mean the universal set."
899 (lfront (getf pleft
'front-sticky
))
900 (lrear (getf pleft
'rear-nonsticky
))
901 (rfront (getf pright
'front-sticky
))
902 (rrear (getf pright
'rear-nonsticky
))
903 cat use-left use-right
)
904 (doplist (sym rval pright
)
905 (unless (or (eq sym
'rear-nonsticky
)
906 (eq sym
'front-sticky
))
907 ;; Indicate whether the property is explicitly
908 ;; defined on the left. (We know it is defined
909 ;; explicitly on the right because otherwise we don't
911 (let* ((lval (getf pleft sym
))
912 ;; Even if lrear or rfront say nothing about the
913 ;; stickiness of SYM,
914 ;; Vtext_property_default_nonsticky may give
915 ;; default stickiness to SYM.
916 (tmp (assoc sym
*text-property-default-nonsticky
*)))
917 (setf use-left
(and lval
918 (not (or (tmem sym lrear
)
921 use-right
(or (tmem sym lrear
)
929 (setf use-right nil
))))
931 ;; We build props as (value sym ...) rather than (sym value ...)
932 ;; because we plan to nreverse it when we're done.
933 (setf (getf props sym
) lval
)
934 (when (tmem sym lfront
)
936 (when (tmem sym lrear
)
939 (setf (getf props sym
) rval
)
940 (when (tmem sym rfront
)
942 (when (tmem sym rrear
)
943 (push sym rear
)))))))
944 ;; Now go through each element of PLEFT.
945 (doplist (sym lval pleft
)
946 (unless (or (eq sym
'rear-nonsticky
)
947 (eq sym
'front-sticky
))
948 ;; If sym is in PRIGHT, we've already considered it.
949 (let* ((present (getf pright sym
))
950 ;; Even if lrear or rfront say nothing about the
951 ;; stickiness of SYM,
952 ;; Vtext_property_default_nonsticky may give
953 ;; default stickiness to SYM.
954 (tmp (assoc sym
*text-property-default-nonsticky
*)))
955 ;; XXX: if sym is set in pright to nil, its the same
956 ;; as sym not being in the list.
958 ;; Since rval is known to be nil in this loop, the test simplifies.
959 (cond ((not (or (tmem sym lrear
)
962 (setf (getf props sym
) lval
)
963 (when (tmem sym lfront
)
965 ((or (tmem sym rfront
)
968 ;; The value is nil, but we still inherit the stickiness
970 (setf (getf props sym
) lval
)
971 (when (tmem sym rrear
)
972 (push sym rear
))))))))
974 (setf (getf props
'rear-nonsticky
) (nreverse rear
)))
975 (setf cat
(textget props
'category
))
976 ;; If we have inherited a front-stick category property that is t,
977 ;; we don't need to set up a detailed one.
981 (eq (get cat
'front-sticky
) t
))))
982 (setf (getf props
'front-sticky
) (nreverse front
)))
985 (defun offset-intervals (buffer start length
)
986 "Make the adjustments necessary to the interval tree of BUFFER to
987 represent an addition or deletion of LENGTH characters starting
988 at position START. Addition or deletion is indicated by the sign
990 (unless (or (null (intervals buffer
))
993 (adjust-intervals-for-insertion (intervals buffer
) start length
)
994 (adjust-intervals-for-deletion buffer
(+ start length
) (- length
)))))
996 (provide :lice-0.1
/intervals
)