Skip to main content

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    /// Whether a child of `node` may carry a field, so that reading
282    /// each child's is worth its cost.
283    fields: bool,
284}
285
286/// Child count from which a frame asks [`has_field_child`] before its
287/// children's fields are read one by one.
288///
289/// A child's field read climbs the hidden grammar levels between it and
290/// its visible parent, and every hidden level consumes input that lands
291/// among that parent's children, so a narrow node bounds the climb. A
292/// wide one need not: each parenthesis of a Tcl `expr` adds a hidden
293/// level under one flat node, which made reading every child's field
294/// quadratic in the count (#1938). Below this width the probe's scan of
295/// the grammar's field ids would cost more than it saves.
296const FIELD_PROBE_WIDTH: usize = 32;
297
298/// Whether some child of `node` carries a field name, through any hidden
299/// grammar levels between them.
300///
301/// `ts_node_child_by_field_id` reads the node's own production field
302/// map, which lists a hidden child's fields as inherited entries, and
303/// returns as soon as the sorted map shows it lacks the id. So this costs
304/// one scan of that small map per field the grammar names, however wide
305/// the node is.
306///
307/// An `ERROR` node has no production of its own, so its map is empty even
308/// where a hidden subtree recovery parked under it hands its visible
309/// children a field (a cursor reads `operators` on a Python `==` there).
310/// It always answers `true`.
311fn has_field_child(node: &crate::Node<'_>) -> bool {
312    if node.is_error() {
313        return true;
314    }
315    (1..=node.as_tree_sitter().language().field_count())
316        .filter_map(|id| u16::try_from(id).ok())
317        .any(|id| node.child_by_field_id(id).is_some())
318}
319
320impl<'a> Frame<'a> {
321    fn new(node: crate::Node<'a>, field: Option<&'static str>) -> Self {
322        let width = node.child_count();
323        Self {
324            node,
325            field,
326            children: Vec::with_capacity(width),
327            next_child: 0,
328            fields: width < FIELD_PROBE_WIDTH || has_field_child(&node),
329        }
330    }
331}
332
333/// What both builders share: the frame stack and the ancestor chain
334/// that mirrors it, so the two cannot disagree on how a node is
335/// finished.
336///
337/// `chain` mirrors `stack`'s nodes, so popping both leaves `chain`
338/// holding exactly the popped node's ancestry. `Alterator::keeps_children`
339/// is the only consumer, and it is the reason this exists rather than
340/// climbing with `Node::parent`: that lookup is `O(depth)` and asking
341/// it per node made `Ast::dump` quadratic in nesting depth — 10 ms
342/// against 418 ms on 8 KB of nested Tcl braces, measured by swapping
343/// this for `Ancestors::unknown()` (#1381, the shape of #1052 / #1122).
344///
345/// That swap is invisible to the test suite: an unknown chain answers
346/// identically and only costs more, so nothing here pins the chain by
347/// asserting on output. Three things do.
348/// `Ancestors::for_walk_without_siblings` in [`Export::finish`] checks
349/// the chain against the node, and that `debug_assert!`
350/// catches a dropped pop on every fixture the dump walk sees, and
351/// `make chain-audit`
352/// upgrades it to the exact `chain.last() == node.parent()` check —
353/// the only one that sees a dropped *push*: `finish` pops before it
354/// asks, so a walk that never pushes empties the chain on its first
355/// node, and the containment check passes vacuously on an empty chain.
356/// The default build pins the push through `keeps_children` instead, in
357/// `each_strategy_hands_the_alterator_the_real_parent` below. And the
358/// swap itself is priced by `dump/tcl-nested-eval` in the benchmark
359/// harness, which it takes from 0.75 to 2.00.
360struct Export<'a, 'code> {
361    code: &'code [u8],
362    span: bool,
363    comment: bool,
364    stack: Vec<Frame<'a>>,
365    chain: Vec<crate::Node<'a>>,
366    /// The walk's memo, lent with the chain: Tcl's `keeps_children`
367    /// asks whether a braced word's argument list is readable, and
368    /// without this every word of a wide erroring line re-scanned the
369    /// list (#1686). `dump/tcl-wide-erroring-eval` prices it.
370    ///
371    /// No `SiblingCache` beside it: no alterator asks for a sibling, and
372    /// this walk asks after a node's children are exported, so it has
373    /// no batch of pushed children to record. An alterator that starts
374    /// to ask under a wide parent trips the walk assertion in a debug
375    /// build (#1601).
376    folds: FoldCache,
377}
378
379impl<'a, 'code> Export<'a, 'code> {
380    fn new(root: crate::Node<'a>, code: &'code [u8], span: bool, comment: bool) -> Self {
381        Self {
382            code,
383            span,
384            comment,
385            stack: vec![Frame::new(root, None)],
386            chain: vec![root],
387            folds: FoldCache::default(),
388        }
389    }
390
391    /// Descends into `child`, reached through `field`.
392    fn enter(&mut self, child: crate::Node<'a>, field: Option<&'static str>) {
393        self.stack.push(Frame::new(child, field));
394        self.chain.push(child);
395    }
396
397    /// Whether the node on top of the stack may have a child with a
398    /// field, so that a child's field is worth reading.
399    fn children_may_have_fields(&self) -> bool {
400        self.stack.last().is_some_and(|parent| parent.fields)
401    }
402
403    /// Descends into the node `cursor` sits on, reading its field only
404    /// where its parent's children may carry one.
405    fn enter_at(&mut self, cursor: &crate::node::Cursor<'a>) {
406        let field = if self.children_may_have_fields() {
407            cursor.field_name()
408        } else {
409            None
410        };
411        self.enter(cursor.node(), field);
412    }
413
414    /// Exports the node on top of the stack — every child of it has
415    /// been exported by now — and attaches it to its parent's frame.
416    /// Breaks with the export once the node finished was the root, and
417    /// with no tree once the [`ParseCancel`](crate::cancel::ParseCancel)
418    /// installed on this thread is cancelled: a wide `ERROR` node still
419    /// has every child's field read, which is quadratic over deep hidden
420    /// nesting (#1942), and a `bca-web` request past its deadline must
421    /// not keep its thread for that long.
422    fn finish<T: ParserTrait>(&mut self) -> ControlFlow<Option<AstNode>> {
423        if crate::cancel::requested() {
424            return ControlFlow::Break(None);
425        }
426        let frame = self
427            .stack
428            .pop()
429            .expect("stack invariant: finish is called only while a frame is pending");
430        self.chain.pop();
431        let node = T::Checker::get_ast_node(
432            &frame.node,
433            self.code,
434            self.span,
435            self.comment,
436            frame.field,
437            frame.children,
438            Ancestors::for_walk_without_siblings(&self.chain, &frame.node, &self.folds),
439        );
440        match self.stack.last_mut() {
441            Some(parent) => {
442                parent.children.extend(node);
443                ControlFlow::Continue(())
444            }
445            None => ControlFlow::Break(node),
446        }
447    }
448}
449
450/// The export walk over one cursor, which is what `dump_inner` runs.
451///
452/// A cursor steps to a sibling in amortised `O(1)` whatever the
453/// parent's shape — each hidden entry on its stack is pushed once and
454/// popped once — and reports the field of the node it sits on from the
455/// path it descended, at the cost of the hidden levels between the
456/// node and its visible parent: `O(log n)` under a balanced `repeat()`,
457/// `O(1)` under a flat node. The enumeration is therefore `O(n log n)`
458/// over a wide balanced list and `O(n)` over a flat one, never
459/// quadratic. The field read is not that cheap everywhere: under a flat
460/// node whose children sit in *nested* hidden rules, such as a Tcl
461/// `expr`'s parentheses, it climbs one more level per child, so a wide
462/// node is first asked whether any child has a field at all
463/// ([`FIELD_PROBE_WIDTH`], #1938; `dump/tcl-expr-parens` prices it).
464/// Indexing the children instead is quadratic on a flat node
465/// — see [`build_indexed`] — and that difference is the whole reason
466/// there are two builders (#1684). What the alterator does per node is
467/// priced separately: `keeps_children` reads the ancestor chain, which
468/// `dump/tcl-nested-eval` covers, and the memo the export lends with
469/// it, which `dump/tcl-wide-erroring-eval` covers (#1686).
470///
471/// The cursor sits on the node of the top frame throughout. Each
472/// iteration descends as far as a first child exists, then finishes
473/// frames upward until a next sibling exists, which it enters, or the
474/// root is finished. A frame is never re-entered: `goto_parent` lands
475/// on a node whose children are all exported, and the only moves from
476/// there are a sibling or another climb. The field is read while the
477/// cursor is on the child, before descending further, because the
478/// cursor answers for its current position only.
479fn build_cursor<T: ParserTrait>(parser: &T, span: bool, comment: bool) -> Option<AstNode> {
480    cursor_builds::record();
481    let root = parser.root();
482    let mut export = Export::new(root, parser.code(), span, comment);
483    let mut cursor = root.cursor();
484    loop {
485        while cursor.goto_first_child() {
486            export.enter_at(&cursor);
487        }
488        loop {
489            if let ControlFlow::Break(root) = export.finish::<T>() {
490                return root;
491            }
492            if cursor.goto_next_sibling() {
493                export.enter_at(&cursor);
494                break;
495            }
496            // The root frame is finished above before this can fail,
497            // so a `false` here cannot leave the walk stranded.
498            let climbed = cursor.goto_parent();
499            debug_assert!(
500                climbed,
501                "the cursor must sit below the root while a frame is pending"
502            );
503        }
504    }
505}
506
507/// The export walk by child index, which `dump_indexed_inner` runs.
508///
509/// Each frame also remembers the next child index to enter.
510/// `Node::child` and `Node::field_name_for_child` both scan the
511/// parent's child array to that index, skipping hidden subtrees by
512/// their cached counts; see the `# Cost` note on
513/// [`Node::child`](crate::Node::child) for which nodes are flat.
514/// Enumerating a flat node this way is quadratic in its width, which
515/// `dump/perl-error-tail-calls` in the benchmark harness prices
516/// (#1684). This is kept as the explicit alternative for consumers
517/// that want index-addressed export, and as the second implementation
518/// the parity tests hold the default to.
519fn build_indexed<T: ParserTrait>(parser: &T, span: bool, comment: bool) -> Option<AstNode> {
520    indexed_builds::record();
521    let root = parser.root();
522    let mut export = Export::new(root, parser.code(), span, comment);
523    loop {
524        let frame = export
525            .stack
526            .last_mut()
527            .expect("stack invariant: loop only runs while a frame is pending");
528        let idx = frame.next_child;
529        if idx < frame.node.child_count() {
530            frame.next_child += 1;
531            let child = frame
532                .node
533                .child(idx)
534                .expect("stack invariant: idx < child_count so the child exists");
535            let field = if frame.fields {
536                frame.node.field_name_for_child(
537                    u32::try_from(idx)
538                        .expect("invariant: tree-sitter caps child indices at u32::MAX"),
539                )
540            } else {
541                None
542            };
543            export.enter(child, field);
544        } else if let ControlFlow::Break(root) = export.finish::<T>() {
545            return root;
546        }
547    }
548}
549
550/// Configuration options for retrieving the nodes of an `AST`.
551#[derive(Debug)]
552pub struct AstCfg {
553    /// The id associated to a request for an `AST`
554    pub id: String,
555    /// The resolved source-language slug to echo in the response
556    /// envelope (#654). The #540 canonical lowercase slug.
557    pub language: String,
558    /// If `true`, nodes representing comments are ignored
559    pub comment: bool,
560    /// If `true`, the start and end positions of a node in a code
561    /// are considered
562    pub span: bool,
563}
564
565/// Build the AST dump for `parser` under `cfg`. Backs `big_code_analysis::Ast::dump`;
566/// the AST-extraction analogue of `big_code_analysis::spaces::metrics_inner` /
567/// `big_code_analysis::ops::ops_inner`.
568///
569/// Walks the tree with one cursor — the same export as
570/// [`dump_cursor_inner`]. [`dump_indexed_inner`] is the explicit
571/// alternative that enumerates children by index; both produce the
572/// same tree, and differ only in cost (#1684).
573pub fn dump_inner<T: ParserTrait>(parser: &T, cfg: AstCfg) -> AstResponse {
574    dump_cursor_inner(parser, cfg)
575}
576
577/// [`dump_inner`], naming its strategy: one cursor walks the tree,
578/// stepping between siblings in amortised `O(1)` whatever the parent's
579/// shape.
580pub fn dump_cursor_inner<T: ParserTrait>(parser: &T, cfg: AstCfg) -> AstResponse {
581    AstResponse {
582        id: cfg.id,
583        language: cfg.language,
584        root: build_cursor(parser, cfg.span, cfg.comment),
585    }
586}
587
588/// [`dump_inner`] by child index: each child is reached through
589/// [`Node::child`](crate::Node::child) and its field through
590/// [`Node::field_name_for_child`](crate::Node::field_name_for_child).
591/// Same tree as the cursor walk; quadratic in the width of a flat
592/// recovery node, where the cursor walk is linear (#1684).
593pub fn dump_indexed_inner<T: ParserTrait>(parser: &T, cfg: AstCfg) -> AstResponse {
594    AstResponse {
595        id: cfg.id,
596        language: cfg.language,
597        root: build_indexed(parser, cfg.span, cfg.comment),
598    }
599}
600
601#[cfg(test)]
602mod tests {
603    use std::path::PathBuf;
604
605    use super::*;
606
607    /// One export entry point, generic over the parser it dumps.
608    #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
609    type Dump<P> = fn(&P, AstCfg) -> AstResponse;
610
611    /// The two explicit strategies, by name.
612    #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
613    fn strategies<P: ParserTrait>() -> [(&'static str, Dump<P>); 2] {
614        [
615            ("cursor", dump_cursor_inner),
616            ("indexed", dump_indexed_inner),
617        ]
618    }
619
620    #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
621    fn cfg_with(span: bool, comment: bool) -> AstCfg {
622        AstCfg {
623            id: String::new(),
624            language: String::new(),
625            comment,
626            span,
627        }
628    }
629
630    #[cfg(any(feature = "cpp", feature = "python", feature = "rust", feature = "tcl"))]
631    fn build_ast_by<P: ParserTrait>(
632        dump: Dump<P>,
633        code: &[u8],
634        filename: &str,
635        span: bool,
636        comment: bool,
637    ) -> AstNode {
638        let path = PathBuf::from(filename);
639        let parser = P::new(code.to_vec(), &path, None);
640        dump(&parser, cfg_with(span, comment))
641            .root
642            .expect("parser should produce a root AST node")
643    }
644
645    /// Runs `check` on the root each strategy exports for `code`, so an
646    /// anchored assertion holds against each implementation on its own.
647    /// Parity between the two cannot see a defect they share, and a
648    /// value asserted through the default alone says nothing about the
649    /// other strategy.
650    #[cfg(any(feature = "cpp", feature = "rust", feature = "tcl"))]
651    fn for_each_strategy<P: ParserTrait>(
652        code: &[u8],
653        filename: &str,
654        span: bool,
655        check: impl Fn(&str, &AstNode),
656    ) {
657        for (name, dump) in strategies::<P>() {
658            check(name, &build_ast_by(dump, code, filename, span, false));
659        }
660    }
661
662    #[cfg(any(feature = "rust", feature = "tcl"))]
663    fn build_ast<P: ParserTrait>(code: &[u8], filename: &str) -> AstNode {
664        build_ast_by::<P>(dump_inner, code, filename, false, false)
665    }
666
667    #[cfg(feature = "rust")]
668    fn build_ast_with_span<P: ParserTrait>(code: &[u8], filename: &str) -> AstNode {
669        build_ast_by::<P>(dump_inner, code, filename, true, false)
670    }
671
672    /// Each direct child's `(type, field_name)`.
673    #[cfg(any(feature = "python", feature = "rust"))]
674    fn kinds_and_fields(node: &AstNode) -> Vec<(&'static str, Option<&'static str>)> {
675        node.children
676            .iter()
677            .map(|c| (c.r#type, c.field_name))
678            .collect()
679    }
680
681    /// How many nodes in `root`'s subtree have a type in `kinds`,
682    /// counted on an explicit stack.
683    #[cfg(feature = "rust")]
684    fn count_kinds(root: &AstNode, kinds: &[&str]) -> usize {
685        let mut pending = vec![root];
686        let mut found = 0;
687        while let Some(node) = pending.pop() {
688            found += usize::from(kinds.contains(&node.r#type));
689            pending.extend(&node.children);
690        }
691        found
692    }
693
694    #[cfg(any(feature = "cpp", feature = "rust"))]
695    fn find_first<'a>(node: &'a AstNode, kind: &str) -> Option<&'a AstNode> {
696        if node.r#type == kind {
697            return Some(node);
698        }
699        node.children.iter().find_map(|c| find_first(c, kind))
700    }
701
702    #[cfg(any(feature = "cpp", feature = "rust"))]
703    fn find_child<'a>(parent: &'a AstNode, field: &str) -> Option<&'a AstNode> {
704        parent.children.iter().find(|c| c.field_name == Some(field))
705    }
706
707    /// A node `FIELD_PROBE_WIDTH` children wide or more is asked whether
708    /// any child has a field before its children's fields are read, and
709    /// one whose children do must still report each (#1938). A tuple
710    /// struct's `ordered_field_declaration_list` names every element type
711    /// `type`. expected: 40 `primitive_type` children with field `type`,
712    /// and none of the 41 punctuation children with a field.
713    #[cfg(feature = "rust")]
714    #[test]
715    fn a_wide_node_with_fields_keeps_them() {
716        const ELEMENTS: usize = 40;
717        const {
718            assert!(
719                2 * ELEMENTS + 1 >= FIELD_PROBE_WIDTH,
720                "the list must be wide enough to probe"
721            );
722        }
723        let code = format!("struct T({});\n", vec!["i32"; ELEMENTS].join(", "));
724        for_each_strategy::<crate::RustParser>(code.as_bytes(), "test.rs", false, |name, root| {
725            let list =
726                find_first(root, "ordered_field_declaration_list").expect("a tuple struct body");
727            let typed = list
728                .children
729                .iter()
730                .filter(|c| c.field_name == Some("type"))
731                .count();
732            assert_eq!(typed, ELEMENTS, "{name}");
733            assert!(
734                list.children
735                    .iter()
736                    .all(|c| (c.r#type == "primitive_type") == (c.field_name == Some("type"))),
737                "{name}"
738            );
739        });
740    }
741
742    /// An `ERROR` node has no production of its own, so the field probe
743    /// finds nothing on it, yet the hidden subtrees recovery leaves under
744    /// it still give its children fields (#1938). An unfinished tuple
745    /// struct recovers into one `ERROR` node whose element types keep
746    /// their `type` field; the export must keep every one whichever side
747    /// of the probe width the node falls. expected: the counts
748    /// `field_name_for_child` reads off the raw node, one per element but
749    /// the first, which recovery leaves without a field.
750    #[cfg(feature = "rust")]
751    #[test]
752    fn a_wide_error_node_keeps_its_childrens_fields() {
753        for (elements, typed) in [(10, 9), (20, 19)] {
754            let code = format!("struct T({}", "i32, ".repeat(elements));
755            let path = PathBuf::from("test.rs");
756            let parser = crate::RustParser::new(code.as_bytes().to_vec(), &path, None);
757            let error = parser
758                .root()
759                .preorder()
760                .find(crate::Node::is_error)
761                .expect("an unfinished tuple struct recovers into an ERROR");
762            let raw = (0..error.child_count())
763                .filter_map(|i| u32::try_from(i).ok())
764                .filter(|&i| error.field_name_for_child(i) == Some("type"))
765                .count();
766            assert_eq!(raw, typed, "raw at {elements}");
767            assert_eq!(
768                error.child_count() >= FIELD_PROBE_WIDTH,
769                elements == 20,
770                "the two inputs must straddle the probe width"
771            );
772            for_each_strategy::<crate::RustParser>(
773                code.as_bytes(),
774                "test.rs",
775                false,
776                |name, root| {
777                    let error = find_first(root, "ERROR").expect("the exported ERROR");
778                    let exported = error
779                        .children
780                        .iter()
781                        .filter(|c| c.field_name == Some("type"))
782                        .count();
783                    assert_eq!(exported, typed, "{name} at {elements}");
784                },
785            );
786        }
787    }
788
789    /// A cancelled flag stops the export as it stops the parse: a wide
790    /// `ERROR` node can make the export quadratic (#1942), and a
791    /// `bca-web` request past its deadline must not keep its thread for
792    /// that. The parse runs before the flag is installed, so only the
793    /// export sees it. expected: the full tree under a live flag, no tree
794    /// once it is cancelled, from both strategies.
795    #[cfg(feature = "rust")]
796    #[test]
797    fn a_cancelled_export_yields_no_tree() {
798        let path = PathBuf::from("test.rs");
799        let parser = crate::RustParser::new(b"fn f() {}\n".to_vec(), &path, None);
800        let cancel = crate::cancel::ParseCancel::new();
801        let export = |dump: Dump<crate::RustParser>| {
802            cancel.run(|| dump(&parser, cfg_with(false, false)).root)
803        };
804        for (name, dump) in strategies::<crate::RustParser>() {
805            assert!(export(dump).is_some(), "{name} under a live flag");
806        }
807        cancel.cancel();
808        for (name, dump) in strategies::<crate::RustParser>() {
809            assert!(export(dump).is_none(), "{name} under a cancelled flag");
810        }
811    }
812
813    #[cfg(feature = "rust")]
814    #[test]
815    fn root_has_no_field_name() {
816        for_each_strategy::<crate::RustParser>(b"fn main() {}", "test.rs", false, |name, root| {
817            assert_eq!(root.field_name, None, "{name}");
818        });
819    }
820
821    #[cfg(feature = "rust")]
822    #[test]
823    fn rust_assignment_carries_left_and_right_field_names() {
824        // `assignment_expression` in the Rust grammar names its operands
825        // `left` and `right`. Without `FieldName` exposed in the JSON,
826        // downstream consumers cannot distinguish the two `identifier`
827        // children. This is the canonical example from issue #244.
828        let code = b"fn f() { let mut a = 0; a = a + 1; }";
829        for_each_strategy::<crate::RustParser>(code, "test.rs", false, |name, root| {
830            let assign = find_first(root, "assignment_expression")
831                .expect("expected an assignment_expression node");
832            let left = find_child(assign, "left").expect("expected a `left` child");
833            let right = find_child(assign, "right").expect("expected a `right` child");
834            assert_eq!(left.field_name, Some("left"), "{name}");
835            assert_eq!(right.field_name, Some("right"), "{name}");
836            // The anonymous `=` token is a child too, with no field name,
837            // and nothing else sits between the operands.
838            assert_eq!(
839                kinds_and_fields(assign),
840                [
841                    ("identifier", Some("left")),
842                    ("=", None),
843                    ("binary_expression", Some("right")),
844                ],
845                "{name}"
846            );
847        });
848    }
849
850    #[cfg(feature = "rust")]
851    #[test]
852    fn rust_function_carries_name_and_body_field_names() {
853        // `function_item` names children `name`, `parameters`, `body`.
854        // Assert the field name directly on the AstNode so a bug that
855        // misnames a field (e.g. always emits "body") fails even if
856        // the target node kinds coincidentally line up.
857        let code = b"fn greet(name: &str) -> &str { name }";
858        for_each_strategy::<crate::RustParser>(code, "test.rs", false, |name, root| {
859            let func = find_first(root, "function_item").expect("expected a function_item node");
860            let name_child =
861                find_child(func, "name").expect("function_item should have a name child");
862            assert_eq!(name_child.field_name, Some("name"), "{name}");
863            assert_eq!(name_child.r#type, "identifier", "{name}");
864            let params_child = find_child(func, "parameters")
865                .expect("function_item should have a parameters child");
866            assert_eq!(params_child.field_name, Some("parameters"), "{name}");
867            assert_eq!(params_child.r#type, "parameters", "{name}");
868            let body_child =
869                find_child(func, "body").expect("function_item should have a body child");
870            assert_eq!(body_child.field_name, Some("body"), "{name}");
871            assert_eq!(body_child.r#type, "block", "{name}");
872        });
873    }
874
875    #[cfg(feature = "cpp")]
876    #[test]
877    fn cpp_assignment_carries_left_and_right_field_names() {
878        // Cross-language confirmation: the C/C++ grammar uses the same
879        // `left`/`right` field names for `assignment_expression`.
880        let code = b"int main(){ int x = 0; x = x + 1; }";
881        for_each_strategy::<crate::CppParser>(code, "test.cpp", false, |name, root| {
882            let assign = find_first(root, "assignment_expression")
883                .expect("expected an assignment_expression node");
884            assert_eq!(
885                find_child(assign, "left").map(|n| n.r#type),
886                Some("identifier"),
887                "{name}"
888            );
889            assert_eq!(
890                find_child(assign, "right").map(|n| n.r#type),
891                Some("binary_expression"),
892                "{name}"
893            );
894        });
895    }
896
897    #[cfg(feature = "rust")]
898    #[test]
899    fn serialized_json_includes_field_name_key() {
900        // Regression for the Serialize derive: every node must serialize
901        // a `field_name` key (null or string). Verifying via JSON
902        // string-match catches accidental removal of the field from
903        // the serializer.
904        let root = build_ast::<crate::RustParser>(b"fn f(){ let a = 1; }", "test.rs");
905        let json = serde_json::to_string(&root).expect("serialize");
906        assert!(
907            json.contains("\"field_name\""),
908            "field_name missing from JSON: {json}"
909        );
910        // The let binding's `pattern` and `value` fields should both
911        // appear as string values in the JSON.
912        assert!(
913            json.contains("\"field_name\":\"pattern\""),
914            "expected pattern field name; got {json}"
915        );
916        assert!(
917            json.contains("\"field_name\":\"value\""),
918            "expected value field name; got {json}"
919        );
920    }
921
922    #[cfg(feature = "rust")]
923    #[test]
924    fn serialized_json_uses_snake_case_keys() {
925        // The serialized AST shape uses snake_case keys (#535). This
926        // anchors the key scheme against accidental reversion to the
927        // former PascalCase `Type`/`TextValue`/`Span`/`Children`.
928        let root = build_ast_with_span::<crate::RustParser>(b"fn f(){}", "test.rs");
929        let json = serde_json::to_string(&root).expect("serialize");
930        for key in [
931            "\"type\":",
932            "\"value\":",
933            "\"span\":",
934            "\"field_name\":",
935            "\"children\":",
936        ] {
937            assert!(json.contains(key), "expected key {key}; got {json}");
938        }
939        for legacy in ["\"Type\"", "\"TextValue\"", "\"Span\"", "\"Children\""] {
940            assert!(
941                !json.contains(legacy),
942                "unexpected PascalCase key {legacy}; got {json}"
943            );
944        }
945    }
946
947    #[cfg(feature = "rust")]
948    #[test]
949    fn span_serializes_as_named_object() {
950        // The span is a flat named object preserving the 1-based
951        // tree-sitter line/column values in the original tuple order
952        // (start_line, start_col, end_line, end_col). The `*_line`
953        // vocabulary matches /function and /metrics (#638).
954        // `fn f(){}` is 8 bytes on one line, so the root spans the whole
955        // half-open byte range [0, 8) (#727).
956        for_each_strategy::<crate::RustParser>(b"fn f(){}", "test.rs", true, |name, root| {
957            let span = root
958                .span
959                .expect("root span present when span tracking is on");
960            assert_eq!(span, Span::new(1, 1, 1, 9, 0, 8), "{name}");
961            let json = serde_json::to_string(&root.span).expect("serialize span");
962            assert!(
963                json.contains("\"start_line\":1")
964                    && json.contains("\"start_col\":1")
965                    && json.contains("\"end_line\":1")
966                    && json.contains("\"end_col\":9")
967                    && json.contains("\"start_byte\":0")
968                    && json.contains("\"end_byte\":8"),
969                "expected named span object with byte offsets; got {json}"
970            );
971            // The pre-2.0 `*_row` keys must be gone (#638).
972            assert!(
973                !json.contains("start_row") && !json.contains("end_row"),
974                "unexpected pre-2.0 *_row span keys; got {json}"
975            );
976        });
977    }
978
979    #[test]
980    fn span_round_trips_through_serde() {
981        // Span derives Deserialize for wire round-trip parity.
982        let span = Span::new(2, 3, 4, 5, 11, 42);
983        let json = serde_json::to_string(&span).expect("serialize");
984        let back: Span = serde_json::from_str(&json).expect("deserialize");
985        assert_eq!(span, back);
986    }
987
988    #[test]
989    fn span_deserializes_pre_byte_offsets_with_default() {
990        // The byte fields carry `#[serde(default)]`, so a span object
991        // serialized before they existed (line/col only) still
992        // deserializes, with the offsets defaulting to 0 (#727).
993        let legacy = r#"{"start_line":2,"start_col":3,"end_line":4,"end_col":5}"#;
994        let span: Span = serde_json::from_str(legacy).expect("deserialize legacy span");
995        assert_eq!(span, Span::new(2, 3, 4, 5, 0, 0));
996    }
997
998    // -----------------------------------------------------------------
999    // Stack-depth regression tests (#1056)
1000    // -----------------------------------------------------------------
1001
1002    /// A chain of `depth` nested [`AstNode`]s below the root, built
1003    /// directly so the depth is exact rather than a function of how many
1004    /// AST levels a grammar spends per source construct.
1005    fn ast_chain(depth: usize) -> AstNode {
1006        let mut node = AstNode::new("leaf", String::new(), None, Vec::new());
1007        for _ in 0..depth {
1008            node = AstNode::new("branch", String::new(), None, vec![node]);
1009        }
1010        node
1011    }
1012
1013    #[test]
1014    fn ast_depth_at_the_serialize_limit_is_accepted_and_one_deeper_is_not() {
1015        let at_limit = ast_chain(MAX_AST_SERIALIZE_DEPTH);
1016        serde_json::to_string(&at_limit).expect("the limit itself must serialize");
1017
1018        let past_limit = ast_chain(MAX_AST_SERIALIZE_DEPTH + 1);
1019        let err = serde_json::to_string(&past_limit).expect_err("one deeper must be refused");
1020        assert!(
1021            err.to_string().contains(&format!(
1022                "AstNode nesting is deeper than the serialization limit of \
1023                 {MAX_AST_SERIALIZE_DEPTH} levels"
1024            )),
1025            "the error must name the type and the limit, got: {err}"
1026        );
1027    }
1028
1029    /// The deepest `children` chain in a tree, measured iteratively so a
1030    /// pathological input cannot overflow the measurement itself.
1031    #[cfg(feature = "tcl")]
1032    fn ast_depth(root: &AstNode) -> usize {
1033        let mut deepest = 0;
1034        let mut stack = vec![(root, 1usize)];
1035        while let Some((node, depth)) = stack.pop() {
1036            deepest = deepest.max(depth);
1037            stack.extend(node.children.iter().map(|child| (child, depth + 1)));
1038        }
1039        deepest
1040    }
1041
1042    /// What one level of Tcl brace nesting costs in `AstNode` levels, and
1043    /// therefore how far [`MAX_AST_SERIALIZE_DEPTH`] actually reaches for
1044    /// this language.
1045    ///
1046    /// The bound's doc quotes a corpus figure of 188 levels, which is a
1047    /// count of `AstNode` levels and not a conversion rate from source
1048    /// nesting. Since #1381 a Tcl script body keeps its children, so the
1049    /// two quantities came apart here more than anywhere else: this test
1050    /// is what keeps the number in that doc honest, and what would notice
1051    /// if an alterator change moved it again.
1052    #[cfg(feature = "tcl")]
1053    #[test]
1054    fn a_tcl_brace_level_costs_three_ast_levels() {
1055        // `eval` evaluates every argument, so each level keeps its
1056        // children rather than flattening to a verbatim leaf.
1057        let levels = 64;
1058        let code = format!("{}puts hi{}", "eval {".repeat(levels), "}".repeat(levels));
1059
1060        let root = build_ast::<crate::TclParser>(code.as_bytes(), "deep.tcl");
1061        let depth = ast_depth(&root);
1062        let per_level = depth / levels;
1063
1064        // Measured 196 over 64 at the pinned grammar: `braced_word` ->
1065        // `command` -> `word_list` before the next `braced_word`. The
1066        // range admits one level of drift either way so a grammar bump
1067        // reports the change rather than simply going red.
1068        assert!(
1069            (3..=4).contains(&per_level),
1070            "a braced script level should cost 3 AstNode levels \
1071             (braced_word -> command -> word_list); measured {depth} \
1072             levels over {levels} braces = {per_level}"
1073        );
1074        // The consequence worth stating in one place: the 512-level bound
1075        // is a low-hundreds brace ceiling for Tcl, not a 512 one.
1076        let ceiling = MAX_AST_SERIALIZE_DEPTH / per_level;
1077        assert!(
1078            (120..=180).contains(&ceiling),
1079            "the effective Tcl brace ceiling should sit near 170, got \
1080             {ceiling} from {per_level} levels per brace"
1081        );
1082    }
1083
1084    // -----------------------------------------------------------------
1085    // Two export strategies (#1684)
1086    // -----------------------------------------------------------------
1087
1088    /// Which builder each entry point runs.
1089    ///
1090    /// Nothing in the output can say: both builders produce the same
1091    /// tree, so routing `dump_inner` back to `build_indexed` would pass
1092    /// every assertion on a dump and show up only as a quadratic `/ast`
1093    /// response on a recovery tree. Each delta is asserted against a
1094    /// seeded count rather than zero, so a `record()` that was never
1095    /// wired up cannot pass either.
1096    #[cfg(feature = "rust")]
1097    #[test]
1098    fn each_entry_point_enters_exactly_its_own_builder() {
1099        let parser = crate::RustParser::new(b"fn f() {}".to_vec(), &PathBuf::from("a.rs"), None);
1100        let _ = dump_cursor_inner(&parser, cfg_with(false, false));
1101        let _ = dump_indexed_inner(&parser, cfg_with(false, false));
1102        let (cursor_seed, indexed_seed) = (cursor_builds::observed(), indexed_builds::observed());
1103        assert!(
1104            cursor_seed > 0 && indexed_seed > 0,
1105            "the seed calls must be counted"
1106        );
1107
1108        let entries: [(&str, Dump<crate::RustParser>, usize, usize); 3] = [
1109            ("dump_inner", dump_inner, 1, 0),
1110            ("dump_cursor_inner", dump_cursor_inner, 1, 0),
1111            ("dump_indexed_inner", dump_indexed_inner, 0, 1),
1112        ];
1113        let (mut cursor_total, mut indexed_total) = (cursor_seed, indexed_seed);
1114        for (name, dump, cursor_delta, indexed_delta) in entries {
1115            let _ = dump(&parser, cfg_with(false, false));
1116            cursor_total += cursor_delta;
1117            indexed_total += indexed_delta;
1118            assert_eq!(
1119                (cursor_builds::observed(), indexed_builds::observed()),
1120                (cursor_total, indexed_total),
1121                "{name} must enter the cursor builder {cursor_delta} time(s) and the indexed \
1122                 builder {indexed_delta} time(s)"
1123            );
1124        }
1125    }
1126
1127    /// A cursor climbs no higher than the node it was built on, and
1128    /// answers no field for that node: whole-tree parity cannot show
1129    /// either, since the walk there starts at the root, which has no
1130    /// parent to climb to or field to hide.
1131    #[cfg(feature = "rust")]
1132    #[test]
1133    fn a_cursor_reports_fields_below_its_start_and_cannot_climb_above_it() {
1134        let parser = crate::RustParser::new(
1135            b"fn f(a: u8) { let b = a; }".to_vec(),
1136            &PathBuf::from("a.rs"),
1137            None,
1138        );
1139        let func = parser
1140            .root()
1141            .children()
1142            .find(|n| n.kind() == "function_item")
1143            .expect("fixture has a function");
1144        let mut cursor = func.cursor();
1145
1146        assert_eq!(cursor.node().id(), func.id());
1147        // `function_item` sits in no field of `source_file`, so this is
1148        // `None` for two reasons; the subtree case below is the one
1149        // that tells them apart.
1150        assert_eq!(cursor.field_name(), None);
1151        assert!(!cursor.goto_parent(), "the start node is the ceiling");
1152        assert_eq!(
1153            cursor.node().id(),
1154            func.id(),
1155            "a refused climb must not move"
1156        );
1157
1158        assert!(cursor.goto_first_child());
1159        let mut fields = Vec::new();
1160        loop {
1161            fields.push((cursor.node().kind(), cursor.field_name()));
1162            if !cursor.goto_next_sibling() {
1163                break;
1164            }
1165        }
1166        assert_eq!(
1167            fields,
1168            [
1169                ("fn", None),
1170                ("identifier", Some("name")),
1171                ("parameters", Some("parameters")),
1172                ("block", Some("body")),
1173            ],
1174            "fields read off the cursor must match the grammar's"
1175        );
1176
1177        assert!(cursor.goto_parent());
1178        assert_eq!(cursor.node().id(), func.id());
1179        assert!(
1180            !cursor.goto_parent(),
1181            "back at the start node, the ceiling holds"
1182        );
1183
1184        // A node reached by descending from a cursor started above it
1185        // *does* know its field, and the same node hides it again once
1186        // a reset makes it the start: the `None` is the ceiling, not
1187        // the grammar.
1188        let let_decl = func
1189            .preorder()
1190            .find(|n| n.kind() == "let_declaration")
1191            .expect("fixture has a let");
1192        let mut from_parent = let_decl.cursor();
1193        assert!(from_parent.goto_first_child() && from_parent.goto_next_sibling());
1194        assert_eq!(from_parent.node().kind(), "identifier");
1195        assert_eq!(from_parent.field_name(), Some("pattern"));
1196        cursor.reset(&from_parent.node());
1197        assert_eq!(
1198            cursor.node().id(),
1199            from_parent.node().id(),
1200            "the reset must move the cursor before its answer means anything"
1201        );
1202        assert_eq!(
1203            cursor.field_name(),
1204            None,
1205            "after a reset the new start node hides its field exactly as the original did"
1206        );
1207    }
1208
1209    /// A field a visible rule inherits from a hidden one is reported,
1210    /// with the same name, by both strategies. The cursor reads it off
1211    /// the token's hidden parent on the way up and the index lookup
1212    /// carries it down through the same level, and the parity sweep's
1213    /// fixtures name no such field, so a grammar that broke the
1214    /// agreement would be caught only by accident there. Python's
1215    /// `comparison_operator` reaches each operator token through
1216    /// `operators`, an entry its `parser.c` marks `.inherited`; the
1217    /// token sits one hidden `_repeat1` level down, so this pins the
1218    /// propagation, not a multi-level climb.
1219    #[cfg(feature = "python")]
1220    #[test]
1221    fn each_strategy_reports_a_field_inherited_through_a_hidden_rule() {
1222        let code = b"a < b <= c\n";
1223        for (name, dump) in strategies::<crate::PythonParser>() {
1224            let root = build_ast_by(dump, code, "c.py", false, false);
1225            let comparison = kinds_and_fields(&root.children[0].children[0]);
1226            // expected: the two operator tokens carry `operators`; the
1227            // three operands sit in no field.
1228            assert_eq!(
1229                comparison,
1230                [
1231                    ("identifier", None),
1232                    ("<", Some("operators")),
1233                    ("identifier", None),
1234                    ("<=", Some("operators")),
1235                    ("identifier", None),
1236                ],
1237                "{name}"
1238            );
1239        }
1240    }
1241
1242    /// The comment filter, asserted on each strategy against an
1243    /// independently derived expectation. The parity sweep's fixtures
1244    /// hold almost no comments, and the filter lives in the step both
1245    /// builders share, so a defect there would hold parity while
1246    /// dropping or keeping the wrong nodes on both.
1247    #[cfg(feature = "rust")]
1248    #[test]
1249    fn each_strategy_filters_comments_only_when_asked() {
1250        let code = b"// lead\nfn f() {\n    // inner\n    let a = 1; /* trail */\n}\n";
1251        for (name, dump) in strategies::<crate::RustParser>() {
1252            for (comment, expected) in [(false, 3), (true, 0)] {
1253                let root = build_ast_by(dump, code, "c.rs", true, comment);
1254                let comments = count_kinds(&root, &["line_comment", "block_comment"]);
1255                // expected: the fixture spells two `//` and one `/* */`
1256                // comment; with the filter on, none survives, and the
1257                // retained content is untouched either way.
1258                assert_eq!(comments, expected, "{name}, comment={comment}");
1259                assert_eq!(
1260                    count_kinds(&root, &["let_declaration"]),
1261                    1,
1262                    "{name}, comment={comment}: the `let` must survive the filter"
1263                );
1264            }
1265        }
1266    }
1267
1268    /// Both envelope fields pass through each explicit entry point
1269    /// unchanged, with values that are not the empty-string default so
1270    /// a dropped or swapped field cannot read as correct.
1271    #[cfg(feature = "rust")]
1272    #[test]
1273    fn each_strategy_echoes_the_request_metadata() {
1274        let parser = crate::RustParser::new(b"fn f() {}".to_vec(), &PathBuf::from("a.rs"), None);
1275        let default: (&str, Dump<crate::RustParser>) = ("default", dump_inner);
1276        // The explicit strategies first, so a defect in one of them is
1277        // reported under its own name rather than as `default`.
1278        for (name, dump) in strategies().into_iter().chain([default]) {
1279            let resp = dump(
1280                &parser,
1281                AstCfg {
1282                    id: "req-42".to_owned(),
1283                    language: "rust".to_owned(),
1284                    comment: false,
1285                    span: false,
1286                },
1287            );
1288            assert_eq!(
1289                (resp.id.as_str(), resp.language.as_str()),
1290                ("req-42", "rust"),
1291                "{name}"
1292            );
1293            assert_eq!(resp.root.map(|r| r.r#type), Some("source_file"), "{name}");
1294        }
1295    }
1296
1297    /// The ancestor chain each builder hands `keeps_children` names the
1298    /// node's real parent, on every push as well as every pop.
1299    ///
1300    /// The walk constructors' default-build `debug_assert!` sees a
1301    /// dropped *pop* — the stale entry no longer contains the node —
1302    /// but not a dropped *push*: `finish` pops before it asks, so a walk
1303    /// that never pushes empties the chain on its first node, and the
1304    /// containment check passes vacuously on an empty chain. Only
1305    /// `make chain-audit` asks
1306    /// the exact question, so this pins the push half through its one
1307    /// consumer. A braced word directly under a `command` is that
1308    /// command's *name*, a literal the alterator flattens to a leaf;
1309    /// the same word under the root or under a `word_list` would be a
1310    /// script and keep its children. `{puts} hi` is therefore a leaf
1311    /// only when the parent handed down really is the `command`, and
1312    /// `eval {puts a}` beside it is the script case, so a chain that
1313    /// answers the root for everything moves exactly one of the two.
1314    #[cfg(feature = "tcl")]
1315    #[test]
1316    fn each_strategy_hands_the_alterator_the_real_parent() {
1317        let code = b"{puts} hi\neval {puts a}\n";
1318        for_each_strategy::<crate::TclParser>(code, "name.tcl", false, |name, root| {
1319            let braced: Vec<(&str, Vec<&str>)> = root
1320                .children
1321                .iter()
1322                .flat_map(|command| command.children.iter())
1323                .flat_map(|word| {
1324                    // The command name sits directly under `command`;
1325                    // the script argument is one `word_list` down.
1326                    std::iter::once(word).chain(word.children.iter())
1327                })
1328                .filter(|node| node.r#type == "braced_word")
1329                .map(|node| {
1330                    let kinds: Vec<&str> = node.children.iter().map(|c| c.r#type).collect();
1331                    (node.value.as_str(), kinds)
1332                })
1333                .collect();
1334            // expected: the name `{puts}` is a literal leaf carrying its
1335            // text; the `eval` body is an internal node — no text —
1336            // keeping `{`, the inner `command`, and `}`.
1337            assert_eq!(
1338                braced,
1339                [("{puts}", vec![]), ("", vec!["{", "command", "}"])],
1340                "{name}"
1341            );
1342        });
1343    }
1344
1345    /// Each builder lends `keeps_children` the export's `FoldCache`, so a
1346    /// wide erroring `eval` line is scanned once per export rather than
1347    /// once per braced word (#1686). The export is the same either way —
1348    /// every word keeps its children, as the count pins — so only the
1349    /// scan count can see the cache; rebuilding the chain in
1350    /// `Export::finish` with `Ancestors::for_walk_chain_only`, the
1351    /// cache unlent, takes it to `width` for both strategies.
1352    #[cfg(feature = "tcl")]
1353    #[test]
1354    fn each_strategy_scans_an_erroring_argument_list_once() {
1355        use crate::lang_helpers::argument_slot_scans;
1356
1357        let width = 200;
1358        let code = crate::test_support::tcl_wide_erroring_eval(width);
1359        for (name, dump) in strategies::<crate::TclParser>() {
1360            let before = argument_slot_scans::observed();
1361            let root = build_ast_by(dump, code.as_bytes(), "wide.tcl", false, false);
1362            assert_eq!(
1363                argument_slot_scans::observed() - before,
1364                1,
1365                "{name}: the export lends one cache for the whole walk"
1366            );
1367            let kept = root
1368                .children
1369                .iter()
1370                .flat_map(|command| command.children.iter())
1371                .flat_map(|list| list.children.iter())
1372                .filter(|word| word.r#type == "braced_word" && !word.children.is_empty())
1373                .count();
1374            assert_eq!(
1375                kept, width,
1376                "{name}: every `eval` argument keeps its children"
1377            );
1378        }
1379    }
1380
1381    /// A file whose only child is a filtered comment: the cursor walk
1382    /// finishes that child with nothing to attach, climbs, and must
1383    /// still finish the root rather than look for another sibling.
1384    #[cfg(feature = "rust")]
1385    #[test]
1386    fn a_comment_only_source_exports_a_childless_root_under_either_strategy() {
1387        let code = b"// only\n";
1388        for (name, dump) in strategies::<crate::RustParser>() {
1389            let keep = build_ast_by(dump, code, "a.rs", false, false);
1390            assert_eq!(
1391                keep.children.len(),
1392                1,
1393                "{name}: without the filter the root keeps its one comment child"
1394            );
1395            let root = build_ast_by(dump, code, "a.rs", false, true);
1396            assert_eq!(
1397                kinds_and_fields(&root),
1398                [],
1399                "{name}: the comment child must be filtered"
1400            );
1401        }
1402    }
1403
1404    #[test]
1405    fn a_pathologically_deep_ast_errors_and_tears_down_without_overflowing() {
1406        // The chain is built directly rather than parsed, but this depth
1407        // is reachable through `bca-web`'s `/ast`: 50 000 levels of
1408        // nested parentheses fit in 100 KB, an order of magnitude inside
1409        // the 4 MiB body cap. Both the recursive `Serialize` and the
1410        // compiler-generated `Drop` glue used to abort the process here —
1411        // `SIGABRT`, which `spawn_blocking` cannot contain (#1056).
1412        const DEPTH: usize = 50_000;
1413        // The stack a `bca` consumer thread and a `tokio` blocking thread
1414        // get; the serialization limit is dimensioned against it.
1415        const PRODUCTION_STACK: usize = 2 * 1024 * 1024;
1416        let message = std::thread::Builder::new()
1417            .stack_size(PRODUCTION_STACK)
1418            .spawn(|| {
1419                let root = ast_chain(DEPTH);
1420                let message = serde_json::to_string(&root)
1421                    .expect_err("depth past the limit must fail, not serialize")
1422                    .to_string();
1423                // `root` drops here: the iterative `Drop` must unwind
1424                // 50 000 levels without touching the stack.
1425                message
1426            })
1427            .expect("spawn bounded-stack thread")
1428            .join()
1429            .expect("bounded-stack thread must not overflow");
1430        assert!(
1431            message.contains("AstNode nesting is deeper than the serialization limit"),
1432            "the error must explain the refusal, got: {message}"
1433        );
1434    }
1435}