1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
// Copyright (c) Facebook, Inc. and its affiliates // SPDX-License-Identifier: MIT OR Apache-2.0 use serde_reflection::{ContainerFormat, Format, FormatHolder, Registry, Result}; use std::collections::{BTreeMap, BTreeSet, HashSet}; fn get_dependencies(format: &ContainerFormat) -> Result<BTreeSet<&str>> { let mut result = BTreeSet::new(); format.visit(&mut |format| { if let Format::TypeName(x) = format { result.insert(x.as_str()); } Ok(()) })?; Ok(result) } /// Build a map of dependencies between the entries of a `Registry`. /// * By definition, an entry named `x` depends on `y` iff the container format of `x` in the registry /// syntactically contains a reference to `y` (i.e. an expression `Format::TypeName(y)`). /// * Dependencies can play a role in code generation in some languages (e.g. Rust or C++) where inductive /// definitions may require explicit "boxing" (i.e. adding pointer indirections) to ensure finite object sizes. pub fn get_dependency_map(registry: &Registry) -> Result<BTreeMap<&str, BTreeSet<&str>>> { let mut children = BTreeMap::new(); for (name, format) in registry { children.insert(name.as_str(), get_dependencies(format)?); } Ok(children) } /// Classic topological sorting algorithm except that it doesn't abort in case of cycles. pub fn best_effort_topological_sort<T>(children: &BTreeMap<T, BTreeSet<T>>) -> Vec<T> where T: Clone + std::cmp::Ord + std::cmp::Eq + std::hash::Hash, { // Build the initial queue so that we pick up nodes with less children first (and otherwise // those with smaller key first). // This is a heuristic to break cycles preferably at large nodes (see comment below). let mut queue: Vec<_> = children.keys().rev().cloned().collect(); queue.sort_by(|node1, node2| children[node1].len().cmp(&children[node2].len())); let mut result = Vec::new(); // Nodes already inserted in result. let mut sorted = HashSet::new(); // Nodes for which children have been enqueued. let mut seen = HashSet::new(); while let Some(node) = queue.pop() { if sorted.contains(&node) { continue; } if seen.contains(&node) { // Second time we see this node. // * If `node` does not belong to a cycle in the graph, then by now, all its children // have been sorted. // * If `node` has children that depend back on it. We may be visiting `node` again // before some of those children. Just insert `node` here. By ignoring edges going back // to `node` now, we are effectively deciding to "break the cycle" there in future // applications (e.g. `node` may be forward-declared in C++ and `Box`-ed in Rust). sorted.insert(node.clone()); result.push(node); continue; } // First time we see this node: // 1. Mark it so that it is no longer enqueued. seen.insert(node.clone()); // 2. Schedule all the (yet unseen) children then this node for a second visit. // (If possible, visit children by increasing key.) queue.push(node.clone()); for child in children[&node].iter().rev() { if !seen.contains(child) { queue.push(child.clone()); } } } result }