big_code_analysis_ast/ast.rs
1// Per-language metric and AST modules deliberately consume the macro-
2// generated tree-sitter token enums via `use crate::*` and `use Foo::*`
3// inside match expressions — explicit imports would list dozens of
4// variants per arm and obscure the per-language token sets that are the
5// point of these files. Allowed at the module level rather than per
6// function so the per-language impl blocks stay readable.
7#![allow(clippy::enum_glob_use, clippy::if_not_else, clippy::wildcard_imports)]
8
9//! The AST dump: [`AstNode`], [`Span`], [`AstCfg`], [`AstResponse`], and
10//! the walk that builds them.
11
12use std::ops::ControlFlow;
13
14use serde::{Deserialize, Serialize};
15
16use crate::*;
17
18/// Start and end positions of a node in a code in terms of lines, columns,
19/// and byte offsets.
20///
21/// Serialized as a flat object
22/// `{start_line, start_col, end_line, end_col, start_byte, end_byte}`. The
23/// line/column pairs are 1-based; the byte offsets are 0-based half-open
24/// (`[start_byte, end_byte)`) indices into the parsed source bytes
25/// (`big_code_analysis::Ast::source`). The `*_line` vocabulary aligns the
26/// `/ast` span field names with the `/function` and `/metrics` endpoints
27/// (`start_line` / `end_line`), so a client correlating spans across
28/// endpoints no longer special-cases `*_row` vs `*_line` per endpoint
29/// (#638). The former `start_row` / `end_row` keys were renamed as a
30/// `2.0`-line break.
31///
32/// The byte offsets let structural consumers slice the original source for a
33/// node — including internal nodes, whose `value` text the dump omits — so a
34/// caller can recover any subtree's exact bytes without re-deriving offsets
35/// from lines and columns (#727). They mirror tree-sitter's own
36/// `Node::start_byte` / `Node::end_byte`.
37///
38/// The struct is `#[non_exhaustive]`: construct it through [`Span::new`] and
39/// read its public fields, but do not rely on struct-literal construction or
40/// exhaustive destructuring from outside the crate. This is the last planned
41/// shape break to the type. The two byte fields carry `#[serde(default)]` so
42/// span objects serialized before they existed still deserialize (the
43/// offsets default to `0`).
44///
45/// A node's span is `None` for the root and any node when span tracking is
46/// disabled; in that case the wrapping `Option<Span>` serializes as `null`.
47#[derive(Debug, Clone, Copy, PartialEq, Eq, Deserialize, Serialize)]
48#[non_exhaustive]
49pub struct Span {
50 /// Line of the start position (1-based).
51 pub start_line: usize,
52 /// Column of the start position (1-based).
53 pub start_col: usize,
54 /// Line of the end position (1-based).
55 pub end_line: usize,
56 /// Column of the end position (1-based).
57 pub end_col: usize,
58 /// Byte offset of the node's first byte in the source (0-based).
59 #[serde(default)]
60 pub start_byte: usize,
61 /// Byte offset one past the node's last byte in the source (0-based,
62 /// exclusive).
63 #[serde(default)]
64 pub end_byte: usize,
65}
66
67impl Span {
68 /// Builds a [`Span`] from 1-based line/column pairs and 0-based,
69 /// half-open byte offsets (`[start_byte, end_byte)`).
70 ///
71 /// This is the supported construction path now that the struct is
72 /// `#[non_exhaustive]`.
73 #[must_use]
74 pub fn new(
75 start_line: usize,
76 start_col: usize,
77 end_line: usize,
78 end_col: usize,
79 start_byte: usize,
80 end_byte: usize,
81 ) -> Self {
82 Self {
83 start_line,
84 start_col,
85 end_line,
86 end_col,
87 start_byte,
88 end_byte,
89 }
90 }
91}
92
93/// The payload of an `Ast` request.
94///
95/// Unknown fields are rejected with a deserialization error naming the
96/// offending key, so a typo'd field cannot silently change request
97/// semantics (#633). The web boundary renders that as a `400` carrying the
98/// `unknown_field` `error_kind` token.
99#[derive(Debug, Deserialize, Serialize)]
100#[serde(deny_unknown_fields)]
101pub struct AstPayload {
102 /// The id associated to a request for an `AST`.
103 ///
104 /// Optional on the wire (#645): an omitted `id` deserializes to the
105 /// empty string, which every downstream surface already treats as
106 /// "no correlation id". Defaulting it stops clients eating a `400`
107 /// for a field whose absence has an obvious meaning.
108 #[serde(default)]
109 pub id: String,
110 /// The filename associated to a source code file
111 pub file_name: String,
112 /// The code to be represented as an `AST`
113 pub code: String,
114 /// If `true`, nodes representing comments are ignored. Optional on
115 /// the wire (#645): omitting it defaults to `false`, matching the
116 /// `bool` default and the most common request shape.
117 #[serde(default)]
118 pub comment: bool,
119 /// If `true`, the start and end positions of a node in a code
120 /// are considered. Optional on the wire (#645): omitting it defaults
121 /// to `false`.
122 #[serde(default)]
123 pub span: bool,
124}
125
126/// The response of an `AST` request.
127///
128/// The envelope echoes the resolved `language` slug alongside `id` and
129/// `root`, matching the `/function`, `/comment`, and `/metrics` analysis
130/// endpoints (#654). AST node kinds are grammar-specific, so an `/ast`
131/// consumer most needs to confirm which grammar actually parsed the
132/// source. `language` is the #540 canonical lowercase slug (the same value
133/// the sibling endpoints emit). The added field is a `2.0`-line shape
134/// change to this published library type (STABILITY.md).
135#[derive(Debug, Serialize)]
136pub struct AstResponse {
137 /// The id associated to a request for an `AST`
138 pub id: String,
139 /// The resolved source-language slug that produced this tree (#654).
140 ///
141 /// The #540 canonical lowercase slug (e.g. `cpp`, `python`), matching
142 /// the other analysis endpoints' `language` echo.
143 pub language: String,
144 /// The root node of an `AST`
145 ///
146 /// If `None`, an error has occurred
147 pub root: Option<AstNode>,
148}
149
150/// Greatest AST depth [`AstNode`] will serialize.
151///
152/// An `AstNode` tree is as deep as the parsed expression nesting, which a
153/// caller controls directly — 100 000 levels fit in a 200 KB payload, well
154/// inside `bca-web`'s body cap. `serde` cannot emit a tree without one
155/// native stack frame per level, and overflowing that stack aborts the
156/// process rather than raising a catchable panic (#1056), so the depth is
157/// bounded: a deeper tree fails serialization with an ordinary serializer
158/// error naming the limit.
159///
160/// The bound is set well clear of real source: the deepest AST across the
161/// integration corpus under `tests/repositories` (TensorFlow, serde,
162/// DeepSpeech, …) is 188 levels. It is also set well clear of the stack:
163/// the earliest measured overflow of any emitted format was 2 000 levels
164/// on a debug build's default 2 MiB thread.
165///
166/// Read that 188 as a corpus figure, not a conversion rate. The depth
167/// counted here is the **`AstNode` tree after [`Alterator::alterate`]**,
168/// and how many levels one level of *source* nesting costs is a
169/// per-language property of what that alterator flattens. The Tcl family
170/// is the outlier: since #1381 a script body keeps its children, so one
171/// brace level spans `braced_word` → `command` → `word_list` and costs
172/// three levels here — 196 levels over 64 nested `eval` braces, measured
173/// by `a_tcl_brace_level_costs_three_ast_levels` below — putting the
174/// ceiling near 170 nested braces rather than 512. Nothing in the corpus
175/// approaches either number — it holds no Tcl at all — but a caller
176/// re-deriving this bound from the 188 alone would be reasoning about
177/// the wrong quantity.
178///
179/// [`Alterator::alterate`]: crate::alterator::Alterator::alterate
180pub const MAX_AST_SERIALIZE_DEPTH: usize = 512;
181
182/// Serializes an [`AstNode`]'s children one level deeper, refusing to
183/// descend past [`MAX_AST_SERIALIZE_DEPTH`].
184fn serialize_children<S: serde::Serializer>(
185 children: &[AstNode],
186 serializer: S,
187) -> Result<S::Ok, S::Error> {
188 crate::recursion::serialize_bounded(children, MAX_AST_SERIALIZE_DEPTH, "AstNode", serializer)
189}
190
191/// Information on an `AST` node.
192///
193/// Serialized as a flat object with `snake_case` keys: `type`, `value`,
194/// `span`, `field_name`, `children`.
195#[derive(Debug, Serialize)]
196#[serde(rename_all = "snake_case")]
197pub struct AstNode {
198 /// The type of node
199 pub r#type: &'static str,
200 /// The code associated to a node
201 pub value: String,
202 /// The start and end positions of a node in a code
203 pub span: Option<Span>,
204 /// Tree-sitter grammar field name through which the parent reaches
205 /// this node (e.g. `left`, `right`, `name`, `body`).
206 ///
207 /// `None` for the root node, anonymous tokens (punctuation, keywords),
208 /// and any child that does not occupy a named grammar field. Consumers
209 /// of the JSON output rely on this to distinguish structurally
210 /// equivalent children without grammar-specific positional knowledge.
211 pub field_name: Option<&'static str>,
212 /// The children of a node
213 #[serde(serialize_with = "serialize_children")]
214 pub children: Vec<AstNode>,
215}
216
217// AST depth is caller-controlled — 100 000 levels of nested parentheses
218// fit in a 200 KB payload — so the compiler-generated `Drop` glue would
219// recurse once per level and abort the process (#1056). See
220// [`crate::recursion`].
221crate::recursion::impl_iterative_drop!(AstNode, children);
222
223impl AstNode {
224 /// Builds an `AstNode` with the supplied type, value, span, and
225 /// children. The `field_name` is set to `None`; use
226 /// [`AstNode::with_field_name`] to record the tree-sitter grammar
227 /// field through which the parent reaches this node.
228 #[must_use]
229 pub fn new(
230 r#type: &'static str,
231 value: String,
232 span: Option<Span>,
233 children: Vec<AstNode>,
234 ) -> Self {
235 Self::with_field_name(r#type, value, span, None, children)
236 }
237
238 /// Builds an `AstNode` carrying the tree-sitter grammar field name
239 /// (`left`, `right`, `name`, `body`, ...) through which the parent
240 /// reaches this node.
241 #[must_use]
242 pub fn with_field_name(
243 r#type: &'static str,
244 value: String,
245 span: Option<Span>,
246 field_name: Option<&'static str>,
247 children: Vec<AstNode>,
248 ) -> Self {
249 Self {
250 r#type,
251 value,
252 span,
253 field_name,
254 children,
255 }
256 }
257}
258
259// Entries into each export builder, on this thread.
260//
261// The two builders produce the same tree — `build_cursor` exists
262// because enumerating a flat `ERROR`'s children by index is quadratic
263// in its width, not because it answers differently — so no assertion
264// on a dump can tell which one `dump_inner` routed to. Rerouting the
265// default back to the indexed walk would pass every output test and
266// show up only as a slow `/ast` response on a recovery tree; the
267// counters are what make it a test failure instead (#1684).
268crate::observation::counter!(cursor_builds, cfg(any(test, feature = "test-support")));
269crate::observation::counter!(indexed_builds, cfg(any(test, feature = "test-support")));
270
271/// The pending state of one node while its subtree is being exported,
272/// bottom-up: the node, the grammar field its parent reached it
273/// through (`None` for the root), the children exported so far, and —
274/// read by [`build_indexed`] alone — the index of the next child to
275/// enter.
276struct Frame<'a> {
277 node: crate::Node<'a>,
278 field: Option<&'static str>,
279 children: Vec<AstNode>,
280 next_child: usize,
281}
282
283impl<'a> Frame<'a> {
284 fn new(node: crate::Node<'a>, field: Option<&'static str>) -> Self {
285 Self {
286 node,
287 field,
288 children: Vec::with_capacity(node.child_count()),
289 next_child: 0,
290 }
291 }
292}
293
294/// What both builders share: the frame stack and the ancestor chain
295/// that mirrors it, so the two cannot disagree on how a node is
296/// finished.
297///
298/// `chain` mirrors `stack`'s nodes, so popping both leaves `chain`
299/// holding exactly the popped node's ancestry. `Alterator::keeps_children`
300/// is the only consumer, and it is the reason this exists rather than
301/// climbing with `Node::parent`: that lookup is `O(depth)` and asking
302/// it per node made `Ast::dump` quadratic in nesting depth — 10 ms
303/// against 418 ms on 8 KB of nested Tcl braces, measured by swapping
304/// this for `Ancestors::unknown()` (#1381, the shape of #1052 / #1122).
305///
306/// That swap is invisible to the test suite: an unknown chain answers
307/// identically and only costs more, so nothing here pins the chain by
308/// asserting on output. Three things do. `Ancestors::for_walk` in
309/// [`Export::finish`] runs `Ancestors::checked`, whose `debug_assert!`
310/// catches a dropped pop on every fixture the dump walk sees, and
311/// `make chain-audit`
312/// upgrades it to the exact `chain.last() == node.parent()` check —
313/// the only one that sees a dropped *push*: `finish` pops before it
314/// asks, so a walk that never pushes empties the chain on its first
315/// node, and the containment check passes vacuously on an empty chain.
316/// The default build pins the push through `keeps_children` instead, in
317/// `each_strategy_hands_the_alterator_the_real_parent` below. And the
318/// swap itself is priced by `dump/tcl-nested-eval` in the benchmark
319/// harness, which it takes from 0.75 to 2.00.
320struct Export<'a, 'code> {
321 code: &'code [u8],
322 span: bool,
323 comment: bool,
324 stack: Vec<Frame<'a>>,
325 chain: Vec<crate::Node<'a>>,
326 /// The walk's memo, lent with the chain: Tcl's `keeps_children`
327 /// asks whether a braced word's argument list is readable, and
328 /// without this every word of a wide erroring line re-scanned the
329 /// list (#1686). `dump/tcl-wide-erroring-eval` prices it.
330 folds: FoldCache,
331}
332
333impl<'a, 'code> Export<'a, 'code> {
334 fn new(root: crate::Node<'a>, code: &'code [u8], span: bool, comment: bool) -> Self {
335 Self {
336 code,
337 span,
338 comment,
339 stack: vec![Frame::new(root, None)],
340 chain: vec![root],
341 folds: FoldCache::default(),
342 }
343 }
344
345 /// Descends into `child`, reached through `field`.
346 fn enter(&mut self, child: crate::Node<'a>, field: Option<&'static str>) {
347 self.stack.push(Frame::new(child, field));
348 self.chain.push(child);
349 }
350
351 /// Exports the node on top of the stack — every child of it has
352 /// been exported by now — and attaches it to its parent's frame.
353 /// Breaks with the export once the node finished was the root.
354 fn finish<T: ParserTrait>(&mut self) -> ControlFlow<Option<AstNode>> {
355 let frame = self
356 .stack
357 .pop()
358 .expect("stack invariant: finish is called only while a frame is pending");
359 self.chain.pop();
360 let node = T::Checker::get_ast_node(
361 &frame.node,
362 self.code,
363 self.span,
364 self.comment,
365 frame.field,
366 frame.children,
367 Ancestors::for_walk(&self.chain, &frame.node, &self.folds),
368 );
369 match self.stack.last_mut() {
370 Some(parent) => {
371 parent.children.extend(node);
372 ControlFlow::Continue(())
373 }
374 None => ControlFlow::Break(node),
375 }
376 }
377}
378
379/// The export walk over one cursor, which is what `dump_inner` runs.
380///
381/// A cursor steps to a sibling in amortised `O(1)` whatever the
382/// parent's shape — each hidden entry on its stack is pushed once and
383/// popped once — and reports the field of the node it sits on from the
384/// path it descended, at the cost of the hidden levels between the
385/// node and its visible parent: `O(log n)` under a balanced `repeat()`,
386/// `O(1)` under a flat node. The enumeration is therefore `O(n log n)`
387/// over a wide balanced list and `O(n)` over a flat one, never
388/// quadratic. Indexing the children instead is quadratic on a flat node
389/// — see [`build_indexed`] — and that difference is the whole reason
390/// there are two builders (#1684). What the alterator does per node is
391/// priced separately: `keeps_children` reads the ancestor chain, which
392/// `dump/tcl-nested-eval` covers, and the memo the export lends with
393/// it, which `dump/tcl-wide-erroring-eval` covers (#1686).
394///
395/// The cursor sits on the node of the top frame throughout. Each
396/// iteration descends as far as a first child exists, then finishes
397/// frames upward until a next sibling exists, which it enters, or the
398/// root is finished. A frame is never re-entered: `goto_parent` lands
399/// on a node whose children are all exported, and the only moves from
400/// there are a sibling or another climb. The field is read while the
401/// cursor is on the child, before descending further, because the
402/// cursor answers for its current position only.
403fn build_cursor<T: ParserTrait>(parser: &T, span: bool, comment: bool) -> Option<AstNode> {
404 cursor_builds::record();
405 let root = parser.root();
406 let mut export = Export::new(root, parser.code(), span, comment);
407 let mut cursor = root.cursor();
408 loop {
409 while cursor.goto_first_child() {
410 export.enter(cursor.node(), cursor.field_name());
411 }
412 loop {
413 if let ControlFlow::Break(root) = export.finish::<T>() {
414 return root;
415 }
416 if cursor.goto_next_sibling() {
417 export.enter(cursor.node(), cursor.field_name());
418 break;
419 }
420 // The root frame is finished above before this can fail,
421 // so a `false` here cannot leave the walk stranded.
422 let climbed = cursor.goto_parent();
423 debug_assert!(
424 climbed,
425 "the cursor must sit below the root while a frame is pending"
426 );
427 }
428 }
429}
430
431/// The export walk by child index, which `dump_indexed_inner` runs.
432///
433/// Each frame also remembers the next child index to enter.
434/// `Node::child` and `Node::field_name_for_child` both scan the
435/// parent's child array to that index, skipping hidden subtrees by
436/// their cached counts; see the `# Cost` note on
437/// [`Node::child`](crate::Node::child) for which nodes are flat.
438/// Enumerating a flat node this way is quadratic in its width, which
439/// `dump/perl-error-tail-calls` in the benchmark harness prices
440/// (#1684). This is kept as the explicit alternative for consumers
441/// that want index-addressed export, and as the second implementation
442/// the parity tests hold the default to.
443fn build_indexed<T: ParserTrait>(parser: &T, span: bool, comment: bool) -> Option<AstNode> {
444 indexed_builds::record();
445 let root = parser.root();
446 let mut export = Export::new(root, parser.code(), span, comment);
447 loop {
448 let frame = export
449 .stack
450 .last_mut()
451 .expect("stack invariant: loop only runs while a frame is pending");
452 let idx = frame.next_child;
453 if idx < frame.node.child_count() {
454 frame.next_child += 1;
455 let child = frame
456 .node
457 .child(idx)
458 .expect("stack invariant: idx < child_count so the child exists");
459 let field = frame.node.field_name_for_child(
460 u32::try_from(idx).expect("invariant: tree-sitter caps child indices at u32::MAX"),
461 );
462 export.enter(child, field);
463 } else if let ControlFlow::Break(root) = export.finish::<T>() {
464 return root;
465 }
466 }
467}
468
469/// Configuration options for retrieving the nodes of an `AST`.
470#[derive(Debug)]
471pub struct AstCfg {
472 /// The id associated to a request for an `AST`
473 pub id: String,
474 /// The resolved source-language slug to echo in the response
475 /// envelope (#654). The #540 canonical lowercase slug.
476 pub language: String,
477 /// If `true`, nodes representing comments are ignored
478 pub comment: bool,
479 /// If `true`, the start and end positions of a node in a code
480 /// are considered
481 pub span: bool,
482}
483
484/// Build the AST dump for `parser` under `cfg`. Backs `big_code_analysis::Ast::dump`;
485/// the AST-extraction analogue of `big_code_analysis::spaces::metrics_inner` /
486/// `big_code_analysis::ops::ops_inner`.
487///
488/// Walks the tree with one cursor — the same export as
489/// [`dump_cursor_inner`]. [`dump_indexed_inner`] is the explicit
490/// alternative that enumerates children by index; both produce the
491/// same tree, and differ only in cost (#1684).
492pub fn dump_inner<T: ParserTrait>(parser: &T, cfg: AstCfg) -> AstResponse {
493 dump_cursor_inner(parser, cfg)
494}
495
496/// [`dump_inner`], naming its strategy: one cursor walks the tree,
497/// stepping between siblings in amortised `O(1)` whatever the parent's
498/// shape.
499pub fn dump_cursor_inner<T: ParserTrait>(parser: &T, cfg: AstCfg) -> AstResponse {
500 AstResponse {
501 id: cfg.id,
502 language: cfg.language,
503 root: build_cursor(parser, cfg.span, cfg.comment),
504 }
505}
506
507/// [`dump_inner`] by child index: each child is reached through
508/// [`Node::child`](crate::Node::child) and its field through
509/// [`Node::field_name_for_child`](crate::Node::field_name_for_child).
510/// Same tree as the cursor walk; quadratic in the width of a flat
511/// recovery node, where the cursor walk is linear (#1684).
512pub fn dump_indexed_inner<T: ParserTrait>(parser: &T, cfg: AstCfg) -> AstResponse {
513 AstResponse {
514 id: cfg.id,
515 language: cfg.language,
516 root: build_indexed(parser, cfg.span, cfg.comment),
517 }
518}
519
520#[cfg(test)]
521mod tests {
522 use std::path::PathBuf;
523
524 use super::*;
525
526 /// One export entry point, generic over the parser it dumps.
527 #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
528 type Dump<P> = fn(&P, AstCfg) -> AstResponse;
529
530 /// The two explicit strategies, by name.
531 #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
532 fn strategies<P: ParserTrait>() -> [(&'static str, Dump<P>); 2] {
533 [
534 ("cursor", dump_cursor_inner),
535 ("indexed", dump_indexed_inner),
536 ]
537 }
538
539 #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
540 fn cfg_with(span: bool, comment: bool) -> AstCfg {
541 AstCfg {
542 id: String::new(),
543 language: String::new(),
544 comment,
545 span,
546 }
547 }
548
549 #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
550 fn build_ast_by<P: ParserTrait>(
551 dump: Dump<P>,
552 code: &[u8],
553 filename: &str,
554 span: bool,
555 comment: bool,
556 ) -> AstNode {
557 let path = PathBuf::from(filename);
558 let parser = P::new(code.to_vec(), &path, None);
559 dump(&parser, cfg_with(span, comment))
560 .root
561 .expect("parser should produce a root AST node")
562 }
563
564 /// Runs `check` on the root each strategy exports for `code`, so an
565 /// anchored assertion holds against each implementation on its own.
566 /// Parity between the two cannot see a defect they share, and a
567 /// value asserted through the default alone says nothing about the
568 /// other strategy.
569 #[cfg(any(feature = "cpp", feature = "rust", feature = "tcl"))]
570 fn for_each_strategy<P: ParserTrait>(
571 code: &[u8],
572 filename: &str,
573 span: bool,
574 check: impl Fn(&str, &AstNode),
575 ) {
576 for (name, dump) in strategies::<P>() {
577 check(name, &build_ast_by(dump, code, filename, span, false));
578 }
579 }
580
581 #[cfg(any(feature = "rust", feature = "tcl"))]
582 fn build_ast<P: ParserTrait>(code: &[u8], filename: &str) -> AstNode {
583 build_ast_by::<P>(dump_inner, code, filename, false, false)
584 }
585
586 #[cfg(feature = "rust")]
587 fn build_ast_with_span<P: ParserTrait>(code: &[u8], filename: &str) -> AstNode {
588 build_ast_by::<P>(dump_inner, code, filename, true, false)
589 }
590
591 /// Each direct child's `(type, field_name)`.
592 #[cfg(any(feature = "python", feature = "rust"))]
593 fn kinds_and_fields(node: &AstNode) -> Vec<(&'static str, Option<&'static str>)> {
594 node.children
595 .iter()
596 .map(|c| (c.r#type, c.field_name))
597 .collect()
598 }
599
600 /// How many nodes in `root`'s subtree have a type in `kinds`,
601 /// counted on an explicit stack.
602 #[cfg(feature = "rust")]
603 fn count_kinds(root: &AstNode, kinds: &[&str]) -> usize {
604 let mut pending = vec![root];
605 let mut found = 0;
606 while let Some(node) = pending.pop() {
607 found += usize::from(kinds.contains(&node.r#type));
608 pending.extend(&node.children);
609 }
610 found
611 }
612
613 #[cfg(any(feature = "cpp", feature = "rust"))]
614 fn find_first<'a>(node: &'a AstNode, kind: &str) -> Option<&'a AstNode> {
615 if node.r#type == kind {
616 return Some(node);
617 }
618 node.children.iter().find_map(|c| find_first(c, kind))
619 }
620
621 #[cfg(any(feature = "cpp", feature = "rust"))]
622 fn find_child<'a>(parent: &'a AstNode, field: &str) -> Option<&'a AstNode> {
623 parent.children.iter().find(|c| c.field_name == Some(field))
624 }
625
626 #[cfg(feature = "rust")]
627 #[test]
628 fn root_has_no_field_name() {
629 for_each_strategy::<crate::RustParser>(b"fn main() {}", "test.rs", false, |name, root| {
630 assert_eq!(root.field_name, None, "{name}");
631 });
632 }
633
634 #[cfg(feature = "rust")]
635 #[test]
636 fn rust_assignment_carries_left_and_right_field_names() {
637 // `assignment_expression` in the Rust grammar names its operands
638 // `left` and `right`. Without `FieldName` exposed in the JSON,
639 // downstream consumers cannot distinguish the two `identifier`
640 // children. This is the canonical example from issue #244.
641 let code = b"fn f() { let mut a = 0; a = a + 1; }";
642 for_each_strategy::<crate::RustParser>(code, "test.rs", false, |name, root| {
643 let assign = find_first(root, "assignment_expression")
644 .expect("expected an assignment_expression node");
645 let left = find_child(assign, "left").expect("expected a `left` child");
646 let right = find_child(assign, "right").expect("expected a `right` child");
647 assert_eq!(left.field_name, Some("left"), "{name}");
648 assert_eq!(right.field_name, Some("right"), "{name}");
649 // The anonymous `=` token is a child too, with no field name,
650 // and nothing else sits between the operands.
651 assert_eq!(
652 kinds_and_fields(assign),
653 [
654 ("identifier", Some("left")),
655 ("=", None),
656 ("binary_expression", Some("right")),
657 ],
658 "{name}"
659 );
660 });
661 }
662
663 #[cfg(feature = "rust")]
664 #[test]
665 fn rust_function_carries_name_and_body_field_names() {
666 // `function_item` names children `name`, `parameters`, `body`.
667 // Assert the field name directly on the AstNode so a bug that
668 // misnames a field (e.g. always emits "body") fails even if
669 // the target node kinds coincidentally line up.
670 let code = b"fn greet(name: &str) -> &str { name }";
671 for_each_strategy::<crate::RustParser>(code, "test.rs", false, |name, root| {
672 let func = find_first(root, "function_item").expect("expected a function_item node");
673 let name_child =
674 find_child(func, "name").expect("function_item should have a name child");
675 assert_eq!(name_child.field_name, Some("name"), "{name}");
676 assert_eq!(name_child.r#type, "identifier", "{name}");
677 let params_child = find_child(func, "parameters")
678 .expect("function_item should have a parameters child");
679 assert_eq!(params_child.field_name, Some("parameters"), "{name}");
680 assert_eq!(params_child.r#type, "parameters", "{name}");
681 let body_child =
682 find_child(func, "body").expect("function_item should have a body child");
683 assert_eq!(body_child.field_name, Some("body"), "{name}");
684 assert_eq!(body_child.r#type, "block", "{name}");
685 });
686 }
687
688 #[cfg(feature = "cpp")]
689 #[test]
690 fn cpp_assignment_carries_left_and_right_field_names() {
691 // Cross-language confirmation: the C/C++ grammar uses the same
692 // `left`/`right` field names for `assignment_expression`.
693 let code = b"int main(){ int x = 0; x = x + 1; }";
694 for_each_strategy::<crate::CppParser>(code, "test.cpp", false, |name, root| {
695 let assign = find_first(root, "assignment_expression")
696 .expect("expected an assignment_expression node");
697 assert_eq!(
698 find_child(assign, "left").map(|n| n.r#type),
699 Some("identifier"),
700 "{name}"
701 );
702 assert_eq!(
703 find_child(assign, "right").map(|n| n.r#type),
704 Some("binary_expression"),
705 "{name}"
706 );
707 });
708 }
709
710 #[cfg(feature = "rust")]
711 #[test]
712 fn serialized_json_includes_field_name_key() {
713 // Regression for the Serialize derive: every node must serialize
714 // a `field_name` key (null or string). Verifying via JSON
715 // string-match catches accidental removal of the field from
716 // the serializer.
717 let root = build_ast::<crate::RustParser>(b"fn f(){ let a = 1; }", "test.rs");
718 let json = serde_json::to_string(&root).expect("serialize");
719 assert!(
720 json.contains("\"field_name\""),
721 "field_name missing from JSON: {json}"
722 );
723 // The let binding's `pattern` and `value` fields should both
724 // appear as string values in the JSON.
725 assert!(
726 json.contains("\"field_name\":\"pattern\""),
727 "expected pattern field name; got {json}"
728 );
729 assert!(
730 json.contains("\"field_name\":\"value\""),
731 "expected value field name; got {json}"
732 );
733 }
734
735 #[cfg(feature = "rust")]
736 #[test]
737 fn serialized_json_uses_snake_case_keys() {
738 // The serialized AST shape uses snake_case keys (#535). This
739 // anchors the key scheme against accidental reversion to the
740 // former PascalCase `Type`/`TextValue`/`Span`/`Children`.
741 let root = build_ast_with_span::<crate::RustParser>(b"fn f(){}", "test.rs");
742 let json = serde_json::to_string(&root).expect("serialize");
743 for key in [
744 "\"type\":",
745 "\"value\":",
746 "\"span\":",
747 "\"field_name\":",
748 "\"children\":",
749 ] {
750 assert!(json.contains(key), "expected key {key}; got {json}");
751 }
752 for legacy in ["\"Type\"", "\"TextValue\"", "\"Span\"", "\"Children\""] {
753 assert!(
754 !json.contains(legacy),
755 "unexpected PascalCase key {legacy}; got {json}"
756 );
757 }
758 }
759
760 #[cfg(feature = "rust")]
761 #[test]
762 fn span_serializes_as_named_object() {
763 // The span is a flat named object preserving the 1-based
764 // tree-sitter line/column values in the original tuple order
765 // (start_line, start_col, end_line, end_col). The `*_line`
766 // vocabulary matches /function and /metrics (#638).
767 // `fn f(){}` is 8 bytes on one line, so the root spans the whole
768 // half-open byte range [0, 8) (#727).
769 for_each_strategy::<crate::RustParser>(b"fn f(){}", "test.rs", true, |name, root| {
770 let span = root
771 .span
772 .expect("root span present when span tracking is on");
773 assert_eq!(span, Span::new(1, 1, 1, 9, 0, 8), "{name}");
774 let json = serde_json::to_string(&root.span).expect("serialize span");
775 assert!(
776 json.contains("\"start_line\":1")
777 && json.contains("\"start_col\":1")
778 && json.contains("\"end_line\":1")
779 && json.contains("\"end_col\":9")
780 && json.contains("\"start_byte\":0")
781 && json.contains("\"end_byte\":8"),
782 "expected named span object with byte offsets; got {json}"
783 );
784 // The pre-2.0 `*_row` keys must be gone (#638).
785 assert!(
786 !json.contains("start_row") && !json.contains("end_row"),
787 "unexpected pre-2.0 *_row span keys; got {json}"
788 );
789 });
790 }
791
792 #[test]
793 fn span_round_trips_through_serde() {
794 // Span derives Deserialize for wire round-trip parity.
795 let span = Span::new(2, 3, 4, 5, 11, 42);
796 let json = serde_json::to_string(&span).expect("serialize");
797 let back: Span = serde_json::from_str(&json).expect("deserialize");
798 assert_eq!(span, back);
799 }
800
801 #[test]
802 fn span_deserializes_pre_byte_offsets_with_default() {
803 // The byte fields carry `#[serde(default)]`, so a span object
804 // serialized before they existed (line/col only) still
805 // deserializes, with the offsets defaulting to 0 (#727).
806 let legacy = r#"{"start_line":2,"start_col":3,"end_line":4,"end_col":5}"#;
807 let span: Span = serde_json::from_str(legacy).expect("deserialize legacy span");
808 assert_eq!(span, Span::new(2, 3, 4, 5, 0, 0));
809 }
810
811 // -----------------------------------------------------------------
812 // Stack-depth regression tests (#1056)
813 // -----------------------------------------------------------------
814
815 /// A chain of `depth` nested [`AstNode`]s below the root, built
816 /// directly so the depth is exact rather than a function of how many
817 /// AST levels a grammar spends per source construct.
818 fn ast_chain(depth: usize) -> AstNode {
819 let mut node = AstNode::new("leaf", String::new(), None, Vec::new());
820 for _ in 0..depth {
821 node = AstNode::new("branch", String::new(), None, vec![node]);
822 }
823 node
824 }
825
826 #[test]
827 fn ast_depth_at_the_serialize_limit_is_accepted_and_one_deeper_is_not() {
828 let at_limit = ast_chain(MAX_AST_SERIALIZE_DEPTH);
829 serde_json::to_string(&at_limit).expect("the limit itself must serialize");
830
831 let past_limit = ast_chain(MAX_AST_SERIALIZE_DEPTH + 1);
832 let err = serde_json::to_string(&past_limit).expect_err("one deeper must be refused");
833 assert!(
834 err.to_string().contains(&format!(
835 "AstNode nesting is deeper than the serialization limit of \
836 {MAX_AST_SERIALIZE_DEPTH} levels"
837 )),
838 "the error must name the type and the limit, got: {err}"
839 );
840 }
841
842 /// The deepest `children` chain in a tree, measured iteratively so a
843 /// pathological input cannot overflow the measurement itself.
844 #[cfg(feature = "tcl")]
845 fn ast_depth(root: &AstNode) -> usize {
846 let mut deepest = 0;
847 let mut stack = vec![(root, 1usize)];
848 while let Some((node, depth)) = stack.pop() {
849 deepest = deepest.max(depth);
850 stack.extend(node.children.iter().map(|child| (child, depth + 1)));
851 }
852 deepest
853 }
854
855 /// What one level of Tcl brace nesting costs in `AstNode` levels, and
856 /// therefore how far [`MAX_AST_SERIALIZE_DEPTH`] actually reaches for
857 /// this language.
858 ///
859 /// The bound's doc quotes a corpus figure of 188 levels, which is a
860 /// count of `AstNode` levels and not a conversion rate from source
861 /// nesting. Since #1381 a Tcl script body keeps its children, so the
862 /// two quantities came apart here more than anywhere else: this test
863 /// is what keeps the number in that doc honest, and what would notice
864 /// if an alterator change moved it again.
865 #[cfg(feature = "tcl")]
866 #[test]
867 fn a_tcl_brace_level_costs_three_ast_levels() {
868 // `eval` evaluates every argument, so each level keeps its
869 // children rather than flattening to a verbatim leaf.
870 let levels = 64;
871 let code = format!("{}puts hi{}", "eval {".repeat(levels), "}".repeat(levels));
872
873 let root = build_ast::<crate::TclParser>(code.as_bytes(), "deep.tcl");
874 let depth = ast_depth(&root);
875 let per_level = depth / levels;
876
877 // Measured 196 over 64 at the pinned grammar: `braced_word` ->
878 // `command` -> `word_list` before the next `braced_word`. The
879 // range admits one level of drift either way so a grammar bump
880 // reports the change rather than simply going red.
881 assert!(
882 (3..=4).contains(&per_level),
883 "a braced script level should cost 3 AstNode levels \
884 (braced_word -> command -> word_list); measured {depth} \
885 levels over {levels} braces = {per_level}"
886 );
887 // The consequence worth stating in one place: the 512-level bound
888 // is a low-hundreds brace ceiling for Tcl, not a 512 one.
889 let ceiling = MAX_AST_SERIALIZE_DEPTH / per_level;
890 assert!(
891 (120..=180).contains(&ceiling),
892 "the effective Tcl brace ceiling should sit near 170, got \
893 {ceiling} from {per_level} levels per brace"
894 );
895 }
896
897 // -----------------------------------------------------------------
898 // Two export strategies (#1684)
899 // -----------------------------------------------------------------
900
901 /// Which builder each entry point runs.
902 ///
903 /// Nothing in the output can say: both builders produce the same
904 /// tree, so routing `dump_inner` back to `build_indexed` would pass
905 /// every assertion on a dump and show up only as a quadratic `/ast`
906 /// response on a recovery tree. Each delta is asserted against a
907 /// seeded count rather than zero, so a `record()` that was never
908 /// wired up cannot pass either.
909 #[cfg(feature = "rust")]
910 #[test]
911 fn each_entry_point_enters_exactly_its_own_builder() {
912 let parser = crate::RustParser::new(b"fn f() {}".to_vec(), &PathBuf::from("a.rs"), None);
913 let _ = dump_cursor_inner(&parser, cfg_with(false, false));
914 let _ = dump_indexed_inner(&parser, cfg_with(false, false));
915 let (cursor_seed, indexed_seed) = (cursor_builds::observed(), indexed_builds::observed());
916 assert!(
917 cursor_seed > 0 && indexed_seed > 0,
918 "the seed calls must be counted"
919 );
920
921 let entries: [(&str, Dump<crate::RustParser>, usize, usize); 3] = [
922 ("dump_inner", dump_inner, 1, 0),
923 ("dump_cursor_inner", dump_cursor_inner, 1, 0),
924 ("dump_indexed_inner", dump_indexed_inner, 0, 1),
925 ];
926 let (mut cursor_total, mut indexed_total) = (cursor_seed, indexed_seed);
927 for (name, dump, cursor_delta, indexed_delta) in entries {
928 let _ = dump(&parser, cfg_with(false, false));
929 cursor_total += cursor_delta;
930 indexed_total += indexed_delta;
931 assert_eq!(
932 (cursor_builds::observed(), indexed_builds::observed()),
933 (cursor_total, indexed_total),
934 "{name} must enter the cursor builder {cursor_delta} time(s) and the indexed \
935 builder {indexed_delta} time(s)"
936 );
937 }
938 }
939
940 /// A cursor climbs no higher than the node it was built on, and
941 /// answers no field for that node: whole-tree parity cannot show
942 /// either, since the walk there starts at the root, which has no
943 /// parent to climb to or field to hide.
944 #[cfg(feature = "rust")]
945 #[test]
946 fn a_cursor_reports_fields_below_its_start_and_cannot_climb_above_it() {
947 let parser = crate::RustParser::new(
948 b"fn f(a: u8) { let b = a; }".to_vec(),
949 &PathBuf::from("a.rs"),
950 None,
951 );
952 let func = parser
953 .root()
954 .children()
955 .find(|n| n.kind() == "function_item")
956 .expect("fixture has a function");
957 let mut cursor = func.cursor();
958
959 assert_eq!(cursor.node().id(), func.id());
960 // `function_item` sits in no field of `source_file`, so this is
961 // `None` for two reasons; the subtree case below is the one
962 // that tells them apart.
963 assert_eq!(cursor.field_name(), None);
964 assert!(!cursor.goto_parent(), "the start node is the ceiling");
965 assert_eq!(
966 cursor.node().id(),
967 func.id(),
968 "a refused climb must not move"
969 );
970
971 assert!(cursor.goto_first_child());
972 let mut fields = Vec::new();
973 loop {
974 fields.push((cursor.node().kind(), cursor.field_name()));
975 if !cursor.goto_next_sibling() {
976 break;
977 }
978 }
979 assert_eq!(
980 fields,
981 [
982 ("fn", None),
983 ("identifier", Some("name")),
984 ("parameters", Some("parameters")),
985 ("block", Some("body")),
986 ],
987 "fields read off the cursor must match the grammar's"
988 );
989
990 assert!(cursor.goto_parent());
991 assert_eq!(cursor.node().id(), func.id());
992 assert!(
993 !cursor.goto_parent(),
994 "back at the start node, the ceiling holds"
995 );
996
997 // A node reached by descending from a cursor started above it
998 // *does* know its field, and the same node hides it again once
999 // a reset makes it the start: the `None` is the ceiling, not
1000 // the grammar.
1001 let let_decl = func
1002 .preorder()
1003 .find(|n| n.kind() == "let_declaration")
1004 .expect("fixture has a let");
1005 let mut from_parent = let_decl.cursor();
1006 assert!(from_parent.goto_first_child() && from_parent.goto_next_sibling());
1007 assert_eq!(from_parent.node().kind(), "identifier");
1008 assert_eq!(from_parent.field_name(), Some("pattern"));
1009 cursor.reset(&from_parent.node());
1010 assert_eq!(
1011 cursor.node().id(),
1012 from_parent.node().id(),
1013 "the reset must move the cursor before its answer means anything"
1014 );
1015 assert_eq!(
1016 cursor.field_name(),
1017 None,
1018 "after a reset the new start node hides its field exactly as the original did"
1019 );
1020 }
1021
1022 /// A field a visible rule inherits from a hidden one is reported,
1023 /// with the same name, by both strategies. The cursor reads it off
1024 /// the token's hidden parent on the way up and the index lookup
1025 /// carries it down through the same level, and the parity sweep's
1026 /// fixtures name no such field, so a grammar that broke the
1027 /// agreement would be caught only by accident there. Python's
1028 /// `comparison_operator` reaches each operator token through
1029 /// `operators`, an entry its `parser.c` marks `.inherited`; the
1030 /// token sits one hidden `_repeat1` level down, so this pins the
1031 /// propagation, not a multi-level climb.
1032 #[cfg(feature = "python")]
1033 #[test]
1034 fn each_strategy_reports_a_field_inherited_through_a_hidden_rule() {
1035 let code = b"a < b <= c\n";
1036 for (name, dump) in strategies::<crate::PythonParser>() {
1037 let root = build_ast_by(dump, code, "c.py", false, false);
1038 let comparison = kinds_and_fields(&root.children[0].children[0]);
1039 // expected: the two operator tokens carry `operators`; the
1040 // three operands sit in no field.
1041 assert_eq!(
1042 comparison,
1043 [
1044 ("identifier", None),
1045 ("<", Some("operators")),
1046 ("identifier", None),
1047 ("<=", Some("operators")),
1048 ("identifier", None),
1049 ],
1050 "{name}"
1051 );
1052 }
1053 }
1054
1055 /// The comment filter, asserted on each strategy against an
1056 /// independently derived expectation. The parity sweep's fixtures
1057 /// hold almost no comments, and the filter lives in the step both
1058 /// builders share, so a defect there would hold parity while
1059 /// dropping or keeping the wrong nodes on both.
1060 #[cfg(feature = "rust")]
1061 #[test]
1062 fn each_strategy_filters_comments_only_when_asked() {
1063 let code = b"// lead\nfn f() {\n // inner\n let a = 1; /* trail */\n}\n";
1064 for (name, dump) in strategies::<crate::RustParser>() {
1065 for (comment, expected) in [(false, 3), (true, 0)] {
1066 let root = build_ast_by(dump, code, "c.rs", true, comment);
1067 let comments = count_kinds(&root, &["line_comment", "block_comment"]);
1068 // expected: the fixture spells two `//` and one `/* */`
1069 // comment; with the filter on, none survives, and the
1070 // retained content is untouched either way.
1071 assert_eq!(comments, expected, "{name}, comment={comment}");
1072 assert_eq!(
1073 count_kinds(&root, &["let_declaration"]),
1074 1,
1075 "{name}, comment={comment}: the `let` must survive the filter"
1076 );
1077 }
1078 }
1079 }
1080
1081 /// Both envelope fields pass through each explicit entry point
1082 /// unchanged, with values that are not the empty-string default so
1083 /// a dropped or swapped field cannot read as correct.
1084 #[cfg(feature = "rust")]
1085 #[test]
1086 fn each_strategy_echoes_the_request_metadata() {
1087 let parser = crate::RustParser::new(b"fn f() {}".to_vec(), &PathBuf::from("a.rs"), None);
1088 let default: (&str, Dump<crate::RustParser>) = ("default", dump_inner);
1089 // The explicit strategies first, so a defect in one of them is
1090 // reported under its own name rather than as `default`.
1091 for (name, dump) in strategies().into_iter().chain([default]) {
1092 let resp = dump(
1093 &parser,
1094 AstCfg {
1095 id: "req-42".to_owned(),
1096 language: "rust".to_owned(),
1097 comment: false,
1098 span: false,
1099 },
1100 );
1101 assert_eq!(
1102 (resp.id.as_str(), resp.language.as_str()),
1103 ("req-42", "rust"),
1104 "{name}"
1105 );
1106 assert_eq!(resp.root.map(|r| r.r#type), Some("source_file"), "{name}");
1107 }
1108 }
1109
1110 /// The ancestor chain each builder hands `keeps_children` names the
1111 /// node's real parent, on every push as well as every pop.
1112 ///
1113 /// `Ancestors::checked`'s default-build `debug_assert!` sees a
1114 /// dropped *pop* — the stale entry no longer contains the node —
1115 /// but not a dropped *push*: `finish` pops before it asks, so a walk
1116 /// that never pushes empties the chain on its first node, and the
1117 /// containment check passes vacuously on an empty chain. Only
1118 /// `make chain-audit` asks
1119 /// the exact question, so this pins the push half through its one
1120 /// consumer. A braced word directly under a `command` is that
1121 /// command's *name*, a literal the alterator flattens to a leaf;
1122 /// the same word under the root or under a `word_list` would be a
1123 /// script and keep its children. `{puts} hi` is therefore a leaf
1124 /// only when the parent handed down really is the `command`, and
1125 /// `eval {puts a}` beside it is the script case, so a chain that
1126 /// answers the root for everything moves exactly one of the two.
1127 #[cfg(feature = "tcl")]
1128 #[test]
1129 fn each_strategy_hands_the_alterator_the_real_parent() {
1130 let code = b"{puts} hi\neval {puts a}\n";
1131 for_each_strategy::<crate::TclParser>(code, "name.tcl", false, |name, root| {
1132 let braced: Vec<(&str, Vec<&str>)> = root
1133 .children
1134 .iter()
1135 .flat_map(|command| command.children.iter())
1136 .flat_map(|word| {
1137 // The command name sits directly under `command`;
1138 // the script argument is one `word_list` down.
1139 std::iter::once(word).chain(word.children.iter())
1140 })
1141 .filter(|node| node.r#type == "braced_word")
1142 .map(|node| {
1143 let kinds: Vec<&str> = node.children.iter().map(|c| c.r#type).collect();
1144 (node.value.as_str(), kinds)
1145 })
1146 .collect();
1147 // expected: the name `{puts}` is a literal leaf carrying its
1148 // text; the `eval` body is an internal node — no text —
1149 // keeping `{`, the inner `command`, and `}`.
1150 assert_eq!(
1151 braced,
1152 [("{puts}", vec![]), ("", vec!["{", "command", "}"])],
1153 "{name}"
1154 );
1155 });
1156 }
1157
1158 /// Each builder lends `keeps_children` the export's `FoldCache`, so a
1159 /// wide erroring `eval` line is scanned once per export rather than
1160 /// once per braced word (#1686). The export is the same either way —
1161 /// every word keeps its children, as the count pins — so only the
1162 /// scan count can see the cache; rebuilding the chain in
1163 /// `Export::finish` with `Ancestors::checked` alone, the cache
1164 /// unlent, takes it to `width` for both strategies.
1165 #[cfg(feature = "tcl")]
1166 #[test]
1167 fn each_strategy_scans_an_erroring_argument_list_once() {
1168 use crate::lang_helpers::argument_slot_scans;
1169
1170 let width = 200;
1171 let code = crate::test_support::tcl_wide_erroring_eval(width);
1172 for (name, dump) in strategies::<crate::TclParser>() {
1173 let before = argument_slot_scans::observed();
1174 let root = build_ast_by(dump, code.as_bytes(), "wide.tcl", false, false);
1175 assert_eq!(
1176 argument_slot_scans::observed() - before,
1177 1,
1178 "{name}: the export lends one cache for the whole walk"
1179 );
1180 let kept = root
1181 .children
1182 .iter()
1183 .flat_map(|command| command.children.iter())
1184 .flat_map(|list| list.children.iter())
1185 .filter(|word| word.r#type == "braced_word" && !word.children.is_empty())
1186 .count();
1187 assert_eq!(
1188 kept, width,
1189 "{name}: every `eval` argument keeps its children"
1190 );
1191 }
1192 }
1193
1194 /// A file whose only child is a filtered comment: the cursor walk
1195 /// finishes that child with nothing to attach, climbs, and must
1196 /// still finish the root rather than look for another sibling.
1197 #[cfg(feature = "rust")]
1198 #[test]
1199 fn a_comment_only_source_exports_a_childless_root_under_either_strategy() {
1200 let code = b"// only\n";
1201 for (name, dump) in strategies::<crate::RustParser>() {
1202 let keep = build_ast_by(dump, code, "a.rs", false, false);
1203 assert_eq!(
1204 keep.children.len(),
1205 1,
1206 "{name}: without the filter the root keeps its one comment child"
1207 );
1208 let root = build_ast_by(dump, code, "a.rs", false, true);
1209 assert_eq!(
1210 kinds_and_fields(&root),
1211 [],
1212 "{name}: the comment child must be filtered"
1213 );
1214 }
1215 }
1216
1217 #[test]
1218 fn a_pathologically_deep_ast_errors_and_tears_down_without_overflowing() {
1219 // The chain is built directly rather than parsed, but this depth
1220 // is reachable through `bca-web`'s `/ast`: 50 000 levels of
1221 // nested parentheses fit in 100 KB, an order of magnitude inside
1222 // the 4 MiB body cap. Both the recursive `Serialize` and the
1223 // compiler-generated `Drop` glue used to abort the process here —
1224 // `SIGABRT`, which `spawn_blocking` cannot contain (#1056).
1225 const DEPTH: usize = 50_000;
1226 // The stack a `bca` consumer thread and a `tokio` blocking thread
1227 // get; the serialization limit is dimensioned against it.
1228 const PRODUCTION_STACK: usize = 2 * 1024 * 1024;
1229 let message = std::thread::Builder::new()
1230 .stack_size(PRODUCTION_STACK)
1231 .spawn(|| {
1232 let root = ast_chain(DEPTH);
1233 let message = serde_json::to_string(&root)
1234 .expect_err("depth past the limit must fail, not serialize")
1235 .to_string();
1236 // `root` drops here: the iterative `Drop` must unwind
1237 // 50 000 levels without touching the stack.
1238 message
1239 })
1240 .expect("spawn bounded-stack thread")
1241 .join()
1242 .expect("bounded-stack thread must not overflow");
1243 assert!(
1244 message.contains("AstNode nesting is deeper than the serialization limit"),
1245 "the error must explain the refusal, got: {message}"
1246 );
1247 }
1248}