rune/
intervals.rs

Help
1use anyhow::{Result, bail};
2use interval_tree::{IntervalTree as Tree, Node, StackIterator};
3
4use crate::{
5    Context,
6    core::{
7        cons::Cons,
8        error::{Type, TypeError},
9        gc::{IntoRoot, Slot, Trace},
10        object::{NIL, Object, ObjectType, TagType, WithLifetime},
11    },
12    fns::eq,
13    textprops::add_properties,
14};
15
16#[derive(Debug)]
17pub struct IntervalTree<'ob> {
18    pub tree: Tree<Slot<Object<'ob>>>,
19}
20
21impl Trace for IntervalTree<'_> {
22    fn trace(&self, state: &mut crate::core::gc::GcState) {
23        self.tree.apply(&mut |x| x.trace(state));
24    }
25}
26
27impl<'new> IntoRoot<IntervalTree<'new>> for IntervalTree<'_> {
28    unsafe fn into_root(self) -> IntervalTree<'new> {
29        self.with_lifetime()
30    }
31}
32
33impl<'new> WithLifetime<'new> for IntervalTree<'_> {
34    type Out = IntervalTree<'new>;
35    unsafe fn with_lifetime(self) -> IntervalTree<'new> {
36        let result: IntervalTree<'new> = std::mem::transmute(self);
37        result
38    }
39}
40
41unsafe impl Send for IntervalTree<'_> {}
42
43impl<'ob> IntervalTree<'ob> {
44    pub fn new() -> Self {
45        IntervalTree { tree: Tree::new() }
46    }
47
48    /// Inserts a new interval with the specified range and value into the interval tree.
49    ///
50    /// If the interval overlaps with existing intervals, their properties will be merged
51    /// using `add_properties`. The resulting object will be stored in the tree.
52    pub fn insert(&mut self, start: usize, end: usize, val: Slot<Object<'ob>>, cx: &'ob Context) {
53        self.tree.insert((start, end), val, |a, b| {
54            add_properties(*a, *b, crate::textprops::PropertySetType::Append, false, cx)
55                .map(Slot::new)
56                .unwrap()
57        });
58        // Ensure canonical form after insertion so adjacent equal intervals are merged
59        self.clean();
60    }
61
62    pub fn set_properties(&mut self, start: usize, end: usize, properties: Object<'ob>) {
63        self.tree.insert((start, end), Slot::new(properties), |a, _b| a).unwrap();
64    }
65
66    pub fn find(&self, position: usize) -> Option<&Node<Slot<Object<'ob>>>> {
67        self.tree.find(position)
68    }
69
70    /// Deletes properties from intervals within [start..end) that match properties in `list_of_props`.
71    ///
72    /// This function iterates through nodes in the specified range and removes any properties
73    /// that are equal (using `eq`) to those in `list_of_props`.
74    ///
75    /// # Arguments
76    ///
77    /// * `start` - Start position of the range (inclusive)
78    /// * `end` - End position of the range (exclusive)
79    /// * `list_of_props` - The properties to delete (as an Object containing a list of properties)
80    /// * `cx` - The context used for equality testing
81    pub fn delete(&mut self, start: usize, end: usize, list_of_props: Object<'ob>) -> Result<()> {
82        let props = list_of_props.as_list()?;
83        self.tree.apply_with_split(
84            |val| {
85                let props = props.clone();
86                let mut result = *val;
87                for sym in props {
88                    let sym = sym.ok()?;
89                    result = remove_sym_from_props(sym, result).ok()?;
90                }
91                Some(unsafe { result.into_root() })
92            },
93            start..end,
94        );
95        Ok(())
96    }
97
98    pub fn clean(&mut self) {
99        self.tree.clean(|a, b| eq(**a, **b), |n| n.is_nil());
100    }
101
102    pub(crate) fn iter<'a>(&'a self, start: usize, end: usize) -> IntervalIntersections<'ob, 'a> {
103        IntervalIntersections::new(self, start, end)
104    }
105
106    pub(crate) fn iter_reverse<'a>(
107        &'a self,
108        start: usize,
109        end: usize,
110    ) -> ReverseIntervalIntersections<'ob, 'a> {
111        ReverseIntervalIntersections::new(self, start, end)
112    }
113}
114
115/// Removes all occurrences of `sym` from the property list `props`.
116///
117/// This function scans through a property list (a cons cell chain) and removes any
118/// pairs where the car matches `sym`. The property list is modified in-place.
119///
120/// # Arguments
121/// * `sym` - The symbol to remove from the property list
122/// * `props` - The property list to modify (must be a cons cell chain)
123///
124/// # Returns
125/// Returns the modified property list with all occurrences of `sym` removed.
126/// If the input is not a cons cell, returns a TypeError.
127fn remove_sym_from_props<'ob>(sym: Object<'ob>, props: Object<'ob>) -> Result<Object<'ob>> {
128    let ObjectType::Cons(props) = props.untag() else {
129        bail!(TypeError::new(Type::List, props))
130    };
131
132    // remove properties at the beginning of list
133
134    let mut plist = Some(props);
135    while let Some(cons) = plist {
136        let prop = cons.car();
137        if eq(prop, sym) {
138            plist = cons.cddr().and_then(|n| n.try_into().ok());
139            // .and_then(|cons: &Cons| cons.cdr().try_into().ok());
140        } else {
141            break;
142        }
143    }
144
145    let result = plist.map(|c| ObjectType::Cons(c).tag()).unwrap_or(NIL);
146
147    // now, first pair in this alist is ensured not to be sym. Let's call it `p1`
148    while let Some(cons) = plist {
149        println!("{cons:?}");
150        let cdr = cons.cdr();
151        if let Some(cdr) = cdr.cons() {
152            let cddr = cdr.cdr();
153            if let Some(this) = cddr.cons() {
154                // if the second pair(p2)'s key is `sym`, remove it and put its cons(p3)
155                // right after p1.
156                // if not, then advance p1 to p2, then continue the loop
157                if eq(this.car(), sym) {
158                    set_cdr(cdr, this.cdr());
159                }
160                plist = Some(this);
161            } else {
162                // cddr is not a cons; then it should be nil
163                break;
164            }
165        }
166    }
167
168    Ok(result)
169}
170
171fn set_cdr<'ob>(this: &'ob Cons, other: Object<'ob>) -> Option<&'ob Cons> {
172    if let Some(cons) = other.cons() {
173        if let Some(_c) = cons.cdr().cons() {
174            this.set_cdr(cons.cdr()).ok()?;
175        }
176        return Some(cons);
177    }
178    None
179}
180
181/// Get the value of property `prop` from `plist`,
182/// which is the plist of an interval.
183/// We check for direct properties, for categories with property `prop`,
184/// and for `prop` appearing on the default-text-properties list.
185pub(crate) fn textget<'ob>(plist: Object<'ob>, prop: Object<'ob>) -> Result<Object<'ob>> {
186    lookup_char_property(plist, prop, true)
187}
188
189/// see `lookup_char_property in intervals.c`
190fn lookup_char_property<'ob>(
191    mut plist: Object<'ob>,
192    prop: Object<'ob>,
193    _is_textprop: bool,
194) -> Result<Object<'ob>> {
195    if plist.is_nil() {
196        // TODO should return default properties
197        return Ok(NIL);
198    }
199    let ObjectType::Cons(_cons) = plist.untag() else {
200        bail!(TypeError::new(Type::Cons, plist))
201    };
202
203    while let ObjectType::Cons(cons) = plist.untag() {
204        let p = cons.car();
205        let val = cons.cadr().ok_or(anyhow::anyhow!(TypeError::new(Type::Cons, prop)))?;
206        if eq(prop, p) {
207            return Ok(val);
208        }
209        match cons.cddr() {
210            Some(obj) => plist = obj,
211            None => break,
212        }
213    }
214    Ok(NIL)
215}
216
217/// An iterator that yields all intersections in a given interval range,
218/// including empty gaps between nodes.
219pub(crate) struct IntervalIntersections<'ob, 'tree> {
220    start: usize,
221    end: usize,
222    current: Option<&'tree Node<Slot<Object<'ob>>>>,
223    iterator: StackIterator<'tree, Slot<Object<'ob>>>,
224    next_start: usize,
225}
226
227impl<'ob, 'tree> IntervalIntersections<'ob, 'tree> {
228    pub(crate) fn new(tree: &'tree IntervalTree<'ob>, start: usize, end: usize) -> Self {
229        let current = tree.tree.find_intersect_min(start..end);
230        let mut iterator = StackIterator::new(&tree.tree, current.map(|n| n.key), false);
231        iterator.next(); // remove current node
232        // let next_start = current.map(|n| n.key.end).unwrap_or(start);
233        let next_start = start;
234        Self { start, end, current, iterator, next_start }
235    }
236}
237
238impl<'ob> Iterator for IntervalIntersections<'ob, '_> {
239    type Item = (std::ops::Range<usize>, Object<'ob>);
240
241    fn next(&mut self) -> Option<Self::Item> {
242        if self.next_start >= self.end {
243            return None;
244        }
245
246        // Handle gap before first node or between nodes
247        if let Some(node) = self.current
248            && self.next_start < node.key.start
249        {
250            let gap_end = node.key.start.min(self.end);
251            let result = (self.next_start..gap_end, NIL);
252            self.next_start = gap_end;
253            return Some(result);
254        }
255
256        // Handle current node
257        if let Some(node) = self.current {
258            let intersect_start = node.key.start.max(self.start);
259            let intersect_end = node.key.end.min(self.end);
260
261            if intersect_start < intersect_end {
262                let result = (intersect_start..intersect_end, *node.val);
263                self.next_start = intersect_end;
264                self.current = self.iterator.next();
265                return Some(result);
266            }
267        }
268
269        // Handle final gap after last node
270        if self.next_start < self.end {
271            let result = (self.next_start..self.end, NIL);
272            self.next_start = self.end;
273            return Some(result);
274        }
275
276        None
277    }
278}
279
280/// An iterator that yields all intersections in a given interval range in reverse order,
281/// including empty gaps between nodes.
282pub(crate) struct ReverseIntervalIntersections<'ob, 'tree> {
283    start: usize,
284    end: usize,
285    current: Option<&'tree Node<Slot<Object<'ob>>>>,
286    iterator: StackIterator<'tree, Slot<Object<'ob>>>,
287    next_end: usize,
288}
289
290impl<'ob, 'tree> ReverseIntervalIntersections<'ob, 'tree> {
291    pub(crate) fn new(tree: &'tree IntervalTree<'ob>, start: usize, end: usize) -> Self {
292        let current = tree.tree.find_intersect_max(start..end);
293        let mut iterator = StackIterator::new(&tree.tree, current.map(|n| n.key), true);
294        iterator.next(); // remove current node
295        let next_end = end;
296        Self { start, end, current, iterator, next_end }
297    }
298}
299
300impl<'ob> Iterator for ReverseIntervalIntersections<'ob, '_> {
301    type Item = (std::ops::Range<usize>, Object<'ob>);
302
303    fn next(&mut self) -> Option<Self::Item> {
304        if self.next_end <= self.start {
305            return None;
306        }
307
308        // Handle gap after last node or between nodes
309        if let Some(node) = self.current
310            && self.next_end > node.key.end
311        {
312            let gap_start = node.key.end.max(self.start);
313            let result = (gap_start..self.next_end, NIL);
314            self.next_end = gap_start;
315            return Some(result);
316        }
317
318        // Handle current node
319        if let Some(node) = self.current {
320            let intersect_start = node.key.start.max(self.start);
321            let intersect_end = node.key.end.min(self.end);
322
323            if intersect_start < intersect_end {
324                let result = (intersect_start..intersect_end, *node.val);
325                self.next_end = intersect_start;
326                self.current = self.iterator.next();
327                return Some(result);
328            }
329        }
330
331        // Handle initial gap before first node
332        if self.next_end > self.start {
333            let result = (self.start..self.next_end, NIL);
334            self.next_end = self.start;
335            return Some(result);
336        }
337
338        None
339    }
340}
341
342/// set `this`'s cdr to `other`'s cddr. i.e., skip a pair in an alist
343#[cfg(test)]
344mod tests {
345    use rune_core::macros::list;
346
347    use super::*;
348    use crate::{RootSet, intern};
349
350    #[test]
351    fn test_remove_sym_from_props() {
352        let roots = &RootSet::default();
353        let cx = Context::new(roots);
354        let sym = intern("foo", &cx);
355        let props = list![ sym, 1, intern("bar", &cx), 2, sym, 3, intern("baz", &cx), 4; &cx];
356
357        // Create a property list: (test 1 test 2 test 3)
358        // Remove all 'test' symbols
359        let result = remove_sym_from_props(sym.into(), props).unwrap();
360        let rs = result.to_string();
361        assert_eq!(rs, "(bar 2 baz 4)".to_string());
362    }
363}
364
365#[cfg(test)]
366mod reverse_interval_iterator_tests {
367    use super::*;
368    use crate::{RootSet, intern};
369
370    #[test]
371    fn test_empty_tree() {
372        let tree = IntervalTree::new();
373
374        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 100);
375        assert_eq!(iter.next(), Some((0..100, NIL)));
376        assert_eq!(iter.next(), None);
377    }
378
379    #[test]
380    fn test_single_interval() {
381        let roots = &RootSet::default();
382        let cx = Context::new(roots);
383        let val = intern("test", &cx);
384        let mut tree = IntervalTree::new();
385        tree.insert(10, 20, Slot::new(val.into()), &cx);
386
387        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 30);
388        assert_eq!(iter.next(), Some((20..30, NIL)));
389        assert_eq!(iter.next(), Some((10..20, val.into())));
390        assert_eq!(iter.next(), Some((0..10, NIL)));
391        assert_eq!(iter.next(), None);
392    }
393
394    #[test]
395    fn test_multiple_intervals() {
396        let roots = &RootSet::default();
397        let cx = Context::new(roots);
398        let val1 = intern("test1", &cx);
399        let val2 = intern("test2", &cx);
400        let mut tree = IntervalTree::new();
401        tree.insert(10, 20, Slot::new(val1.into()), &cx);
402        tree.insert(25, 35, Slot::new(val2.into()), &cx);
403
404        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 40);
405        assert_eq!(iter.next(), Some((35..40, NIL)));
406        assert_eq!(iter.next(), Some((25..35, val2.into())));
407        assert_eq!(iter.next(), Some((20..25, NIL)));
408        assert_eq!(iter.next(), Some((10..20, val1.into())));
409        assert_eq!(iter.next(), Some((0..10, NIL)));
410        assert_eq!(iter.next(), None);
411    }
412
413    #[test]
414    fn test_overlapping_intervals() {
415        let roots = &RootSet::default();
416        let cx = Context::new(roots);
417        let val1 = intern("test1", &cx);
418        let val2 = intern("test2", &cx);
419        let mut tree = IntervalTree::new();
420        tree.insert(10, 20, Slot::new(val1.into()), &cx);
421        tree.insert(20, 30, Slot::new(val1.into()), &cx);
422        tree.insert(30, 40, Slot::new(val2.into()), &cx);
423
424        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 50);
425        assert_eq!(iter.next(), Some((40..50, NIL)));
426        assert_eq!(iter.next(), Some((30..40, val2.into())));
427        assert_eq!(iter.next(), Some((10..30, val1.into())));
428        assert_eq!(iter.next(), Some((0..10, NIL)));
429        assert_eq!(iter.next(), None);
430    }
431}
432
433#[cfg(test)]
434mod interval_iterator_tests {
435    use super::*;
436    use crate::{RootSet, intern};
437
438    #[test]
439    fn test_empty_tree() {
440        let tree = IntervalTree::new();
441
442        let mut iter = IntervalIntersections::new(&tree, 0, 100);
443        assert_eq!(iter.next(), Some((0..100, NIL)));
444        assert_eq!(iter.next(), None);
445    }
446
447    #[test]
448    fn test_single_interval() {
449        let roots = &RootSet::default();
450        let cx = Context::new(roots);
451        let val = intern("test", &cx);
452        let mut tree = IntervalTree::new();
453        tree.insert(10, 20, Slot::new(val.into()), &cx);
454
455        let mut iter = IntervalIntersections::new(&tree, 0, 30);
456        assert_eq!(iter.next(), Some((0..10, NIL)));
457        assert_eq!(iter.next(), Some((10..20, val.into())));
458        assert_eq!(iter.next(), Some((20..30, NIL)));
459        assert_eq!(iter.next(), None);
460    }
461
462    #[test]
463    fn test_multiple_intervals() {
464        let roots = &RootSet::default();
465        let cx = Context::new(roots);
466        let val1 = intern("test1", &cx);
467        let val2 = intern("test2", &cx);
468        let mut tree = IntervalTree::new();
469        tree.insert(10, 20, Slot::new(val1.into()), &cx);
470        tree.insert(25, 35, Slot::new(val2.into()), &cx);
471
472        let mut iter = IntervalIntersections::new(&tree, 0, 40);
473        assert_eq!(iter.next(), Some((0..10, NIL)));
474        assert_eq!(iter.next(), Some((10..20, val1.into())));
475        assert_eq!(iter.next(), Some((20..25, NIL)));
476        assert_eq!(iter.next(), Some((25..35, val2.into())));
477        assert_eq!(iter.next(), Some((35..40, NIL)));
478        assert_eq!(iter.next(), None);
479    }
480
481    #[test]
482    fn test_overlapping_intervals() {
483        let roots = &RootSet::default();
484        let cx = Context::new(roots);
485        let val1 = intern("test1", &cx);
486        let val2 = intern("test2", &cx);
487        let mut tree = IntervalTree::new();
488        tree.insert(10, 20, Slot::new(val1.into()), &cx);
489        tree.insert(20, 30, Slot::new(val1.into()), &cx);
490        tree.insert(30, 40, Slot::new(val2.into()), &cx);
491        // merge the tree
492        tree.clean();
493
494        let mut iter = IntervalIntersections::new(&tree, 0, 50);
495        assert_eq!(iter.next(), Some((0..10, NIL)));
496        assert_eq!(iter.next(), Some((10..30, val1.into())));
497        assert_eq!(iter.next(), Some((30..40, val2.into())));
498        assert_eq!(iter.next(), Some((40..50, NIL)));
499        assert_eq!(iter.next(), None);
500    }
501}
rune/intervals.rs

rune/
intervals.rs
