node_maintainer/
graph.rs

1use std::{
2    collections::VecDeque,
3    ffi::OsStr,
4    ops::{Index, IndexMut},
5    path::Path,
6};
7
8use indexmap::IndexMap;
9use kdl::KdlDocument;
10use nassun::{package::Package, PackageResolution, PackageSpec};
11use oro_common::CorgiManifest;
12use petgraph::stable_graph::{EdgeIndex, NodeIndex, StableGraph};
13#[cfg(not(target_arch = "wasm32"))]
14use petgraph::Direction;
15use unicase::UniCase;
16
17use crate::{error::NodeMaintainerError, Lockfile, LockfileNode};
18
19#[cfg(debug_assertions)]
20use NodeMaintainerError::GraphValidationError;
21
22#[derive(Debug, Hash, PartialEq, Eq)]
23pub(crate) struct DemotionTarget {
24    /// Index of the target ancestor node that should hold the demoted copy.
25    pub(crate) target_idx: NodeIndex,
26
27    /// Index of the dependent node
28    pub(crate) dependent_idx: NodeIndex,
29
30    /// Index of the edge between dependency and dependent
31    pub(crate) edge_idx: EdgeIndex,
32}
33
34#[derive(Debug, Clone)]
35pub struct Node {
36    /// Index of this Node inside its [`Graph`].
37    pub(crate) idx: NodeIndex,
38    /// Name this node is written to the filesystem as.
39    pub(crate) name: UniCase<String>,
40    /// Resolved [`Package`] for this Node.
41    pub(crate) package: Package,
42    /// Quick index back to this Node's [`Graph`]'s root Node.
43    pub(crate) root: NodeIndex,
44    /// Name-indexed map of outgoing [`crate::Edge`]s from this Node.
45    pub(crate) dependencies: IndexMap<UniCase<String>, EdgeIndex>,
46    /// Map of dependencies to their requirements.
47    pub(crate) dependency_reqs: IndexMap<UniCase<String>, (PackageSpec, DepType)>,
48    /// Parent, if any, of this Node in the logical filesystem hierarchy.
49    pub(crate) parent: Option<NodeIndex>,
50    /// Children of this node in the logical filesystem hierarchy. These are
51    /// not necessarily dependencies, and this Node's dependencies may not all
52    /// be in this HashMap.
53    pub(crate) children: IndexMap<UniCase<String>, NodeIndex>,
54}
55
56impl Node {
57    pub(crate) fn new(
58        name: UniCase<String>,
59        package: Package,
60        manifest: CorgiManifest,
61        is_root: bool,
62    ) -> Result<Self, NodeMaintainerError> {
63        let deps = manifest
64            .dependencies
65            .iter()
66            .map(|x| (x, DepType::Prod))
67            .chain(
68                manifest
69                    .optional_dependencies
70                    .iter()
71                    .map(|x| (x, DepType::Opt)),
72                // TODO: Place these properly.
73                // )
74                // .chain(
75                //     manifest
76                //         .peer_dependencies
77                //         .iter()
78                //         .map(|x| (x, DepType::Peer)),
79            );
80
81        let deps: Box<dyn Iterator<Item = ((&String, &String), DepType)> + Send> = if is_root {
82            Box::new(deps.chain(manifest.dev_dependencies.iter().map(|x| (x, DepType::Dev))))
83        } else {
84            Box::new(deps)
85        };
86        let mut dependency_reqs = IndexMap::new();
87        for ((name, spec), dep_type) in deps {
88            dependency_reqs.insert(
89                UniCase::new(name.clone()),
90                (format!("{name}@{spec}").parse()?, dep_type),
91            );
92        }
93        Ok(Self {
94            package,
95            name,
96            idx: NodeIndex::new(0),
97            root: NodeIndex::new(0),
98            parent: None,
99            children: IndexMap::new(),
100            dependencies: IndexMap::new(),
101            dependency_reqs,
102        })
103    }
104
105    /// This Node's depth in the logical filesystem hierarchy.
106    pub(crate) fn depth(&self, graph: &Graph) -> usize {
107        graph.node_parent_iter(self.idx).count() - 1
108    }
109}
110
111#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
112pub enum DepType {
113    Prod,
114    Dev,
115    Peer,
116    Opt,
117}
118
119#[derive(Debug, Clone, PartialEq, Eq)]
120pub struct Edge {
121    pub(crate) requested: PackageSpec,
122    pub(crate) dep_type: DepType,
123}
124
125impl Edge {
126    pub(crate) fn new(requested: PackageSpec, dep_type: DepType) -> Self {
127        Self {
128            requested,
129            dep_type,
130        }
131    }
132}
133
134#[derive(Debug, Default)]
135pub(crate) struct Graph {
136    pub(crate) root: NodeIndex,
137    pub(crate) inner: StableGraph<Node, Edge>,
138}
139
140impl Index<NodeIndex> for Graph {
141    type Output = Node;
142
143    fn index(&self, index: NodeIndex) -> &Self::Output {
144        &self.inner[index]
145    }
146}
147
148impl IndexMut<NodeIndex> for Graph {
149    fn index_mut(&mut self, index: NodeIndex) -> &mut Self::Output {
150        &mut self.inner[index]
151    }
152}
153
154impl Index<EdgeIndex> for Graph {
155    type Output = Edge;
156
157    fn index(&self, index: EdgeIndex) -> &Self::Output {
158        &self.inner[index]
159    }
160}
161
162impl IndexMut<EdgeIndex> for Graph {
163    fn index_mut(&mut self, index: EdgeIndex) -> &mut Self::Output {
164        &mut self.inner[index]
165    }
166}
167
168impl Graph {
169    #[cfg(not(target_arch = "wasm32"))]
170    pub fn is_optional(&self, node: NodeIndex) -> bool {
171        for edge_ref in self.inner.edges_directed(node, Direction::Incoming) {
172            if edge_ref.weight().dep_type != DepType::Opt {
173                return false;
174            }
175        }
176        true
177    }
178
179    pub fn resolve_dep(&self, node: NodeIndex, dep: &UniCase<String>) -> Option<NodeIndex> {
180        for parent in self.node_parent_iter(node) {
181            if let Some(resolved) = parent.children.get(dep) {
182                return Some(*resolved);
183            }
184        }
185        None
186    }
187
188    pub fn is_ancestor(&self, ancestor: NodeIndex, descendant: NodeIndex) -> bool {
189        self.node_parent_iter(descendant)
190            .any(|parent| parent.idx == ancestor)
191    }
192
193    pub fn to_lockfile(&self) -> Result<Lockfile, NodeMaintainerError> {
194        let root = self.node_lockfile_node(self.root, true)?;
195        let packages = self
196            .inner
197            .node_indices()
198            .filter(|idx| *idx != self.root)
199            .map(|idx| {
200                let node = self.node_lockfile_node(idx, false)?;
201                Ok((
202                    UniCase::from(
203                        node.path
204                            .iter()
205                            .map(|x| x.to_string())
206                            .collect::<Vec<_>>()
207                            .join("/node_modules/"),
208                    ),
209                    node,
210                ))
211            })
212            .collect::<Result<IndexMap<_, _>, NodeMaintainerError>>()?;
213        Ok(Lockfile {
214            version: 1,
215            root,
216            packages,
217        })
218    }
219
220    pub fn to_kdl(&self) -> Result<KdlDocument, NodeMaintainerError> {
221        Ok(self.to_lockfile()?.to_kdl())
222    }
223
224    pub(crate) fn node_parent_iter(&self, idx: NodeIndex) -> NodeParentIterator {
225        NodeParentIterator {
226            graph: self,
227            current: Some(idx),
228        }
229    }
230
231    pub(crate) fn node_at_path(&self, path: &Path) -> Option<&Node> {
232        let mut current = Some(self.root);
233        let mut in_nm = true;
234        let mut scope = None;
235        let slash = OsStr::new("/");
236        let backslash = OsStr::new("\\");
237        let nm = UniCase::new("node_modules".to_owned());
238        for raw_segment in path {
239            let str_segment = raw_segment.to_string_lossy().to_string();
240            let segment = UniCase::new(str_segment.clone());
241            if (segment == nm && scope.is_none())
242                || slash == raw_segment
243                || backslash == raw_segment
244            {
245                in_nm = true;
246                continue;
247            } else if let Some(curr_idx) = current {
248                if !in_nm {
249                    break;
250                } else if segment.starts_with('@') {
251                    scope = Some(segment.to_string());
252                } else if let Some(curr_scope) = scope.as_deref() {
253                    let scoped_seg = UniCase::new(format!("{curr_scope}/{segment}"));
254                    if let Some(child) = self.inner[curr_idx].children.get(&scoped_seg) {
255                        current = Some(*child);
256                    }
257                    in_nm = false;
258                    scope = None;
259                } else if let Some(child) = self.inner[curr_idx].children.get(&segment) {
260                    current = Some(*child);
261                    in_nm = false;
262                } else {
263                    break;
264                }
265            } else {
266                break;
267            }
268        }
269        if current == Some(self.root) {
270            None
271        } else {
272            current.map(|idx| &self.inner[idx])
273        }
274    }
275
276    pub(crate) fn package_at_path(&self, path: &Path) -> Option<Package> {
277        Some(self.node_at_path(path)?.package.clone())
278    }
279
280    pub(crate) fn find_by_name(
281        &self,
282        parent: NodeIndex,
283        name: &UniCase<String>,
284    ) -> Result<Option<NodeIndex>, NodeMaintainerError> {
285        Ok(self.node_parent_iter(parent).find_map(|node| {
286            if node.children.contains_key(name) {
287                Some(node.children[name])
288            } else {
289                None
290            }
291        }))
292    }
293
294    pub(crate) fn node_path(&self, node_idx: NodeIndex) -> VecDeque<UniCase<String>> {
295        let node = &self.inner[node_idx];
296        let mut path = VecDeque::new();
297        if node_idx != self.root {
298            path.push_front(node.name.clone());
299            let mut parent = node.parent;
300            while let Some(parent_idx) = parent {
301                if parent_idx == self.root {
302                    break;
303                }
304                path.push_front(self.inner[parent_idx].name.clone());
305                parent = self.inner[parent_idx].parent;
306            }
307        };
308        path
309    }
310
311    pub(crate) fn node_path_string(&self, node_idx: NodeIndex) -> String {
312        self.node_path(node_idx)
313            .iter()
314            .map(|x| x.to_string())
315            .collect::<Vec<_>>()
316            .join("/node_modules/")
317    }
318
319    /// Validate that file system hierarchy (parent -> children) is compatible
320    /// with graph edges (dependent -> dependency).
321    #[cfg(debug_assertions)]
322    pub(crate) fn validate(&self) -> Result<(), NodeMaintainerError> {
323        // Verify that all nodes in the tree are in the graph
324        let mut q = VecDeque::new();
325        q.push_back(self.root);
326        while let Some(node) = q.pop_front() {
327            if !self.inner.contains_node(node) {
328                return Err(GraphValidationError(format!(
329                    "Missing node in the graph for: {node:?}"
330                )));
331            }
332
333            q.extend(self.inner[node].children.values());
334        }
335
336        // Verify that depencies are satisfied by the logical hierarchy.
337        for dependent in self.inner.node_weights() {
338            for (dep_name, edge_idx) in &dependent.dependencies {
339                let edge = &self.inner[*edge_idx];
340
341                if let Some(dep_idx) = self.resolve_dep(dependent.idx, dep_name) {
342                    let dependency = &self.inner[dep_idx];
343
344                    if !dependency.package.resolved().satisfies(&edge.requested)? {
345                        return Err(GraphValidationError(format!(
346                            "Dependency {:?} does not satisfy requirement {} from {:?}",
347                            dependency.package.resolved(),
348                            edge.requested,
349                            dependent.package.resolved(),
350                        )));
351                    }
352                } else {
353                    return Err(GraphValidationError(format!(
354                        "Dependency {:?} {} not reachable from {:?}",
355                        dep_name,
356                        edge.requested,
357                        dependent.package.resolved(),
358                    )));
359                }
360            }
361        }
362
363        Ok(())
364    }
365
366    pub(crate) fn node_lockfile_node(
367        &self,
368        node: NodeIndex,
369        is_root: bool,
370    ) -> Result<LockfileNode, NodeMaintainerError> {
371        let path = self.node_path(node);
372        let node = &self.inner[node];
373        let resolved = match node.package.resolved() {
374            PackageResolution::Npm { tarball, .. } => tarball.to_string(),
375            PackageResolution::Dir { path, .. } => path.to_string_lossy().into(),
376            PackageResolution::Git { info, .. } => info.to_string(),
377        };
378        let version = if let PackageResolution::Npm { version, .. } = node.package.resolved() {
379            Some(version.clone())
380        } else {
381            None
382        };
383
384        let mut prod_deps = IndexMap::new();
385        let mut dev_deps = IndexMap::new();
386        let mut peer_deps = IndexMap::new();
387        let mut opt_deps = IndexMap::new();
388        let dependencies = node.dependencies.iter().map(|(name, edge_idx)| {
389            let edge = &self.inner[*edge_idx];
390            (name, &edge.requested, &edge.dep_type)
391        });
392        for (name, requested, dep_type) in dependencies {
393            use DepType::*;
394            let deps = match dep_type {
395                Prod => &mut prod_deps,
396                Dev => &mut dev_deps,
397                Peer => &mut peer_deps,
398                Opt => &mut opt_deps,
399            };
400            deps.insert(name.to_string(), requested.requested().clone());
401        }
402        Ok(LockfileNode {
403            name: UniCase::new(node.package.name().to_string()),
404            is_root,
405            path: path.into(),
406            resolved: Some(resolved),
407            version,
408            dependencies: prod_deps,
409            dev_dependencies: dev_deps,
410            peer_dependencies: peer_deps,
411            optional_dependencies: opt_deps,
412            integrity: match node.package.resolved() {
413                PackageResolution::Npm { ref integrity, .. } => integrity.clone(),
414                _ => None,
415            },
416        })
417    }
418}
419
420pub(crate) struct NodeParentIterator<'a> {
421    graph: &'a Graph,
422    current: Option<NodeIndex>,
423}
424
425impl<'a> Iterator for NodeParentIterator<'a> {
426    type Item = &'a Node;
427
428    fn next(&mut self) -> Option<Self::Item> {
429        if let Some(idx) = self.current {
430            let res = &self.graph[idx];
431            self.current = res.parent;
432            Some(res)
433        } else {
434            None
435        }
436    }
437}
node_maintainer/graph.rs

node_maintainer/
graph.rs
