From 6a7078c598f91fb23f8e43d792415fdd1719b4ff Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Fri, 15 Feb 2013 17:30:22 -0800 Subject: remove unused imports --- .../scala/tools/nsc/transform/patmat/Logic.scala | 85 +++++++++---------- .../tools/nsc/transform/patmat/MatchAnalysis.scala | 82 ++++++++---------- .../tools/nsc/transform/patmat/MatchCodeGen.scala | 24 ++---- .../nsc/transform/patmat/MatchOptimization.scala | 39 ++++----- .../nsc/transform/patmat/MatchTranslation.scala | 96 ++++------------------ .../nsc/transform/patmat/MatchTreeMakers.scala | 52 +++++------- .../nsc/transform/patmat/PatternMatching.scala | 91 +++++++++++++++----- 7 files changed, 206 insertions(+), 263 deletions(-) diff --git a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala index 23c0272a30..9af4800a70 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/Logic.scala @@ -6,26 +6,16 @@ package scala.tools.nsc.transform.patmat -import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -import transform._ -import typechecker._ -import symtab._ -import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} +import scala.tools.nsc.symtab._ import scala.language.postfixOps -import scala.tools.nsc.transform.TypingTransformers -import scala.tools.nsc.transform.Transform import scala.collection.mutable import scala.reflect.internal.util.Statistics -import scala.reflect.internal.Types +import scala.reflect.internal.util.Position import scala.reflect.internal.util.HashSet -trait Logic { self: PatternMatching => +trait Logic extends Debugging { import PatternMatchingStats._ - val global: Global - import global.{Type, Tree, currentUnit, Position} - - import debugging.patmatDebug private def max(xs: Seq[Int]) = if (xs isEmpty) 0 else xs max private def alignedColumns(cols: Seq[AnyRef]): Seq[String] = { @@ -54,6 +44,9 @@ trait Logic { self: PatternMatching => // http://users.encs.concordia.ca/~ta_ahmed/ms_thesis.pdf // propositional logic with constants and equality trait PropositionalLogic { + type Type + type Tree + class Prop case class Eq(p: Var, q: Const) extends Prop @@ -172,14 +165,11 @@ trait Logic { self: PatternMatching => import scala.tools.cmd.FromString.IntFromString val max = sys.props.get("scalac.patmat.analysisBudget").collect(IntFromString.orElse{case "off" => Integer.MAX_VALUE}).getOrElse(256) - abstract class Exception extends RuntimeException("CNF budget exceeded") { - val advice: String - def warn(pos: Position, kind: String) = currentUnit.uncheckedWarning(pos, s"Cannot check match for $kind.\n$advice") - } + abstract class Exception(val advice: String) extends RuntimeException("CNF budget exceeded") + + object exceeded extends Exception( + s"(The analysis required more space than allowed. Please try with scalac -Dscalac.patmat.analysisBudget=${AnalysisBudget.max*2} or -Dscalac.patmat.analysisBudget=off.)") - object exceeded extends Exception { - val advice = s"(The analysis required more space than allowed. Please try with scalac -Dscalac.patmat.analysisBudget=${AnalysisBudget.max*2} or -Dscalac.patmat.analysisBudget=off.)" - } } // convert finite domain propositional logic with subtyping to pure boolean propositional logic @@ -229,7 +219,7 @@ trait Logic { self: PatternMatching => val eqAxioms = formulaBuilder @inline def addAxiom(p: Prop) = addFormula(eqAxioms, eqFreePropToSolvable(p)) - patmatDebug("removeVarEq vars: "+ vars) + debug.patmat("removeVarEq vars: "+ vars) vars.foreach { v => // if v.domainSyms.isEmpty, we must consider the domain to be infinite // otherwise, since the domain fully partitions the type of the value, @@ -253,8 +243,8 @@ trait Logic { self: PatternMatching => } } - patmatDebug("eqAxioms:\n"+ cnfString(toFormula(eqAxioms))) - patmatDebug("pure:"+ pure.map(p => cnfString(p)).mkString("\n")) + debug.patmat("eqAxioms:\n"+ cnfString(toFormula(eqAxioms))) + debug.patmat("pure:"+ pure.map(p => cnfString(p)).mkString("\n")) if (Statistics.canEnable) Statistics.stopTimer(patmatAnaVarEq, start) @@ -402,7 +392,7 @@ trait Logic { self: PatternMatching => // if (Statistics.canEnable) patmatCNFSizes(res.size).value += 1 -// patmatDebug("cnf for\n"+ p +"\nis:\n"+cnfString(res)) +// debug.patmat("cnf for\n"+ p +"\nis:\n"+cnfString(res)) res } } @@ -430,19 +420,19 @@ trait Logic { self: PatternMatching => // returns all solutions, if any (TODO: better infinite recursion backstop -- detect fixpoint??) def findAllModelsFor(f: Formula): List[Model] = { val vars: Set[Sym] = f.flatMap(_ collect {case l: Lit => l.sym}).toSet - // patmatDebug("vars "+ vars) + // debug.patmat("vars "+ vars) // the negation of a model -(S1=True/False /\ ... /\ SN=True/False) = clause(S1=False/True, ...., SN=False/True) def negateModel(m: Model) = clause(m.toSeq.map{ case (sym, pos) => Lit(sym, !pos) } : _*) def findAllModels(f: Formula, models: List[Model], recursionDepthAllowed: Int = 10): List[Model]= if (recursionDepthAllowed == 0) models else { - patmatDebug("find all models for\n"+ cnfString(f)) + debug.patmat("find all models for\n"+ cnfString(f)) val model = findModelFor(f) // if we found a solution, conjunct the formula with the model's negation and recurse if (model ne NoModel) { val unassigned = (vars -- model.keySet).toList - patmatDebug("unassigned "+ unassigned +" in "+ model) + debug.patmat("unassigned "+ unassigned +" in "+ model) def force(lit: Lit) = { val model = withLit(findModelFor(dropUnit(f, lit)), lit) if (model ne NoModel) List(model) @@ -451,7 +441,7 @@ trait Logic { self: PatternMatching => val forced = unassigned flatMap { s => force(Lit(s, true)) ++ force(Lit(s, false)) } - patmatDebug("forced "+ forced) + debug.patmat("forced "+ forced) val negated = negateModel(model) findAllModels(f :+ negated, model :: (forced ++ models), recursionDepthAllowed - 1) } @@ -479,7 +469,7 @@ trait Logic { self: PatternMatching => def findModelFor(f: Formula): Model = { @inline def orElse(a: Model, b: => Model) = if (a ne NoModel) a else b - patmatDebug("DPLL\n"+ cnfString(f)) + debug.patmat("DPLL\n"+ cnfString(f)) val start = if (Statistics.canEnable) Statistics.startTimer(patmatAnaDPLL) else null @@ -489,7 +479,7 @@ trait Logic { self: PatternMatching => else f.find(_.size == 1) match { case Some(unitClause) => val unitLit = unitClause.head - // patmatDebug("unit: "+ unitLit) + // debug.patmat("unit: "+ unitLit) withLit(findModelFor(dropUnit(f, unitLit)), unitLit) case _ => // partition symbols according to whether they appear in positive and/or negative literals @@ -509,12 +499,12 @@ trait Logic { self: PatternMatching => // (since equality on literals is in terms of equality // of the underlying symbol and its positivity, simply construct a new Lit) val pureLit = Lit(pureSym, pos(pureSym)) - // patmatDebug("pure: "+ pureLit +" pures: "+ pures +" impures: "+ impures) + // debug.patmat("pure: "+ pureLit +" pures: "+ pures +" impures: "+ impures) val simplified = f.filterNot(_.contains(pureLit)) withLit(findModelFor(simplified), pureLit) } else { val split = f.head.head - // patmatDebug("split: "+ split) + // debug.patmat("split: "+ split) orElse(findModelFor(f :+ clause(split)), findModelFor(f :+ clause(-split))) } } @@ -524,8 +514,13 @@ trait Logic { self: PatternMatching => satisfiableWithModel } } +} +trait ScalaLogic extends Logic { self: PatternMatching => trait TreesAndTypesDomain extends PropositionalLogic with CheckableTreeAndTypeAnalysis { + type Type = global.Type + type Tree = global.Tree + // resets hash consing -- only supposed to be called by TreeMakersToProps def prepareNewAnalysis(): Unit = { Var.resetUniques(); Const.resetUniques() } @@ -542,7 +537,7 @@ trait Logic { self: PatternMatching => private[this] val id: Int = Var.nextId // private[this] var canModify: Option[Array[StackTraceElement]] = None - private[this] def ensureCanModify() = {} //if (canModify.nonEmpty) patmatDebug("BUG!"+ this +" modified after having been observed: "+ canModify.get.mkString("\n")) + private[this] def ensureCanModify() = {} //if (canModify.nonEmpty) debug.patmat("BUG!"+ this +" modified after having been observed: "+ canModify.get.mkString("\n")) private[this] def observed() = {} //canModify = Some(Thread.currentThread.getStackTrace) @@ -613,8 +608,8 @@ trait Logic { self: PatternMatching => (lower != NullConst && !upper.isValue && instanceOfTpImplies(if (lower.isValue) lower.wideTp else lower.tp, upper.tp)) - // if(r) patmatDebug("implies : "+(lower, lower.tp, upper, upper.tp)) - // else patmatDebug("NOT implies: "+(lower, upper)) + // if(r) debug.patmat("implies : "+(lower, lower.tp, upper, upper.tp)) + // else debug.patmat("NOT implies: "+(lower, upper)) /** does V = C preclude V having value `other`? @@ -630,8 +625,8 @@ trait Logic { self: PatternMatching => def excludes(a: Const, b: Const): Boolean = a != b && ((a == NullConst || b == NullConst) || (a.isValue && b.isValue)) - // if(r) patmatDebug("excludes : "+(a, a.tp, b, b.tp)) - // else patmatDebug("NOT excludes: "+(a, b)) + // if(r) debug.patmat("excludes : "+(a, a.tp, b, b.tp)) + // else debug.patmat("NOT excludes: "+(a, b)) /* [ HALF BAKED FANCINESS: //!equalitySyms.exists(common => implies(common.const, a) && implies(common.const, b))) @@ -678,9 +673,9 @@ trait Logic { self: PatternMatching => val (excluded, notExcluded) = todo partition (b => excludes(sym.const, b.const)) val implied = notExcluded filter (b => implies(sym.const, b.const)) - patmatDebug("eq axioms for: "+ sym.const) - patmatDebug("excluded: "+ excluded) - patmatDebug("implied: "+ implied) + debug.patmat("eq axioms for: "+ sym.const) + debug.patmat("excluded: "+ excluded) + debug.patmat("implied: "+ implied) excluded foreach { excludedSym => excludedPair += ExcludedPair(sym.const, excludedSym.const)} @@ -729,11 +724,11 @@ trait Logic { self: PatternMatching => uniques.get(tp).getOrElse( uniques.find {case (oldTp, oldC) => oldTp =:= tp} match { case Some((_, c)) => - patmatDebug("unique const: "+ (tp, c)) + debug.patmat("unique const: "+ (tp, c)) c case _ => val fresh = mkFresh - patmatDebug("uniqued const: "+ (tp, fresh)) + debug.patmat("uniqued const: "+ (tp, fresh)) uniques(tp) = fresh fresh }) @@ -749,12 +744,12 @@ trait Logic { self: PatternMatching => if (!t.symbol.isStable) t.tpe.narrow else trees find (a => a.correspondsStructure(t)(sameValue)) match { case Some(orig) => - patmatDebug("unique tp for tree: "+ (orig, orig.tpe)) + debug.patmat("unique tp for tree: "+ (orig, orig.tpe)) orig.tpe case _ => // duplicate, don't mutate old tree (TODO: use a map tree -> type instead?) val treeWithNarrowedType = t.duplicate setType t.tpe.narrow - patmatDebug("uniqued: "+ (t, t.tpe, treeWithNarrowedType.tpe)) + debug.patmat("uniqued: "+ (t, t.tpe, treeWithNarrowedType.tpe)) trees += treeWithNarrowedType treeWithNarrowedType.tpe } @@ -839,7 +834,7 @@ trait Logic { self: PatternMatching => } } sealed class ValueConst(val tp: Type, val wideTp: Type, override val toString: String) extends Const { - // patmatDebug("VC"+(tp, wideTp, toString)) + // debug.patmat("VC"+(tp, wideTp, toString)) assert(!(tp =:= NullTp)) // TODO: assert(!tp.isStable) /*private[this] val id: Int = */Const.nextValueId def isValue = true diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala index 1e12975880..39157e3843 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala @@ -6,21 +6,12 @@ package scala.tools.nsc.transform.patmat -import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -import transform._ -import typechecker._ -import symtab._ -import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} import scala.language.postfixOps -import scala.tools.nsc.transform.TypingTransformers -import scala.tools.nsc.transform.Transform import scala.collection.mutable import scala.reflect.internal.util.Statistics -import scala.reflect.internal.Types -import scala.reflect.internal.util.HashSet +import scala.reflect.internal.util.Position trait TreeAndTypeAnalysis extends Debugging { - val global: Global import global.{Tree, Type, Symbol, definitions, analyzer, ConstantType, Literal, Constant, appliedType, WildcardType, TypeRef, ModuleClassSymbol, nestedMemberType, TypeMap, Ident} @@ -28,7 +19,6 @@ trait TreeAndTypeAnalysis extends Debugging { import definitions._ import analyzer.Typer - import debugging.patmatDebug // we use subtyping as a model for implication between instanceof tests // i.e., when S <:< T we assume x.isInstanceOf[S] implies x.isInstanceOf[T] @@ -70,7 +60,7 @@ trait TreeAndTypeAnalysis extends Debugging { Some(List(tp)) // make sure it's not a primitive, else (5: Byte) match { case 5 => ... } sees no Byte case sym if !sym.isSealed || isPrimitiveValueClass(sym) => - patmatDebug("enum unsealed "+ (tp, sym, sym.isSealed, isPrimitiveValueClass(sym))) + debug.patmat("enum unsealed "+ (tp, sym, sym.isSealed, isPrimitiveValueClass(sym))) None case sym => val subclasses = ( @@ -78,7 +68,7 @@ trait TreeAndTypeAnalysis extends Debugging { // symbols which are both sealed and abstract need not be covered themselves, because // all of their children must be and they cannot otherwise be created. filterNot (x => x.isSealed && x.isAbstractClass && !isPrimitiveValueClass(x))) - patmatDebug("enum sealed -- subclasses: "+ (sym, subclasses)) + debug.patmat("enum sealed -- subclasses: "+ (sym, subclasses)) val tpApprox = typer.infer.approximateAbstracts(tp) val pre = tpApprox.prefix @@ -92,11 +82,11 @@ trait TreeAndTypeAnalysis extends Debugging { val memberType = nestedMemberType(sym, pre, tpApprox.typeSymbol.owner) val subTp = appliedType(memberType, sym.typeParams.map(_ => WildcardType)) val subTpApprox = typer.infer.approximateAbstracts(subTp) // TODO: needed? - // patmatDebug("subtp"+(subTpApprox <:< tpApprox, subTpApprox, tpApprox)) + // debug.patmat("subtp"+(subTpApprox <:< tpApprox, subTpApprox, tpApprox)) if (subTpApprox <:< tpApprox) Some(checkableType(subTp)) else None }) - patmatDebug("enum sealed "+ (tp, tpApprox) + " as "+ validSubTypes) + debug.patmat("enum sealed "+ (tp, tpApprox) + " as "+ validSubTypes) Some(validSubTypes) } @@ -118,7 +108,7 @@ trait TreeAndTypeAnalysis extends Debugging { } val res = typeArgsToWildcardsExceptArray(tp) - patmatDebug("checkable "+(tp, res)) + debug.patmat("checkable "+(tp, res)) res } @@ -129,7 +119,7 @@ trait TreeAndTypeAnalysis extends Debugging { val checkable = ( (isTupleType(tp) && tupleComponents(tp).exists(tp => !uncheckableType(tp))) || enumerateSubtypes(tp).nonEmpty) - // if (!checkable) patmatDebug("deemed uncheckable: "+ tp) + // if (!checkable) debug.patmat("deemed uncheckable: "+ tp) !checkable } } @@ -137,8 +127,7 @@ trait TreeAndTypeAnalysis extends Debugging { trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => import PatternMatchingStats._ - val global: Global - import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition, + import global.{Tree, Type, Symbol, CaseDef, atPos, Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest, ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser, Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef, @@ -148,8 +137,6 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => import definitions._ import analyzer.{Typer, ErrorUtils, formalTypes} - import debugging.patmatDebug - /** * Represent a match as a formula in propositional logic that encodes whether the match matches (abstractly: we only consider types) * @@ -196,8 +183,8 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => uniqueTypeProps getOrElseUpdate((testedPath, pt), Eq(Var(testedPath), TypeConst(checkableType(pt)))) // a variable in this set should never be replaced by a tree that "does not consist of a selection on a variable in this set" (intuitively) - private val pointsToBound = scala.collection.mutable.HashSet(root) - private val trees = scala.collection.mutable.HashSet.empty[Tree] + private val pointsToBound = mutable.HashSet(root) + private val trees = mutable.HashSet.empty[Tree] // the substitution that renames variables to variables in pointsToBound private var normalize: Substitution = EmptySubstitution @@ -215,7 +202,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => def unique(t: Tree, tpOverride: Type = NoType): Tree = trees find (a => a.correspondsStructure(t)(sameValue)) match { case Some(orig) => - // patmatDebug("unique: "+ (t eq orig, orig)) + // debug.patmat("unique: "+ (t eq orig, orig)) orig case _ => trees += t @@ -253,14 +240,14 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => // reverse substitution that would otherwise replace a variable we already encountered by a new variable // NOTE: this forgets the more precise type we have for these later variables, but that's probably okay normalize >>= Substitution(boundTo map (_.symbol), boundFrom map (CODE.REF(_))) - // patmatDebug ("normalize subst: "+ normalize) + // debug.patmat ("normalize subst: "+ normalize) val okSubst = Substitution(unboundFrom, unboundTo map (normalize(_))) // it's important substitution does not duplicate trees here -- it helps to keep hash consing simple, anyway pointsToBound ++= ((okSubst.from, okSubst.to).zipped filter { (f, t) => pointsToBound exists (sym => t.exists(_.symbol == sym)) })._1 - // patmatDebug("pointsToBound: "+ pointsToBound) + // debug.patmat("pointsToBound: "+ pointsToBound) accumSubst >>= okSubst - // patmatDebug("accumSubst: "+ accumSubst) + // debug.patmat("accumSubst: "+ accumSubst) } def handleUnknown(tm: TreeMaker): Prop @@ -351,18 +338,21 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => /\(tests.takeWhile(t => !t.treeMaker.isInstanceOf[BodyTreeMaker]).map(t => t.prop)) def showTreeMakers(cases: List[List[TreeMaker]]) = { - patmatDebug("treeMakers:") - patmatDebug(alignAcrossRows(cases, ">>")) + debug.patmat("treeMakers:") + debug.patmat(alignAcrossRows(cases, ">>")) } def showTests(testss: List[List[Test]]) = { - patmatDebug("tests: ") - patmatDebug(alignAcrossRows(testss, "&")) + debug.patmat("tests: ") + debug.patmat(alignAcrossRows(testss, "&")) } } trait SymbolicMatchAnalysis extends TreeMakerApproximation { self: CodegenCore => - // TODO: model dependencies between variables: if V1 corresponds to (x: List[_]) and V2 is (x.hd), V2 cannot be assigned when V1 = null or V1 = Nil + def uncheckedWarning(pos: Position, msg: String) = global.currentUnit.uncheckedWarning(pos, msg) + def warn(pos: Position, ex: AnalysisBudget.Exception, kind: String) = uncheckedWarning(pos, s"Cannot check match for $kind.\n${ex.advice}") + + // TODO: model dependencies between variables: if V1 corresponds to (x: List[_]) and V2 is (x.hd), V2 cannot be assigned when V1 = null or V1 = Nil // right now hackily implement this by pruning counter-examples // unreachability would also benefit from a more faithful representation @@ -403,8 +393,8 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => var reachable = true var caseIndex = 0 - patmatDebug("reachability, vars:\n"+ ((propsCasesFail flatMap gatherVariables).distinct map (_.describe) mkString ("\n"))) - patmatDebug("equality axioms:\n"+ cnfString(eqAxiomsOk)) + debug.patmat("reachability, vars:\n"+ ((propsCasesFail flatMap gatherVariables).distinct map (_.describe) mkString ("\n"))) + debug.patmat("equality axioms:\n"+ cnfString(eqAxiomsOk)) // invariant (prefixRest.length == current.length) && (prefix.reverse ++ prefixRest == symbolicCasesFail) // termination: prefixRest.length decreases by 1 @@ -418,8 +408,8 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => current = current.tail val model = findModelFor(andFormula(current.head, toFormula(prefix))) - // patmatDebug("trying to reach:\n"+ cnfString(current.head) +"\nunder prefix:\n"+ cnfString(prefix)) - // if (NoModel ne model) patmatDebug("reached: "+ modelString(model)) + // debug.patmat("trying to reach:\n"+ cnfString(current.head) +"\nunder prefix:\n"+ cnfString(prefix)) + // if (NoModel ne model) debug.patmat("reached: "+ modelString(model)) reachable = NoModel ne model } @@ -430,7 +420,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => if (reachable) None else Some(caseIndex) } catch { case ex: AnalysisBudget.Exception => - ex.warn(prevBinder.pos, "unreachability") + warn(prevBinder.pos, ex, "unreachability") None // CNF budget exceeded } } @@ -451,7 +441,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => val symbolicCases = approx.approximateMatch(cases, approx.onUnknown { tm => approx.fullRewrite.applyOrElse[TreeMaker, Prop](tm, { case BodyTreeMaker(_, _) => True // irrelevant -- will be discarded by symbolCase later - case _ => // patmatDebug("backing off due to "+ tm) + case _ => // debug.patmat("backing off due to "+ tm) backoff = true False }) @@ -474,11 +464,11 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => val matchFails = Not(\/(symbolicCases)) // debug output: - patmatDebug("analysing:") + debug.patmat("analysing:") showTreeMakers(cases) - // patmatDebug("\nvars:\n"+ (vars map (_.describe) mkString ("\n"))) - // patmatDebug("\nmatchFails as CNF:\n"+ cnfString(propToSolvable(matchFails))) + // debug.patmat("\nvars:\n"+ (vars map (_.describe) mkString ("\n"))) + // debug.patmat("\nmatchFails as CNF:\n"+ cnfString(propToSolvable(matchFails))) try { // find the models (under which the match fails) @@ -493,7 +483,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => pruned } catch { case ex : AnalysisBudget.Exception => - ex.warn(prevBinder.pos, "exhaustivity") + warn(prevBinder.pos, ex, "exhaustivity") Nil // CNF budget exceeded } } @@ -580,14 +570,14 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => // ... val varAssignment = modelToVarAssignment(model) - patmatDebug("var assignment for model "+ model +":\n"+ varAssignmentString(varAssignment)) + debug.patmat("var assignment for model "+ model +":\n"+ varAssignmentString(varAssignment)) // chop a path into a list of symbols def chop(path: Tree): List[Symbol] = path match { case Ident(_) => List(path.symbol) case Select(pre, name) => chop(pre) :+ path.symbol case _ => - // patmatDebug("don't know how to chop "+ path) + // debug.patmat("don't know how to chop "+ path) Nil } @@ -647,7 +637,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => def toCounterExample(beBrief: Boolean = false): CounterExample = if (!allFieldAssignmentsLegal) NoExample else { - patmatDebug("describing "+ (variable, equalTo, notEqualTo, fields, cls, allFieldAssignmentsLegal)) + debug.patmat("describing "+ (variable, equalTo, notEqualTo, fields, cls, allFieldAssignmentsLegal)) val res = prunedEqualTo match { // a definite assignment to a value case List(eq: ValueConst) if fields.isEmpty => ValueExample(eq) @@ -688,7 +678,7 @@ trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => // TODO: improve reasoning -- in the mean time, a false negative is better than an annoying false positive case _ => NoExample } - patmatDebug("described as: "+ res) + debug.patmat("described as: "+ res) res } diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala index a22d35a6b4..4c024cf71c 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala @@ -6,30 +6,18 @@ package scala.tools.nsc.transform.patmat -import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -import transform._ -import typechecker._ -import symtab._ -import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} +import scala.tools.nsc.symtab.Flags.SYNTHETIC import scala.language.postfixOps -import scala.tools.nsc.transform.TypingTransformers -import scala.tools.nsc.transform.Transform -import scala.collection.mutable import scala.reflect.internal.util.Statistics -import scala.reflect.internal.Types -import scala.reflect.internal.util.HashSet +import scala.reflect.internal.util.Position +import scala.reflect.internal.util.NoPosition trait CodeGen { self: PatternMatching => import PatternMatchingStats._ - val global: Global - import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition, - Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest, - ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser, - Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef, - UniqueType, RefinedType, currentUnit, SingletonType, singleType, ModuleClassSymbol, - nestedMemberType, TypeMap, EmptyScope, Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw, newTermName} + import global.{nme, treeInfo, definitions, gen, Tree, Type, Symbol, NoSymbol, + appliedType, NoType, MethodType, newTermName, Name, + Block, Literal, Constant, EmptyTree, Function, Typed, ValDef, LabelDef} import definitions._ -// import analyzer.{Typer, ErrorUtils, formalTypes} /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // generate actual trees diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala index 1419d0cb93..eda30b88b7 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala @@ -6,33 +6,22 @@ package scala.tools.nsc.transform.patmat -import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -import transform._ -import typechecker._ -import symtab._ -import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} +import scala.tools.nsc.symtab.Flags.MUTABLE import scala.language.postfixOps -import scala.tools.nsc.transform.TypingTransformers -import scala.tools.nsc.transform.Transform import scala.collection.mutable import scala.reflect.internal.util.Statistics -import scala.reflect.internal.Types -import scala.reflect.internal.util.HashSet +import scala.reflect.internal.util.Position +import scala.reflect.internal.util.NoPosition trait Optimization { self: PatternMatching => import PatternMatchingStats._ - val global: Global - import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition, - Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest, - ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser, - Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef, - UniqueType, RefinedType, currentUnit, SingletonType, singleType, ModuleClassSymbol, - nestedMemberType, TypeMap, EmptyScope, Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw, newTermName} + import global.{Tree, Type, Symbol, NoSymbol, CaseDef, atPos, + ConstantType, Literal, Constant, gen, EmptyTree, + Typed, treeInfo, nme, Ident, + Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw} - import definitions._ - import analyzer.{Typer, ErrorUtils, formalTypes} + import global.definitions._ - import debugging.patmatDebug //// trait CommonSubconditionElimination extends TreeMakerApproximation { self: OptimizedCodegen => @@ -44,7 +33,7 @@ trait Optimization { self: PatternMatching => * we generalize sharing to implication, where b reuses a if a => b and priors(a) => priors(b) (the priors of a sub expression form the path through the decision tree) */ def doCSE(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): List[List[TreeMaker]] = { - patmatDebug("before CSE:") + debug.patmat("before CSE:") showTreeMakers(cases) val testss = approximateMatchConservative(prevBinder, cases) @@ -94,7 +83,7 @@ trait Optimization { self: PatternMatching => tested.clear() tests dropWhile storeDependencies } - patmatDebug("dependencies: "+ dependencies) + debug.patmat("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 @@ -128,8 +117,8 @@ trait Optimization { self: PatternMatching => case _ => } - patmatDebug("sharedPrefix: "+ sharedPrefix) - patmatDebug("suffix: "+ sharedPrefix) + debug.patmat("sharedPrefix: "+ sharedPrefix) + debug.patmat("suffix: "+ sharedPrefix) // if the shared prefix contains interesting conditions (!= True) // and the last of such interesting shared conditions reuses another treemaker's test // replace the whole sharedPrefix by a ReusingCondTreeMaker @@ -145,7 +134,7 @@ trait Optimization { self: PatternMatching => // replace original treemakers that are reused (as determined when computing collapsed), // by ReusedCondTreeMakers val reusedMakers = collapsed mapConserve (_ mapConserve reusedOrOrig) - patmatDebug("after CSE:") + debug.patmat("after CSE:") showTreeMakers(reusedMakers) reusedMakers } @@ -460,7 +449,7 @@ trait Optimization { self: PatternMatching => CaseDef(Alternative(switchableAlts), guard, body) } case _ => - // patmatDebug("can't emit switch for "+ makers) + // debug.patmat("can't emit switch for "+ makers) None //failure (can't translate pattern to a switch) } } diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala index d03e3741ef..984d82d955 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala @@ -6,32 +6,24 @@ package scala.tools.nsc.transform.patmat -import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -import transform._ -import typechecker._ -import symtab._ -import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} import scala.language.postfixOps -import scala.tools.nsc.transform.TypingTransformers -import scala.tools.nsc.transform.Transform import scala.collection.mutable import scala.reflect.internal.util.Statistics -import scala.reflect.internal.Types -import scala.reflect.internal.util.HashSet trait Translation { self: PatternMatching => import PatternMatchingStats._ - val global: Global - import global._ - - import definitions._ - import analyzer.{Typer, ErrorUtils, formalTypes} - - import debugging.patmatDebug - + import global.{phase, currentRun, Symbol, + Apply, Bind, CaseDef, ClassInfoType, Ident, Literal, Match, + Alternative, Constant, EmptyTree, Select, Star, This, Throw, Typed, UnApply, + Type, MethodType, WildcardType, PolyType, ErrorType, NoType, TypeRef, typeRef, + Name, NoSymbol, Position, Tree, atPos, glb, rootMirror, treeInfo, nme, Transformer, + elimAnonymousClass, asCompactDebugString, hasLength} + import global.definitions.{ThrowableClass, SeqClass, ScalaPackageClass, BooleanClass, UnitClass, RepeatedParamClass, + repeatedToSeq, isRepeatedParamType, getProductArgs} + import global.analyzer.{ErrorUtils, formalTypes} trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore => - import typer.{typed, context, silent, reallyExists} + import typer.context // Why is it so difficult to say "here's a name and a context, give me any // matching symbol in scope" ? I am sure this code is wrong, but attempts to @@ -133,7 +125,7 @@ trait Translation { self: PatternMatching => if (phase.id >= currentRun.uncurryPhase.id) devWarning(s"running translateMatch past uncurry (at $phase) on $selector match $cases") - patmatDebug("translating "+ cases.mkString("{", "\n", "}")) + debug.patmat("translating "+ cases.mkString("{", "\n", "}")) val start = if (Statistics.canEnable) Statistics.startTimer(patmatNanos) else null @@ -249,14 +241,14 @@ trait Translation { self: PatternMatching => if (!extractor.isTyped) ErrorUtils.issueNormalTypeError(patTree, "Could not typecheck extractor call: "+ extractor)(context) // if (extractor.resultInMonad == ErrorType) throw new TypeError(pos, "Unsupported extractor type: "+ extractor.tpe) - patmatDebug("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType)) + debug.patmat("translateExtractorPattern checking parameter type: "+ (patBinder, patBinder.info.widen, extractor.paramType, patBinder.info.widen <:< extractor.paramType)) // must use type `tp`, which is provided by extractor's result, not the type expected by binder, // as b.info may be based on a Typed type ascription, which has not been taken into account yet by the translation // (it will later result in a type test when `tp` is not a subtype of `b.info`) // TODO: can we simplify this, together with the Bound case? (extractor.subPatBinders, extractor.subPatTypes).zipped foreach { case (b, tp) => - patmatDebug("changing "+ b +" : "+ b.info +" -> "+ tp) + debug.patmat("changing "+ b +" : "+ b.info +" -> "+ tp) b setInfo tp } @@ -312,7 +304,7 @@ trait Translation { self: PatternMatching => case WildcardPattern() => noFurtherSubPats() case UnApply(unfun, args) => // TODO: check unargs == args - // patmatDebug("unfun: "+ (unfun.tpe, unfun.symbol.ownerChain, unfun.symbol.info, patBinder.info)) + // debug.patmat("unfun: "+ (unfun.tpe, unfun.symbol.ownerChain, unfun.symbol.info, patBinder.info)) translateExtractorPattern(ExtractorCall(unfun, args)) /** A constructor pattern is of the form c(p1, ..., pn) where n ≥ 0. @@ -379,7 +371,7 @@ trait Translation { self: PatternMatching => */ case Bind(n, p) => // this happens in certain ill-formed programs, there'll be an error later - patmatDebug("WARNING: Bind tree with unbound symbol "+ patTree) + debug.patmat("WARNING: Bind tree with unbound symbol "+ patTree) noFurtherSubPats() // there's no symbol -- something's wrong... don't fail here though (or should we?) // case Star(_) | ArrayValue => error("stone age pattern relics encountered!") @@ -536,8 +528,8 @@ trait Translation { self: PatternMatching => // private val orig = fun match {case tpt: TypeTree => tpt.original case _ => fun} // private val origExtractorTp = unapplyMember(orig.symbol.filter(sym => reallyExists(unapplyMember(sym.tpe))).tpe).tpe // private val extractorTp = if (wellKinded(fun.tpe)) fun.tpe else existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType) - // patmatDebug("ExtractorCallProd: "+ (fun.tpe, existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType))) - // patmatDebug("ExtractorCallProd: "+ (fun.tpe, args map (_.tpe))) + // debug.patmat("ExtractorCallProd: "+ (fun.tpe, existentialAbstraction(origExtractorTp.typeParams, origExtractorTp.resultType))) + // debug.patmat("ExtractorCallProd: "+ (fun.tpe, args map (_.tpe))) private def constructorTp = fun.tpe def isTyped = fun.isTyped @@ -678,58 +670,4 @@ trait Translation { self: PatternMatching => } } -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -// substitution -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - trait TypedSubstitution extends MatchMonadInterface { - object Substitution { - def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to)) - // requires sameLength(from, to) - def apply(from: List[Symbol], to: List[Tree]) = - if (from nonEmpty) new Substitution(from, to) else EmptySubstitution - } - - class Substitution(val from: List[Symbol], val to: List[Tree]) { - // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed, - // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees. - def apply(tree: Tree): Tree = { - // according to -Ystatistics 10% of translateMatch's time is spent in this method... - // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst - if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree - else (new Transformer { - private def typedIfOrigTyped(to: Tree, origTp: Type): Tree = - if (origTp == null || origTp == NoType) to - // important: only type when actually substing and when original tree was typed - // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors) - else typer.typed(to) - - override def transform(tree: Tree): Tree = { - def subst(from: List[Symbol], to: List[Tree]): Tree = - if (from.isEmpty) tree - else if (tree.symbol == from.head) typedIfOrigTyped(to.head.shallowDuplicate.setPos(tree.pos), tree.tpe) - else subst(from.tail, to.tail) - - tree match { - case Ident(_) => subst(from, to) - case _ => super.transform(tree) - } - } - }).transform(tree) - } - - - // the substitution that chains `other` before `this` substitution - // forall t: Tree. this(other(t)) == (this >> other)(t) - def >>(other: Substitution): Substitution = { - 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.map(_.name) zip to) mkString("Substitution(", ", ", ")") - } - - object EmptySubstitution extends Substitution(Nil, Nil) { - override def apply(tree: Tree): Tree = tree - override def >>(other: Substitution): Substitution = other - } - } } \ No newline at end of file diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala index b334a6b228..da9d6b3531 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala @@ -6,33 +6,25 @@ package scala.tools.nsc.transform.patmat -import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -import transform._ -import typechecker._ -import symtab._ -import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} +//import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} +//import transform._ +//import typechecker._ +//import symtab._ +import scala.tools.nsc.symtab.Flags.{SYNTHETIC, ARTIFACT} import scala.language.postfixOps -import scala.tools.nsc.transform.TypingTransformers -import scala.tools.nsc.transform.Transform import scala.collection.mutable import scala.reflect.internal.util.Statistics -import scala.reflect.internal.Types -import scala.reflect.internal.util.HashSet +import scala.reflect.internal.util.Position +import scala.reflect.internal.util.NoPosition trait TreeMaking { self: PatternMatching => import PatternMatchingStats._ - val global: Global - import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition, settings, - Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest, - ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser, - Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef, - UniqueType, RefinedType, currentUnit, SingletonType, singleType, ModuleClassSymbol, - nestedMemberType, TypeMap, EmptyScope, Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw, newTermName} + import global.{Tree, Type, Symbol, CaseDef, atPos, settings, + Select, Block, ThisType, SingleType, NoPrefix, NoType, needsOuterTest, + ConstantType, Literal, Constant, gen, This, EmptyTree, map2, NoSymbol, Traverser, + Function, Typed, treeInfo, TypeRef, DefTree} - import definitions._ - import analyzer.{Typer, ErrorUtils, formalTypes} - - import debugging.patmatDebug + import global.definitions.{SomeClass, AnyRefClass, UncheckedClass, BooleanClass} /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // the making of the trees @@ -62,7 +54,7 @@ trait TreeMaking { self: PatternMatching => private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = { if (currSub ne null) { - patmatDebug("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst)) + debug.patmat("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst)) Thread.dumpStack() } else currSub = outerSubst >> substitution @@ -172,7 +164,7 @@ trait TreeMaking { self: PatternMatching => if (!emitVars) in else { // binders in `subPatBindersStored` that are referenced by tree `in` - val usedBinders = new collection.mutable.HashSet[Symbol]() + val usedBinders = new mutable.HashSet[Symbol]() // all potentially stored subpat binders val potentiallyStoredBinders = stored.unzip._1.toSet // compute intersection of all symbols in the tree `in` and all potentially stored subpat binders @@ -391,7 +383,7 @@ trait TreeMaking { self: PatternMatching => **/ case class TypeTestTreeMaker(prevBinder: Symbol, testedBinder: Symbol, expectedTp: Type, nextBinderTp: Type)(override val pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker { import TypeTestTreeMaker._ - patmatDebug("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp)) + debug.patmat("TTTM"+(prevBinder, extractorArgTypeTest, testedBinder, expectedTp, nextBinderTp)) lazy val outerTestNeeded = ( !((expectedTp.prefix eq NoPrefix) || expectedTp.prefix.typeSymbol.isPackageClass) @@ -527,7 +519,7 @@ trait TreeMaking { self: PatternMatching => def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = fixerUpper(owner, scrut.pos){ def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree))) - patmatDebug("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}"))) + debug.patmat("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}"))) val (unchecked, requireSwitch) = if (settings.XnoPatmatAnalysis.value) (true, false) @@ -581,27 +573,27 @@ trait TreeMaking { self: PatternMatching => t match { case Function(_, _) if t.symbol == NoSymbol => t.symbol = currentOwner.newAnonymousFunctionValue(t.pos) - patmatDebug("new symbol for "+ (t, t.symbol.ownerChain)) + debug.patmat("new symbol for "+ (t, t.symbol.ownerChain)) case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) => - patmatDebug("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain)) + debug.patmat("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain)) t.symbol.owner = currentOwner case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2) - patmatDebug("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain)) + debug.patmat("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain)) if(d.symbol.moduleClass ne NoSymbol) d.symbol.moduleClass.owner = currentOwner d.symbol.owner = currentOwner // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) => - patmatDebug("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain)) + debug.patmat("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain)) case _ => } super.traverse(t) } // override def apply - // patmatDebug("before fixerupper: "+ xTree) + // debug.patmat("before fixerupper: "+ xTree) // currentRun.trackerFactory.snapshot() - // patmatDebug("after fixerupper") + // debug.patmat("after fixerupper") // currentRun.trackerFactory.snapshot() } } diff --git a/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala b/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala index 26078118fd..03c4e78771 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala @@ -6,18 +6,14 @@ package scala.tools.nsc.transform.patmat -import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -import transform._ -import typechecker._ -import symtab._ -import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} +import scala.tools.nsc.Global +import scala.tools.nsc.ast import scala.language.postfixOps import scala.tools.nsc.transform.TypingTransformers import scala.tools.nsc.transform.Transform -import scala.collection.mutable import scala.reflect.internal.util.Statistics import scala.reflect.internal.Types -import scala.reflect.internal.util.HashSet +import scala.reflect.internal.util.Position /** Translate pattern matching. * @@ -44,12 +40,9 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL with Translation with TreeMaking with CodeGen - with Logic + with ScalaLogic with Analysis with Optimization { - - import PatternMatchingStats._ - val global: Global import global._ val phaseName: String = "patmat" @@ -86,20 +79,20 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL class OptimizingMatchTranslator(val typer: analyzer.Typer) extends MatchTranslation with TreeMakers with MatchOptimizations } -trait Debugging { +trait HasGlobal { val global: Global - import global.settings +} - // TODO: the inliner fails to inline the closures to patmatDebug - object debugging { - val printPatmat = settings.Ypatmatdebug.value - @inline final def patmatDebug(s: => String) = if (printPatmat) println(s) +trait Debugging extends HasGlobal { + // TODO: the inliner fails to inline the closures to debug.patmat unless the method is nested in an object + object debug { + val printPatmat = global.settings.Ypatmatdebug.value + @inline final def patmat(s: => String) = if (printPatmat) println(s) } } -trait Interface { self: ast.TreeDSL => - val global: Global - import global.{newTermName, Position, Type, analyzer, ErrorType, Symbol, Tree} +trait Interface { self: ast.TreeDSL with HasGlobal => + import global.{newTermName, analyzer, Type, ErrorType, Symbol, Tree} import analyzer.Typer // 2.10/2.11 compatibility @@ -183,6 +176,64 @@ trait Interface { self: ast.TreeDSL => protected def matchMonadSym: Symbol } + + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// substitution +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + trait TypedSubstitution extends MatchMonadInterface { + object Substitution { + def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to)) + // requires sameLength(from, to) + def apply(from: List[Symbol], to: List[Tree]) = + if (from nonEmpty) new Substitution(from, to) else EmptySubstitution + } + + class Substitution(val from: List[Symbol], val to: List[Tree]) { + import global.{Transformer, Ident, NoType} + + // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed, + // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees. + def apply(tree: Tree): Tree = { + // according to -Ystatistics 10% of translateMatch's time is spent in this method... + // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst + if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree + else (new Transformer { + private def typedIfOrigTyped(to: Tree, origTp: Type): Tree = + if (origTp == null || origTp == NoType) to + // important: only type when actually substing and when original tree was typed + // (don't need to use origTp as the expected type, though, and can't always do this anyway due to unknown type params stemming from polymorphic extractors) + else typer.typed(to) + + override def transform(tree: Tree): Tree = { + def subst(from: List[Symbol], to: List[Tree]): Tree = + if (from.isEmpty) tree + else if (tree.symbol == from.head) typedIfOrigTyped(to.head.shallowDuplicate.setPos(tree.pos), tree.tpe) + else subst(from.tail, to.tail) + + tree match { + case Ident(_) => subst(from, to) + case _ => super.transform(tree) + } + } + }).transform(tree) + } + + + // the substitution that chains `other` before `this` substitution + // forall t: Tree. this(other(t)) == (this >> other)(t) + def >>(other: Substitution): Substitution = { + 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.map(_.name) zip to) mkString("Substitution(", ", ", ")") + } + + object EmptySubstitution extends Substitution(Nil, Nil) { + override def apply(tree: Tree): Tree = tree + override def >>(other: Substitution): Substitution = other + } + } } object PatternMatchingStats { -- cgit v1.2.3 From d2a36ab9061ece70a559e35139729c5b9118b5f0 Mon Sep 17 00:00:00 2001 From: Som Snytt Date: Sat, 16 Feb 2013 08:33:26 -0800 Subject: Shadowed Implict typo (fixes no issue) --- src/compiler/scala/tools/nsc/doc/html/page/Template.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/compiler/scala/tools/nsc/doc/html/page/Template.scala b/src/compiler/scala/tools/nsc/doc/html/page/Template.scala index ea07ff29c4..5cbb14b486 100644 --- a/src/compiler/scala/tools/nsc/doc/html/page/Template.scala +++ b/src/compiler/scala/tools/nsc/doc/html/page/Template.scala @@ -215,7 +215,7 @@ class Template(universe: doc.Universe, generator: DiagramGenerator, tpl: DocTemp { if (shadowedImplicitMembers.isEmpty) NodeSeq.Empty else
-

Shadowed Implict Value Members

+

Shadowed Implicit Value Members

    { shadowedImplicitMembers map (memberToHtml(_, tpl)) }
} -- cgit v1.2.3 From b20e28832d0fc509cbb2fcfe043eda66b7fb9e6c Mon Sep 17 00:00:00 2001 From: Heather Miller Date: Tue, 19 Feb 2013 22:56:16 +0100 Subject: Fixed error in reflection API docs about linearization order on method baseClasses --- src/reflect/scala/reflect/api/Symbols.scala | 2 +- src/reflect/scala/reflect/api/Types.scala | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/src/reflect/scala/reflect/api/Symbols.scala b/src/reflect/scala/reflect/api/Symbols.scala index b53c700701..c8e03f1d91 100644 --- a/src/reflect/scala/reflect/api/Symbols.scala +++ b/src/reflect/scala/reflect/api/Symbols.scala @@ -946,7 +946,7 @@ trait Symbols { self: Universe => def knownDirectSubclasses: Set[Symbol] /** The list of all base classes of this type (including its own typeSymbol) - * in reverse linearization order, starting with the class itself and ending + * in linearization order, starting with the class itself and ending * in class Any. * * @group Class diff --git a/src/reflect/scala/reflect/api/Types.scala b/src/reflect/scala/reflect/api/Types.scala index 143438b8f5..72163ef0e9 100644 --- a/src/reflect/scala/reflect/api/Types.scala +++ b/src/reflect/scala/reflect/api/Types.scala @@ -149,7 +149,7 @@ trait Types { self: Universe => def =:= (that: Type): Boolean /** The list of all base classes of this type (including its own typeSymbol) - * in reverse linearization order, starting with the class itself and ending + * in linearization order, starting with the class itself and ending * in class Any. */ def baseClasses: List[Symbol] -- cgit v1.2.3 From 18a2ba2f27004e74952ea88c1ea2eb8086c44ea4 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Thu, 21 Feb 2013 13:42:23 -0800 Subject: please ant with filenames, add comments --- .../tools/nsc/transform/patmat/MatchAnalysis.scala | 2 +- .../tools/nsc/transform/patmat/MatchCodeGen.scala | 7 +- .../nsc/transform/patmat/MatchOptimization.scala | 8 +- .../nsc/transform/patmat/MatchTranslation.scala | 7 +- .../nsc/transform/patmat/MatchTreeMakers.scala | 600 -------------------- .../nsc/transform/patmat/MatchTreeMaking.scala | 601 +++++++++++++++++++++ .../nsc/transform/patmat/PatternMatching.scala | 23 +- 7 files changed, 632 insertions(+), 616 deletions(-) delete mode 100644 src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala create mode 100644 src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMaking.scala diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala index 39157e3843..ed990105fd 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchAnalysis.scala @@ -125,7 +125,7 @@ trait TreeAndTypeAnalysis extends Debugging { } } -trait Analysis extends TreeAndTypeAnalysis { self: PatternMatching => +trait MatchAnalysis extends TreeAndTypeAnalysis { self: PatternMatching => import PatternMatchingStats._ import global.{Tree, Type, Symbol, CaseDef, atPos, Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest, diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala index 4c024cf71c..ce19d9cba8 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala @@ -12,7 +12,12 @@ import scala.reflect.internal.util.Statistics import scala.reflect.internal.util.Position import scala.reflect.internal.util.NoPosition -trait CodeGen { self: PatternMatching => +/** Factory methods used by TreeMakers to make the actual trees. + * + * We have two modes in which to emit trees: optimized (the default) + * and pure (aka "virtualized": match is parametric in its monad). + */ +trait MatchCodeGen { self: PatternMatching => import PatternMatchingStats._ import global.{nme, treeInfo, definitions, gen, Tree, Type, Symbol, NoSymbol, appliedType, NoType, MethodType, newTermName, Name, diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala index eda30b88b7..c14b4ebc3b 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchOptimization.scala @@ -13,7 +13,13 @@ import scala.reflect.internal.util.Statistics import scala.reflect.internal.util.Position import scala.reflect.internal.util.NoPosition -trait Optimization { self: PatternMatching => +/** Optimize and analyze matches based on their TreeMaker-representation. + * + * The patmat translation doesn't rely on this, so it could be disabled in principle. + * + * TODO: split out match analysis + */ +trait MatchOptimization { self: PatternMatching => import PatternMatchingStats._ import global.{Tree, Type, Symbol, NoSymbol, CaseDef, atPos, ConstantType, Literal, Constant, gen, EmptyTree, diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala index 984d82d955..5d11fb6459 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTranslation.scala @@ -10,7 +10,9 @@ import scala.language.postfixOps import scala.collection.mutable import scala.reflect.internal.util.Statistics -trait Translation { self: PatternMatching => +/** Translate typed Trees that represent pattern matches into the patternmatching IR, defined by TreeMakers. + */ +trait MatchTranslation { self: PatternMatching => import PatternMatchingStats._ import global.{phase, currentRun, Symbol, Apply, Bind, CaseDef, ClassInfoType, Ident, Literal, Match, @@ -22,7 +24,7 @@ trait Translation { self: PatternMatching => repeatedToSeq, isRepeatedParamType, getProductArgs} import global.analyzer.{ErrorUtils, formalTypes} - trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore => + trait MatchTranslator extends MatchMonadInterface { self: TreeMakers with CodegenCore => import typer.context // Why is it so difficult to say "here's a name and a context, give me any @@ -669,5 +671,4 @@ trait Translation { self: PatternMatching => } } } - } \ No newline at end of file diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala deleted file mode 100644 index da9d6b3531..0000000000 --- a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMakers.scala +++ /dev/null @@ -1,600 +0,0 @@ -/* NSC -- new Scala compiler - * - * Copyright 2011-2013 LAMP/EPFL - * @author Adriaan Moors - */ - -package scala.tools.nsc.transform.patmat - -//import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} -//import transform._ -//import typechecker._ -//import symtab._ -import scala.tools.nsc.symtab.Flags.{SYNTHETIC, ARTIFACT} -import scala.language.postfixOps -import scala.collection.mutable -import scala.reflect.internal.util.Statistics -import scala.reflect.internal.util.Position -import scala.reflect.internal.util.NoPosition - -trait TreeMaking { self: PatternMatching => - import PatternMatchingStats._ - import global.{Tree, Type, Symbol, CaseDef, atPos, settings, - Select, Block, ThisType, SingleType, NoPrefix, NoType, needsOuterTest, - ConstantType, Literal, Constant, gen, This, EmptyTree, map2, NoSymbol, Traverser, - Function, Typed, treeInfo, TypeRef, DefTree} - - import global.definitions.{SomeClass, AnyRefClass, UncheckedClass, BooleanClass} - -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// -// the making of the trees -/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// - trait TreeMakers extends TypedSubstitution { self: CodegenCore => - 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], unchecked: Boolean): Option[Tree] = - None - - // for catch (no need to customize match failure) - def emitTypeSwitch(bindersAndCases: List[(Symbol, List[TreeMaker])], pt: Type): Option[List[CaseDef]] = - None - - abstract class TreeMaker { - def pos: Position - - /** captures the scope and the value of the bindings in patterns - * important *when* the substitution happens (can't accumulate and do at once after the full matcher has been constructed) - */ - def substitution: Substitution = - if (currSub eq null) localSubstitution - else currSub - - protected def localSubstitution: Substitution - - private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = { - if (currSub ne null) { - debug.patmat("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst)) - Thread.dumpStack() - } - else currSub = outerSubst >> substitution - } - private[this] var currSub: Substitution = null - - /** The substitution that specifies the trees that compute the values of the subpattern binders. - * - * Should not be used to perform actual substitution! - * Only used to reason symbolically about the values the subpattern binders are bound to. - * See TreeMakerToCond#updateSubstitution. - * - * Overridden in PreserveSubPatBinders to pretend it replaces the subpattern binders by subpattern refs - * (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.) - * - * TODO: clean this up, would be nicer to have some higher-level way to compute - * the binders bound by this tree maker and the symbolic values that correspond to them - */ - def subPatternsAsSubstitution: Substitution = substitution - - // build Tree that chains `next` after the current extractor - def chainBefore(next: Tree)(casegen: Casegen): Tree - } - - trait NoNewBinders extends TreeMaker { - protected val localSubstitution: Substitution = EmptySubstitution - } - - case class TrivialTreeMaker(tree: Tree) extends TreeMaker with NoNewBinders { - def pos = tree.pos - - def chainBefore(next: Tree)(casegen: Casegen): Tree = tree - } - - case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker with NoNewBinders { - def pos = body.pos - - 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 pos = NoPosition - - 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 { - val nextBinder: Symbol - def pos = nextBinder.pos - } - - abstract class CondTreeMaker extends FunTreeMaker { - val prevBinder: Symbol - val nextBinderTp: Type - val cond: Tree - val res: Tree - - lazy val nextBinder = freshSym(pos, nextBinderTp) - lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder))) - - def chainBefore(next: Tree)(casegen: Casegen): Tree = - atPos(pos)(casegen.flatMapCond(cond, res, nextBinder, substitution(next))) - } - - // unless we're optimizing, emit local variable bindings for all subpatterns of extractor/case class patterns - protected val debugInfoEmitVars = !settings.optimise.value - - trait PreserveSubPatBinders extends TreeMaker { - val subPatBinders: List[Symbol] - val subPatRefs: List[Tree] - val ignoredSubPatBinders: Set[Symbol] - - // unless `debugInfoEmitVars`, this set should contain the bare minimum for correctness - // mutable case class fields need to be stored regardless (SI-5158, SI-6070) -- see override in ProductExtractorTreeMaker - // sub patterns bound to wildcard (_) are never stored as they can't be referenced - // dirty debuggers will have to get dirty to see the wildcards - lazy val storedBinders: Set[Symbol] = - (if (debugInfoEmitVars) subPatBinders.toSet else Set.empty) ++ extraStoredBinders -- ignoredSubPatBinders - - // e.g., mutable fields of a case class in ProductExtractorTreeMaker - def extraStoredBinders: Set[Symbol] - - def emitVars = storedBinders.nonEmpty - - private lazy val (stored, substed) = (subPatBinders, subPatRefs).zipped.partition{ case (sym, _) => storedBinders(sym) } - - protected lazy val localSubstitution: Substitution = if (!emitVars) Substitution(subPatBinders, subPatRefs) - else { - val (subPatBindersSubstituted, subPatRefsSubstituted) = substed.unzip - Substitution(subPatBindersSubstituted.toList, subPatRefsSubstituted.toList) - } - - /** The substitution that specifies the trees that compute the values of the subpattern binders. - * - * We pretend to replace the subpattern binders by subpattern refs - * (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.) - */ - override def subPatternsAsSubstitution = - Substitution(subPatBinders, subPatRefs) >> super.subPatternsAsSubstitution - - import CODE._ - def bindSubPats(in: Tree): Tree = - if (!emitVars) in - else { - // binders in `subPatBindersStored` that are referenced by tree `in` - val usedBinders = new mutable.HashSet[Symbol]() - // all potentially stored subpat binders - val potentiallyStoredBinders = stored.unzip._1.toSet - // compute intersection of all symbols in the tree `in` and all potentially stored subpat binders - in.foreach(t => if (potentiallyStoredBinders(t.symbol)) usedBinders += t.symbol) - - if (usedBinders.isEmpty) in - else { - // only store binders actually used - val (subPatBindersStored, subPatRefsStored) = stored.filter{case (b, _) => usedBinders(b)}.unzip - Block(map2(subPatBindersStored.toList, subPatRefsStored.toList)(VAL(_) === _), in) - } - } - } - - /** - * Make a TreeMaker that will result in an extractor call specified by `extractor` - * the next TreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing - * a function with binder `nextBinder` over our extractor's result - * the function's body is determined by the next TreeMaker - * (furthermore, the interpretation of `flatMap` depends on the codegen instance we're using). - * - * The values for the subpatterns, as computed by the extractor call in `extractor`, - * are stored in local variables that re-use the symbols in `subPatBinders`. - * This makes extractor patterns more debuggable (SI-5739). - */ - case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol)( - val subPatBinders: List[Symbol], - val subPatRefs: List[Tree], - extractorReturnsBoolean: Boolean, - val checkedLength: Option[Int], - val prevBinder: Symbol, - val ignoredSubPatBinders: Set[Symbol] - ) extends FunTreeMaker with PreserveSubPatBinders { - - def extraStoredBinders: Set[Symbol] = Set() - - def chainBefore(next: Tree)(casegen: Casegen): Tree = { - val condAndNext = extraCond match { - case Some(cond) => - casegen.ifThenElseZero(substitution(cond), bindSubPats(substitution(next))) - case _ => - bindSubPats(substitution(next)) - } - atPos(extractor.pos)( - if (extractorReturnsBoolean) casegen.flatMapCond(extractor, CODE.UNIT, nextBinder, condAndNext) - else casegen.flatMap(extractor, nextBinder, condAndNext) - ) - } - - override def toString = "X"+(extractor, nextBinder.name) - } - - /** - * An optimized version of ExtractorTreeMaker for Products. - * For now, this is hard-coded to case classes, and we simply extract the case class fields. - * - * The values for the subpatterns, as specified by the case class fields at the time of extraction, - * are stored in local variables that re-use the symbols in `subPatBinders`. - * This makes extractor patterns more debuggable (SI-5739) as well as - * avoiding mutation after the pattern has been matched (SI-5158, SI-6070) - * - * TODO: make this user-definable as follows - * When a companion object defines a method `def unapply_1(x: T): U_1`, but no `def unapply` or `def unapplySeq`, - * the extractor is considered to match any non-null value of type T - * the pattern is expected to have as many sub-patterns as there are `def unapply_I(x: T): U_I` methods, - * and the type of the I'th sub-pattern is `U_I`. - * The same exception for Seq patterns applies: if the last extractor is of type `Seq[U_N]`, - * the pattern must have at least N arguments (exactly N if the last argument is annotated with `: _*`). - * The arguments starting at N (and beyond) are taken from the sequence returned by apply_N, - * and it is checked that that sequence has enough elements to provide values for all expected sub-patterns. - * - * For a case class C, the implementation is assumed to be `def unapply_I(x: C) = x._I`, - * and the extractor call is inlined under that assumption. - */ - case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree])( - val subPatBinders: List[Symbol], - val subPatRefs: List[Tree], - val mutableBinders: List[Symbol], - binderKnownNonNull: Boolean, - val ignoredSubPatBinders: Set[Symbol] - ) extends FunTreeMaker with PreserveSubPatBinders { - - import CODE._ - val nextBinder = prevBinder // just passing through - - // mutable binders must be stored to avoid unsoundness or seeing mutation of fields after matching (SI-5158, SI-6070) - def extraStoredBinders: Set[Symbol] = mutableBinders.toSet - - def chainBefore(next: Tree)(casegen: Casegen): Tree = { - val nullCheck = REF(prevBinder) OBJ_NE NULL - val cond = - if (binderKnownNonNull) extraCond - else (extraCond map (nullCheck AND _) - orElse Some(nullCheck)) - - cond match { - case Some(cond) => - casegen.ifThenElseZero(cond, bindSubPats(substitution(next))) - case _ => - bindSubPats(substitution(next)) - } - } - - override def toString = "P"+(prevBinder.name, extraCond getOrElse "", localSubstitution) - } - - object IrrefutableExtractorTreeMaker { - // will an extractor with unapply method of methodtype `tp` always succeed? - // note: this assumes the other side-conditions implied by the extractor are met - // (argument of the right type, length check succeeds for unapplySeq,...) - def irrefutableExtractorType(tp: Type): Boolean = tp.resultType.dealias match { - case TypeRef(_, SomeClass, _) => true - // probably not useful since this type won't be inferred nor can it be written down (yet) - case ConstantType(Constant(true)) => true - case _ => false - } - - def unapply(xtm: ExtractorTreeMaker): Option[(Tree, Symbol)] = xtm match { - case ExtractorTreeMaker(extractor, None, nextBinder) if irrefutableExtractorType(extractor.tpe) => - Some((extractor, nextBinder)) - case _ => - None - } - } - - 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 - def tru: Result - } - - object treeCondStrategy extends TypeTestCondStrategy { import CODE._ - type Result = Tree - - def and(a: Result, b: Result): Result = a AND b - def tru = mkTRUE - 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 - - def outerTest(testedBinder: Symbol, expectedTp: Type): Tree = { - val expectedOuter = expectedTp.prefix match { - case ThisType(clazz) => THIS(clazz) - case pre if pre != NoType => REF(pre.prefix, pre.termSymbol) - case _ => mkTRUE // fallback for SI-6183 - } - - // 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, newFlags = SYNTHETIC | ARTIFACT) setInfo expectedTp.prefix - - (Select(codegen._asInstanceOf(testedBinder, expectedTp), outer)) OBJ_EQ expectedOuter - } - } - - object pureTypeTestChecker extends TypeTestCondStrategy { - type Result = Boolean - - def typeTest(testedBinder: Symbol, expectedTp: Type): Result = true - - 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 - def tru = true - } - - def nonNullImpliedByTestChecker(binder: Symbol) = new TypeTestCondStrategy { - type Result = Boolean - - def typeTest(testedBinder: Symbol, expectedTp: Type): Result = testedBinder eq binder - def outerTest(testedBinder: Symbol, expectedTp: Type): Result = false - def nonNullTest(testedBinder: Symbol): Result = testedBinder eq binder - def equalsTest(pat: Tree, testedBinder: Symbol): Result = false // could in principle analyse pat and see if it's statically known to be non-null - def eqTest(pat: Tree, testedBinder: Symbol): Result = false // could in principle analyse pat and see if it's statically known to be non-null - def and(a: Result, b: Result): Result = a || b - def tru = false - } - } - - /** 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)(override val pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker { - import TypeTestTreeMaker._ - debug.patmat("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) - - // propagate expected type - def expTp(t: Tree): t.type = t setType 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(gen.mkAttributedQualifier(expectedTp), 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(Constant(null)) if testedBinder.info.widen <:< AnyRefClass.tpe - => eqTest(expTp(CODE.NULL), testedBinder) - case ConstantType(const) => equalsTest(expTp(Literal(const)), testedBinder) - case ThisType(sym) => eqTest(expTp(This(sym)), 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 testedBinder.info.widen <:< expectedTp => - // if the expected type is a primitive value type, it cannot be null and it cannot have an outer pointer - // since the types conform, no further checking is required - if (expectedTp.typeSymbol.isPrimitiveValueClass) tru - // have to test outer and non-null only when it's a reference type - else if (expectedTp <:< AnyRefClass.tpe) { - // 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) - } else default - - case _ => default - } - } - - val cond = renderCondition(treeCondStrategy) - val res = codegen._asInstanceOf(testedBinder, nextBinderTp) - - // is this purely a type test, e.g. no outer check, no equality tests (used in switch emission) - def isPureTypeTest = renderCondition(pureTypeTestChecker) - - def impliesBinderNonNull(binder: Symbol) = renderCondition(nonNullImpliedByTestChecker(binder)) - - 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) - case class EqualityTestTreeMaker(prevBinder: Symbol, patTree: Tree, override val pos: Position) extends CondTreeMaker { - val nextBinderTp = prevBinder.info.widen - - // NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null) - // 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.name, patTree) - } - - case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker with NoNewBinders { - // don't substitute prevBinder to nextBinder, a set of alternatives does not need to introduce a new binder, simply reuse the previous one - - override private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = { - super.incorporateOuterSubstitution(outerSubst) - altss = altss map (alts => propagateSubstitution(alts, substitution)) - } - - def chainBefore(next: Tree)(codegenAlt: Casegen): Tree = { import CODE._ - atPos(pos){ - // one alternative may still generate multiple trees (e.g., an extractor call + equality test) - // (for now,) alternatives may not bind variables (except wildcards), so we don't care about the final substitution built internally by makeTreeMakers - val combinedAlts = altss map (altTreeMakers => - ((casegen: Casegen) => combineExtractors(altTreeMakers :+ TrivialTreeMaker(casegen.one(mkTRUE)))(casegen)) - ) - - val findAltMatcher = codegenAlt.matcher(EmptyTree, NoSymbol, BooleanClass.tpe)(combinedAlts, Some(x => mkFALSE)) - codegenAlt.ifThenElseZero(findAltMatcher, substitution(next)) - } - } - } - - case class GuardTreeMaker(guardTree: Tree) extends TreeMaker with NoNewBinders { - val pos = guardTree.pos - - def chainBefore(next: Tree)(casegen: Casegen): Tree = casegen.flatMapGuard(substitution(guardTree), next) - override def toString = "G("+ guardTree +")" - } - - // combineExtractors changes the current substitution's of the tree makers in `treeMakers` - // requires propagateSubstitution(treeMakers) has been called - def combineExtractors(treeMakers: List[TreeMaker])(casegen: Casegen): Tree = - treeMakers.foldRight(EmptyTree: Tree)((a, b) => a.chainBefore(b)(casegen)) - - - def removeSubstOnly(makers: List[TreeMaker]) = makers filterNot (_.isInstanceOf[SubstOnlyTreeMaker]) - - // a foldLeft to accumulate the localSubstitution left-to-right - // it drops SubstOnly tree makers, since their only goal in life is to propagate substitutions to the next tree maker, which is fullfilled by propagateSubstitution - def propagateSubstitution(treeMakers: List[TreeMaker], initial: Substitution): List[TreeMaker] = { - var accumSubst: Substitution = initial - treeMakers foreach { maker => - maker incorporateOuterSubstitution accumSubst - accumSubst = maker.substitution - } - removeSubstOnly(treeMakers) - } - - // calls propagateSubstitution on the treemakers - def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = { - // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them - val casesNoSubstOnly = casesRaw map (propagateSubstitution(_, EmptySubstitution)) - combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, matchFailGenOverride) - } - - // pt is the fully defined type of the cases (either pt or the lub of the types of the cases) - def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = - fixerUpper(owner, scrut.pos){ - def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree))) - debug.patmat("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}"))) - - val (unchecked, requireSwitch) = - if (settings.XnoPatmatAnalysis.value) (true, false) - else scrut match { - case Typed(_, tpt) => - (tpt.tpe hasAnnotation UncheckedClass, - // matches with two or fewer cases need not apply for switchiness (if-then-else will do) - treeInfo.isSwitchAnnotation(tpt.tpe) && casesNoSubstOnly.lengthCompare(2) > 0) - case _ => - (false, false) - } - - emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt, matchFailGenOverride, unchecked).getOrElse{ - if (requireSwitch) typer.context.unit.warning(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 - // exhaustivity and reachability must be checked before optimization as well - // TODO: improve notion of trivial/irrefutable -- a trivial type test before the body still makes for a default case - // ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op) - // irrefutability checking should use the approximation framework also used for CSE, unreachability and exhaustivity checking - val synthCatchAll = - if (casesNoSubstOnly.nonEmpty && { - val nonTrivLast = casesNoSubstOnly.last - nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker] - }) None - else matchFailGen - - val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt, unchecked) - - val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, synthCatchAll) - - if (toHoist isEmpty) matchRes else Block(toHoist, matchRes) - } else { - codegen.matcher(scrut, scrutSym, pt)(Nil, matchFailGen) - } - } - } - - // TODO: do this during tree construction, but that will require tracking the current owner in treemakers - // TODO: assign more fine-grained positions - // fixes symbol nesting, assigns positions - protected def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser { - currentOwner = origOwner - - override def traverse(t: Tree) { - if (t != EmptyTree && t.pos == NoPosition) { - t.setPos(pos) - } - t match { - case Function(_, _) if t.symbol == NoSymbol => - t.symbol = currentOwner.newAnonymousFunctionValue(t.pos) - debug.patmat("new symbol for "+ (t, t.symbol.ownerChain)) - case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) => - debug.patmat("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain)) - t.symbol.owner = currentOwner - case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2) - debug.patmat("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain)) - if(d.symbol.moduleClass ne NoSymbol) - d.symbol.moduleClass.owner = currentOwner - - d.symbol.owner = currentOwner - // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) => - debug.patmat("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain)) - case _ => - } - super.traverse(t) - } - - // override def apply - // debug.patmat("before fixerupper: "+ xTree) - // currentRun.trackerFactory.snapshot() - // debug.patmat("after fixerupper") - // currentRun.trackerFactory.snapshot() - } - } -} \ No newline at end of file diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMaking.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMaking.scala new file mode 100644 index 0000000000..c9285f9229 --- /dev/null +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchTreeMaking.scala @@ -0,0 +1,601 @@ +/* NSC -- new Scala compiler + * + * Copyright 2011-2013 LAMP/EPFL + * @author Adriaan Moors + */ + +package scala.tools.nsc.transform.patmat + +import scala.tools.nsc.symtab.Flags.{SYNTHETIC, ARTIFACT} +import scala.language.postfixOps +import scala.collection.mutable +import scala.reflect.internal.util.Statistics +import scala.reflect.internal.util.Position +import scala.reflect.internal.util.NoPosition + +/** Translate our IR (TreeMakers) into actual Scala Trees using the factory methods in MatchCodeGen. + * + * The IR is mostly concerned with sequencing, substitution, and rendering all necessary conditions, + * mostly agnostic to whether we're in optimized/pure (virtualized) mode. + */ +trait MatchTreeMaking { self: PatternMatching => + import PatternMatchingStats._ + import global.{Tree, Type, Symbol, CaseDef, atPos, settings, + Select, Block, ThisType, SingleType, NoPrefix, NoType, needsOuterTest, + ConstantType, Literal, Constant, gen, This, EmptyTree, map2, NoSymbol, Traverser, + Function, Typed, treeInfo, TypeRef, DefTree} + + import global.definitions.{SomeClass, AnyRefClass, UncheckedClass, BooleanClass} + +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// the making of the trees +/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + trait TreeMakers extends TypedSubstitution { self: CodegenCore => + 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], unchecked: Boolean): Option[Tree] = + None + + // for catch (no need to customize match failure) + def emitTypeSwitch(bindersAndCases: List[(Symbol, List[TreeMaker])], pt: Type): Option[List[CaseDef]] = + None + + abstract class TreeMaker { + def pos: Position + + /** captures the scope and the value of the bindings in patterns + * important *when* the substitution happens (can't accumulate and do at once after the full matcher has been constructed) + */ + def substitution: Substitution = + if (currSub eq null) localSubstitution + else currSub + + protected def localSubstitution: Substitution + + private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = { + if (currSub ne null) { + debug.patmat("BUG: incorporateOuterSubstitution called more than once for "+ (this, currSub, outerSubst)) + Thread.dumpStack() + } + else currSub = outerSubst >> substitution + } + private[this] var currSub: Substitution = null + + /** The substitution that specifies the trees that compute the values of the subpattern binders. + * + * Should not be used to perform actual substitution! + * Only used to reason symbolically about the values the subpattern binders are bound to. + * See TreeMakerToCond#updateSubstitution. + * + * Overridden in PreserveSubPatBinders to pretend it replaces the subpattern binders by subpattern refs + * (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.) + * + * TODO: clean this up, would be nicer to have some higher-level way to compute + * the binders bound by this tree maker and the symbolic values that correspond to them + */ + def subPatternsAsSubstitution: Substitution = substitution + + // build Tree that chains `next` after the current extractor + def chainBefore(next: Tree)(casegen: Casegen): Tree + } + + trait NoNewBinders extends TreeMaker { + protected val localSubstitution: Substitution = EmptySubstitution + } + + case class TrivialTreeMaker(tree: Tree) extends TreeMaker with NoNewBinders { + def pos = tree.pos + + def chainBefore(next: Tree)(casegen: Casegen): Tree = tree + } + + case class BodyTreeMaker(body: Tree, matchPt: Type) extends TreeMaker with NoNewBinders { + def pos = body.pos + + 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 pos = NoPosition + + 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 { + val nextBinder: Symbol + def pos = nextBinder.pos + } + + abstract class CondTreeMaker extends FunTreeMaker { + val prevBinder: Symbol + val nextBinderTp: Type + val cond: Tree + val res: Tree + + lazy val nextBinder = freshSym(pos, nextBinderTp) + lazy val localSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder))) + + def chainBefore(next: Tree)(casegen: Casegen): Tree = + atPos(pos)(casegen.flatMapCond(cond, res, nextBinder, substitution(next))) + } + + // unless we're optimizing, emit local variable bindings for all subpatterns of extractor/case class patterns + protected val debugInfoEmitVars = !settings.optimise.value + + trait PreserveSubPatBinders extends TreeMaker { + val subPatBinders: List[Symbol] + val subPatRefs: List[Tree] + val ignoredSubPatBinders: Set[Symbol] + + // unless `debugInfoEmitVars`, this set should contain the bare minimum for correctness + // mutable case class fields need to be stored regardless (SI-5158, SI-6070) -- see override in ProductExtractorTreeMaker + // sub patterns bound to wildcard (_) are never stored as they can't be referenced + // dirty debuggers will have to get dirty to see the wildcards + lazy val storedBinders: Set[Symbol] = + (if (debugInfoEmitVars) subPatBinders.toSet else Set.empty) ++ extraStoredBinders -- ignoredSubPatBinders + + // e.g., mutable fields of a case class in ProductExtractorTreeMaker + def extraStoredBinders: Set[Symbol] + + def emitVars = storedBinders.nonEmpty + + private lazy val (stored, substed) = (subPatBinders, subPatRefs).zipped.partition{ case (sym, _) => storedBinders(sym) } + + protected lazy val localSubstitution: Substitution = if (!emitVars) Substitution(subPatBinders, subPatRefs) + else { + val (subPatBindersSubstituted, subPatRefsSubstituted) = substed.unzip + Substitution(subPatBindersSubstituted.toList, subPatRefsSubstituted.toList) + } + + /** The substitution that specifies the trees that compute the values of the subpattern binders. + * + * We pretend to replace the subpattern binders by subpattern refs + * (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.) + */ + override def subPatternsAsSubstitution = + Substitution(subPatBinders, subPatRefs) >> super.subPatternsAsSubstitution + + import CODE._ + def bindSubPats(in: Tree): Tree = + if (!emitVars) in + else { + // binders in `subPatBindersStored` that are referenced by tree `in` + val usedBinders = new mutable.HashSet[Symbol]() + // all potentially stored subpat binders + val potentiallyStoredBinders = stored.unzip._1.toSet + // compute intersection of all symbols in the tree `in` and all potentially stored subpat binders + in.foreach(t => if (potentiallyStoredBinders(t.symbol)) usedBinders += t.symbol) + + if (usedBinders.isEmpty) in + else { + // only store binders actually used + val (subPatBindersStored, subPatRefsStored) = stored.filter{case (b, _) => usedBinders(b)}.unzip + Block(map2(subPatBindersStored.toList, subPatRefsStored.toList)(VAL(_) === _), in) + } + } + } + + /** + * Make a TreeMaker that will result in an extractor call specified by `extractor` + * the next TreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing + * a function with binder `nextBinder` over our extractor's result + * the function's body is determined by the next TreeMaker + * (furthermore, the interpretation of `flatMap` depends on the codegen instance we're using). + * + * The values for the subpatterns, as computed by the extractor call in `extractor`, + * are stored in local variables that re-use the symbols in `subPatBinders`. + * This makes extractor patterns more debuggable (SI-5739). + */ + case class ExtractorTreeMaker(extractor: Tree, extraCond: Option[Tree], nextBinder: Symbol)( + val subPatBinders: List[Symbol], + val subPatRefs: List[Tree], + extractorReturnsBoolean: Boolean, + val checkedLength: Option[Int], + val prevBinder: Symbol, + val ignoredSubPatBinders: Set[Symbol] + ) extends FunTreeMaker with PreserveSubPatBinders { + + def extraStoredBinders: Set[Symbol] = Set() + + def chainBefore(next: Tree)(casegen: Casegen): Tree = { + val condAndNext = extraCond match { + case Some(cond) => + casegen.ifThenElseZero(substitution(cond), bindSubPats(substitution(next))) + case _ => + bindSubPats(substitution(next)) + } + atPos(extractor.pos)( + if (extractorReturnsBoolean) casegen.flatMapCond(extractor, CODE.UNIT, nextBinder, condAndNext) + else casegen.flatMap(extractor, nextBinder, condAndNext) + ) + } + + override def toString = "X"+(extractor, nextBinder.name) + } + + /** + * An optimized version of ExtractorTreeMaker for Products. + * For now, this is hard-coded to case classes, and we simply extract the case class fields. + * + * The values for the subpatterns, as specified by the case class fields at the time of extraction, + * are stored in local variables that re-use the symbols in `subPatBinders`. + * This makes extractor patterns more debuggable (SI-5739) as well as + * avoiding mutation after the pattern has been matched (SI-5158, SI-6070) + * + * TODO: make this user-definable as follows + * When a companion object defines a method `def unapply_1(x: T): U_1`, but no `def unapply` or `def unapplySeq`, + * the extractor is considered to match any non-null value of type T + * the pattern is expected to have as many sub-patterns as there are `def unapply_I(x: T): U_I` methods, + * and the type of the I'th sub-pattern is `U_I`. + * The same exception for Seq patterns applies: if the last extractor is of type `Seq[U_N]`, + * the pattern must have at least N arguments (exactly N if the last argument is annotated with `: _*`). + * The arguments starting at N (and beyond) are taken from the sequence returned by apply_N, + * and it is checked that that sequence has enough elements to provide values for all expected sub-patterns. + * + * For a case class C, the implementation is assumed to be `def unapply_I(x: C) = x._I`, + * and the extractor call is inlined under that assumption. + */ + case class ProductExtractorTreeMaker(prevBinder: Symbol, extraCond: Option[Tree])( + val subPatBinders: List[Symbol], + val subPatRefs: List[Tree], + val mutableBinders: List[Symbol], + binderKnownNonNull: Boolean, + val ignoredSubPatBinders: Set[Symbol] + ) extends FunTreeMaker with PreserveSubPatBinders { + + import CODE._ + val nextBinder = prevBinder // just passing through + + // mutable binders must be stored to avoid unsoundness or seeing mutation of fields after matching (SI-5158, SI-6070) + def extraStoredBinders: Set[Symbol] = mutableBinders.toSet + + def chainBefore(next: Tree)(casegen: Casegen): Tree = { + val nullCheck = REF(prevBinder) OBJ_NE NULL + val cond = + if (binderKnownNonNull) extraCond + else (extraCond map (nullCheck AND _) + orElse Some(nullCheck)) + + cond match { + case Some(cond) => + casegen.ifThenElseZero(cond, bindSubPats(substitution(next))) + case _ => + bindSubPats(substitution(next)) + } + } + + override def toString = "P"+(prevBinder.name, extraCond getOrElse "", localSubstitution) + } + + object IrrefutableExtractorTreeMaker { + // will an extractor with unapply method of methodtype `tp` always succeed? + // note: this assumes the other side-conditions implied by the extractor are met + // (argument of the right type, length check succeeds for unapplySeq,...) + def irrefutableExtractorType(tp: Type): Boolean = tp.resultType.dealias match { + case TypeRef(_, SomeClass, _) => true + // probably not useful since this type won't be inferred nor can it be written down (yet) + case ConstantType(Constant(true)) => true + case _ => false + } + + def unapply(xtm: ExtractorTreeMaker): Option[(Tree, Symbol)] = xtm match { + case ExtractorTreeMaker(extractor, None, nextBinder) if irrefutableExtractorType(extractor.tpe) => + Some((extractor, nextBinder)) + case _ => + None + } + } + + 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 + def tru: Result + } + + object treeCondStrategy extends TypeTestCondStrategy { import CODE._ + type Result = Tree + + def and(a: Result, b: Result): Result = a AND b + def tru = mkTRUE + 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 + + def outerTest(testedBinder: Symbol, expectedTp: Type): Tree = { + val expectedOuter = expectedTp.prefix match { + case ThisType(clazz) => THIS(clazz) + case pre if pre != NoType => REF(pre.prefix, pre.termSymbol) + case _ => mkTRUE // fallback for SI-6183 + } + + // 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, newFlags = SYNTHETIC | ARTIFACT) setInfo expectedTp.prefix + + (Select(codegen._asInstanceOf(testedBinder, expectedTp), outer)) OBJ_EQ expectedOuter + } + } + + object pureTypeTestChecker extends TypeTestCondStrategy { + type Result = Boolean + + def typeTest(testedBinder: Symbol, expectedTp: Type): Result = true + + 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 + def tru = true + } + + def nonNullImpliedByTestChecker(binder: Symbol) = new TypeTestCondStrategy { + type Result = Boolean + + def typeTest(testedBinder: Symbol, expectedTp: Type): Result = testedBinder eq binder + def outerTest(testedBinder: Symbol, expectedTp: Type): Result = false + def nonNullTest(testedBinder: Symbol): Result = testedBinder eq binder + def equalsTest(pat: Tree, testedBinder: Symbol): Result = false // could in principle analyse pat and see if it's statically known to be non-null + def eqTest(pat: Tree, testedBinder: Symbol): Result = false // could in principle analyse pat and see if it's statically known to be non-null + def and(a: Result, b: Result): Result = a || b + def tru = false + } + } + + /** 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)(override val pos: Position, extractorArgTypeTest: Boolean = false) extends CondTreeMaker { + import TypeTestTreeMaker._ + debug.patmat("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) + + // propagate expected type + def expTp(t: Tree): t.type = t setType 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(gen.mkAttributedQualifier(expectedTp), 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(Constant(null)) if testedBinder.info.widen <:< AnyRefClass.tpe + => eqTest(expTp(CODE.NULL), testedBinder) + case ConstantType(const) => equalsTest(expTp(Literal(const)), testedBinder) + case ThisType(sym) => eqTest(expTp(This(sym)), 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 testedBinder.info.widen <:< expectedTp => + // if the expected type is a primitive value type, it cannot be null and it cannot have an outer pointer + // since the types conform, no further checking is required + if (expectedTp.typeSymbol.isPrimitiveValueClass) tru + // have to test outer and non-null only when it's a reference type + else if (expectedTp <:< AnyRefClass.tpe) { + // 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) + } else default + + case _ => default + } + } + + val cond = renderCondition(treeCondStrategy) + val res = codegen._asInstanceOf(testedBinder, nextBinderTp) + + // is this purely a type test, e.g. no outer check, no equality tests (used in switch emission) + def isPureTypeTest = renderCondition(pureTypeTestChecker) + + def impliesBinderNonNull(binder: Symbol) = renderCondition(nonNullImpliedByTestChecker(binder)) + + 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) + case class EqualityTestTreeMaker(prevBinder: Symbol, patTree: Tree, override val pos: Position) extends CondTreeMaker { + val nextBinderTp = prevBinder.info.widen + + // NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null) + // 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.name, patTree) + } + + case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker with NoNewBinders { + // don't substitute prevBinder to nextBinder, a set of alternatives does not need to introduce a new binder, simply reuse the previous one + + override private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = { + super.incorporateOuterSubstitution(outerSubst) + altss = altss map (alts => propagateSubstitution(alts, substitution)) + } + + def chainBefore(next: Tree)(codegenAlt: Casegen): Tree = { import CODE._ + atPos(pos){ + // one alternative may still generate multiple trees (e.g., an extractor call + equality test) + // (for now,) alternatives may not bind variables (except wildcards), so we don't care about the final substitution built internally by makeTreeMakers + val combinedAlts = altss map (altTreeMakers => + ((casegen: Casegen) => combineExtractors(altTreeMakers :+ TrivialTreeMaker(casegen.one(mkTRUE)))(casegen)) + ) + + val findAltMatcher = codegenAlt.matcher(EmptyTree, NoSymbol, BooleanClass.tpe)(combinedAlts, Some(x => mkFALSE)) + codegenAlt.ifThenElseZero(findAltMatcher, substitution(next)) + } + } + } + + case class GuardTreeMaker(guardTree: Tree) extends TreeMaker with NoNewBinders { + val pos = guardTree.pos + + def chainBefore(next: Tree)(casegen: Casegen): Tree = casegen.flatMapGuard(substitution(guardTree), next) + override def toString = "G("+ guardTree +")" + } + + // combineExtractors changes the current substitution's of the tree makers in `treeMakers` + // requires propagateSubstitution(treeMakers) has been called + def combineExtractors(treeMakers: List[TreeMaker])(casegen: Casegen): Tree = + treeMakers.foldRight(EmptyTree: Tree)((a, b) => a.chainBefore(b)(casegen)) + + + def removeSubstOnly(makers: List[TreeMaker]) = makers filterNot (_.isInstanceOf[SubstOnlyTreeMaker]) + + // a foldLeft to accumulate the localSubstitution left-to-right + // it drops SubstOnly tree makers, since their only goal in life is to propagate substitutions to the next tree maker, which is fullfilled by propagateSubstitution + def propagateSubstitution(treeMakers: List[TreeMaker], initial: Substitution): List[TreeMaker] = { + var accumSubst: Substitution = initial + treeMakers foreach { maker => + maker incorporateOuterSubstitution accumSubst + accumSubst = maker.substitution + } + removeSubstOnly(treeMakers) + } + + // calls propagateSubstitution on the treemakers + def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = { + // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them + val casesNoSubstOnly = casesRaw map (propagateSubstitution(_, EmptySubstitution)) + combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, matchFailGenOverride) + } + + // pt is the fully defined type of the cases (either pt or the lub of the types of the cases) + def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = + fixerUpper(owner, scrut.pos){ + def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree))) + debug.patmat("combining cases: "+ (casesNoSubstOnly.map(_.mkString(" >> ")).mkString("{", "\n", "}"))) + + val (unchecked, requireSwitch) = + if (settings.XnoPatmatAnalysis.value) (true, false) + else scrut match { + case Typed(_, tpt) => + (tpt.tpe hasAnnotation UncheckedClass, + // matches with two or fewer cases need not apply for switchiness (if-then-else will do) + treeInfo.isSwitchAnnotation(tpt.tpe) && casesNoSubstOnly.lengthCompare(2) > 0) + case _ => + (false, false) + } + + emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt, matchFailGenOverride, unchecked).getOrElse{ + if (requireSwitch) typer.context.unit.warning(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 + // exhaustivity and reachability must be checked before optimization as well + // TODO: improve notion of trivial/irrefutable -- a trivial type test before the body still makes for a default case + // ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op) + // irrefutability checking should use the approximation framework also used for CSE, unreachability and exhaustivity checking + val synthCatchAll = + if (casesNoSubstOnly.nonEmpty && { + val nonTrivLast = casesNoSubstOnly.last + nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker] + }) None + else matchFailGen + + val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt, unchecked) + + val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, synthCatchAll) + + if (toHoist isEmpty) matchRes else Block(toHoist, matchRes) + } else { + codegen.matcher(scrut, scrutSym, pt)(Nil, matchFailGen) + } + } + } + + // TODO: do this during tree construction, but that will require tracking the current owner in treemakers + // TODO: assign more fine-grained positions + // fixes symbol nesting, assigns positions + protected def fixerUpper(origOwner: Symbol, pos: Position) = new Traverser { + currentOwner = origOwner + + override def traverse(t: Tree) { + if (t != EmptyTree && t.pos == NoPosition) { + t.setPos(pos) + } + t match { + case Function(_, _) if t.symbol == NoSymbol => + t.symbol = currentOwner.newAnonymousFunctionValue(t.pos) + debug.patmat("new symbol for "+ (t, t.symbol.ownerChain)) + case Function(_, _) if (t.symbol.owner == NoSymbol) || (t.symbol.owner == origOwner) => + debug.patmat("fundef: "+ (t, t.symbol.ownerChain, currentOwner.ownerChain)) + t.symbol.owner = currentOwner + case d : DefTree if (d.symbol != NoSymbol) && ((d.symbol.owner == NoSymbol) || (d.symbol.owner == origOwner)) => // don't indiscriminately change existing owners! (see e.g., pos/t3440, pos/t3534, pos/unapplyContexts2) + debug.patmat("def: "+ (d, d.symbol.ownerChain, currentOwner.ownerChain)) + if(d.symbol.moduleClass ne NoSymbol) + d.symbol.moduleClass.owner = currentOwner + + d.symbol.owner = currentOwner + // case _ if (t.symbol != NoSymbol) && (t.symbol ne null) => + debug.patmat("untouched "+ (t, t.getClass, t.symbol.ownerChain, currentOwner.ownerChain)) + case _ => + } + super.traverse(t) + } + + // override def apply + // debug.patmat("before fixerupper: "+ xTree) + // currentRun.trackerFactory.snapshot() + // debug.patmat("after fixerupper") + // currentRun.trackerFactory.snapshot() + } + } +} \ No newline at end of file diff --git a/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala b/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala index 03c4e78771..07eed2cd94 100644 --- a/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala +++ b/src/compiler/scala/tools/nsc/transform/patmat/PatternMatching.scala @@ -17,8 +17,8 @@ import scala.reflect.internal.util.Position /** Translate pattern matching. * - * Either into optimized if/then/else's, - * or virtualized as method calls (these methods form a zero-plus monad), similar in spirit to how for-comprehensions are compiled. + * Either into optimized if/then/else's, or virtualized as method calls (these methods form a zero-plus monad), + * similar in spirit to how for-comprehensions are compiled. * * For each case, express all patterns as extractor calls, guards as 0-ary extractors, and sequence them using `flatMap` * (lifting the body of the case into the monad using `one`). @@ -37,12 +37,12 @@ import scala.reflect.internal.util.Position trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL with Debugging with Interface - with Translation - with TreeMaking - with CodeGen + with MatchTranslation + with MatchTreeMaking + with MatchCodeGen with ScalaLogic - with Analysis - with Optimization { + with MatchAnalysis + with MatchOptimization { import global._ val phaseName: String = "patmat" @@ -70,13 +70,16 @@ trait PatternMatching extends Transform with TypingTransformers with ast.TreeDSL case _ => super.transform(tree) } - def translator: MatchTranslation with CodegenCore = { + // TODO: only instantiate new match translator when localTyper has changed + // override def atOwner[A](tree: Tree, owner: Symbol)(trans: => A): A + // as this is the only time TypingTransformer changes it + def translator: MatchTranslator with CodegenCore = { new OptimizingMatchTranslator(localTyper) } } - class PureMatchTranslator(val typer: analyzer.Typer, val matchStrategy: Tree) extends MatchTranslation with TreeMakers with PureCodegen - class OptimizingMatchTranslator(val typer: analyzer.Typer) extends MatchTranslation with TreeMakers with MatchOptimizations + class PureMatchTranslator(val typer: analyzer.Typer, val matchStrategy: Tree) extends MatchTranslator with TreeMakers with PureCodegen + class OptimizingMatchTranslator(val typer: analyzer.Typer) extends MatchTranslator with TreeMakers with MatchOptimizations } trait HasGlobal { -- cgit v1.2.3 From 3d5758ca705be7f304d0a09f749e5742ec37231b Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Fri, 22 Feb 2013 22:04:58 +0100 Subject: SI-7171 Consider prefix when assessing type finality. `Type#isFinalType` determines if a type could have a non-bottom subtype. This property is exploited by the pattern matcher to flag impossible patterns. This check was ignoring the type's prefix, and incorrectly deemed that `T#A` in `trait T { final class A }` was a final type. But it could have been subtyped by `U#A` where `U` <:< `T`, or, more simply, by `T.this.A`. Now, type finality requires that the prefix is stable. The existing test cases in neg/patmat-type-check.scala still correctly flag incompatiblities. `isFinalType` is also used by some code that massages pattern matches post specialization. That is actually either broken or obsolete under virtpatmat, I've opened SI-7172 to invesigate that. It is also used by GenICode to determine whether to emit the appropriate equality checks that are correct in the face of boxing. It is possible that this change will force the slow path in some rare cases, but it won't affect correctness. --- src/reflect/scala/reflect/internal/Types.scala | 4 ++-- test/files/neg/t7171.check | 7 +++++++ test/files/neg/t7171.flags | 1 + test/files/neg/t7171.scala | 11 +++++++++++ test/files/neg/t7171b.check | 10 ++++++++++ test/files/neg/t7171b.flags | 1 + test/files/neg/t7171b.scala | 15 +++++++++++++++ test/files/run/t7171.scala | 22 ++++++++++++++++++++++ 8 files changed, 69 insertions(+), 2 deletions(-) create mode 100644 test/files/neg/t7171.check create mode 100644 test/files/neg/t7171.flags create mode 100644 test/files/neg/t7171.scala create mode 100644 test/files/neg/t7171b.check create mode 100644 test/files/neg/t7171b.flags create mode 100644 test/files/neg/t7171b.scala create mode 100644 test/files/run/t7171.scala diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index fb493fabd8..546df8a207 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -391,8 +391,8 @@ trait Types extends api.Types { self: SymbolTable => * This is assessed to be the case if the class is final, * and all type parameters (if any) are invariant. */ - def isFinalType = - typeSymbol.isFinal && (typeSymbol.typeParams forall symbolIsNonVariant) + def isFinalType: Boolean = + typeSymbol.isFinal && (typeSymbol.typeParams forall symbolIsNonVariant) && prefix.isStable /** Is this type completed (i.e. not a lazy type)? */ def isComplete: Boolean = true diff --git a/test/files/neg/t7171.check b/test/files/neg/t7171.check new file mode 100644 index 0000000000..8bdf08129b --- /dev/null +++ b/test/files/neg/t7171.check @@ -0,0 +1,7 @@ +t7171.scala:2: error: The outer reference in this type test cannot be checked at run time. + final case class A() + ^ +t7171.scala:9: error: The outer reference in this type test cannot be checked at run time. + case _: A => true; case _ => false + ^ +two errors found diff --git a/test/files/neg/t7171.flags b/test/files/neg/t7171.flags new file mode 100644 index 0000000000..464cc20ea6 --- /dev/null +++ b/test/files/neg/t7171.flags @@ -0,0 +1 @@ +-Xfatal-warnings -unchecked \ No newline at end of file diff --git a/test/files/neg/t7171.scala b/test/files/neg/t7171.scala new file mode 100644 index 0000000000..534b2070a3 --- /dev/null +++ b/test/files/neg/t7171.scala @@ -0,0 +1,11 @@ +trait T { + final case class A() + + // Was: + // error: scrutinee is incompatible with pattern type; + // found : T.this.A + // required: T#A + def foo(a: T#A) = a match { + case _: A => true; case _ => false + } +} diff --git a/test/files/neg/t7171b.check b/test/files/neg/t7171b.check new file mode 100644 index 0000000000..bd6b2bcfb4 --- /dev/null +++ b/test/files/neg/t7171b.check @@ -0,0 +1,10 @@ +t7171b.scala:2: error: The outer reference in this type test cannot be checked at run time. + final case class A() + ^ +t7171b.scala:8: error: The outer reference in this type test cannot be checked at run time. + case _: A => true; case _ => false + ^ +t7171b.scala:13: error: The outer reference in this type test cannot be checked at run time. + case _: A => true; case _ => false + ^ +three errors found diff --git a/test/files/neg/t7171b.flags b/test/files/neg/t7171b.flags new file mode 100644 index 0000000000..464cc20ea6 --- /dev/null +++ b/test/files/neg/t7171b.flags @@ -0,0 +1 @@ +-Xfatal-warnings -unchecked \ No newline at end of file diff --git a/test/files/neg/t7171b.scala b/test/files/neg/t7171b.scala new file mode 100644 index 0000000000..53c7787f8b --- /dev/null +++ b/test/files/neg/t7171b.scala @@ -0,0 +1,15 @@ +trait T { + final case class A() +} + +final class U extends T { + // this match should also not be deemed impossible + def foo(a: U#A) = a match { + case _: A => true; case _ => false + } + + // this match should also not be deemed impossible + def bar(a: T#A) = a match { + case _: A => true; case _ => false + } +} diff --git a/test/files/run/t7171.scala b/test/files/run/t7171.scala new file mode 100644 index 0000000000..97585b9860 --- /dev/null +++ b/test/files/run/t7171.scala @@ -0,0 +1,22 @@ +trait T { + final case class A() + + // Was: + // error: scrutinee is incompatible with pattern type; + // found : T.this.A + // required: T#A + def foo(a: T#A) = a match { + case _: A => true; case _ => false + } +} + +object Test extends App { + val t1 = new T {} + val t2 = new T {} + val a1 = new t1.A() + val a2 = new t1.A() + assert(t1.foo(a1)) + // as noted in the unchecked warning (tested in the corresponding neg test), + // the outer pointer isn't checked + assert(t1.foo(a2)) +} -- cgit v1.2.3