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 fn is_attr(&self, _kind: &K) -> bool {
158 false
159 }
160}
161
162pub(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
213fn 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
236fn kind_of<K>(e: &Element<K>) -> &K {
238 e.kind()
239}
240
241pub(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
294fn 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
321fn 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
332pub(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
374fn 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 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 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}