Skip to main content

nix_flake_lock/
model.rs

1use std::borrow::Cow;
2
3use crate::{Change, Error, Limits, ResolveError, ValidationError};
4
5/// An index into a lock file's compact node arena.
6#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
7pub struct NodeId(pub(crate) u32);
8
9impl NodeId {
10    /// Return the zero-based arena index.
11    pub const fn index(self) -> usize {
12        self.0 as usize
13    }
14}
15
16/// A fetcher attribute value. Nix restricts these values to this flat set.
17#[derive(Clone, Debug, Eq, PartialEq)]
18pub enum AttrValue<'a> {
19    /// A UTF-8 string, borrowed from the input when it did not require JSON
20    /// unescaping.
21    String(Cow<'a, str>),
22    /// An unsigned integer.
23    Integer(u64),
24    /// A Boolean.
25    Bool(bool),
26}
27
28impl AttrValue<'_> {
29    /// Return the string value, or `None` for another variant.
30    pub fn as_str(&self) -> Option<&str> {
31        match self {
32            Self::String(value) => Some(value),
33            _ => None,
34        }
35    }
36
37    /// Return the unsigned integer value, or `None` for another variant.
38    pub const fn as_u64(&self) -> Option<u64> {
39        match self {
40            Self::Integer(value) => Some(*value),
41            _ => None,
42        }
43    }
44
45    /// Return the Boolean value, or `None` for another variant.
46    pub const fn as_bool(&self) -> Option<bool> {
47        match self {
48            Self::Bool(value) => Some(*value),
49            _ => None,
50        }
51    }
52
53    pub(crate) fn into_owned(self) -> AttrValue<'static> {
54        match self {
55            Self::String(value) => AttrValue::String(Cow::Owned(value.into_owned())),
56            Self::Integer(value) => AttrValue::Integer(value),
57            Self::Bool(value) => AttrValue::Bool(value),
58        }
59    }
60}
61
62/// One name-value pair from a fetcher attribute set.
63#[derive(Clone, Debug, Eq, PartialEq)]
64pub struct Attr<'a> {
65    pub(crate) name: Cow<'a, str>,
66    pub(crate) value: AttrValue<'a>,
67}
68
69impl<'a> Attr<'a> {
70    /// Return the attribute name.
71    pub fn name(&self) -> &str {
72        self.name.as_ref()
73    }
74
75    /// Return the attribute value.
76    pub const fn value(&self) -> &AttrValue<'a> {
77        &self.value
78    }
79}
80
81/// A sorted flat fetcher attribute map.
82#[derive(Clone, Debug, Default, Eq, PartialEq)]
83pub struct AttrSet<'a> {
84    pub(crate) entries: Vec<Attr<'a>>,
85}
86
87impl<'a> AttrSet<'a> {
88    /// Iterate over attributes in lexicographic name order.
89    pub fn iter(&self) -> impl ExactSizeIterator<Item = &Attr<'a>> {
90        self.entries.iter()
91    }
92
93    /// Return the number of attributes.
94    pub fn len(&self) -> usize {
95        self.entries.len()
96    }
97
98    /// Return whether the set contains no attributes.
99    pub fn is_empty(&self) -> bool {
100        self.entries.is_empty()
101    }
102
103    /// Look up an attribute by name.
104    pub fn get(&self, name: &str) -> Option<&AttrValue<'a>> {
105        self.entries
106            .binary_search_by(|entry| entry.name.as_ref().cmp(name))
107            .ok()
108            .map(|index| &self.entries[index].value)
109    }
110
111    /// Look up a string attribute by name.
112    pub fn get_str(&self, name: &str) -> Option<&str> {
113        self.get(name).and_then(AttrValue::as_str)
114    }
115
116    /// Look up an unsigned integer attribute by name.
117    pub fn get_u64(&self, name: &str) -> Option<u64> {
118        self.get(name).and_then(AttrValue::as_u64)
119    }
120
121    /// Look up a Boolean attribute by name.
122    pub fn get_bool(&self, name: &str) -> Option<bool> {
123        self.get(name).and_then(AttrValue::as_bool)
124    }
125
126    pub(crate) fn from_entries(entries: Vec<Attr<'a>>) -> Self {
127        Self { entries }
128    }
129
130    pub(crate) fn overlay(&mut self, newer: Self) {
131        let old = std::mem::take(&mut self.entries);
132        let mut old = old.into_iter().peekable();
133        let mut newer = newer.entries.into_iter().peekable();
134        let mut merged = Vec::with_capacity(old.len().saturating_add(newer.len()));
135
136        loop {
137            match (old.peek(), newer.peek()) {
138                (Some(left), Some(right)) => match left.name.cmp(&right.name) {
139                    std::cmp::Ordering::Less => {
140                        merged.push(old.next().expect("peeked old attribute"));
141                    }
142                    std::cmp::Ordering::Equal => {
143                        old.next();
144                        merged.push(newer.next().expect("peeked new attribute"));
145                    }
146                    std::cmp::Ordering::Greater => {
147                        merged.push(newer.next().expect("peeked new attribute"));
148                    }
149                },
150                (Some(_), None) => {
151                    merged.extend(old);
152                    break;
153                }
154                (None, Some(_)) => {
155                    merged.extend(newer);
156                    break;
157                }
158                (None, None) => break,
159            }
160        }
161        self.entries = merged;
162    }
163
164    pub(crate) fn into_owned(self) -> AttrSet<'static> {
165        AttrSet {
166            entries: self
167                .entries
168                .into_iter()
169                .map(|entry| Attr {
170                    name: Cow::Owned(entry.name.into_owned()),
171                    value: entry.value.into_owned(),
172                })
173                .collect(),
174        }
175    }
176}
177
178/// A path of input names, used by `follows` edges and graph lookup.
179#[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
180pub struct InputPath<'a>(pub(crate) Vec<Cow<'a, str>>);
181
182impl<'a> InputPath<'a> {
183    /// Construct a path from borrowed or owned components.
184    pub fn new<I, S>(components: I) -> Self
185    where
186        I: IntoIterator<Item = S>,
187        S: Into<Cow<'a, str>>,
188    {
189        Self(components.into_iter().map(Into::into).collect())
190    }
191
192    /// Iterate over path components.
193    pub fn iter(&self) -> impl ExactSizeIterator<Item = &str> {
194        self.0.iter().map(AsRef::as_ref)
195    }
196
197    /// Return the number of path components.
198    pub fn len(&self) -> usize {
199        self.0.len()
200    }
201
202    /// Return whether the path contains no components.
203    pub fn is_empty(&self) -> bool {
204        self.0.is_empty()
205    }
206
207    /// Return the underlying components.
208    pub fn as_slice(&self) -> &[Cow<'a, str>] {
209        &self.0
210    }
211
212    pub(crate) fn into_owned(self) -> InputPath<'static> {
213        InputPath(
214            self.0
215                .into_iter()
216                .map(|component| Cow::Owned(component.into_owned()))
217                .collect(),
218        )
219    }
220}
221
222/// An outgoing edge from a lock-file node.
223#[derive(Clone, Debug, Eq, PartialEq)]
224pub enum Edge<'a> {
225    /// A direct edge to another node in the same lock file.
226    Node(NodeId),
227    /// An edge following an input path from the root node.
228    Follows(InputPath<'a>),
229}
230
231/// A named outgoing edge from a node.
232#[derive(Clone, Debug, Eq, PartialEq)]
233pub struct Input<'a> {
234    pub(crate) name: Cow<'a, str>,
235    pub(crate) edge: Edge<'a>,
236}
237
238impl<'a> Input<'a> {
239    /// Return the input name.
240    pub fn name(&self) -> &str {
241        self.name.as_ref()
242    }
243
244    /// Return the input edge.
245    pub const fn edge(&self) -> &Edge<'a> {
246        &self.edge
247    }
248}
249
250/// The lock metadata associated with a non-root node.
251#[derive(Clone, Debug, Eq, PartialEq)]
252pub struct LockedNode<'a> {
253    pub(crate) original: AttrSet<'a>,
254    pub(crate) locked: AttrSet<'a>,
255    pub(crate) is_flake: bool,
256    pub(crate) parent: Option<InputPath<'a>>,
257}
258
259impl<'a> LockedNode<'a> {
260    /// Return the original, unlocked fetcher attributes.
261    pub const fn original(&self) -> &AttrSet<'a> {
262        &self.original
263    }
264
265    /// Return the resolved, locked fetcher attributes.
266    pub const fn locked(&self) -> &AttrSet<'a> {
267        &self.locked
268    }
269
270    /// Return whether this input is itself a flake.
271    pub const fn is_flake(&self) -> bool {
272        self.is_flake
273    }
274
275    /// Return the parent path used to interpret relative source paths.
276    pub const fn parent(&self) -> Option<&InputPath<'a>> {
277        self.parent.as_ref()
278    }
279
280    /// Return the locked input's `type` attribute.
281    pub fn input_type(&self) -> Option<&str> {
282        self.locked.get_str("type")
283    }
284
285    /// Return the locked input's `rev` attribute.
286    pub fn revision(&self) -> Option<&str> {
287        self.locked.get_str("rev")
288    }
289
290    /// Return the locked input's `narHash` attribute.
291    pub fn nar_hash(&self) -> Option<&str> {
292        self.locked.get_str("narHash")
293    }
294
295    /// Return the locked input's `lastModified` attribute.
296    pub fn last_modified(&self) -> Option<u64> {
297        self.locked.get_u64("lastModified")
298    }
299}
300
301/// The root or locked-node-specific portion of a node.
302#[derive(Clone, Debug, Eq, PartialEq)]
303pub enum NodeKind<'a> {
304    /// The synthetic root node.
305    Root,
306    /// A resolved non-root input.
307    Locked(LockedNode<'a>),
308}
309
310/// A node in the compact lock-file graph.
311#[derive(Clone, Debug, Eq, PartialEq)]
312pub struct Node<'a> {
313    pub(crate) wire_key: Cow<'a, str>,
314    pub(crate) inputs: Vec<Input<'a>>,
315    pub(crate) kind: NodeKind<'a>,
316}
317
318impl<'a> Node<'a> {
319    /// Return the node key found in the source document.
320    ///
321    /// Node keys are serialization details rather than graph identity. The
322    /// canonical writer may assign a different key.
323    pub fn source_key(&self) -> &str {
324        self.wire_key.as_ref()
325    }
326
327    /// Return outgoing inputs in lexicographic name order.
328    pub fn inputs(&self) -> &[Input<'a>] {
329        &self.inputs
330    }
331
332    /// Return whether this is the root or a locked node.
333    pub const fn kind(&self) -> &NodeKind<'a> {
334        &self.kind
335    }
336
337    /// Look up an input by name.
338    pub fn input(&self, name: &str) -> Option<&Input<'a>> {
339        self.inputs
340            .binary_search_by(|input| input.name.as_ref().cmp(name))
341            .ok()
342            .map(|index| &self.inputs[index])
343    }
344
345    /// Return lock metadata for a non-root node.
346    pub fn locked(&self) -> Option<&LockedNode<'a>> {
347        match &self.kind {
348            NodeKind::Root => None,
349            NodeKind::Locked(node) => Some(node),
350        }
351    }
352}
353
354/// A parsed Nix flake lock file.
355///
356/// Unescaped strings borrow from the input. Call [`LockFile::into_owned`] when
357/// the value must outlive the input buffer. The graph is intentionally
358/// read-only; serialization always emits Nix's canonical version 7 form.
359#[derive(Clone, Debug)]
360pub struct LockFile<'a> {
361    pub(crate) source_version: u8,
362    pub(crate) root: NodeId,
363    pub(crate) nodes: Vec<Node<'a>>,
364}
365
366impl<'a> LockFile<'a> {
367    /// Parse a version 5, 6, or 7 lock file using default resource limits.
368    pub fn parse(bytes: &'a [u8]) -> Result<Self, Error> {
369        Self::parse_with_limits(bytes, Limits::default())
370    }
371
372    /// Parse a lock file using caller-supplied resource limits.
373    pub fn parse_with_limits(bytes: &'a [u8], limits: Limits) -> Result<Self, Error> {
374        crate::parse::parse(bytes, limits)
375    }
376
377    /// Return the version found in the source document.
378    ///
379    /// Canonical serialization always writes version 7.
380    pub const fn source_version(&self) -> u8 {
381        self.source_version
382    }
383
384    /// Return the root node identifier.
385    pub const fn root_id(&self) -> NodeId {
386        self.root
387    }
388
389    /// Return the root node.
390    pub fn root(&self) -> &Node<'a> {
391        &self.nodes[self.root.index()]
392    }
393
394    /// Look up a node by identifier.
395    ///
396    /// A [`NodeId`] is meaningful only for the `LockFile` that produced it.
397    pub fn node(&self, id: NodeId) -> Option<&Node<'a>> {
398        self.nodes.get(id.index())
399    }
400
401    /// Iterate over all reachable nodes in arena order.
402    pub fn nodes(&self) -> impl ExactSizeIterator<Item = (NodeId, &Node<'a>)> {
403        self.nodes
404            .iter()
405            .enumerate()
406            .map(|(index, node)| (NodeId(index as u32), node))
407    }
408
409    /// Return the number of reachable nodes, including the root.
410    pub fn node_count(&self) -> usize {
411        self.nodes.len()
412    }
413
414    /// Resolve an input path from the root node.
415    ///
416    /// Returns `Ok(None)` when a component does not exist.
417    pub fn resolve<'p, I>(&'p self, path: I) -> Result<Option<NodeId>, ResolveError>
418    where
419        I: IntoIterator<Item = &'p str>,
420    {
421        crate::validate::resolve(self, path)
422    }
423
424    /// Resolve a parsed input path from the root node.
425    ///
426    /// This avoids the temporary path collection required by [`Self::resolve`].
427    pub fn resolve_path(&self, path: &InputPath<'_>) -> Result<Option<NodeId>, ResolveError> {
428        crate::validate::resolve_path(self, path)
429    }
430
431    /// Validate all `follows` edges in the reachable graph.
432    ///
433    /// This checks for missing targets and `follows` cycles. It does not fetch
434    /// inputs or apply fetcher-specific validity rules.
435    pub fn validate(&self) -> Result<(), ValidationError> {
436        crate::validate::validate(self)
437    }
438
439    /// Return semantic input changes between this lock file and `newer`.
440    pub fn changes<'b>(&self, newer: &LockFile<'b>) -> Vec<Change> {
441        crate::diff::diff(self, newer)
442    }
443
444    /// Return whether two rooted graphs have the same semantic lock content.
445    ///
446    /// Source versions, source node keys, arena order, and string ownership do
447    /// not affect semantic equality. Node sharing and cycles are preserved.
448    pub fn semantically_eq(&self, other: &LockFile<'_>) -> bool {
449        if self.node_count() != other.node_count() {
450            return false;
451        }
452        let mut left_to_right = vec![None; self.node_count()];
453        let mut right_to_left = vec![None; other.node_count()];
454        let mut stack = vec![(self.root_id(), other.root_id())];
455
456        while let Some((left_id, right_id)) = stack.pop() {
457            if let Some(mapped) = left_to_right[left_id.index()] {
458                if mapped != right_id {
459                    return false;
460                }
461                continue;
462            }
463            if right_to_left[right_id.index()].is_some() {
464                return false;
465            }
466            left_to_right[left_id.index()] = Some(right_id);
467            right_to_left[right_id.index()] = Some(left_id);
468
469            let left = self.node(left_id).expect("semantic node id is valid");
470            let right = other.node(right_id).expect("semantic node id is valid");
471            if !node_kind_eq(&left.kind, &right.kind) || left.inputs.len() != right.inputs.len() {
472                return false;
473            }
474            for (left_input, right_input) in left.inputs.iter().zip(&right.inputs) {
475                if left_input.name != right_input.name {
476                    return false;
477                }
478                match (&left_input.edge, &right_input.edge) {
479                    (Edge::Node(left), Edge::Node(right)) => stack.push((*left, *right)),
480                    (Edge::Follows(left), Edge::Follows(right)) if left.iter().eq(right.iter()) => {
481                    }
482                    _ => return false,
483                }
484            }
485        }
486        true
487    }
488
489    /// Append Nix-compatible, two-space-indented version 7 JSON to `output`.
490    /// The emitted document includes the trailing newline used for `flake.lock`.
491    pub fn write_nix(&self, output: &mut Vec<u8>) {
492        crate::write::write_nix(self, output);
493    }
494
495    /// Serialize to newly allocated Nix-compatible version 7 JSON bytes.
496    pub fn to_nix_bytes(&self) -> Vec<u8> {
497        let mut output = Vec::with_capacity(self.nodes.len().saturating_mul(256));
498        self.write_nix(&mut output);
499        output
500    }
501
502    /// Convert all borrowed strings into owned strings.
503    pub fn into_owned(self) -> LockFile<'static> {
504        LockFile {
505            source_version: self.source_version,
506            root: self.root,
507            nodes: self
508                .nodes
509                .into_iter()
510                .map(|node| Node {
511                    wire_key: Cow::Owned(node.wire_key.into_owned()),
512                    inputs: node
513                        .inputs
514                        .into_iter()
515                        .map(|input| Input {
516                            name: Cow::Owned(input.name.into_owned()),
517                            edge: match input.edge {
518                                Edge::Node(id) => Edge::Node(id),
519                                Edge::Follows(path) => Edge::Follows(path.into_owned()),
520                            },
521                        })
522                        .collect(),
523                    kind: match node.kind {
524                        NodeKind::Root => NodeKind::Root,
525                        NodeKind::Locked(locked) => NodeKind::Locked(LockedNode {
526                            original: locked.original.into_owned(),
527                            locked: locked.locked.into_owned(),
528                            is_flake: locked.is_flake,
529                            parent: locked.parent.map(InputPath::into_owned),
530                        }),
531                    },
532                })
533                .collect(),
534        }
535    }
536}
537
538impl<'a, 'b> PartialEq<LockFile<'b>> for LockFile<'a> {
539    fn eq(&self, other: &LockFile<'b>) -> bool {
540        self.semantically_eq(other)
541    }
542}
543
544impl Eq for LockFile<'_> {}
545
546/// An owned lock file that does not borrow its input buffer.
547pub type OwnedLockFile = LockFile<'static>;
548
549fn node_kind_eq(left: &NodeKind<'_>, right: &NodeKind<'_>) -> bool {
550    match (left, right) {
551        (NodeKind::Root, NodeKind::Root) => true,
552        (NodeKind::Locked(left), NodeKind::Locked(right)) => {
553            attrs_eq(&left.original, &right.original)
554                && attrs_eq(&left.locked, &right.locked)
555                && left.is_flake == right.is_flake
556                && match (&left.parent, &right.parent) {
557                    (Some(left), Some(right)) => left.iter().eq(right.iter()),
558                    (None, None) => true,
559                    _ => false,
560                }
561        }
562        _ => false,
563    }
564}
565
566fn attrs_eq(left: &AttrSet<'_>, right: &AttrSet<'_>) -> bool {
567    let left_len = left.iter().filter(|attr| attr.name != "__final").count();
568    let right_len = right.iter().filter(|attr| attr.name != "__final").count();
569    left_len == right_len
570        && left
571            .iter()
572            .filter(|attr| attr.name != "__final")
573            .zip(right.iter().filter(|attr| attr.name != "__final"))
574            .all(|(left, right)| {
575                left.name == right.name && attr_value_eq(&left.value, &right.value)
576            })
577}
578
579fn attr_value_eq(left: &AttrValue<'_>, right: &AttrValue<'_>) -> bool {
580    match (left, right) {
581        (AttrValue::String(left), AttrValue::String(right)) => left == right,
582        (AttrValue::Integer(left), AttrValue::Integer(right)) => left == right,
583        (AttrValue::Bool(left), AttrValue::Bool(right)) => left == right,
584        _ => false,
585    }
586}