module_util/evaluator/dfs/
mod.rs

1//! [`Dfs`] evaluation.
2
3use alloc::collections::{LinkedList, VecDeque};
4use alloc::vec::Vec;
5
6use module::merge::Merge;
7
8use super::{Evaluator, Imports, Trace};
9
10pub mod error;
11pub use self::error::Error;
12
13///////////////////////////////////////////////////////////////////////////////
14
15/// An [`Evaluator`] that visits modules in DFS order.
16#[derive(Debug)]
17pub struct Dfs<I, M> {
18    imports: LinkedList<VecDeque<I>>,
19    value: Option<M>,
20
21    /// Module trace.
22    pub trace: Trace<I>,
23}
24
25impl<I, M> Dfs<I, M> {
26    /// Create a new [`Dfs`] evaluator.
27    #[must_use]
28    pub const fn new() -> Self {
29        Self {
30            imports: LinkedList::new(),
31            value: None,
32            trace: Trace::empty(),
33        }
34    }
35}
36
37impl<I, M> Default for Dfs<I, M> {
38    #[inline]
39    fn default() -> Self {
40        Self::new()
41    }
42}
43
44impl<I, M> Evaluator for Dfs<I, M>
45where
46    M: Merge,
47{
48    type Id = I;
49    type Module = M;
50    type Error = Error;
51
52    fn is_empty(&self) -> bool {
53        self.value.is_none()
54    }
55
56    fn next(&mut self) -> Option<Self::Id> {
57        loop {
58            let x = self.imports.front_mut()?;
59
60            match x.pop_front() {
61                Some(x) => break Some(x),
62                None => {
63                    let _ = self.trace.pop();
64                    let _ = self.imports.pop_front();
65                    continue;
66                }
67            }
68        }
69    }
70
71    fn eval(
72        &mut self,
73        id: Self::Id,
74        imports: Imports<Self::Id>,
75        module: Self::Module,
76    ) -> Result<(), Self::Error> {
77        self.trace.push(id);
78        self.imports.push_front(VecDeque::from(Vec::from(imports)));
79        self.value.merge_ref(Some(module)).map_err(Error::Merge)?;
80        Ok(())
81    }
82
83    fn finish(self) -> Option<Self::Module> {
84        self.value
85    }
86}
module_util/evaluator/dfs/mod.rs

module_util/evaluator/dfs/
mod.rs
