From 2a2d5d6af91fe25b42a36639f1aaf983d6a2dd02 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Thu, 16 Jun 2011 03:22:59 +0000 Subject: Eliminating accumulated dead ends from the patt... Eliminating accumulated dead ends from the pattern matcher. No review. --- .../tools/nsc/matching/ParallelMatching.scala | 14 ++++--- .../scala/tools/nsc/matching/PatternBindings.scala | 42 ++++++------------- .../scala/tools/nsc/matching/Patterns.scala | 47 +++++++++------------- 3 files changed, 41 insertions(+), 62 deletions(-) diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala index bd78ba0f3d..65e570f133 100644 --- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala +++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala @@ -50,10 +50,12 @@ trait ParallelMatching extends ast.TreeDSL shortCuts(key) = theLabel -key } - def createLabelDef(prefix: String, params: List[Symbol] = Nil, tpe: Type = matchResultType) = { - val labelSym = owner.newLabel(owner.pos, cunit.freshTermName(prefix)) setInfo MethodType(params, tpe) + def createLabelDef(namePrefix: String, body: Tree, params: List[Symbol] = Nil, restpe: Type = matchResultType) = { + val labelName = cunit.freshTermName(namePrefix) + val labelSym = owner.newLabel(owner.pos, labelName) + val labelInfo = MethodType(params, restpe) - (body: Tree) => LabelDef(labelSym, params, body setType tpe) + LabelDef(labelSym setInfo labelInfo, params, body setType restpe) } /** This is the recursively focal point for translating the current @@ -297,7 +299,7 @@ trait ParallelMatching extends ast.TreeDSL literals.zipWithIndex map { case (lit, index) => val tag = lit.intValue - (tag -> index, tag -> lit.deepBoundVariables) + (tag -> index, tag -> lit.boundVariables) } unzip ) def literalMap = litPairs groupBy (_._1) map { @@ -511,7 +513,7 @@ trait ParallelMatching extends ast.TreeDSL case PseudoType(o) => o } private lazy val labelDef = - createLabelDef("fail%")(remake((rest.rows.tail, pmatch.tail).zipped map (_ insert _)).toTree) + createLabelDef("fail%", remake((rest.rows.tail, pmatch.tail).zipped map (_ insert _)).toTree) lazy val cond = handleOuter(rhs MEMBER_== scrut.id) lazy val successOne = rest.rows.head.insert2(List(NoPattern), head.boundVariables, scrut.sym) @@ -707,7 +709,7 @@ trait ParallelMatching extends ast.TreeDSL traceCategory("Final State", "(%s) => %s", paramsString, body) def label = Some(labelDef) - private lazy val labelDef = createLabelDef("body%" + bx, params, caseResultType)(body) + private lazy val labelDef = createLabelDef("body%" + bx, body, params, caseResultType) protected def applyBindingsImpl(subst: Map[Symbol, Symbol]) = { val tree = diff --git a/src/compiler/scala/tools/nsc/matching/PatternBindings.scala b/src/compiler/scala/tools/nsc/matching/PatternBindings.scala index 8bba8b559c..bfca609ca7 100644 --- a/src/compiler/scala/tools/nsc/matching/PatternBindings.scala +++ b/src/compiler/scala/tools/nsc/matching/PatternBindings.scala @@ -31,6 +31,12 @@ trait PatternBindings extends ast.TreeDSL // For spotting duplicate unapplies def isEquivalentTree(t1: Tree, t2: Tree) = (t1.symbol == t2.symbol) && (t1 equalsStructure t2) + // Reproduce the Bind trees wrapping oldTree around newTree + def moveBindings(oldTree: Tree, newTree: Tree): Tree = oldTree match { + case b @ Bind(x, body) => Bind(b.symbol, moveBindings(body, newTree)) + case _ => newTree + } + // used as argument to `EqualsPatternClass' case class PseudoType(o: Tree) extends SimpleTypeProxy { override def underlying: Type = o.tpe @@ -58,42 +64,20 @@ trait PatternBindings extends ast.TreeDSL // bound variables beneath them return a list of said patterns for flatMapping. def subpatternsForVars: List[Pattern] = Nil - private def shallowBoundVariables = strip(boundTree) - private def otherBoundVariables = subpatternsForVars flatMap (_.deepBoundVariables) - - def deepBoundVariables: List[Symbol] = shallowBoundVariables ::: otherBoundVariables - // An indiscriminate deep search would be: - // - // def deepBoundVariables = deepstrip(boundTree) - - lazy val boundVariables = { - val res = shallowBoundVariables - val deep = deepBoundVariables - - if (res.size != deep.size) - TRACE("deep variable list %s is larger than bound %s", deep, res) - - res - } - - // XXX only a var for short-term experimentation. - private var _boundTree: Bind = null - def boundTree = if (_boundTree == null) tree else _boundTree - def withBoundTree(x: Bind): this.type = { + // The outermost Bind(x1, Bind(x2, ...)) surrounding the tree. + private var _boundTree: Tree = tree + def boundTree = _boundTree + def setBound(x: Bind): Pattern = { _boundTree = x - tracing[this.type]("Bound")(this) + this } + def boundVariables = strip(boundTree) // If a tree has bindings, boundTree looks something like // Bind(v3, Bind(v2, Bind(v1, tree))) // This takes the given tree and creates a new pattern // using the same bindings. - def rebindTo(t: Tree): Pattern = { - if (boundVariables.size < deepBoundVariables.size) - TRACE("ALERT: rebinding %s is losing %s", this, otherBoundVariables) - - Pattern(wrapBindings(boundVariables, t)) - } + def rebindTo(t: Tree): Pattern = Pattern(moveBindings(boundTree, t)) // Wrap this pattern's bindings around (_: Type) def rebindToType(tpe: Type, ascription: Type = null): Pattern = { diff --git a/src/compiler/scala/tools/nsc/matching/Patterns.scala b/src/compiler/scala/tools/nsc/matching/Patterns.scala index 3ea1b1cdb2..92ec9a8e33 100644 --- a/src/compiler/scala/tools/nsc/matching/Patterns.scala +++ b/src/compiler/scala/tools/nsc/matching/Patterns.scala @@ -75,7 +75,7 @@ trait Patterns extends ast.TreeDSL { case ExtractorPattern(ua) if pv.sym.tpe <:< tpt.tpe => this rebindTo expr case _ => this } - override def description = "%s: %s".format(exprPat.boundNameString, tpt) + override def description = "%s: %s".format(exprPat, tpt) } // 8.1.3 @@ -190,35 +190,38 @@ trait Patterns extends ast.TreeDSL { // Special List handling. It was like that when I got here. case class ListExtractorPattern(tree: UnApply, tpt: Tree, elems: List[Tree]) extends UnapplyPattern with SequenceLikePattern { - private val cons = ConsClass.primaryConstructor.tpe.resultType - private val consRef = typeRef(cons.prefix, ConsClass, List(tpt.tpe)) - private val listRef = typeRef(cons.prefix, ListClass, List(tpt.tpe)) - private val seqRef = typeRef(cons.prefix, SeqClass, List(tpt.tpe)) + // As yet I can't testify this is doing any good relative to using + // tpt.tpe, but it doesn't seem to hurt either. + private val packedType = global.typer.computeType(tpt, tpt.tpe) + private val consRef = typeRef(NoPrefix, ConsClass, List(packedType)) + private val listRef = typeRef(NoPrefix, ListClass, List(packedType)) + private val seqRef = typeRef(NoPrefix, SeqClass, List(packedType)) + private def thisSeqRef = { val tc = (tree.tpe baseType SeqClass).typeConstructor - if (tc.typeParams.size == 1) appliedType(tc, List(tpt.tpe)) + if (tc.typeParams.size == 1) appliedType(tc, List(packedType)) else seqRef } // Fold a list into a well-typed x :: y :: etc :: tree. - private def listFolder(x: Pattern, xs: Pattern): Pattern = x match { - case Pattern(Star(_)) => x rebindTo WILD(x.tpe) - case _ => + private def listFolder(hd: Tree, tl: Tree): Tree = unbind(hd) match { + case t @ Star(_) => moveBindings(hd, WILD(t.tpe)) + case _ => val dummyMethod = new TermSymbol(NoSymbol, NoPosition, "matching$dummy") - val consType = MethodType(dummyMethod newSyntheticValueParams List(tpt.tpe, listRef), consRef) + val consType = MethodType(dummyMethod newSyntheticValueParams List(packedType, listRef), consRef) - Pattern(Apply(TypeTree(consType), List(x.boundTree, xs.boundTree)) setType consRef) + Apply(TypeTree(consType), List(hd, tl)) setType consRef } - private def foldedPatterns = elems.foldRight(NilPattern)((x, y) => listFolder(Pattern(x), y)) + private def foldedPatterns = elems.foldRight(gen.mkNil)((x, y) => listFolder(x, y)) override def necessaryType = if (nonStarPatterns.nonEmpty) consRef else listRef override def simplify(pv: PatternVar) = { if (pv.tpe <:< necessaryType) - foldedPatterns + Pattern(foldedPatterns) else this rebindTo (Typed(tree, TypeTree(necessaryType)) setType necessaryType) } - override def description = "List(%s => %s)".format(tpt.tpe, resTypesString) + override def description = "List(%s => %s)".format(packedType, resTypesString) } trait SequenceLikePattern extends Pattern { @@ -277,7 +280,7 @@ trait Patterns extends ast.TreeDSL { return cache(tree) val p = tree match { - case x: Bind => apply(unbind(tree)) withBoundTree x + case x: Bind => apply(unbind(tree)) setBound x case EmptyTree => WildcardPattern() case Ident(nme.WILDCARD) => WildcardPattern() case x @ Alternative(ps) => AlternativePattern(x) @@ -455,11 +458,6 @@ trait Patterns extends ast.TreeDSL { tree setType tpe this } - def boundName: Option[Name] = boundTree match { - case Bind(name, _) => Some(name) - case _ => None - } - def boundNameString = "" + (boundName getOrElse "_") def equalsCheck = tracing("equalsCheck")( @@ -474,14 +472,9 @@ trait Patterns extends ast.TreeDSL { } override def hashCode() = boundTree.hashCode() def description = super.toString() - def bindingsDescription = - if (boundTree.isEmpty) "" - else (boundVariables map (_.name)).mkString("", ", ", " @ ") - final override def toString() = { - if (boundVariables.isEmpty) description - else "%s%s".format(bindingsDescription, description) - } + final override def toString() = description + def toTypeString() = "%s <: x <: %s".format(necessaryType, sufficientType) } -- cgit v1.2.3