Skip to main content

nix_flake_lock/
validate.rs

1use std::{collections::HashMap, error, fmt};
2
3use crate::{Edge, InputPath, LockFile, NodeId};
4
5/// An error encountered while resolving an input path.
6#[derive(Clone, Debug, Eq, PartialEq)]
7#[non_exhaustive]
8pub enum ResolveError {
9    /// A chain of `follows` edges returned to an active edge.
10    FollowsCycle {
11        /// The input names participating in the cycle.
12        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/// A graph-integrity error found by [`LockFile::validate`].
33#[derive(Clone, Debug, Eq, PartialEq)]
34#[non_exhaustive]
35pub enum ValidationError {
36    /// A chain of `follows` edges returned to an active edge.
37    FollowsCycle {
38        /// The input names participating in the cycle.
39        inputs: Vec<String>,
40    },
41    /// A `follows` edge points to a path that does not exist.
42    MissingFollowsTarget {
43        /// The root-relative path of the input containing the edge.
44        input: String,
45        /// The missing root-relative target path.
46        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}