1use crate::error::{PipelineError, invalid};
3use serde::{Deserialize, Serialize};
4use std::collections::{HashMap, HashSet};
5use std::fmt;
6
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
9pub enum Role {
10 Source,
11 Step,
12 Sink,
13}
14
15pub trait Kind: Sized {
18 type Error: From<PipelineError>;
20 const EXAMPLE: &'static str = "src=source:NAME";
22 fn parse(spec: &str) -> Result<Self, Self::Error>;
24 fn text(&self) -> String;
26 fn role(&self) -> Role;
27 fn check_tee(_tee: &str) -> Result<(), Self::Error> {
29 Ok(())
30 }
31 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 #[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 #[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
70pub type Resolve<'a, K> = &'a dyn Fn(&Node<K>) -> Option<String>;
72
73#[derive(Debug, Clone, PartialEq, Eq)]
76pub enum Problem {
77 Twice(String),
79 NoNode {
81 from: String,
82 to: String,
83 end: String,
84 },
85 FeedsItself(String),
86 Cycle(Vec<String>),
88 NoSource,
89 NoSink,
90 SourceHasInputs(String),
91 NoInput(String),
93 SinkNotLeaf(String),
94 LeafNotSink(String),
96 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 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 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 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 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 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 pub fn ups(&self, id: &str) -> Vec<&Edge> {
243 self.edges.iter().filter(|e| e.to == id).collect()
244 }
245
246 pub fn downs(&self, id: &str) -> Vec<&Edge> {
248 self.edges.iter().filter(|e| e.from == id).collect()
249 }
250
251 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}