c3_inheritance/c3/
algorithm.rs

1use super::*;
2
3impl<'a> InheritLinearized<'a> {
4    fn new(graph: &'a InheritGraph) -> Self {
5        Self { graph, maps: BTreeMap::new() }
6    }
7    fn insert(&mut self, name: &'a str, value: Vec<&'a str>) {
8        self.maps.insert(name, value.to_vec());
9    }
10    /// Get the linearization for a class.
11    pub fn mro(&self, name: &str) -> Option<&[&'a str]> {
12        Some(self.maps.get(name)?.as_slice())
13    }
14    /// Check if A is a B
15    pub fn is_ancestor(&self, this: &str, ancestor: &str) -> Option<bool> {
16        Some(self.maps.get(this)?.contains(&ancestor))
17    }
18}
19
20impl InheritGraph {
21    /// Linearize the inheritance graph.
22    pub fn linearize(&self) -> LinearizeResult<InheritLinearized> {
23        let mut results = InheritLinearized::new(self);
24        for (head, _) in &self.base {
25            c3_linearize(self, head, &mut results, &mut BTreeMap::new())?;
26        }
27        Ok(results)
28    }
29    fn get_base(&self, name: &str) -> Option<&[BaseClass]> {
30        Some(self.base.get(name)?.base.as_slice())
31    }
32    /// Check if the graph has at least one base class.
33    pub fn has_base(&self, class: &str) -> Option<bool> {
34        Some(!self.base.get(class)?.base.is_empty())
35    }
36}
37
38fn c3_linearize<'a>(
39    graph: &'a InheritGraph,
40    head: &'a str,
41    results: &mut InheritLinearized<'a>,
42    visiting: &mut BTreeMap<&'a str, bool>,
43) -> LinearizeResult<Vec<&'a str>> {
44    if let Some(res) = results.mro(head) {
45        return Ok(res.to_vec());
46    }
47    check_circle(head, visiting)?;
48    visiting.insert(head, true);
49
50    let parents = graph.get_base(head).unwrap();
51
52    if parents.is_empty() {
53        let res = vec![head];
54        results.insert(head, res.clone());
55        return Ok(res);
56    }
57
58    let mut sequences = Vec::new();
59    for parent in parents {
60        let sequence = c3_linearize(graph, &parent.class, results, visiting)?;
61        sequences.push(sequence);
62    }
63
64    if let Some(false) = graph.has_base(head) {
65        sequences.push(vec![head]);
66    }
67
68    let res = vec![head].into_iter().chain(merge(sequences)?).collect::<Vec<_>>();
69    results.insert(head, res.clone());
70
71    visiting.remove(head);
72
73    Ok(res)
74}
75
76fn merge(sequences: Vec<Vec<&str>>) -> LinearizeResult<Vec<&str>> {
77    let mut result = Vec::new();
78    let mut sequences = sequences.into_iter().map(|s| s.into_iter().collect::<Vec<&str>>()).collect::<Vec<_>>();
79
80    while !sequences.is_empty() {
81        let mut found = false;
82        let mut head = None;
83
84        for seq in &sequences {
85            head = seq.first().cloned();
86
87            fn is_bad_head(seq: &&Vec<&str>, s: &&Vec<&str>) -> bool {
88                s != seq && s[1..].contains(&seq[0])
89            }
90
91            if !sequences.iter().any(|s| is_bad_head(&seq, &s)) {
92                found = true;
93                if let Some(head) = head {
94                    result.push(head);
95
96                    for seq in &mut sequences {
97                        if let Some(index) = seq.iter().position(|&x| x == head) {
98                            seq.remove(index);
99                        }
100                    }
101
102                    break;
103                }
104            }
105        }
106
107        sequences = sequences.into_iter().filter(|s| !s.is_empty()).collect::<Vec<_>>();
108
109        if !found {
110            return Err(LinearizeError::NotFound { base: head.unwrap().to_string() });
111        }
112    }
113
114    Ok(result)
115}
116
117fn check_circle(head: &str, visiting: &BTreeMap<&str, bool>) -> LinearizeResult<()> {
118    for item in visiting.keys() {
119        if head.eq(*item) {
120            return Err(LinearizeError::Circular { class: head.to_string() });
121        }
122    }
123    Ok(())
124}
c3_inheritance/c3/algorithm.rs

c3_inheritance/c3/
algorithm.rs
