grex_core/tree/graph.rs
1//! Read-only pack graph produced by the [`crate::tree::Walker`].
2//!
3//! The graph is a value type: once the walker returns a [`PackGraph`] the
4//! structure is immutable. Callers (validators, schedulers, renderers) only
5//! ever see the already-assembled graph — they never participate in its
6//! construction. This decoupling lets us swap the walker for, say, an IPC
7//! driver or a snapshot-replay harness without touching any downstream
8//! consumer.
9//!
10//! # Ownership model
11//!
12//! * Nodes live in a `Vec`; node id == vector index.
13//! * Edges are a flat vector for cheap iteration; the few lookups we perform
14//! on a walked tree do not justify an adjacency-map yet.
15//! * The root is always at index `0` by construction.
16//!
17//! # Non-goals
18//!
19//! * No mutation API. The graph cannot grow or shrink after walker exit.
20//! * No topological sort here — that belongs to the scheduler slice.
21//! * No serialisation — persistence is a later slice.
22
23use std::path::PathBuf;
24
25use crate::pack::PackManifest;
26
27/// Node-edge relationship kind.
28///
29/// `Child` edges are *owned*: the walker cloned the target repo and recursed
30/// into it. `DependsOn` edges are *referential*: the walker recorded that the
31/// parent named this dep but did not hydrate it — resolution happens at
32/// validate time via `DependsOnValidator`.
33///
34/// Marked `#[non_exhaustive]` so new edge relations (e.g. `Provides`,
35/// `Conflicts`) can land without breaking external match sites.
36#[non_exhaustive]
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub enum EdgeKind {
39 /// Parent owns/walks this child (cloned + recursed).
40 Child,
41 /// Parent merely references this pack by name or url.
42 DependsOn,
43}
44
45/// A pack in the walked graph.
46///
47/// Every field is `pub` by design: the graph is a read-only value type, and
48/// exposing the full record here is simpler than hand-curating accessors for
49/// each field.
50///
51/// Marked `#[non_exhaustive]` so audit fields (resolved ref SHA, hydration
52/// timestamps) can land without breaking library consumers who destructure
53/// the struct.
54#[non_exhaustive]
55#[derive(Debug, Clone)]
56pub struct PackNode {
57 /// Stable index inside the graph (equal to the `Vec` position).
58 pub id: usize,
59 /// `name` copied from the pack manifest for O(1) lookup.
60 pub name: String,
61 /// On-disk location of the pack's working tree.
62 pub path: PathBuf,
63 /// Source URL the walker used to hydrate this node, or `None` for the
64 /// root / nodes that were loaded directly from an on-disk path.
65 pub source_url: Option<String>,
66 /// Full parsed manifest.
67 pub manifest: PackManifest,
68 /// Parent id; `None` for the root.
69 pub parent: Option<usize>,
70 /// Resolved commit SHA of the pack's working tree, when the walker
71 /// could obtain one. `None` for the root (local path, no clone step)
72 /// or when `head_sha` probing fails. Mixed into
73 /// [`crate::lockfile::compute_actions_hash`] so ref drift invalidates
74 /// the skip-on-hash short-circuit (M4-D spec §M4 req 4a).
75 pub commit_sha: Option<String>,
76}
77
78/// An edge in the walked graph.
79///
80/// Marked `#[non_exhaustive]` so future edge-level metadata (priority,
81/// guard expression) is non-breaking for library consumers.
82#[non_exhaustive]
83#[derive(Debug, Clone)]
84pub struct PackEdge {
85 /// Origin node id.
86 pub from: usize,
87 /// Target node id.
88 pub to: usize,
89 /// Relationship kind.
90 pub kind: EdgeKind,
91}
92
93/// Fully-walked pack graph. Immutable post-construction.
94///
95/// Nodes are owned; callers borrow via [`PackGraph::nodes`] or the dedicated
96/// lookup helpers.
97#[derive(Debug)]
98pub struct PackGraph {
99 nodes: Vec<PackNode>,
100 edges: Vec<PackEdge>,
101}
102
103impl PackGraph {
104 /// Construct a graph from raw node and edge vectors.
105 ///
106 /// Pub-crate visibility keeps mutation ownership with the walker while
107 /// allowing an empty graph or a manually-assembled fixture inside tests
108 /// (via `pub(crate)` helpers invoked from the integration test harness).
109 ///
110 /// # Panics
111 ///
112 /// Panics if `nodes` is empty — a walk always produces at least the
113 /// root. This is a programming-error guard rather than a user-facing
114 /// failure mode.
115 #[must_use]
116 pub(crate) fn new(nodes: Vec<PackNode>, edges: Vec<PackEdge>) -> Self {
117 assert!(!nodes.is_empty(), "PackGraph must contain at least the root node");
118 Self { nodes, edges }
119 }
120
121 /// The root node (id == 0).
122 #[must_use]
123 pub fn root(&self) -> &PackNode {
124 &self.nodes[0]
125 }
126
127 /// All nodes in insertion order.
128 #[must_use]
129 pub fn nodes(&self) -> &[PackNode] {
130 &self.nodes
131 }
132
133 /// All edges in insertion order.
134 #[must_use]
135 pub fn edges(&self) -> &[PackEdge] {
136 &self.edges
137 }
138
139 /// Iterate the `Child`-kind neighbours of `id` (in insertion order).
140 pub fn children_of(&self, id: usize) -> impl Iterator<Item = &PackNode> {
141 self.neighbours(id, EdgeKind::Child)
142 }
143
144 /// Iterate the `DependsOn`-kind neighbours of `id`.
145 pub fn depends_on_of(&self, id: usize) -> impl Iterator<Item = &PackNode> {
146 self.neighbours(id, EdgeKind::DependsOn)
147 }
148
149 /// Find a node by its manifest name. Returns the first match in
150 /// insertion order; names are not guaranteed unique across a graph,
151 /// though per-pack validators may reject duplicates in future slices.
152 #[must_use]
153 pub fn find_by_name(&self, name: &str) -> Option<&PackNode> {
154 self.nodes.iter().find(|n| n.name == name)
155 }
156
157 /// Borrow a node by id.
158 #[must_use]
159 pub fn node(&self, id: usize) -> Option<&PackNode> {
160 self.nodes.get(id)
161 }
162
163 fn neighbours(&self, id: usize, kind: EdgeKind) -> impl Iterator<Item = &PackNode> {
164 self.edges
165 .iter()
166 .filter(move |e| e.from == id && e.kind == kind)
167 .filter_map(|e| self.nodes.get(e.to))
168 }
169}