vissue_core/
graph.rs

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

vissue_core/
graph.rs
