1use std::{collections::HashMap, error, fmt};
2
3use crate::{Edge, InputPath, LockFile, NodeId};
4
5#[derive(Clone, Debug, Eq, PartialEq)]
7#[non_exhaustive]
8pub enum ResolveError {
9 FollowsCycle {
11 inputs: Vec<String>,
13 },
14}
15
16impl fmt::Display for ResolveError {
17 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
18 match self {
19 Self::FollowsCycle { inputs } => {
20 write!(
21 formatter,
22 "follow cycle detected: [{}]",
23 inputs.join(" -> ")
24 )
25 }
26 }
27 }
28}
29
30impl error::Error for ResolveError {}
31
32#[derive(Clone, Debug, Eq, PartialEq)]
34#[non_exhaustive]
35pub enum ValidationError {
36 FollowsCycle {
38 inputs: Vec<String>,
40 },
41 MissingFollowsTarget {
43 input: String,
45 target: String,
47 },
48}
49
50impl fmt::Display for ValidationError {
51 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
52 match self {
53 Self::FollowsCycle { inputs } => {
54 write!(
55 formatter,
56 "follow cycle detected: [{}]",
57 inputs.join(" -> ")
58 )
59 }
60 Self::MissingFollowsTarget { input, target } => {
61 write!(
62 formatter,
63 "input '{input}' follows a non-existent input '{target}'"
64 )
65 }
66 }
67 }
68}
69
70impl error::Error for ValidationError {}
71
72type EdgeKey = (NodeId, usize);
73
74enum ResolveStep<'a, 'data> {
75 Component(&'a str),
76 FinishFollows {
77 edge: EdgeKey,
78 target: &'a InputPath<'data>,
79 },
80}
81
82pub(crate) fn resolve<'a, 'data, I>(
83 lock_file: &'a LockFile<'data>,
84 path: I,
85) -> Result<Option<NodeId>, ResolveError>
86where
87 I: IntoIterator<Item = &'a str>,
88{
89 resolve_inner(lock_file, path, None)
90}
91
92pub(crate) fn resolve_path<'a, 'data, 'path>(
93 lock_file: &'a LockFile<'data>,
94 path: &'a InputPath<'path>,
95) -> Result<Option<NodeId>, ResolveError> {
96 let mut current = lock_file.root_id();
97 for component in path.as_slice() {
98 let node = lock_file.node(current).expect("resolved node id is valid");
99 let Ok(input_index) = node
100 .inputs
101 .binary_search_by(|input| input.name.as_ref().cmp(component.as_ref()))
102 else {
103 return Ok(None);
104 };
105 match &node.inputs[input_index].edge {
106 Edge::Node(child) => current = *child,
107 Edge::Follows(_) => return resolve_inner(lock_file, path.iter(), None),
108 }
109 }
110 Ok(Some(current))
111}
112
113fn resolve_inner<'a, 'data, I>(
114 lock_file: &'a LockFile<'data>,
115 path: I,
116 mut cache: Option<&mut HashMap<&'a InputPath<'data>, Option<NodeId>>>,
117) -> Result<Option<NodeId>, ResolveError>
118where
119 I: IntoIterator<Item = &'a str>,
120{
121 let mut steps: Vec<ResolveStep<'a, 'data>> =
122 path.into_iter().map(ResolveStep::Component).collect();
123 steps.reverse();
124 let mut current = lock_file.root_id();
125 let mut active_positions = HashMap::new();
126 let mut active_follows = Vec::new();
127
128 while let Some(step) = steps.pop() {
129 match step {
130 ResolveStep::Component(component) => {
131 let node = lock_file.node(current).expect("resolved node id is valid");
132 let Ok(input_index) = node
133 .inputs
134 .binary_search_by(|input| input.name.as_ref().cmp(component))
135 else {
136 return Ok(None);
137 };
138 match &node.inputs[input_index].edge {
139 Edge::Node(child) => current = *child,
140 Edge::Follows(target) => {
141 if let Some(cached) =
142 cache.as_ref().and_then(|cache| cache.get(target)).copied()
143 {
144 let Some(resolved) = cached else {
145 return Ok(None);
146 };
147 current = resolved;
148 continue;
149 }
150
151 let edge = (current, input_index);
152 if let Some(cycle_start) = active_positions.get(&edge).copied() {
153 let mut inputs: Vec<String> = active_follows[cycle_start..]
154 .iter()
155 .map(|edge| follows_name(lock_file, *edge))
156 .collect();
157 inputs.push(follows_name(lock_file, edge));
158 return Err(ResolveError::FollowsCycle { inputs });
159 }
160 active_positions.insert(edge, active_follows.len());
161 active_follows.push(edge);
162 steps.push(ResolveStep::FinishFollows { edge, target });
163 for component in target.as_slice().iter().rev() {
164 steps.push(ResolveStep::Component(component.as_ref()));
165 }
166 current = lock_file.root_id();
167 }
168 }
169 }
170 ResolveStep::FinishFollows { edge, target } => {
171 let popped = active_follows.pop();
172 debug_assert_eq!(popped, Some(edge));
173 active_positions.remove(&edge);
174 if let Some(cache) = cache.as_deref_mut() {
175 cache.insert(target, Some(current));
176 }
177 }
178 }
179 }
180 Ok(Some(current))
181}
182
183fn follows_name(lock_file: &LockFile<'_>, (node, input): (NodeId, usize)) -> String {
184 lock_file
185 .node(node)
186 .and_then(|node| node.inputs.get(input))
187 .map(|input| input.name.to_string())
188 .unwrap_or_else(|| String::from("<invalid>"))
189}
190
191pub(crate) fn validate(lock_file: &LockFile<'_>) -> Result<(), ValidationError> {
192 let mut visited = vec![false; lock_file.node_count()];
193 let mut parents: Vec<Option<(NodeId, usize)>> = vec![None; lock_file.node_count()];
194 visited[lock_file.root_id().index()] = true;
195 let mut stack = vec![lock_file.root_id()];
196 let mut cache = HashMap::new();
197
198 while let Some(node_id) = stack.pop() {
199 let node = lock_file.node(node_id).expect("visited node id is valid");
200 for (input_index, input) in node.inputs.iter().enumerate().rev() {
201 match &input.edge {
202 Edge::Node(child) => {
203 if !std::mem::replace(&mut visited[child.index()], true) {
204 parents[child.index()] = Some((node_id, input_index));
205 stack.push(*child);
206 }
207 }
208 Edge::Follows(target) if !target.is_empty() => {
209 match resolve_inner(lock_file, target.iter(), Some(&mut cache)) {
210 Ok(Some(_)) => {}
211 Ok(None) => {
212 return Err(ValidationError::MissingFollowsTarget {
213 input: input_path(lock_file, &parents, node_id, input_index),
214 target: target.iter().collect::<Vec<_>>().join("/"),
215 });
216 }
217 Err(ResolveError::FollowsCycle { inputs }) => {
218 return Err(ValidationError::FollowsCycle { inputs });
219 }
220 }
221 }
222 Edge::Follows(_) => {}
223 }
224 }
225 }
226 Ok(())
227}
228
229fn input_path(
230 lock_file: &LockFile<'_>,
231 parents: &[Option<(NodeId, usize)>],
232 node_id: NodeId,
233 input_index: usize,
234) -> String {
235 let mut components = vec![
236 lock_file
237 .node(node_id)
238 .and_then(|node| node.inputs.get(input_index))
239 .map(|input| input.name.as_ref())
240 .unwrap_or("<invalid>"),
241 ];
242 let mut current = node_id;
243 while current != lock_file.root_id() {
244 let Some((parent, parent_input)) = parents[current.index()] else {
245 components.push("<invalid>");
246 break;
247 };
248 components.push(
249 lock_file
250 .node(parent)
251 .and_then(|node| node.inputs.get(parent_input))
252 .map(|input| input.name.as_ref())
253 .unwrap_or("<invalid>"),
254 );
255 current = parent;
256 }
257 components.reverse();
258 components.join("/")
259}