diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2013-07-16 12:06:43 +1000 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2013-07-17 09:55:38 +1000 |
commit | 635892e34119d2e4b82fbced5b9d8cbd6dd064b7 (patch) | |
tree | d1b5586f0c53d6de258d095267f7d211aad180a0 /src/compiler | |
parent | 11dcf82910b388046e675d76d277b09b931d5363 (diff) | |
download | scala-635892e34119d2e4b82fbced5b9d8cbd6dd064b7.tar.gz scala-635892e34119d2e4b82fbced5b9d8cbd6dd064b7.tar.bz2 scala-635892e34119d2e4b82fbced5b9d8cbd6dd064b7.zip |
SI-7669 Fix exhaustivity warnings for recursive ADTs.
The pattern matcher's analysis was correctly finding
models under which the match in the enclosed test
could fail. But, when trying to render that model
as a counter example, it ran into an internal inconsistency
and gave up.
That inconsistency arose from VariableAssignment, which:
> turn the variable assignments into a tree
> the root is the scrutinee (x1), edges are labelled
> by the fields that are assigned a node is a variable
> example (which is later turned into a counter example)
In the process, it notes the unreachable case `V2 = NotHandled`,
which can only arise if `V1 = Op`, ie the scrutinee is `Op(NotHandled())`.
V2 is assosicated with the path `x1.arg`. The code then looked for
any variable assosicated with the prefix `x1` and registered that its
field `arg` was assosicated with this variable assignment.
However, the assignment for `V1 = NotHandled` (another missing case)
is also associated with the path `x1`. Registering this field makes
no sense here; we should only do that for `Op`.
This commit conditionally registers the fields based on the class
of `VariableAssignment#cls`. We no longer hit the inconsistency in
`VariableAssignment#allFieldAssignmentsLegal`.
This favourably changes the results of two existing tests.
I had to tweak the counter example pruning to avoid relying on
CounterExample.==, which is flaky in the light of Nil and List().
It is possible to have:
A, B where A != B && A.coveredBy(B) && B.coveredBy(A)
Luckily it is straightforward to implement pruning entirely with
coveredBy.
Diffstat (limited to 'src/compiler')
-rw-r--r-- | src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala | 21 |
1 files changed, 16 insertions, 5 deletions
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala index f527c30b8a..f089c8f5a5 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala @@ -488,8 +488,13 @@ trait MatchAnalysis extends MatchApproximation { object CounterExample { def prune(examples: List[CounterExample]): List[CounterExample] = { - val distinct = examples.filterNot(_ == NoExample).toSet - distinct.filterNot(ce => distinct.exists(other => (ce ne other) && ce.coveredBy(other))).toList + // SI-7669 Warning: we don't used examples.distinct here any more as + // we can have A != B && A.coveredBy(B) && B.coveredBy(A) + // with Nil and List(). + val result = mutable.Buffer[CounterExample]() + for (example <- examples if (!result.exists(example coveredBy _))) + result += example + result.toList } } @@ -591,7 +596,7 @@ trait MatchAnalysis extends MatchApproximation { private def unique(variable: Var): VariableAssignment = uniques.getOrElseUpdate(variable, { val (eqTo, neqTo) = varAssignment.getOrElse(variable, (Nil, Nil)) // TODO - VariableAssignment(variable, eqTo.toList, neqTo.toList, mutable.HashMap.empty) + VariableAssignment(variable, eqTo.toList, neqTo.toList) }) def apply(variable: Var): VariableAssignment = { @@ -605,7 +610,7 @@ trait MatchAnalysis extends MatchApproximation { else { findVar(pre) foreach { preVar => val outerCtor = this(preVar) - outerCtor.fields(field) = newCtor + outerCtor.addField(field, newCtor) } newCtor } @@ -613,7 +618,8 @@ trait MatchAnalysis extends MatchApproximation { } // node in the tree that describes how to construct a counter-example - case class VariableAssignment(variable: Var, equalTo: List[Const], notEqualTo: List[Const], fields: scala.collection.mutable.Map[Symbol, VariableAssignment]) { + case class VariableAssignment(variable: Var, equalTo: List[Const], notEqualTo: List[Const]) { + private val fields: mutable.Map[Symbol, VariableAssignment] = mutable.HashMap.empty // need to prune since the model now incorporates all super types of a constant (needed for reachability) private lazy val uniqueEqualTo = equalTo filterNot (subsumed => equalTo.exists(better => (better ne subsumed) && instanceOfTpImplies(better.tp, subsumed.tp))) private lazy val prunedEqualTo = uniqueEqualTo filterNot (subsumed => variable.staticTpCheckable <:< subsumed.tp) @@ -622,6 +628,11 @@ trait MatchAnalysis extends MatchApproximation { private lazy val cls = if (ctor == NoSymbol) NoSymbol else ctor.owner private lazy val caseFieldAccs = if (cls == NoSymbol) Nil else cls.caseFieldAccessors + def addField(symbol: Symbol, assign: VariableAssignment) { + // SI-7669 Only register this field if if this class contains it. + val shouldConstrainField = !symbol.isCaseAccessor || caseFieldAccs.contains(symbol) + if (shouldConstrainField) fields(symbol) = assign + } def allFieldAssignmentsLegal: Boolean = (fields.keySet subsetOf caseFieldAccs.toSet) && fields.values.forall(_.allFieldAssignmentsLegal) |