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<'input_transaction, 'input_budget, 'output_transaction, 'output_budget, R, Q>
76where
77 Q: ResourceQuantity,
78{
79 /// Transaction receiving the complete original-tree charges.
80 input: &'input_transaction mut JsonValueTransaction<'input_budget, R, Q>,
81 /// Transaction receiving the complete mutated-tree charges.
82 output: &'output_transaction mut JsonValueTransaction<'output_budget, R, Q>,
83}
84
85impl<'input_transaction, 'input_budget, 'output_transaction, 'output_budget, R, Q>
86 JsonTreeMutator<'input_transaction, 'input_budget, 'output_transaction, 'output_budget, R, Q>
87where
88 R: Clone,
89 Q: ResourceQuantity,
90{
91 /// Creates a mutator borrowing independent input and output transactions.
92 ///
93 /// # Parameters
94 ///
95 /// * `input` - Transaction receiving charges for the complete original
96 /// tree.
97 /// * `output` - Transaction receiving charges for the complete mutated
98 /// tree.
99 ///
100 /// # Returns
101 ///
102 /// A mutator borrowing both transactions for its lifetime.
103 #[inline(always)]
104 #[must_use]
105 pub fn new(
106 input: &'input_transaction mut JsonValueTransaction<'input_budget, R, Q>,
107 output: &'output_transaction mut JsonValueTransaction<'output_budget, R, Q>,
108 ) -> Self {
109 Self { input, output }
110 }
111
112 /// Admits the original tree, mutates it, and admits the final tree.
113 ///
114 /// Both admissions and all visitor callbacks use explicit stacks rather
115 /// than Rust recursion. `SkipSubtree` affects callbacks only; final output
116 /// admission always covers every resulting descendant.
117 ///
118 /// Callbacks may visit descendants added by earlier callbacks. Output
119 /// `max_nodes` and `max_depth` are checked only against the complete final
120 /// tree; they do not limit callback count or intermediate expansion. A
121 /// visitor that adds descendants must bound its own expansion and ensure
122 /// traversal terminates. Returning [`JsonTreeControl::SkipSubtree`] skips
123 /// descent from the current node, but the final tree is still subject to
124 /// output admission. See the
125 /// [mutable tree traversal guidance](https://github.com/qubit-ltd/rs-json/blob/main/doc/user_guide.md#read-and-mutate-existing-trees).
126 ///
127 /// # Type Parameters
128 ///
129 /// * `V` - Visitor controlling mutations and descendant callbacks.
130 ///
131 /// # Parameters
132 ///
133 /// * `root` - Root JSON value to process and mutate.
134 /// * `visitor` - Visitor applied after complete input admission.
135 ///
136 /// # Returns
137 ///
138 /// `Ok(())` after both complete trees fit and every callback succeeds.
139 ///
140 /// # Errors
141 ///
142 /// Returns [`JsonTreeMutateError::InputBudget`] before mutation when the
143 /// original tree is rejected, [`JsonTreeMutateError::Visitor`] after a
144 /// callback failure, or [`JsonTreeMutateError::OutputBudget`] after a
145 /// complete mutation whose result is rejected. Visitor and output failures
146 /// retain mutations already made to `root`.
147 pub fn process<V>(&mut self, root: &mut Value, visitor: &mut V) -> Result<(), JsonTreeMutateError<R, Q, V::Error>>
148 where
149 V: JsonTreeMutVisitor,
150 {
151 JsonTreeReader::new(&mut *self.input)
152 .account(root)
153 .map_err(JsonTreeMutateError::InputBudget)?;
154 Self::mutate(root, visitor).map_err(JsonTreeMutateError::Visitor)?;
155 JsonTreeReader::new(&mut *self.output)
156 .account(root)
157 .map_err(JsonTreeMutateError::OutputBudget)
158 }
159
160 /// Runs mutable visitor callbacks without budget side effects.
161 ///
162 /// An explicit frame stack visits each node before its children. The
163 /// visitor may replace the current value or skip its descendants; its first
164 /// error stops traversal and is returned to the caller. Parent cursors
165 /// remain suspended while a child frame is active, preserving the
166 /// pointer-safety invariant documented for this module.
167 ///
168 /// # Type Parameters
169 ///
170 /// * `V` - Visitor receiving each mutable value and its location context.
171 ///
172 /// # Parameters
173 ///
174 /// * `root` - Root value whose nodes are visited and may be replaced.
175 /// * `visitor` - Callback applied before descending into each node's
176 /// children.
177 ///
178 /// # Returns
179 ///
180 /// `Ok(())` after all selected callbacks complete, or the first visitor
181 /// error before traversal finishes.
182 ///
183 /// # Errors
184 ///
185 /// Returns the visitor's error unchanged when a callback fails; mutations
186 /// already made to `root` remain in place.
187 ///
188 /// # Panics
189 ///
190 /// Panics only if the traversal stack invariant is violated and its active
191 /// frame is unexpectedly absent.
192 fn mutate<V>(root: &mut Value, visitor: &mut V) -> Result<(), V::Error>
193 where
194 V: JsonTreeMutVisitor,
195 {
196 // SAFETY: the stack is local to this call and is dropped before the
197 // exclusive borrow of `root` ends, including on error or panic exits.
198 let mut stack = vec![unsafe { MutFrame::root(root) }];
199 while !stack.is_empty() {
200 let index = stack.len() - 1;
201 if !stack[index].entered {
202 let frame = &mut stack[index];
203 // SAFETY: this is the top unentered frame, it has no cursor,
204 // and all ancestors remain suspended for the callback.
205 let control = unsafe { frame.visit(visitor) }?;
206 frame.entered = true;
207 if control != JsonTreeControl::Descend {
208 frame.finished = true;
209 }
210 continue;
211 }
212 // SAFETY: only the active top frame is advanced, after its visitor
213 // returned and its previously yielded child frame has been popped.
214 if let Some(child) = unsafe { stack[index].next_child() } {
215 stack.push(child);
216 continue;
217 }
218 let _ = stack.pop().expect("mutable frame exists");
219 }
220 Ok(())
221 }
222}