vissue_core/
graph.rs

1//! In-memory dependency graph for validation and bounded multi-hop queries.
2
3use anyhow::anyhow;
4
5use crate::error::Result;
6use daggy::{Dag, NodeIndex};
7use petgraph::Direction;
8use petgraph::algo::{has_path_connecting, toposort};
9use std::collections::{HashMap, HashSet, VecDeque};
10
11use crate::error::Error;
12use crate::model::IssueHeading;
13
14/// A blocker edge points from the prerequisite to the issue waiting on it.
15#[derive(Debug)]
16pub struct DependencyGraph {
17    dag: Dag<String, ()>,
18    ids: HashMap<String, NodeIndex>,
19}
20
21impl DependencyGraph {
22    /// Build a graph and reject malformed duplicate IDs or cyclic dependencies.
23    ///
24    /// # Errors
25    ///
26    /// Returns an error if two headings share an id, an issue blocks itself, or
27    /// the blocker edges form a cycle.
28    pub fn from_issues(issues: &[(String, IssueHeading)]) -> Result<Self> {
29        Self::from_headings(issues.iter().map(|(_, heading)| heading))
30    }
31
32    /// Same graph as [`Self::from_issues`], without copying headings.
33    ///
34    /// # Errors
35    ///
36    /// Returns an error if two headings share an id, an issue blocks itself, or
37    /// the blocker edges form a cycle.
38    pub fn from_headings<'a, I>(issues: I) -> Result<Self>
39    where
40        I: IntoIterator<Item = &'a IssueHeading>,
41    {
42        let headings: Vec<&IssueHeading> = issues.into_iter().collect();
43        let mut graph = Self {
44            dag: Dag::new(),
45            ids: HashMap::with_capacity(headings.len()),
46        };
47        let mut seen_edges = HashSet::new();
48        for issue in &headings {
49            if graph.ids.contains_key(&issue.id) {
50                return Err(anyhow!("duplicate issue id {}", issue.id).into());
51            }
52            let node = graph.dag.add_node(issue.id.clone());
53            graph.ids.insert(issue.id.clone(), node);
54        }
55        for issue in &headings {
56            for blocker in issue.blocked_by() {
57                let Some(&from) = graph.ids.get(&blocker) else {
58                    continue;
59                };
60                let to = graph.ids[&issue.id];
61                if from == to {
62                    return Err(anyhow!("issue {} blocks itself", issue.id).into());
63                }
64                if !seen_edges.insert((from, to)) {
65                    continue;
66                }
67                graph
68                    .dag
69                    .add_edge(from, to, ())
70                    .map_err(|_| anyhow!("blocker cycle involving {} and {}", blocker, issue.id))?;
71            }
72        }
73        Ok(graph)
74    }
75
76    /// Validate a prospective blocker insertion without mutating the graph.
77    ///
78    /// Unknown ids are accepted: a missing endpoint is not a cycle.
79    ///
80    /// # Errors
81    ///
82    /// Returns an error if `blocker` is `issue`, or if adding the edge would
83    /// close a loop.
84    pub fn accepts_edge(&self, blocker: &str, issue: &str) -> std::result::Result<(), Error> {
85        let Some(&from) = self.ids.get(blocker) else {
86            return Ok(());
87        };
88        let Some(&to) = self.ids.get(issue) else {
89            return Ok(());
90        };
91        if from == to || has_path_connecting(self.dag.graph(), to, from, None) {
92            return Err(Error::BlockerCycle {
93                blocker: blocker.to_string(),
94                issue: issue.to_string(),
95            });
96        }
97        Ok(())
98    }
99
100    /// Return a deterministic prerequisite-first order.
101    ///
102    /// # Errors
103    ///
104    /// Returns an error if the graph contains a cycle.
105    pub fn topological_ids(&self) -> Result<Vec<String>> {
106        let ids = toposort(self.dag.graph(), None)
107            .map_err(|cycle| anyhow!("dependency cycle at {}", self.dag.graph()[cycle.node_id()]))?
108            .into_iter()
109            .map(|node| self.dag.graph()[node].clone())
110            .collect::<Vec<_>>();
111        Ok(ids)
112    }
113
114    /// Return nodes that transitively block issue, bounded by hop depth.
115    ///
116    /// # Errors
117    ///
118    /// Returns an error if `issue` is not in the graph.
119    pub fn ancestors(
120        &self,
121        issue: &str,
122        depth: usize,
123    ) -> std::result::Result<Vec<(usize, String)>, Error> {
124        self.walk(issue, depth, Direction::Incoming)
125    }
126
127    /// Return nodes transitively waiting on issue, bounded by hop depth.
128    ///
129    /// # Errors
130    ///
131    /// Returns an error if `issue` is not in the graph.
132    pub fn descendants(
133        &self,
134        issue: &str,
135        depth: usize,
136    ) -> std::result::Result<Vec<(usize, String)>, Error> {
137        self.walk(issue, depth, Direction::Outgoing)
138    }
139
140    fn walk(
141        &self,
142        issue: &str,
143        depth: usize,
144        direction: Direction,
145    ) -> std::result::Result<Vec<(usize, String)>, Error> {
146        let Some(&root) = self.ids.get(issue) else {
147            return Err(Error::IssueNotFound {
148                id: issue.to_string(),
149            });
150        };
151        let mut seen = HashSet::from([root]);
152        let mut queue = VecDeque::from([(root, 0usize)]);
153        let mut result = Vec::new();
154        while let Some((node, distance)) = queue.pop_front() {
155            if distance == depth {
156                continue;
157            }
158            for neighbor in self.dag.graph().neighbors_directed(node, direction) {
159                if !seen.insert(neighbor) {
160                    continue;
161                }
162                let next_distance = distance + 1;
163                result.push((next_distance, self.dag.graph()[neighbor].clone()));
164                queue.push_back((neighbor, next_distance));
165            }
166        }
167        result.sort();
168        Ok(result)
169    }
170}
vissue_core/graph.rs

vissue_core/
graph.rs
