cranelift_isle/
overlap.rs

1//! Overlap detection for rules in ISLE.
2
3use std::collections::hash_map::Entry;
4use std::collections::{HashMap, HashSet};
5
6use crate::error::{Error, Span};
7use crate::lexer::Pos;
8use crate::sema::{TermEnv, TermId, TermKind};
9use crate::trie_again;
10
11/// Check for overlap.
12pub fn check(termenv: &TermEnv) -> Result<Vec<(TermId, trie_again::RuleSet)>, Vec<Error>> {
13    let (terms, mut errors) = trie_again::build(termenv);
14    errors.append(&mut check_overlaps(&terms, termenv).report());
15
16    if errors.is_empty() {
17        Ok(terms)
18    } else {
19        Err(errors)
20    }
21}
22
23/// A graph of rules that overlap in the ISLE source. The edges are undirected.
24#[derive(Default)]
25struct Errors {
26    /// Edges between rules indicating overlap.
27    nodes: HashMap<Pos, HashSet<Pos>>,
28    /// For each (mask, shadowed) pair, every rule in `shadowed` is unmatchable because `mask` will
29    /// always match first.
30    shadowed: HashMap<Pos, Vec<Pos>>,
31}
32
33impl Errors {
34    /// Condense the overlap information down into individual errors. We iteratively remove the
35    /// nodes from the graph with the highest degree, reporting errors for them and their direct
36    /// connections. The goal with reporting errors this way is to prefer reporting rules that
37    /// overlap with many others first, and then report other more targeted overlaps later.
38    fn report(mut self) -> Vec<Error> {
39        let mut errors = Vec::new();
40
41        while let Some((&pos, _)) = self
42            .nodes
43            .iter()
44            .max_by_key(|(pos, edges)| (edges.len(), *pos))
45        {
46            let node = self.nodes.remove(&pos).unwrap();
47            for other in node.iter() {
48                if let Entry::Occupied(mut entry) = self.nodes.entry(*other) {
49                    let back_edges = entry.get_mut();
50                    back_edges.remove(&pos);
51                    if back_edges.is_empty() {
52                        entry.remove();
53                    }
54                }
55            }
56
57            // build the real error
58            let mut rules = vec![Span::new_single(pos)];
59
60            rules.extend(node.into_iter().map(Span::new_single));
61
62            errors.push(Error::OverlapError {
63                msg: String::from("rules are overlapping"),
64                rules,
65            });
66        }
67
68        errors.extend(
69            self.shadowed
70                .into_iter()
71                .map(|(mask, shadowed)| Error::ShadowedError {
72                    shadowed: shadowed.into_iter().map(Span::new_single).collect(),
73                    mask: Span::new_single(mask),
74                }),
75        );
76
77        errors.sort_by_key(|err| match err {
78            Error::ShadowedError { mask, .. } => mask.from,
79            Error::OverlapError { rules, .. } => rules[0].from,
80            _ => Pos::default(),
81        });
82        errors
83    }
84
85    fn check_pair(&mut self, a: &trie_again::Rule, b: &trie_again::Rule) {
86        if let trie_again::Overlap::Yes { subset } = a.may_overlap(b) {
87            if a.prio == b.prio {
88                // edges are undirected
89                self.nodes.entry(a.pos).or_default().insert(b.pos);
90                self.nodes.entry(b.pos).or_default().insert(a.pos);
91            } else if subset {
92                // One rule's constraints are a subset of the other's, or they're equal.
93                // This is fine as long as the higher-priority rule has more constraints.
94                let (lo, hi) = if a.prio < b.prio { (a, b) } else { (b, a) };
95                if hi.total_constraints() <= lo.total_constraints() {
96                    // Otherwise, the lower-priority rule can never match.
97                    self.shadowed.entry(hi.pos).or_default().push(lo.pos);
98                }
99            }
100        }
101    }
102}
103
104/// Determine if any rules overlap in the input that they accept. This checks every unique pair of
105/// rules, as checking rules in aggregate tends to suffer from exponential explosion in the
106/// presence of wildcard patterns.
107fn check_overlaps(terms: &[(TermId, trie_again::RuleSet)], env: &TermEnv) -> Errors {
108    let mut errs = Errors::default();
109    for (tid, ruleset) in terms {
110        let is_multi_ctor = match &env.terms[tid.index()].kind {
111            TermKind::Decl { flags, .. } => flags.multi,
112            _ => false,
113        };
114        if is_multi_ctor {
115            // Rules for multi-constructors are not checked for
116            // overlap: the ctor returns *every* match, not just
117            // the first or highest-priority one, so overlap does
118            // not actually affect the results.
119            continue;
120        }
121
122        let mut cursor = ruleset.rules.iter();
123        while let Some(left) = cursor.next() {
124            for right in cursor.as_slice() {
125                errs.check_pair(left, right);
126            }
127        }
128    }
129    errs
130}
cranelift_isle/overlap.rs

cranelift_isle/
overlap.rs
