Skip to main content

lower_lang/
pick.rs

1//! Tree access: how an archetype's fields are found among a node's children.
2//!
3//! A syntax tree from lang-forge 1.x has no field labels, so a field is found
4//! by position or by kind ([`Pick::Nth`], [`Pick::Kind`], [`Pick::After`], ...).
5//! Trees from LSF2 sketches will carry `name:expr` labels; a host that has them
6//! supplies a [`Labeler`] and addresses fields with [`Pick::Label`]. Either way
7//! the mapping is data: a `Pick` is a small `Copy` value, and the common path
8//! needs no closures.
9
10use alloc::vec::Vec;
11
12use syntax_lang::{Element, Node, TokenKind};
13
14/// Where a field of an archetype is found among a node's children.
15///
16/// Positions count the node's **significant** children: every child node and
17/// every token that is not trivia (whitespace and comments never count). List
18/// picks ([`All`](Pick::All), [`Nodes`](Pick::Nodes), [`AllKind`](Pick::AllKind),
19/// [`Range`](Pick::Range), [`AllAfter`](Pick::AllAfter),
20/// [`Between`](Pick::Between), and [`Label`](Pick::Label)) select every match,
21/// splice the children of *container* kinds in place, and (except `AllKind`,
22/// `Nodes`, and `Label`) leave out *skip* kinds such as `,` and `;` (both
23/// declared in the [`Mapping`](crate::Mapping)). Used where one child is
24/// expected, a list pick takes its first match.
25///
26/// A pick that finds nothing makes the field absent: optional fields are then
27/// left out, and required ones become an error node plus a
28/// [`MissingField`](crate::ProblemKind::MissingField) problem.
29///
30/// # Examples
31///
32/// ```
33/// use lower_lang::Pick;
34///
35/// // `let NAME = VALUE ;` in a tree without labels: the name is the first
36/// // identifier, the value is whatever follows `=`.
37/// let ident = 7u16; // the language's IDENT kind
38/// let eq = 9u16;    // its `=` kind
39/// let name = Pick::Kind(ident);
40/// let value = Pick::After(eq);
41/// assert_ne!(name, value);
42/// assert_eq!(Pick::<u16>::default(), Pick::Absent);
43/// ```
44#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
45#[non_exhaustive]
46pub enum Pick<K> {
47    /// The construct never has this field.
48    Absent,
49    /// The child (or, as a list, every child) whose host-provided field label
50    /// is this id. Needs a [`Labeler`]; without one it finds nothing.
51    Label(u16),
52    /// The `n`-th significant child (0-based).
53    Nth(u16),
54    /// The `n`-th significant child from the end (`Back(0)` is the last).
55    Back(u16),
56    /// The `n`-th child node (tokens not counted).
57    NthNode(u16),
58    /// The first significant child of this kind.
59    Kind(K),
60    /// The `n`-th significant child of this kind.
61    KindNth(K, u16),
62    /// The first significant child, if it is of this kind (a leading `::`, a
63    /// leading keyword).
64    First(K),
65    /// The first significant child after the first child of this kind (the
66    /// value after `=`, the return type after `->`).
67    After(K),
68    /// The significant child just before the first child of this kind (the
69    /// key before `=>`, the last item before `)`).
70    Before(K),
71    /// List: every significant child that is not a skip kind.
72    All,
73    /// List: every child node.
74    Nodes,
75    /// List: every significant child of this kind.
76    AllKind(K),
77    /// List: the significant children from position `from` up to `back`
78    /// positions before the end (`Range(1, 1)` is everything between a node's
79    /// first and last child, such as the items between `(` and `)`).
80    Range(u16, u16),
81    /// List: every significant child after the first child of this kind.
82    AllAfter(K),
83    /// List: the significant children after the first child of the first kind
84    /// and before the next child of the second kind (or the end).
85    Between(K, K),
86}
87
88// Written out: `#[derive(Default)]` would require `K: Default`, which kind
89// types such as lang-forge's `Kind` do not implement.
90#[allow(clippy::derivable_impls)]
91impl<K> Default for Pick<K> {
92    fn default() -> Self {
93        Self::Absent
94    }
95}
96
97impl<K> Pick<K> {
98    /// Whether this pick names nothing (`Absent`).
99    ///
100    /// # Examples
101    ///
102    /// ```
103    /// use lower_lang::Pick;
104    ///
105    /// assert!(Pick::<u8>::Absent.is_absent());
106    /// assert!(!Pick::<u8>::Nth(0).is_absent());
107    /// ```
108    #[must_use]
109    pub const fn is_absent(&self) -> bool {
110        matches!(self, Self::Absent)
111    }
112}
113
114/// Supplies field labels for the children of a node: the integration point for
115/// trees whose grammar names its fields (LSF2 `name:expr`).
116///
117/// `index` is the child's position among **all** of `parent`'s children,
118/// trivia included, as [`Node::children`] yields them. Return the label id the
119/// mapping's [`Pick::Label`] values use, or `None` for an unlabelled child.
120///
121/// # Examples
122///
123/// ```
124/// use lower_lang::Labeler;
125/// use syntax_lang::Node;
126///
127/// // A toy host whose grammar labels the first child of every node `0`.
128/// struct FirstIsZero;
129/// impl<K> Labeler<K> for FirstIsZero {
130///     fn label(&self, _parent: &Node<K>, index: usize) -> Option<u16> {
131///         (index == 0).then_some(0)
132///     }
133/// }
134/// let n: Node<u8> = Node::new(1, vec![]);
135/// assert_eq!(FirstIsZero.label(&n, 0), Some(0));
136/// assert_eq!(FirstIsZero.label(&n, 1), None);
137/// ```
138pub trait Labeler<K> {
139    /// The label of `parent`'s child at `index`, if it has one.
140    fn label(&self, parent: &Node<K>, index: usize) -> Option<u16>;
141}
142
143/// One significant child with its label.
144#[derive(Clone, Copy)]
145pub(crate) struct Kid<'t, K> {
146    pub(crate) elem: &'t Element<K>,
147    pub(crate) label: Option<u16>,
148}
149
150/// The kind sets a pick consults while selecting.
151pub(crate) trait KindSets<K> {
152    /// Whether list picks leave this kind out.
153    fn is_skip(&self, kind: &K) -> bool;
154    /// Whether list picks splice this node kind's children in place.
155    fn is_container(&self, kind: &K) -> bool;
156}
157
158/// Collects `node`'s significant children (and their labels) into `out`.
159pub(crate) fn collect_kids<'t, K: TokenKind>(
160    node: &'t Node<K>,
161    labeler: Option<&dyn Labeler<K>>,
162    out: &mut Vec<Kid<'t, K>>,
163) {
164    out.clear();
165    for (index, elem) in node.children().enumerate() {
166        if let Element::Token(t) = elem {
167            if t.kind().is_trivia() {
168                continue;
169            }
170        }
171        let label = match labeler {
172            Some(l) => l.label(node, index),
173            None => None,
174        };
175        out.push(Kid { elem, label });
176    }
177}
178
179/// The element's kind.
180fn kind_of<K>(e: &Element<K>) -> &K {
181    e.kind()
182}
183
184/// Resolves a pick that names one child.
185pub(crate) fn single<'t, K: Copy + Eq + TokenKind>(
186    pick: Pick<K>,
187    kids: &[Kid<'t, K>],
188    sets: &dyn KindSets<K>,
189) -> Option<&'t Element<K>> {
190    let at = |i: usize| kids.get(i).map(|k| k.elem);
191    match pick {
192        Pick::Absent => None,
193        Pick::Label(l) => kids.iter().find(|k| k.label == Some(l)).map(|k| k.elem),
194        Pick::Nth(n) => at(usize::from(n)),
195        Pick::Back(n) => kids.len().checked_sub(usize::from(n) + 1).and_then(at),
196        Pick::NthNode(n) => kids
197            .iter()
198            .filter(|k| k.elem.is_node())
199            .nth(usize::from(n))
200            .map(|k| k.elem),
201        Pick::Kind(kind) => kids
202            .iter()
203            .find(|k| *kind_of(k.elem) == kind)
204            .map(|k| k.elem),
205        Pick::KindNth(kind, n) => kids
206            .iter()
207            .filter(|k| *kind_of(k.elem) == kind)
208            .nth(usize::from(n))
209            .map(|k| k.elem),
210        Pick::First(kind) => kids
211            .first()
212            .filter(|k| *kind_of(k.elem) == kind)
213            .map(|k| k.elem),
214        Pick::After(kind) => {
215            let i = kids.iter().position(|k| *kind_of(k.elem) == kind)?;
216            at(i + 1)
217        }
218        Pick::Before(kind) => {
219            let i = kids.iter().position(|k| *kind_of(k.elem) == kind)?;
220            at(i.checked_sub(1)?)
221        }
222        Pick::All
223        | Pick::Nodes
224        | Pick::AllKind(_)
225        | Pick::Range(..)
226        | Pick::AllAfter(_)
227        | Pick::Between(..) => {
228            let (lo, hi) = list_bounds(pick, kids);
229            kids.get(lo..hi)?
230                .iter()
231                .find(|k| list_keeps(pick, k, sets))
232                .map(|k| k.elem)
233        }
234    }
235}
236
237/// The index range a list pick scans.
238fn list_bounds<K: Copy + Eq>(pick: Pick<K>, kids: &[Kid<'_, K>]) -> (usize, usize) {
239    let len = kids.len();
240    match pick {
241        Pick::Range(from, back) => {
242            let lo = usize::from(from).min(len);
243            let hi = len.saturating_sub(usize::from(back)).max(lo);
244            (lo, hi)
245        }
246        Pick::AllAfter(kind) => match kids.iter().position(|k| *kind_of(k.elem) == kind) {
247            Some(i) => (i + 1, len),
248            None => (len, len),
249        },
250        Pick::Between(open, close) => match kids.iter().position(|k| *kind_of(k.elem) == open) {
251            Some(i) => {
252                let end = kids
253                    .get(i + 1..)
254                    .and_then(|rest| rest.iter().position(|k| *kind_of(k.elem) == close))
255                    .map_or(len, |j| i + 1 + j);
256                (i + 1, end)
257            }
258            None => (len, len),
259        },
260        _ => (0, len),
261    }
262}
263
264/// Whether a list pick keeps this child (before container splicing).
265fn list_keeps<K: Copy + Eq>(pick: Pick<K>, kid: &Kid<'_, K>, sets: &dyn KindSets<K>) -> bool {
266    let kind = kind_of(kid.elem);
267    match pick {
268        Pick::Nodes => kid.elem.is_node(),
269        Pick::AllKind(k) => *kind == k,
270        Pick::Label(l) => kid.label == Some(l),
271        _ => !sets.is_skip(kind),
272    }
273}
274
275/// Resolves a pick as a list, appending the selected elements to `out` in
276/// source order. Container nodes are replaced by their significant, non-skip
277/// children, iteratively (nested containers are spliced too).
278pub(crate) fn list<'t, K: Copy + Eq + TokenKind>(
279    pick: Pick<K>,
280    kids: &[Kid<'t, K>],
281    sets: &dyn KindSets<K>,
282    out: &mut Vec<&'t Element<K>>,
283) {
284    match pick {
285        Pick::Absent => {}
286        Pick::Nth(_)
287        | Pick::Back(_)
288        | Pick::NthNode(_)
289        | Pick::Kind(_)
290        | Pick::KindNth(..)
291        | Pick::First(_)
292        | Pick::After(_)
293        | Pick::Before(_) => {
294            if let Some(e) = single(pick, kids, sets) {
295                splice_into(e, sets, out);
296            }
297        }
298        Pick::Label(_)
299        | Pick::All
300        | Pick::Nodes
301        | Pick::AllKind(_)
302        | Pick::Range(..)
303        | Pick::AllAfter(_)
304        | Pick::Between(..) => {
305            let (lo, hi) = list_bounds(pick, kids);
306            if let Some(slice) = kids.get(lo..hi) {
307                for kid in slice {
308                    if list_keeps(pick, kid, sets) {
309                        splice_into(kid.elem, sets, out);
310                    }
311                }
312            }
313        }
314    }
315}
316
317/// Pushes `elem`, or, for a container node, its significant non-skip
318/// descendants through nested containers, with an explicit stack.
319fn splice_into<'t, K: Copy + Eq + TokenKind>(
320    elem: &'t Element<K>,
321    sets: &dyn KindSets<K>,
322    out: &mut Vec<&'t Element<K>>,
323) {
324    let Element::Node(node) = elem else {
325        out.push(elem);
326        return;
327    };
328    if !sets.is_container(node.kind()) {
329        out.push(elem);
330        return;
331    }
332    let mut stack = Vec::new();
333    stack.push(node.children());
334    while let Some(top) = stack.last_mut() {
335        let Some(child) = top.next() else {
336            let _ = stack.pop();
337            continue;
338        };
339        match child {
340            Element::Token(t) => {
341                if !t.kind().is_trivia() && !sets.is_skip(t.kind()) {
342                    out.push(child);
343                }
344            }
345            Element::Node(n) => {
346                if sets.is_container(n.kind()) {
347                    stack.push(n.children());
348                } else if !sets.is_skip(n.kind()) {
349                    out.push(child);
350                }
351            }
352        }
353    }
354}
355
356#[cfg(test)]
357mod tests {
358    use super::*;
359    use alloc::vec;
360    use syntax_lang::{Span, Token};
361
362    #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
363    enum K {
364        Root,
365        List,
366        Ident,
367        Comma,
368        Open,
369        Close,
370        Space,
371    }
372    impl TokenKind for K {
373        fn is_trivia(&self) -> bool {
374            matches!(self, K::Space)
375        }
376    }
377
378    struct Sets;
379    impl KindSets<K> for Sets {
380        fn is_skip(&self, kind: &K) -> bool {
381            *kind == K::Comma
382        }
383        fn is_container(&self, kind: &K) -> bool {
384            *kind == K::List
385        }
386    }
387
388    fn tok(kind: K, at: u32) -> Element<K> {
389        Element::Token(Token::new(kind, Span::new(at, at + 1)))
390    }
391
392    /// `( a , [b , c] )` where `[...]` is a container node.
393    fn sample() -> Node<K> {
394        let inner = Node::new(
395            K::List,
396            vec![tok(K::Ident, 5), tok(K::Comma, 6), tok(K::Ident, 7)],
397        );
398        Node::new(
399            K::Root,
400            vec![
401                tok(K::Open, 0),
402                tok(K::Space, 1),
403                tok(K::Ident, 2),
404                tok(K::Comma, 3),
405                Element::Node(inner),
406                tok(K::Close, 9),
407            ],
408        )
409    }
410
411    #[test]
412    fn test_positional_picks_skip_trivia() {
413        let root = sample();
414        let mut kids = Vec::new();
415        collect_kids(&root, None, &mut kids);
416        assert_eq!(kids.len(), 5);
417        let span = |p| single(p, &kids, &Sets).map(|e| e.span().start().to_u32());
418        assert_eq!(span(Pick::Nth(1)), Some(2));
419        assert_eq!(span(Pick::Back(0)), Some(9));
420        assert_eq!(span(Pick::NthNode(0)), Some(5));
421        assert_eq!(span(Pick::Kind(K::Ident)), Some(2));
422        assert_eq!(span(Pick::After(K::Comma)), Some(5));
423        assert_eq!(span(Pick::Before(K::Comma)), Some(2));
424        assert_eq!(span(Pick::Before(K::Open)), None);
425        assert_eq!(span(Pick::First(K::Open)), Some(0));
426        assert_eq!(span(Pick::First(K::Ident)), None);
427        assert_eq!(span(Pick::Nth(40)), None);
428        assert_eq!(span(Pick::Back(40)), None);
429        assert_eq!(span(Pick::Absent), None);
430    }
431
432    #[test]
433    fn test_list_picks_splice_containers_and_drop_skips() {
434        let root = sample();
435        let mut kids = Vec::new();
436        collect_kids(&root, None, &mut kids);
437        let starts = |p| {
438            let mut out = Vec::new();
439            list(p, &kids, &Sets, &mut out);
440            out.iter()
441                .map(|e| e.span().start().to_u32())
442                .collect::<Vec<_>>()
443        };
444        assert_eq!(starts(Pick::Range(1, 1)), [2, 5, 7]);
445        assert_eq!(starts(Pick::Between(K::Open, K::Close)), [2, 5, 7]);
446        assert_eq!(starts(Pick::AllKind(K::Ident)), [2]);
447        assert_eq!(starts(Pick::Nodes), [5, 7]);
448        assert_eq!(starts(Pick::AllAfter(K::Comma)), [5, 7, 9]);
449        assert_eq!(starts(Pick::Range(9, 9)), Vec::<u32>::new());
450        assert_eq!(starts(Pick::Nth(1)), [2]);
451    }
452
453    #[test]
454    fn test_labels_come_from_the_labeler() {
455        struct Odd;
456        impl Labeler<K> for Odd {
457            fn label(&self, _: &Node<K>, index: usize) -> Option<u16> {
458                (index % 2 == 0).then_some(3)
459            }
460        }
461        let root = sample();
462        let mut kids = Vec::new();
463        collect_kids(&root, Some(&Odd), &mut kids);
464        let first = single(Pick::Label(3), &kids, &Sets).map(|e| e.span().start().to_u32());
465        assert_eq!(first, Some(0));
466        let mut out = Vec::new();
467        list(Pick::Label(3), &kids, &Sets, &mut out);
468        // `(`, `a`, and the container (spliced into `b`, `c`).
469        assert_eq!(out.len(), 4);
470    }
471
472    #[test]
473    fn test_deeply_nested_containers_splice_without_recursion() {
474        let mut node = Node::new(K::List, vec![tok(K::Ident, 0)]);
475        for _ in 0..100_000 {
476            node = Node::new(K::List, vec![Element::Node(node)]);
477        }
478        let root = Node::new(K::Root, vec![Element::Node(node)]);
479        let mut kids = Vec::new();
480        collect_kids(&root, None, &mut kids);
481        let mut out = Vec::new();
482        list(Pick::All, &kids, &Sets, &mut out);
483        assert_eq!(out.len(), 1);
484    }
485}