use alloc::vec::Vec;
use syntax_lang::{Element, Node, TokenKind};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[non_exhaustive]
pub enum Pick<K> {
Absent,
Label(u16),
Nth(u16),
Back(u16),
NthNode(u16),
Kind(K),
KindNth(K, u16),
First(K),
After(K),
Before(K),
All,
Nodes,
AllKind(K),
Range(u16, u16),
AllAfter(K),
Between(K, K),
}
#[allow(clippy::derivable_impls)]
impl<K> Default for Pick<K> {
fn default() -> Self {
Self::Absent
}
}
impl<K> Pick<K> {
#[must_use]
pub const fn is_absent(&self) -> bool {
matches!(self, Self::Absent)
}
}
pub trait Labeler<K> {
fn label(&self, parent: &Node<K>, index: usize) -> Option<u16>;
}
#[derive(Clone, Copy)]
pub(crate) struct Kid<'t, K> {
pub(crate) elem: &'t Element<K>,
pub(crate) label: Option<u16>,
}
pub(crate) trait KindSets<K> {
fn is_skip(&self, kind: &K) -> bool;
fn is_container(&self, kind: &K) -> bool;
fn is_attr(&self, _kind: &K) -> bool {
false
}
}
pub(crate) fn collect_kids<'t, K: Copy + TokenKind>(
node: &'t Node<K>,
labeler: Option<&dyn Labeler<K>>,
sets: &dyn KindSets<K>,
out: &mut Vec<Kid<'t, K>>,
mut attrs: Option<&mut Vec<&'t Element<K>>>,
) {
out.clear();
if let Some(a) = attrs.as_deref_mut() {
a.clear();
}
for (index, elem) in node.children().enumerate() {
match elem {
Element::Token(t) => {
if t.kind().is_trivia() {
continue;
}
}
Element::Node(n) => {
if sets.is_attr(n.kind()) {
if let Some(a) = attrs.as_deref_mut() {
a.push(elem);
}
continue;
}
if sets.is_container(n.kind()) && is_attr_group(n, sets) {
if let Some(a) = attrs.as_deref_mut() {
a.extend(
n.children().filter(
|c| matches!(c, Element::Node(x) if sets.is_attr(x.kind())),
),
);
}
continue;
}
}
}
let label = match labeler {
Some(l) => l.label(node, index),
None => None,
};
out.push(Kid { elem, label });
}
}
fn is_attr_group<K: Copy + TokenKind>(n: &Node<K>, sets: &dyn KindSets<K>) -> bool {
let mut any = false;
for c in n.children() {
match c {
Element::Token(t) => {
if !t.kind().is_trivia() && !sets.is_skip(t.kind()) {
return false;
}
}
Element::Node(x) => {
if sets.is_attr(x.kind()) {
any = true;
} else if !sets.is_skip(x.kind()) {
return false;
}
}
}
}
any
}
fn kind_of<K>(e: &Element<K>) -> &K {
e.kind()
}
pub(crate) fn single<'t, K: Copy + Eq + TokenKind>(
pick: Pick<K>,
kids: &[Kid<'t, K>],
sets: &dyn KindSets<K>,
) -> Option<&'t Element<K>> {
let at = |i: usize| kids.get(i).map(|k| k.elem);
match pick {
Pick::Absent => None,
Pick::Label(l) => kids.iter().find(|k| k.label == Some(l)).map(|k| k.elem),
Pick::Nth(n) => at(usize::from(n)),
Pick::Back(n) => kids.len().checked_sub(usize::from(n) + 1).and_then(at),
Pick::NthNode(n) => kids
.iter()
.filter(|k| k.elem.is_node())
.nth(usize::from(n))
.map(|k| k.elem),
Pick::Kind(kind) => kids
.iter()
.find(|k| *kind_of(k.elem) == kind)
.map(|k| k.elem),
Pick::KindNth(kind, n) => kids
.iter()
.filter(|k| *kind_of(k.elem) == kind)
.nth(usize::from(n))
.map(|k| k.elem),
Pick::First(kind) => kids
.first()
.filter(|k| *kind_of(k.elem) == kind)
.map(|k| k.elem),
Pick::After(kind) => {
let i = kids.iter().position(|k| *kind_of(k.elem) == kind)?;
at(i + 1)
}
Pick::Before(kind) => {
let i = kids.iter().position(|k| *kind_of(k.elem) == kind)?;
at(i.checked_sub(1)?)
}
Pick::All
| Pick::Nodes
| Pick::AllKind(_)
| Pick::Range(..)
| Pick::AllAfter(_)
| Pick::Between(..) => {
let (lo, hi) = list_bounds(pick, kids);
kids.get(lo..hi)?
.iter()
.find(|k| list_keeps(pick, k, sets))
.map(|k| k.elem)
}
}
}
fn list_bounds<K: Copy + Eq>(pick: Pick<K>, kids: &[Kid<'_, K>]) -> (usize, usize) {
let len = kids.len();
match pick {
Pick::Range(from, back) => {
let lo = usize::from(from).min(len);
let hi = len.saturating_sub(usize::from(back)).max(lo);
(lo, hi)
}
Pick::AllAfter(kind) => match kids.iter().position(|k| *kind_of(k.elem) == kind) {
Some(i) => (i + 1, len),
None => (len, len),
},
Pick::Between(open, close) => match kids.iter().position(|k| *kind_of(k.elem) == open) {
Some(i) => {
let end = kids
.get(i + 1..)
.and_then(|rest| rest.iter().position(|k| *kind_of(k.elem) == close))
.map_or(len, |j| i + 1 + j);
(i + 1, end)
}
None => (len, len),
},
_ => (0, len),
}
}
fn list_keeps<K: Copy + Eq>(pick: Pick<K>, kid: &Kid<'_, K>, sets: &dyn KindSets<K>) -> bool {
let kind = kind_of(kid.elem);
match pick {
Pick::Nodes => kid.elem.is_node(),
Pick::AllKind(k) => *kind == k,
Pick::Label(l) => kid.label == Some(l),
_ => !sets.is_skip(kind),
}
}
pub(crate) fn list<'t, K: Copy + Eq + TokenKind>(
pick: Pick<K>,
kids: &[Kid<'t, K>],
sets: &dyn KindSets<K>,
out: &mut Vec<&'t Element<K>>,
) {
match pick {
Pick::Absent => {}
Pick::Nth(_)
| Pick::Back(_)
| Pick::NthNode(_)
| Pick::Kind(_)
| Pick::KindNth(..)
| Pick::First(_)
| Pick::After(_)
| Pick::Before(_) => {
if let Some(e) = single(pick, kids, sets) {
splice_into(e, sets, out);
}
}
Pick::Label(_)
| Pick::All
| Pick::Nodes
| Pick::AllKind(_)
| Pick::Range(..)
| Pick::AllAfter(_)
| Pick::Between(..) => {
let (lo, hi) = list_bounds(pick, kids);
if let Some(slice) = kids.get(lo..hi) {
for kid in slice {
if list_keeps(pick, kid, sets) {
splice_into(kid.elem, sets, out);
}
}
}
}
}
}
fn splice_into<'t, K: Copy + Eq + TokenKind>(
elem: &'t Element<K>,
sets: &dyn KindSets<K>,
out: &mut Vec<&'t Element<K>>,
) {
let Element::Node(node) = elem else {
out.push(elem);
return;
};
if !sets.is_container(node.kind()) {
out.push(elem);
return;
}
let mut stack = Vec::new();
stack.push(node.children());
while let Some(top) = stack.last_mut() {
let Some(child) = top.next() else {
let _ = stack.pop();
continue;
};
match child {
Element::Token(t) => {
if !t.kind().is_trivia() && !sets.is_skip(t.kind()) {
out.push(child);
}
}
Element::Node(n) => {
if sets.is_container(n.kind()) {
stack.push(n.children());
} else if !sets.is_skip(n.kind()) {
out.push(child);
}
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use alloc::vec;
use syntax_lang::{Span, Token};
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum K {
Root,
List,
Ident,
Comma,
Open,
Close,
Space,
}
impl TokenKind for K {
fn is_trivia(&self) -> bool {
matches!(self, K::Space)
}
}
struct Sets;
impl KindSets<K> for Sets {
fn is_skip(&self, kind: &K) -> bool {
*kind == K::Comma
}
fn is_container(&self, kind: &K) -> bool {
*kind == K::List
}
}
fn tok(kind: K, at: u32) -> Element<K> {
Element::Token(Token::new(kind, Span::new(at, at + 1)))
}
fn sample() -> Node<K> {
let inner = Node::new(
K::List,
vec![tok(K::Ident, 5), tok(K::Comma, 6), tok(K::Ident, 7)],
);
Node::new(
K::Root,
vec![
tok(K::Open, 0),
tok(K::Space, 1),
tok(K::Ident, 2),
tok(K::Comma, 3),
Element::Node(inner),
tok(K::Close, 9),
],
)
}
#[test]
fn test_positional_picks_skip_trivia() {
let root = sample();
let mut kids = Vec::new();
collect_kids(&root, None, &Sets, &mut kids, None);
assert_eq!(kids.len(), 5);
let span = |p| single(p, &kids, &Sets).map(|e| e.span().start().to_u32());
assert_eq!(span(Pick::Nth(1)), Some(2));
assert_eq!(span(Pick::Back(0)), Some(9));
assert_eq!(span(Pick::NthNode(0)), Some(5));
assert_eq!(span(Pick::Kind(K::Ident)), Some(2));
assert_eq!(span(Pick::After(K::Comma)), Some(5));
assert_eq!(span(Pick::Before(K::Comma)), Some(2));
assert_eq!(span(Pick::Before(K::Open)), None);
assert_eq!(span(Pick::First(K::Open)), Some(0));
assert_eq!(span(Pick::First(K::Ident)), None);
assert_eq!(span(Pick::Nth(40)), None);
assert_eq!(span(Pick::Back(40)), None);
assert_eq!(span(Pick::Absent), None);
}
#[test]
fn test_list_picks_splice_containers_and_drop_skips() {
let root = sample();
let mut kids = Vec::new();
collect_kids(&root, None, &Sets, &mut kids, None);
let starts = |p| {
let mut out = Vec::new();
list(p, &kids, &Sets, &mut out);
out.iter()
.map(|e| e.span().start().to_u32())
.collect::<Vec<_>>()
};
assert_eq!(starts(Pick::Range(1, 1)), [2, 5, 7]);
assert_eq!(starts(Pick::Between(K::Open, K::Close)), [2, 5, 7]);
assert_eq!(starts(Pick::AllKind(K::Ident)), [2]);
assert_eq!(starts(Pick::Nodes), [5, 7]);
assert_eq!(starts(Pick::AllAfter(K::Comma)), [5, 7, 9]);
assert_eq!(starts(Pick::Range(9, 9)), Vec::<u32>::new());
assert_eq!(starts(Pick::Nth(1)), [2]);
}
#[test]
fn test_labels_come_from_the_labeler() {
struct Odd;
impl Labeler<K> for Odd {
fn label(&self, _: &Node<K>, index: usize) -> Option<u16> {
(index % 2 == 0).then_some(3)
}
}
let root = sample();
let mut kids = Vec::new();
collect_kids(&root, Some(&Odd), &Sets, &mut kids, None);
let first = single(Pick::Label(3), &kids, &Sets).map(|e| e.span().start().to_u32());
assert_eq!(first, Some(0));
let mut out = Vec::new();
list(Pick::Label(3), &kids, &Sets, &mut out);
assert_eq!(out.len(), 4);
}
#[test]
fn test_deeply_nested_containers_splice_without_recursion() {
let mut node = Node::new(K::List, vec![tok(K::Ident, 0)]);
for _ in 0..100_000 {
node = Node::new(K::List, vec![Element::Node(node)]);
}
let root = Node::new(K::Root, vec![Element::Node(node)]);
let mut kids = Vec::new();
collect_kids(&root, None, &Sets, &mut kids, None);
let mut out = Vec::new();
list(Pick::All, &kids, &Sets, &mut out);
assert_eq!(out.len(), 1);
}
}