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    /// Whether nodes of this kind are attributes (invisible to picks).
157    fn is_attr(&self, _kind: &K) -> bool {
158        false
159    }
160}
161
162/// Collects `node`'s significant children (and their labels) into `out`.
163/// Attribute nodes, and container nodes whose significant non-skip children
164/// are all attributes (an attribute group such as `#[A, B]`), are not
165/// children for picks: with `attrs`, the attributes are collected there
166/// instead (a group's attributes spliced in order). A container that mixes
167/// attributes with other children is an ordinary container.
168pub(crate) fn collect_kids<'t, K: Copy + TokenKind>(
169    node: &'t Node<K>,
170    labeler: Option<&dyn Labeler<K>>,
171    sets: &dyn KindSets<K>,
172    out: &mut Vec<Kid<'t, K>>,
173    mut attrs: Option<&mut Vec<&'t Element<K>>>,
174) {
175    out.clear();
176    if let Some(a) = attrs.as_deref_mut() {
177        a.clear();
178    }
179    for (index, elem) in node.children().enumerate() {
180        match elem {
181            Element::Token(t) => {
182                if t.kind().is_trivia() {
183                    continue;
184                }
185            }
186            Element::Node(n) => {
187                if sets.is_attr(n.kind()) {
188                    if let Some(a) = attrs.as_deref_mut() {
189                        a.push(elem);
190                    }
191                    continue;
192                }
193                if sets.is_container(n.kind()) && is_attr_group(n, sets) {
194                    if let Some(a) = attrs.as_deref_mut() {
195                        a.extend(
196                            n.children().filter(
197                                |c| matches!(c, Element::Node(x) if sets.is_attr(x.kind())),
198                            ),
199                        );
200                    }
201                    continue;
202                }
203            }
204        }
205        let label = match labeler {
206            Some(l) => l.label(node, index),
207            None => None,
208        };
209        out.push(Kid { elem, label });
210    }
211}
212
213/// Whether a container node holds attributes and nothing else significant
214/// (skip kinds such as `#[`, `,`, `]` aside).
215fn is_attr_group<K: Copy + TokenKind>(n: &Node<K>, sets: &dyn KindSets<K>) -> bool {
216    let mut any = false;
217    for c in n.children() {
218        match c {
219            Element::Token(t) => {
220                if !t.kind().is_trivia() && !sets.is_skip(t.kind()) {
221                    return false;
222                }
223            }
224            Element::Node(x) => {
225                if sets.is_attr(x.kind()) {
226                    any = true;
227                } else if !sets.is_skip(x.kind()) {
228                    return false;
229                }
230            }
231        }
232    }
233    any
234}
235
236/// The element's kind.
237fn kind_of<K>(e: &Element<K>) -> &K {
238    e.kind()
239}
240
241/// Resolves a pick that names one child.
242pub(crate) fn single<'t, K: Copy + Eq + TokenKind>(
243    pick: Pick<K>,
244    kids: &[Kid<'t, K>],
245    sets: &dyn KindSets<K>,
246) -> Option<&'t Element<K>> {
247    let at = |i: usize| kids.get(i).map(|k| k.elem);
248    match pick {
249        Pick::Absent => None,
250        Pick::Label(l) => kids.iter().find(|k| k.label == Some(l)).map(|k| k.elem),
251        Pick::Nth(n) => at(usize::from(n)),
252        Pick::Back(n) => kids.len().checked_sub(usize::from(n) + 1).and_then(at),
253        Pick::NthNode(n) => kids
254            .iter()
255            .filter(|k| k.elem.is_node())
256            .nth(usize::from(n))
257            .map(|k| k.elem),
258        Pick::Kind(kind) => kids
259            .iter()
260            .find(|k| *kind_of(k.elem) == kind)
261            .map(|k| k.elem),
262        Pick::KindNth(kind, n) => kids
263            .iter()
264            .filter(|k| *kind_of(k.elem) == kind)
265            .nth(usize::from(n))
266            .map(|k| k.elem),
267        Pick::First(kind) => kids
268            .first()
269            .filter(|k| *kind_of(k.elem) == kind)
270            .map(|k| k.elem),
271        Pick::After(kind) => {
272            let i = kids.iter().position(|k| *kind_of(k.elem) == kind)?;
273            at(i + 1)
274        }
275        Pick::Before(kind) => {
276            let i = kids.iter().position(|k| *kind_of(k.elem) == kind)?;
277            at(i.checked_sub(1)?)
278        }
279        Pick::All
280        | Pick::Nodes
281        | Pick::AllKind(_)
282        | Pick::Range(..)
283        | Pick::AllAfter(_)
284        | Pick::Between(..) => {
285            let (lo, hi) = list_bounds(pick, kids);
286            kids.get(lo..hi)?
287                .iter()
288                .find(|k| list_keeps(pick, k, sets))
289                .map(|k| k.elem)
290        }
291    }
292}
293
294/// The index range a list pick scans.
295fn list_bounds<K: Copy + Eq>(pick: Pick<K>, kids: &[Kid<'_, K>]) -> (usize, usize) {
296    let len = kids.len();
297    match pick {
298        Pick::Range(from, back) => {
299            let lo = usize::from(from).min(len);
300            let hi = len.saturating_sub(usize::from(back)).max(lo);
301            (lo, hi)
302        }
303        Pick::AllAfter(kind) => match kids.iter().position(|k| *kind_of(k.elem) == kind) {
304            Some(i) => (i + 1, len),
305            None => (len, len),
306        },
307        Pick::Between(open, close) => match kids.iter().position(|k| *kind_of(k.elem) == open) {
308            Some(i) => {
309                let end = kids
310                    .get(i + 1..)
311                    .and_then(|rest| rest.iter().position(|k| *kind_of(k.elem) == close))
312                    .map_or(len, |j| i + 1 + j);
313                (i + 1, end)
314            }
315            None => (len, len),
316        },
317        _ => (0, len),
318    }
319}
320
321/// Whether a list pick keeps this child (before container splicing).
322fn list_keeps<K: Copy + Eq>(pick: Pick<K>, kid: &Kid<'_, K>, sets: &dyn KindSets<K>) -> bool {
323    let kind = kind_of(kid.elem);
324    match pick {
325        Pick::Nodes => kid.elem.is_node(),
326        Pick::AllKind(k) => *kind == k,
327        Pick::Label(l) => kid.label == Some(l),
328        _ => !sets.is_skip(kind),
329    }
330}
331
332/// Resolves a pick as a list, appending the selected elements to `out` in
333/// source order. Container nodes are replaced by their significant, non-skip
334/// children, iteratively (nested containers are spliced too).
335pub(crate) fn list<'t, K: Copy + Eq + TokenKind>(
336    pick: Pick<K>,
337    kids: &[Kid<'t, K>],
338    sets: &dyn KindSets<K>,
339    out: &mut Vec<&'t Element<K>>,
340) {
341    match pick {
342        Pick::Absent => {}
343        Pick::Nth(_)
344        | Pick::Back(_)
345        | Pick::NthNode(_)
346        | Pick::Kind(_)
347        | Pick::KindNth(..)
348        | Pick::First(_)
349        | Pick::After(_)
350        | Pick::Before(_) => {
351            if let Some(e) = single(pick, kids, sets) {
352                splice_into(e, sets, out);
353            }
354        }
355        Pick::Label(_)
356        | Pick::All
357        | Pick::Nodes
358        | Pick::AllKind(_)
359        | Pick::Range(..)
360        | Pick::AllAfter(_)
361        | Pick::Between(..) => {
362            let (lo, hi) = list_bounds(pick, kids);
363            if let Some(slice) = kids.get(lo..hi) {
364                for kid in slice {
365                    if list_keeps(pick, kid, sets) {
366                        splice_into(kid.elem, sets, out);
367                    }
368                }
369            }
370        }
371    }
372}
373
374/// Pushes `elem`, or, for a container node, its significant non-skip
375/// descendants through nested containers, with an explicit stack.
376fn splice_into<'t, K: Copy + Eq + TokenKind>(
377    elem: &'t Element<K>,
378    sets: &dyn KindSets<K>,
379    out: &mut Vec<&'t Element<K>>,
380) {
381    let Element::Node(node) = elem else {
382        out.push(elem);
383        return;
384    };
385    if !sets.is_container(node.kind()) {
386        out.push(elem);
387        return;
388    }
389    let mut stack = Vec::new();
390    stack.push(node.children());
391    while let Some(top) = stack.last_mut() {
392        let Some(child) = top.next() else {
393            let _ = stack.pop();
394            continue;
395        };
396        match child {
397            Element::Token(t) => {
398                if !t.kind().is_trivia() && !sets.is_skip(t.kind()) {
399                    out.push(child);
400                }
401            }
402            Element::Node(n) => {
403                if sets.is_container(n.kind()) {
404                    stack.push(n.children());
405                } else if !sets.is_skip(n.kind()) {
406                    out.push(child);
407                }
408            }
409        }
410    }
411}
412
413#[cfg(test)]
414mod tests {
415    use super::*;
416    use alloc::vec;
417    use syntax_lang::{Span, Token};
418
419    #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
420    enum K {
421        Root,
422        List,
423        Ident,
424        Comma,
425        Open,
426        Close,
427        Space,
428    }
429    impl TokenKind for K {
430        fn is_trivia(&self) -> bool {
431            matches!(self, K::Space)
432        }
433    }
434
435    struct Sets;
436    impl KindSets<K> for Sets {
437        fn is_skip(&self, kind: &K) -> bool {
438            *kind == K::Comma
439        }
440        fn is_container(&self, kind: &K) -> bool {
441            *kind == K::List
442        }
443    }
444
445    fn tok(kind: K, at: u32) -> Element<K> {
446        Element::Token(Token::new(kind, Span::new(at, at + 1)))
447    }
448
449    /// `( a , [b , c] )` where `[...]` is a container node.
450    fn sample() -> Node<K> {
451        let inner = Node::new(
452            K::List,
453            vec![tok(K::Ident, 5), tok(K::Comma, 6), tok(K::Ident, 7)],
454        );
455        Node::new(
456            K::Root,
457            vec![
458                tok(K::Open, 0),
459                tok(K::Space, 1),
460                tok(K::Ident, 2),
461                tok(K::Comma, 3),
462                Element::Node(inner),
463                tok(K::Close, 9),
464            ],
465        )
466    }
467
468    #[test]
469    fn test_positional_picks_skip_trivia() {
470        let root = sample();
471        let mut kids = Vec::new();
472        collect_kids(&root, None, &Sets, &mut kids, None);
473        assert_eq!(kids.len(), 5);
474        let span = |p| single(p, &kids, &Sets).map(|e| e.span().start().to_u32());
475        assert_eq!(span(Pick::Nth(1)), Some(2));
476        assert_eq!(span(Pick::Back(0)), Some(9));
477        assert_eq!(span(Pick::NthNode(0)), Some(5));
478        assert_eq!(span(Pick::Kind(K::Ident)), Some(2));
479        assert_eq!(span(Pick::After(K::Comma)), Some(5));
480        assert_eq!(span(Pick::Before(K::Comma)), Some(2));
481        assert_eq!(span(Pick::Before(K::Open)), None);
482        assert_eq!(span(Pick::First(K::Open)), Some(0));
483        assert_eq!(span(Pick::First(K::Ident)), None);
484        assert_eq!(span(Pick::Nth(40)), None);
485        assert_eq!(span(Pick::Back(40)), None);
486        assert_eq!(span(Pick::Absent), None);
487    }
488
489    #[test]
490    fn test_list_picks_splice_containers_and_drop_skips() {
491        let root = sample();
492        let mut kids = Vec::new();
493        collect_kids(&root, None, &Sets, &mut kids, None);
494        let starts = |p| {
495            let mut out = Vec::new();
496            list(p, &kids, &Sets, &mut out);
497            out.iter()
498                .map(|e| e.span().start().to_u32())
499                .collect::<Vec<_>>()
500        };
501        assert_eq!(starts(Pick::Range(1, 1)), [2, 5, 7]);
502        assert_eq!(starts(Pick::Between(K::Open, K::Close)), [2, 5, 7]);
503        assert_eq!(starts(Pick::AllKind(K::Ident)), [2]);
504        assert_eq!(starts(Pick::Nodes), [5, 7]);
505        assert_eq!(starts(Pick::AllAfter(K::Comma)), [5, 7, 9]);
506        assert_eq!(starts(Pick::Range(9, 9)), Vec::<u32>::new());
507        assert_eq!(starts(Pick::Nth(1)), [2]);
508    }
509
510    #[test]
511    fn test_labels_come_from_the_labeler() {
512        struct Odd;
513        impl Labeler<K> for Odd {
514            fn label(&self, _: &Node<K>, index: usize) -> Option<u16> {
515                (index % 2 == 0).then_some(3)
516            }
517        }
518        let root = sample();
519        let mut kids = Vec::new();
520        collect_kids(&root, Some(&Odd), &Sets, &mut kids, None);
521        let first = single(Pick::Label(3), &kids, &Sets).map(|e| e.span().start().to_u32());
522        assert_eq!(first, Some(0));
523        let mut out = Vec::new();
524        list(Pick::Label(3), &kids, &Sets, &mut out);
525        // `(`, `a`, and the container (spliced into `b`, `c`).
526        assert_eq!(out.len(), 4);
527    }
528
529    #[test]
530    fn test_deeply_nested_containers_splice_without_recursion() {
531        let mut node = Node::new(K::List, vec![tok(K::Ident, 0)]);
532        for _ in 0..100_000 {
533            node = Node::new(K::List, vec![Element::Node(node)]);
534        }
535        let root = Node::new(K::Root, vec![Element::Node(node)]);
536        let mut kids = Vec::new();
537        collect_kids(&root, None, &Sets, &mut kids, None);
538        let mut out = Vec::new();
539        list(Pick::All, &kids, &Sets, &mut out);
540        assert_eq!(out.len(), 1);
541    }
542}