Skip to main content

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}