1
//! Graph manipulation code
2
//!
3
//! I had hoped to use petgraph, but it is optimized for efficiency over
4
//! usability, and I got lost in a maze of indices.
5

            
6
// @@ begin lint list maintained by maint/add_warning @@
7
#![cfg_attr(not(ci_arti_stable), allow(renamed_and_removed_lints))]
8
#![cfg_attr(not(ci_arti_nightly), allow(unknown_lints))]
9
#![warn(missing_docs)]
10
#![warn(noop_method_call)]
11
#![warn(unreachable_pub)]
12
#![warn(clippy::all)]
13
#![deny(clippy::await_holding_lock)]
14
#![deny(clippy::cargo_common_metadata)]
15
#![deny(clippy::cast_lossless)]
16
#![deny(clippy::checked_conversions)]
17
#![warn(clippy::cognitive_complexity)]
18
#![deny(clippy::debug_assert_with_mut_call)]
19
#![deny(clippy::exhaustive_enums)]
20
#![deny(clippy::exhaustive_structs)]
21
#![deny(clippy::expl_impl_clone_on_copy)]
22
#![deny(clippy::fallible_impl_from)]
23
#![deny(clippy::implicit_clone)]
24
#![deny(clippy::large_stack_arrays)]
25
#![warn(clippy::manual_ok_or)]
26
#![deny(clippy::missing_docs_in_private_items)]
27
#![warn(clippy::needless_borrow)]
28
#![warn(clippy::needless_pass_by_value)]
29
#![warn(clippy::option_option)]
30
#![deny(clippy::print_stderr)]
31
#![deny(clippy::print_stdout)]
32
#![warn(clippy::rc_buffer)]
33
#![deny(clippy::ref_option_ref)]
34
#![warn(clippy::semicolon_if_nothing_returned)]
35
#![warn(clippy::trait_duplication_in_bounds)]
36
#![deny(clippy::unchecked_duration_subtraction)]
37
#![deny(clippy::unnecessary_wraps)]
38
#![warn(clippy::unseparated_literal_suffix)]
39
#![deny(clippy::unwrap_used)]
40
#![allow(clippy::let_unit_value)] // This can reasonably be done for explicitness
41
#![allow(clippy::uninlined_format_args)]
42
#![allow(clippy::significant_drop_in_scrutinee)] // arti/-/merge_requests/588/#note_2812945
43
#![allow(clippy::result_large_err)] // temporary workaround for arti#587
44
#![allow(clippy::needless_raw_string_hashes)] // complained-about code is fine, often best
45
//! <!-- @@ end lint list maintained by maint/add_warning @@ -->
46

            
47
// @@ begin test lint list maintained by maint/add_warning @@
48
#![allow(clippy::bool_assert_comparison)]
49
#![allow(clippy::clone_on_copy)]
50
#![allow(clippy::dbg_macro)]
51
#![allow(clippy::mixed_attributes_style)]
52
#![allow(clippy::print_stderr)]
53
#![allow(clippy::print_stdout)]
54
#![allow(clippy::single_char_pattern)]
55
#![allow(clippy::unwrap_used)]
56
#![allow(clippy::unchecked_duration_subtraction)]
57
#![allow(clippy::useless_vec)]
58
#![allow(clippy::needless_pass_by_value)]
59
//! <!-- @@ end test lint list maintained by maint/add_warning @@ -->
60

            
61
#![allow(clippy::missing_docs_in_private_items)]
62
#![allow(unreachable_pub)]
63

            
64
use anyhow::{anyhow, Result};
65
use std::collections::{HashMap, HashSet};
66
use std::hash::Hash;
67

            
68
/// Given a hashmap representing a binary relationship, compute its transitive closure.
69
fn transitive_closure<K: Hash + Eq + PartialEq + Clone>(
70
    inp: &HashMap<K, HashSet<K>>,
71
) -> HashMap<K, HashSet<K>> {
72
    let mut out = inp.clone();
73
    let max_iters = inp.len();
74
    for _ in 0..max_iters {
75
        let mut new_out = out.clone();
76
        for (k, vs) in out.iter() {
77
            let new_vs = new_out
78
                .get_mut(k)
79
                .expect("That key should have been there when I cloned it...");
80
            for v in vs.iter() {
81
                if let Some(vv) = out.get(v) {
82
                    new_vs.extend(vv.iter().cloned());
83
                }
84
            }
85
        }
86
        if out == new_out {
87
            break;
88
        } else {
89
            out = new_out;
90
        }
91
    }
92
    out
93
}
94

            
95
/// Given a hashmap representing a binary relationship, invert it.
96
fn invert<K: Hash + Eq + PartialEq + Clone>(
97
    inp: &HashMap<K, HashSet<K>>,
98
) -> HashMap<K, HashSet<K>> {
99
    let mut out: HashMap<K, HashSet<K>> = HashMap::new();
100
    for (k, vs) in inp.iter() {
101
        for v in vs {
102
            out.entry(v.clone()).or_default().insert(k.clone());
103
        }
104
    }
105
    out
106
}
107

            
108
/// A representation of which features depend on what.
109
#[derive(Clone, Debug, Default)]
110
pub struct FeatureGraph {
111
    /// List of all features.
112
    all_features: HashSet<String>,
113
    /// Adjacency map: for each feature F, `depends_on[F]` includes G if F
114
    /// directly depends on G.
115
    depends_on: HashMap<String, HashSet<String>>,
116
    /// Inverse adjacency map.
117
    depended_on_by: HashMap<String, HashSet<String>>,
118
    /// Transitive closure of the adjacency map.
119
    reachable_from: HashMap<String, HashSet<String>>,
120
}
121

            
122
impl FeatureGraph {
123
    /// Convert a toml `[features]` section into a [`FeatureGraph`].
124
    pub fn from_features_table(features: &toml_edit::Table) -> Result<Self> {
125
        let mut depends_on = HashMap::new();
126
        for (k, vs) in features.iter() {
127
            let mut d = HashSet::new();
128
            for v in vs
129
                .as_array()
130
                .ok_or_else(|| anyhow!("features.{} was not an array", k))?
131
            {
132
                let v = v
133
                    .as_str()
134
                    .ok_or_else(|| anyhow!("features.{} contained a non-string", k))?;
135
                d.insert(v.to_string());
136
            }
137
            depends_on.insert(k.to_string(), d);
138
        }
139
        let all_features = depends_on.keys().cloned().collect();
140
        let reachable_from = transitive_closure(&depends_on);
141
        let depended_on_by = invert(&depends_on);
142
        Ok(Self {
143
            all_features,
144
            depends_on,
145
            depended_on_by,
146
            reachable_from,
147
        })
148
    }
149

            
150
    pub fn all_features(&self) -> impl Iterator<Item = String> + '_ {
151
        self.depends_on.keys().cloned()
152
    }
153

            
154
    pub fn contains_feature(&self, feature: &str) -> bool {
155
        self.all_features.contains(feature)
156
    }
157

            
158
    pub fn contains_edge(&self, from: &str, to: &str) -> bool {
159
        match self.depends_on.get(from) {
160
            Some(fs) => fs.contains(to),
161
            None => false,
162
        }
163
    }
164

            
165
    pub fn all_reachable_from(&self, feature: &str) -> impl Iterator<Item = String> + '_ {
166
        match self.reachable_from.get(feature) {
167
            Some(set) => itertools::Either::Left(set.iter().cloned()),
168
            None => itertools::Either::Right(std::iter::empty()),
169
        }
170
    }
171

            
172
    /// Return all the features that `feature` depends on.  Return an empty iterator if
173
    /// it has no dependencies, or is not in this map.
174
    pub fn edges_from(&self, feature: &str) -> impl Iterator<Item = String> + '_ {
175
        match self.depends_on.get(feature) {
176
            Some(set) => itertools::Either::Left(set.iter().cloned()),
177
            None => itertools::Either::Right(std::iter::empty()),
178
        }
179
    }
180

            
181
    /// Return all the features that depend on `feature` directly.  Return an empty iterator if
182
    /// it has no dependencies, or is not in this map.
183
    pub fn edges_to(&self, feature: &str) -> impl Iterator<Item = String> + '_ {
184
        match self.depended_on_by.get(feature) {
185
            Some(set) => itertools::Either::Left(set.iter().cloned()),
186
            None => itertools::Either::Right(std::iter::empty()),
187
        }
188
    }
189
}