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#[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 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 pub const fn max_bytes(self) -> usize {
31 self.max_bytes
32 }
33
34 pub const fn with_max_bytes(mut self, max_bytes: usize) -> Self {
36 self.max_bytes = max_bytes;
37 self
38 }
39
40 pub const fn max_nodes(self) -> usize {
42 self.max_nodes
43 }
44
45 pub const fn with_max_nodes(mut self, max_nodes: usize) -> Self {
47 self.max_nodes = max_nodes;
48 self
49 }
50
51 pub const fn max_depth(self) -> usize {
53 self.max_depth
54 }
55
56 pub const fn with_max_depth(mut self, max_depth: usize) -> Self {
58 self.max_depth = max_depth;
59 self
60 }
61
62 pub const fn max_path_components(self) -> usize {
64 self.max_path_components
65 }
66
67 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#[derive(Clone, Debug, Eq, PartialEq)]
82#[non_exhaustive]
83pub enum ErrorKind {
84 InvalidUtf8,
86 InputTooLarge {
88 size: usize,
90 limit: usize,
92 },
93 UnexpectedEof,
95 Expected(&'static str),
97 TrailingCharacters,
99 InvalidEscape,
101 InvalidUnicodeEscape,
103 InvalidNumber,
105 UnsupportedVersion(u64),
107 MissingField(&'static str),
109 MissingNode(String),
111 TooManyNodes {
113 count: usize,
115 limit: usize,
117 },
118 NestingTooDeep {
120 limit: usize,
122 },
123 PathTooLong {
125 limit: usize,
127 },
128 UnsupportedInputAttributeType,
130 CycleToRoot,
132}
133
134#[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 pub const fn kind(&self) -> &ErrorKind {
148 &self.kind
149 }
150
151 pub const fn offset(&self) -> usize {
153 self.offset
154 }
155
156 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 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}