turbo_tasks/graph/
non_deterministic.rs

1use std::hash::Hash;
2
3use rustc_hash::FxHashSet;
4
5use super::graph_store::GraphStore;
6
7/// A graph traversal that does not guarantee any particular order, and may not
8/// return the same order every time it is run.
9pub struct NonDeterministic<T, E> {
10    output: Vec<T>,
11    visited: FxHashSet<T>,
12    phantom: std::marker::PhantomData<E>,
13}
14
15impl<T, E> Default for NonDeterministic<T, E> {
16    fn default() -> Self {
17        Self::new()
18    }
19}
20
21impl<T, E> NonDeterministic<T, E> {
22    pub fn new() -> Self {
23        Self {
24            output: Vec::new(),
25            visited: FxHashSet::default(),
26            phantom: std::marker::PhantomData,
27        }
28    }
29}
30
31impl<T, E> GraphStore for NonDeterministic<T, E>
32where
33    T: Send + Hash + Eq + Clone,
34    E: Send,
35{
36    type Node = T;
37    type Edge = E;
38    type Handle = ();
39
40    fn insert(&mut self, _from: Option<(&(), E)>, node: T) {
41        self.output.push(node);
42    }
43
44    fn try_enter(&mut self, node: &T) -> Option<()> {
45        if self.visited.insert(node.clone()) {
46            Some(())
47        } else {
48            None
49        }
50    }
51}
52
53impl<T, E> IntoIterator for NonDeterministic<T, E> {
54    type Item = T;
55    type IntoIter = <Vec<T> as IntoIterator>::IntoIter;
56
57    fn into_iter(self) -> Self::IntoIter {
58        self.output.into_iter()
59    }
60}
turbo_tasks/graph/non_deterministic.rs

turbo_tasks/graph/
non_deterministic.rs
