PmCheck: Formulate as translation between Clause Trees
We used to check
GrdVecs arising from multiple clauses and guards in
isolation. That resulted in a split between
pmCheckGuards, the implementations of which were similar, but subtly
different in detail. Also the throttling mechanism described in
Note [Countering exponential blowup] ultimately got quite complicated
because it had to cater for both checking functions.
This patch realises that pattern match checking doesn't just consider
single guarded RHSs, but that it's always a whole set of clauses, each
of which can have multiple guarded RHSs in turn. We do so by
translating a list of
Matches to a
data GrdTree = Rhs !RhsInfo | Sequence !GrdTree !GrdTree -- captures top-to-bottom match semantics | Guard !PmGrd !GrdTree -- captures lef-to-right match semantics | Empty -- For -XEmptyCase, neutral element of Sequence
Then we have a function
checkGrdTree that matches a given
against an incoming set of values, represented by
checkGrdTree :: GrdTree -> Deltas -> CheckResult ...
Throttling is isolated to the
Sequence case and becomes as easy as one
would expect: When the union of uncovered values becomes too big, just
return the original incoming
Deltas instead (which is always a
superset of the union, thus a sound approximation).
CheckResult contains two things:
- The set of values that were not covered by any of the clauses, for exhaustivity warnings.
AnnotatedTreethat enriches the syntactic structure of the input program with divergence and inaccessibility information.
data AnnotatedTree = AccessibleRhs !RhsInfo | InaccessibleRhs !RhsInfo | MayDiverge !AnnotatedTree | SequenceAnn !AnnotatedTree !AnnotatedTree | EmptyAnn
MayDiverge asserts that the tree may force diverging
values, so not all of its wrapped clauses can be redundant.
While the set of uncovered values can be used to generate the missing
equations for warning messages, redundant and proper inaccessible
equations can be extracted from
For this to work properly, the interface to the Oracle had to change.
addPmCts now, which takes a bag of
PmCts. There's a
whole bunch of
PmCt variants to replace the different oracle functions
AnnotatedTree structure allows for more accurate warning
reporting (as evidenced by a number of changes spread throughout GHC's
code base), thus we fix #17465 (closed).
Fixes #17646 (closed) on the go.