Skip to main content

weirdnet_pipelines/
graph.rs

1//! Graph types, the node and edge syntax, ordering and checks.
2use crate::error::{PipelineError, invalid};
3use serde::{Deserialize, Serialize};
4use std::collections::{HashMap, HashSet};
5use std::fmt;
6
7/// Where a node sits: sources have no inputs, sinks are the leaves, steps are in between.
8#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum Role {
10    Source,
11    Step,
12    Sink,
13}
14
15/// What a node does, defined by the application: how its spec reads and prints, and its role.
16/// The crate gives no source, step or sink any meaning of its own.
17pub trait Kind: Sized {
18    /// The application's error; graph errors convert into it.
19    type Error: From<PipelineError>;
20    /// A node spec shown when one has no `=` (`src=source:NAME`).
21    const EXAMPLE: &'static str = "src=source:NAME";
22    /// Read the part of a node spec after `ID=` and before any `+tee`.
23    fn parse(spec: &str) -> Result<Self, Self::Error>;
24    /// The spec again (`parse(text())` gives the same kind).
25    fn text(&self) -> String;
26    fn role(&self) -> Role;
27    /// Check a tee (a side save: `+SPEC` after the kind) when the node is read.
28    fn check_tee(_tee: &str) -> Result<(), Self::Error> {
29        Ok(())
30    }
31    /// What a sink lands in, for [`crate::PipelineRun::landed`] (its text by default).
32    fn target(&self) -> String {
33        self.text()
34    }
35}
36
37#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
38pub struct Node<K> {
39    pub id: String,
40    #[serde(flatten)]
41    pub kind: K,
42    /// Side saves along the way: the data is saved there and flows on.
43    #[serde(default, skip_serializing_if = "Vec::is_empty")]
44    pub tees: Vec<String>,
45}
46
47#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
48pub struct Edge {
49    pub from: String,
50    pub to: String,
51    /// The name the downstream node gets this input under (default: the upstream's id).
52    #[serde(default, rename = "as", skip_serializing_if = "Option::is_none")]
53    pub name: Option<String>,
54}
55
56#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
57pub struct Graph<K> {
58    #[serde(default = "Vec::new")]
59    pub nodes: Vec<Node<K>>,
60    #[serde(default)]
61    pub edges: Vec<Edge>,
62}
63
64impl<K> Default for Graph<K> {
65    fn default() -> Self {
66        Graph { nodes: vec![], edges: vec![] }
67    }
68}
69
70/// Says why a node's names do not resolve in the application (`None`: they do).
71pub type Resolve<'a, K> = &'a dyn Fn(&Node<K>) -> Option<String>;
72
73/// Something wrong with a graph ([`Graph::check`]). The texts are general; an application
74/// can word them its own way by matching on the variant.
75#[derive(Debug, Clone, PartialEq, Eq)]
76pub enum Problem {
77    /// Two nodes have this id.
78    Twice(String),
79    /// An edge names a node that is not there (`end`).
80    NoNode {
81        from: String,
82        to: String,
83        end: String,
84    },
85    FeedsItself(String),
86    /// The nodes that could not be ordered.
87    Cycle(Vec<String>),
88    NoSource,
89    NoSink,
90    SourceHasInputs(String),
91    /// A step or sink with nothing feeding it.
92    NoInput(String),
93    SinkNotLeaf(String),
94    /// A leaf that is not a sink.
95    LeafNotSink(String),
96    /// The application could not resolve what the node names.
97    Unresolved {
98        id: String,
99        why: String,
100    },
101}
102
103impl fmt::Display for Problem {
104    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
105        match self {
106            Problem::Twice(id) => write!(f, "node `{id}` is there twice"),
107            Problem::NoNode { from, to, end } => write!(f, "edge {from}>{to}: no node `{end}`"),
108            Problem::FeedsItself(id) => write!(f, "node `{id}` feeds itself"),
109            Problem::Cycle(ids) => write!(f, "{}", cycle(ids)),
110            Problem::NoSource => write!(f, "no source node"),
111            Problem::NoSink => write!(f, "no sink node"),
112            Problem::SourceHasInputs(id) => write!(f, "source `{id}` has inputs"),
113            Problem::NoInput(id) => write!(f, "`{id}` gets no data (connect a source to it)"),
114            Problem::SinkNotLeaf(id) => write!(f, "sink `{id}` must be a leaf (nothing after it)"),
115            Problem::LeafNotSink(id) => write!(f, "`{id}` is a leaf: every leaf is a sink"),
116            Problem::Unresolved { id, why } => write!(f, "`{id}`: {why}"),
117        }
118    }
119}
120
121fn cycle(ids: &[String]) -> PipelineError {
122    invalid(format!("a cycle through {}", ids.join(", ")))
123}
124
125impl<K: Kind> Graph<K> {
126    /// Read `ID=KIND` node specs (with `+tee` saves: `raw=step:fast+save:raw`) and
127    /// `A>B[:NAME]` edges; `A>B>C` chains.
128    pub fn parse(nodes: &[String], edges: &[String]) -> Result<Self, K::Error> {
129        let mut g: Graph<K> = Graph::default();
130        for n in nodes {
131            g.add_node(n)?;
132        }
133        for e in edges {
134            g.add_edges(e)?;
135        }
136        Ok(g)
137    }
138
139    /// Add a node, or replace the one with its id.
140    pub fn add_node(&mut self, spec: &str) -> Result<(), K::Error> {
141        let (id, rest) = spec.split_once('=').ok_or_else(|| invalid(format!("`{spec}`: a node is ID=KIND ({})", K::EXAMPLE)))?;
142        let id = id.trim().to_string();
143        if id.is_empty() || id.contains(['>', ':', ' ']) {
144            return Err(invalid(format!("`{id}` is not a node id (letters, digits, - and _)")).into());
145        }
146        let mut parts = rest.split('+');
147        let kind = K::parse(parts.next().unwrap_or_default())?;
148        let tees: Vec<String> = parts.map(|t| t.trim().to_string()).collect();
149        for t in &tees {
150            K::check_tee(t)?;
151        }
152        match self.nodes.iter_mut().find(|n| n.id == id) {
153            Some(n) => *n = Node { id, kind, tees },
154            None => self.nodes.push(Node { id, kind, tees }),
155        }
156        Ok(())
157    }
158
159    /// What is wrong with the graph (empty: valid). `resolve`, when given, says why a node's
160    /// names do not resolve in the application (`None`: they do).
161    pub fn check(&self, resolve: Option<Resolve<'_, K>>) -> Vec<Problem> {
162        let mut p = vec![];
163        let mut seen = HashSet::new();
164        for n in &self.nodes {
165            if !seen.insert(n.id.as_str()) {
166                p.push(Problem::Twice(n.id.clone()));
167            }
168        }
169        for e in &self.edges {
170            for end in [&e.from, &e.to] {
171                if self.node(end).is_none() {
172                    p.push(Problem::NoNode { from: e.from.clone(), to: e.to.clone(), end: end.clone() });
173                }
174            }
175            if e.from == e.to {
176                p.push(Problem::FeedsItself(e.from.clone()));
177            }
178        }
179        if let Err(stuck) = self.ordered() {
180            p.push(Problem::Cycle(stuck));
181        }
182        if !self.nodes.iter().any(|n| n.kind.role() == Role::Source) {
183            p.push(Problem::NoSource);
184        }
185        if !self.nodes.iter().any(|n| n.kind.role() == Role::Sink) {
186            p.push(Problem::NoSink);
187        }
188        for n in &self.nodes {
189            let (ups, downs) = (self.ups(&n.id).len(), self.downs(&n.id).len());
190            let role = n.kind.role();
191            match role {
192                Role::Source if ups > 0 => p.push(Problem::SourceHasInputs(n.id.clone())),
193                Role::Source => {}
194                _ if ups == 0 => p.push(Problem::NoInput(n.id.clone())),
195                _ => {}
196            }
197            match role {
198                Role::Sink if downs > 0 => p.push(Problem::SinkNotLeaf(n.id.clone())),
199                Role::Sink => {}
200                _ if downs == 0 => p.push(Problem::LeafNotSink(n.id.clone())),
201                _ => {}
202            }
203            if let Some(why) = resolve.and_then(|r| r(n)) {
204                p.push(Problem::Unresolved { id: n.id.clone(), why });
205            }
206        }
207        p
208    }
209}
210
211impl<K> Graph<K> {
212    /// Add `A>B[:NAME]` edges (`A>B>C` chains); an edge already there is kept as it is.
213    pub fn add_edges(&mut self, spec: &str) -> Result<(), PipelineError> {
214        let hops: Vec<&str> = spec.split('>').map(str::trim).collect();
215        if hops.len() < 2 || hops.iter().any(|h| h.is_empty()) {
216            return Err(invalid(format!("`{spec}`: an edge is FROM>TO[:NAME] (or A>B>C)")));
217        }
218        for w in hops.windows(2) {
219            let (to, name) = w[1].split_once(':').map(|(a, b)| (a.trim(), Some(b.trim().to_string()))).unwrap_or((w[1], None));
220            let from = w[0].split_once(':').map(|x| x.0.trim()).unwrap_or(w[0]);
221            let e = Edge { from: from.into(), to: to.into(), name };
222            if !self.edges.iter().any(|x| x.from == e.from && x.to == e.to) {
223                self.edges.push(e);
224            }
225        }
226        Ok(())
227    }
228
229    /// Remove a node and its edges; whether it was there.
230    pub fn remove_node(&mut self, id: &str) -> bool {
231        let n = self.nodes.len();
232        self.nodes.retain(|x| x.id != id);
233        self.edges.retain(|e| e.from != id && e.to != id);
234        n != self.nodes.len()
235    }
236
237    pub fn node(&self, id: &str) -> Option<&Node<K>> {
238        self.nodes.iter().find(|n| n.id == id)
239    }
240
241    /// Edges into a node.
242    pub fn ups(&self, id: &str) -> Vec<&Edge> {
243        self.edges.iter().filter(|e| e.to == id).collect()
244    }
245
246    /// Edges out of a node.
247    pub fn downs(&self, id: &str) -> Vec<&Edge> {
248        self.edges.iter().filter(|e| e.from == id).collect()
249    }
250
251    /// Node ids in an order where every node comes after its upstreams (ties in the order
252    /// the nodes were added); `Err` names a cycle.
253    pub fn order(&self) -> Result<Vec<String>, PipelineError> {
254        self.ordered().map_err(|stuck| cycle(&stuck))
255    }
256
257    fn ordered(&self) -> Result<Vec<String>, Vec<String>> {
258        let mut deg: HashMap<&str, usize> = self.nodes.iter().map(|n| (n.id.as_str(), 0)).collect();
259        for e in &self.edges {
260            if let Some(d) = deg.get_mut(e.to.as_str()) {
261                *d += 1;
262            }
263        }
264        let mut ready: Vec<&str> = self.nodes.iter().map(|n| n.id.as_str()).filter(|id| deg[id] == 0).collect();
265        let mut out = vec![];
266        while let Some(id) = (!ready.is_empty()).then(|| ready.remove(0)) {
267            out.push(id.to_string());
268            for e in self.edges.iter().filter(|e| e.from == id) {
269                if let Some(d) = deg.get_mut(e.to.as_str()) {
270                    *d -= 1;
271                    if *d == 0 {
272                        ready.push(e.to.as_str());
273                    }
274                }
275            }
276        }
277        if out.len() < self.nodes.len() {
278            return Err(self.nodes.iter().map(|n| n.id.clone()).filter(|id| !out.contains(id)).collect());
279        }
280        Ok(out)
281    }
282}