diff options
Diffstat (limited to 'src/compiler')
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 { |