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}