hyperast/position/
offsets_and_nodes.rs

1use std::fmt::Debug;
2
3use super::{tags, TreePath, TreePathMut};
4use crate::types::{HyperAST, NodeId, NodeStore, Tree, WithChildren};
5use crate::PrimInt;
6
7/// BottomUp content
8#[derive(Clone)]
9pub struct StructuralPosition<IdN, Idx, Config = tags::TopDownFull> {
10    pub(super) parents: Vec<IdN>, //parents? // most likely parents
11    pub(super) offsets: Vec<Idx>,
12    _phantom: std::marker::PhantomData<Config>,
13}
14
15impl<IdN, C, Idx> super::node_filter_traits::Full for StructuralPosition<IdN, Idx, C> {}
16
17impl<IdN: Debug, Idx: Debug> std::fmt::Debug for StructuralPosition<IdN, Idx, tags::TopDownFull> {
18    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
19        write!(f, "SP{{{:?} {:?} TopDown}}", &self.parents, &self.offsets)
20    }
21}
22
23impl<IdN: Debug, Idx: Debug> std::fmt::Debug for StructuralPosition<IdN, Idx, tags::BottomUpFull> {
24    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
25        write!(f, "SP{{{:?} {:?} BottomUp}}", &self.parents, &self.offsets)
26    }
27}
28
29impl<IdN: std::hash::Hash, C, Idx: std::hash::Hash> std::hash::Hash
30    for StructuralPosition<IdN, Idx, C>
31{
32    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
33        self.parents.last().hash(state);
34        self.parents.first().hash(state);
35        self.offsets.hash(state);
36    }
37}
38impl<IdN: std::cmp::PartialEq, C, Idx: std::cmp::PartialEq> PartialEq
39    for StructuralPosition<IdN, Idx, C>
40{
41    fn eq(&self, other: &Self) -> bool {
42        self.parents.last() == other.parents.last()
43            && self.parents.first() == other.parents.first()
44            && self.offsets == other.offsets
45    }
46}
47impl<IdN: std::cmp::Eq, C, Idx: std::cmp::Eq> Eq for StructuralPosition<IdN, Idx, C> {}
48impl<IdN: std::cmp::Eq, Idx: PrimInt> PartialOrd for StructuralPosition<IdN, Idx> {
49    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
50        Some(self.cmp(other))
51    }
52}
53impl<IdN: std::cmp::Eq, Idx: PrimInt> Ord for StructuralPosition<IdN, Idx> {
54    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
55        use crate::position::position_accessors::SharedPath;
56        use std::cmp::Ordering::*;
57        match crate::position::position_accessors::WithPreOrderOffsets::shared_ancestors(
58            self, other,
59        ) {
60            SharedPath::Exact(_) => std::cmp::Ordering::Equal,
61            SharedPath::Remain(_) => Less,
62            SharedPath::Submatch(_) => Greater,
63            SharedPath::Different(a) => {
64                let c = self.offsets[a.len() + 1].cmp(&other.offsets[a.len() + 1]);
65                assert_ne!(c, std::cmp::Ordering::Equal);
66                c
67            }
68        }
69    }
70}
71
72impl<IdN, Idx, C> StructuralPosition<IdN, Idx, C> {
73    pub fn empty() -> Self {
74        Self {
75            parents: vec![],
76            offsets: vec![],
77            _phantom: Default::default(),
78        }
79    }
80    pub fn _set_first_node(&mut self, n: IdN, o: Idx) {
81        assert!(self.parents.is_empty());
82        assert!(self.offsets.len() == 1);
83        self.parents.push(n);
84        self.offsets[0] = o;
85    }
86    pub(crate) fn solved(self, node: IdN) -> SolvedStructuralPosition<IdN, Idx, C> {
87        SolvedStructuralPosition {
88            parents: self.parents,
89            offsets: self.offsets,
90            node,
91            _phantom: Default::default(),
92        }
93    }
94
95    pub fn parent(&self) -> Option<&IdN> {
96        let i = self.parents.len().checked_sub(2)?;
97        self.parents.get(i)
98    }
99}
100
101impl<IdN, Idx: PrimInt, C> super::position_accessors::WithOffsets
102    for StructuralPosition<IdN, Idx, C>
103{
104    type Idx = Idx;
105}
106
107impl<IdN, Idx: PrimInt> super::position_accessors::WithPath<IdN> for StructuralPosition<IdN, Idx> {}
108
109impl<IdN, Idx: PrimInt> super::position_accessors::WithPreOrderOffsets
110    for StructuralPosition<IdN, Idx>
111{
112    type It<'a>
113        = SPIter<'a, Idx>
114    where
115        Idx: 'a,
116        Self: 'a;
117
118    fn iter_offsets(&self) -> Self::It<'_> {
119        let mut iter = self.offsets.iter();
120        iter.next().unwrap();
121        SPIter(iter)
122    }
123}
124
125impl<IdN, Idx: PrimInt> super::position_accessors::WithPostOrderOffsets
126    for StructuralPosition<IdN, Idx>
127{
128    fn iter(&self) -> impl Iterator<Item = Self::Idx> {
129        self.offsets[1..]
130            .iter()
131            .rev()
132            .cloned()
133            .map(|o| o - num::one())
134    }
135}
136
137impl<IdN: Copy, Idx: PrimInt> super::position_accessors::WithPostOrderPath<IdN>
138    for StructuralPosition<IdN, Idx>
139{
140    fn iter_offsets_and_parents(&self) -> impl Iterator<Item = (Self::Idx, IdN)> {
141        super::position_accessors::WithPostOrderOffsets::iter(self)
142            .zip(self.parents.iter().rev().skip(1).cloned())
143    }
144}
145
146impl<IdN: Copy, Idx: PrimInt> super::position_accessors::RootedPosition<IdN>
147    for StructuralPosition<IdN, Idx>
148{
149    fn root(&self) -> IdN {
150        self.parents.first().unwrap().clone()
151    }
152}
153
154impl<IdN: Copy, Idx: PrimInt> super::position_accessors::WithFullPostOrderPath<IdN>
155    for StructuralPosition<IdN, Idx>
156{
157    fn iter_with_nodes(&self) -> (IdN, impl Iterator<Item = (Self::Idx, IdN)>) {
158        use crate::position::position_accessors::WithPostOrderPath;
159        (*self.node().unwrap(), self.iter_offsets_and_parents())
160    }
161}
162
163impl<IdN: Copy, Idx: PrimInt> super::position_accessors::SolvedPosition<IdN>
164    for StructuralPosition<IdN, Idx>
165{
166    fn node(&self) -> IdN {
167        *TreePath::node(self).unwrap()
168    }
169}
170
171pub struct SPIter<'a, Idx>(std::slice::Iter<'a, Idx>);
172
173impl<'a, Idx: PrimInt> Iterator for SPIter<'a, Idx> {
174    type Item = Idx;
175
176    fn next(&mut self) -> Option<Self::Item> {
177        self.0.next().map(|x| *x - num::one())
178    }
179}
180
181/// BottomUp content
182#[derive(Clone, Debug)]
183pub struct SolvedStructuralPosition<IdN, Idx, Config = tags::TopDownFull> {
184    pub(super) parents: Vec<IdN>,
185    pub(super) offsets: Vec<Idx>,
186    pub(super) node: IdN,
187    _phantom: std::marker::PhantomData<Config>,
188}
189impl<IdN, Idx, C> Into<(IdN, Vec<Idx>)> for SolvedStructuralPosition<IdN, Idx, C> {
190    fn into(self) -> (IdN, Vec<Idx>) {
191        (self.node, self.offsets)
192    }
193}
194impl<IdN, Idx, C> From<SolvedStructuralPosition<IdN, Idx, C>> for StructuralPosition<IdN, Idx, C> {
195    fn from(value: SolvedStructuralPosition<IdN, Idx, C>) -> Self {
196        Self {
197            parents: value.parents,
198            offsets: value.offsets,
199            _phantom: Default::default(),
200        }
201    }
202}
203// #[derive(Clone, Debug)]
204// pub struct RootedStructuralPosition<IdN, Idx> {
205//     pub(super) nodes: Vec<IdN>,
206//     pub(super) offsets: Vec<Idx>,
207//     pub(super) root: IdN,
208// }
209
210impl<IdN: Copy, Idx: PrimInt> TreePath<IdN, Idx> for StructuralPosition<IdN, Idx> {
211    fn node(&self) -> Option<&IdN> {
212        self.parents.last()
213    }
214
215    fn offset(&self) -> Option<&Idx> {
216        self.offsets.last()
217    }
218
219    fn check<'store, HAST>(&self, stores: &'store HAST) -> Result<(), ()>
220    where
221        HAST: HyperAST<'store, IdN = IdN::IdN>,
222        HAST::T: WithChildren<ChildIdx = Idx>,
223        HAST::IdN: Eq,
224        IdN: NodeId,
225        IdN::IdN: NodeId<IdN = IdN::IdN>,
226    {
227        use num::one;
228        assert_eq!(self.offsets.len(), self.parents.len());
229        if self.parents.is_empty() {
230            return Ok(());
231        }
232        let mut i = self.parents.len() - 1;
233
234        while i > 0 {
235            let e = self.parents[i];
236            let o = self.offsets[i] - one();
237            let p = self.parents[i - 1];
238            let b = stores.node_store().resolve(&p.as_id());
239            if !b.has_children()
240                || Some(e.as_id()) != b.child(&num::cast(o).expect("too big")).as_ref()
241            {
242                return Err(());
243            }
244            i -= 1;
245        }
246        Ok(())
247    }
248}
249
250impl<IdN: Copy, Idx: PrimInt> TreePathMut<IdN, Idx> for StructuralPosition<IdN, Idx> {
251    fn pop(&mut self) -> Option<(IdN, Idx)> {
252        Some((self.parents.pop()?, self.offsets.pop()?))
253    }
254
255    fn goto(&mut self, node: IdN, i: Idx) {
256        use num::one;
257        self.parents.push(node);
258        // self.offsets.push(i);
259        // TODO remove or justify usage right here
260        self.offsets.push(i + one());
261    }
262
263    fn inc(&mut self, node: IdN) {
264        use num::one;
265        *self.parents.last_mut().unwrap() = node;
266        *self.offsets.last_mut().unwrap() += one();
267    }
268
269    fn dec(&mut self, node: IdN) {
270        use num::one;
271        *self.parents.last_mut().unwrap() = node;
272        if let Some(offsets) = self.offsets.last_mut() {
273            assert!(*offsets >= one());
274            *offsets -= one();
275        }
276    }
277}
278
279impl<IdN, Idx: num::Zero, C> StructuralPosition<IdN, Idx, C> {
280    pub fn new(node: IdN) -> Self {
281        Self {
282            parents: vec![node],
283            offsets: vec![num::zero()],
284            _phantom: Default::default(),
285        }
286    }
287}
288
289impl<IdN, Idx: PrimInt, C> StructuralPosition<IdN, Idx, C> {
290    pub fn o(&self) -> Option<Idx> {
291        self.offsets
292            .last()
293            .and_then(|&x| x.checked_sub(&num::one()))
294    }
295}
296
297impl<IdN, Idx> From<(Vec<IdN>, Vec<Idx>, IdN)> for StructuralPosition<IdN, Idx> {
298    fn from(mut x: (Vec<IdN>, Vec<Idx>, IdN)) -> Self {
299        assert_eq!(x.0.len() + 1, x.1.len());
300        x.0.push(x.2);
301        Self {
302            parents: x.0,
303            offsets: x.1,
304            _phantom: Default::default(),
305        }
306    }
307}
308impl<IdN, Idx> From<(Vec<IdN>, Vec<Idx>)> for StructuralPosition<IdN, Idx> {
309    fn from(x: (Vec<IdN>, Vec<Idx>)) -> Self {
310        assert_eq!(x.0.len(), x.1.len());
311        Self {
312            parents: x.0,
313            offsets: x.1,
314            _phantom: Default::default(),
315        }
316    }
317}
318impl<IdN, Idx: num::Zero> From<IdN> for StructuralPosition<IdN, Idx> {
319    fn from(node: IdN) -> Self {
320        Self::new(node)
321    }
322}
323
324mod impl_c_p_p_receivers {
325
326    use super::super::building;
327    use super::PrimInt;
328    use super::SolvedStructuralPosition;
329    use super::StructuralPosition;
330    use building::top_down;
331
332    impl<IdN, Idx: PrimInt, C> top_down::CreateBuilder for StructuralPosition<IdN, Idx, C> {
333        fn create() -> Self {
334            Self {
335                offsets: vec![],
336                parents: vec![],
337                _phantom: Default::default(),
338            }
339        }
340    }
341
342    impl<IdN, Idx: PrimInt, C> top_down::ReceiveParent<IdN, Self> for StructuralPosition<IdN, Idx, C> {
343        fn push(self, _parent: IdN) -> Self {
344            self
345        }
346    }
347
348    impl<IdN, Idx: PrimInt, C> building::top_down::ReceiveDirName<Self>
349        for StructuralPosition<IdN, Idx, C>
350    {
351        fn push(self, _dir_name: &str) -> Self {
352            self
353        }
354    }
355
356    impl<IdN, Idx: PrimInt, C> building::bottom_up::ReceiveDirName<Self>
357        for StructuralPosition<IdN, Idx, C>
358    {
359        fn push(self, _dir_name: &str) -> Self {
360            self
361        }
362    }
363
364    // impl<IdN, Idx: PrimInt, C> top_down::ReceiveIdx<Idx, Self> for SolvedStructuralPosition<IdN, Idx, C> {
365    //     fn push(mut self, idx: Idx) -> Self {
366    //         self.offsets.push(idx);
367    //         self
368    //     }
369    // }
370
371    impl<IdN, Idx: PrimInt, C> building::top_down::ReceiveIdx<Idx, Self>
372        for StructuralPosition<IdN, Idx, C>
373    {
374        fn push(self, _idx: Idx) -> Self {
375            // self.offsets.push(idx);
376            self
377        }
378    }
379
380    // impl<IdN, Idx: PrimInt, C> top_down::ReceiveIdxNoSpace<Idx, Self> for SolvedStructuralPosition<IdN, Idx, C> {
381    //     fn push(self, _idx: Idx) -> Self {
382    //         //self.offsets.push(idx);
383    //         self
384    //     }
385    // }
386
387    impl<IdN, Idx: PrimInt, C> building::top_down::ReceiveIdxNoSpace<Idx, Self>
388        for StructuralPosition<IdN, Idx, C>
389    {
390        fn push(mut self, idx: Idx) -> Self {
391            self.offsets.push(idx);
392            self
393        }
394    }
395
396    impl<IdN, Idx: PrimInt, C> top_down::FileSysReceiver for StructuralPosition<IdN, Idx, C> {
397        type InFile<O> = Self;
398    }
399
400    impl<IdN, Idx: PrimInt, IdO, C> building::top_down::ReceiveOffset<IdO, Self>
401        for StructuralPosition<IdN, Idx, C>
402    {
403        fn push(self, _bytes: IdO) -> Self {
404            self
405        }
406    }
407    impl<IdN, Idx: PrimInt, IdO, C> building::SetLen<IdO, Self> for StructuralPosition<IdN, Idx, C> {
408        fn set(self, _len: IdO) -> Self {
409            self
410        }
411    }
412    // impl<IdN, Idx: PrimInt, C> top_down::SetNode<IdN, SolvedStructuralPosition<IdN, Idx, C>>
413    //     for StructuralPosition<IdN, Idx, C>
414    // {
415    //     fn set_node(self, node: IdN) -> SolvedStructuralPosition<IdN, Idx, C> {
416    //         self.solved(node)
417    //     }
418    // }
419    impl<IdN, Idx: PrimInt, C> top_down::SetNode<IdN, SolvedStructuralPosition<IdN, Idx, C>>
420        for StructuralPosition<IdN, Idx, C>
421    {
422        fn set_node(self, node: IdN) -> SolvedStructuralPosition<IdN, Idx, C> {
423            self.solved(node)
424        }
425    }
426    impl<IdN, Idx: PrimInt, C> top_down::SetFileName<Self> for StructuralPosition<IdN, Idx, C> {
427        fn set_file_name(self, _file_name: &str) -> Self {
428            self
429        }
430    }
431    impl<IdN, Idx: PrimInt, IdO, C> building::ReceiveRows<IdO, Self>
432        for StructuralPosition<IdN, Idx, C>
433    {
434        fn push(self, _row: IdO) -> Self {
435            self
436        }
437    }
438    impl<IdN, Idx: PrimInt, IdO, C> building::ReceiveColumns<IdO, Self>
439        for StructuralPosition<IdN, Idx, C>
440    {
441        fn push(self, _col: IdO) -> Self {
442            self
443        }
444    }
445    impl<IdN, Idx: PrimInt, C> building::Transition<Self> for StructuralPosition<IdN, Idx, C> {
446        fn transit(self) -> Self {
447            self
448        }
449    }
450}
hyperast/position/offsets_and_nodes.rs

hyperast/position/
offsets_and_nodes.rs
