MCPcopy Create free account
hub / github.com/atomicdotdev/atomic / check_depth_and_cycles

Function check_depth_and_cycles

atomic-repository/src/git_binding/pack.rs:538–603  ·  view source on GitHub ↗

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,
)

Source from the content-addressed store, hash-verified

536/// and enforces the depth budget without recursing (deep adversarial chains
537/// must not exhaust the stack).
538fn 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 }

Callers 3

validate_binding_closureFunction · 0.85
depth_budget_is_enforcedFunction · 0.85

Calls 7

getMethod · 0.65
collectMethod · 0.45
lenMethod · 0.45
iterMethod · 0.45
insertMethod · 0.45
to_base32Method · 0.45
pushMethod · 0.45

Tested by 2

depth_budget_is_enforcedFunction · 0.68