big_code_analysis_ast/
recursion.rs

1//! Stack-depth bounds for the crate's recursive types.
2//!
3//! `big-code-analysis`'s `FuncSpace` and `Ops`, and this crate's
4//! [`AstNode`](crate::AstNode), are trees whose nesting depth is
5//! caller-controlled: nested functions, nested closures, and nested
6//! expressions are ordinary legal constructs in every supported language.
7//! Issues #700 / #709 converted every AST *traversal* to an explicit work
8//! stack, but two implicit recursions survived on the types themselves —
9//! `Serialize` and the compiler-generated `Drop` glue. Overflowing the
10//! stack in either is not a catchable panic: the runtime aborts the
11//! process with `SIGABRT`, taking every in-flight `bca-web` request with
12//! it (#1056).
13//!
14//! `Drop` is made iterative outright by [`impl_iterative_drop`].
15//! `Serialize` cannot be: `serde` offers no way to emit a tree without one
16//! native frame per level, because `serialize_field` must run the child's
17//! `Serialize` to completion before it returns. So it is bounded instead —
18//! [`serialize_bounded`] refuses to descend past a per-type limit and
19//! returns an ordinary serializer error, mirroring the 128-level recursion
20//! limit `serde_json`'s `Deserializer` already applies to the same shapes.
21//!
22//! The third recursion #1056 covered is not here: projecting a compute
23//! tree onto its wire form. That one *is* de-recursed outright, by
24//! `wire::map_tree`, which lives next to the `From` impls it serves.
25
26use std::cell::Cell;
27
28use serde::{Serialize, Serializer, ser::Error as _};
29
30thread_local! {
31    /// Levels of bounded nesting currently being serialized on this thread.
32    ///
33    /// A thread-local rather than a parameter because `serde`'s
34    /// `serialize_with` hook receives only the field and the serializer.
35    /// It is shared by every bounded type; the crate's recursive types
36    /// never nest inside one another, and if they ever did, sharing the
37    /// counter is the conservative direction.
38    static DEPTH: Cell<usize> = const { Cell::new(0) };
39}
40
41/// Restores [`DEPTH`] when a bounded level finishes, including when the
42/// serializer returns an error or a `Serialize` impl further down panics.
43struct DepthGuard;
44
45impl Drop for DepthGuard {
46    fn drop(&mut self) {
47        DEPTH.with(|depth| depth.set(depth.get().saturating_sub(1)));
48    }
49}
50
51/// Serializes a recursive type's child collection one level deeper.
52///
53/// `limit` is the greatest number of nested child levels below the root
54/// that will be emitted; `type_name` names the offending type in the
55/// error. A deeper tree fails with a serializer error — reported by the
56/// caller like any other output failure — rather than recursing far enough
57/// to overflow the thread stack.
58#[doc(hidden)]
59pub fn serialize_bounded<S, T>(
60    children: &[T],
61    limit: usize,
62    type_name: &str,
63    serializer: S,
64) -> Result<S::Ok, S::Error>
65where
66    S: Serializer,
67    T: Serialize,
68{
69    // A leaf's empty child list recurses no further, so it costs no depth.
70    // Skipping it keeps `limit` an exact count of *nested* levels and
71    // spares the counter on the majority of nodes in any real tree.
72    if children.is_empty() {
73        return children.serialize(serializer);
74    }
75    let depth = DEPTH.with(|d| {
76        let entered = d.get() + 1;
77        d.set(entered);
78        entered
79    });
80    let _guard = DepthGuard;
81    if depth > limit {
82        return Err(S::Error::custom(format!(
83            "{type_name} nesting is deeper than the serialization limit of {limit} levels"
84        )));
85    }
86    children.serialize(serializer)
87}
88
89/// Implements `Drop` for a tree type so teardown costs no stack depth.
90///
91/// `$children` names the field holding the node's children. Every
92/// descendant is hoisted into one flat work list, so a node is dropped
93/// only after its own children have been moved out of it and its
94/// compiler-generated glue finds an empty list — the recursion is one
95/// level deep regardless of the tree's shape.
96#[macro_export]
97#[doc(hidden)]
98macro_rules! impl_iterative_drop {
99    ($ty:ty, $children:ident) => {
100        impl Drop for $ty {
101            fn drop(&mut self) {
102                let mut pending = ::std::mem::take(&mut self.$children);
103                while let Some(mut node) = pending.pop() {
104                    pending.append(&mut node.$children);
105                }
106            }
107        }
108    };
109}
110
111pub use impl_iterative_drop;
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    /// The guard must restore the counter on the error path, or one
118    /// rejected tree would poison every later serialization on the thread.
119    #[test]
120    fn depth_counter_is_restored_after_a_rejection() {
121        let deep = vec![vec![vec![0_u8]]];
122        // Limit 0 rejects immediately at the first bounded level.
123        let mut out = Vec::new();
124        let mut ser = serde_json::Serializer::new(&mut out);
125        let err = serialize_bounded(&deep, 0, "Probe", &mut ser).expect_err("limit 0 must reject");
126        assert!(
127            err.to_string().contains("serialization limit of 0 levels"),
128            "error must name the limit, got: {err}"
129        );
130        assert_eq!(DEPTH.with(Cell::get), 0, "counter must unwind to zero");
131
132        // The same thread must still serialize a shallow value afterwards.
133        let mut out = Vec::new();
134        let mut ser = serde_json::Serializer::new(&mut out);
135        serialize_bounded(&deep, 1, "Probe", &mut ser).expect("limit 1 accepts one level");
136        assert_eq!(DEPTH.with(Cell::get), 0, "counter must unwind to zero");
137        assert_eq!(String::from_utf8(out).expect("utf-8"), "[[[0]]]");
138    }
139}
big_code_analysis_ast/recursion.rs

big_code_analysis_ast/
recursion.rs
