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

Function detect_fork_conflicts

atomic-core/src/output/repo/fork.rs:56–220  ·  view source on GitHub ↗

Detect fork conflicts in the alive graph. A fork is a vertex with ≥2 children that reside in different SCCs (i.e. there is no ordering between them). Only non-empty, non-root content children are considered — structural markers (empty inode vertices) are filtered out. # Arguments `graph` - The alive graph to scan for forks `order` - The computed SCC ordering from Tarjan's algorithm # Returns

(
    graph: &AliveGraph,
    order: &OrderResult,
)

Source from the content-addressed store, hash-verified

54/// Returns [`PristineError::Inconsistent`] when the order or graph edges
55/// reference a vertex that is absent from the alive graph or its SCC order.
56pub(crate) fn detect_fork_conflicts(
57 graph: &AliveGraph,
58 order: &OrderResult,
59) -> Result<Vec<ForkConflict>, PristineError> {
60 use std::collections::{HashMap, HashSet, VecDeque};
61
62 let mut forks = Vec::new();
63
64 // Build vertex → SCC-index map so we can identify multi-vertex SCCs.
65 let mut vertex_to_scc: HashMap<VertexId, usize> = HashMap::new();
66 for (scc_idx, scc) in order.sccs.iter().enumerate() {
67 for &vid in scc {
68 graph
69 .try_get_vertex(vid)
70 .ok_or_else(|| PristineError::Inconsistent {
71 message: format!("order references missing alive graph vertex {vid:?}"),
72 })?;
73 vertex_to_scc.insert(vid, scc_idx);
74 }
75 }
76
77 // Reachability helper: does `from` reach `to` by following the alive
78 // graph's child edges (i.e. is `to` topologically downstream of
79 // `from`)? Used to filter out children that are linearly ordered
80 // through the additive edge model — they form a chain, not a fork.
81 let reachable = |from: VertexId, to: VertexId| -> Result<bool, PristineError> {
82 if from == to {
83 return Ok(false);
84 }
85 let mut seen: HashSet<VertexId> = HashSet::new();
86 let mut queue: VecDeque<VertexId> = VecDeque::new();
87 queue.push_back(from);
88 seen.insert(from);
89 while let Some(v) = queue.pop_front() {
90 graph
91 .try_get_vertex(v)
92 .ok_or_else(|| PristineError::Inconsistent {
93 message: format!(
94 "fork reachability references missing alive graph vertex {v:?}"
95 ),
96 })?;
97 for (_, child) in graph.children(v) {
98 if child.is_dummy() {
99 continue;
100 }
101 graph
102 .try_get_vertex(*child)
103 .ok_or_else(|| PristineError::Inconsistent {
104 message: format!(
105 "fork child edge references missing alive graph vertex {child:?}"
106 ),
107 })?;
108 if !seen.insert(*child) {
109 continue;
110 }
111 if *child == to {
112 return Ok(true);
113 }

Callers 3

three_way_forkFunction · 0.85

Calls 15

try_get_vertexMethod · 0.80
childrenMethod · 0.80
is_dummyMethod · 0.80
len_verticesMethod · 0.80
child_countMethod · 0.80
contains_keyMethod · 0.80
getMethod · 0.65
iterMethod · 0.45
insertMethod · 0.45
containsMethod · 0.45
pushMethod · 0.45
lenMethod · 0.45

Tested by 2

three_way_forkFunction · 0.68