Skip to main content

relate_core/value/
depth.rs

1//! ADR-0462 value-nesting depth: the fixed cap, the one iterative depth
2//! walk and its two front ends, the typed guard, and the checked
3//! constructors. Extracted from `value/mod.rs` for the file-size rule (the
4//! `ordering.rs`/`json.rs` precedent); the methods stay inherent, so no
5//! caller changes.
6
7use std::collections::{BTreeMap, HashMap};
8use std::sync::Arc;
9
10use super::{Node, PropertyMap, Relationship, Value};
11
12/// The deepest container nesting a [`Value`] may have (ADR-0462,
13/// LABS-606).
14///
15/// Equal to the parser's static nesting limit (ADR-0257) so every
16/// parse-legal literal is accepted, and low enough that the derived
17/// recursive `Drop`, clone, and render walks over an at-cap value stay well
18/// inside every surface's stack. Every dynamic container construction in
19/// the evaluator goes through [`Value::checked_list`]/
20/// [`Value::checked_map`]; a `reduce` accumulator can therefore grow one
21/// level per iteration without ever exceeding this bound — the level-501
22/// construction fails with a typed `ValueDepthExceeded` error instead of
23/// building a value that later overflows a recursive walker.
24///
25/// Fixed constant, no knob: the same house rule as ADR-0257's 4 MiB/500 and
26/// ADR-0395's fixed 100 000-pass budget. Lifting it would require a
27/// payload-newtype `Drop` for `Value` (never `impl Drop for Value`, which
28/// makes the move-out matches E0509), so a recursive drop cannot overflow.
29pub const MAX_VALUE_DEPTH: u32 = 500;
30
31/// What the infallible renderers emit for a container nested past
32/// [`MAX_VALUE_DEPTH`] instead of recursing (ADR-0462). Unreachable behind
33/// the checked constructors: it is the depth safety valve for a caller that
34/// bypassed them, never a documented rendering.
35pub(crate) const DEPTH_LIMIT_MARKER: &str = "<depth limit exceeded>";
36
37/// The one `ValueDepthExceeded` detail payload (ADR-0462), beside
38/// [`MAX_VALUE_DEPTH`]. `what` names the value shape the walker rejected
39/// (`"value"`, `"tagged value"`, `"coll.flatten() input"`). Every raiser —
40/// [`Value::check_depth`], the tagged decoder and encoder, the collection
41/// helpers — spells the message through here so the detail and the limit
42/// cannot drift.
43pub fn value_depth_exceeded(what: &str) -> String {
44    format!(
45        "ValueDepthExceeded: {what} nesting exceeds {MAX_VALUE_DEPTH} levels; \
46         container nesting compounds per level (security limit)."
47    )
48}
49
50/// The next container level below `depth`, or `None` once that level would
51/// exceed [`MAX_VALUE_DEPTH`]. The canonical ADR-0462 guard for walkers that
52/// saturate or throw at the cap (renderers, JSON decoders/encoders, the
53/// model bridge, the logical-bytes walk); re-exported so the HTTP Query API
54/// encoder spells it the same way. `depth` is the number of containers
55/// enclosing the value, so a root is 0.
56pub fn next_depth(depth: u32) -> Option<u32> {
57    let next = child_level(depth);
58    (next <= MAX_VALUE_DEPTH).then_some(next)
59}
60
61/// The most worklist steps one depth walk may take before it conservatively
62/// refuses (ADR-0462, PR #547 round-5). The walk memoizes container payloads
63/// by identity, so a DAG of N distinct payloads costs O(N) steps; this is the
64/// belt-and-braces refusal for a sharing pattern the memo cannot collapse —
65/// the walk gives up as over-cap instead of hanging. Symmetric with the fixed
66/// pass budgets elsewhere (ADR-0395).
67const MAX_DEPTH_WALK_STEPS: u64 = 10_000_000;
68
69/// Identity of one container payload during a depth walk: its `Arc`
70/// allocation address. Distinct live allocations never share an address, and
71/// the walk's root keeps every visited payload alive for the walk's duration,
72/// so a key can never alias a freed allocation. The variant kind is
73/// redundant: the address already identifies the container, and the memo
74/// stores a depth derived from that payload's own contents.
75type PayloadKey = usize;
76
77/// One container's lazily enumerated children. Every variant is O(1) to
78/// build, so a memo hit drops it without touching the children — the walk
79/// stays O(distinct payloads), never O(expanded edges).
80enum Children<'a> {
81    Values(std::slice::Iter<'a, Value>),
82    MapValues(std::collections::btree_map::Values<'a, String, Value>),
83    PropValues(PropValues<'a>),
84    Path {
85        nodes: std::slice::Iter<'a, Node>,
86        rels: std::slice::Iter<'a, Relationship>,
87        current: Option<PropValues<'a>>,
88    },
89}
90
91/// `PropertyMap` entry values: the depth walk only needs the value half.
92type PropValues<'a> =
93    std::iter::Map<std::slice::Iter<'a, (String, Value)>, fn(&'a (String, Value)) -> &'a Value>;
94
95fn entry_value((_, value): &(String, Value)) -> &Value {
96    value
97}
98
99fn prop_values(props: &PropertyMap) -> PropValues<'_> {
100    props.entries().iter().map(entry_value)
101}
102
103impl<'a> Iterator for Children<'a> {
104    type Item = &'a Value;
105
106    fn next(&mut self) -> Option<Self::Item> {
107        match self {
108            Children::Values(items) => items.next(),
109            Children::MapValues(values) => values.next(),
110            Children::PropValues(values) => values.next(),
111            Children::Path {
112                nodes,
113                rels,
114                current,
115            } => loop {
116                if let Some(values) = current.as_mut() {
117                    if let Some(value) = values.next() {
118                        return Some(value);
119                    }
120                    *current = None;
121                }
122                if let Some(node) = nodes.next() {
123                    *current = Some(prop_values(&node.properties));
124                    continue;
125                }
126                if let Some(rel) = rels.next() {
127                    *current = Some(prop_values(&rel.properties));
128                    continue;
129                }
130                return None;
131            },
132        }
133    }
134}
135
136/// The one owner of the container vocabulary (ADR-0462): a container value's
137/// memo identity and its children together, from one enumeration — so the
138/// memo key, the child count and the child iteration cannot drift apart. The
139/// scalar variants are spelled out on purpose: a future `Value` variant is a
140/// non-exhaustive-match compile error at this one classification site.
141fn container(value: &Value) -> Option<(PayloadKey, Children<'_>)> {
142    match value {
143        Value::List(xs) | Value::Vector { values: xs, .. } => {
144            Some((Arc::as_ptr(xs) as usize, Children::Values(xs.iter())))
145        }
146        Value::Map(map) => Some((Arc::as_ptr(map) as usize, Children::MapValues(map.values()))),
147        Value::Node(node) => Some((
148            Arc::as_ptr(node) as usize,
149            Children::PropValues(prop_values(&node.properties)),
150        )),
151        Value::Relationship(rel) => Some((
152            Arc::as_ptr(rel) as usize,
153            Children::PropValues(prop_values(&rel.properties)),
154        )),
155        Value::Path(path) => Some((
156            Arc::as_ptr(path) as usize,
157            Children::Path {
158                nodes: path.nodes.iter(),
159                rels: path.rels.iter(),
160                current: None,
161            },
162        )),
163        Value::Null
164        | Value::Bool(_)
165        | Value::Int(_)
166        | Value::Float(_)
167        | Value::String(_)
168        | Value::Temporal(_)
169        | Value::Point(_)
170        | Value::Uuid(_)
171        | Value::Bytes(_) => None,
172    }
173}
174
175/// One frame of the iterative depth walk.
176enum Frame<'a> {
177    /// Visit a value: a scalar completes with depth 0, a container with its
178    /// memoized relative depth, or — on its first visit — schedules its
179    /// children and the matching [`Frame::Exit`].
180    Enter(&'a Value),
181    /// A container's children have each pushed exactly one result on top of
182    /// `results`; fold those results (from `base`) into the container's
183    /// relative depth and memoize it.
184    Exit { key: PayloadKey, base: usize },
185}
186
187/// The one owner of the level arithmetic (ADR-0462): the level one container
188/// deeper than `depth`, saturating at `u32::MAX` — a value that deep is
189/// over the cap in every caller. Every walker and guard routes through here
190/// so the three previous spellings cannot drift.
191fn child_level(depth: u32) -> u32 {
192    depth.saturating_add(1)
193}
194
195/// Whether a walker at `depth` (containers enclosing the value) may descend
196/// into the value's contents — the boolean spelling of [`next_depth`] for
197/// the comparison walkers, whose guards read naturally as a match-arm
198/// condition. [`next_depth`] owns the boundary; this only answers its
199/// `Some`/`None`.
200pub(crate) fn descends(depth: u32) -> bool {
201    next_depth(depth).is_some()
202}
203
204impl Value {
205    /// Whether every container in this value nests at most `limit` levels
206    /// deep (ADR-0462). Iterative over an explicit worklist — never
207    /// recursive — so an over-deep value is rejected without first growing
208    /// the stack to its depth.
209    ///
210    /// A scalar has depth 0; a container's own level is one more than its
211    /// parent's, so `[]` is depth 1 and `[[]]` depth 2. Node, relationship
212    /// and path values count as containers, and their property values nest
213    /// inside them.
214    pub fn depth_within(&self, limit: u32) -> bool {
215        // One iterative walker, two front ends (ADR-0462): the walk is on
216        // capped values, so the exact depth is cheap to compute and there is
217        // no separate early-exit spelling to drift.
218        self.depth() <= limit
219    }
220
221    /// The typed depth guard: `Ok` when this value nests at most
222    /// [`MAX_VALUE_DEPTH`] levels (ADR-0462), else a `ValueDepthExceeded`
223    /// execution error. The `Kind:` prefix is the token the error channel
224    /// classifies (`ErrorKind::ValueDepthExceeded`).
225    pub fn check_depth(&self) -> crate::Result<()> {
226        Self::check_known_depth(self.depth())
227    }
228
229    /// This value's exact container depth (scalar 0, `[]` 1, `[[]]` 2),
230    /// walked iteratively once. For a value whose depth is already known,
231    /// [`Value::checked_list_with_depth`] avoids this walk.
232    ///
233    /// The walk memoizes container payloads by identity: a shared subtree is
234    /// measured once, so the cost is linear in **distinct payloads**, never in
235    /// the expanded node count of a fan-out DAG (a `[acc, acc]` chain would
236    /// otherwise expand exponentially). A walk that exceeds
237    /// [`MAX_DEPTH_WALK_STEPS`] conservatively answers [`u32::MAX`] (over any
238    /// cap), so it can refuse but never hang.
239    pub fn depth(&self) -> u32 {
240        self.depth_capped().unwrap_or(u32::MAX)
241    }
242
243    /// [`Value::depth`] with the ADR-0462 step bound: `None` when the walk
244    /// exceeds [`MAX_DEPTH_WALK_STEPS`], which every caller treats as
245    /// over-cap.
246    fn depth_capped(&self) -> Option<u32> {
247        let mut memo: HashMap<PayloadKey, u32> = HashMap::new();
248        let mut results: Vec<u32> = Vec::new();
249        let mut stack: Vec<Frame<'_>> = vec![Frame::Enter(self)];
250        let mut steps: u64 = 0;
251        while let Some(frame) = stack.pop() {
252            steps += 1;
253            if steps > MAX_DEPTH_WALK_STEPS {
254                return None;
255            }
256            match frame {
257                Frame::Enter(value) => {
258                    let Some((key, children)) = container(value) else {
259                        results.push(0);
260                        continue;
261                    };
262                    if let Some(rel) = memo.get(&key) {
263                        // Memo hit: the lazily built `children` is dropped
264                        // unused, so a shared payload costs O(1).
265                        results.push(*rel);
266                        continue;
267                    }
268                    // Record where this container's children's results begin,
269                    // then push the children on top of the Exit frame.
270                    let base = results.len();
271                    stack.push(Frame::Exit { key, base });
272                    stack.extend(children.map(Frame::Enter));
273                }
274                Frame::Exit { key, base } => {
275                    // Every child of this container pushed exactly one result
276                    // after `base` was recorded; fold them into `1 + max`.
277                    let max = results[base..].iter().copied().max().unwrap_or(0);
278                    results.truncate(base);
279                    let rel = child_level(max);
280                    memo.insert(key, rel);
281                    results.push(rel);
282                }
283            }
284        }
285        results.pop()
286    }
287
288    /// The depth check for a caller that already knows the result's depth —
289    /// the O(1) path behind [`Value::checked_list_with_depth`]. `depth` is
290    /// the candidate value's own container level.
291    fn check_known_depth(depth: u32) -> crate::Result<()> {
292        if depth <= MAX_VALUE_DEPTH {
293            Ok(())
294        } else {
295            Err(crate::Error::execution(value_depth_exceeded("value")))
296        }
297    }
298
299    /// Build a list value, rejecting one that would nest deeper than
300    /// [`MAX_VALUE_DEPTH`] (ADR-0462). The one constructor for a list the
301    /// evaluator builds from dynamic expression results.
302    pub fn checked_list(values: Vec<Value>) -> crate::Result<Value> {
303        let value = Value::List(values.into());
304        value.check_depth()?;
305        Ok(value)
306    }
307
308    /// **Evaluator-internal O(1) seam** (ADR-0462): build a list when the
309    /// caller already knows `child_depth` — the exact maximum container depth
310    /// of `values` — instead of walking the subtree. The result's own level
311    /// is `child_depth + 1`.
312    ///
313    /// Invariant: only the evaluator's depth-tracking loops (the
314    /// `reduce`/`allReduce` wrap fast path) may call this, passing the depth
315    /// they track per iteration. Every other caller must use
316    /// [`Value::checked_list`]. Release builds trust the caller and stay
317    /// O(1); debug builds assert every element is within the claimed depth.
318    #[doc(hidden)]
319    pub fn checked_list_with_depth(values: Vec<Value>, child_depth: u32) -> crate::Result<Value> {
320        debug_assert!(
321            values.iter().all(|v| v.depth_within(child_depth)),
322            "checked_list_with_depth: an element is deeper than the claimed child_depth"
323        );
324        Self::check_known_depth(child_level(child_depth))?;
325        Ok(Value::List(values.into()))
326    }
327
328    /// Build a map value, rejecting one that would nest deeper than
329    /// [`MAX_VALUE_DEPTH`] (ADR-0462). The one constructor for a map the
330    /// evaluator builds from dynamic expression results.
331    pub fn checked_map(values: BTreeMap<String, Value>) -> crate::Result<Value> {
332        let value = Value::Map(values.into());
333        value.check_depth()?;
334        Ok(value)
335    }
336}