turbo_tasks/graph/
visit.rs

1use std::future::Future;
2
3use anyhow::Result;
4use tracing::Span;
5
6use super::VisitControlFlow;
7
8/// A trait that allows a graph traversal to visit the edges of a node
9/// transitively.
10pub trait Visit<Node, Abort = !, Impl = ()> {
11    type Edge;
12    type EdgesIntoIter: IntoIterator<Item = Self::Edge>;
13    type EdgesFuture: Future<Output = Result<Self::EdgesIntoIter>> + Send;
14
15    /// Visits an edge to get to the neighbor node. Should return a
16    /// [`VisitControlFlow`] that indicates whether to:
17    /// * continue visiting the neighbor node edges;
18    /// * skip visiting the neighbor node's edges;
19    /// * abort the traversal entirely.
20    fn visit(&mut self, edge: Self::Edge) -> VisitControlFlow<Node, Abort>;
21
22    /// Returns a future that resolves to the outgoing edges of the given `node`.
23    ///
24    /// Lifetimes:
25    /// - The returned future's lifetime cannot depend on the reference to self because there are
26    ///   multiple `edges` futures created and awaited concurrently.
27    /// - The returned future's lifetime cannot depend on `node` because `GraphStore::insert`
28    ///   returns a node reference that's only valid for the lifetime of its `&mut self` reference.
29    fn edges(&mut self, node: &Node) -> Self::EdgesFuture;
30
31    /// Returns a [Span] for the given `node`, under which all edges are
32    /// processed.
33    fn span(&mut self, node: &Node) -> Span {
34        let _ = node;
35        Span::current()
36    }
37}
38
39// The different `Impl*` here are necessary in order to avoid the `Conflicting
40// implementations of trait` error when implementing `Visit` on different
41// kinds of `FnMut`.
42// See https://users.rust-lang.org/t/conflicting-implementation-when-implementing-traits-for-fn/53359/3
43
44pub struct ImplRef;
45
46impl<Node, VisitFn, NeighFut, NeighIt> Visit<Node, !, ImplRef> for VisitFn
47where
48    VisitFn: FnMut(&Node) -> NeighFut,
49    NeighFut: Future<Output = Result<NeighIt>> + Send,
50    NeighIt: IntoIterator<Item = Node>,
51{
52    type Edge = Node;
53    type EdgesIntoIter = NeighIt;
54    type EdgesFuture = NeighFut;
55
56    fn visit(&mut self, edge: Self::Edge) -> VisitControlFlow<Node> {
57        VisitControlFlow::Continue(edge)
58    }
59
60    fn edges(&mut self, node: &Node) -> Self::EdgesFuture {
61        (self)(node)
62    }
63}
64
65pub struct ImplValue;
66
67impl<Node, VisitFn, NeighFut, NeighIt> Visit<Node, !, ImplValue> for VisitFn
68where
69    Node: Clone,
70    VisitFn: FnMut(Node) -> NeighFut,
71    NeighFut: Future<Output = Result<NeighIt>> + Send,
72    NeighIt: IntoIterator<Item = Node>,
73{
74    type Edge = Node;
75    type EdgesIntoIter = NeighIt;
76    type EdgesFuture = NeighFut;
77
78    fn visit(&mut self, edge: Self::Edge) -> VisitControlFlow<Node> {
79        VisitControlFlow::Continue(edge)
80    }
81
82    fn edges(&mut self, node: &Node) -> Self::EdgesFuture {
83        (self)(node.clone())
84    }
85}
turbo_tasks/graph/visit.rs

turbo_tasks/graph/
visit.rs
