diff options
author | Paul Phillips <paulp@improving.org> | 2010-05-12 21:17:29 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2010-05-12 21:17:29 +0000 |
commit | 016d815104b1d44b2b899c68804dde500963fbcd (patch) | |
tree | e223ac275ad0321f9e5d51e847f30ab11e7a234f /src | |
parent | 0ed53d4d686db74a54315cd5ccf79bda3690b036 (diff) | |
download | scala-016d815104b1d44b2b899c68804dde500963fbcd.tar.gz scala-016d815104b1d44b2b899c68804dde500963fbcd.tar.bz2 scala-016d815104b1d44b2b899c68804dde500963fbcd.zip |
Overhauled sequence length logic in the pattern...
Overhauled sequence length logic in the pattern matcher. Removes
unnecessary boxing and a few varieties of wrongness.
Closes #3395, #3150, #2958, #2945, #2187. No review.
Diffstat (limited to 'src')
-rw-r--r-- | src/compiler/scala/tools/nsc/ast/TreeDSL.scala | 1 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/matching/ParallelMatching.scala | 91 | ||||
-rw-r--r-- | src/compiler/scala/tools/nsc/matching/Patterns.scala | 84 |
3 files changed, 89 insertions, 87 deletions
diff --git a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala index fd13958053..9aa36de703 100644 --- a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala +++ b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala @@ -93,6 +93,7 @@ trait TreeDSL { def INT_| (other: Tree) = fn(target, getMember(IntClass, nme.OR), other) def INT_& (other: Tree) = fn(target, getMember(IntClass, nme.AND), other) + def INT_>= (other: Tree) = fn(target, getMember(IntClass, nme.GE), other) def INT_== (other: Tree) = fn(target, getMember(IntClass, nme.EQ), other) def INT_!= (other: Tree) = fn(target, getMember(IntClass, nme.NE), other) diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala index 1806dec2d2..77997c4565 100644 --- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala +++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala @@ -175,7 +175,6 @@ trait ParallelMatching extends ast.TreeDSL def isCaseHead = head.isCaseClass private val dummyCount = if (isCaseHead) headType.typeSymbol.caseFieldAccessors.length else 0 def dummies = emptyPatterns(dummyCount) - // def dummies = head.dummies def apply(i: Int): Pattern = ps(i) def pzip() = ps.zipWithIndex @@ -443,32 +442,92 @@ trait ParallelMatching extends ast.TreeDSL * Note: pivot == head, just better typed. */ sealed class MixSequence(val pmatch: PatternMatch, val rest: Rep, pivot: SequencePattern) extends RuleApplication { + require(scrut.tpe <:< head.tpe) + def hasStar = pivot.hasStar - private def pivotLen = pivot.nonStarLength + private def pivotLen = pivot.nonStarLength + private def seqDummies = emptyPatterns(pivot.elems.length + 1) // one pattern var per sequence element up to elemCount, and one more for the rest of the sequence lazy val pvs = scrut createSequenceVars pivotLen - // divide the remaining rows into success/failure branches, expanding subsequences of patterns - private lazy val rowsplit = { - require(scrut.tpe <:< head.tpe) + // Should the given pattern join the expanded pivot in the success matrix? If so, + // this partial function will be defined for the pattern, and the result of the apply + // is the expanded sequence of new patterns. + lazy val successMatrixFn = new PartialFunction[Pattern, List[Pattern]] { + private def seqIsDefinedAt(x: SequenceLikePattern) = (hasStar, x.hasStar) match { + case (true, true) => true + case (true, false) => pivotLen <= x.nonStarLength + case (false, true) => pivotLen >= x.nonStarLength + case (false, false) => pivotLen == x.nonStarLength + } - val res = for ((c, rows) <- pmatch pzip rest.rows) yield { - def canSkip = pivot canSkipSubsequences c - def passthrough(skip: Boolean) = if (skip) None else Some(rows insert c) + def isDefinedAt(pat: Pattern) = pat match { + case x: SequenceLikePattern => seqIsDefinedAt(x) + case WildcardPattern() => true + case _ => false + } - pivot.subsequences(c, scrut.seqType) match { - case Some(ps) => (Some(rows insert ps), passthrough(canSkip)) - case None => (None, passthrough(false)) - } + def apply(pat: Pattern): List[Pattern] = pat match { + case x: SequenceLikePattern => + def isSameLength = pivotLen == x.nonStarLength + def rebound = x.nonStarPatterns :+ (x.elemPatterns.last rebindTo WILD(scrut.seqType)) + + (pivot.hasStar, x.hasStar, isSameLength) match { + case (true, true, true) => rebound :+ NoPattern + case (true, true, false) => (seqDummies drop 1) :+ x + case (true, false, true) => x.elemPatterns ++ List(NilPattern, NoPattern) + case (false, true, true) => rebound + case (false, false, true) => x.elemPatterns :+ NoPattern + case _ => seqDummies + } + + case _ => seqDummies } + } - res.unzip match { case (l1, l2) => (l1.flatten, l2.flatten) } + // Should the given pattern be in the fail matrix? This is true of any sequences + // as long as the result of the length test on the pivot doesn't make it impossible: + // for instance if neither sequence is right ignoring and they are of different + // lengths, the later one cannot match since its length must be wrong. + def failureMatrixFn(c: Pattern) = (pivot ne c) && (c match { + case x: SequenceLikePattern => + (hasStar, x.hasStar) match { + case (_, true) => true + case (true, false) => pivotLen > x.nonStarLength + case (false, false) => pivotLen != x.nonStarLength + } + case WildcardPattern() => true + case _ => false + }) + + // divide the remaining rows into success/failure branches, expanding subsequences of patterns + val successRows = pmatch pzip rest.rows collect { + case (c, row) if successMatrixFn isDefinedAt c => row insert successMatrixFn(c) + } + val failRows = pmatch pzip rest.rows collect { + case (c, row) if failureMatrixFn(c) => row insert c } - lazy val cond = (pivot precondition pmatch).get // length check - lazy val success = squeezedBlockPVs(pvs, remake(rowsplit._1, pvs, hasStar).toTree) - lazy val failure = remake(rowsplit._2).toTree + // the discrimination test for sequences is a call to lengthCompare. Note that + // this logic must be fully consistent wiith successMatrixFn and failureMatrixFn above: + // any inconsistency will (and frequently has) manifested as pattern matcher crashes. + lazy val cond = { + // the method call symbol + val methodOp: Symbol = head.tpe member nme.lengthCompare + + // the comparison to perform. If the pivot is right ignoring, then a scrutinee sequence + // of >= pivot length could match it; otherwise it must be exactly equal. + val compareOp: (Tree, Tree) => Tree = if (hasStar) _ INT_>= _ else _ INT_== _ + + // scrutinee.lengthCompare(pivotLength) [== | >=] 0 + val compareFn: Tree => Tree = (t: Tree) => compareOp((t DOT methodOp)(LIT(pivotLen)), ZERO) + + // wrapping in a null check on the scrutinee + nullSafe(compareFn, FALSE)(scrut.id) + } + lazy val success = squeezedBlockPVs(pvs, remake(successRows, pvs, hasStar).toTree) + lazy val failure = remake(failRows).toTree final def tree(): Tree = codegen } diff --git a/src/compiler/scala/tools/nsc/matching/Patterns.scala b/src/compiler/scala/tools/nsc/matching/Patterns.scala index a21a9c7d9f..d35049c1e5 100644 --- a/src/compiler/scala/tools/nsc/matching/Patterns.scala +++ b/src/compiler/scala/tools/nsc/matching/Patterns.scala @@ -177,9 +177,9 @@ trait Patterns extends ast.TreeDSL { } // 8.1.8 (unapplySeq calls) - case class SequenceExtractorPattern(tree: UnApply) extends UnapplyPattern { + case class SequenceExtractorPattern(tree: UnApply) extends UnapplyPattern with SequenceLikePattern { - private val UnApply( + lazy val UnApply( Apply(TypeApply(Select(_, nme.unapplySeq), List(tptArg)), _), List(ArrayValue(_, elems)) ) = tree @@ -211,88 +211,34 @@ trait Patterns extends ast.TreeDSL { override def description = "UnSeq(%s => %s)".format(tptArg, resTypesString) } - abstract class SequencePattern extends Pattern { - val tree: ArrayValue - def nonStarPatterns: List[Pattern] - def subsequences(other: Pattern, seqType: Type): Option[List[Pattern]] - def canSkipSubsequences(second: Pattern): Boolean - - lazy val ArrayValue(elemtpt, elems) = tree - lazy val elemPatterns = toPats(elems) - - override def dummies = emptyPatterns(elems.length + 1) - override def subpatternsForVars: List[Pattern] = elemPatterns + trait SequenceLikePattern extends Pattern { + def elems: List[Tree] + def elemPatterns = toPats(elems) + def nonStarPatterns: List[Pattern] = if (hasStar) elemPatterns.init else elemPatterns def nonStarLength = nonStarPatterns.length def isAllDefaults = nonStarPatterns forall (_.isDefault) - def isShorter(other: SequencePattern) = nonStarLength < other.nonStarLength - def isSameLength(other: SequencePattern) = nonStarLength == other.nonStarLength - - protected def lengthCheckOp: (Tree, Tree) => Tree = - if (hasStar) _ ANY_>= _ - else _ MEMBER_== _ - - // optimization to avoid trying to match if length makes it impossible - override def precondition(pm: PatternMatch) = { - import pm.{ scrut, head } - val len = nonStarLength - val compareOp = head.tpe member nme.lengthCompare - - def cmpFunction(t1: Tree) = lengthCheckOp((t1 DOT compareOp)(LIT(len)), ZERO) + def isShorter(other: SequenceLikePattern) = nonStarLength < other.nonStarLength + def isSameLength(other: SequenceLikePattern) = nonStarLength == other.nonStarLength + } - Some(nullSafe(cmpFunction _, FALSE)(scrut.id)) - } + abstract class SequencePattern extends Pattern with SequenceLikePattern { + val tree: ArrayValue + lazy val ArrayValue(elemtpt, elems) = tree - /** True if 'next' must be checked even if 'first' failed to match after passing its length test - * (the conditional supplied by getPrecondition.) This is an optimization to avoid checking sequences - * which cannot match due to a length incompatibility. - */ + override def subpatternsForVars: List[Pattern] = elemPatterns override def description = "Seq(%s)".format(elemPatterns) } // 8.1.8 (b) (literal ArrayValues) case class SequenceNoStarPattern(tree: ArrayValue) extends SequencePattern { require(!hasStar) - lazy val nonStarPatterns = elemPatterns - - // no star - def subsequences(other: Pattern, seqType: Type): Option[List[Pattern]] = - condOpt(other) { - case next: SequenceStarPattern if isSameLength(next) => next rebindStar seqType - case next: SequenceNoStarPattern if isSameLength(next) => next.elemPatterns ::: List(NoPattern) - case WildcardPattern() | (_: SequencePattern) => dummies - } - - def canSkipSubsequences(second: Pattern): Boolean = - (tree eq second.tree) || (cond(second) { - case x: SequenceNoStarPattern => (x isShorter this) && this.isAllDefaults - }) } // 8.1.8 (b) case class SequenceStarPattern(tree: ArrayValue) extends SequencePattern { require(hasStar) - lazy val nonStarPatterns = elemPatterns.init - - // yes star - private def nilPats = List(NilPattern, NoPattern) - def subsequences(other: Pattern, seqType: Type): Option[List[Pattern]] = - condOpt(other) { - case next: SequenceStarPattern if isSameLength(next) => (next rebindStar seqType) ::: List(NoPattern) - case next: SequenceStarPattern if (next isShorter this) => (dummies drop 1) ::: List(next) - case next: SequenceNoStarPattern if isSameLength(next) => next.elemPatterns ::: nilPats - case WildcardPattern() | (_: SequencePattern) => dummies - } - - def rebindStar(seqType: Type): List[Pattern] = - nonStarPatterns ::: List(elemPatterns.last rebindTo WILD(seqType)) - - def canSkipSubsequences(second: Pattern): Boolean = - (tree eq second.tree) || (cond(second) { - case x: SequenceStarPattern => this isShorter x - case x: SequenceNoStarPattern => !(x isShorter this) - }) override def description = "Seq*(%s)".format(elemPatterns) } @@ -504,10 +450,6 @@ trait Patterns extends ast.TreeDSL { // the right number of dummies for this pattern def dummies: List[Pattern] = Nil - // given this scrutinee, what if any condition must be satisfied before - // we even try to match? - def precondition(scrut: PatternMatch): Option[Tree] = None - // 8.1.13 // A pattern p is irrefutable for type T if any of the following applies: // 1) p is a variable pattern |