| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Fixes non-determinism within the DPLL algorithm and disallows
infeasible counter examples directly in the formula.
The function to compute all solutions was flawed and thus only
returned a subset of the solutions. The algorithm would stop too soon
and thus depending on the ordering of the symbols return more or less
solutions. I also added printing a warning when the search was stopped
because the max recursion depth was reached. This is very useful as an
explanation of spuriously failing regression tests, since less counter
examples might be reported. In such a case the recursion depth should
be set to infinite by adding `-Ypatmat-exhaust-depth off`.
The mapping of the solutions of the DPLL algorithm to counter examples
has been adapted to take the additional solutions from the
solver into account:
Consider for example `t8430.scala`:
```Scala
sealed trait CL3Literal
case object IntLit extends CL3Literal
case object CharLit extends CL3Literal
case object BooleanLit extends CL3Literal
case object UnitLit extends CL3Literal
sealed trait Tree
case class LetL(value: CL3Literal) extends Tree
case object LetP extends Tree
case object LetC extends Tree
case object LetF extends Tree
object Test {
(tree: Tree) => tree match {case LetL(CharLit) => ??? }
}
```
This test contains 2 domains, `IntLit, CharLit, ...` and `LetL, LetP, ...`,
the corresponding formula to check exhaustivity looks like:
```
V1=LetC.type#13 \/ V1=LetF.type#14 \/ V1=LetL#11 \/ V1=LetP.type#15 /\
V2=BooleanLit.type#16 \/ V2=CharLit#12 \/ V2=IntLit.type#17 \/ V2=UnitLit.type#18 /\
-V1=LetL#11 \/ -V2=CharLit#12 \/ \/
```
The first two lines assign a value of the domain to the scrutinee (and
the correponding member in case of `LetL`) and prohibit the counter
example `LetL(CharLit)` since it's covered by the pattern match. The
used Boolean encoding allows that scrutinee `V1` can be equal to
`LetC` and `LetF` at the same time and thus, during enumeration of all
possible solutions of the formula, such a solution will be found,
since only one literal needs to be set to true, to satisfy that
clause. That means, if at least one of the literals of such a clause
was in the `unassigned` list of the DPLL procedure, we will get
solutions where the scrutinee is equal to more than one element of the
domain.
A remedy would be to add constraints that forbid both literals
to be true at the same time. His is infeasible for big domains (see
`pos/t8531.scala`), since we would have to add a quadratic number of
clauses (one clause for each pair in the domain). A much simpler
solution is to just filter the invalid results. Since both values for
`unassigned` literals are explored, we will eventually find a valid
counter example.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
We check exhaustivity by representing a match as a formula in
finite-domain propositional logic (FDPL) that is false when
the match may fail. The variables in the formula represent
tested trees in the match (type tests/value equality tests).
The approximation uses the same framework as the CSE analysis.
A matrix of tree makers is turned into a DAG, where sharing
represents the same value/type being tested.
We reduce FDPL to Boolean PL as follows.
For all assignments, V_i = c_i_j, we introduce a proposition
P_i_j that is true iff V_i is equal to the constant c_i_j,
for a given i, and all j, P_i_j are mutually exclusive
(a variable cannot have multiple values).
If the variable's domain is closed, we assert that one of P_i_j
must be true for each i and some j. The conjunction of these
propositions constitutes the equality axioms.
After going through negational normal form to conjunctive normal
form, we use a small SAT solver (the DPLL algorithm) to find
a model under which the equational axioms hold but the match fails.
The formula: EqAxioms /\ -MatchSucceeds.
Note that match failure expresses nicely in CNF: the
negation of each case (which yields a disjunction) is anded.
We then turn this model into variable assignments
(what's the variable (not) equal to, along with recursive
assignments for its fields). Valid assignments (no ill-typed
field assignments) are then presented to the user as counter examples.
A counter example is a value, a type test, a constructor call
or a wildcard. We prune the example set and only report the
most general examples. (Finally, we sort the output to yield stable,
i.e. testable, warning messages.)
A match is only checked for exhaustivity when the type of the
selector is "checkable" (has a sealed type or is a tuple
with at least one component of sealed type).
We consider statically known guard outcomes, but generally back
off (don't check exhaustivity) when a match has guards
or user-defined extractor calls. (Sometimes constant folding
lets us statically decide a guard.)
We ignore possibly failing null checks (which are performed
before calling extractors, for example), though this could
be done easily in the current framework. The problem is false
positives. People don't usually put nulls in tuples or lists.
To improve the exhaustivity checks, we rewrite `List()` to Nil.
TODO: more general rewrite of List(a, b, ..., z) to `a :: b :: ... :: z`.
When presenting counter examples, we represent lists in the
user-friendly List(a,...,z) format. (Similarly for tuples.)
There are no exhaustivity checks for a match-defined PartialFunction.
misc notes:
- fix pure case of dpll solver
impure set (symbol that occurs both as a positive and negative literal)
was always empty since I was looking for literals (which are not equal if positivity is not equal)
but should have been looking for symbols
- FDPL -> BoolPL translation collects all syms in props
since propForEqualsTo generates an Or, must traverse the prop
rather than assuming only top-level Syms are relevant...
also, propForEqualsTo will not assume Or'ing a whole domain is equivalent to True
(which it isn't, since the type test may fail in general)
- improve counter example description
- treat as constructor call when we either have definite type information about a real class,
or we have no equality information at all, but the variable's type is a class
and we gathered constraints about its fields (typically when selector is a tuple)
- flatten a :: b :: ... :: Nil to List(a, b, ...)
- don't print tuple constructor names, so instead of "Tuple2(a, b)", say "(a, b)"
- filter out more statically impossible subtypes
the static types convey more information than is actually checkable at run time
this is good, as it allows us to narrow down the subtypes of a sealed type,
however, when modeling the corresponding run-time checks we need to "erase" the
uncheckable parts (using existentials so that the types are still well-kinded),
so that we can use static subtyping as a sound model for dynamic type checks
- experimental java enum handling seals enum class
before, we created a refinement class as the placeholder for the sealed children
it seems more direct to use the enum class for that
this way, the new pattern matcher's exhaustiveness checker just works for java enums
|
