Skip to main content

nix_flake_lock/
parse.rs

1use std::{borrow::Cow, error, fmt, str};
2
3use memchr::memchr2;
4
5use crate::{
6    Attr, AttrSet, AttrValue, Edge, Input, InputPath, LockFile, LockedNode, Node, NodeId, NodeKind,
7};
8
9/// Resource limits applied while parsing untrusted lock files.
10#[derive(Clone, Copy, Debug, Eq, PartialEq)]
11pub struct Limits {
12    max_bytes: usize,
13    max_nodes: usize,
14    max_depth: usize,
15    max_path_components: usize,
16}
17
18impl Limits {
19    /// Construct the default limits.
20    pub const fn new() -> Self {
21        Self {
22            max_bytes: 16 * 1024 * 1024,
23            max_nodes: 1_000_000,
24            max_depth: 256,
25            max_path_components: 65_536,
26        }
27    }
28
29    /// Return the maximum accepted input size in bytes.
30    pub const fn max_bytes(self) -> usize {
31        self.max_bytes
32    }
33
34    /// Set the maximum accepted input size in bytes.
35    pub const fn with_max_bytes(mut self, max_bytes: usize) -> Self {
36        self.max_bytes = max_bytes;
37        self
38    }
39
40    /// Return the maximum number of unique nodes.
41    pub const fn max_nodes(self) -> usize {
42        self.max_nodes
43    }
44
45    /// Set the maximum number of unique nodes.
46    pub const fn with_max_nodes(mut self, max_nodes: usize) -> Self {
47        self.max_nodes = max_nodes;
48        self
49    }
50
51    /// Return the maximum JSON nesting depth.
52    pub const fn max_depth(self) -> usize {
53        self.max_depth
54    }
55
56    /// Set the maximum JSON nesting depth.
57    pub const fn with_max_depth(mut self, max_depth: usize) -> Self {
58        self.max_depth = max_depth;
59        self
60    }
61
62    /// Return the maximum number of components in one `follows` path.
63    pub const fn max_path_components(self) -> usize {
64        self.max_path_components
65    }
66
67    /// Set the maximum number of components in one `follows` path.
68    pub const fn with_max_path_components(mut self, max_path_components: usize) -> Self {
69        self.max_path_components = max_path_components;
70        self
71    }
72}
73
74impl Default for Limits {
75    fn default() -> Self {
76        Self::new()
77    }
78}
79
80/// The category and associated context of a parse failure.
81#[derive(Clone, Debug, Eq, PartialEq)]
82#[non_exhaustive]
83pub enum ErrorKind {
84    /// The input is not valid UTF-8.
85    InvalidUtf8,
86    /// The input exceeds [`Limits::max_bytes`].
87    InputTooLarge {
88        /// The actual input size.
89        size: usize,
90        /// The configured maximum size.
91        limit: usize,
92    },
93    /// The JSON document ended before the expected value was complete.
94    UnexpectedEof,
95    /// A particular JSON token or value was expected.
96    Expected(&'static str),
97    /// Non-whitespace bytes followed the top-level JSON value.
98    TrailingCharacters,
99    /// A JSON string contained an unknown escape.
100    InvalidEscape,
101    /// A JSON string contained an invalid Unicode escape or surrogate pair.
102    InvalidUnicodeEscape,
103    /// A required unsigned integer was not representable as a `u64`.
104    InvalidNumber,
105    /// The source lock-file version is not supported.
106    UnsupportedVersion(u64),
107    /// A required lock-file field was absent.
108    MissingField(&'static str),
109    /// A direct edge referenced a node not present in the `nodes` object.
110    MissingNode(String),
111    /// The number of unique nodes exceeds [`Limits::max_nodes`].
112    TooManyNodes {
113        /// The actual number of unique nodes.
114        count: usize,
115        /// The configured maximum number of nodes.
116        limit: usize,
117    },
118    /// JSON nesting exceeds [`Limits::max_depth`].
119    NestingTooDeep {
120        /// The configured maximum nesting depth.
121        limit: usize,
122    },
123    /// A `follows` or parent path exceeds [`Limits::max_path_components`].
124    PathTooLong {
125        /// The configured maximum number of path components.
126        limit: usize,
127    },
128    /// A fetcher attribute was not a string, unsigned integer, or Boolean.
129    UnsupportedInputAttributeType,
130    /// A direct edge pointed back to the root node.
131    CycleToRoot,
132}
133
134/// A parse error carrying a byte offset into the input document.
135#[derive(Clone, Debug, Eq, PartialEq)]
136pub struct Error {
137    kind: ErrorKind,
138    offset: usize,
139}
140
141impl Error {
142    fn new(kind: ErrorKind, offset: usize) -> Self {
143        Self { kind, offset }
144    }
145
146    /// Return the parse failure category.
147    pub const fn kind(&self) -> &ErrorKind {
148        &self.kind
149    }
150
151    /// Return the byte offset associated with the failure.
152    pub const fn offset(&self) -> usize {
153        self.offset
154    }
155
156    /// Consume the error and return its failure category.
157    pub fn into_kind(self) -> ErrorKind {
158        self.kind
159    }
160}
161
162impl fmt::Display for Error {
163    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
164        match &self.kind {
165            ErrorKind::InvalidUtf8 => write!(formatter, "lock file is not valid UTF-8"),
166            ErrorKind::InputTooLarge { size, limit } => {
167                write!(
168                    formatter,
169                    "lock file is {size} bytes, exceeding the {limit}-byte limit"
170                )
171            }
172            ErrorKind::UnexpectedEof => write!(formatter, "unexpected end of lock file"),
173            ErrorKind::Expected(expected) => write!(formatter, "expected {expected}"),
174            ErrorKind::TrailingCharacters => {
175                write!(formatter, "trailing characters after lock file")
176            }
177            ErrorKind::InvalidEscape => write!(formatter, "invalid JSON string escape"),
178            ErrorKind::InvalidUnicodeEscape => write!(formatter, "invalid JSON Unicode escape"),
179            ErrorKind::InvalidNumber => write!(formatter, "invalid unsigned integer"),
180            ErrorKind::UnsupportedVersion(version) => {
181                write!(
182                    formatter,
183                    "unsupported lock file version {version}; expected 5 through 7"
184                )
185            }
186            ErrorKind::MissingField(field) => write!(formatter, "missing required field '{field}'"),
187            ErrorKind::MissingNode(node) => {
188                write!(formatter, "lock file references missing node '{node}'")
189            }
190            ErrorKind::TooManyNodes { count, limit } => {
191                write!(
192                    formatter,
193                    "lock file has {count} nodes, exceeding the {limit}-node limit"
194                )
195            }
196            ErrorKind::NestingTooDeep { limit } => {
197                write!(formatter, "JSON nesting exceeds the limit of {limit}")
198            }
199            ErrorKind::PathTooLong { limit } => {
200                write!(
201                    formatter,
202                    "input path exceeds the limit of {limit} components"
203                )
204            }
205            ErrorKind::UnsupportedInputAttributeType => {
206                write!(formatter, "unsupported input attribute type in lock file")
207            }
208            ErrorKind::CycleToRoot => write!(formatter, "lock file contains cycle to root node"),
209        }?;
210        write!(formatter, " at byte {}", self.offset)
211    }
212}
213
214impl error::Error for Error {}
215
216struct WireLock<'a> {
217    version: u64,
218    root: Cow<'a, str>,
219    nodes: Vec<WireNode<'a>>,
220}
221
222struct WireNode<'a> {
223    offset: usize,
224    key: Cow<'a, str>,
225    inputs: Vec<WireInput<'a>>,
226    original: Option<AttrSet<'a>>,
227    locked: Option<AttrSet<'a>>,
228    info: Option<AttrSet<'a>>,
229    is_flake: bool,
230    parent: Option<InputPath<'a>>,
231}
232
233struct WireInput<'a> {
234    offset: usize,
235    name: Cow<'a, str>,
236    edge: WireEdge<'a>,
237}
238
239enum WireEdge<'a> {
240    Node(Cow<'a, str>),
241    Follows(InputPath<'a>),
242}
243
244pub(crate) fn parse<'a>(bytes: &'a [u8], limits: Limits) -> Result<LockFile<'a>, Error> {
245    if bytes.len() > limits.max_bytes {
246        return Err(Error::new(
247            ErrorKind::InputTooLarge {
248                size: bytes.len(),
249                limit: limits.max_bytes,
250            },
251            0,
252        ));
253    }
254    let source = str::from_utf8(bytes)
255        .map_err(|error| Error::new(ErrorKind::InvalidUtf8, error.valid_up_to()))?;
256    let mut parser = Parser {
257        source,
258        bytes,
259        position: 0,
260        depth: 0,
261        limits,
262    };
263    let wire = parser.parse_lock_file()?;
264    parser.whitespace();
265    if parser.position != bytes.len() {
266        return Err(parser.error(ErrorKind::TrailingCharacters));
267    }
268    build(wire, limits)
269}
270
271struct Parser<'a> {
272    source: &'a str,
273    bytes: &'a [u8],
274    position: usize,
275    depth: usize,
276    limits: Limits,
277}
278
279impl<'a> Parser<'a> {
280    fn parse_lock_file(&mut self) -> Result<WireLock<'a>, Error> {
281        self.whitespace();
282        self.expect(b'{', "'{'")?;
283        self.enter()?;
284        let mut version = None;
285        let mut root = None;
286        let mut nodes = None;
287        self.whitespace();
288        if self.consume(b'}') {
289            self.leave();
290        } else {
291            loop {
292                let key = self.string()?;
293                self.whitespace();
294                self.expect(b':', "':'")?;
295                self.whitespace();
296                match key.as_ref() {
297                    "version" => version = Some(self.unsigned()?),
298                    "root" => root = Some(self.string()?),
299                    "nodes" => nodes = Some(self.nodes()?),
300                    _ => self.skip_value()?,
301                }
302                self.whitespace();
303                if self.consume(b'}') {
304                    self.leave();
305                    break;
306                }
307                self.expect(b',', "',' or '}'")?;
308                self.whitespace();
309            }
310        }
311
312        let version = version.ok_or_else(|| self.error(ErrorKind::MissingField("version")))?;
313        if !(5..=7).contains(&version) {
314            return Err(self.error(ErrorKind::UnsupportedVersion(version)));
315        }
316        Ok(WireLock {
317            version,
318            root: root.ok_or_else(|| self.error(ErrorKind::MissingField("root")))?,
319            nodes: nodes.ok_or_else(|| self.error(ErrorKind::MissingField("nodes")))?,
320        })
321    }
322
323    fn nodes(&mut self) -> Result<Vec<WireNode<'a>>, Error> {
324        self.expect(b'{', "nodes object")?;
325        self.enter()?;
326        let mut nodes: Vec<WireNode<'a>> = Vec::new();
327        self.whitespace();
328        if self.consume(b'}') {
329            self.leave();
330            return self.finish_nodes(nodes);
331        }
332        loop {
333            let offset = self.position;
334            let key = self.string()?;
335            self.whitespace();
336            self.expect(b':', "':'")?;
337            self.whitespace();
338            let node = self.node(offset, key)?;
339            nodes.push(node);
340            self.whitespace();
341            if self.consume(b'}') {
342                self.leave();
343                return self.finish_nodes(nodes);
344            }
345            self.expect(b',', "',' or '}'")?;
346            self.whitespace();
347        }
348    }
349
350    fn finish_nodes(&self, mut nodes: Vec<WireNode<'a>>) -> Result<Vec<WireNode<'a>>, Error> {
351        // Sorting once avoids quadratic shifting for reverse-ordered JSON
352        // objects. Descending offsets make `dedup_by` retain the last value for
353        // duplicate JSON keys, matching the previous parser and Nix's JSON
354        // object behavior.
355        nodes.sort_unstable_by(|left, right| {
356            left.key
357                .as_ref()
358                .cmp(right.key.as_ref())
359                .then_with(|| right.offset.cmp(&left.offset))
360        });
361        nodes.dedup_by(|right, left| right.key == left.key);
362        if nodes.len() > self.limits.max_nodes {
363            return Err(self.error(ErrorKind::TooManyNodes {
364                count: nodes.len(),
365                limit: self.limits.max_nodes,
366            }));
367        }
368        Ok(nodes)
369    }
370
371    fn node(&mut self, offset: usize, key: Cow<'a, str>) -> Result<WireNode<'a>, Error> {
372        self.expect(b'{', "node object")?;
373        self.enter()?;
374        let mut node = WireNode {
375            offset,
376            key,
377            inputs: Vec::new(),
378            original: None,
379            locked: None,
380            info: None,
381            is_flake: true,
382            parent: None,
383        };
384        self.whitespace();
385        if self.consume(b'}') {
386            self.leave();
387            return Ok(node);
388        }
389        loop {
390            let field = self.string()?;
391            self.whitespace();
392            self.expect(b':', "':'")?;
393            self.whitespace();
394            match field.as_ref() {
395                "inputs" => node.inputs = self.inputs()?,
396                "original" => node.original = Some(self.attrs()?),
397                "locked" => node.locked = Some(self.attrs()?),
398                "info" => node.info = Some(self.attrs()?),
399                "flake" => node.is_flake = self.boolean()?,
400                "parent" => {
401                    node.parent = if self.starts_with(b"null") {
402                        self.null()?;
403                        None
404                    } else {
405                        Some(self.path()?)
406                    }
407                }
408                _ => self.skip_value()?,
409            }
410            self.whitespace();
411            if self.consume(b'}') {
412                self.leave();
413                return Ok(node);
414            }
415            self.expect(b',', "',' or '}'")?;
416            self.whitespace();
417        }
418    }
419
420    fn inputs(&mut self) -> Result<Vec<WireInput<'a>>, Error> {
421        self.expect(b'{', "inputs object")?;
422        self.enter()?;
423        let mut inputs: Vec<WireInput<'a>> = Vec::new();
424        self.whitespace();
425        if self.consume(b'}') {
426            self.leave();
427            return Ok(inputs);
428        }
429        loop {
430            let offset = self.position;
431            let name = self.string()?;
432            self.whitespace();
433            self.expect(b':', "':'")?;
434            self.whitespace();
435            let edge = if self.peek() == Some(b'[') {
436                WireEdge::Follows(self.path()?)
437            } else {
438                WireEdge::Node(self.string()?)
439            };
440            inputs.push(WireInput { offset, name, edge });
441            self.whitespace();
442            if self.consume(b'}') {
443                self.leave();
444                inputs.sort_unstable_by(|left, right| {
445                    left.name
446                        .as_ref()
447                        .cmp(right.name.as_ref())
448                        .then_with(|| right.offset.cmp(&left.offset))
449                });
450                inputs.dedup_by(|right, left| right.name == left.name);
451                return Ok(inputs);
452            }
453            self.expect(b',', "',' or '}'")?;
454            self.whitespace();
455        }
456    }
457
458    fn attrs(&mut self) -> Result<AttrSet<'a>, Error> {
459        self.expect(b'{', "input attribute object")?;
460        self.enter()?;
461        let mut attrs = Vec::new();
462        self.whitespace();
463        if self.consume(b'}') {
464            self.leave();
465            return Ok(AttrSet::default());
466        }
467        loop {
468            let offset = self.position;
469            let name = self.string()?;
470            self.whitespace();
471            self.expect(b':', "':'")?;
472            self.whitespace();
473            let value = match self.peek() {
474                Some(b'"') => AttrValue::String(self.string()?),
475                Some(b't' | b'f') => AttrValue::Bool(self.boolean()?),
476                Some(b'0'..=b'9') => AttrValue::Integer(self.unsigned()?),
477                _ => return Err(self.error(ErrorKind::UnsupportedInputAttributeType)),
478            };
479            attrs.push((offset, Attr { name, value }));
480            self.whitespace();
481            if self.consume(b'}') {
482                self.leave();
483                attrs.sort_unstable_by(|(left_offset, left), (right_offset, right)| {
484                    left.name
485                        .as_ref()
486                        .cmp(right.name.as_ref())
487                        .then_with(|| right_offset.cmp(left_offset))
488                });
489                attrs.dedup_by(|(_, right), (_, left)| right.name == left.name);
490                return Ok(AttrSet::from_entries(
491                    attrs.into_iter().map(|(_, attr)| attr).collect(),
492                ));
493            }
494            self.expect(b',', "',' or '}'")?;
495            self.whitespace();
496        }
497    }
498
499    fn path(&mut self) -> Result<InputPath<'a>, Error> {
500        self.expect(b'[', "input path array")?;
501        self.enter()?;
502        let mut components = Vec::new();
503        self.whitespace();
504        if self.consume(b']') {
505            self.leave();
506            return Ok(InputPath(components));
507        }
508        loop {
509            components.push(self.string()?);
510            if components.len() > self.limits.max_path_components {
511                return Err(self.error(ErrorKind::PathTooLong {
512                    limit: self.limits.max_path_components,
513                }));
514            }
515            self.whitespace();
516            if self.consume(b']') {
517                self.leave();
518                return Ok(InputPath(components));
519            }
520            self.expect(b',', "',' or ']'")?;
521            self.whitespace();
522        }
523    }
524
525    fn string(&mut self) -> Result<Cow<'a, str>, Error> {
526        self.expect(b'"', "JSON string")?;
527        let start = self.position;
528        let mut segment_start = start;
529        let mut decoded: Option<String> = None;
530
531        loop {
532            let relative = memchr2(b'"', b'\\', &self.bytes[self.position..])
533                .ok_or_else(|| self.error(ErrorKind::UnexpectedEof))?;
534            let marker = self.position + relative;
535            if let Some(control) = self.bytes[self.position..marker]
536                .iter()
537                .position(|byte| *byte < 0x20)
538            {
539                return Err(Error::new(
540                    ErrorKind::Expected("escaped control character"),
541                    self.position + control,
542                ));
543            }
544            self.position = marker + 1;
545            match self.bytes[marker] {
546                b'"' => {
547                    if let Some(mut decoded) = decoded {
548                        decoded.push_str(&self.source[segment_start..marker]);
549                        return Ok(Cow::Owned(decoded));
550                    }
551                    return Ok(Cow::Borrowed(&self.source[start..marker]));
552                }
553                b'\\' => {
554                    let output = decoded.get_or_insert_with(|| {
555                        let mut value = String::with_capacity(marker.saturating_sub(start) + 8);
556                        value.push_str(&self.source[start..marker]);
557                        value
558                    });
559                    if segment_start != start {
560                        output.push_str(&self.source[segment_start..marker]);
561                    }
562                    self.escape(output)?;
563                    segment_start = self.position;
564                }
565                _ => unreachable!(),
566            }
567        }
568    }
569
570    fn escape(&mut self, output: &mut String) -> Result<(), Error> {
571        let escape = self
572            .next()
573            .ok_or_else(|| self.error(ErrorKind::UnexpectedEof))?;
574        match escape {
575            b'"' => output.push('"'),
576            b'\\' => output.push('\\'),
577            b'/' => output.push('/'),
578            b'b' => output.push('\u{0008}'),
579            b'f' => output.push('\u{000c}'),
580            b'n' => output.push('\n'),
581            b'r' => output.push('\r'),
582            b't' => output.push('\t'),
583            b'u' => {
584                let first = self.hex_quad()?;
585                let scalar = if (0xd800..=0xdbff).contains(&first) {
586                    if !self.consume(b'\\') || !self.consume(b'u') {
587                        return Err(self.error(ErrorKind::InvalidUnicodeEscape));
588                    }
589                    let second = self.hex_quad()?;
590                    if !(0xdc00..=0xdfff).contains(&second) {
591                        return Err(self.error(ErrorKind::InvalidUnicodeEscape));
592                    }
593                    0x10000 + (((first - 0xd800) as u32) << 10) + (second - 0xdc00) as u32
594                } else if (0xdc00..=0xdfff).contains(&first) {
595                    return Err(self.error(ErrorKind::InvalidUnicodeEscape));
596                } else {
597                    first as u32
598                };
599                output.push(
600                    char::from_u32(scalar)
601                        .ok_or_else(|| self.error(ErrorKind::InvalidUnicodeEscape))?,
602                );
603            }
604            _ => return Err(self.error(ErrorKind::InvalidEscape)),
605        }
606        Ok(())
607    }
608
609    fn hex_quad(&mut self) -> Result<u16, Error> {
610        if self.position + 4 > self.bytes.len() {
611            return Err(self.error(ErrorKind::UnexpectedEof));
612        }
613        let mut value = 0u16;
614        for _ in 0..4 {
615            let digit = match self.next().expect("length checked") {
616                b'0'..=b'9' => self.bytes[self.position - 1] - b'0',
617                b'a'..=b'f' => self.bytes[self.position - 1] - b'a' + 10,
618                b'A'..=b'F' => self.bytes[self.position - 1] - b'A' + 10,
619                _ => return Err(self.error(ErrorKind::InvalidUnicodeEscape)),
620            };
621            value = (value << 4) | u16::from(digit);
622        }
623        Ok(value)
624    }
625
626    fn unsigned(&mut self) -> Result<u64, Error> {
627        let start = self.position;
628        let first = self
629            .next()
630            .ok_or_else(|| self.error(ErrorKind::UnexpectedEof))?;
631        if !first.is_ascii_digit() {
632            return Err(Error::new(ErrorKind::InvalidNumber, start));
633        }
634        if first == b'0' && self.peek().is_some_and(|byte| byte.is_ascii_digit()) {
635            return Err(Error::new(ErrorKind::InvalidNumber, start));
636        }
637        let mut value = u64::from(first - b'0');
638        while let Some(byte @ b'0'..=b'9') = self.peek() {
639            self.position += 1;
640            value = value
641                .checked_mul(10)
642                .and_then(|value| value.checked_add(u64::from(byte - b'0')))
643                .ok_or_else(|| Error::new(ErrorKind::InvalidNumber, start))?;
644        }
645        if matches!(self.peek(), Some(b'.' | b'e' | b'E')) {
646            return Err(Error::new(ErrorKind::InvalidNumber, start));
647        }
648        Ok(value)
649    }
650
651    fn boolean(&mut self) -> Result<bool, Error> {
652        if self.starts_with(b"true") {
653            self.position += 4;
654            Ok(true)
655        } else if self.starts_with(b"false") {
656            self.position += 5;
657            Ok(false)
658        } else {
659            Err(self.error(ErrorKind::Expected("Boolean")))
660        }
661    }
662
663    fn null(&mut self) -> Result<(), Error> {
664        if self.starts_with(b"null") {
665            self.position += 4;
666            Ok(())
667        } else {
668            Err(self.error(ErrorKind::Expected("null")))
669        }
670    }
671
672    fn skip_value(&mut self) -> Result<(), Error> {
673        self.whitespace();
674        match self.peek() {
675            Some(b'"') => {
676                self.string()?;
677                Ok(())
678            }
679            Some(b'{') => self.skip_object(),
680            Some(b'[') => self.skip_array(),
681            Some(b't' | b'f') => self.boolean().map(drop),
682            Some(b'n') => self.null(),
683            Some(b'-' | b'0'..=b'9') => self.skip_number(),
684            Some(_) => Err(self.error(ErrorKind::Expected("JSON value"))),
685            None => Err(self.error(ErrorKind::UnexpectedEof)),
686        }
687    }
688
689    fn skip_object(&mut self) -> Result<(), Error> {
690        self.expect(b'{', "'{'")?;
691        self.enter()?;
692        self.whitespace();
693        if self.consume(b'}') {
694            self.leave();
695            return Ok(());
696        }
697        loop {
698            self.string()?;
699            self.whitespace();
700            self.expect(b':', "':'")?;
701            self.skip_value()?;
702            self.whitespace();
703            if self.consume(b'}') {
704                self.leave();
705                return Ok(());
706            }
707            self.expect(b',', "',' or '}'")?;
708            self.whitespace();
709        }
710    }
711
712    fn skip_array(&mut self) -> Result<(), Error> {
713        self.expect(b'[', "'['")?;
714        self.enter()?;
715        self.whitespace();
716        if self.consume(b']') {
717            self.leave();
718            return Ok(());
719        }
720        loop {
721            self.skip_value()?;
722            self.whitespace();
723            if self.consume(b']') {
724                self.leave();
725                return Ok(());
726            }
727            self.expect(b',', "',' or ']'")?;
728            self.whitespace();
729        }
730    }
731
732    fn skip_number(&mut self) -> Result<(), Error> {
733        let start = self.position;
734        self.consume(b'-');
735        match self.next() {
736            Some(b'0') => {
737                if self.peek().is_some_and(|byte| byte.is_ascii_digit()) {
738                    return Err(Error::new(ErrorKind::InvalidNumber, start));
739                }
740            }
741            Some(b'1'..=b'9') => {
742                while self.peek().is_some_and(|byte| byte.is_ascii_digit()) {
743                    self.position += 1;
744                }
745            }
746            _ => return Err(Error::new(ErrorKind::InvalidNumber, start)),
747        }
748        if self.consume(b'.') {
749            if !self.peek().is_some_and(|byte| byte.is_ascii_digit()) {
750                return Err(Error::new(ErrorKind::InvalidNumber, start));
751            }
752            while self.peek().is_some_and(|byte| byte.is_ascii_digit()) {
753                self.position += 1;
754            }
755        }
756        if matches!(self.peek(), Some(b'e' | b'E')) {
757            self.position += 1;
758            if matches!(self.peek(), Some(b'+' | b'-')) {
759                self.position += 1;
760            }
761            if !self.peek().is_some_and(|byte| byte.is_ascii_digit()) {
762                return Err(Error::new(ErrorKind::InvalidNumber, start));
763            }
764            while self.peek().is_some_and(|byte| byte.is_ascii_digit()) {
765                self.position += 1;
766            }
767        }
768        Ok(())
769    }
770
771    fn whitespace(&mut self) {
772        while matches!(self.peek(), Some(b' ' | b'\n' | b'\r' | b'\t')) {
773            self.position += 1;
774        }
775    }
776
777    fn enter(&mut self) -> Result<(), Error> {
778        self.depth += 1;
779        if self.depth > self.limits.max_depth {
780            return Err(self.error(ErrorKind::NestingTooDeep {
781                limit: self.limits.max_depth,
782            }));
783        }
784        Ok(())
785    }
786
787    fn leave(&mut self) {
788        self.depth -= 1;
789    }
790
791    fn expect(&mut self, byte: u8, expected: &'static str) -> Result<(), Error> {
792        if self.consume(byte) {
793            Ok(())
794        } else if self.position == self.bytes.len() {
795            Err(self.error(ErrorKind::UnexpectedEof))
796        } else {
797            Err(self.error(ErrorKind::Expected(expected)))
798        }
799    }
800
801    fn consume(&mut self, byte: u8) -> bool {
802        if self.peek() == Some(byte) {
803            self.position += 1;
804            true
805        } else {
806            false
807        }
808    }
809
810    fn starts_with(&self, bytes: &[u8]) -> bool {
811        self.bytes[self.position..].starts_with(bytes)
812    }
813
814    fn peek(&self) -> Option<u8> {
815        self.bytes.get(self.position).copied()
816    }
817
818    fn next(&mut self) -> Option<u8> {
819        let byte = self.peek()?;
820        self.position += 1;
821        Some(byte)
822    }
823
824    fn error(&self, kind: ErrorKind) -> Error {
825        Error::new(kind, self.position)
826    }
827}
828
829fn build<'a>(wire: WireLock<'a>, limits: Limits) -> Result<LockFile<'a>, Error> {
830    let root_old = wire
831        .nodes
832        .binary_search_by(|node| node.key.as_ref().cmp(wire.root.as_ref()))
833        .map_err(|_| Error::new(ErrorKind::MissingNode(wire.root.into_owned()), 0))?;
834
835    let mut reachable = vec![false; wire.nodes.len()];
836    let mut resolved_targets: Vec<Vec<Option<usize>>> = wire
837        .nodes
838        .iter()
839        .map(|node| vec![None; node.inputs.len()])
840        .collect();
841    let mut stack = vec![root_old];
842    while let Some(node_index) = stack.pop() {
843        if std::mem::replace(&mut reachable[node_index], true) {
844            continue;
845        }
846        let node = &wire.nodes[node_index];
847        for (input_index, input) in node.inputs.iter().enumerate() {
848            if let WireEdge::Node(target) = &input.edge {
849                let target_index = wire
850                    .nodes
851                    .binary_search_by(|candidate| candidate.key.as_ref().cmp(target.as_ref()))
852                    .map_err(|_| {
853                        Error::new(ErrorKind::MissingNode(target.to_string()), input.offset)
854                    })?;
855                if target_index == root_old {
856                    return Err(Error::new(ErrorKind::CycleToRoot, input.offset));
857                }
858                resolved_targets[node_index][input_index] = Some(target_index);
859                stack.push(target_index);
860            }
861        }
862    }
863
864    let reachable_count = reachable.iter().filter(|reachable| **reachable).count();
865    if reachable_count > limits.max_nodes || reachable_count > u32::MAX as usize {
866        return Err(Error::new(
867            ErrorKind::TooManyNodes {
868                count: reachable_count,
869                limit: limits.max_nodes.min(u32::MAX as usize),
870            },
871            0,
872        ));
873    }
874
875    let mut old_to_new = vec![None; wire.nodes.len()];
876    old_to_new[root_old] = Some(NodeId(0));
877    let mut next_id = 1u32;
878    for (old, is_reachable) in reachable.iter().copied().enumerate() {
879        if is_reachable && old != root_old {
880            old_to_new[old] = Some(NodeId(next_id));
881            next_id += 1;
882        }
883    }
884
885    let mut slots: Vec<Option<Node<'a>>> = (0..reachable_count).map(|_| None).collect();
886    for (old_index, mut node) in wire.nodes.into_iter().enumerate() {
887        let Some(new_id) = old_to_new[old_index] else {
888            continue;
889        };
890        let mut inputs = Vec::with_capacity(node.inputs.len());
891        for (input_index, input) in node.inputs.into_iter().enumerate() {
892            let edge = match input.edge {
893                WireEdge::Node(_) => {
894                    let target_old = resolved_targets[old_index][input_index]
895                        .expect("reachable direct edge was resolved");
896                    Edge::Node(old_to_new[target_old].expect("target is reachable"))
897                }
898                WireEdge::Follows(path) => Edge::Follows(path),
899            };
900            inputs.push(Input {
901                name: input.name,
902                edge,
903            });
904        }
905        let kind = if old_index == root_old {
906            NodeKind::Root
907        } else {
908            let mut locked = node
909                .locked
910                .take()
911                .ok_or_else(|| Error::new(ErrorKind::MissingField("locked"), node.offset))?;
912            if let Some(info) = node.info.take() {
913                locked.overlay(info);
914            }
915            NodeKind::Locked(LockedNode {
916                original: node
917                    .original
918                    .take()
919                    .ok_or_else(|| Error::new(ErrorKind::MissingField("original"), node.offset))?,
920                locked,
921                is_flake: node.is_flake,
922                parent: node.parent,
923            })
924        };
925        slots[new_id.index()] = Some(Node {
926            wire_key: node.key,
927            inputs,
928            kind,
929        });
930    }
931
932    Ok(LockFile {
933        source_version: wire.version as u8,
934        root: NodeId(0),
935        nodes: slots
936            .into_iter()
937            .map(|node| node.expect("every reachable node received a slot"))
938            .collect(),
939    })
940}