1use alloc::vec::Vec;
11
12use syntax_lang::{Element, Node, TokenKind};
13
14#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
45#[non_exhaustive]
46pub enum Pick<K> {
47 Absent,
49 Label(u16),
52 Nth(u16),
54 Back(u16),
56 NthNode(u16),
58 Kind(K),
60 KindNth(K, u16),
62 First(K),
65 After(K),
68 Before(K),
71 All,
73 Nodes,
75 AllKind(K),
77 Range(u16, u16),
81 AllAfter(K),
83 Between(K, K),
86}
87
88#[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 #[must_use]
109 pub const fn is_absent(&self) -> bool {
110 matches!(self, Self::Absent)
111 }
112}
113
114pub trait Labeler<K> {
139 fn label(&self, parent: &Node<K>, index: usize) -> Option<u16>;
141}
142
143#[derive(Clone, Copy)]
145pub(crate) struct Kid<'t, K> {
146 pub(crate) elem: &'t Element<K>,
147 pub(crate) label: Option<u16>,
148}
149
150pub(crate) trait KindSets<K> {
152 fn is_skip(&self, kind: &K) -> bool;
154 fn is_container(&self, kind: &K) -> bool;
156}
157
158pub(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
179fn kind_of<K>(e: &Element<K>) -> &K {
181 e.kind()
182}
183
184pub(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
237fn 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
264fn 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
275pub(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
317fn 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 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 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}