Iterative DFS over the closure-internal dependency graph: rejects cycles and enforces the depth budget without recursing (deep adversarial chains must not exhaust the stack).
(
edges: &HashMap<Hash, Vec<Hash>>,
max_depth: usize,
)
| 536 | /// and enforces the depth budget without recursing (deep adversarial chains |
| 537 | /// must not exhaust the stack). |
| 538 | fn check_depth_and_cycles( |
| 539 | edges: &HashMap<Hash, Vec<Hash>>, |
| 540 | max_depth: usize, |
| 541 | ) -> Result<usize, BindingClosureError> { |
| 542 | #[derive(Clone, Copy, PartialEq)] |
| 543 | enum Color { |
| 544 | White, |
| 545 | Grey, |
| 546 | Black, |
| 547 | } |
| 548 | let mut color: HashMap<Hash, Color> = edges.keys().map(|h| (*h, Color::White)).collect(); |
| 549 | let mut depth: HashMap<Hash, usize> = HashMap::with_capacity(edges.len()); |
| 550 | let mut overall = 0usize; |
| 551 | |
| 552 | let roots: Vec<Hash> = edges.keys().copied().collect(); |
| 553 | for root in roots { |
| 554 | if color[&root] != Color::White { |
| 555 | continue; |
| 556 | } |
| 557 | // Stack holds (node, phase): phase 0 = enter, 1 = leave. |
| 558 | let mut stack: Vec<(Hash, u8)> = vec![(root, 0)]; |
| 559 | while let Some((node, phase)) = stack.pop() { |
| 560 | if phase == 1 { |
| 561 | let child_max = edges[&node] |
| 562 | .iter() |
| 563 | .filter_map(|dep| depth.get(dep)) |
| 564 | .copied() |
| 565 | .max() |
| 566 | .unwrap_or(0); |
| 567 | let here = child_max + 1; |
| 568 | depth.insert(node, here); |
| 569 | if here > max_depth { |
| 570 | return Err(BindingClosureError::ClosureTooDeep { |
| 571 | limit: max_depth, |
| 572 | found: here, |
| 573 | }); |
| 574 | } |
| 575 | overall = overall.max(here); |
| 576 | color.insert(node, Color::Black); |
| 577 | continue; |
| 578 | } |
| 579 | match color[&node] { |
| 580 | Color::Black => continue, |
| 581 | Color::Grey => { |
| 582 | return Err(BindingClosureError::DependencyCycle { |
| 583 | at: node.to_base32(), |
| 584 | }) |
| 585 | } |
| 586 | Color::White => {} |
| 587 | } |
| 588 | color.insert(node, Color::Grey); |
| 589 | stack.push((node, 1)); |
| 590 | for dep in edges[&node].iter().rev() { |
| 591 | if color[dep] == Color::Grey { |
| 592 | return Err(BindingClosureError::DependencyCycle { |
| 593 | at: dep.to_base32(), |
| 594 | }); |
| 595 | } |