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    /// # Type Parameters
119    ///
120    /// * `V` - Visitor controlling mutations and descendant callbacks.
121    ///
122    /// # Parameters
123    ///
124    /// * `root` - Root JSON value to process and mutate.
125    /// * `visitor` - Visitor applied after complete input admission.
126    ///
127    /// # Returns
128    ///
129    /// `Ok(())` after both complete trees fit and every callback succeeds.
130    ///
131    /// # Errors
132    ///
133    /// Returns [`JsonTreeMutateError::InputBudget`] before mutation when the
134    /// original tree is rejected, [`JsonTreeMutateError::Visitor`] after a
135    /// callback failure, or [`JsonTreeMutateError::OutputBudget`] after a
136    /// complete mutation whose result is rejected. Visitor and output failures
137    /// retain mutations already made to `root`.
138    pub fn process<V>(&mut self, root: &mut Value, visitor: &mut V) -> Result<(), JsonTreeMutateError<R, Q, V::Error>>
139    where
140        V: JsonTreeMutVisitor,
141    {
142        JsonTreeReader::new(&mut *self.input)
143            .account(root)
144            .map_err(JsonTreeMutateError::InputBudget)?;
145        Self::mutate(root, visitor).map_err(JsonTreeMutateError::Visitor)?;
146        JsonTreeReader::new(&mut *self.output)
147            .account(root)
148            .map_err(JsonTreeMutateError::OutputBudget)
149    }
150
151    /// Runs mutable visitor callbacks without budget side effects.
152    fn mutate<V>(root: &mut Value, visitor: &mut V) -> Result<(), V::Error>
153    where
154        V: JsonTreeMutVisitor,
155    {
156        let mut stack = vec![MutFrame::root(root)];
157        while !stack.is_empty() {
158            let index = stack.len() - 1;
159            if !stack[index].entered {
160                let frame = &mut stack[index];
161                let context = frame.location.context(frame.depth);
162                // SAFETY: frames originate from the caller's exclusive root
163                // borrow. No ancestor container is accessed while a child
164                // frame is live, and each frame is removed before its parent
165                // resumes structural traversal.
166                let value = unsafe { frame.value.as_mut() };
167                let control = visitor.visit(value, context)?;
168                frame.entered = true;
169                if control != JsonTreeControl::Descend {
170                    frame.finished = true;
171                }
172                continue;
173            }
174            if let Some(child) = stack[index].next_child() {
175                stack.push(child);
176                continue;
177            }
178            let _ = stack.pop().expect("mutable frame exists");
179        }
180        Ok(())
181    }
182}
qubit_json/value/traverse/json_tree_mutator.rs

qubit_json/value/traverse/
json_tree_mutator.rs
