//! Graph manipulation code //! //! I had hoped to use petgraph, but it is optimized for efficiency over //! usability, and I got lost in a maze of indices. // @@ begin lint list maintained by maint/add_warning @@ #![allow(renamed_and_removed_lints)] // @@REMOVE_WHEN(ci_arti_stable) #![allow(unknown_lints)] // @@REMOVE_WHEN(ci_arti_nightly) #![warn(missing_docs)] #![warn(noop_method_call)] #![warn(unreachable_pub)] #![warn(clippy::all)] #![deny(clippy::await_holding_lock)] #![deny(clippy::cargo_common_metadata)] #![deny(clippy::cast_lossless)] #![deny(clippy::checked_conversions)] #![allow(clippy::cognitive_complexity)] // See arti#2556 #![deny(clippy::debug_assert_with_mut_call)] #![deny(clippy::exhaustive_enums)] #![deny(clippy::exhaustive_structs)] #![deny(clippy::expl_impl_clone_on_copy)] #![deny(clippy::fallible_impl_from)] #![deny(clippy::implicit_clone)] #![deny(clippy::large_stack_arrays)] #![warn(clippy::manual_ok_or)] #![deny(clippy::missing_docs_in_private_items)] #![warn(clippy::needless_borrow)] #![warn(clippy::needless_pass_by_value)] #![warn(clippy::option_option)] #![deny(clippy::print_stderr)] #![deny(clippy::print_stdout)] #![warn(clippy::rc_buffer)] #![deny(clippy::ref_option_ref)] #![warn(clippy::semicolon_if_nothing_returned)] #![warn(clippy::trait_duplication_in_bounds)] #![deny(clippy::unchecked_time_subtraction)] #![deny(clippy::unnecessary_wraps)] #![warn(clippy::unseparated_literal_suffix)] #![deny(clippy::unwrap_used)] #![deny(clippy::mod_module_files)] #![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness #![allow(clippy::uninlined_format_args)] #![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945 #![allow(clippy::result_large_err)] // temporary workaround for arti#587 #![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best #![allow(clippy::needless_lifetimes)] // See arti#1765 #![allow(mismatched_lifetime_syntaxes)] // temporary workaround for arti#2060 #![allow(clippy::collapsible_if)] // See arti#2342 #![deny(clippy::unused_async)] #![deny(clippy::string_slice)] // See arti#2571 //! // @@ begin test lint list maintained by maint/add_warning @@ #![allow(clippy::bool_assert_comparison)] #![allow(clippy::clone_on_copy)] #![allow(clippy::dbg_macro)] #![allow(clippy::mixed_attributes_style)] #![allow(clippy::print_stderr)] #![allow(clippy::print_stdout)] #![allow(clippy::single_char_pattern)] #![allow(clippy::unwrap_used)] #![allow(clippy::unchecked_time_subtraction)] #![allow(clippy::useless_vec)] #![allow(clippy::needless_pass_by_value)] #![allow(clippy::string_slice)] // See arti#2571 //! #![allow(clippy::missing_docs_in_private_items)] #![allow(unreachable_pub)] use anyhow::{Result, anyhow}; use std::collections::{HashMap, HashSet}; use std::hash::Hash; /// Given a hashmap representing a binary relationship, compute its transitive closure. fn transitive_closure( inp: &HashMap>, ) -> HashMap> { let mut out = inp.clone(); let max_iters = inp.len(); for _ in 0..max_iters { let mut new_out = out.clone(); for (k, vs) in out.iter() { let new_vs = new_out .get_mut(k) .expect("That key should have been there when I cloned it..."); for v in vs.iter() { if let Some(vv) = out.get(v) { new_vs.extend(vv.iter().cloned()); } } } if out == new_out { break; } else { out = new_out; } } out } /// Given a hashmap representing a binary relationship, invert it. fn invert( inp: &HashMap>, ) -> HashMap> { let mut out: HashMap> = HashMap::new(); for (k, vs) in inp.iter() { for v in vs { out.entry(v.clone()).or_default().insert(k.clone()); } } out } /// A representation of which features depend on what. #[derive(Clone, Debug, Default)] pub struct FeatureGraph { /// List of all features. all_features: HashSet, /// Adjacency map: for each feature F, `depends_on[F]` includes G if F /// directly depends on G. depends_on: HashMap>, /// Inverse adjacency map. depended_on_by: HashMap>, /// Transitive closure of the adjacency map. reachable_from: HashMap>, } impl FeatureGraph { /// Convert a toml `[features]` section into a [`FeatureGraph`]. pub fn from_features_table(features: &toml_edit::Table) -> Result { let mut depends_on = HashMap::new(); for (k, vs) in features.iter() { let mut d = HashSet::new(); for v in vs .as_array() .ok_or_else(|| anyhow!("features.{} was not an array", k))? { let v = v .as_str() .ok_or_else(|| anyhow!("features.{} contained a non-string", k))?; d.insert(v.to_string()); } depends_on.insert(k.to_string(), d); } let all_features = depends_on.keys().cloned().collect(); let reachable_from = transitive_closure(&depends_on); let depended_on_by = invert(&depends_on); Ok(Self { all_features, depends_on, depended_on_by, reachable_from, }) } pub fn all_features(&self) -> impl Iterator + '_ { self.depends_on.keys().cloned() } pub fn contains_feature(&self, feature: &str) -> bool { self.all_features.contains(feature) } pub fn contains_edge(&self, from: &str, to: &str) -> bool { match self.depends_on.get(from) { Some(fs) => fs.contains(to), None => false, } } pub fn all_reachable_from(&self, feature: &str) -> impl Iterator + '_ + use<'_> { match self.reachable_from.get(feature) { Some(set) => itertools::Either::Left(set.iter().cloned()), None => itertools::Either::Right(std::iter::empty()), } } /// Return all the features that `feature` depends on. Return an empty iterator if /// it has no dependencies, or is not in this map. pub fn edges_from(&self, feature: &str) -> impl Iterator + '_ + use<'_> { match self.depends_on.get(feature) { Some(set) => itertools::Either::Left(set.iter().cloned()), None => itertools::Either::Right(std::iter::empty()), } } /// Return all the features that depend on `feature` directly. Return an empty iterator if /// it has no dependencies, or is not in this map. pub fn edges_to(&self, feature: &str) -> impl Iterator + '_ + use<'_> { match self.depended_on_by.get(feature) { Some(set) => itertools::Either::Left(set.iter().cloned()), None => itertools::Either::Right(std::iter::empty()), } } }