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}