diff options
author | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-05-22 11:03:42 +0200 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-05-22 11:34:08 +0200 |
commit | 0497c1513b9c8e561e16ebb56a004b5baabf8ecd (patch) | |
tree | b931cbe279484621f4849c510588a0ee89c4bb1e /src/compiler | |
parent | f406550146250f5a6036d3d778582efa6d68252a (diff) | |
download | scala-0497c1513b9c8e561e16ebb56a004b5baabf8ecd.tar.gz scala-0497c1513b9c8e561e16ebb56a004b5baabf8ecd.tar.bz2 scala-0497c1513b9c8e561e16ebb56a004b5baabf8ecd.zip |
TreeMaker approximation refactorings and bug fixes
- TypeTestTreeMaker subsumes the old TypeTestTM and TypeAndEqualityTM
its type- and equality-testing logic is configurable so that it can:
- generate trees (main purpose)
- check whether this tree maker is a pure type test
- generate the proposition that models this tree maker
(for exhaustivity and other analyses)
- [CSE] subst binders of dropped tm's to stored ones
somehow the refactoring broke the replacement of the binder of dropped
treemakers by the binder of the reused treemaker
when replacing
TM1(x1 => ...) >> TM2(x2 => ...) >> TM3(x3 => ...) >> ...
TM1'(x1' => ...) >> TM2'(x2' => ...) >> TM3(x3' => ...) >> ...
by
Memo1(x1 => ...) >> TM2(x2 => ...) >> Memo2(x3 => ...) >> ...
Reuse(Memo2)...
you need to replace x1' and x2' by x1
since TM2 tested a shared condition but was not memo-ised,
that implies it simply passed x1 through to x3 unmodified,
and x2' can simply use the stored x1
- type of first uniqued binder sets type of tree
when approximating a tree of treemakers as a DAG,
where sharing indicates the same value is tested,
use the type of the binder that was first used to
create a unique tree as the type of that tree,
and thus all trees used for the same binder in the future
- track substitution of alternatives when approximating
- error on unswitchable @switch annotated matches
if we can't turn a match (with more than two cases) into a switch,
but the user insists, emit an error
misc notes:
- when all you need is nextBinder, FunTreeMaker is your guy
- must pass flag to TypeTestTM for extractorarg test
case TypeTestTreeMaker(prevBinder, testedBinder, expectedTp, nextBinderTp)
(prevBinder eq testedBinder) does not imply it's a pure type test for an extractor call
note that the expected type for an extractor argument is not a type pattern,
thus we only do a classic type test -- the idea was to detect that case by noticing we're
being called with the same previous and tested binder, but that case also arises
for Typed patterns
Diffstat (limited to 'src/compiler')
-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) |