nargo_resolver/
graph.rs

1//! Dependency graph data structures and algorithms.
2
3use nargo_types::{Error, Result};
4use petgraph::{
5    algo::{is_cyclic_directed, toposort},
6    graph::{DiGraph, NodeIndex},
7    visit::EdgeRef,
8    Direction,
9};
10use serde::{Deserialize, Serialize};
11use std::collections::{HashMap, HashSet};
12
13/// Represents the source of a package.
14#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
15pub enum PackageSource {
16    /// Package from npm registry.
17    Registry {
18        /// Registry URL (default: https://registry.npmjs.org).
19        registry: String,
20    },
21    /// Package from Git repository.
22    Git {
23        /// Git repository URL.
24        url: String,
25        /// Git reference (branch, tag, or commit).
26        reference: Option<String>,
27    },
28    /// Package from local path.
29    Path {
30        /// Local file system path.
31        path: String,
32    },
33    /// Package from GitHub shorthand.
34    Github {
35        /// GitHub repository (owner/repo).
36        repo: String,
37        /// Git reference (branch, tag, or commit).
38        reference: Option<String>,
39    },
40    /// Package from workspace.
41    Workspace,
42}
43
44impl Default for PackageSource {
45    fn default() -> Self {
46        PackageSource::Registry { registry: "https://registry.npmjs.org".to_string() }
47    }
48}
49
50/// Represents a node in the dependency graph.
51#[derive(Debug, Clone, Serialize, Deserialize)]
52pub struct DependencyNode {
53    /// Package name.
54    pub name: String,
55    /// Resolved version.
56    pub version: String,
57    /// Package source.
58    pub source: PackageSource,
59    /// Whether this is a dev dependency.
60    pub is_dev: bool,
61    /// Whether this is an optional dependency.
62    pub is_optional: bool,
63    /// Features enabled for this package.
64    pub features: Vec<String>,
65}
66
67impl DependencyNode {
68    /// Creates a new dependency node.
69    pub fn new(name: impl Into<String>, version: impl Into<String>) -> Self {
70        Self { name: name.into(), version: version.into(), source: PackageSource::default(), is_dev: false, is_optional: false, features: Vec::new() }
71    }
72
73    /// Sets the package source.
74    pub fn with_source(mut self, source: PackageSource) -> Self {
75        self.source = source;
76        self
77    }
78
79    /// Marks this as a dev dependency.
80    pub fn as_dev(mut self, is_dev: bool) -> Self {
81        self.is_dev = is_dev;
82        self
83    }
84
85    /// Marks this as a dev dependency (sets to true).
86    pub fn set_dev(mut self) -> Self {
87        self.is_dev = true;
88        self
89    }
90
91    /// Marks this as an optional dependency.
92    pub fn as_optional(mut self) -> Self {
93        self.is_optional = true;
94        self
95    }
96
97    /// Sets the enabled features.
98    pub fn with_features(mut self, features: Vec<String>) -> Self {
99        self.features = features;
100        self
101    }
102
103    /// Returns a unique key for this node.
104    pub fn key(&self) -> String {
105        format!("{}@{}", self.name, self.version)
106    }
107}
108
109/// Represents an edge in the dependency graph.
110#[derive(Debug, Clone, Serialize, Deserialize)]
111pub struct DependencyEdge {
112    /// Version constraint from the dependent.
113    pub constraint: String,
114    /// Whether this is a peer dependency relationship.
115    pub is_peer: bool,
116}
117
118impl DependencyEdge {
119    /// Creates a new dependency edge.
120    pub fn new(constraint: impl Into<String>) -> Self {
121        Self { constraint: constraint.into(), is_peer: false }
122    }
123
124    /// Marks this as a peer dependency edge.
125    pub fn as_peer(mut self) -> Self {
126        self.is_peer = true;
127        self
128    }
129}
130
131/// The dependency graph structure.
132#[derive(Debug, Default, Clone)]
133pub struct DependencyGraph {
134    /// The underlying directed graph.
135    graph: DiGraph<DependencyNode, DependencyEdge>,
136    /// Map from package name to node index.
137    name_to_index: HashMap<String, NodeIndex>,
138    /// Map from (name, version) to node index.
139    key_to_index: HashMap<String, NodeIndex>,
140}
141
142impl DependencyGraph {
143    /// Creates a new empty dependency graph.
144    pub fn new() -> Self {
145        Self { graph: DiGraph::new(), name_to_index: HashMap::new(), key_to_index: HashMap::new() }
146    }
147
148    /// Adds a node to the graph.
149    pub fn add_node(&mut self, node: DependencyNode) -> NodeIndex {
150        let key = node.key();
151        let name = node.name.clone();
152        let idx = self.graph.add_node(node);
153        self.name_to_index.insert(name, idx);
154        self.key_to_index.insert(key, idx);
155        idx
156    }
157
158    /// Adds an edge between two nodes.
159    pub fn add_edge(&mut self, from: NodeIndex, to: NodeIndex, edge: DependencyEdge) {
160        self.graph.add_edge(from, to, edge);
161    }
162
163    /// Gets a node by name.
164    pub fn get_node_by_name(&self, name: &str) -> Option<&DependencyNode> {
165        self.name_to_index.get(name).map(|idx| &self.graph[*idx])
166    }
167
168    /// Gets a node by key (name@version).
169    pub fn get_node_by_key(&self, key: &str) -> Option<&DependencyNode> {
170        self.key_to_index.get(key).map(|idx| &self.graph[*idx])
171    }
172
173    /// Gets a node by its index.
174    pub fn get_node(&self, idx: NodeIndex) -> Option<&DependencyNode> {
175        self.graph.node_weight(idx)
176    }
177
178    /// Returns all nodes in the graph.
179    pub fn nodes(&self) -> impl Iterator<Item = &DependencyNode> {
180        self.graph.node_weights()
181    }
182
183    /// Returns the number of nodes.
184    pub fn node_count(&self) -> usize {
185        self.graph.node_count()
186    }
187
188    /// Returns the number of edges.
189    pub fn edge_count(&self) -> usize {
190        self.graph.edge_count()
191    }
192
193    /// Checks if the graph has cycles.
194    pub fn has_cycle(&self) -> bool {
195        is_cyclic_directed(&self.graph)
196    }
197
198    /// Detects cycles and returns the cycle path if found.
199    pub fn detect_cycle(&self) -> Option<Vec<String>> {
200        if !self.has_cycle() {
201            return None;
202        }
203
204        let mut visited = HashSet::new();
205        let mut path = Vec::new();
206        let mut result = None;
207
208        for node_idx in self.graph.node_indices() {
209            if result.is_some() {
210                break;
211            }
212            self.dfs_cycle(node_idx, &mut visited, &mut path, &mut result);
213        }
214
215        result
216    }
217
218    fn dfs_cycle(&self, node: NodeIndex, visited: &mut HashSet<NodeIndex>, path: &mut Vec<NodeIndex>, result: &mut Option<Vec<String>>) {
219        if result.is_some() {
220            return;
221        }
222
223        if path.contains(&node) {
224            let cycle_start = path.iter().position(|&n| n == node).unwrap();
225            let cycle: Vec<String> = path[cycle_start..].iter().chain(std::iter::once(&node)).map(|&idx| self.graph[idx].key()).collect();
226            *result = Some(cycle);
227            return;
228        }
229
230        if visited.contains(&node) {
231            return;
232        }
233
234        visited.insert(node);
235        path.push(node);
236
237        for neighbor in self.graph.neighbors_directed(node, Direction::Outgoing) {
238            self.dfs_cycle(neighbor, visited, path, result);
239        }
240
241        path.pop();
242    }
243
244    /// Performs topological sort and returns nodes in order.
245    pub fn topological_sort(&self) -> Result<Vec<DependencyNode>> {
246        if self.has_cycle() {
247            let cycle = self.detect_cycle();
248            let msg = if let Some(cycle) = cycle { format!("Circular dependency detected: {}", cycle.join(" -> ")) } else { "Circular dependency detected".to_string() };
249            return Err(Error::external_error("resolver".to_string(), msg, nargo_types::Span::unknown()));
250        }
251
252        let sorted: Vec<NodeIndex> = toposort(&self.graph, None).map_err(|e| Error::external_error("resolver".to_string(), format!("Topological sort failed: {:?}", e), nargo_types::Span::unknown()))?;
253
254        Ok(sorted.into_iter().filter_map(|idx| self.graph.node_weight(idx).cloned()).collect())
255    }
256
257    /// Returns all dependencies of a node.
258    pub fn dependencies_of(&self, node_idx: NodeIndex) -> Vec<(&DependencyNode, &DependencyEdge)> {
259        self.graph
260            .edges_directed(node_idx, Direction::Outgoing)
261            .filter_map(|edge| {
262                let target = edge.target();
263                self.graph.node_weight(target).map(|node| (node, edge.weight()))
264            })
265            .collect()
266    }
267
268    /// Returns all dependents of a node (reverse dependencies).
269    pub fn dependents_of(&self, node_idx: NodeIndex) -> Vec<(&DependencyNode, &DependencyEdge)> {
270        self.graph
271            .edges_directed(node_idx, Direction::Incoming)
272            .filter_map(|edge| {
273                let source = edge.source();
274                self.graph.node_weight(source).map(|node| (node, edge.weight()))
275            })
276            .collect()
277    }
278
279    /// Returns the node index for a given name.
280    pub fn node_index(&self, name: &str) -> Option<NodeIndex> {
281        self.name_to_index.get(name).copied()
282    }
283}
nargo_resolver/graph.rs

nargo_resolver/
graph.rs
