esvc_core/
graph.rs

1use crate::Hash;
2use serde::{Deserialize, Serialize};
3use std::collections::{BTreeMap, BTreeSet};
4
5// NOTE: avoid changing these data types, it would influence the data format
6// which means that hashes or some other relevant stuff would change.
7// We don't want that. (especially this one)
8
9#[derive(Clone, Debug, Deserialize, Serialize, PartialEq, Eq)]
10pub struct Event<Arg> {
11    pub cmd: u32,
12    pub arg: Arg,
13    pub deps: BTreeSet<Hash>,
14}
15
16#[derive(Clone, Copy, Debug, PartialEq)]
17pub enum IncludeSpec {
18    IncludeAll,
19    IncludeOnlyDeps,
20}
21
22#[derive(Clone, Debug, Deserialize, Serialize, PartialEq, Eq)]
23pub struct Graph<Arg> {
24    pub events: BTreeMap<Hash, Event<Arg>>,
25
26    /// saved combined states
27    pub nstates: BTreeMap<String, BTreeSet<Hash>>,
28}
29
30impl<Arg> Default for Graph<Arg> {
31    fn default() -> Self {
32        Self {
33            events: BTreeMap::new(),
34            nstates: BTreeMap::new(),
35        }
36    }
37}
38
39#[derive(Clone, Debug, thiserror::Error)]
40pub enum GraphError {
41    #[error("unable to find the specified dataset")]
42    DatasetNotFound,
43
44    #[error("dependency circuit @ {0}")]
45    DependencyCircuit(Hash),
46
47    #[error("unable to retrieve dependency {0}")]
48    DependencyNotFound(Hash),
49
50    // we don't want any dependency on `Arg` here
51    #[error("hash collision @ {0} detected during insertion of {}")]
52    HashCollision(Hash, String),
53}
54
55impl<Arg: Serialize> Graph<Arg> {
56    /// fold a state, expanding of compressing it along the dependencies.
57    /// `st` entries should be initialized to `false` when creating a state from a `BTreeSet<Hash>`.
58    pub fn fold_state(
59        &self,
60        mut st: BTreeMap<Hash, bool>,
61        expand: bool,
62    ) -> Option<BTreeMap<Hash, bool>> {
63        loop {
64            let orig_len = st.len();
65            let mut errs = false;
66            st.extend(
67                st.clone()
68                    .into_iter()
69                    .flat_map(|(i, _)| match self.events.get(&i) {
70                        Some(x) => Some(x.deps.iter().map(|&j| (j, true))),
71                        None => {
72                            errs = true;
73                            None
74                        }
75                    })
76                    .flatten(),
77            );
78            if errs {
79                return None;
80            }
81            if orig_len == st.len() {
82                break;
83            }
84        }
85        if !expand {
86            // keep only non-dependencies
87            st.retain(|_, is_dep| !*is_dep);
88        }
89        Some(st)
90    }
91
92    /// utility function for debugging of incorrect evaluation orders
93    pub fn debug_exec_order(
94        &self,
95        evids: BTreeMap<Hash, IncludeSpec>,
96    ) -> Result<Vec<Hash>, GraphError> {
97        let mut tt = BTreeSet::new();
98        let mut ret = Vec::new();
99        let mut deps = Vec::new();
100        for (main_evid, incl) in evids {
101            // heap of necessary dependencies
102            deps.push(main_evid);
103
104            while let Some(evid) = deps.pop() {
105                if tt.contains(&evid) {
106                    // nothing to do
107                    continue;
108                } else if evid == main_evid && !deps.is_empty() {
109                    return Err(GraphError::DependencyCircuit(main_evid));
110                }
111
112                let evwd = self
113                    .events
114                    .get(&evid)
115                    .ok_or(GraphError::DependencyNotFound(evid))?;
116                let mut necessary_deps = evwd.deps.difference(&tt);
117                if let Some(&x) = necessary_deps.next() {
118                    deps.push(evid);
119                    // TODO: check for dependency cycles
120                    deps.push(x);
121                    deps.extend(necessary_deps.copied());
122                } else {
123                    if evid == main_evid && incl != IncludeSpec::IncludeAll {
124                        // we want to omit the final dep
125                        deps.clear();
126                        break;
127                    }
128                    // run the item, all dependencies are satisfied
129                    ret.push(evid);
130                    tt.insert(evid);
131                }
132            }
133        }
134        Ok(ret)
135    }
136}
137
138impl<Arg> Graph<Arg> {
139    /// get-or-insert event, check if it matches
140    ///
141    /// @returns (Some(@arg ev) if collision else None, Hash of @arg ev)
142    pub fn ensure_event(&mut self, ev: Event<Arg>) -> (Option<Event<Arg>>, Hash)
143    where
144        Arg: esvc_traits::CommandArg,
145    {
146        let serval = bincode::serialize::<Event<Arg>>(&ev).unwrap();
147        let h = crate::calculate_hash(&serval[..]);
148        use std::collections::btree_map::Entry;
149        (
150            match self.events.entry(h) {
151                Entry::Occupied(o) if o.get() == &ev => None,
152                Entry::Occupied(_) => Some(ev),
153                Entry::Vacant(v) => {
154                    v.insert(ev);
155                    None
156                }
157            },
158            h,
159        )
160    }
161}
162
163pub fn print_deps<W, DI>(w: &mut W, pfx: &str, deps: DI) -> std::io::Result<()>
164where
165    DI: Iterator<Item = Hash>,
166    W: std::io::Write,
167{
168    for i in deps {
169        writeln!(w, "{}{}", pfx, i)?;
170    }
171    Ok(())
172}
esvc_core/graph.rs

esvc_core/
graph.rs
