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}