diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala | 626 |
1 files changed, 401 insertions, 225 deletions
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala index 61e02edaff..d12b8f848f 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatternMatching.scala @@ -12,6 +12,8 @@ import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC} import language.postfixOps import scala.tools.nsc.transform.TypingTransformers import scala.tools.nsc.transform.Transform +import scala.collection.mutable.HashSet +import scala.collection.mutable.HashMap /** Translate pattern matching. * @@ -306,7 +308,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // it tests the type, checks the outer pointer and casts to the expected type // TODO: the outer check is mandated by the spec for case classes, but we do it for user-defined unapplies as well [SPEC] // (the prefix of the argument passed to the unapply must equal the prefix of the type of the binder) - val treeMaker = TypeTestTreeMaker(patBinder, extractor.paramType, pos) + val treeMaker = TypeTestTreeMaker(patBinder, patBinder, extractor.paramType, extractor.paramType)(pos, extractorArgTypeTest = true) (List(treeMaker), treeMaker.nextBinder) } else (Nil, patBinder) @@ -364,7 +366,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // must treat Typed and Bind together -- we need to know the patBinder of the Bind pattern to get at the actual type case MaybeBoundTyped(subPatBinder, pt) => // a typed pattern never has any subtrees - noFurtherSubPats(TypeAndEqualityTestTreeMaker(subPatBinder, patBinder, pt, pos)) + noFurtherSubPats(TypeTestTreeMaker(subPatBinder, patBinder, pt, glb(List(patBinder.info.widen, pt)).normalize)(pos)) /** A pattern binder x@p consists of a pattern variable x and a pattern p. The type of the variable x is the static type T of the pattern p. @@ -562,8 +564,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL protected def lengthGuard(binder: Symbol): Option[Tree] = // no need to check unless it's an unapplySeq and the minimal length is non-trivially satisfied - if (!isSeq || (expectedLength < minLenToCheck)) None - else { import CODE._ + checkedLength map { expectedLength => import CODE._ // `binder.lengthCompare(expectedLength)` def checkExpectedLength = (seqTree(binder) DOT seqLenCmp)(LIT(expectedLength)) @@ -575,8 +576,14 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL else _ INT_== _ // `if (binder != null && $checkExpectedLength [== | >=] 0) then else zero` - Some((seqTree(binder) ANY_!= NULL) AND compareOp(checkExpectedLength, ZERO)) + (seqTree(binder) ANY_!= NULL) AND compareOp(checkExpectedLength, ZERO) } + + def checkedLength: Option[Int] = + // no need to check unless it's an unapplySeq and the minimal length is non-trivially satisfied + if (!isSeq || (expectedLength < minLenToCheck)) None + else Some(expectedLength) + } // TODO: to be called when there's a def unapplyProd(x: T): U @@ -650,7 +657,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) + ExtractorTreeMaker(extractorApply, lengthGuard(binder), binder, Substitution(subPatBinders, subPatRefs(binder)))(resultType.typeSymbol == BooleanClass, checkedLength, patBinderOrCasted) } override protected def seqTree(binder: Symbol): Tree = @@ -762,7 +769,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) => !other.from.contains(f) } new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly } - override def toString = (from zip to) mkString("Substitution(", ", ", ")") + override def toString = (from.map(_.name) zip to) mkString("Substitution(", ", ", ")") } object EmptySubstitution extends Substitution(Nil, Nil) { @@ -775,7 +782,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // the making of the trees /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// trait TreeMakers extends TypedSubstitution { self: CodegenCore => - def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) = + def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type, unchecked: Boolean): (List[List[TreeMaker]], List[Tree]) = (cases, Nil) def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type, matchFailGenOverride: Option[Tree => Tree]): Option[Tree] = @@ -819,11 +826,13 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker with NoNewBinders { def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(next eq EmptyTree) atPos(body.pos)(casegen.one(substitution(body))) // since SubstOnly treemakers are dropped, need to do it here + override def toString = "B"+(body, matchPt) } case class SubstOnlyTreeMaker(prevBinder: Symbol, nextBinder: Symbol) extends TreeMaker { val localSubstitution = Substitution(prevBinder, CODE.REF(nextBinder)) def chainBefore(next: Tree)(casegen: Casegen): Tree = substitution(next) + override def toString = "S"+ localSubstitution } abstract class FunTreeMaker extends TreeMaker { @@ -851,7 +860,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) extends FunTreeMaker { + case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol, 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)( @@ -860,136 +869,157 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL ) } - override def toString = "X"+(extractor, nextBinder) + override def toString = "X"+(extractor, nextBinder.name) } // TODO: allow user-defined unapplyProduct - case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], localSubstitution: Substitution) extends TreeMaker { import CODE._ + case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree], 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 val cond = extraCond map (nullCheck AND _) getOrElse nullCheck casegen.ifThenElseZero(cond, substitution(next)) } - override def toString = "P"+(prevBinder, extraCond getOrElse "", localSubstitution) + override def toString = "P"+(prevBinder.name, extraCond getOrElse "", localSubstitution) } - // tack an outer test onto `cond` if binder.info and expectedType warrant it - def maybeWithOuterCheck(binder: Symbol, expectedTp: Type)(cond: Tree): Tree = { import CODE._ - if ( !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass) - && needsOuterTest(expectedTp, binder.info, matchOwner)) { - val expectedPrefix = expectedTp.prefix match { - case ThisType(clazz) => THIS(clazz) - case pre => REF(pre.prefix, pre.termSymbol) - } + // typetag-based tests are inserted by the type checker + def needsTypeTest(tp: Type, pt: Type): Boolean = !(tp <:< pt) + + object TypeTestTreeMaker { + // factored out so that we can consistently generate other representations of the tree that implements the test + // (e.g. propositions for exhaustivity and friends, boolean for isPureTypeTest) + trait TypeTestCondStrategy { + type Result + + def outerTest(testedBinder: Symbol, expectedTp: Type): Result + // TODO: can probably always widen + def typeTest(testedBinder: Symbol, expectedTp: Type): Result + def nonNullTest(testedBinder: Symbol): Result + def equalsTest(pat: Tree, testedBinder: Symbol): Result + def eqTest(pat: Tree, testedBinder: Symbol): Result + def and(a: Result, b: Result): Result + } + + object treeCondStrategy extends TypeTestCondStrategy { import CODE._ + type Result = Tree + + def and(a: Result, b: Result): Result = a AND b + def typeTest(testedBinder: Symbol, expectedTp: Type) = codegen._isInstanceOf(testedBinder, expectedTp) + def nonNullTest(testedBinder: Symbol) = REF(testedBinder) OBJ_NE NULL + def equalsTest(pat: Tree, testedBinder: Symbol) = codegen._equals(pat, testedBinder) + def eqTest(pat: Tree, testedBinder: Symbol) = REF(testedBinder) OBJ_EQ pat - // ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix` - // if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor? - val outer = expectedTp.typeSymbol.newMethod(vpmName.outer) setInfo expectedTp.prefix setFlag SYNTHETIC - val outerCheck = (Select(codegen._asInstanceOf(binder, expectedTp), outer)) OBJ_EQ expectedPrefix + def outerTest(testedBinder: Symbol, expectedTp: Type): Tree = { + val expectedOuter = expectedTp.prefix match { + case ThisType(clazz) => THIS(clazz) + case pre => REF(pre.prefix, pre.termSymbol) + } + + // ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix` + // if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor? + val outer = expectedTp.typeSymbol.newMethod(vpmName.outer) setInfo expectedTp.prefix setFlag SYNTHETIC - // first check cond, since that should ensure we're not selecting outer on null - codegen.and(cond, outerCheck) + (Select(codegen._asInstanceOf(testedBinder, expectedTp), outer)) OBJ_EQ expectedOuter + } } - else - cond - } - // containsUnchecked: also need to test when erasing pt loses crucial information (maybe we can recover it using a TypeTag) - def needsTypeTest(tp: Type, pt: Type): Boolean = !(tp <:< pt) // || containsUnchecked(pt) - // TODO: try to find the TypeTag for the binder's type and the expected type, and if they exists, - // check that the TypeTag of the binder's type conforms to the TypeTag of the expected type - private def typeTest(binderToTest: Symbol, expectedTp: Type, disableOuterCheck: Boolean = false, dynamic: Boolean = false): Tree = { import CODE._ - // def coreTest = - if (disableOuterCheck) codegen._isInstanceOf(binderToTest, expectedTp) else maybeWithOuterCheck(binderToTest, expectedTp)(codegen._isInstanceOf(binderToTest, expectedTp)) - // [Eugene to Adriaan] use `resolveErasureTag` instead of `findManifest`. please, provide a meaningful position - // if (opt.experimental && containsUnchecked(expectedTp)) { - // if (dynamic) { - // val expectedTpTagTree = findManifest(expectedTp, true) - // if (!expectedTpTagTree.isEmpty) - // ((expectedTpTagTree DOT "erasure".toTermName) DOT "isAssignableFrom".toTermName)(REF(binderToTest) DOT nme.getClass_) - // else - // coreTest - // } else { - // val expectedTpTagTree = findManifest(expectedTp, true) - // val binderTpTagTree = findManifest(binderToTest.info, true) - // if(!(expectedTpTagTree.isEmpty || binderTpTagTree.isEmpty)) - // coreTest AND (binderTpTagTree DOT nme.CONFORMS)(expectedTpTagTree) - // else - // coreTest - // } - // } else coreTest - } + object pureTypeTestChecker extends TypeTestCondStrategy { + type Result = Boolean + + def typeTest(testedBinder: Symbol, expectedTp: Type): Result = true - // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case) - case class TypeTestTreeMaker(prevBinder: Symbol, nextBinderTp: Type, pos: Position) extends CondTreeMaker { - val cond = typeTest(prevBinder, nextBinderTp, dynamic = true) - val res = codegen._asInstanceOf(prevBinder, nextBinderTp) - override def toString = "TT"+(prevBinder, nextBinderTp) + def outerTest(testedBinder: Symbol, expectedTp: Type): Result = false + def nonNullTest(testedBinder: Symbol): Result = false + def equalsTest(pat: Tree, testedBinder: Symbol): Result = false + def eqTest(pat: Tree, testedBinder: Symbol): Result = false + def and(a: Result, b: Result): Result = false // we don't and type tests, so the conjunction must include at least one false + } } - // implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations) - // TODO: normalize construction, which yields a combination of a EqualityTestTreeMaker (when necessary) and a TypeTestTreeMaker - case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends CondTreeMaker { - val nextBinderTp = glb(List(patBinder.info.widen, pt)).normalize - - /** Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms: - - A reference to a class C, p.C, or T#C. - This type pattern matches any non-null instance of the given class. - Note that the prefix of the class, if it is given, is relevant for determining class instances. - For instance, the pattern p.C matches only instances of classes C which were created with the path p as prefix. - The bottom types scala.Nothing and scala.Null cannot be used as type patterns, because they would match nothing in any case. - - - A singleton type p.type. - This type pattern matches only the value denoted by the path p - (that is, a pattern match involved a comparison of the matched value with p using method eq in class AnyRef). // TODO: the actual pattern matcher uses ==, so that's what I'm using for now - // https://issues.scala-lang.org/browse/SI-4577 "pattern matcher, still disappointing us at equality time" - - - A compound type pattern T1 with ... with Tn where each Ti is a type pat- tern. - This type pattern matches all values that are matched by each of the type patterns Ti. - - - A parameterized type pattern T[a1,...,an], where the ai are type variable patterns or wildcards _. - This type pattern matches all values which match T for some arbitrary instantiation of the type variables and wildcards. - The bounds or alias type of these type variable are determined as described in (§8.3). - - - A parameterized type pattern scala.Array[T1], where T1 is a type pattern. // TODO - This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1. - **/ - - // generate the tree for the run-time test that follows from the fact that - // a `scrut` of known type `scrutTp` is expected to have type `expectedTp` - // uses maybeWithOuterCheck to check the type's prefix - private def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree = { import CODE._ - // TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null` - // don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false") - def genEqualsAndInstanceOf(sym: Symbol): Tree - = codegen._equals(REF(sym), patBinder) AND typeTest(patBinder, pt.widen, disableOuterCheck = true) - - def isRefTp(tp: Type) = tp <:< AnyRefClass.tpe - - val patBinderTp = patBinder.info.widen - def isMatchUnlessNull = isRefTp(pt) && !needsTypeTest(patBinderTp, pt) - - // TODO: [SPEC] type test for Array - // TODO: use TypeTags to improve tests (for erased types we can do better when we have a TypeTag) - pt match { - case SingleType(_, sym) /*this implies sym.isStable*/ => genEqualsAndInstanceOf(sym) // TODO: [SPEC] the spec requires `eq` instead of `==` here - case ThisType(sym) if sym.isModule => genEqualsAndInstanceOf(sym) // must use == to support e.g. List() == Nil - case ThisType(sym) => REF(patBinder) OBJ_EQ This(sym) - case ConstantType(Constant(null)) if isRefTp(patBinderTp) => REF(patBinder) OBJ_EQ NULL - case ConstantType(const) => codegen._equals(Literal(const), patBinder) - case _ if isMatchUnlessNull => maybeWithOuterCheck(patBinder, pt)(REF(patBinder) OBJ_NE NULL) - case _ => typeTest(patBinder, pt) - } + /** implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations) + * + * Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms: + - A reference to a class C, p.C, or T#C. + This type pattern matches any non-null instance of the given class. + Note that the prefix of the class, if it is given, is relevant for determining class instances. + For instance, the pattern p.C matches only instances of classes C which were created with the path p as prefix. + The bottom types scala.Nothing and scala.Null cannot be used as type patterns, because they would match nothing in any case. + + - A singleton type p.type. + This type pattern matches only the value denoted by the path p + (that is, a pattern match involved a comparison of the matched value with p using method eq in class AnyRef). // TODO: the actual pattern matcher uses ==, so that's what I'm using for now + // https://issues.scala-lang.org/browse/SI-4577 "pattern matcher, still disappointing us at equality time" + + - A compound type pattern T1 with ... with Tn where each Ti is a type pat- tern. + This type pattern matches all values that are matched by each of the type patterns Ti. + + - A parameterized type pattern T[a1,...,an], where the ai are type variable patterns or wildcards _. + This type pattern matches all values which match T for some arbitrary instantiation of the type variables and wildcards. + The bounds or alias type of these type variable are determined as described in (§8.3). + + - A parameterized type pattern scala.Array[T1], where T1 is a type pattern. // TODO + This type pattern matches any non-null instance of type scala.Array[U1], where U1 is a type matched by T1. + **/ + case class TypeTestTreeMaker(prevBinder: Symbol, testedBinder: Symbol, expectedTp: Type, nextBinderTp: Type)(_pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker { + val pos = _pos + + import TypeTestTreeMaker._ + // println("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp)) + + lazy val outerTestNeeded = ( + !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass) + && needsOuterTest(expectedTp, testedBinder.info, matchOwner)) + + // the logic to generate the run-time test that follows from the fact that + // a `prevBinder` is expected to have type `expectedTp` + // the actual tree-generation logic is factored out, since the analyses generate Cond(ition)s rather than Trees + // TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null` + // don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false") + def renderCondition(cs: TypeTestCondStrategy): cs.Result = { + import cs._ + + def default = + // do type test first to ensure we won't select outer on null + if (outerTestNeeded) and(typeTest(testedBinder, expectedTp), outerTest(testedBinder, expectedTp)) + else typeTest(testedBinder, expectedTp) + + // true when called to type-test the argument to an extractor + // don't do any fancy equality checking, just test the type + if (extractorArgTypeTest) default + else expectedTp match { + // TODO: [SPEC] the spec requires `eq` instead of `==` for singleton types + // this implies sym.isStable + case SingleType(_, sym) => and(equalsTest(CODE.REF(sym), testedBinder), typeTest(testedBinder, expectedTp.widen)) + // must use == to support e.g. List() == Nil + case ThisType(sym) if sym.isModule => and(equalsTest(CODE.REF(sym), testedBinder), typeTest(testedBinder, expectedTp.widen)) + case ConstantType(const) => equalsTest(Literal(const), testedBinder) + + case ThisType(sym) => eqTest(This(sym), testedBinder) + case ConstantType(Constant(null)) if testedBinder.info.widen <:< AnyRefClass.tpe + => eqTest(CODE.NULL, testedBinder) + + // TODO: verify that we don't need to special-case Array + // I think it's okay: + // - the isInstanceOf test includes a test for the element type + // - Scala's arrays are invariant (so we don't drop type tests unsoundly) + case _ if (expectedTp <:< AnyRefClass.tpe) && !needsTypeTest(testedBinder.info.widen, expectedTp) => + // do non-null check first to ensure we won't select outer on null + if (outerTestNeeded) and(nonNullTest(testedBinder), outerTest(testedBinder, expectedTp)) + else nonNullTest(testedBinder) + + case _ => default + } } - val cond = typeAndEqualityTest(patBinder, pt) - val res = codegen._asInstanceOf(patBinder, nextBinderTp) + val cond = renderCondition(treeCondStrategy) + val res = codegen._asInstanceOf(testedBinder, nextBinderTp) - // TODO: remove this - def isStraightTypeTest = cond match { case TypeApply(_, _) => cond.symbol == Any_isInstanceOf case _ => false } + // is this purely a type test, e.g. no outer check, no equality tests (used in switch emission) + def isPureTypeTest = renderCondition(pureTypeTestChecker) - override def toString = "TET"+(patBinder, pt) + override def toString = "TT"+(expectedTp, testedBinder.name, nextBinderTp) } // need to substitute to deal with existential types -- TODO: deal with existentials better, don't substitute (see RichClass during quick.comp) @@ -1000,7 +1030,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // equals need not be well-behaved, so don't intersect with pattern's (stabilized) type (unlike MaybeBoundTyped's accumType, where it's required) val cond = codegen._equals(patTree, prevBinder) val res = CODE.REF(prevBinder) - override def toString = "ET"+(prevBinder, patTree) + override def toString = "ET"+(prevBinder.name, patTree) } case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker with NoNewBinders { @@ -1062,7 +1092,21 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree))) // println("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}"))) + def isSwitchAnnotation(tpe: Type) = tpe hasAnnotation SwitchClass + def isUncheckedAnnotation(tpe: Type) = tpe hasAnnotation UncheckedClass + + val (unchecked, requireSwitch) = scrut match { + case Typed(_, tpt) => + (isUncheckedAnnotation(tpt.tpe), + // matches with two or fewer cases need not apply for switchiness (if-then-else will do) + isSwitchAnnotation(tpt.tpe) && casesNoSubstOnly.lengthCompare(2) > 0) + case _ => + (false, false) + } + emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt, matchFailGenOverride).getOrElse{ + if (requireSwitch) typer.context.unit.error(scrut.pos, "could not emit switch for @switch annotated match") + if (casesNoSubstOnly nonEmpty) { // before optimizing, check casesNoSubstOnly for presence of a default case, // since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one @@ -1077,7 +1121,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL }) None else matchFailGen - val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt) + val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt, unchecked) val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, synthCatchAll) @@ -1262,7 +1306,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // decisions, decisions /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - trait TreeMakerApproximation extends TreeMakers { self: CodegenCore => + trait TreeMakerApproximation extends TreeMakers with Prettification{ self: CodegenCore => object Test { var currId = 0 } @@ -1281,9 +1325,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL val id = { Test.currId += 1; Test.currId} override def toString = - if (cond eq Top) "T" - else if(cond eq Havoc) "!?" - else "T"+ id + (if(reusedBy nonEmpty) "!["+ treeMaker +"]" else (if(reuses.isEmpty) "["+ treeMaker +"]" else " cf. T"+reuses.get.id)) + "T"+ id + "C("+ cond +")" //+ (reuses map ("== T"+_.id) getOrElse (if(reusedBy.isEmpty) treeMaker else reusedBy mkString (treeMaker+ " -->(", ", ",")"))) } object Cond { @@ -1304,10 +1346,11 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL } // does not contribute any knowledge - case object Top extends Cond + case object Top extends Cond {override def toString = "T"} + // takes away knowledge. e.g., a user-defined guard - case object Havoc extends Cond + case object Havoc extends Cond {override def toString = "_|_"} // we know everything! everything! // this either means the case is unreachable, @@ -1315,11 +1358,15 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // case object Bottom extends Cond + 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 +")"} + object EqualityCond { private val uniques = new collection.mutable.HashMap[(Tree, Tree), EqualityCond] def apply(testedPath: Tree, rhs: Tree): EqualityCond = uniques getOrElseUpdate((testedPath, rhs), new EqualityCond(testedPath, rhs)) + def unapply(c: EqualityCond) = Some(c.testedPath, c.rhs) } - class EqualityCond(testedPath: Tree, rhs: Tree) extends Cond { + class EqualityCond(val testedPath: Tree, val rhs: Tree) extends Cond { // def negation = TopCond // inequality doesn't teach us anything // do simplification when we know enough about the tree statically: // - collapse equal trees @@ -1329,103 +1376,181 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL override def toString = testedPath +" == "+ rhs +"#"+ id } - object TypeCond { - private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeCond] - def apply(testedPath: Tree, pt: Type): TypeCond = uniques getOrElseUpdate((testedPath, pt), new TypeCond(testedPath, pt)) + object NonNullCond { + private val uniques = new collection.mutable.HashMap[Tree, NonNullCond] + def apply(testedPath: Tree): NonNullCond = uniques getOrElseUpdate(testedPath, new NonNullCond(testedPath)) + def unapply(c: NonNullCond) = Some(c.testedPath) } - class TypeCond(testedPath: Tree, pt: Type) extends Cond { - // def negation = TopCond // inequality doesn't teach us anything - // do simplification when we know enough about the tree statically: - // - collapse equal trees - // - accumulate tests when (in)equality not known statically - // - become bottom when we statically know this can never match - override def toString = testedPath +" <: "+ pt +"#"+ id + class NonNullCond(val testedPath: Tree) extends Cond { + override def toString = testedPath +" ne null " +"#"+ id } - object TypeAndEqualityCond { - private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeAndEqualityCond] - def apply(testedPath: Tree, pt: Type): TypeAndEqualityCond = uniques getOrElseUpdate((testedPath, pt), new TypeAndEqualityCond(testedPath, pt)) + object TypeCond { + private val uniques = new collection.mutable.HashMap[(Tree, Type), TypeCond] + def apply(testedPath: Tree, pt: Type): TypeCond = uniques getOrElseUpdate((testedPath, pt), new TypeCond(testedPath, pt)) + def unapply(c: TypeCond) = Some(c.testedPath, c.pt) } - class TypeAndEqualityCond(testedPath: Tree, pt: Type) extends Cond { + class TypeCond(val testedPath: Tree, val pt: Type) extends Cond { // def negation = TopCond // inequality doesn't teach us anything // do simplification when we know enough about the tree statically: // - collapse equal trees // - accumulate tests when (in)equality not known statically // - become bottom when we statically know this can never match - override def toString = testedPath +" (<: && ==) "+ pt +"#"+ id + override def toString = testedPath +" : "+ pt +"#"+ id } - def approximateMatch(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = { +// class OuterEqCond(val testedPath: Tree, val expectedType: Type) extends Cond { +// val expectedOuter = expectedTp.prefix match { +// case ThisType(clazz) => THIS(clazz) +// case pre => REF(pre.prefix, pre.termSymbol) +// } +// +// // ExplicitOuter replaces `Select(q, outerSym) OBJ_EQ expectedPrefix` by `Select(q, outerAccessor(outerSym.owner)) OBJ_EQ expectedPrefix` +// // if there's an outer accessor, otherwise the condition becomes `true` -- TODO: can we improve needsOuterTest so there's always an outerAccessor? +// val outer = expectedTp.typeSymbol.newMethod(vpmName.outer) setInfo expectedTp.prefix setFlag SYNTHETIC +// +// (Select(codegen._asInstanceOf(testedBinder, expectedTp), outer)) OBJ_EQ expectedOuter +// } + + + // returns (tree, tests), where `tree` will be used to refer to `root` in `tests` + abstract class TreeMakersToConds(val root: Symbol, val cases: List[List[TreeMaker]]) { // 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) - val pointsToBound = collection.mutable.HashSet(root) + private val pointsToBound = collection.mutable.HashSet(root) // the substitution that renames variables to variables in pointsToBound - var normalize: Substitution = EmptySubstitution + private var normalize: Substitution = EmptySubstitution // replaces a variable (in pointsToBound) by a selection on another variable in pointsToBound // TODO check: // pointsToBound -- accumSubst.from == Set(root) && (accumSubst.from.toSet -- pointsToBound) isEmpty - var accumSubst: Substitution = EmptySubstitution + private var accumSubst: Substitution = EmptySubstitution + + private val trees = new collection.mutable.HashSet[Tree] - val trees = new collection.mutable.HashSet[Tree] + // TODO: improve, e.g., for constants + def sameValue(a: Tree, b: Tree): Boolean = (a eq b) || ((a, b) match { + case (_ : Ident, _ : Ident) => a.symbol eq b.symbol + case _ => false + }) + + // hashconsing trees (modulo value-equality) + def unique(t: Tree, tpOverride: Type = NoType): Tree = + trees find (a => a.equalsStructure0(t)(sameValue)) match { + case Some(orig) => orig // println("unique: "+ (t eq orig, orig)); + case _ => + trees += t + if (tpOverride != NoType) t setType tpOverride + else t + } - def approximateTreeMaker(tm: TreeMaker): Test = { - val subst = tm.substitution + def uniqueTp(tp: Type): Type = tp match { + // typerefs etc are already hashconsed + case _ : UniqueType => tp + case tp@RefinedType(parents, EmptyScope) => tp.memo(tp: Type)(identity) // TODO: does this help? + case _ => tp + } + // produce the unique tree used to refer to this binder + // the type of the binder passed to the first invocation + // determines the type of the tree that'll be returned for that binder as of then + def binderToUniqueTree(b: Symbol) = + unique(accumSubst(normalize(CODE.REF(b))), b.tpe) + + // 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 + def treeMakerToCond(tm: TreeMaker): Cond = { + 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) = Top // TODO OuterEqCond(testedBinder, expectedType) + def typeTest(b: Symbol, pt: Type) = TypeCond(binderToUniqueTree(b), 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 == + } + ttm.renderCondition(condStrategy) + case EqualityTestTreeMaker(prevBinder, patTree, _) => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree)) + case AlternativesTreeMaker(_, altss, _) => altss map (_ map treeMakerToCond reduceLeft AndCond) reduceLeft OrCond + case ProductExtractorTreeMaker(testedBinder, None, subst) => NonNullCond(binderToUniqueTree(testedBinder)) + case ExtractorTreeMaker(_, _, _, _) + | GuardTreeMaker(_) + | ProductExtractorTreeMaker(_, Some(_), _) + | BodyTreeMaker(_, _) => Havoc + case SubstOnlyTreeMaker(_, _) => Top + } + } + + 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 we have for these later variables, but that's probably okay normalize >>= Substitution(boundTo map (_.symbol), boundFrom map (CODE.REF(_))) // println("normalize: "+ normalize) - val (unboundFrom, unboundTo) = unboundSubst unzip 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 // println("pointsToBound: "+ pointsToBound) accumSubst >>= okSubst // println("accumSubst: "+ accumSubst) + } - // TODO: improve, e.g., for constants - def sameValue(a: Tree, b: Tree): Boolean = (a eq b) || ((a, b) match { - case (_ : Ident, _ : Ident) => a.symbol eq b.symbol - case _ => false - }) - - // hashconsing trees (modulo value-equality) - def unique(t: Tree): Tree = - trees find (a => a.equalsStructure0(t)(sameValue)) match { - case Some(orig) => orig // println("unique: "+ (t eq orig, orig)); - case _ => trees += t; t - } + def approximateTreeMaker(tm: TreeMaker): Test = + Test(treeMakerToCond(tm), tm) - def uniqueTp(tp: Type): Type = tp match { - // typerefs etc are already hashconsed - case _ : UniqueType => tp - case tp@RefinedType(parents, EmptyScope) => tp.memo(tp: Type)(identity) // TODO: does this help? - case _ => tp - } + def approximateMatch: List[List[Test]] = cases.map { _ map approximateTreeMaker } + } - def binderToUniqueTree(b: Symbol) = unique(accumSubst(normalize(CODE.REF(b)))) + def approximateMatch(root: Symbol, cases: List[List[TreeMaker]]): List[List[Test]] = { + object approximator extends TreeMakersToConds(root, cases) + approximator.approximateMatch + } - Test(tm match { - case ProductExtractorTreeMaker(pb, None, subst) => Top // TODO: NotNullTest(prevBinder) - case tm@TypeTestTreeMaker(prevBinder, nextBinderTp, _) => TypeCond(binderToUniqueTree(prevBinder), uniqueTp(nextBinderTp)) - case tm@TypeAndEqualityTestTreeMaker(_, patBinder, pt, _) => TypeAndEqualityCond(binderToUniqueTree(patBinder), uniqueTp(pt)) - case tm@EqualityTestTreeMaker(prevBinder, patTree, _) => EqualityCond(binderToUniqueTree(prevBinder), unique(patTree)) - case ExtractorTreeMaker(_, _, _, _) - | GuardTreeMaker(_) - | ProductExtractorTreeMaker(_, Some(_), _) => Havoc - case AlternativesTreeMaker(_, _, _) => Havoc // TODO: can do better here - case SubstOnlyTreeMaker(_, _) => Top - case BodyTreeMaker(_, _) => Havoc - }, tm) - } + def showTreeMakers(cases: List[List[TreeMaker]]) = { + println("treeMakers:") + println(alignAcrossRows(cases, ">>")) + } + + def showTests(testss: List[List[Test]]) = { + println("tests: ") + println(alignAcrossRows(testss, "&")) + } + } + + trait Prettification { + private def max(xs: Seq[Int]) = if (xs isEmpty) 0 else xs max - cases.map { _ map approximateTreeMaker } + def alignedColumns(cols: Seq[AnyRef]): Seq[String] = { + def toString(x: AnyRef) = if (x eq null) "" else x.toString + if (cols.isEmpty || cols.tails.isEmpty) cols map toString + else { + val (colStrs, colLens) = cols map {c => val s = toString(c); (s, s.length)} unzip + val maxLen = max(colLens) + val avgLen = colLens.sum/colLens.length + val goalLen = maxLen min avgLen*2 + def pad(s: String) = { + val toAdd = ((goalLen - s.length) max 0) + 2 + (" " * (toAdd/2)) + s + (" " * (toAdd/2 + (toAdd%2))) + } + cols map (x => pad(toString(x))) + } + } + def alignAcrossRows(xss: List[List[AnyRef]], sep: String, lineSep: String = "\n"): String = { + val maxLen = max(xss map (_.length)) + val padded = xss map (xs => xs ++ List.fill(maxLen - xs.length)(null)) + padded.transpose.map(alignedColumns).transpose map (_.mkString(sep)) mkString(lineSep) } } @@ -1446,28 +1571,49 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // interpret: val dependencies = new collection.mutable.LinkedHashMap[Test, Set[Cond]] val tested = new collection.mutable.HashSet[Cond] - testss foreach { tests => - tested.clear() - tests dropWhile { test => - val cond = test.cond - if ((cond eq Havoc) || (cond eq Top)) (cond eq Top) // stop when we encounter a havoc, skip top - else { - tested += cond + + def storeDependencies(test: Test) = { + val cond = test.cond + + def simplify(c: Cond): Set[Cond] = c match { + case AndCond(a, b) => simplify(a) ++ simplify(b) + case OrCond(_, _) => Set(Havoc) // TODO: supremum? + case NonNullCond(_) => Set(Top) // not worth remembering + case _ => Set(c) + } + val conds = simplify(cond) + + if (conds(Havoc)) false // stop when we encounter a havoc + else { + val nonTrivial = conds filterNot (_ == Top) + if (nonTrivial nonEmpty) { + tested ++= nonTrivial // is there an earlier test that checks our condition and whose dependencies are implied by ours? - dependencies find { case (priorTest, deps) => - ((priorTest.cond eq cond) || (deps contains cond)) && (deps subsetOf tested) - } foreach { case (priorTest, deps) => - // if so, note the dependency in both tests - priorTest registerReuseBy test + dependencies find { + 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 + } foreach { + case (priorTest, _) => + // if so, note the dependency in both tests + priorTest registerReuseBy test } dependencies(test) = tested.toSet // copies - true } + true } } + + testss foreach { tests => + tested.clear() + tests dropWhile storeDependencies + } + // println("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 // store the result of the final test and the intermediate results in hoisted mutable variables (TODO: optimize: don't store intermediate results that aren't used) @@ -1476,7 +1622,12 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL var okToCall = false val reusedOrOrig = (tm: TreeMaker) => {assert(okToCall); reused.getOrElse(tm, tm)} - val res = testss map { tests => + // maybe collapse: replace shared prefix of tree makers by a ReusingCondTreeMaker + // once this has been computed, we'll know which tree makers are reused, + // and we'll replace those by the ReusedCondTreeMakers we've constructed (and stored in the reused map) + val collapsed = testss map { tests => + // map tests to the equivalent list of treemakers, replacing shared prefixes by a reusing treemaker + // if there's no sharing, simply map to the tree makers corresponding to the tests var currDeps = Set[Cond]() val (sharedPrefix, suffix) = tests span { test => (test.cond eq Top) || (for( @@ -1487,23 +1638,33 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL yield diff).nonEmpty } - val collapsedTreeMakers = if (sharedPrefix.nonEmpty) { // even sharing prefixes of length 1 brings some benefit (overhead-percentage for compiler: 26->24%, lib: 19->16%) - for (test <- sharedPrefix; reusedTest <- test.reuses) reusedTest.treeMaker match { - case reusedCTM: CondTreeMaker => reused(reusedCTM) = ReusedCondTreeMaker(reusedCTM) - case _ => - } + val collapsedTreeMakers = + if (sharedPrefix.isEmpty) None + else { // even sharing prefixes of length 1 brings some benefit (overhead-percentage for compiler: 26->24%, lib: 19->16%) + for (test <- sharedPrefix; reusedTest <- test.reuses) reusedTest.treeMaker match { + case reusedCTM: CondTreeMaker => reused(reusedCTM) = ReusedCondTreeMaker(reusedCTM) + case _ => + } - // println("sharedPrefix: "+ sharedPrefix) - for (lastShared <- sharedPrefix.reverse.dropWhile(_.cond eq Top).headOption; - lastReused <- lastShared.reuses) - yield ReusingCondTreeMaker(sharedPrefix, reusedOrOrig) :: suffix.map(_.treeMaker) - } else None + // println("sharedPrefix: "+ sharedPrefix) + // if the shared prefix contains interesting conditions (!= Top) + // and the last of such interesting shared conditions reuses another treemaker's test + // replace the whole sharedPrefix by a ReusingCondTreeMaker + for (lastShared <- sharedPrefix.reverse.dropWhile(_.cond eq Top).headOption; + lastReused <- lastShared.reuses) + yield ReusingCondTreeMaker(sharedPrefix, reusedOrOrig) :: suffix.map(_.treeMaker) + } collapsedTreeMakers getOrElse tests.map(_.treeMaker) // sharedPrefix need not be empty (but it only contains Top-tests, which are dropped above) } okToCall = true // TODO: remove (debugging) - res mapConserve (_ mapConserve reusedOrOrig) + // replace original treemakers that are reused (as determined when computing collapsed), + // by ReusedCondTreeMakers + val reusedMakers = collapsed mapConserve (_ mapConserve reusedOrOrig) +// println("after CSE:") +// showTreeMakers(reusedMakers) + reusedMakers } object ReusedCondTreeMaker { @@ -1520,28 +1681,45 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // TODO: finer-grained duplication def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(codegen eq optimizedCodegen) atPos(pos)(casegen.asInstanceOf[optimizedCodegen.OptimizedCasegen].flatMapCondStored(cond, storedCond, res, nextBinder, substitution(next).duplicate)) + + override def toString = "Memo"+(nextBinder.name, storedCond.name, cond, res, substitution) } case class ReusingCondTreeMaker(sharedPrefix: List[Test], toReused: TreeMaker => TreeMaker) extends TreeMaker { import CODE._ - lazy val dropped_priors = sharedPrefix map (t => (toReused(t.treeMaker), t.reuses map (test => toReused(test.treeMaker)))) lazy val localSubstitution = { - val (from, to) = dropped_priors.collect { - case (dropped: CondTreeMaker, Some(prior: ReusedCondTreeMaker)) => - (dropped.nextBinder, REF(prior.nextBinder)) - }.unzip - val oldSubs = dropped_priors.collect { - case (dropped: TreeMaker, _) => - dropped.substitution + // replace binder of each dropped treemaker by corresponding binder bound by the most recent reused treemaker + var mostRecentReusedMaker: ReusedCondTreeMaker = null + def mapToStored(droppedBinder: Symbol) = if (mostRecentReusedMaker eq null) Nil else List((droppedBinder, REF(mostRecentReusedMaker.nextBinder))) + val (from, to) = sharedPrefix.flatMap { dropped => + dropped.reuses.map(test => toReused(test.treeMaker)).foreach { + case reusedMaker: ReusedCondTreeMaker => + mostRecentReusedMaker = reusedMaker + case _ => } - oldSubs.foldLeft(Substitution(from, to))(_ >> _) + + // TODO: have super-trait for retrieving the variable that's operated on by a tree maker + // and thus assumed in scope, either because it binds it or because it refers to it + dropped.treeMaker match { + case dropped: FunTreeMaker => + mapToStored(dropped.nextBinder) + case _ => Nil + } + }.unzip + val rerouteToReusedBinders = Substitution(from, to) + + val collapsedDroppedSubst = sharedPrefix map (t => (toReused(t.treeMaker).substitution)) + + collapsedDroppedSubst.foldLeft(rerouteToReusedBinders)(_ >> _) } - def chainBefore(next: Tree)(casegen: Casegen): Tree = { - val cond = REF(dropped_priors.reverse.collectFirst{case (_, Some(ctm: ReusedCondTreeMaker)) => ctm}.get.storedCond) + lazy val lastReusedTreeMaker = sharedPrefix.reverse.flatMap(tm => tm.reuses map (test => toReused(test.treeMaker))).collectFirst{case x: ReusedCondTreeMaker => x}.head - // TODO: finer-grained duplication -- MUST duplicate though, or we'll get VerifyErrors since sharing trees confuses lambdalift, and its confusion it emits illegal casts (diagnosed by Grzegorz: checkcast T ; invokevirtual S.m, where T not a subtype of S) - casegen.ifThenElseZero(cond, substitution(next).duplicate) + def chainBefore(next: Tree)(casegen: Casegen): Tree = { + // TODO: finer-grained duplication -- MUST duplicate though, or we'll get VerifyErrors since sharing trees confuses lambdalift, + // and in its confusion it emits illegal casts (diagnosed by Grzegorz: checkcast T ; invokevirtual S.m, where T not a subtype of S) + casegen.ifThenElseZero(REF(lastReusedTreeMaker.storedCond), substitution(next).duplicate) } + override def toString = "R"+(lastReusedTreeMaker.storedCond.name, substitution) } } @@ -1669,10 +1847,8 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL // analyze the result of approximateTreeMaker rather than the TreeMaker itself object SwitchableTreeMaker extends SwitchableTreeMakerExtractor { def unapply(x: TreeMaker): Option[Tree] = x match { - case tm@TypeTestTreeMaker(_, _, _) => - Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(tm.nextBinderTp)) /* not used by back-end */)) // -- TODO: use this if binder does not occur in the body - case tm@TypeAndEqualityTestTreeMaker(_, patBinder, pt, _) if tm.isStraightTypeTest => - Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(tm.nextBinderTp)) /* not used by back-end */)) + case tm@TypeTestTreeMaker(_, _, pt, _) if tm.isPureTypeTest => // -- TODO: use this if binder does not occur in the body + Some(Bind(tm.nextBinder, Typed(Ident(nme.WILDCARD), TypeTree(pt)) /* not used by back-end */)) case _ => None } @@ -1824,7 +2000,7 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL with DeadCodeElimination with SwitchEmission with OptimizedCodegen { self: TreeMakers => - override def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) = { + override def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type, unchecked: Boolean): (List[List[TreeMaker]], List[Tree]) = { val optCases = doCSE(prevBinder, doDCE(prevBinder, cases, pt), pt) val toHoist = ( for (treeMakers <- optCases) |