knave 0.14.16

A Lisp programming language for humans and agents that infers types and ownership and compiles to readable Rust
Documentation 
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
138
139
140
141
142

mod column_head;
mod constructor;
mod constructor_catalog;
mod constructor_tag;
mod cover_pattern;
mod coverage_verdict;
mod exhaustiveness;
mod missing_case_search;
mod pattern_guard;
mod pattern_matrix;
mod query;
#[cfg(test)]
mod search_fixture;
mod unreachable_arm;
mod usefulness;
mod witness;
mod witness_text;

use rustc_hash::FxHashSet;

pub(super) use constructor_catalog::ConstructorCatalog;
use cover_pattern::CoverPattern;
use coverage_verdict::CoverageVerdict;
use exhaustiveness::Exhaustiveness;
use missing_case_search::MissingCaseSearch;
use pattern_guard::PatternGuard;
use pattern_matrix::PatternMatrix;
use query::Query;
use unreachable_arm::UnreachableArm;
use usefulness::Usefulness;
pub(super) use witness_text::WitnessText;

use crate::core::BindingArena;
use crate::source::Span;
use crate::types::{Type, TypedArm};

pub(super) struct MatchCoverage<'a> {
    bindings: &'a BindingArena,
    catalog: ConstructorCatalog<'a>,
    text: WitnessText<'a>,
}

impl<'a> MatchCoverage<'a> {
    pub(super) fn new(
        bindings: &'a BindingArena,
        catalog: ConstructorCatalog<'a>,
        text: WitnessText<'a>,
    ) -> Self {
        Self {
            bindings,
            catalog,
            text,
        }
    }

    pub(super) fn judge(&self, scrutinee: &Type, arms: &[TypedArm]) -> CoverageVerdict {
        let scrutinee = self.catalog.peeled(scrutinee);
        let usefulness = Usefulness::new(&self.catalog);
        let mut matrix = PatternMatrix::default();
        let mut unreachable_arms = Vec::new();
        for (position, arm) in arms.iter().enumerate() {
            let pattern = CoverPattern::of(&arm.pattern, self.bindings);
            if usefulness.is_useful(&matrix, Self::single_query(&pattern, &scrutinee)) {
                matrix.push(pattern);
            } else {
                unreachable_arms.push(UnreachableArm {
                    pattern: arm.pattern.span,
                    covered_by: self.covering_arm(&arms[..position], &pattern, &scrutinee),
                });
            }
        }
        let exhaustiveness = match self.missing_cases(&usefulness, &matrix, scrutinee.clone()) {
            Some(cases) => Exhaustiveness::Missing(cases),
            None if self.is_exhaustive_without_guards(&usefulness, &scrutinee, arms) => {
                Exhaustiveness::Complete
            }
            None => Exhaustiveness::OnlyWithGuards,
        };
        CoverageVerdict::new(unreachable_arms, exhaustiveness)
    }

    fn single_query<'q>(pattern: &'q CoverPattern, scrutinee: &'q Type) -> Query<'q> {
        Query::new(
            std::slice::from_ref(pattern),
            std::slice::from_ref(scrutinee),
        )
    }

    fn covering_arm(
        &self,
        previous: &[TypedArm],
        pattern: &CoverPattern,
        scrutinee: &Type,
    ) -> Option<Span> {
        let usefulness = Usefulness::new(&self.catalog);
        previous
            .iter()
            .find(|arm| {
                let earlier: PatternMatrix =
                    std::iter::once(CoverPattern::of(&arm.pattern, self.bindings)).collect();
                !usefulness.is_useful(&earlier, Self::single_query(pattern, scrutinee))
            })
            .map(|arm| arm.pattern.span)
    }

    fn missing_cases(
        &self,
        usefulness: &Usefulness,
        matrix: &PatternMatrix,
        scrutinee: Type,
    ) -> Option<Vec<String>> {
        let wild = CoverPattern::wild();
        if !usefulness.is_useful(matrix, Self::single_query(&wild, &scrutinee)) {
            return None;
        }
        let mut seen = FxHashSet::default();
        let cases = MissingCaseSearch::new(&self.catalog)
            .witnesses(matrix, &[scrutinee])
            .iter()
            .map(|row| self.text.show(&row[0]))
            .filter(|case| seen.insert(case.clone()))
            .collect();
        Some(cases)
    }

    fn is_exhaustive_without_guards(
        &self,
        usefulness: &Usefulness,
        scrutinee: &Type,
        arms: &[TypedArm],
    ) -> bool {
        let unguarded: PatternMatrix = arms
            .iter()
            .filter(|arm| !PatternGuard::of(&arm.pattern).is_needed())
            .map(|arm| CoverPattern::of(&arm.pattern, self.bindings))
            .collect();
        !usefulness.is_useful(
            &unguarded,
            Self::single_query(&CoverPattern::wild(), scrutinee),
        )
    }
}