Skip to main content

tvm_ffi/extra/
structural_walk.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//! Observer callbacks and adapters for structural walking.
21//!
22//! Callbacks report failures with [`Result`] and must not panic. A panic reaching
23//! the non-unwinding native callback boundary aborts the process.
24
25use super::structural_visit::{
26    DefRegionKind, StructuralVisitEngine, StructuralVisitorView, VisitInterrupt,
27};
28use crate::{Any, AnyView, Dispatcher, IntoDispatcher, Result};
29use std::borrow::BorrowMut;
30
31// -----------------------------------------------------------------------------
32// Key data structures and callback results.
33// -----------------------------------------------------------------------------
34
35/// What a callback asks the Rust walker to do with the current value.
36pub enum WalkResult {
37    /// Continue and visit this value's children.
38    Advance,
39    /// Continue without visiting this value's children or firing its exit hook.
40    Skip,
41    /// Halt the entire traversal.
42    Interrupt,
43    /// Halt the entire traversal and return a payload to the caller.
44    InterruptWith(Any),
45}
46
47/// The result of a walk callback: a [`WalkResult`], or a `Result<WalkResult>`
48/// for a callback that uses `?`.
49pub trait IntoWalkResult {
50    /// The result as a `Result<WalkResult>`.
51    fn into_walk_result(self) -> Result<WalkResult>;
52}
53
54impl IntoWalkResult for WalkResult {
55    #[inline(always)]
56    fn into_walk_result(self) -> Result<WalkResult> {
57        Ok(self)
58    }
59}
60
61impl IntoWalkResult for Result<WalkResult> {
62    #[inline(always)]
63    fn into_walk_result(self) -> Result<WalkResult> {
64        self
65    }
66}
67
68/// Callback order for [`structural_walk`].
69#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
70pub enum WalkOrder {
71    /// Run the typed handler before the current value's children.
72    #[default]
73    PreOrder,
74    /// Run the typed handler after the current value's children.
75    PostOrder,
76}
77
78// -----------------------------------------------------------------------------
79// Walk adapter to Dispatcher.
80// -----------------------------------------------------------------------------
81
82impl<O: IntoWalkResult> super::dispatch::CallbackResult<Result<WalkResult>> for O {
83    #[inline(always)]
84    fn callback_result(self) -> Result<WalkResult> {
85        self.into_walk_result()
86    }
87}
88
89// -----------------------------------------------------------------------------
90// Implementation of walk.
91// -----------------------------------------------------------------------------
92
93// A walk is an ordinary visitor handler: the visitor core owns all child
94// recursion, native hooks and region transitions. This adapter only chooses
95// when the observer runs and translates its control result.
96struct WalkVisitor<'a, D, const PRE_ORDER: bool> {
97    observer: &'a mut D,
98}
99
100impl<'v, 'c, 'r, 'a, D, const PRE_ORDER: bool>
101    Dispatcher<
102        (
103            AnyView<'v>,
104            &'c mut StructuralVisitorView<'r, WalkVisitor<'a, D, PRE_ORDER>>,
105        ),
106        Option<Result<Option<VisitInterrupt>>>,
107    > for &mut WalkVisitor<'a, D, PRE_ORDER>
108where
109    for<'d, 'b> &'d mut D: Dispatcher<(AnyView<'b>, DefRegionKind), Option<Result<WalkResult>>>,
110{
111    #[inline(always)]
112    fn dispatch_tuple(
113        self,
114        (value, visitor): (
115            AnyView<'v>,
116            &'c mut StructuralVisitorView<'r, WalkVisitor<'a, D, PRE_ORDER>>,
117        ),
118    ) -> Option<Result<Option<VisitInterrupt>>> {
119        Some(self.visit(value, visitor))
120    }
121}
122
123impl<'a, D, const PRE_ORDER: bool> WalkVisitor<'a, D, PRE_ORDER>
124where
125    for<'s, 'v> &'s mut D: Dispatcher<(AnyView<'v>, DefRegionKind), Option<Result<WalkResult>>>,
126{
127    #[inline(always)]
128    fn visit(
129        &mut self,
130        value: AnyView<'_>,
131        visitor: &mut StructuralVisitorView<'_, Self>,
132    ) -> Result<Option<VisitInterrupt>> {
133        let kind = visitor.def_region_kind();
134        if !PRE_ORDER && let Some(interrupt) = visitor.default_visit(self, value)? {
135            core::hint::cold_path();
136            return Ok(Some(interrupt));
137        }
138        match (&mut *self.observer)
139            .dispatch_tuple((value, kind))
140            .unwrap_or_else(|| Ok(WalkResult::Advance))?
141        {
142            WalkResult::Advance if PRE_ORDER => visitor.default_visit(self, value),
143            WalkResult::Advance => Ok(None),
144            WalkResult::Skip => {
145                core::hint::cold_path();
146                Ok(None)
147            }
148            WalkResult::Interrupt => {
149                core::hint::cold_path();
150                Ok(Some(VisitInterrupt::new(Any::new())))
151            }
152            WalkResult::InterruptWith(payload) => {
153                core::hint::cold_path();
154                Ok(Some(VisitInterrupt::new(payload)))
155            }
156        }
157    }
158}
159
160#[inline(always)]
161fn run_walker<D>(
162    root: AnyView<'_>,
163    observer: &mut D,
164    order: WalkOrder,
165) -> Result<Option<VisitInterrupt>>
166where
167    for<'s, 'v> &'s mut D: Dispatcher<(AnyView<'v>, DefRegionKind), Option<Result<WalkResult>>>,
168{
169    let root = *root.as_raw_ffi_any();
170    match order {
171        WalkOrder::PreOrder => {
172            StructuralVisitEngine::run_visitor(root, &mut WalkVisitor::<D, true> { observer })
173        }
174        WalkOrder::PostOrder => {
175            StructuralVisitEngine::run_visitor(root, &mut WalkVisitor::<D, false> { observer })
176        }
177    }
178}
179
180/// Walk `root` with an observer, calling it on every reachable value in
181/// `order`.
182///
183/// `walker` is anything implementing [`IntoDispatcher`]: a `&mut` reference to a
184/// stateful [`Dispatcher`] walker (declared with `#[dispatch]`), a bare closure
185/// in any [`crate::IntoDispatcher`] callback shape (catch-all `AnyView<'_>`, typed, or node,
186/// with an optional trailing [`DefRegionKind`]), or a tuple of such
187/// callbacks tried in order until one matches.
188/// Callback views cannot escape their invocation; retain an [`Any`] explicitly
189/// when a value must outlive the callback:
190///
191/// ```compile_fail,E0521
192/// use tvm_ffi::{structural_walk, AnyView, WalkOrder, WalkResult};
193/// let mut retained: Option<AnyView<'static>> = None;
194/// structural_walk(&1_i64, |value: AnyView<'_>| {
195///     retained = Some(value);
196///     WalkResult::Advance
197/// }, WalkOrder::PreOrder).unwrap();
198/// ```
199///
200/// The walker owns recursion: the handler runs once per value,
201/// before or after the value's children according to `order`, and steers
202/// traversal through the returned [`WalkResult`]. Walk accepts its existing
203/// dispatcher borrows, closure observers and callback tuples; each adapter runs
204/// through the same borrowed traversal engine.
205///
206/// Callbacks must report failures through [`Result`] and must not panic: a panic
207/// reaching the non-unwinding native callback boundary aborts the process.
208///
209/// A callback must not modify an `ffi.List` or `ffi.Dict` that holds the
210/// value it receives or one of that value's ancestors: the traversal borrows
211/// their cells while the callback runs.
212///
213/// # Arguments
214///
215/// * `root` - Value borrowed for traversal, convertible into an [`AnyView`].
216/// * `walker` - Mutable dispatcher, closure, or first-match callback tuple
217///   implementing [`IntoDispatcher`]. Each callback observes a value and returns a
218///   result convertible through [`IntoWalkResult`] to control traversal.
219/// * `order` - [`WalkOrder::PreOrder`] observes each value before its children;
220///   [`WalkOrder::PostOrder`] observes it after its children. Skipping children
221///   with [`WalkResult::Skip`] only affects pre-order traversal.
222///
223/// # Examples
224///
225/// Collect integer leaves with a typed closure:
226///
227/// ```
228/// use tvm_ffi::{structural_walk, Array, WalkOrder, WalkResult};
229///
230/// let root = Array::from_vec(vec![1_i64, 2, 3]);
231/// let mut integers = Vec::new();
232/// structural_walk(&root, |value: i64| {
233///     integers.push(value);
234///     WalkResult::Advance
235/// }, WalkOrder::PreOrder)?;
236/// assert_eq!(integers, vec![1, 2, 3]);
237/// # Ok::<(), tvm_ffi::Error>(())
238/// ```
239pub fn structural_walk<'input, R, M, H, D, O>(
240    root: R,
241    walker: H,
242    order: WalkOrder,
243) -> Result<Option<VisitInterrupt>>
244where
245    for<'v> H: IntoDispatcher<
246            (AnyView<'v>, DefRegionKind),
247            Option<Result<WalkResult>>,
248            M,
249            Target = D,
250            Output = O,
251        >,
252    for<'s, 'v> &'s mut D: Dispatcher<(AnyView<'v>, DefRegionKind), Option<Result<WalkResult>>>,
253    R: Into<AnyView<'input>>,
254    O: BorrowMut<D>,
255{
256    let mut storage = walker.into_dispatcher();
257    run_walker(root.into(), storage.borrow_mut(), order)
258}