1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

//! Overlap detection for rules in ISLE.

use std::collections::hash_map::Entry;
use std::collections::{HashMap, HashSet};

use crate::error::{self, Error, Span};
use crate::lexer::Pos;
use crate::sema::{TermEnv, TermId, TermKind, TypeEnv};
use crate::trie_again;

/// Check for overlap.
pub fn check(
    tyenv: &TypeEnv,
    termenv: &TermEnv,
) -> Result<Vec<(TermId, trie_again::RuleSet)>, error::Errors> {
    let (terms, mut errors) = trie_again::build(termenv);
    errors.append(&mut check_overlaps(&terms, termenv).report());

    if errors.is_empty() {
        Ok(terms)
    } else {
        Err(error::Errors {
            errors,
            filenames: tyenv.filenames.clone(),
            file_texts: tyenv.file_texts.clone(),
        })
    }
}

/// A graph of rules that overlap in the ISLE source. The edges are undirected.
#[derive(Default)]
struct Errors {
    /// Edges between rules indicating overlap.
    nodes: HashMap<Pos, HashSet<Pos>>,
    /// For each (mask, shadowed) pair, every rule in `shadowed` is unmatchable because `mask` will
    /// always match first.
    shadowed: HashMap<Pos, Vec<Pos>>,
}

impl Errors {
    /// Condense the overlap information down into individual errors. We iteratively remove the
    /// nodes from the graph with the highest degree, reporting errors for them and their direct
    /// connections. The goal with reporting errors this way is to prefer reporting rules that
    /// overlap with many others first, and then report other more targeted overlaps later.
    fn report(mut self) -> Vec<Error> {
        let mut errors = Vec::new();

        while let Some((&pos, _)) = self
            .nodes
            .iter()
            .max_by_key(|(pos, edges)| (edges.len(), *pos))
        {
            let node = self.nodes.remove(&pos).unwrap();
            for other in node.iter() {
                if let Entry::Occupied(mut entry) = self.nodes.entry(*other) {
                    let back_edges = entry.get_mut();
                    back_edges.remove(&pos);
                    if back_edges.is_empty() {
                        entry.remove();
                    }
                }
            }

            // build the real error
            let mut rules = vec![Span::new_single(pos)];

            rules.extend(node.into_iter().map(Span::new_single));

            errors.push(Error::OverlapError {
                msg: String::from("rules are overlapping"),
                rules,
            });
        }

        errors.extend(
            self.shadowed
                .into_iter()
                .map(|(mask, shadowed)| Error::ShadowedError {
                    shadowed: shadowed.into_iter().map(Span::new_single).collect(),
                    mask: Span::new_single(mask),
                }),
        );

        errors.sort_by_key(|err| match err {
            Error::ShadowedError { mask, .. } => mask.from,
            Error::OverlapError { rules, .. } => rules[0].from,
            _ => Pos::default(),
        });
        errors
    }

    fn check_pair(&mut self, a: &trie_again::Rule, b: &trie_again::Rule) {
        if let trie_again::Overlap::Yes { subset } = a.may_overlap(b) {
            if a.prio == b.prio {
                // edges are undirected
                self.nodes.entry(a.pos).or_default().insert(b.pos);
                self.nodes.entry(b.pos).or_default().insert(a.pos);
            } else if subset {
                // One rule's constraints are a subset of the other's, or they're equal.
                // This is fine as long as the higher-priority rule has more constraints.
                let (lo, hi) = if a.prio < b.prio { (a, b) } else { (b, a) };
                if hi.total_constraints() <= lo.total_constraints() {
                    // Otherwise, the lower-priority rule can never match.
                    self.shadowed.entry(hi.pos).or_default().push(lo.pos);
                }
            }
        }
    }
}

/// Determine if any rules overlap in the input that they accept. This checks every unique pair of
/// rules, as checking rules in aggregate tends to suffer from exponential explosion in the
/// presence of wildcard patterns.
fn check_overlaps(terms: &[(TermId, trie_again::RuleSet)], env: &TermEnv) -> Errors {
    let mut errs = Errors::default();
    for (tid, ruleset) in terms {
        let is_multi_ctor = match &env.terms[tid.index()].kind {
            TermKind::Decl { flags, .. } => flags.multi,
            _ => false,
        };
        if is_multi_ctor {
            // Rules for multi-constructors are not checked for
            // overlap: the ctor returns *every* match, not just
            // the first or highest-priority one, so overlap does
            // not actually affect the results.
            continue;
        }

        let mut cursor = ruleset.rules.iter();
        while let Some(left) = cursor.next() {
            for right in cursor.as_slice() {
                errs.check_pair(left, right);
            }
        }
    }
    errs
}