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

Function compute_insert_order

atomic-repository/src/apply/mod.rs:158–203  ·  view source on GitHub ↗

Determine the order to insert a set of changes respecting dependencies. This performs a topological sort of the changes based on their dependency relationships. # Arguments `changes` - Map of change hash to change # Returns Ordered list of hashes to insert (dependencies first).

(
    changes: &std::collections::HashMap<Hash, Change>,
)

Source from the content-addressed store, hash-verified

156///
157/// Ordered list of hashes to insert (dependencies first).
158pub fn compute_insert_order(
159 changes: &std::collections::HashMap<Hash, Change>,
160) -> InsertResult<Vec<Hash>> {
161 let mut order = Vec::new();
162 let mut visited = HashSet::new();
163 let mut in_progress = HashSet::new();
164
165 fn visit(
166 hash: &Hash,
167 changes: &std::collections::HashMap<Hash, Change>,
168 visited: &mut HashSet<Hash>,
169 in_progress: &mut HashSet<Hash>,
170 order: &mut Vec<Hash>,
171 ) -> InsertResult<()> {
172 if visited.contains(hash) {
173 return Ok(());
174 }
175 if in_progress.contains(hash) {
176 return Err(InsertError::CyclicDependency {
177 message: format!("Cycle detected involving {}", hash.to_base32()),
178 });
179 }
180
181 in_progress.insert(*hash);
182
183 if let Some(change) = changes.get(hash) {
184 for dep in change.dependencies() {
185 if changes.contains_key(dep) {
186 visit(dep, changes, visited, in_progress, order)?;
187 }
188 }
189 }
190
191 in_progress.remove(hash);
192 visited.insert(*hash);
193 order.push(*hash);
194
195 Ok(())
196 }
197
198 for hash in changes.keys() {
199 visit(hash, changes, &mut visited, &mut in_progress, &mut order)?;
200 }
201
202 Ok(order)
203}
204
205/// Write a change to the graph and add it to a view's change log.
206///

Callers 2

order_changes_by_depsFunction · 0.85

Calls 1

visitFunction · 0.70

Tested by 1