qubit_json/value/traverse/json_tree_mutator.rs
1// =============================================================================
2// Copyright (c) 2026 Haixing Hu.
3//
4// SPDX-License-Identifier: Apache-2.0
5//
6// Licensed under the Apache License, Version 2.0.
7// =============================================================================
8//! Implements non-recursive, budget-aware mutable JSON tree processing.
9//!
10//! # Mutable traversal safety
11//!
12//! The caller's exclusive root borrow outlives the complete frame stack. The
13//! visitor borrow for a node ends before a cursor over that node is created.
14//! Traversal then suspends every ancestor cursor while processing one child,
15//! pops that child before advancing the parent, and never dereferences an
16//! ancestor while a descendant is active. Visitors may replace the current
17//! `Value`, but after descent begins they cannot change an ancestor array
18//! length, object key set, or backing allocation. These rules are the safety
19//! contract for the internal `NonNull` pointers and lifetime-erased object
20//! iterator.
21
22use qubit_budget::ResourceQuantity;
23use qubit_budget::json::JsonValueTransaction;
24use serde_json::Value;
25
26use super::JsonTreeControl;
27use super::JsonTreeMutVisitor;
28use super::JsonTreeMutateError;
29use super::JsonTreeReader;
30use super::internal::MutFrame;
31
32/// Mutates a JSON tree between independent input and output transactions.
33///
34/// The complete original tree is admitted before the first visitor callback.
35/// After all callbacks succeed, the complete mutated tree is admitted against
36/// the output transaction. Visitor failures and panics can retain partial
37/// mutations, while output accounting does not begin until visitor success.
38///
39/// # Type Parameters
40///
41/// * `R` - Resource identity shared by the two transactions.
42/// * `Q` - Quantity representation shared by the two transactions.
43///
44/// # Examples
45///
46/// ```
47/// use qubit_budget::json::{JsonResource, JsonValueBudget, JsonValueLimits};
48/// use qubit_json::value::traverse::{
49/// JsonTreeContext, JsonTreeControl, JsonTreeMutVisitor, JsonTreeMutator,
50/// };
51/// use serde_json::Value;
52///
53/// struct Visitor;
54/// impl JsonTreeMutVisitor for Visitor {
55/// type Error = std::convert::Infallible;
56///
57/// fn visit(
58/// &mut self,
59/// _: &mut Value,
60/// _: JsonTreeContext<'_>,
61/// ) -> Result<JsonTreeControl, Self::Error> {
62/// Ok(JsonTreeControl::SkipSubtree)
63/// }
64/// }
65///
66/// let limits = JsonValueLimits::<JsonResource, usize>::default();
67/// let mut input_budget = JsonValueBudget::new(limits);
68/// let mut output_budget = JsonValueBudget::new(limits);
69/// let mut input = input_budget.transaction();
70/// let mut output = output_budget.transaction();
71/// let mut mutator = JsonTreeMutator::new(&mut input, &mut output);
72/// let mut value = Value::Null;
73/// assert!(mutator.process(&mut value, &mut Visitor).is_ok());
74/// ```
75pub struct JsonTreeMutator<
76 'input_transaction,
77 'input_budget,
78 'output_transaction,
79 'output_budget,
80 R,
81 Q,
82> where
83 Q: ResourceQuantity,
84{
85 /// Transaction receiving the complete original-tree charges.
86 input: &'input_transaction mut JsonValueTransaction<'input_budget, R, Q>,
87 /// Transaction receiving the complete mutated-tree charges.
88 output: &'output_transaction mut JsonValueTransaction<'output_budget, R, Q>,
89}
90
91impl<'input_transaction, 'input_budget, 'output_transaction, 'output_budget, R, Q>
92 JsonTreeMutator<'input_transaction, 'input_budget, 'output_transaction, 'output_budget, R, Q>
93where
94 R: Clone,
95 Q: ResourceQuantity,
96{
97 /// Creates a mutator borrowing independent input and output transactions.
98 ///
99 /// # Parameters
100 ///
101 /// * `input` - Transaction receiving charges for the complete original
102 /// tree.
103 /// * `output` - Transaction receiving charges for the complete mutated
104 /// tree.
105 ///
106 /// # Returns
107 ///
108 /// A mutator borrowing both transactions for its lifetime.
109 #[inline(always)]
110 #[must_use]
111 pub fn new(
112 input: &'input_transaction mut JsonValueTransaction<'input_budget, R, Q>,
113 output: &'output_transaction mut JsonValueTransaction<'output_budget, R, Q>,
114 ) -> Self {
115 Self { input, output }
116 }
117
118 /// Admits the original tree, mutates it, and admits the final tree.
119 ///
120 /// Both admissions and all visitor callbacks use explicit stacks rather
121 /// than Rust recursion. `SkipSubtree` affects callbacks only; final output
122 /// admission always covers every resulting descendant.
123 ///
124 /// Callbacks may visit descendants added by earlier callbacks. Output
125 /// `max_nodes` and `max_depth` are checked only against the complete final
126 /// tree; they do not limit callback count or intermediate expansion. A
127 /// visitor that adds descendants must bound its own expansion and ensure
128 /// traversal terminates. Returning [`JsonTreeControl::SkipSubtree`] skips
129 /// descent from the current node, but the final tree is still subject to
130 /// output admission. See the
131 /// [mutable tree traversal guidance](https://github.com/qubit-ltd/rs-json/blob/main/doc/user_guide.md#read-and-mutate-existing-trees).
132 ///
133 /// # Type Parameters
134 ///
135 /// * `V` - Visitor controlling mutations and descendant callbacks.
136 ///
137 /// # Parameters
138 ///
139 /// * `root` - Root JSON value to process and mutate.
140 /// * `visitor` - Visitor applied after complete input admission.
141 ///
142 /// # Returns
143 ///
144 /// `Ok(())` after both complete trees fit and every callback succeeds.
145 ///
146 /// # Errors
147 ///
148 /// Returns [`JsonTreeMutateError::InputBudget`] before mutation when the
149 /// original tree is rejected, [`JsonTreeMutateError::Visitor`] after a
150 /// callback failure, or [`JsonTreeMutateError::OutputBudget`] after a
151 /// complete mutation whose result is rejected. Visitor and output failures
152 /// retain mutations already made to `root`.
153 pub fn process<V>(
154 &mut self,
155 root: &mut Value,
156 visitor: &mut V,
157 ) -> Result<(), JsonTreeMutateError<R, Q, V::Error>>
158 where
159 V: JsonTreeMutVisitor,
160 {
161 JsonTreeReader::new(&mut *self.input)
162 .account(root)
163 .map_err(JsonTreeMutateError::InputBudget)?;
164 Self::mutate(root, visitor).map_err(JsonTreeMutateError::Visitor)?;
165 JsonTreeReader::new(&mut *self.output)
166 .account(root)
167 .map_err(JsonTreeMutateError::OutputBudget)
168 }
169
170 /// Runs mutable visitor callbacks without budget side effects.
171 ///
172 /// An explicit frame stack visits each node before its children. The
173 /// visitor may replace the current value or skip its descendants; its first
174 /// error stops traversal and is returned to the caller. Parent cursors
175 /// remain suspended while a child frame is active, preserving the
176 /// pointer-safety invariant documented for this module.
177 ///
178 /// # Type Parameters
179 ///
180 /// * `V` - Visitor receiving each mutable value and its location context.
181 ///
182 /// # Parameters
183 ///
184 /// * `root` - Root value whose nodes are visited and may be replaced.
185 /// * `visitor` - Callback applied before descending into each node's
186 /// children.
187 ///
188 /// # Returns
189 ///
190 /// `Ok(())` after all selected callbacks complete, or the first visitor
191 /// error before traversal finishes.
192 ///
193 /// # Errors
194 ///
195 /// Returns the visitor's error unchanged when a callback fails; mutations
196 /// already made to `root` remain in place.
197 ///
198 /// # Panics
199 ///
200 /// Panics only if the traversal stack invariant is violated and its active
201 /// frame is unexpectedly absent.
202 fn mutate<V>(root: &mut Value, visitor: &mut V) -> Result<(), V::Error>
203 where
204 V: JsonTreeMutVisitor,
205 {
206 // SAFETY: the stack is local to this call and is dropped before the
207 // exclusive borrow of `root` ends, including on error or panic exits.
208 let mut stack = vec![unsafe { MutFrame::root(root) }];
209 while !stack.is_empty() {
210 let index = stack.len() - 1;
211 if !stack[index].entered {
212 let frame = &mut stack[index];
213 // SAFETY: this is the top unentered frame, it has no cursor,
214 // and all ancestors remain suspended for the callback.
215 let control = unsafe { frame.visit(visitor) }?;
216 frame.entered = true;
217 if control != JsonTreeControl::Descend {
218 frame.finished = true;
219 }
220 continue;
221 }
222 // SAFETY: only the active top frame is advanced, after its visitor
223 // returned and its previously yielded child frame has been popped.
224 if let Some(child) = unsafe { stack[index].next_child() } {
225 stack.push(child);
226 continue;
227 }
228 let _ = stack.pop().expect("mutable frame exists");
229 }
230 Ok(())
231 }
232}