expectation_graph/
precedence.rs

1//! Exceptions. `Overrides: X` says "where we both apply, I win". Overrides must form a DAG:
2//! a cycle would have two expectations each winning over the other.
3
4use expectation_model::{Diagnostic, ExpId, Suite};
5
6pub struct Precedence {
7    /// `beats[w][l]`: `w` wins over `l`, directly or through a chain of overrides.
8    beats: Vec<Vec<bool>>,
9    /// The `Overrides:` lines as written: (winner, loser).
10    pub declared: Vec<(ExpId, ExpId)>,
11}
12
13impl Precedence {
14    pub fn beats(&self, winner: ExpId, loser: ExpId) -> bool {
15        self.beats.get(winner.0 as usize).and_then(|r| r.get(loser.0 as usize)).copied().unwrap_or(false)
16    }
17
18    /// Expectations that win over `e`.
19    pub fn winners_over(&self, e: ExpId) -> Vec<ExpId> {
20        (0..self.beats.len()).filter(|&w| self.beats[w][e.0 as usize]).map(|w| ExpId(w as u32)).collect()
21    }
22}
23
24pub fn build(suite: &Suite) -> (Precedence, Vec<Diagnostic>) {
25    let n = suite.expectations.len();
26    let declared: Vec<(ExpId, ExpId)> =
27        suite.expectations.iter().flat_map(|e| e.overrides.iter().map(move |l| (e.id, *l))).collect();
28    let mut adj = vec![vec![]; n];
29    for (w, l) in &declared {
30        adj[w.0 as usize].push(l.0 as usize);
31    }
32
33    let mut beats = vec![vec![false; n]; n];
34    for (start, row) in beats.iter_mut().enumerate() {
35        let mut stack = adj[start].clone();
36        while let Some(x) = stack.pop() {
37            if !row[x] {
38                row[x] = true;
39                stack.extend(&adj[x]);
40            }
41        }
42    }
43
44    let mut diags = vec![];
45    let mut reported = vec![false; n];
46    for start in 0..n {
47        if !beats[start][start] || reported[start] {
48            continue;
49        }
50        let cycle = find_cycle(&adj, start);
51        for &c in &cycle {
52            reported[c] = true;
53        }
54        let names: Vec<String> = cycle.iter().map(|&c| format!("«{}»", suite.expectations[c].name)).collect();
55        let mut d = Diagnostic::error("override-cycle", "these expectations override each other in a circle")
56            .note_that(format!("{} → {}", names.join(" → "), names[0]))
57            .help("an exception has to be more specific than what it overrides; remove one of the Overrides lines");
58        for &c in &cycle {
59            d = d.at(&suite.expectations[c].span, "");
60        }
61        diags.push(d);
62    }
63    (Precedence { beats, declared }, diags)
64}
65
66/// The nodes of one cycle through `start`, in order.
67fn find_cycle(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
68    fn walk(adj: &[Vec<usize>], at: usize, start: usize, path: &mut Vec<usize>, seen: &mut [bool]) -> bool {
69        for &next in &adj[at] {
70            if next == start {
71                return true;
72            }
73            if !seen[next] {
74                seen[next] = true;
75                path.push(next);
76                if walk(adj, next, start, path, seen) {
77                    return true;
78                }
79                path.pop();
80            }
81        }
82        false
83    }
84    let mut path = vec![start];
85    let mut seen = vec![false; adj.len()];
86    walk(adj, start, start, &mut path, &mut seen);
87    path
88}
expectation_graph/precedence.rs

expectation_graph/
precedence.rs
