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| match *x {
52                    true => "1",
53                    false => "0",
54                })
55                .join("")
56        )
57    }
58}
59
60impl PartialOrd for GornIndex {
61    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
62        Some(self.cmp(other))
63    }
64}
65
66impl Ord for GornIndex {
67    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
68        self.index[..self.size].cmp(&other.index[..other.size])
69    }
70}
71
72impl Iterator for GornIterator {
73    type Item = Direction;
74
75    fn next(&mut self) -> Option<Self::Item> {
76        if self.pos < self.gorn.size {
77            let d = self.gorn.index[self.pos];
78            self.pos += 1;
79            Some(d.into())
80        } else {
81            None
82        }
83    }
84}
85
86#[derive(Default, Copy, Clone, PartialEq, Eq, Hash)]
87pub struct GornIterator {
88    pos: usize,
89    gorn: GornIndex,
90}
91
92impl IntoIterator for GornIndex {
93    type Item = Direction;
94
95    type IntoIter = GornIterator;
96
97    fn into_iter(self) -> Self::IntoIter {
98        GornIterator { pos: 0, gorn: self }
99    }
100}
101
102impl<T> From<T> for GornIndex
103where
104    T: Borrow<[Direction]>,
105{
106    fn from(value: T) -> Self {
107        let value = value.borrow();
108        let size = value.len();
109        let mut index = IndexArray::default();
110        value
111            .iter()
112            .enumerate()
113            .for_each(|(i, &x)| index.set(i, x.into()));
114        GornIndex { size, index }
115    }
116}
117impl From<GornIndex> for Vec<Direction> {
118    fn from(value: GornIndex) -> Self {
119        value
120            .index
121            .into_iter()
122            .take(value.size)
123            .map(|x| x.into())
124            .collect()
125    }
126}
127
128impl GornIndex {
129    ///Take a [`GornIndex`] and add a child with [`Direction`] `d`.
130    #[inline]
131    pub fn clone_push(&self, d: Direction) -> Self {
132        let mut v = *self;
133        v.index.set(v.size, d.into());
134        v.size += 1;
135        v
136    }
137
138    ///Create a [`GornIndex`] with one [`Direction`] preset (you can use [`GornIndex::default`] for
139    ///the root).
140    pub fn new(d: Direction) -> Self {
141        let mut v = GornIndex {
142            size: 0,
143            index: IndexArray::default(),
144        };
145        v.index.set(v.size, d.into());
146        v.size += 1;
147        v
148    }
149
150    ///How deep in the tree is this [`GornIndex`]
151    pub fn depth(&self) -> usize {
152        self.size
153    }
154
155    ///Is `self` an ancestor of `x` ?
156    pub fn is_ancestor_of(&self, x: GornIndex) -> bool {
157        self.size < x.size && (self.into_iter().zip(x).all(|(x, y)| x == y))
158    }
159
160    ///Is `self` the parent of `x`?
161    pub fn is_parent_of(&self, x: GornIndex) -> bool {
162        x.size > 0 && self.size == (x.size - 1) && (self.into_iter().zip(x).all(|(x, y)| x == y))
163    }
164
165    pub(crate) fn infix_order(x: &GornIndex, y: &GornIndex) -> Ordering {
166        for (a, b) in (*x).into_iter().zip(*y) {
167            match (a, b) {
168                (Direction::Left, Direction::Right) => return Ordering::Less,
169                (Direction::Right, Direction::Left) => return Ordering::Greater,
170                _ => (),
171            };
172        }
173        match x.size.cmp(&y.size) {
174            Ordering::Less => {
175                if y.index[x.size] {
176                    // if x is a prefix of y and ys first new direction is RIGHT
177                    // then it goes right
178                    Ordering::Less
179                } else {
180                    Ordering::Greater
181                }
182            }
183            Ordering::Greater => {
184                if x.index[y.size] {
185                    Ordering::Greater
186                } else {
187                    Ordering::Less
188                }
189            }
190            Ordering::Equal => Ordering::Equal,
191        }
192    }
193}
194
195#[derive(Debug, Clone, PartialEq, Eq)]
196pub(crate) struct FutureTree {
197    pub node: NodeIndex,
198    pub index: GornIndex,
199    pub id: RuleIndex,
200}
201
202impl PartialOrd for FutureTree {
203    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
204        Some(self.cmp(other))
205    }
206}
207
208impl Ord for FutureTree {
209    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
210        match self.index.cmp(&other.index) {
211            core::cmp::Ordering::Equal => {}
212            ord => return ord,
213        }
214        self.node.cmp(&other.node)
215    }
216}
217
218#[derive(Debug, Clone, PartialEq, Eq)]
219pub(crate) struct ParseMoment {
220    pub tree: FutureTree,
221    pub stolen_head: Option<StolenHead>,
222    pub movers: ThinVec<FutureTree>,
223}
224
225impl ParseMoment {
226    pub fn least_index(&self) -> &GornIndex {
227        let mut least = &self.tree.index;
228        for m in self.movers.iter() {
229            if m.index < *least {
230                least = &m.index
231            }
232        }
233        least
234    }
235
236    pub fn new(
237        tree: FutureTree,
238        movers: ThinVec<FutureTree>,
239        stolen_head: Option<StolenHead>,
240    ) -> Self {
241        ParseMoment {
242            tree,
243            movers,
244            stolen_head,
245        }
246    }
247    pub fn no_movers(&self) -> bool {
248        self.movers.is_empty()
249    }
250}
251
252impl PartialOrd for ParseMoment {
253    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
254        Some(self.cmp(other))
255    }
256}
257
258impl Ord for ParseMoment {
259    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
260        self.least_index().cmp(other.least_index())
261    }
262}
263
264#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
265pub enum StolenHead {
266    Stealer(usize),
267    StolenHead(usize, GornIndex),
268}
269
270impl StolenHead {
271    pub(crate) fn new_stolen(pos: usize, direction: Direction) -> Self {
272        StolenHead::StolenHead(pos, GornIndex::new(direction))
273    }
274}
minimalist_grammar_parser/parsing/trees.rs

minimalist_grammar_parser/parsing/
trees.rs
