Build a validated, deterministic dependency closure from direct view membership. Direct dependency hashes are sorted before traversal. The resulting order always places dependencies before dependents while preserving the membership order wherever dependency constraints permit.
(
txn: &T,
membership: &ViewMembershipSet,
)
| 112 | /// order always places dependencies before dependents while preserving the |
| 113 | /// membership order wherever dependency constraints permit. |
| 114 | pub fn try_from_membership<T: GraphTxnT>( |
| 115 | txn: &T, |
| 116 | membership: &ViewMembershipSet, |
| 117 | ) -> Result<Self, PristineError> { |
| 118 | #[derive(Clone, Copy, PartialEq, Eq)] |
| 119 | enum VisitColor { |
| 120 | White, |
| 121 | Gray, |
| 122 | Black, |
| 123 | } |
| 124 | |
| 125 | struct VisitFrame { |
| 126 | change_id: NodeId, |
| 127 | dependencies: Vec<crate::types::Hash>, |
| 128 | next_dependency: usize, |
| 129 | } |
| 130 | |
| 131 | fn load_frame<T: GraphTxnT>( |
| 132 | txn: &T, |
| 133 | change_id: NodeId, |
| 134 | ) -> Result<VisitFrame, PristineError> { |
| 135 | if txn.get_external(change_id)?.is_none() { |
| 136 | return Err(PristineError::ChangeNotFound { |
| 137 | id: change_id.get(), |
| 138 | }); |
| 139 | } |
| 140 | Ok(VisitFrame { |
| 141 | change_id, |
| 142 | dependencies: txn.get_indexed_change_deps(change_id)?, |
| 143 | next_dependency: 0, |
| 144 | }) |
| 145 | } |
| 146 | |
| 147 | let mut colors = HashMap::new(); |
| 148 | let mut dependency_first = Vec::new(); |
| 149 | let mut closure_membership = HashSet::new(); |
| 150 | |
| 151 | for root_id in membership.iter().copied() { |
| 152 | let root_color = colors.get(&root_id).copied().unwrap_or(VisitColor::White); |
| 153 | if root_color == VisitColor::Black { |
| 154 | continue; |
| 155 | } |
| 156 | |
| 157 | let root_frame = load_frame(txn, root_id)?; |
| 158 | colors.insert(root_id, VisitColor::Gray); |
| 159 | let mut stack = vec![root_frame]; |
| 160 | |
| 161 | while let Some(frame) = stack.last_mut() { |
| 162 | if frame.next_dependency == frame.dependencies.len() { |
| 163 | let completed_id = frame.change_id; |
| 164 | stack.pop(); |
| 165 | colors.insert(completed_id, VisitColor::Black); |
| 166 | if closure_membership.insert(completed_id) { |
| 167 | dependency_first.push(completed_id); |
| 168 | } |
| 169 | continue; |
| 170 | } |
| 171 |
nothing calls this directly
no test coverage detected