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
54            .insert((start, end), val, |a, b| {
55                add_properties(*a, *b, crate::textprops::PropertySetType::Append, false, cx)
56                    .map(Slot::new)
57                    .unwrap()
58            })
59            .unwrap();
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 ObjectType::Cons(cdr) = cdr.untag() {
152            // let sym = cdr.car();
153            let cddr = cdr.cdr();
154            if let ObjectType::Cons(this) = cddr.untag() {
155                // if the second pair(p2)'s key is `sym`, remove it and put its cons(p3)
156                // right after p1.
157                // if not, then advance p1 to p2, then continue the loop
158                if eq(this.car(), sym) {
159                    set_cdr(cdr, this.cdr());
160                }
161                plist = Some(this);
162            } else {
163                // cddr is not a cons; then it should be nil
164                break;
165            }
166        }
167    }
168
169    Ok(result)
170}
171
172fn set_cdr<'ob>(this: &'ob Cons, other: Object<'ob>) -> Option<&'ob Cons> {
173    if let ObjectType::Cons(cons) = other.untag() {
174        if let ObjectType::Cons(_c) = cons.cdr().untag() {
175            this.set_cdr(cons.cdr()).ok()?;
176        }
177        return Some(cons);
178    }
179    None
180}
181
182/// Get the value of property `prop` from `plist`,
183/// which is the plist of an interval.
184/// We check for direct properties, for categories with property `prop`,
185/// and for `prop` appearing on the default-text-properties list.
186pub(crate) fn textget<'ob>(plist: Object<'ob>, prop: Object<'ob>) -> Result<Object<'ob>> {
187    lookup_char_property(plist, prop, true)
188}
189
190/// see `lookup_char_property in intervals.c`
191fn lookup_char_property<'ob>(
192    mut plist: Object<'ob>,
193    prop: Object<'ob>,
194    _is_textprop: bool,
195) -> Result<Object<'ob>> {
196    if plist.is_nil() {
197        // TODO should return default properties
198        return Ok(NIL);
199    }
200    let ObjectType::Cons(_cons) = plist.untag() else {
201        bail!(TypeError::new(Type::Cons, plist))
202    };
203
204    while let ObjectType::Cons(cons) = plist.untag() {
205        let p = cons.car();
206        let val = cons.cadr().ok_or(anyhow::anyhow!(TypeError::new(Type::Cons, prop)))?;
207        if eq(prop, p) {
208            return Ok(val);
209        }
210        match cons.cddr() {
211            Some(obj) => plist = obj,
212            None => break,
213        }
214    }
215    Ok(NIL)
216}
217
218/// An iterator that yields all intersections in a given interval range,
219/// including empty gaps between nodes.
220pub(crate) struct IntervalIntersections<'ob, 'tree> {
221    start: usize,
222    end: usize,
223    current: Option<&'tree Node<Slot<Object<'ob>>>>,
224    iterator: StackIterator<'tree, Slot<Object<'ob>>>,
225    next_start: usize,
226}
227
228impl<'ob, 'tree> IntervalIntersections<'ob, 'tree> {
229    pub(crate) fn new(tree: &'tree IntervalTree<'ob>, start: usize, end: usize) -> Self {
230        let current = tree.tree.find_intersect_min(start..end);
231        let mut iterator = StackIterator::new(&tree.tree, current.map(|n| n.key), false);
232        iterator.next(); // remove current node
233        // let next_start = current.map(|n| n.key.end).unwrap_or(start);
234        let next_start = start;
235        Self { start, end, current, iterator, next_start }
236    }
237}
238
239impl<'ob> Iterator for IntervalIntersections<'ob, '_> {
240    type Item = (std::ops::Range<usize>, Object<'ob>);
241
242    fn next(&mut self) -> Option<Self::Item> {
243        if self.next_start >= self.end {
244            return None;
245        }
246
247        // Handle gap before first node or between nodes
248        if let Some(node) = self.current {
249            if self.next_start < node.key.start {
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
257        // Handle current node
258        if let Some(node) = self.current {
259            let intersect_start = node.key.start.max(self.start);
260            let intersect_end = node.key.end.min(self.end);
261
262            if intersect_start < intersect_end {
263                let result = (intersect_start..intersect_end, *node.val);
264                self.next_start = intersect_end;
265                self.current = self.iterator.next();
266                return Some(result);
267            }
268        }
269
270        // Handle final gap after last node
271        if self.next_start < self.end {
272            let result = (self.next_start..self.end, NIL);
273            self.next_start = self.end;
274            return Some(result);
275        }
276
277        None
278    }
279}
280
281/// An iterator that yields all intersections in a given interval range in reverse order,
282/// including empty gaps between nodes.
283pub(crate) struct ReverseIntervalIntersections<'ob, 'tree> {
284    start: usize,
285    end: usize,
286    current: Option<&'tree Node<Slot<Object<'ob>>>>,
287    iterator: StackIterator<'tree, Slot<Object<'ob>>>,
288    next_end: usize,
289}
290
291impl<'ob, 'tree> ReverseIntervalIntersections<'ob, 'tree> {
292    pub(crate) fn new(tree: &'tree IntervalTree<'ob>, start: usize, end: usize) -> Self {
293        let current = tree.tree.find_intersect_max(start..end);
294        let mut iterator = StackIterator::new(&tree.tree, current.map(|n| n.key), true);
295        iterator.next(); // remove current node
296        let next_end = end;
297        Self { start, end, current, iterator, next_end }
298    }
299}
300
301impl<'ob> Iterator for ReverseIntervalIntersections<'ob, '_> {
302    type Item = (std::ops::Range<usize>, Object<'ob>);
303
304    fn next(&mut self) -> Option<Self::Item> {
305        if self.next_end <= self.start {
306            return None;
307        }
308
309        // Handle gap after last node or between nodes
310        if let Some(node) = self.current {
311            if self.next_end > node.key.end {
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
319        // Handle current node
320        if let Some(node) = self.current {
321            let intersect_start = node.key.start.max(self.start);
322            let intersect_end = node.key.end.min(self.end);
323
324            if intersect_start < intersect_end {
325                let result = (intersect_start..intersect_end, *node.val);
326                self.next_end = intersect_start;
327                self.current = self.iterator.next();
328                return Some(result);
329            }
330        }
331
332        // Handle initial gap before first node
333        if self.next_end > self.start {
334            let result = (self.start..self.next_end, NIL);
335            self.next_end = self.start;
336            return Some(result);
337        }
338
339        None
340    }
341}
342
343/// set `this`'s cdr to `other`'s cddr. i.e., skip a pair in an alist
344#[cfg(test)]
345mod tests {
346    use rune_core::macros::list;
347
348    use super::*;
349    use crate::{RootSet, intern};
350
351    #[test]
352    fn test_remove_sym_from_props() {
353        let roots = &RootSet::default();
354        let cx = Context::new(roots);
355        let sym = intern("foo", &cx);
356        let props = list![ sym, 1, intern("bar", &cx), 2, sym, 3, intern("baz", &cx), 4; &cx];
357
358        // Create a property list: (test 1 test 2 test 3)
359        // Remove all 'test' symbols
360        let result = remove_sym_from_props(sym.into(), props).unwrap();
361        let rs = result.to_string();
362        assert_eq!(rs, "(bar 2 baz 4)".to_string());
363    }
364}
365
366#[cfg(test)]
367mod reverse_interval_iterator_tests {
368    use super::*;
369    use crate::{RootSet, intern};
370
371    #[test]
372    fn test_empty_tree() {
373        let tree = IntervalTree::new();
374
375        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 100);
376        assert_eq!(iter.next(), Some((0..100, NIL)));
377        assert_eq!(iter.next(), None);
378    }
379
380    #[test]
381    fn test_single_interval() {
382        let roots = &RootSet::default();
383        let cx = Context::new(roots);
384        let val = intern("test", &cx);
385        let mut tree = IntervalTree::new();
386        tree.insert(10, 20, Slot::new(val.into()), &cx);
387
388        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 30);
389        assert_eq!(iter.next(), Some((20..30, NIL)));
390        assert_eq!(iter.next(), Some((10..20, val.into())));
391        assert_eq!(iter.next(), Some((0..10, NIL)));
392        assert_eq!(iter.next(), None);
393    }
394
395    #[test]
396    fn test_multiple_intervals() {
397        let roots = &RootSet::default();
398        let cx = Context::new(roots);
399        let val1 = intern("test1", &cx);
400        let val2 = intern("test2", &cx);
401        let mut tree = IntervalTree::new();
402        tree.insert(10, 20, Slot::new(val1.into()), &cx);
403        tree.insert(25, 35, Slot::new(val2.into()), &cx);
404
405        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 40);
406        assert_eq!(iter.next(), Some((35..40, NIL)));
407        assert_eq!(iter.next(), Some((25..35, val2.into())));
408        assert_eq!(iter.next(), Some((20..25, NIL)));
409        assert_eq!(iter.next(), Some((10..20, val1.into())));
410        assert_eq!(iter.next(), Some((0..10, NIL)));
411        assert_eq!(iter.next(), None);
412    }
413
414    #[test]
415    fn test_overlapping_intervals() {
416        let roots = &RootSet::default();
417        let cx = Context::new(roots);
418        let val1 = intern("test1", &cx);
419        let val2 = intern("test2", &cx);
420        let mut tree = IntervalTree::new();
421        tree.insert(10, 20, Slot::new(val1.into()), &cx);
422        tree.insert(20, 30, Slot::new(val1.into()), &cx);
423        tree.insert(30, 40, Slot::new(val2.into()), &cx);
424
425        let mut iter = ReverseIntervalIntersections::new(&tree, 0, 50);
426        assert_eq!(iter.next(), Some((40..50, NIL)));
427        assert_eq!(iter.next(), Some((30..40, val2.into())));
428        assert_eq!(iter.next(), Some((20..30, val1.into())));
429        assert_eq!(iter.next(), Some((10..20, val1.into())));
430        assert_eq!(iter.next(), Some((0..10, NIL)));
431        assert_eq!(iter.next(), None);
432    }
433}
434
435#[cfg(test)]
436mod interval_iterator_tests {
437    use super::*;
438    use crate::{RootSet, intern};
439
440    #[test]
441    fn test_empty_tree() {
442        let tree = IntervalTree::new();
443
444        let mut iter = IntervalIntersections::new(&tree, 0, 100);
445        assert_eq!(iter.next(), Some((0..100, NIL)));
446        assert_eq!(iter.next(), None);
447    }
448
449    #[test]
450    fn test_single_interval() {
451        let roots = &RootSet::default();
452        let cx = Context::new(roots);
453        let val = intern("test", &cx);
454        let mut tree = IntervalTree::new();
455        tree.insert(10, 20, Slot::new(val.into()), &cx);
456
457        let mut iter = IntervalIntersections::new(&tree, 0, 30);
458        assert_eq!(iter.next(), Some((0..10, NIL)));
459        assert_eq!(iter.next(), Some((10..20, val.into())));
460        assert_eq!(iter.next(), Some((20..30, NIL)));
461        assert_eq!(iter.next(), None);
462    }
463
464    #[test]
465    fn test_multiple_intervals() {
466        let roots = &RootSet::default();
467        let cx = Context::new(roots);
468        let val1 = intern("test1", &cx);
469        let val2 = intern("test2", &cx);
470        let mut tree = IntervalTree::new();
471        tree.insert(10, 20, Slot::new(val1.into()), &cx);
472        tree.insert(25, 35, Slot::new(val2.into()), &cx);
473
474        let mut iter = IntervalIntersections::new(&tree, 0, 40);
475        assert_eq!(iter.next(), Some((0..10, NIL)));
476        assert_eq!(iter.next(), Some((10..20, val1.into())));
477        assert_eq!(iter.next(), Some((20..25, NIL)));
478        assert_eq!(iter.next(), Some((25..35, val2.into())));
479        assert_eq!(iter.next(), Some((35..40, NIL)));
480        assert_eq!(iter.next(), None);
481    }
482
483    #[test]
484    fn test_overlapping_intervals() {
485        let roots = &RootSet::default();
486        let cx = Context::new(roots);
487        let val1 = intern("test1", &cx);
488        let val2 = intern("test2", &cx);
489        let mut tree = IntervalTree::new();
490        tree.insert(10, 20, Slot::new(val1.into()), &cx);
491        tree.insert(20, 30, Slot::new(val1.into()), &cx);
492        tree.insert(30, 40, Slot::new(val2.into()), &cx);
493        // tree.tree.print();
494
495        let mut iter = IntervalIntersections::new(&tree, 0, 50);
496        assert_eq!(iter.next(), Some((0..10, NIL)));
497        assert_eq!(iter.next(), Some((10..20, val1.into())));
498        assert_eq!(iter.next(), Some((20..30, val1.into())));
499        assert_eq!(iter.next(), Some((30..40, val2.into())));
500        assert_eq!(iter.next(), Some((40..50, NIL)));
501        assert_eq!(iter.next(), None);
502    }
503}
rune/intervals.rs

rune/
intervals.rs
