diff options
author | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-07-17 14:37:16 -0700 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-07-17 14:37:16 -0700 |
commit | 4f07a12b3f4ce1595d4976123e5cfe34e186d4ba (patch) | |
tree | 05adc73031cbcbb462fc44a41f5df748cf0dff6b | |
parent | 0cfd858a38ddf0ac83d9bbefe85110f88dc707c0 (diff) | |
parent | 4276f61551b89162001dadbb3b77f29a85c19c4a (diff) | |
download | scala-4f07a12b3f4ce1595d4976123e5cfe34e186d4ba.tar.gz scala-4f07a12b3f4ce1595d4976123e5cfe34e186d4ba.tar.bz2 scala-4f07a12b3f4ce1595d4976123e5cfe34e186d4ba.zip |
Merge pull request #904 from adriaanm/ticket-6077
SI-6077 more conservative TreeMakersToConds for CSE
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala | 328 | ||||
-rw-r--r-- | test/files/run/t6077_patmat_cse_irrefutable.check | 1 | ||||
-rw-r--r-- | test/files/run/t6077_patmat_cse_irrefutable.scala | 13 |
3 files changed, 193 insertions, 149 deletions
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala index da45b9bde3..4e4176e531 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala @@ -47,8 +47,11 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL val phaseName: String = "patmat" // TODO: the inliner fails to inline the closures to patmatDebug - // private val printPatmat = settings.Ypatmatdebug.value - // @inline final def patmatDebug(s: => String) = if (printPatmat) println(s) + object debugging { + val printPatmat = settings.Ypatmatdebug.value + @inline final def patmatDebug(s: => String) = if (printPatmat) println(s) + } + import debugging.patmatDebug def newTransformer(unit: CompilationUnit): Transformer = if (opt.virtPatmat) new MatchTransformer(unit) @@ -185,7 +188,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // (that would require more sophistication when generating trees, // and the only place that emits Matches after typers is for exception handling anyway) if(phase.id >= currentRun.uncurryPhase.id) debugwarn("running translateMatch at "+ phase +" on "+ selector +" match "+ cases) - // patmatDebug ("translating "+ cases.mkString("{", "\n", "}")) + patmatDebug("translating "+ cases.mkString("{", "\n", "}")) def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match { case TypeRef(_, RepeatedParamClass, arg :: Nil) => seqType(arg) @@ -310,14 +313,14 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL if (!extractor.isTyped) ErrorUtils.issueNormalTypeError(patTree, "Could not typecheck extractor call: "+ extractor)(context) // if (extractor.resultInMonad == ErrorType) throw new TypeError(pos, "Unsupported extractor type: "+ extractor.tpe) - // patmatDebug ("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType)) + patmatDebug("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType)) // must use type `tp`, which is provided by extractor's result, not the type expected by binder, // as b.info may be based on a Typed type ascription, which has not been taken into account yet by the translation // (it will later result in a type test when `tp` is not a subtype of `b.info`) // TODO: can we simplify this, together with the Bound case? (extractor.subPatBinders, extractor.subPatTypes).zipped foreach { case (b, tp) => - // patmatDebug ("changing "+ b +" : "+ b.info +" -> "+ tp) + patmatDebug("changing "+ b +" : "+ b.info +" -> "+ tp) b setInfo tp } @@ -424,7 +427,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL */ case Bind(n, p) => // this happens in certain ill-formed programs, there'll be an error later - // patmatDebug ("WARNING: Bind tree with unbound symbol "+ patTree) + patmatDebug("WARNING: Bind tree with unbound symbol "+ patTree) noFurtherSubPats() // there's no symbol -- something's wrong... don't fail here though (or should we?) // case Star(_) | ArrayValue | This => error("stone age pattern relics encountered!") @@ -634,7 +637,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // binder has type paramType def treeMaker(binder: Symbol, pos: Position): TreeMaker = { // checks binder ne null before chaining to the next extractor - ProductExtractorTreeMaker(binder, lengthGuard(binder), Substitution(subPatBinders, subPatRefs(binder))) + ProductExtractorTreeMaker(binder, lengthGuard(binder))(Substitution(subPatBinders, subPatRefs(binder))) } // reference the (i-1)th case accessor if it exists, otherwise the (i-1)th tuple component @@ -678,7 +681,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // the extractor call (applied to the binder bound by the flatMap corresponding to the previous (i.e., enclosing/outer) pattern) val extractorApply = atPos(pos)(spliceApply(patBinderOrCasted)) val binder = freshSym(pos, pureType(resultInMonad)) // can't simplify this when subPatBinders.isEmpty, since UnitClass.tpe is definitely wrong when isSeq, and resultInMonad should always be correct since it comes directly from the extractor's result type - ExtractorTreeMaker(extractorApply, lengthGuard(binder), binder, Substitution(subPatBinders, subPatRefs(binder)))(resultType.typeSymbol == BooleanClass, checkedLength, patBinderOrCasted) + ExtractorTreeMaker(extractorApply, lengthGuard(binder), binder)(Substitution(subPatBinders, subPatRefs(binder)), resultType.typeSymbol == BooleanClass, checkedLength, patBinderOrCasted) } override protected def seqTree(binder: Symbol): Tree = @@ -827,7 +830,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = { if (currSub ne null) { - // patmatDebug ("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst)) + patmatDebug("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst)) Thread.dumpStack() } else currSub = outerSubst >> substitution @@ -889,7 +892,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL * the function's body is determined by the next TreeMaker * in this function's body, and all the subsequent ones, references to the symbols in `from` will be replaced by the corresponding tree in `to` */ - case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol, localSubstitution: Substitution)(extractorReturnsBoolean: Boolean, val checkedLength: Option[Int], val prevBinder: Symbol) extends FunTreeMaker { + case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol)(val localSubstitution: Substitution, extractorReturnsBoolean: Boolean, val checkedLength: Option[Int], val prevBinder: Symbol) extends FunTreeMaker { def chainBefore(next: Tree)(casegen: Casegen): Tree = { val condAndNext = extraCond map (casegen.ifThenElseZero(_, next)) getOrElse next atPos(extractor.pos)( @@ -902,7 +905,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL } // TODO: allow user-defined unapplyProduct - case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], localSubstitution: Substitution) extends FunTreeMaker { import CODE._ + case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree])(val localSubstitution: Substitution) extends FunTreeMaker { import CODE._ val nextBinder = prevBinder // just passing through def chainBefore(next: Tree)(casegen: Casegen): Tree = { val nullCheck = REF(prevBinder) OBJ_NE NULL @@ -993,7 +996,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL **/ case class TypeTestTreeMaker(prevBinder: Symbol, testedBinder: Symbol, expectedTp: Type, nextBinderTp: Type)(override val pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker { import TypeTestTreeMaker._ - // patmatDebug ("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp)) + patmatDebug("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp)) lazy val outerTestNeeded = ( !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass) @@ -1121,7 +1124,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = fixerUpper(owner, scrut.pos){ def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree))) - // patmatDebug ("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}"))) + patmatDebug("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}"))) val (unchecked, requireSwitch) = if (settings.XnoPatmatAnalysis.value) (true, false) @@ -1175,12 +1178,12 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL t match { case Function(_, _) if t.symbol == NoSymbol => t.symbol = currentOwner.newAnonymousFunctionValue(t.pos) - // patmatDebug ("new symbol for "+ (t, t.symbol.ownerChain)) + patmatDebug("new symbol for "+ (t, t.symbol.ownerChain)) case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) => - // patmatDebug ("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain)) + patmatDebug("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain)) t.symbol.owner = currentOwner case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2) - // patmatDebug ("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain)) + patmatDebug("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain)) if(d.symbol.isLazy) { // for lazy val's accessor -- is there no tree?? assert(d.symbol.lazyAccessor != NoSymbol && d.symbol.lazyAccessor.owner == d.symbol.owner, d.symbol.lazyAccessor) d.symbol.lazyAccessor.owner = currentOwner @@ -1190,7 +1193,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL d.symbol.owner = currentOwner // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) => - // patmatDebug ("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain)) + patmatDebug("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain)) case _ => } super.traverse(t) @@ -1386,7 +1389,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL case object FalseCond extends Cond {override def toString = "F"} case class AndCond(a: Cond, b: Cond) extends Cond {override def toString = a +"/\\"+ b} - case class OrCond(a: Cond, b: Cond) extends Cond {override def toString = "("+a+") \\/ ("+ b +")"} + case class OrCond(a: Cond, b: Cond) extends Cond {override def toString = "("+a+") \\/ ("+ b +")"} object EqualityCond { private val uniques = new collection.mutable.HashMap[(Tree, Tree), EqualityCond] @@ -1445,9 +1448,9 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL case _ => false } - def unapply(xtm: ExtractorTreeMaker): Option[(Tree, Symbol, Substitution)] = xtm match { - case ExtractorTreeMaker(extractor, None, nextBinder, subst) if irrefutableExtractorType(extractor.tpe) => - Some(extractor, nextBinder, subst) + def unapply(xtm: ExtractorTreeMaker): Option[(Tree, Symbol)] = xtm match { + case ExtractorTreeMaker(extractor, None, nextBinder) if irrefutableExtractorType(extractor.tpe) => + Some(extractor, nextBinder) case _ => None } @@ -1455,18 +1458,13 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // returns (tree, tests), where `tree` will be used to refer to `root` in `tests` class TreeMakersToConds(val root: Symbol) { - def discard() = { - pointsToBound.clear() - trees.clear() - normalize = EmptySubstitution - accumSubst = EmptySubstitution - } // a variable in this set should never be replaced by a tree that "does not consist of a selection on a variable in this set" (intuitively) private val pointsToBound = collection.mutable.HashSet(root) private val trees = collection.mutable.HashSet.empty[Tree] // the substitution that renames variables to variables in pointsToBound private var normalize: Substitution = EmptySubstitution + private var substitutionComputed = false // replaces a variable (in pointsToBound) by a selection on another variable in pointsToBound // in the end, instead of having x1, x1.hd, x2, x2.hd, ... flying around, @@ -1476,29 +1474,6 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // pointsToBound -- accumSubst.from == Set(root) && (accumSubst.from.toSet -- pointsToBound) isEmpty private var accumSubst: Substitution = EmptySubstitution - private def updateSubstitution(subst: Substitution) = { - // find part of substitution that replaces bound symbols by new symbols, and reverse that part - // so that we don't introduce new aliases for existing symbols, thus keeping the set of bound symbols minimal - val (boundSubst, unboundSubst) = (subst.from zip subst.to) partition { - case (f, t) => - t.isInstanceOf[Ident] && (t.symbol ne NoSymbol) && pointsToBound(f) - } - val (boundFrom, boundTo) = boundSubst.unzip - val (unboundFrom, unboundTo) = unboundSubst.unzip - - // reverse substitution that would otherwise replace a variable we already encountered by a new variable - // NOTE: this forgets the more precise type we have for these later variables, but that's probably okay - normalize >>= Substitution(boundTo map (_.symbol), boundFrom map (CODE.REF(_))) - // patmatDebug ("normalize subst: "+ normalize) - - val okSubst = Substitution(unboundFrom, unboundTo map (normalize(_))) // it's important substitution does not duplicate trees here -- it helps to keep hash consing simple, anyway - pointsToBound ++= ((okSubst.from, okSubst.to).zipped filter { (f, t) => pointsToBound exists (sym => t.exists(_.symbol == sym)) })._1 - // patmatDebug ("pointsToBound: "+ pointsToBound) - - accumSubst >>= okSubst - // patmatDebug ("accumSubst: "+ accumSubst) - } - // hashconsing trees (modulo value-equality) def unique(t: Tree, tpOverride: Type = NoType): Tree = trees find (a => a.correspondsStructure(t)(sameValue)) match { @@ -1529,74 +1504,120 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // note that the sequencing of operations is important: must visit in same order as match execution // binderToUniqueTree uses the type of the first symbol that was encountered as the type for all future binders - final def treeMakerToCond(tm: TreeMaker, handleUnknown: TreeMaker => Cond, updateSubst: Boolean, rewriteNil: Boolean = false): Cond = { - if (updateSubst) updateSubstitution(tm.substitution) - - tm match { - case ttm@TypeTestTreeMaker(prevBinder, testedBinder, pt, _) => - object condStrategy extends TypeTestTreeMaker.TypeTestCondStrategy { - type Result = Cond - def and(a: Result, b: Result) = AndCond(a, b) - def outerTest(testedBinder: Symbol, expectedTp: Type) = TrueCond // TODO OuterEqCond(testedBinder, expectedType) - def typeTest(b: Symbol, pt: Type) = { // a type test implies the tested path is non-null (null.isInstanceOf[T] is false for all T) - val p = binderToUniqueTree(b); AndCond(NonNullCond(p), TypeCond(p, uniqueTp(pt))) + abstract class TreeMakerToCond extends (TreeMaker => Cond) { + // requires(if (!substitutionComputed)) + def updateSubstitution(subst: Substitution): Unit = { + // find part of substitution that replaces bound symbols by new symbols, and reverse that part + // so that we don't introduce new aliases for existing symbols, thus keeping the set of bound symbols minimal + val (boundSubst, unboundSubst) = (subst.from zip subst.to) partition { + case (f, t) => + t.isInstanceOf[Ident] && (t.symbol ne NoSymbol) && pointsToBound(f) + } + val (boundFrom, boundTo) = boundSubst.unzip + val (unboundFrom, unboundTo) = unboundSubst.unzip + + // reverse substitution that would otherwise replace a variable we already encountered by a new variable + // NOTE: this forgets the more precise type we have for these later variables, but that's probably okay + normalize >>= Substitution(boundTo map (_.symbol), boundFrom map (CODE.REF(_))) + // patmatDebug ("normalize subst: "+ normalize) + + val okSubst = Substitution(unboundFrom, unboundTo map (normalize(_))) // it's important substitution does not duplicate trees here -- it helps to keep hash consing simple, anyway + pointsToBound ++= ((okSubst.from, okSubst.to).zipped filter { (f, t) => pointsToBound exists (sym => t.exists(_.symbol == sym)) })._1 + // patmatDebug("pointsToBound: "+ pointsToBound) + + accumSubst >>= okSubst + // patmatDebug("accumSubst: "+ accumSubst) + } + + def handleUnknown(tm: TreeMaker): Cond + + /** apply itself must render a faithful representation of the TreeMaker + * + * Concretely, TrueCond must only be used to represent a TreeMaker that is sure to match and that does not do any computation at all + * e.g., doCSE relies on apply itself being sound in this sense (since it drops TreeMakers that are approximated to TrueCond -- SI-6077) + * + * handleUnknown may be customized by the caller to approximate further + * + * TODO: don't ignore outer-checks + */ + def apply(tm: TreeMaker): Cond = { + if (!substitutionComputed) updateSubstitution(tm.substitution) + + tm match { + case ttm@TypeTestTreeMaker(prevBinder, testedBinder, pt, _) => + object condStrategy extends TypeTestTreeMaker.TypeTestCondStrategy { + type Result = Cond + def and(a: Result, b: Result) = AndCond(a, b) + def outerTest(testedBinder: Symbol, expectedTp: Type) = TrueCond // TODO OuterEqCond(testedBinder, expectedType) + def typeTest(b: Symbol, pt: Type) = { // a type test implies the tested path is non-null (null.isInstanceOf[T] is false for all T) + val p = binderToUniqueTree(b); AndCond(NonNullCond(p), TypeCond(p, uniqueTp(pt))) + } + def nonNullTest(testedBinder: Symbol) = NonNullCond(binderToUniqueTree(testedBinder)) + def equalsTest(pat: Tree, testedBinder: Symbol) = EqualityCond(binderToUniqueTree(testedBinder), unique(pat)) + def eqTest(pat: Tree, testedBinder: Symbol) = EqualityCond(binderToUniqueTree(testedBinder), unique(pat)) // TODO: eq, not == } - def nonNullTest(testedBinder: Symbol) = NonNullCond(binderToUniqueTree(testedBinder)) - def equalsTest(pat: Tree, testedBinder: Symbol) = EqualityCond(binderToUniqueTree(testedBinder), unique(pat)) - def eqTest(pat: Tree, testedBinder: Symbol) = EqualityCond(binderToUniqueTree(testedBinder), unique(pat)) // TODO: eq, not == - } - ttm.renderCondition(condStrategy) - case EqualityTestTreeMaker(prevBinder, patTree, _) => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree)) - case AlternativesTreeMaker(_, altss, _) => \/(altss map (alts => /\(alts map (treeMakerToCond(_, handleUnknown, updateSubst))))) - case ProductExtractorTreeMaker(testedBinder, None, subst) => NonNullCond(binderToUniqueTree(testedBinder)) - case IrrefutableExtractorTreeMaker(_, _, _) => - // the extra condition is None, the extractor's result indicates it always succeeds, - // and the potential type-test for the argument is represented by a separate TypeTestTreeMaker - TrueCond - case GuardTreeMaker(guard) => - guard.tpe match { - case ConstantType(Constant(true)) => TrueCond - case ConstantType(Constant(false)) => FalseCond - case _ => handleUnknown(tm) - } - case p @ ExtractorTreeMaker(extractor, Some(lenCheck), testedBinder, _) => - p.checkedLength match { - // special-case: interpret pattern `List()` as `Nil` - // TODO: make it more general List(1, 2) => 1 :: 2 :: Nil -- not sure this is a good idea... - case Some(0) if rewriteNil && testedBinder.tpe.typeSymbol == ListClass => // extractor.symbol.owner == SeqFactory - EqualityCond(binderToUniqueTree(p.prevBinder), unique(Ident(NilModule) setType NilModule.tpe)) - case _ => handleUnknown(tm) - } - case SubstOnlyTreeMaker(_, _) => TrueCond - case ProductExtractorTreeMaker(_, Some(_), _) | - ExtractorTreeMaker(_, _, _, _) | BodyTreeMaker(_, _) => handleUnknown(tm) + ttm.renderCondition(condStrategy) + case EqualityTestTreeMaker(prevBinder, patTree, _) => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree)) + case AlternativesTreeMaker(_, altss, _) => \/(altss map (alts => /\(alts map this))) + case ProductExtractorTreeMaker(testedBinder, None) => NonNullCond(binderToUniqueTree(testedBinder)) + case SubstOnlyTreeMaker(_, _) => TrueCond + case GuardTreeMaker(guard) => + guard.tpe match { + case ConstantType(Constant(true)) => TrueCond + case ConstantType(Constant(false)) => FalseCond + case _ => handleUnknown(tm) + } + case ExtractorTreeMaker(_, _, _) | + ProductExtractorTreeMaker(_, _) | + BodyTreeMaker(_, _) => handleUnknown(tm) + } } } - val constFalse = (_: TreeMaker) => FalseCond - val constTrue = (_: TreeMaker) => TrueCond - final def approximateMatch(cases: List[List[TreeMaker]], handleUnknown: TreeMaker => Cond = constFalse, rewriteNil: Boolean = false): List[List[Test]] = - cases.map { _ map (tm => Test(treeMakerToCond(tm, handleUnknown, updateSubst = true, rewriteNil), tm)) } + private val irrefutableExtractor: PartialFunction[TreeMaker, Cond] = { + // the extra condition is None, the extractor's result indicates it always succeeds, + // (the potential type-test for the argument is represented by a separate TypeTestTreeMaker) + case IrrefutableExtractorTreeMaker(_, _) => TrueCond + } - final def approximateMatchAgain(cases: List[List[TreeMaker]], handleUnknown: TreeMaker => Cond = constFalse, rewriteNil: Boolean = false): List[List[Test]] = - cases.map { _ map (tm => Test(treeMakerToCond(tm, handleUnknown, updateSubst = false, rewriteNil), tm)) } - } + // special-case: interpret pattern `List()` as `Nil` + // TODO: make it more general List(1, 2) => 1 :: 2 :: Nil -- not sure this is a good idea... + private val rewriteListPattern: PartialFunction[TreeMaker, Cond] = { + case p @ ExtractorTreeMaker(_, _, testedBinder) + if testedBinder.tpe.typeSymbol == ListClass && p.checkedLength == Some(0) => + EqualityCond(binderToUniqueTree(p.prevBinder), unique(Ident(NilModule) setType NilModule.tpe)) + } + val fullRewrite = (irrefutableExtractor orElse rewriteListPattern) + val refutableRewrite = irrefutableExtractor + @inline def onUnknown(handler: TreeMaker => Cond) = new TreeMakerToCond { + def handleUnknown(tm: TreeMaker) = handler(tm) + } - def approximateMatch(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = { - object approximator extends TreeMakersToConds(root) - approximator.approximateMatch(cases) + // used for CSE -- rewrite all unknowns to False (the most conserative option) + object conservative extends TreeMakerToCond { + def handleUnknown(tm: TreeMaker) = FalseCond + } + + final def approximateMatch(cases: List[List[TreeMaker]], treeMakerToCond: TreeMakerToCond = conservative) ={ + val testss = cases.map { _ map (tm => Test(treeMakerToCond(tm), tm)) } + substitutionComputed = true // a second call to approximateMatch should not re-compute the substitution (would be wrong) + testss + } } + def approximateMatchConservative(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = + (new TreeMakersToConds(root)).approximateMatch(cases) + def showTreeMakers(cases: List[List[TreeMaker]]) = { - // patmatDebug ("treeMakers:") - // patmatDebug (alignAcrossRows(cases, ">>")) + patmatDebug("treeMakers:") + patmatDebug(alignAcrossRows(cases, ">>")) } def showTests(testss: List[List[Test]]) = { - // patmatDebug ("tests: ") - // patmatDebug (alignAcrossRows(testss, "&")) + patmatDebug("tests: ") + patmatDebug(alignAcrossRows(testss, "&")) } } @@ -1788,7 +1809,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL override def hashCode = a.hashCode ^ b.hashCode } - // patmatDebug ("removeVarEq vars: "+ vars) + patmatDebug("removeVarEq vars: "+ vars) vars.foreach { v => val excludedPair = new collection.mutable.HashSet[ExcludedPair] @@ -1807,16 +1828,17 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL } val syms = v.equalitySyms - // patmatDebug ("eqSyms "+(v, syms)) + patmatDebug("eqSyms "+(v, syms)) syms foreach { sym => // if we've already excluded the pair at some point (-A \/ -B), then don't exclude the symmetric one (-B \/ -A) // (nor the positive implications -B \/ A, or -A \/ B, which would entail the equality axioms falsifying the whole formula) val todo = syms filterNot (b => (b.const == sym.const) || excludedPair(ExcludedPair(b.const, sym.const))) val (excluded, notExcluded) = todo partition (b => sym.const.excludes(b.const)) val implied = notExcluded filter (b => sym.const.implies(b.const)) - // patmatDebug ("eq axioms for: "+ sym.const) - // patmatDebug ("excluded: "+ excluded) - // patmatDebug ("implied: "+ implied) + + patmatDebug("eq axioms for: "+ sym.const) + patmatDebug("excluded: "+ excluded) + patmatDebug("implied: "+ implied) // when this symbol is true, what must hold... implied foreach (impliedSym => addAxiom(Or(Not(sym), impliedSym))) @@ -1829,8 +1851,8 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL } } - // patmatDebug ("eqAxioms:\n"+ cnfString(eqFreePropToSolvable(eqAxioms))) - // patmatDebug ("pure:"+ pure.map(p => cnfString(eqFreePropToSolvable(p))).mkString("\n")) + patmatDebug("eqAxioms:\n"+ cnfString(eqFreePropToSolvable(eqAxioms))) + patmatDebug("pure:"+ pure.map(p => cnfString(eqFreePropToSolvable(p))).mkString("\n")) Statistics.stopTimer(patmatAnaVarEq, start) @@ -1972,12 +1994,12 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL def findAllModels(f: Formula, models: List[Model], recursionDepthAllowed: Int = 10): List[Model]= if (recursionDepthAllowed == 0) models else { - // patmatDebug ("find all models for\n"+ cnfString(f)) + patmatDebug("find all models for\n"+ cnfString(f)) val model = findModelFor(f) // if we found a solution, conjunct the formula with the model's negation and recurse if (model ne NoModel) { val unassigned = (vars -- model.keySet).toList - // patmatDebug ("unassigned "+ unassigned +" in "+ model) + patmatDebug("unassigned "+ unassigned +" in "+ model) def force(lit: Lit) = { val model = withLit(findModelFor(dropUnit(f, lit)), lit) if (model ne NoModel) List(model) @@ -1986,7 +2008,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL val forced = unassigned flatMap { s => force(Lit(s, true)) ++ force(Lit(s, false)) } - // patmatDebug ("forced "+ forced) + patmatDebug("forced "+ forced) val negated = negateModel(model) findAllModels(f :+ negated, model :: (forced ++ models), recursionDepthAllowed - 1) } @@ -2009,7 +2031,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL def findModelFor(f: Formula): Model = { @inline def orElse(a: Model, b: => Model) = if (a ne NoModel) a else b - // patmatDebug ("DPLL\n"+ cnfString(f)) + patmatDebug("DPLL\n"+ cnfString(f)) val start = Statistics.startTimer(patmatAnaDPLL) @@ -2153,11 +2175,11 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL uniques.get(tp).getOrElse( uniques.find {case (oldTp, oldC) => oldTp =:= tp} match { case Some((_, c)) => - // patmatDebug ("unique const: "+ (tp, c)) + patmatDebug("unique const: "+ (tp, c)) c case _ => val fresh = mkFresh - // patmatDebug ("uniqued const: "+ (tp, fresh)) + patmatDebug("uniqued const: "+ (tp, fresh)) uniques(tp) = fresh fresh }) @@ -2173,12 +2195,12 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL if (!t.symbol.isStable) t.tpe.narrow else trees find (a => a.correspondsStructure(t)(sameValue)) match { case Some(orig) => - // patmatDebug ("unique tp for tree: "+ (orig, orig.tpe)) + patmatDebug("unique tp for tree: "+ (orig, orig.tpe)) orig.tpe case _ => // duplicate, don't mutate old tree (TODO: use a map tree -> type instead?) val treeWithNarrowedType = t.duplicate setType t.tpe.narrow - // patmatDebug ("uniqued: "+ (t, t.tpe, treeWithNarrowedType.tpe)) + patmatDebug("uniqued: "+ (t, t.tpe, treeWithNarrowedType.tpe)) trees += treeWithNarrowedType treeWithNarrowedType.tpe } @@ -2349,11 +2371,15 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // use the same approximator so we share variables, // but need different conditions depending on whether we're conservatively looking for failure or success - val reachabilityApproximation = new TreeMakersToConds(prevBinder) - val testCasesOk = reachabilityApproximation.approximateMatch(cases, reachabilityApproximation.constTrue) - val testCasesFail = reachabilityApproximation.approximateMatchAgain(cases, reachabilityApproximation.constFalse) + // don't rewrite List-like patterns, as List() and Nil need to distinguished for unreachability + val approx = new TreeMakersToConds(prevBinder) + def approximate(default: Cond) = approx.approximateMatch(cases, approx.onUnknown { tm => + approx.refutableRewrite.applyOrElse(tm, (_: TreeMaker) => default ) + }) + + val testCasesOk = approximate(TrueCond) + val testCasesFail = approximate(FalseCond) - reachabilityApproximation.discard() prepareNewAnalysis() val propsCasesOk = testCasesOk map (t => symbolicCase(t, modelNull = true)) @@ -2373,8 +2399,8 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL var reachable = true var caseIndex = 0 - // patmatDebug ("reachability, vars:\n"+ ((propsCasesFail flatMap gatherVariables) map (_.describe) mkString ("\n"))) - // patmatDebug ("equality axioms:\n"+ cnfString(eqAxiomsCNF)) + patmatDebug("reachability, vars:\n"+ ((propsCasesFail flatMap gatherVariables) map (_.describe) mkString ("\n"))) + patmatDebug("equality axioms:\n"+ cnfString(eqAxiomsCNF)) // invariant (prefixRest.length == current.length) && (prefix.reverse ++ prefixRest == symbolicCasesFail) // termination: prefixRest.length decreases by 1 @@ -2421,7 +2447,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL Some(List(tp)) // make sure it's not a primitive, else (5: Byte) match { case 5 => ... } sees no Byte case sym if !sym.isSealed || isPrimitiveValueClass(sym) => - // patmatDebug ("enum unsealed "+ (tp, sym, sym.isSealed, isPrimitiveValueClass(sym))) + patmatDebug("enum unsealed "+ (tp, sym, sym.isSealed, isPrimitiveValueClass(sym))) None case sym => val subclasses = ( @@ -2429,7 +2455,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // symbols which are both sealed and abstract need not be covered themselves, because // all of their children must be and they cannot otherwise be created. filterNot (x => x.isSealed && x.isAbstractClass && !isPrimitiveValueClass(x))) - // patmatDebug ("enum sealed -- subclasses: "+ (sym, subclasses)) + patmatDebug("enum sealed -- subclasses: "+ (sym, subclasses)) val tpApprox = typer.infer.approximateAbstracts(tp) val pre = tpApprox.prefix @@ -2445,7 +2471,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL if (subTpApprox <:< tpApprox) Some(checkableType(subTp)) else None }) - // patmatDebug ("enum sealed "+ (tp, tpApprox) + " as "+ validSubTypes) + patmatDebug("enum sealed "+ (tp, tpApprox) + " as "+ validSubTypes) Some(validSubTypes) } @@ -2465,7 +2491,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL } } val res = toCheckable(tp) - // patmatDebug ("checkable "+(tp, res)) + patmatDebug("checkable "+(tp, res)) res } @@ -2490,19 +2516,19 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL val start = Statistics.startTimer(patmatAnaExhaust) var backoff = false - val exhaustivityApproximation = new TreeMakersToConds(prevBinder) - val tests = exhaustivityApproximation.approximateMatch(cases, { - case BodyTreeMaker(_, _) => TrueCond // will be discarded by symbolCase later - case tm => - // patmatDebug("backing off due to "+ tm) + val approx = new TreeMakersToConds(prevBinder) + val tests = approx.approximateMatch(cases, approx.onUnknown { tm => + approx.fullRewrite.applyOrElse[TreeMaker, Cond](tm, { + case BodyTreeMaker(_, _) => TrueCond // irrelevant -- will be discarded by symbolCase later + case _ => // patmatDebug("backing off due to "+ tm) backoff = true FalseCond - }, rewriteNil = true) + }) + }) if (backoff) Nil else { - val prevBinderTree = exhaustivityApproximation.binderToUniqueTree(prevBinder) + val prevBinderTree = approx.binderToUniqueTree(prevBinder) - exhaustivityApproximation.discard() prepareNewAnalysis() val symbolicCases = tests map (symbolicCase(_, modelNull = false)) @@ -2523,7 +2549,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL val vars = gatherVariables(matchFails) // debug output: - // patmatDebug ("analysing:") + patmatDebug("analysing:") showTreeMakers(cases) showTests(tests) @@ -2543,7 +2569,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL pruned } catch { case e : CNFBudgetExceeded => - // patmatDebug (util.Position.formatMessage(prevBinder.pos, "Cannot check match for exhaustivity", false)) + patmatDebug(util.Position.formatMessage(prevBinder.pos, "Cannot check match for exhaustivity", false)) // e.printStackTrace() Nil // CNF budget exceeded } @@ -2633,7 +2659,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // ... val varAssignment = modelToVarAssignment(model) - // patmatDebug ("var assignment for model "+ model +":\n"+ varAssignmentString(varAssignment)) + patmatDebug("var assignment for model "+ model +":\n"+ varAssignmentString(varAssignment)) // chop a path into a list of symbols def chop(path: Tree): List[Symbol] = path match { @@ -2700,7 +2726,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL def toCounterExample(beBrief: Boolean = false): CounterExample = if (!allFieldAssignmentsLegal) NoExample else { - // patmatDebug ("describing "+ (variable, equalTo, notEqualTo, fields, cls, allFieldAssignmentsLegal)) + patmatDebug("describing "+ (variable, equalTo, notEqualTo, fields, cls, allFieldAssignmentsLegal)) val res = prunedEqualTo match { // a definite assignment to a value case List(eq: ValueConst) if fields.isEmpty => ValueExample(eq) @@ -2741,7 +2767,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // TODO: improve reasoning -- in the mean time, a false negative is better than an annoying false positive case _ => NoExample } - // patmatDebug ("described as: "+ res) + patmatDebug("described as: "+ res) res } @@ -2766,7 +2792,10 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL * we generalize sharing to implication, where b reuses a if a => b and priors(a) => priors(b) (the priors of a sub expression form the path through the decision tree) */ def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = { - val testss = approximateMatch(prevBinder, cases) + patmatDebug("before CSE:") + showTreeMakers(cases) + + val testss = approximateMatchConservative(prevBinder, cases) // interpret: val dependencies = new collection.mutable.LinkedHashMap[Test, Set[Cond]] @@ -2776,10 +2805,10 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL val cond = test.cond def simplify(c: Cond): Set[Cond] = c match { - case AndCond(a, b) => simplify(a) ++ simplify(b) + case AndCond(a, b) => simplify(a) ++ simplify(b) case OrCond(_, _) => Set(FalseCond) // TODO: make more precise case NonNullCond(_) => Set(TrueCond) // not worth remembering - case _ => Set(c) + case _ => Set(c) } val conds = simplify(cond) @@ -2794,7 +2823,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL case (priorTest, deps) => ((simplify(priorTest.cond) == nonTrivial) || // our conditions are implied by priorTest if it checks the same thing directly (nonTrivial subsetOf deps) // or if it depends on a superset of our conditions - ) && (deps subsetOf tested) // the conditions we've tested when we are here in the match satisfy the prior test, and hence what it tested + ) && (deps subsetOf tested) // the conditions we've tested when we are here in the match satisfy the prior test, and hence what it tested } foreach { case (priorTest, _) => // if so, note the dependency in both tests @@ -2812,7 +2841,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL tested.clear() tests dropWhile storeDependencies } - // patmatDebug ("dependencies: "+ dependencies) + patmatDebug("dependencies: "+ dependencies) // find longest prefix of tests that reuse a prior test, and whose dependent conditions monotonically increase // then, collapse these contiguous sequences of reusing tests @@ -2846,7 +2875,8 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL case _ => } - // patmatDebug("sharedPrefix: "+ sharedPrefix) + patmatDebug("sharedPrefix: "+ sharedPrefix) + patmatDebug("suffix: "+ sharedPrefix) // if the shared prefix contains interesting conditions (!= TrueCond) // and the last of such interesting shared conditions reuses another treemaker's test // replace the whole sharedPrefix by a ReusingCondTreeMaker @@ -2862,7 +2892,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // replace original treemakers that are reused (as determined when computing collapsed), // by ReusedCondTreeMakers val reusedMakers = collapsed mapConserve (_ mapConserve reusedOrOrig) - // patmatDebug ("after CSE:") + patmatDebug("after CSE:") showTreeMakers(reusedMakers) reusedMakers } diff --git a/test/files/run/t6077_patmat_cse_irrefutable.check b/test/files/run/t6077_patmat_cse_irrefutable.check new file mode 100644 index 0000000000..9766475a41 --- /dev/null +++ b/test/files/run/t6077_patmat_cse_irrefutable.check @@ -0,0 +1 @@ +ok diff --git a/test/files/run/t6077_patmat_cse_irrefutable.scala b/test/files/run/t6077_patmat_cse_irrefutable.scala new file mode 100644 index 0000000000..b130ae7813 --- /dev/null +++ b/test/files/run/t6077_patmat_cse_irrefutable.scala @@ -0,0 +1,13 @@ +class LiteralNode(val value: Any) + +object LiteralNode { + // irrefutable + def unapply(n: LiteralNode) = Some(n.value) +} + +object Test extends App { + ((new LiteralNode(false)): Any) match { + case LiteralNode(true) => println("uh-oh") + case LiteralNode(false) => println("ok") + } +}
\ No newline at end of file |