minimalist_grammar_parser/parsing/
trees.rs

1use std::{borrow::Borrow, cmp::Ordering};
2
3use itertools::Itertools;
4use petgraph::graph::NodeIndex;
5
6use crate::Direction;
7use bitvec::prelude::*;
8use thin_vec::ThinVec;
9
10use super::RuleIndex;
11
12pub const N_CHUNKS: u32 = 128 / usize::BITS;
13type IndexArray = BitArray<[usize; N_CHUNKS as usize], Lsb0>;
14
15///A compile time limitation on the maximum number of steps in a derivation (set to 128).
16pub const MAX_STEPS: usize = (usize::BITS * N_CHUNKS) as usize;
17
18///A Gorn Address which marks the path to a node in a tree.
19///For example, [] is root, [1] is the second child and [1,0] is the first child of the second child
20///of the root.
21#[derive(Default, Copy, Clone, PartialEq, Eq, Hash)]
22pub struct GornIndex {
23    index: IndexArray,
24    size: usize,
25}
26
27impl std::fmt::Debug for GornIndex {
28    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
29        f.debug_list()
30            .entries(
31                self.index[..self.size]
32                    .iter()
33                    .map(|x| {
34                        let x: bool = *x.as_ref();
35                        let x: u8 = x.into();
36                        x
37                    })
38                    .collect::<Vec<_>>(),
39            )
40            .finish()
41    }
42}
43
44impl std::fmt::Display for GornIndex {
45    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
46        write!(
47            f,
48            "{}",
49            self.index[..self.size]
50                .iter()
51                .map(|x| if *x { "1" } else { "0" })
52                .join("")
53        )
54    }
55}
56
57impl PartialOrd for GornIndex {
58    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
59        Some(self.cmp(other))
60    }
61}
62
63impl Ord for GornIndex {
64    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
65        self.index[..self.size].cmp(&other.index[..other.size])
66    }
67}
68
69impl Iterator for GornIterator {
70    type Item = Direction;
71
72    fn next(&mut self) -> Option<Self::Item> {
73        if self.pos < self.gorn.size {
74            let d = self.gorn.index[self.pos];
75            self.pos += 1;
76            Some(d.into())
77        } else {
78            None
79        }
80    }
81}
82
83#[derive(Default, Clone, PartialEq, Eq, Hash)]
84pub struct GornIterator {
85    pos: usize,
86    gorn: GornIndex,
87}
88
89impl IntoIterator for GornIndex {
90    type Item = Direction;
91
92    type IntoIter = GornIterator;
93
94    fn into_iter(self) -> Self::IntoIter {
95        GornIterator { pos: 0, gorn: self }
96    }
97}
98
99impl<T> From<T> for GornIndex
100where
101    T: Borrow<[Direction]>,
102{
103    fn from(value: T) -> Self {
104        let value = value.borrow();
105        let size = value.len();
106        let mut index = IndexArray::default();
107        value
108            .iter()
109            .enumerate()
110            .for_each(|(i, &x)| index.set(i, x.into()));
111        GornIndex { index, size }
112    }
113}
114impl From<GornIndex> for Vec<Direction> {
115    fn from(value: GornIndex) -> Self {
116        value
117            .index
118            .into_iter()
119            .take(value.size)
120            .map(std::convert::Into::into)
121            .collect()
122    }
123}
124
125impl GornIndex {
126    ///Take a [`GornIndex`] and add a child with [`Direction`] `d`.
127    #[inline]
128    #[must_use]
129    pub fn clone_push(&self, d: Direction) -> Self {
130        let mut v = *self;
131        v.index.set(v.size, d.into());
132        v.size += 1;
133        v
134    }
135
136    ///Add a [`Direction`] to a [`GornIndex`]
137    pub fn push(&mut self, d: Direction) {
138        self.index.set(self.size, d.into());
139        self.size += 1;
140    }
141
142    ///Create a [`GornIndex`] with one [`Direction`] preset (you can use [`GornIndex::default`] for
143    ///the root).
144    #[must_use]
145    pub fn new(d: Direction) -> Self {
146        let mut v = GornIndex {
147            size: 0,
148            index: IndexArray::default(),
149        };
150        v.index.set(v.size, d.into());
151        v.size += 1;
152        v
153    }
154
155    ///How deep in the tree is this [`GornIndex`]
156    #[must_use]
157    pub fn depth(&self) -> usize {
158        self.size
159    }
160
161    ///Is `self` an ancestor of `x` ?
162    #[must_use]
163    pub fn is_ancestor_of(&self, x: GornIndex) -> bool {
164        self.size < x.size && (self.into_iter().zip(x).all(|(x, y)| x == y))
165    }
166
167    ///Is `self` the parent of `x`?
168    #[must_use]
169    pub fn is_parent_of(&self, x: GornIndex) -> bool {
170        x.size > 0 && self.size == (x.size - 1) && (self.into_iter().zip(x).all(|(x, y)| x == y))
171    }
172
173    ///Is `self` to the left of `x`?
174    #[must_use]
175    pub fn comes_before(&self, x: &GornIndex) -> bool {
176        matches!(GornIndex::infix_order(self, x), Ordering::Less)
177    }
178
179    pub(crate) fn infix_order(x: &GornIndex, y: &GornIndex) -> Ordering {
180        for (a, b) in (*x).into_iter().zip(*y) {
181            match (a, b) {
182                (Direction::Left, Direction::Right) => return Ordering::Less,
183                (Direction::Right, Direction::Left) => return Ordering::Greater,
184                _ => (),
185            }
186        }
187        match x.size.cmp(&y.size) {
188            Ordering::Less => {
189                if y.index[x.size] {
190                    // if x is a prefix of y and ys first new direction is RIGHT
191                    // then it goes right
192                    Ordering::Less
193                } else {
194                    Ordering::Greater
195                }
196            }
197            Ordering::Greater => {
198                if x.index[y.size] {
199                    Ordering::Greater
200                } else {
201                    Ordering::Less
202                }
203            }
204            Ordering::Equal => Ordering::Equal,
205        }
206    }
207
208    ///The length of the [`GornIndex`]
209    ///```
210    ///# use minimalist_grammar_parser::parsing::GornIndex;
211    ///# use minimalist_grammar_parser::Direction;
212    ///assert_eq!(GornIndex::default().len(), 0);
213    ///assert_eq!(GornIndex::from([Direction::Left, Direction::Right]).len(), 2);
214    ///```
215    #[must_use]
216    pub fn len(&self) -> usize {
217        self.size
218    }
219
220    ///Checks if the [`GornIndex`] is root.
221    #[must_use]
222    pub fn is_empty(&self) -> bool {
223        self.size == 0
224    }
225}
226
227#[derive(Debug, Copy, Clone, PartialEq, Eq)]
228pub(crate) struct FutureTree {
229    pub node: NodeIndex,
230    pub index: GornIndex,
231    pub id: RuleIndex,
232}
233
234impl PartialOrd for FutureTree {
235    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
236        Some(self.cmp(other))
237    }
238}
239
240impl Ord for FutureTree {
241    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
242        match self.index.cmp(&other.index) {
243            core::cmp::Ordering::Equal => {}
244            ord => return ord,
245        }
246        self.node.cmp(&other.node)
247    }
248}
249
250#[derive(Debug, Clone, PartialEq, Eq)]
251pub(crate) struct ParseMoment {
252    pub tree: FutureTree,
253    pub stolen_head: StolenHead,
254    pub movers: ThinVec<FutureTree>,
255}
256
257impl ParseMoment {
258    pub fn least_index(&self) -> &GornIndex {
259        let mut least = &self.tree.index;
260        for m in &self.movers {
261            if m.index < *least {
262                least = &m.index;
263            }
264        }
265        least
266    }
267
268    pub fn new(tree: FutureTree, movers: ThinVec<FutureTree>, stolen_head: StolenHead) -> Self {
269        ParseMoment {
270            tree,
271            stolen_head,
272            movers,
273        }
274    }
275
276    pub fn should_be_scanned(&self) -> bool {
277        self.movers.is_empty()
278    }
279}
280
281impl PartialOrd for ParseMoment {
282    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
283        Some(self.cmp(other))
284    }
285}
286
287impl Ord for ParseMoment {
288    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
289        self.stolen_head
290            .cmp(&other.stolen_head)
291            .then(self.least_index().cmp(other.least_index()))
292    }
293}
294
295#[derive(Debug, Copy, Clone, PartialEq, Eq)]
296pub enum StolenHead {
297    None,
298    Root(usize),
299    Affix {
300        rule: RuleIndex,
301        direction: Direction,
302        stealer_id: usize,
303        is_done: bool,
304    },
305}
306
307impl PartialOrd for StolenHead {
308    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
309        Some(self.cmp(other))
310    }
311}
312
313impl Ord for StolenHead {
314    fn cmp(&self, other: &Self) -> Ordering {
315        match (self, other) {
316            (StolenHead::Affix { .. }, StolenHead::None | StolenHead::Root(_)) => Ordering::Less,
317            (StolenHead::None | StolenHead::Root(_), StolenHead::Affix { .. }) => Ordering::Greater,
318            _ => Ordering::Equal,
319        }
320    }
321}
322
323impl StolenHead {
324    pub(crate) fn new_stolen(rule: RuleIndex, direction: Direction, stealer_id: usize) -> Self {
325        StolenHead::Affix {
326            rule,
327            direction,
328            stealer_id,
329            is_done: false,
330        }
331    }
332
333    pub(crate) fn with_done(self) -> Self {
334        match self {
335            StolenHead::None => StolenHead::None,
336            StolenHead::Root(x) => StolenHead::Root(x),
337            StolenHead::Affix {
338                rule,
339                direction,
340                stealer_id,
341                ..
342            } => StolenHead::Affix {
343                rule,
344                direction,
345                stealer_id,
346                is_done: true,
347            },
348        }
349    }
350
351    pub(crate) fn with_not_done(self) -> Self {
352        match self {
353            StolenHead::None | StolenHead::Root(_) => panic!("These can't be finished!"),
354            StolenHead::Affix {
355                rule,
356                direction,
357                stealer_id,
358                ..
359            } => StolenHead::Affix {
360                rule,
361                direction,
362                stealer_id,
363                is_done: false,
364            },
365        }
366    }
367}
minimalist_grammar_parser/parsing/trees.rs

minimalist_grammar_parser/parsing/
trees.rs
