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,
)
| 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. |
| 56 | pub(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 | } |