tvm_ffi/extra/structural_map.rs
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20//! Ordered replacement callbacks and adapters for structural mapping.
21
22use super::structural_common::raw_ffi_any_same_as;
23use super::structural_mutate::{
24 IntoMutateResult, MutationView, StructuralMutateEngine, StructuralMutatorView,
25};
26use super::structural_visit::DefRegionKind;
27use super::structural_walk::WalkOrder;
28use super::unchanged::{UnchangedOr, is_unchanged};
29use super::visit_error_context::update_visit_error_context;
30use crate::{Any, AnyView, Dispatcher, IntoDispatcher, Result};
31use std::borrow::BorrowMut;
32
33// -----------------------------------------------------------------------------
34// Map adapter to Dispatcher.
35// -----------------------------------------------------------------------------
36
37impl<O: IntoMutateResult> super::dispatch::CallbackResult<Result<Any>> for O {
38 #[inline(always)]
39 fn callback_result(self) -> Result<Any> {
40 self.into_mutate_result().map(Any::from)
41 }
42}
43
44impl<O: IntoMutateResult> super::dispatch::CallbackResult<Result<UnchangedOr<Any>>> for O {
45 #[inline(always)]
46 fn callback_result(self) -> Result<UnchangedOr<Any>> {
47 self.into_mutate_result()
48 }
49}
50
51// -----------------------------------------------------------------------------
52// Implementation of map.
53// -----------------------------------------------------------------------------
54
55struct MapMutator<'a, D, const PRE_ORDER: bool> {
56 dispatch: &'a mut D,
57}
58
59fn run_mapper<D>(root: Any, dispatch: &mut D, order: WalkOrder) -> Result<Any>
60where
61 for<'s, 'v> &'s mut D:
62 Dispatcher<(AnyView<'v>, DefRegionKind), Option<Result<UnchangedOr<Any>>>>,
63{
64 match order {
65 WalkOrder::PreOrder => {
66 StructuralMutateEngine::run_mutator::<MapMutator<'_, D, true>, false>(
67 root,
68 &mut MapMutator::<D, true> { dispatch },
69 )
70 }
71 WalkOrder::PostOrder => StructuralMutateEngine::run_mutator::<
72 MapMutator<'_, D, false>,
73 false,
74 >(root, &mut MapMutator::<D, false> { dispatch }),
75 }
76}
77
78impl<'v, 'c, 'r, 'a, D, const PRE_ORDER: bool>
79 Dispatcher<
80 (
81 MutationView<'v>,
82 &'c mut StructuralMutatorView<'r, MapMutator<'a, D, PRE_ORDER>>,
83 ),
84 Option<Result<UnchangedOr<Any>>>,
85 > for &mut MapMutator<'a, D, PRE_ORDER>
86where
87 for<'s, 'value> &'s mut D:
88 Dispatcher<(AnyView<'value>, DefRegionKind), Option<Result<UnchangedOr<Any>>>>,
89{
90 #[inline(always)]
91 fn dispatch_tuple(
92 self,
93 (value, mutator): (
94 MutationView<'v>,
95 &'c mut StructuralMutatorView<'r, MapMutator<'a, D, PRE_ORDER>>,
96 ),
97 ) -> Option<Result<UnchangedOr<Any>>> {
98 Some(self.map_current(value, mutator).map(UnchangedOr::from_any))
99 }
100}
101
102impl<D, const PRE_ORDER: bool> MapMutator<'_, D, PRE_ORDER>
103where
104 for<'s, 'v> &'s mut D:
105 Dispatcher<(AnyView<'v>, DefRegionKind), Option<Result<UnchangedOr<Any>>>>,
106{
107 #[inline(always)]
108 fn map_current(
109 &mut self,
110 value: MutationView<'_>,
111 mutator: &mut StructuralMutatorView<'_, Self>,
112 ) -> Result<Any> {
113 let mode = value.inplace_mode();
114 let raw = *value.as_any_view().as_raw_ffi_any();
115 let kind = mutator.def_region_kind();
116 if PRE_ORDER {
117 // Snapshot the mode before a callback can retain or release ownership.
118 // SAFETY: the input owner, possibly a list or dict cell the callback
119 // does not modify (the callback contract), remains live through this
120 // synchronous callback; its higher-ranked view cannot escape into the
121 // owning result.
122 let Some(callback_result) = self
123 .dispatch
124 .dispatch_tuple((unsafe { AnyView::from_raw_ffi_any(raw) }, kind))
125 else {
126 return mutator.default_mutate(self, value).map(Into::into);
127 };
128 let mapped: Any = callback_result
129 .map_err(|error| update_visit_error_context(error, raw))?
130 .into();
131 if is_unchanged(&mapped) || raw_ffi_any_same_as(raw, *mapped.as_raw_ffi_any()) {
132 // Drop temporary ownership before default descent checks uniqueness.
133 drop(mapped);
134 mutator.default_mutate(self, value).map(Into::into)
135 } else {
136 let replacement = MutationView::new(AnyView::from(&mapped), mode);
137 let descended: Any = mutator.default_mutate(self, replacement)?.into();
138 Ok(if is_unchanged(&descended) {
139 mapped
140 } else {
141 descended
142 })
143 }
144 } else {
145 let mapped: Any = mutator.default_mutate(self, value)?.into();
146 let current = if is_unchanged(&mapped) {
147 // SAFETY: Unchanged leaves the original input owner in place, and
148 // the callback does not modify a list or dict cell holding it (the
149 // callback contract). Borrow it only through the callback; the
150 // other branch borrows mapped.
151 unsafe { AnyView::from_raw_ffi_any(raw) }
152 } else {
153 AnyView::from(&mapped)
154 };
155 match self.dispatch.dispatch_tuple((current, kind)) {
156 Some(Ok(result)) if result.is_unchanged() => Ok(mapped),
157 Some(result) => result
158 .map(Any::from)
159 .map_err(|error| update_visit_error_context(error, *current.as_raw_ffi_any())),
160 None => Ok(mapped),
161 }
162 }
163 }
164}
165
166/// Transform a structured value graph with ordered replacement callbacks.
167///
168/// The root is consumed. A uniquely owned built-in container may therefore be
169/// reused in place, while passing `root.clone()` keeps the original shared and
170/// selects copy-on-write behavior. Map and Dict keys are anchors and are not
171/// mapped. Their registered structural hooks own container traversal.
172///
173/// Callbacks run at every occurrence. Default reflected descent handles FreeVar
174/// and DAG-node remapping; registered hooks own their type's remapping policy.
175/// Callback replacements are not automatically recorded as substitutions.
176///
177/// In-place changes completed before an error are not rolled back. Because
178/// this function consumes `root`, an error does not return the partly mapped
179/// root to the caller.
180///
181/// Callbacks must report failures through [`Result`] and must not panic: a panic
182/// reaching the non-unwinding native callback boundary aborts the process.
183///
184/// A callback must not modify an `ffi.List` or `ffi.Dict` that holds the
185/// value it receives or one of that value's ancestors: the traversal borrows
186/// their cells while the callback runs. A callback that returns an `Error`
187/// object as its value fails the traversal with a `TypeError`.
188///
189/// # Arguments
190///
191/// * `root` - Owned value to transform, convertible into an [`Any`]. Clone it
192/// first to preserve the original through copy-on-write behavior.
193/// * `mapper` - Mutable dispatcher, closure, or first-match callback tuple
194/// implementing [`IntoDispatcher`]. Callbacks return replacements; unmatched
195/// values retain their value while default traversal maps their children.
196/// * `order` - [`WalkOrder::PreOrder`] applies the callback before traversing the
197/// replacement's children; [`WalkOrder::PostOrder`] maps children before
198/// applying the callback to their parent.
199///
200/// # Examples
201///
202/// Increment integer leaves while keeping a shared original unchanged:
203///
204/// ```
205/// use tvm_ffi::{structural_map, Array, WalkOrder};
206///
207/// let root = Array::from_vec(vec![1_i64, 2, 3]);
208/// let mapped = structural_map(root.clone(), |value: i64| value + 1, WalkOrder::PostOrder)?;
209/// let mapped = Array::<i64>::try_from(mapped)?;
210/// assert_eq!(mapped.iter().copied().collect::<Vec<_>>(), vec![2, 3, 4]);
211/// assert_eq!(root.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
212/// # Ok::<(), tvm_ffi::Error>(())
213/// ```
214pub fn structural_map<R, M, H, D, O>(root: R, mapper: H, order: WalkOrder) -> Result<Any>
215where
216 R: Into<Any>,
217 O: BorrowMut<D>,
218 for<'v> H: IntoDispatcher<
219 (AnyView<'v>, DefRegionKind),
220 Option<Result<UnchangedOr<Any>>>,
221 M,
222 Target = D,
223 Output = O,
224 >,
225 for<'s, 'v> &'s mut D:
226 Dispatcher<(AnyView<'v>, DefRegionKind), Option<Result<UnchangedOr<Any>>>>,
227{
228 run_mapper(root.into(), mapper.into_dispatcher().borrow_mut(), order)
229}