From e373d268a5a15daab4ee2aef8f45eccca908b026 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Sun, 5 Jul 2009 12:51:47 +0000 Subject: Removed a pile of gratuitous implicit parameter... Removed a pile of gratuitous implicit parameters from the pattern matcher. Moved many things to more believable locations. Transitioned everything in CodeFactory and deleted it. --- src/compiler/scala/tools/nsc/ast/TreeDSL.scala | 10 + .../scala/tools/nsc/matching/CodeFactory.scala | 99 -- .../tools/nsc/matching/ParallelMatching.scala | 1580 ++++++++++---------- .../scala/tools/nsc/matching/PatternNodes.scala | 2 - .../scala/tools/nsc/matching/TransMatcher.scala | 135 +- .../scala/tools/nsc/transform/ExplicitOuter.scala | 7 +- 6 files changed, 936 insertions(+), 897 deletions(-) delete mode 100644 src/compiler/scala/tools/nsc/matching/CodeFactory.scala diff --git a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala index 229a650477..d25861ee39 100644 --- a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala +++ b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala @@ -19,10 +19,20 @@ trait TreeDSL { import gen.{ scalaDot } object CODE { + // clarity aliases + type TreeFunction1 = Tree => Tree + type TreeFunction2 = (Tree, Tree) => Tree + // Create a conditional based on a partial function - for values not defined // on the partial, it is false. def cond[T](x: T)(f: PartialFunction[T, Boolean]) = (f isDefinedAt x) && f(x) + // strip bindings to find what lies beneath + final def unbind(x: Tree): Tree = x match { + case Bind(_, y) => unbind(y) + case y => y + } + object LIT extends (Any => Literal) { def apply(x: Any) = Literal(Constant(x)) def unapply(x: Any) = x match { diff --git a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala deleted file mode 100644 index 2b25b2c49c..0000000000 --- a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala +++ /dev/null @@ -1,99 +0,0 @@ -/* NSC -- new Scala compiler - * Copyright 2005-2009 LAMP/EPFL - * @author Burak Emir - */ -// $Id$ - -package scala.tools.nsc.matching - -import scala.tools.nsc.util.Position - -/** Helper methods that build trees for pattern matching. - * - * @author Burak Emir - */ -trait CodeFactory extends ast.TreeDSL -{ - self: transform.ExplicitOuter with PatternNodes => - - import global.{ typer => _, _ } - import analyzer.Typer - import definitions._ - import CODE._ - - // strip bindings to find what tree lies underneath - def unbind(x: Tree): Tree = x match { - case Bind(_, y) => unbind(y) - case y => y - } - - final def typedValDef(x: Symbol, rhs: Tree)(implicit typer: Typer) = { - val finalRhs = x.tpe match { - case WildcardType => - rhs setType null - x setInfo (typer typed rhs).tpe - rhs - case _ => - typer.typed(rhs, x.tpe) - } - typer typed (VAL(x) === finalRhs) - } - - final def squeezedBlock(vds: List[Tree], exp: Tree)(implicit theOwner: Symbol): Tree = - if (settings_squeeze) Block(Nil, squeezedBlock1(vds, exp)) - else Block(vds, exp) - - final def squeezedBlock1(vds: List[Tree], exp: Tree)(implicit theOwner: Symbol): Tree = { - class RefTraverser(sym: Symbol) extends Traverser { - var nref, nsafeRef = 0 - override def traverse(tree: Tree) = tree match { - case t: Ident if t.symbol eq sym => - nref += 1 - if (sym.owner == currentOwner) // oldOwner should match currentOwner - nsafeRef += 1 - - case LabelDef(_, args, rhs) => - (args dropWhile(_.symbol ne sym)) match { - case Nil => - case _ => nref += 2 // cannot substitute this one - } - traverse(rhs) - case t if nref > 1 => // abort, no story to tell - case t => - super.traverse(t) - } - } - - class Subst(sym: Symbol, rhs: Tree) extends Transformer { - var stop = false - override def transform(tree: Tree) = tree match { - case t: Ident if t.symbol == sym => - stop = true - rhs - case _ => if (stop) tree else super.transform(tree) - } - } - - lazy val squeezedTail = squeezedBlock(vds.tail, exp) - def default = squeezedTail match { - case Block(vds2, exp2) => Block(vds.head :: vds2, exp2) - case exp2 => Block(vds.head :: Nil, exp2) - } - - if (vds.isEmpty) exp - else vds.head match { - case vd: ValDef => - val sym = vd.symbol - val rt = new RefTraverser(sym) - rt.atOwner (theOwner) (rt traverse squeezedTail) - - rt.nref match { - case 0 => squeezedTail - case 1 if rt.nsafeRef == 1 => new Subst(sym, vd.rhs) transform squeezedTail - case _ => default - } - case _ => - default - } - } -} diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala index 7ce01f9c48..d6b0592989 100644 --- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala +++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala @@ -26,10 +26,16 @@ import MatchUtil._ * * Row( p_m1 ... p_mn g_m b_m ) + subst * + * Implementation based on the algorithm described in + * + * "A Term Pattern-Match Compiler Inspired by Finite Automata Theory" + * Mikael Pettersson + * ftp://ftp.ida.liu.se/pub/labs/pelab/papers/cc92pmc.ps.gz + * * @author Burak Emir */ trait ParallelMatching extends ast.TreeDSL { - self: transform.ExplicitOuter with PatternNodes with CodeFactory => + self: transform.ExplicitOuter with PatternNodes => // debugging var, set to true to see how sausages are made private var trace = false @@ -40,61 +46,22 @@ trait ParallelMatching extends ast.TreeDSL { import Types._ import CODE._ - type TreeFunction1 = Tree => Tree - type TreeFunction2 = (Tree, Tree) => Tree - object Implicits { implicit def mkPattern(t: Tree) = Pattern(t) } import Implicits._ def ifDebug(body: => Unit): Unit = { if (settings.debug.value) body } - def DBG(msg: String): Unit = { ifDebug(println(msg)) } + def DBG(msg: => String): Unit = { ifDebug(println(msg)) } def TRACE(f: String, xs: Any*): Unit = { if (trace) println(if (xs.isEmpty) f else f.format(xs : _*)) } def logAndReturn[T](s: String, x: T): T = { log(s + x.toString) ; x } def traceAndReturn[T](s: String, x: T): T = { TRACE(s + x.toString) ; x } - /** - * Encapsulates a symbol being matched on. - * - * sym match { ... } - * - * results in Scrutinee(sym). - * - * Note that we only ever match on Symbols, not Trees: a temporary variable - * is created for any expressions being matched on. - */ - case class Scrutinee(val sym: Symbol) { - import definitions._ - - // presenting a face of our symbol - def tpe = sym.tpe - def pos = sym.pos - def accessors = sym.caseFieldAccessors - def id = ID(sym) // attributed ident - - // tests - def isDefined = sym ne NoSymbol - def isSimple = tpe.isChar || tpe.isInt - - // sequences - def seqType = tpe.widen baseType SeqClass - def elemType = tpe typeArgs 0 // can this happen? if (seqType == NoType) error("...") - - // for propagating "unchecked" to synthetic vars - def flags: List[Long] = if (sym hasFlag Flags.TRANS_FLAG) List(Flags.TRANS_FLAG) else Nil - - def assertIsSubtype(other: Type) = assert(isSubType(tpe, other), "problem "+tpe+" not <: "+other) - def casted(headType: Type)(implicit theOwner: Symbol) = - if (tpe =:= headType) this - else new Scrutinee(newVar(pos, headType, flags = flags)) - } - + def isRightIgnoring(t: Tree) = t.isRightIgnoring case class Pattern(tree: Tree) { import definitions._ lazy val sym = tree.symbol lazy val tpe = tree.tpe - lazy val symtpe = sym.tpe lazy val prefix = tpe.prefix lazy val tpeIfHead = stripped.tree match { case p @ (_:Ident | _:Select) => singleType(stripped.prefix, stripped.sym) //should be singleton object @@ -114,6 +81,13 @@ trait ParallelMatching extends ast.TreeDSL { final def isDefault = isDefaultPattern(tree) final def isEquals = cond(tpe) { case TypeRef(_, EqualsPatternClass, _) => true } + /* a Seq ending in _* */ + final def isRightIgnoring = { + def isStar(t: Tree) = cond(unbind(t)) { case Star(q) => isDefaultPattern(q) } + + cond(tree) { case ArrayValue(_, xs) if !xs.isEmpty => isStar(xs.last) } + } + final def getAlternativeBranches: List[Tree] = { def get_BIND(pctx: TreeFunction1, p: Tree): List[Tree] = p match { case b @ Bind(n, p) => get_BIND((x: Tree) => pctx(treeCopy.Bind(b, n, x) setType x.tpe), p) @@ -142,573 +116,17 @@ trait ParallelMatching extends ast.TreeDSL { (sym ne null) && (sym != NoSymbol) && prefix.isStable && (head =:= singleType(prefix, sym)) } - case class Patterns(scrut: Scrutinee, ps: List[Pattern]) { - private lazy val column = ps map (_.tree) - lazy val head = ps.head - lazy val tail = Patterns(scrut, ps.tail) - lazy val last = ps.last - lazy val headType = head.tpeIfHead - lazy val isCaseHead = headType.isCaseClass - lazy val dummies = if (isCaseHead) getDummies(headType.typeSymbol.caseFieldAccessors.length) else Nil - lazy val size = ps.length - - def apply(i: Int): Tree = ps(i).tree - def zip() = column.zipWithIndex - def zip[T](ys: List[T]) = column zip ys - - def isObjectTest(pat: Pattern) = pat isObjectTest headType - def isObjectTest(pat: Tree) = Pattern(pat) isObjectTest headType - // an unapply for which we don't need a type test - def isUnapplyHead = cond (head.tree) { case __UnApply(_,tpe,_) => scrut.tpe <:< tpe } - - def isSimpleSwitch: Boolean = - scrut.isSimple && ps.init.forall(_.isSimpleSwitchCandidate) && - // TODO: This needs to also allow the case that the last is a compatible type pattern. - (last.isSimpleSwitchCandidate || last.isDefault) - - def mkRule(rest: Rep)(implicit rep: RepFactory): RuleApplication = - logAndReturn("mkRule: ", head match { - case x if x.isEquals => new MixEquals(this, rest) - case Pattern(x: ArrayValue) => if (isRightIgnoring(x)) new MixSequenceStar(this, rest) - else new MixSequence(this, rest) - case _ if isSimpleSwitch => new MixLiterals(this, rest) - case _ if isUnapplyHead => new MixUnapply(this, rest) - case _ => new MixTypes(this, rest) - } - ) - } - - /** - * Class encapsulating a guard expression in a pattern match: - * case ... if(tree) => ... - */ - case class Guard(tree: Tree) { - def isEmpty = tree eq EmptyTree - def duplicate = Guard(tree.duplicate) - override def toString() = if (isEmpty) "" else " // if %s" format tree - } - val NoGuard = Guard(EmptyTree) - - /** picks which rewrite rule to apply - * @precondition: column does not contain alternatives (ensured by initRep) - */ - def MixtureRule(scrut: Scrutinee, column: List[Tree], rest: Rep)(implicit rep: RepFactory): RuleApplication = - Patterns(scrut, column map Pattern) mkRule rest - - sealed abstract class RuleApplication(rep: RepFactory) { - implicit def typer = rep.typer - - def pats: Patterns - def rest: Rep - lazy val Patterns(scrut, patterns) = pats - lazy val head = pats.head - private lazy val sym = scrut.sym - - def mkFail(xs: List[Row])(implicit theOwner: Symbol) = - rep.make(sym :: rest.temp, xs) - def mkNewRep(pre: List[Symbol], post: List[Symbol], rows: List[Row])(implicit theOwner: Symbol) = - rep.make(pre ::: sym :: post, rows) - - /** translate outcome of the rule application into code (possible involving recursive application of rewriting) */ - def tree(implicit theOwner: Symbol, failTree: Tree): Tree - } - - case class ErrorRule(implicit rep:RepFactory) extends RuleApplication(rep) { - def pats: Patterns = impossible - def rest: Rep = impossible - final def tree(implicit theOwner: Symbol, failTree: Tree) = failTree - } - - /** {case ... if guard => bx} else {guardedRest} */ - case class VariableRule(subst: Bindings, guard: Guard, guardedRest: Rep, bx: Int)(implicit rep:RepFactory) extends RuleApplication(rep) { - def pats: Patterns = impossible - def rest: Rep = guardedRest - - final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = { - val body = typer typed rep.requestBody(bx, subst) - def vdefs = subst.targetParams - def typedElse = guardedRest.toTree - def typedIf = typer typed (IF (guard.duplicate.tree) THEN body ELSE typedElse) - - if (guard.isEmpty) body - else typer typed squeezedBlock(vdefs, typedIf) - } - } - - /** mixture rule for literals - */ - class MixLiterals(val pats: Patterns, val rest: Rep)(implicit rep:RepFactory) extends RuleApplication(rep) { - // e.g. (1,1) (1,3) (42,2) for column { case ..1.. => ;; case ..42..=> ;; case ..1.. => } - var defaultV: Set[Symbol] = emptySymbolSet - var defaultIndexSet = new BitSet(pats.size) - - def insertDefault(tag: Int, vs: Traversable[Symbol]) { - defaultIndexSet += tag - defaultV = defaultV ++ vs - } - - def haveDefault: Boolean = !defaultIndexSet.isEmpty - def defaultRows: List[Row] = defaultIndexSet.toList reverseMap grabRow - - protected var tagIndices = IntMap.empty[List[Int]] - protected def grabRow(index: Int): Row = { - val r = rest.row(index) - if (defaultV.isEmpty) r - else r.insert2(Nil, pats(index).boundVariables, scrut.sym) // get vars - } - - /** inserts row indices using in to list of tagIndices */ - protected def tagIndicesToReps(implicit theOwner: Symbol) : List[(Int, Rep)] = - tagIndices map { case (k, v) => (k, rep.make(rest.temp, v.reverseMap(grabRow) ::: defaultRows)) } toList - - protected def defaultsToRep(implicit theOwner: Symbol) = rep.make(rest.temp, defaultRows) - - protected def insertTagIndexPair(tag: Int, index: Int) = - tagIndices = tagIndices.update(tag, index :: tagIndices.getOrElse(tag, Nil)) - - /** returns - * @return list of continuations, - * @return variables bound to default continuation, - * @return optionally, a default continuation - **/ - def getTransition(implicit theOwner: Symbol): (List[(Int,Rep)], Set[Symbol], Option[Rep]) = - (tagIndicesToReps, defaultV, if (haveDefault) Some(defaultsToRep) else None) - - val varMap: List[(Int, List[Symbol])] = - (for ((x, i) <- pats.zip) yield x.stripped match { - case p @ LIT(c: Int) => insertTagIndexPair(c, i) ; Some(c, definedVars(x)) - case p @ LIT(c: Char) => insertTagIndexPair(c.toInt, i) ; Some(c.toInt, definedVars(x)) - case p if isDefaultPattern(p) => insertDefault(i, x.boundVariables) ; None - }) . flatMap(x => x) . reverse - - // lazy - private def bindVars(Tag: Int, orig: Bindings): Bindings = { - def myBindVars(rest:List[(Int,List[Symbol])], bnd: Bindings): Bindings = rest match { - case Nil => bnd - case (Tag,vs)::xs => myBindVars(xs, bnd.add(vs, scrut.sym)) - case (_, vs)::xs => myBindVars(xs, bnd) - } - myBindVars(varMap, orig) - } - - final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = { - val (branches, defaultV, defaultRep) = this.getTransition // tag body pairs - val cases = for ((tag, r) <- branches) yield { - val r2 = rep.make(r.temp, r.row map (x => x rebind bindVars(tag, x.subst))) - - CASE(Literal(tag)) ==> r2.toTree - } - lazy val ndefault = defaultRep map (_.toTree) getOrElse (failTree) - lazy val casesWithDefault = cases ::: List(CASE(WILD(definitions.IntClass.tpe)) ==> ndefault) - - cases match { - case CaseDef(lit,_,body) :: Nil => IF (scrut.id ANY_== lit) THEN body ELSE ndefault - case _ => - val target: Tree = if (scrut.tpe.isChar) scrut.id DOT nme.toInt else scrut.id // chars to ints - target MATCH (casesWithDefault: _*) - } - } - override def toString = { - "MixLiterals {\n pats: %s\n varMap: %s\n}".format( - pats, varMap - ) - } - } - - /** mixture rule for unapply pattern - */ - class MixUnapply(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) - extends RuleApplication(rep) { - lazy val Strip(vs, ua @ UnApply(app @ Apply(fxn, _ :: applyTail), args)) = head.tree - - object sameUnapplyCall { - def sameFunction(fn1: Tree) = fxn.symbol == fn1.symbol && (fxn equalsStructure fn1) - def unapply(t: Tree) = t match { - case UnApply(Apply(fn1, _), args) if sameFunction(fn1) => Some(args) - case _ => None - } - } - - def newVarCapture(pos: Position, tpe: Type)(implicit theOwner: Symbol) = - newVar(pos, tpe, flags = scrut.flags) - - /** returns (unapply-call, success-rep, optional fail-rep*/ - final def getTransition(implicit theOwner: Symbol): Branch[UnapplyCall] = { - val unapplyRes = newVarCapture(ua.pos, app.tpe) - val rhs = Apply(fxn, scrut.id :: applyTail) setType unapplyRes.tpe - val zipped = pats zip rest.row - val nrowsOther = zipped.tail flatMap { - case (Stripped(sameUnapplyCall(_)), _) => Nil - case (pat, r) => List(r insert pat) - } - - def mkTransition(vdefs: List[Tree], ntemps: List[Symbol], nrows: List[Row]) = - Branch( - UnapplyCall(typedValDef(unapplyRes, rhs), vdefs), - mkNewRep(ntemps, rest.temp, nrows), - if (nrowsOther.isEmpty) None else Some(mkFail(nrowsOther)) - ) - - // Second argument is number of dummies to prepend in the default case - def mkNewRows(sameFilter: (List[Tree]) => List[Tree], dum: Int) = - for ((pat @ Strip(vs, p), r) <- zipped) yield p match { - case sameUnapplyCall(args) => r.insert2(sameFilter(args) ::: List(EmptyTree), vs, scrut.sym) - case _ => r insert (getDummies(dum) ::: List(pat)) - } - def mkGet(s: Symbol) = typedValDef(s, fn(ID(unapplyRes), nme.get)) - def mkVar(tpe: Type) = newVarCapture(ua.pos, tpe) - - import definitions.{ getProductArgs, productProj } - // 0 args => Boolean, 1 => Option[T], >1 => Option[? <: ProductN[T1,...,Tn]] - args.length match { - case 0 => - mkTransition(Nil, Nil, mkNewRows((xs) => Nil, 0)) - - case 1 => - val vsym = mkVar(app.tpe typeArgs 0) - val nrows = mkNewRows(xs => List(xs.head), 1) - val vdef = mkGet(vsym) - - mkTransition(List(vdef), List(vsym), nrows) - - case _ => - val uresGet = mkVar(app.tpe typeArgs 0) - val vdefHead = mkGet(uresGet) - val ts = getProductArgs(uresGet.tpe).get - // val ts = analyzer.unapplyTypeListFromReturnType(uresGet.tpe) - val nrows = mkNewRows(identity, ts.size) - - val (vdefs: List[Tree], vsyms: List[Symbol]) = List.unzip( - for ((vtpe, i) <- ts.zip((1 to ts.size).toList)) yield { - val vchild = mkVar(vtpe) - val accSym = productProj(uresGet, i) - val rhs = typer typed fn(ID(uresGet), accSym) - - (typedValDef(vchild, rhs), vchild) - }) - - mkTransition(vdefHead :: vdefs, vsyms, nrows) - } - } /* def getTransition(...) */ - - final def tree(implicit theOwner: Symbol, failTree: Tree) = { - val Branch(UnapplyCall(uacall, vdefs), srep, frep) = this.getTransition - val succ = srep.toTree - val fail = frep map (_.toTree) getOrElse (failTree) - val cond = - if (uacall.symbol.tpe.isBoolean) typer typed ID(uacall.symbol) - else uacall.symbol IS_DEFINED - - typer typed (squeezedBlock( - List(rep handleOuter uacall), - IF(cond) THEN squeezedBlock(vdefs, succ) ELSE fail - )) - } - override def toString = { - "MixUnapply {\n pats: %s\n ua: %s\n}".format( - pats, ua - ) - } - } - - /** handle sequence pattern and ArrayValue (but not star patterns) - */ - sealed class MixSequence(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { - def compareOp = head.tpe member nme.lengthCompare // symbol for length comparison - - final def removeStar(xs: List[Tree]): List[Tree] = - xs.init ::: makeBind(xs.last.boundVariables, WILD(scrut.seqType)) :: Nil - - protected def getSubPatterns(len: Int, x: Tree): Option[List[Tree]] = x match { - case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length == len) => Some(xs ::: List(EmptyTree)) - case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length == len+1) => Some(removeStar(xs)) // (*) - case EmptyTree | Ident(nme.WILDCARD) => Some(getDummies(len+1)) - case _ => None - } - - protected def makeSuccRep(vs: List[Symbol], tail: Symbol, nrows: List[Row])(implicit theOwner: Symbol) = - rep.make(vs ::: tail :: rest.temp, nrows) - - /** True if x must be checked even if y failed to match after passing its length test - * (the conditional supplied by getCond) - */ - protected def mustCheck(x:Tree, y:Tree): Boolean = - isDefaultPattern(x) || ((x, y) match { - case (av @ ArrayValue(_,xs), bv @ ArrayValue(_,ys)) => - // if they are both right-ignoring, x must be more general if it has fewer literals - bug #889 - if (isRightIgnoring(av) && isRightIgnoring(bv) && xs.length < ys.length) true - // otherwise, x is more general only if it is y plus a star - else isRightIgnoring(av) && !isRightIgnoring(bv) && xs.length == ys.length+1 // see (*) - case _ => - false - }) - - case class TransitionContext(f: TreeFunction2) - - // context (to be used in IF), success and failure Rep - def getTransition(implicit theOwner: Symbol): Branch[TransitionContext] = { - scrut assertIsSubtype head.tpe // scrut.tpe <:< column.head.tpe confirmed by assertion - val av @ ArrayValue(_, xs) = head.tree - val ys = if (isRightIgnoring(av)) xs.init else xs - val vs = ys map (y => newVar(y.stripped.pos, scrut.elemType)) - def scrutineeCopy = scrut.id.duplicate - - lazy val tail = newVar(scrut.pos, scrut.seqType) - lazy val lastBinding = typedValDef(tail, scrutineeCopy DROP ys.size) - def elemAt(i: Int) = typer typed ((scrutineeCopy DOT (scrutineeCopy.tpe member nme.apply))(LIT(i))) - - val bindings = - (vs.zipWithIndex map { case (v,i) => typedValDef(v, elemAt(i)) }) ::: List(lastBinding) - - val (nrows, frows) = List.unzip( - for ((c, row) <- pats zip rest.row) yield getSubPatterns(ys.size, c) match { - case Some(ps) => (Some(row insert ps), if (mustCheck(c, av)) Some(row insert c) else None) - case None => (None, Some(row insert c)) - }) - - val succ = makeSuccRep(vs, tail, nrows.flatMap(x => x)) - val fail = mkFail(frows flatMap (x => x)) - def context = (thenp: Tree, elsep: Tree) => - IF (getPrecondition(scrutineeCopy, xs.length)) THEN squeezedBlock(bindings, thenp) ELSE elsep - - Branch(TransitionContext(context), succ, Some(fail)) - } - - protected def lengthCheck(tree: Tree, len: Int, op: TreeFunction2) = - typer typed op((tree.duplicate DOT compareOp)(LIT(len)), ZERO) - - // precondition for matching: sequence is exactly length of arg - protected def getPrecondition(tree: Tree, lengthArg: Int) = - lengthCheck(tree, lengthArg, _ ANY_== _) - - final def tree(implicit theOwner: Symbol, failTree: Tree) = { - val Branch(TransitionContext(context), succ, Some(fail)) = this.getTransition - context(succ.toTree, fail.toTree) - } - } - - /** handle sequence pattern and ArrayValue with star patterns - */ - final class MixSequenceStar(pats: Patterns, rest:Rep)(implicit rep:RepFactory) extends MixSequence(pats, rest) { - // in principle, we could optimize more, but variable binding gets complicated (@todo use finite state methods instead) - override def getSubPatterns(minlen:Int, x:Tree) = x match { - case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length == minlen) => // Seq(p1,...,pN) - Some(xs ::: gen.mkNil :: EmptyTree :: Nil) - case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 == minlen) => // Seq(p1,...,pN,_*) - Some( removeStar(xs) ::: EmptyTree :: Nil) - case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 < minlen) => // Seq(p1..,pJ,_*) J < N - Some( getDummies(minlen + 1) ::: x :: Nil) - case EmptyTree | Ident(nme.WILDCARD) => - Some( getDummies(minlen + 1 + 1)) - case _ => - None - - } - - override protected def makeSuccRep(vs:List[Symbol], tail:Symbol, nrows:List[Row])(implicit theOwner: Symbol) = - mkNewRep(vs ::: List(tail), rest.temp, nrows) - - // precondition for matching - sequence is at least length of (arg - 1) - // I believe the "- 1" is to remove the _* term. - override protected def getPrecondition(tree: Tree, lengthArg: Int) = - lengthCheck(tree, lengthArg - 1, _ ANY_>= _) - } - - - // @todo: equals test for same constant - class MixEquals(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { - /** condition (to be used in IF), success and failure Rep */ - final def getTransition(implicit theOwner: Symbol): (Branch[Tree], Symbol) = { - val vlue = (head.tpe: @unchecked) match { - case TypeRef(_,_,List(SingleType(pre,sym))) => REF(pre, sym) - case TypeRef(_,_,List(PseudoType(o))) => o.duplicate - } - assert(vlue.tpe ne null, "value tpe is null") - val vs = head.boundVariables - val nsuccFst = rest.row.head.insert2(List(EmptyTree), vs, scrut.sym) - val failLabel = theOwner.newLabel(scrut.pos, newName(scrut.pos, "failCont%")) // warning, untyped - val sx = rep shortCut failLabel // register shortcut - val nsuccRow = nsuccFst :: Row(getDummies( 1 /* scrutinee */ + rest.temp.length), NoBinding, NoGuard, sx) :: Nil - - // todo: optimize if no guard, and no further tests - val nsucc = mkNewRep(Nil, rest.temp, nsuccRow) - val nfail = mkFail(List.map2(rest.row.tail, pats.tail.ps)(_ insert _)) - - (Branch(typer typed (scrut.id ANY_== vlue), nsucc, Some(nfail)), failLabel) - } - - final def tree(implicit theOwner: Symbol, failTree: Tree) = { - val (Branch(cond, srep, Some(frep)), failLabel) = this.getTransition - val cond2 = typer typed (rep handleOuter cond) - val fail = typer typed frep.toTree - failLabel setInfo MethodType(Nil, fail.tpe) - - typer typed { IF (cond2) THEN srep.toTree ELSE LabelDef(failLabel, Nil, fail) } - } - } - - /** mixture rule for type tests - **/ - class MixTypes(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { - private def subpatterns(p: Tree): List[Tree] = p match { - case Bind(_, p) => subpatterns(p) - case app @ Apply(fn, ps) if app.tpe.isCaseClass && fn.isType => if (pats.isCaseHead) ps else pats.dummies - case Apply(fn, xs) if !xs.isEmpty || fn.isType => abort("strange Apply") - case _ => pats.dummies - } - - // moreSpecific: more specific patterns - // subsumed: more general patterns (subsuming current), row index and subpatterns - // remaining: remaining, row index and pattern - def join[T](xs: List[Option[T]]): List[T] = xs.flatMap(x => x) - val (moreSpecific, subsumed, remaining) : (List[Tree], List[(Int, List[Tree])], List[(Int, Tree)]) = unzip3( - for ((pat @ Stripped(spat), j) <- pats.zip) yield { - def eqHead(tpe: Type) = pats.headType =:= tpe - def alts(yes: Tree, no: Tree) = if (eqHead(pat.tpe)) yes else no - - lazy val isDef = isDefaultPattern(pat) - lazy val cmp: TypeComparison = spat.tpe cmp pats.headType // contains type info about pattern's type vs. head pattern - lazy val dummy = (j, pats.dummies) - lazy val pass = (j, pat) - lazy val subs = (j, subpatterns(pat)) - - import cmp._ // imports xIsaY, etc. - - // each pattern will yield a triple of options corresponding to the three lists, - // which will be flattened down to the values - implicit def mkOpt[T](x: T): Option[T] = Some(x) // limits noise from Some(value) - (spat match { - case LIT(null) if !eqHead(spat.tpe) => (None, None, pass) // special case for constant null - case _ if pats.isObjectTest(pat) => (EmptyTree, dummy, None) // matching an object - case Typed(p @ Stripped(_: UnApply), _) if xIsaY => (p, dummy, None) // <:< is never - case q @ Typed(pp, _) if xIsaY => (alts(pp, q), dummy, None) // never =:= for - // this next line inflicted great suffering upon innocents - // case z: UnApply => (None, None, pass) - // XXX note - while removing the above line fixed the abhorrent "wrong answer" behavior - // illustrated in bug #1697, it then led to "consistency problem in target generation" - // failures with extractors in the first position (see classifyPat.) - case z: UnApply => (EmptyTree, dummy, pass) - case _ if erased.xIsaY || xIsaY && !isDef => (alts(EmptyTree, pat), subs, None) // never =:= for - case _ if erased.yIsaX || yIsaX || isDef => (EmptyTree, dummy, pass) // subsuming (matched *and* remaining pattern) - case _ => (None, None, pass) - }) : (Option[Tree], Option[(Int, List[Tree])], Option[(Int, Tree)]) - } - ) match { case (x,y,z) => (join(x), join(y), join(z)) } - - override def toString = { - "MixTypes(%s: %s) {\n moreSpecific: %s\n subsumed: %s\n remaining: %s\n}".format( - scrut, scrut.tpe, moreSpecific, subsumed, remaining - ) - } - - /** returns casted symbol, success matrix and optionally fail matrix for type test on the top of this column */ - final def getTransition(implicit theOwner: Symbol): Branch[Scrutinee] = { - val casted = scrut casted pats.headType - - // succeeding => transition to translate(subsumed) (taking into account more specific) - val nmatrix = { - val ms = moreSpecific exists (_ != EmptyTree) - val accessorTemps = - if (!pats.isCaseHead) Nil - else casted.accessors map (meth => newVar(scrut.pos, (casted.tpe memberType meth).resultType, scrut.flags)) - val subtestTemps = if (!ms) Nil else List(casted.sym) - val subtests = - if (!ms) subsumed - else moreSpecific.zip(subsumed) map { case (mspat, (j, pats)) => (j, mspat::pats) } - val ntriples = - for ((j, ps) <- subtests ; val Strip(vs, thePat) = pats(j)) yield - (rest row j).insert2(ps, vs, casted.sym) - - rep.make(subtestTemps ::: accessorTemps ::: rest.temp, ntriples) - } - - // fails => transition to translate(remaining) - val nmatrixFail: Option[Rep] = { - val ntriples = for ((j, pat) <- remaining) yield (rest row j) insert pat - if (ntriples.isEmpty) None else Some(mkFail(ntriples)) - } - - Branch(casted, nmatrix, nmatrixFail) - } - - final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = { - val Branch(casted, srep, frep) = this.getTransition - val cond = condition(casted.tpe, scrut) - val succ = srep.toTree - val fail = frep map (_.toTree) getOrElse (failTree) - - // dig out case field accessors that were buried in (***) - val cfa = if (!pats.isCaseHead) Nil else casted.accessors - val caseTemps = srep.temp match { case x :: xs if x == casted.sym => xs ; case x => x } - def needCast = if (casted.sym ne scrut.sym) List(VAL(casted.sym) === (scrut.id AS_ANY casted.tpe)) else Nil - val vdefs = needCast ::: ( - for ((tmp, accessor) <- caseTemps zip cfa) yield - typedValDef(tmp, typer typed fn(casted.id, accessor)) - ) - - typer typed (IF (cond) THEN squeezedBlock(vdefs, succ) ELSE fail) - } - } - - case class Row(pat: List[Tree], subst: Bindings, guard: Guard, bx: Int) { - def insert(h: Tree) = copy(pat = h :: pat) - def insert(hs: List[Tree]) = copy(pat = hs ::: pat) // prepends supplied tree - def replace(hs: List[Tree]) = copy(pat = hs) // substitutes for patterns - def rebind(b: Bindings) = copy(subst = b) // substitutes for bindings - def insert2(hs: List[Tree], vs: Iterable[Symbol], temp: Symbol) = // prepends and prepends - copy(pat = hs ::: pat, subst = subst.add(vs, temp)) - - def insert(p: Pattern) = copy(pat = p.tree :: pat) // transitioning to patterns - - /** returns true if the patterns in this row cover a type symbols "combination" and there is no guard - * @param comb pairs of (column index, type symbol) - */ - def covers(comb: List[Combo]) = { - val results = for (Combo(i, sym) <- comb ; val p = pat(i).stripped) yield p match { - case _ if isDefaultPattern(p) => true - case _: UnApply | _: ArrayValue => true - case _ => p.tpe coversSym sym - } - - guard.isEmpty && (results forall (true ==)) - } - - // returns this row with alternatives expanded - def expand(classifyPat: (Tree, Int) => Tree): List[Row] = { - def isAlternative(p: Tree) = cond(p.stripped) { case Alternative(_) => true } - def getAlternativeBranches(p: Tree): List[Tree] = { - def get_BIND(pctx: TreeFunction1, p:Tree): List[Tree] = p match { - case b @ Bind(n,p) => get_BIND((x: Tree) => pctx(treeCopy.Bind(b, n, x) setType x.tpe), p) - case Alternative(ps) => ps map pctx - } - logAndReturn("get_BIND: ", get_BIND(x => x, p)) - } - - val indexOfAlternative = pat findIndexOf isAlternative - val pats: List[Tree] = List.map2(pat, pat.indices.toList)(classifyPat) - lazy val (prefix, alts :: suffix) = pats splitAt indexOfAlternative - lazy val alternativeBranches = getAlternativeBranches(alts) map (x => replace(prefix ::: x :: suffix)) - - if (indexOfAlternative == -1) List(replace(pats)) else alternativeBranches - } - override def toString() = { - val patStr = pat.mkString - val others = List(subst, guard) map (_.toString) filter (_ != "") - val otherStr = if (others.isEmpty) "" else " // " + others.mkString(" ") - - "Row(%d) %s%s".format(bx, patStr, otherStr) - } - } - import collection.mutable.HashMap - class RepFactory(val handleOuter: TreeFunction1, val typer: Typer) { + class MatchMatrix(context: MatchMatrixContext, failTree: Tree) { + import context._ + var vss: List[List[Symbol]] = _ val labels: HashMap[Int, Symbol] = new HashMap var targets: List[Tree] = _ var reached: BitSet = _ var shortCuts: List[Symbol] = _ - final def make(temp: List[Symbol], row:List[Row], targets: List[Tree], vss: List[List[Symbol]])(implicit theOwner: Symbol): Rep = { + final def make(temp: List[Symbol], row:List[Row], targets: List[Tree], vss: List[List[Symbol]]): Rep = { // ensured that labels(i) eq null for all i, cleanup() has to be called after translation this.vss = vss this.labels.clear() @@ -724,7 +142,7 @@ trait ParallelMatching extends ast.TreeDSL { -shortCuts.length } - final def cleanup(tree: Tree)(implicit theOwner: Symbol): Tree = { + final def cleanup(tree: Tree): Tree = { // Extractors which can spot pure true/false expressions // even through the haze of braces abstract class SeeThroughBlocks[T] { @@ -792,7 +210,7 @@ trait ParallelMatching extends ast.TreeDSL { /** first time bx is requested, a LabelDef is returned. next time, a jump. * the function takes care of binding */ - final def requestBody(bx: Int, subst: Bindings)(implicit theOwner: Symbol): Tree = { + final def requestBody(bx: Int, subst: Bindings): Tree = { if (bx < 0) { // is shortcut val jlabel = shortCuts(-bx-1) return Apply(ID(jlabel), Nil) @@ -801,15 +219,14 @@ trait ParallelMatching extends ast.TreeDSL { // might be bound elsewhere val (vsyms, vdefs) : (List[Symbol], List[Tree]) = List.unzip( for (v <- vss(bx) ; substv <- subst(v)) yield - (v, typedValDef(v, substv)(typer)) + (v, typedValDef(v, substv)) ) val body = targets(bx) // @bug: typer is not able to digest a body of type Nothing being assigned result type Unit val tpe = if (body.tpe.isNothing) body.tpe else resultType - // val label = theOwner.newLabel(body.pos, "body%"+bx) setInfo MethodType(vsyms, tpe) val newType = MethodType(vsyms, tpe) - val label = theOwner.newLabel(body.pos, "body%"+bx) setInfo newType + val label = owner.newLabel(body.pos, "body%"+bx) setInfo newType labels(bx) = label return logAndReturn("requestBody(%d) first time: ".format(bx), squeezedBlock(vdefs, ( @@ -848,14 +265,14 @@ trait ParallelMatching extends ast.TreeDSL { cunit.error(body.pos, msg) } - def vds = for (v <- vss(bx) ; substv <- subst(v)) yield typedValDef(v, substv)(typer) + def vds = for (v <- vss(bx) ; substv <- subst(v)) yield typedValDef(v, substv) if (isLabellable(body)) ID(label) APPLY (args) else squeezedBlock(vds, body.duplicate setType resultType) } /** the injection here handles alternatives and unapply type tests */ - final def make(temp: List[Symbol], row1: List[Row])(implicit theOwner: Symbol): Rep = { + final def make(temp: List[Symbol], row1: List[Row]): Rep = { // equals check: call singleType(NoPrefix, o.symbol) `stpe'. Then we could also return // `typeRef(definitions.ScalaPackageClass.tpe, definitions.EqualsPatternClass, List(stpe))' // and force an equality check. However, exhaustivity checking would not work anymore. @@ -954,215 +371,822 @@ trait ParallelMatching extends ast.TreeDSL { ) filterNot (_._2.isEmpty) val strs = toPrint map { case (k, v) => " %s = %s\n".format(k, v) } - if (toPrint.isEmpty) "RepFactory()" - else "RepFactory(\n%s)".format(strs mkString) + if (toPrint.isEmpty) "MatchMatrix()" + else "MatchMatrix(\n%s)".format(strs mkString) + } + + /** + * Encapsulates a symbol being matched on. + * + * sym match { ... } + * + * results in Scrutinee(sym). + * + * Note that we only ever match on Symbols, not Trees: a temporary variable + * is created for any expressions being matched on. + */ + case class Scrutinee(val sym: Symbol) { + import definitions._ + + // presenting a face of our symbol + def tpe = sym.tpe + def pos = sym.pos + def accessors = sym.caseFieldAccessors + def id = ID(sym) // attributed ident + + // tests + def isDefined = sym ne NoSymbol + def isSimple = tpe.isChar || tpe.isInt + + // sequences + def seqType = tpe.widen baseType SeqClass + def elemType = tpe typeArgs 0 // can this happen? if (seqType == NoType) error("...") + + // for propagating "unchecked" to synthetic vars + def flags: List[Long] = List(Flags.TRANS_FLAG) filter (sym hasFlag _) + + def assertIsSubtype(other: Type) = assert(isSubType(tpe, other), "problem "+tpe+" not <: "+other) + def casted(headType: Type) = + if (tpe =:= headType) this + else new Scrutinee(newVar(pos, headType, flags = flags)) } - } - case class Combo(index: Int, sym: Symbol) {} - case class SetCombo(index: Int, syms: Set[Symbol]) {} - case class Branch[T](action: T, succ: Rep, fail: Option[Rep]) - case class UnapplyCall(ua: Tree, args: List[Tree]) + case class Patterns(scrut: Scrutinee, ps: List[Pattern]) { + private lazy val column = ps map (_.tree) + lazy val head = ps.head + lazy val tail = Patterns(scrut, ps.tail) + lazy val last = ps.last + lazy val headType = head.tpeIfHead + lazy val isCaseHead = headType.isCaseClass + lazy val dummies = if (isCaseHead) getDummies(headType.typeSymbol.caseFieldAccessors.length) else Nil + lazy val size = ps.length + + def apply(i: Int): Tree = ps(i).tree + def zip() = column.zipWithIndex + def zip[T](ys: List[T]) = column zip ys + + def isObjectTest(pat: Pattern) = pat isObjectTest headType + def isObjectTest(pat: Tree) = Pattern(pat) isObjectTest headType + // an unapply for which we don't need a type test + def isUnapplyHead = cond (head.tree) { case __UnApply(_,tpe,_) => scrut.tpe <:< tpe } + + def isSimpleSwitch: Boolean = + scrut.isSimple && ps.init.forall(_.isSimpleSwitchCandidate) && + // TODO: This needs to also allow the case that the last is a compatible type pattern. + (last.isSimpleSwitchCandidate || last.isDefault) + + def mkRule(rest: Rep): RuleApplication = + logAndReturn("mkRule: ", head match { + case x if x.isEquals => new MixEquals(this, rest) + case Pattern(x: ArrayValue) => if (x.isRightIgnoring) new MixSequenceStar(this, rest) + else new MixSequence(this, rest) + case _ if isSimpleSwitch => new MixLiterals(this, rest) + case _ if isUnapplyHead => new MixUnapply(this, rest) + case _ => new MixTypes(this, rest) + } + ) + } - case class Rep(val temp: List[Symbol], val row: List[Row]) { - /** converts this to a tree - performs recursive call to translation in the process to get sub reps + /** + * Class encapsulating a guard expression in a pattern match: + * case ... if(tree) => ... */ - final def toTree(implicit theOwner: Symbol, failTree: Tree, rep: RepFactory): Tree = - this.applyRule.tree - - private def toUse(s: Symbol) = - (s hasFlag Flags.MUTABLE) && // indicates that have not yet checked exhaustivity - !(s hasFlag Flags.TRANS_FLAG) && // indicates @unchecked - (s.tpe.typeSymbol hasFlag Flags.SEALED) - - // the superclass is taken if it is not abstract - private def countSuper(s: Symbol): Set[Symbol] = if (s hasFlag Flags.ABSTRACT) emptySymbolSet else Set(s) - private def countSymbol(s: Symbol): Set[Symbol] = candidates(s) ++ countSuper(s) - private def candidates(s: Symbol): Set[Symbol] = - if (s hasFlag Flags.SEALED) s.children flatMap countSymbol - else emptySymbolSet - - private def setsToCombine: List[(Int, Set[Symbol])] = - for ((sym, i) <- temp.zipWithIndex ; if toUse(sym)) yield { - sym resetFlag Flags.MUTABLE - (i, candidates(sym.tpe.typeSymbol)) - } + case class Guard(tree: Tree) { + def isEmpty = tree eq EmptyTree + def duplicate = Guard(tree.duplicate) + override def toString() = if (isEmpty) "" else " // if %s" format tree + } + val NoGuard = Guard(EmptyTree) + + /** "The Mixture Rule" + + {v=pat1, pats1 .. } {q1} + match {.. } {..} + {v=patn, patsn .. } {qn} + + The is the real work-horse of the algorithm. There is some column whose top-most pattern is a + constructor. (Forsimplicity, itisdepicted above asthe left-most column, but anycolumn will do.) + The goal is to build a test state with the variablevand some outgoing arcs (one for each construc- + tor and possibly a default arc). Foreach constructorcin the selected column, its arc is defined as + follows: + + Let {i1,...,ij} be the row-indices of the patterns in the column that matchc. Since the pat- + terns are viewed as regular expressions, this will be the indices of the patterns that either + have the same constructor c, or are wildcards. + + Let {pat1,...,patj} be the patterns in the column corresponding to the indices computed + above, and let nbe the arity of the constructor c, i.e. the number of sub-patterns it has. For + eachpati, its n sub-patterns are extracted; if pat i is a wildcard, nwildcards are produced + instead, each tagged with the right path variable. This results in a pattern matrix with n + columns and j rows. This matrix is then appended to the result of selecting, from each col- + umn in the rest of the original matrix, those rows whose indices are in {i1,...,ij}. Finally + the indices are used to select the corresponding final states that go with these rows. Note + that the order of the indices is significant; selected rows do not change their relative orders. + The arc for the constructor c is now defined as (c’,state), where c’ is cwith any + immediate sub-patterns replaced by their path variables (thus c’ is a simple pattern), and + state is the result of recursively applying match to the new matrix and the new sequence + of final states. + + Finally, the possibility for matching failure is considered. If the set of constructors is exhaustive, + then no more arcs are computed. Otherwise, a default arc(_,state)is the last arc. If there are + any wildcard patterns in the selected column, then their rows are selected from the rest of the + matrix and the final states, and the state is the result of applying match to the new matrix and + states. Otherwise,the error state is used after its reference count has been incremented. + **/ + + /** picks which rewrite rule to apply + * @precondition: column does not contain alternatives (ensured by initRep) + */ + def MixtureRule(scrut: Scrutinee, column: List[Tree], rest: Rep): RuleApplication = + Patterns(scrut, column map Pattern) mkRule rest + + sealed abstract class RuleApplication { + def pats: Patterns + def rest: Rep + lazy val Patterns(scrut, patterns) = pats + lazy val head = pats.head + private lazy val sym = scrut.sym + + def mkFail(xs: List[Row]) = + make(sym :: rest.temp, xs) + def mkNewRep(pre: List[Symbol], post: List[Symbol], rows: List[Row]) = + make(pre ::: sym :: post, rows) + + /** translate outcome of the rule application into code (possible involving recursive application of rewriting) */ + def tree(): Tree + } + + case class ErrorRule() extends RuleApplication { + def pats: Patterns = impossible + def rest: Rep = impossible + final def tree() = failTree + } + + /** {case ... if guard => bx} else {guardedRest} */ + /** VariableRule: The top-most row has only variable (non-constructor) patterns. */ + case class VariableRule(subst: Bindings, guard: Guard, guardedRest: Rep, bx: Int) extends RuleApplication { + def pats: Patterns = impossible + def rest: Rep = guardedRest - // computes cartesian product, keeps indices available - private def combine(colcom: List[(Int, Set[Symbol])]): List[List[Combo]] = colcom match { - case Nil => Nil - case (i, syms) :: Nil => syms.toList map (s => List(Combo(i, s))) - case (i, syms) :: cs => for (s <- syms.toList; rest <- combine(cs)) yield Combo(i, s) :: rest + final def tree(): Tree = { + def body = requestBody(bx, subst) + def guardTest = IF (guard.duplicate.tree) THEN body ELSE guardedRest.toTree + + typer typed( + if (guard.isEmpty) body + else squeezedBlock(subst.targetParams(typer), guardTest) + ) + } } - private def comboCovers(combo: List[Combo]) = row exists (_ covers combo) + /** mixture rule for literals + */ + class MixLiterals(val pats: Patterns, val rest: Rep) extends RuleApplication { + // e.g. (1,1) (1,3) (42,2) for column { case ..1.. => ;; case ..42..=> ;; case ..1.. => } + var defaultV: Set[Symbol] = emptySymbolSet + var defaultIndexSet = new BitSet(pats.size) + + def insertDefault(tag: Int, vs: Traversable[Symbol]) { + defaultIndexSet += tag + defaultV = defaultV ++ vs + } + + def haveDefault: Boolean = !defaultIndexSet.isEmpty + def defaultRows: List[Row] = defaultIndexSet.toList reverseMap grabRow - def init: this.type = { - val allcomb = combine(setsToCombine) - if (allcomb forall comboCovers) return this + protected var tagIndices = IntMap.empty[List[Int]] + protected def grabRow(index: Int): Row = { + val r = rest.row(index) + if (defaultV.isEmpty) r + else r.insert2(Nil, pats(index).boundVariables, scrut.sym) // get vars + } - // if we reach here, patterns were not exhaustive - def mkPad(xs: List[Combo], i: Int): String = xs match { - case Nil => pad("*") - case Combo(j, sym) :: rest => if (j == i) pad(sym.name.toString) else mkPad(rest, i) + /** inserts row indices using in to list of tagIndices */ + protected def tagIndicesToReps() : List[(Int, Rep)] = + tagIndices map { case (k, v) => (k, make(rest.temp, (v reverseMap grabRow) ::: defaultRows)) } toList + + protected def defaultsToRep() = make(rest.temp, defaultRows) + + protected def insertTagIndexPair(tag: Int, index: Int) = + tagIndices = tagIndices.update(tag, index :: tagIndices.getOrElse(tag, Nil)) + + /** returns + * @return list of continuations, + * @return variables bound to default continuation, + * @return optionally, a default continuation + **/ + def getTransition(): (List[(Int,Rep)], Set[Symbol], Option[Rep]) = + (tagIndicesToReps, defaultV, if (haveDefault) Some(defaultsToRep) else None) + + val varMap: List[(Int, List[Symbol])] = + (for ((x, i) <- pats.zip) yield x.stripped match { + case p @ LIT(c: Int) => insertTagIndexPair(c, i) ; Some(c, definedVars(x)) + case p @ LIT(c: Char) => insertTagIndexPair(c.toInt, i) ; Some(c.toInt, definedVars(x)) + case p if isDefaultPattern(p) => insertDefault(i, x.boundVariables) ; None + }) flatMap (x => x) reverse + + // lazy + private def bindVars(Tag: Int, orig: Bindings): Bindings = { + def myBindVars(rest:List[(Int,List[Symbol])], bnd: Bindings): Bindings = rest match { + case Nil => bnd + case (Tag,vs)::xs => myBindVars(xs, bnd.add(vs, scrut.sym)) + case (_, vs)::xs => myBindVars(xs, bnd) + } + myBindVars(varMap, orig) } - def mkMissingStr(open: List[Combo]) = - "missing combination " + temp.indices.map(mkPad(open, _)).mkString + "\n" - val missingCombos = (allcomb filter (open => row.forall(!_.covers(open))) map mkMissingStr).mkString - cunit.warning(temp.head.pos, "match is not exhaustive!\n" + missingCombos) - this + final def tree(): Tree = { + val (branches, defaultV, defaultRep) = this.getTransition // tag body pairs + val cases = for ((tag, r) <- branches) yield { + val r2 = make(r.temp, r.row map (x => x rebind bindVars(tag, x.subst))) + + CASE(Literal(tag)) ==> r2.toTree + } + lazy val ndefault = defaultRep map (_.toTree) getOrElse (failTree) + lazy val casesWithDefault = cases ::: List(CASE(WILD(definitions.IntClass.tpe)) ==> ndefault) + + cases match { + case CaseDef(lit,_,body) :: Nil => IF (scrut.id ANY_== lit) THEN body ELSE ndefault + case _ => + val target: Tree = if (scrut.tpe.isChar) scrut.id DOT nme.toInt else scrut.id // chars to ints + target MATCH (casesWithDefault: _*) + } + } + override def toString = { + "MixLiterals {\n pats: %s\n varMap: %s\n}".format( + pats, varMap + ) + } } - /* internal representation is (temp:List[Symbol], row:List[Row]) - * - * tmp1 tmp_m + /** mixture rule for unapply pattern */ - final def applyRule(implicit theOwner: Symbol, rep: RepFactory): RuleApplication = { - def dropIndex[T](xs: List[T], n: Int) = (xs take n) ::: (xs drop (n + 1)) - row match { - case Nil => ErrorRule() - case Row(pats, subst, g, bx) :: xs => - - var bnd = subst - for (((rpat, t), px) <- pats zip temp zipWithIndex) { - val Strip(vs, p) = rpat - - if (isDefaultPattern(p)) bnd = bnd.add(vs, t) - else { - // Row( _ ... _ p_1i ... p_1n g_m b_m ) :: rows - // cut out column px that contains the non-default pattern - val column = rpat :: (row.tail map (_ pat px)) - val restTemp = dropIndex(temp, px) - val restRows = row map (r => r replace dropIndex(r.pat, px)) - val mr = MixtureRule(new Scrutinee(t), column, rep.make(restTemp, restRows)) - - // TRACE("Mixture rule is = " + mr.getClass) - return mr - } + class MixUnapply(val pats: Patterns, val rest: Rep) extends RuleApplication { + lazy val Strip(vs, ua @ UnApply(app @ Apply(fxn, _ :: applyTail), args)) = head.tree + + object sameUnapplyCall { + def sameFunction(fn1: Tree) = fxn.symbol == fn1.symbol && (fxn equalsStructure fn1) + def unapply(t: Tree) = t match { + case UnApply(Apply(fn1, _), args) if sameFunction(fn1) => Some(args) + case _ => None + } + } + + def newVarCapture(pos: Position, tpe: Type) = + newVar(pos, tpe, flags = scrut.flags) + + /** returns (unapply-call, success-rep, optional fail-rep*/ + final def getTransition(): Branch[UnapplyCall] = { + val unapplyRes = newVarCapture(ua.pos, app.tpe) + val rhs = Apply(fxn, scrut.id :: applyTail) setType unapplyRes.tpe + val zipped = pats zip rest.row + val nrowsOther = zipped.tail flatMap { + case (Stripped(sameUnapplyCall(_)), _) => Nil + case (pat, r) => List(r insert pat) + } + + def mkTransition(vdefs: List[Tree], ntemps: List[Symbol], nrows: List[Row]) = + Branch( + UnapplyCall(typedValDef(unapplyRes, rhs), vdefs), + mkNewRep(ntemps, rest.temp, nrows), + if (nrowsOther.isEmpty) None else Some(mkFail(nrowsOther)) + ) + + // Second argument is number of dummies to prepend in the default case + def mkNewRows(sameFilter: (List[Tree]) => List[Tree], dum: Int) = + for ((pat @ Strip(vs, p), r) <- zipped) yield p match { + case sameUnapplyCall(args) => r.insert2(sameFilter(args) ::: List(EmptyTree), vs, scrut.sym) + case _ => r insert (getDummies(dum) ::: List(pat)) } - // Row( _ ... _ g_1 b_1 ) :: rows it's all default patterns - val rest = if (g.isEmpty) null else rep.make(temp, xs) // TODO - why null? - VariableRule (bnd, g, rest, bx) + def mkGet(s: Symbol) = typedValDef(s, fn(ID(unapplyRes), nme.get)) + def mkVar(tpe: Type) = newVarCapture(ua.pos, tpe) + + import definitions.{ getProductArgs, productProj } + // 0 args => Boolean, 1 => Option[T], >1 => Option[? <: ProductN[T1,...,Tn]] + args.length match { + case 0 => + mkTransition(Nil, Nil, mkNewRows((xs) => Nil, 0)) + + case 1 => + val vsym = mkVar(app.tpe typeArgs 0) + val nrows = mkNewRows(xs => List(xs.head), 1) + val vdef = mkGet(vsym) + + mkTransition(List(vdef), List(vsym), nrows) + + case _ => + val uresGet = mkVar(app.tpe typeArgs 0) + val vdefHead = mkGet(uresGet) + val ts = getProductArgs(uresGet.tpe).get + val nrows = mkNewRows(identity, ts.size) + + val (vdefs: List[Tree], vsyms: List[Symbol]) = List.unzip( + for ((vtpe, i) <- ts.zip((1 to ts.size).toList)) yield { + val vchild = mkVar(vtpe) + val accSym = productProj(uresGet, i) + val rhs = typer typed fn(ID(uresGet), accSym) + + (typedValDef(vchild, rhs), vchild) + }) + + mkTransition(vdefHead :: vdefs, vsyms, nrows) + } + } /* def getTransition(...) */ + + final def tree() = { + val Branch(UnapplyCall(uacall, vdefs), srep, frep) = this.getTransition + val succ = srep.toTree + val fail = frep map (_.toTree) getOrElse (failTree) + val cond = + if (uacall.symbol.tpe.isBoolean) ID(uacall.symbol) + else uacall.symbol IS_DEFINED + + typer typed squeezedBlock( + List(handleOuter(uacall)), + IF (cond) THEN squeezedBlock(vdefs, succ) ELSE fail + ) + } + override def toString = { + "MixUnapply {\n pats: %s\n ua: %s\n}".format( + pats, ua + ) } } - // a fancy toString method for debugging - override def toString() = { - val tempStr = (temp map (t => pad(t.name))).mkString - val underlines = tempStr.replaceAll("""\S""", "-") - val rowStr = ( - for (Row(pat, subst, guard, bx) <- row) yield { - val extraStr: String = guard.toString + subst - "%s %s\n".format(pat map pad mkString, extraStr) + /** handle sequence pattern and ArrayValue (but not star patterns) + */ + sealed class MixSequence(val pats: Patterns, val rest: Rep) extends RuleApplication { + + final def removeStar(xs: List[Tree]): List[Tree] = + xs.init ::: makeBind(xs.last.boundVariables, WILD(scrut.seqType)) :: Nil + + protected def getSubPatterns(len: Int, x: Tree): Option[List[Tree]] = x match { + case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length == len) => Some(xs ::: List(EmptyTree)) + case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length == len+1) => Some(removeStar(xs)) // (*) + case EmptyTree | Ident(nme.WILDCARD) => Some(getDummies(len+1)) + case _ => None + } + + protected def makeSuccRep(vs: List[Symbol], tail: Symbol, nrows: List[Row]) = + make(vs ::: tail :: rest.temp, nrows) + + /** True if x must be checked even if y failed to match after passing its length test + * (the conditional supplied by getPrecondition) + */ + protected def mustCheck(x:Tree, y:Tree): Boolean = + isDefaultPattern(x) || cond((x, y)) { + case (av @ ArrayValue(_, xs), bv @ ArrayValue(_, ys)) if isRightIgnoring(av) => + ( isRightIgnoring(bv) && xs.length < ys.length ) || // see bug #889 + (!isRightIgnoring(bv) && xs.length == ys.length + 1) } - ) mkString - if (temp.size == 0) "Rep(%dx%d)".format(temp.size, row.size) - else "Rep(%dx%d)\n%s\n%s\n%s".format(temp.size, row.size, tempStr, underlines, rowStr) + case class TransitionContext(f: TreeFunction2) + + // context (to be used in IF), success and failure Rep + def getTransition(): Branch[TransitionContext] = { + scrut assertIsSubtype head.tpe // scrut.tpe <:< column.head.tpe confirmed by assertion + val av @ ArrayValue(_, xs) = head.tree + val ys = if (isRightIgnoring(av)) xs.init else xs + val vs = ys map (y => newVar(y.stripped.pos, scrut.elemType)) + def scrutineeCopy = scrut.id.duplicate + + lazy val tail = newVar(scrut.pos, scrut.seqType) + lazy val lastBinding = typedValDef(tail, scrutineeCopy DROP ys.size) + def elemAt(i: Int) = typer typed ((scrutineeCopy DOT (scrutineeCopy.tpe member nme.apply))(LIT(i))) + + val bindings = + (vs.zipWithIndex map { case (v,i) => typedValDef(v, elemAt(i)) }) ::: List(lastBinding) + + val (nrows, frows) = List.unzip( + for ((c, row) <- pats zip rest.row) yield getSubPatterns(ys.size, c) match { + case Some(ps) => (Some(row insert ps), if (mustCheck(c, av)) Some(row insert c) else None) + case None => (None, Some(row insert c)) + }) + + val succ = makeSuccRep(vs, tail, nrows flatMap (x => x)) + val fail = mkFail(frows flatMap (x => x)) + def transition = (thenp: Tree, elsep: Tree) => + IF (getPrecondition(scrutineeCopy, xs.length)) THEN squeezedBlock(bindings, thenp) ELSE elsep + + Branch(TransitionContext(transition), succ, Some(fail)) + } + + protected def lengthCheck(tree: Tree, len: Int, op: TreeFunction2) = { + def compareOp = head.tpe member nme.lengthCompare // symbol for "lengthCompare" method + typer typed op((tree.duplicate DOT compareOp)(LIT(len)), ZERO) + } + + // precondition for matching: sequence is exactly length of arg + protected def getPrecondition(tree: Tree, lengthArg: Int) = + lengthCheck(tree, lengthArg, _ ANY_== _) + + final def tree() = { + val Branch(TransitionContext(transition), succ, Some(fail)) = this.getTransition + transition(succ.toTree, fail.toTree) + } + } + + /** handle sequence pattern and ArrayValue with star patterns + */ + final class MixSequenceStar(pats: Patterns, rest:Rep) extends MixSequence(pats, rest) { + // in principle, we could optimize more, but variable binding gets complicated (@todo use finite state methods instead) + override def getSubPatterns(minlen: Int, x: Tree) = x match { + case av @ ArrayValue(_,xs) if (!isRightIgnoring(av) && xs.length == minlen) => // Seq(p1,...,pN) + Some(xs ::: gen.mkNil :: EmptyTree :: Nil) + case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 == minlen) => // Seq(p1,...,pN,_*) + Some( removeStar(xs) ::: EmptyTree :: Nil) + case av @ ArrayValue(_,xs) if ( isRightIgnoring(av) && xs.length-1 < minlen) => // Seq(p1..,pJ,_*) J < N + Some( getDummies(minlen + 1) ::: x :: Nil) + case EmptyTree | Ident(nme.WILDCARD) => + Some( getDummies(minlen + 1 + 1)) + case _ => + None + + } + + override protected def makeSuccRep(vs: List[Symbol], tail: Symbol, nrows: List[Row]) = + mkNewRep(vs ::: List(tail), rest.temp, nrows) + + // precondition for matching - sequence is at least length of (arg - 1) + // I believe the "- 1" is to remove the _* term. + override protected def getPrecondition(tree: Tree, lengthArg: Int) = + lengthCheck(tree, lengthArg - 1, _ ANY_>= _) } - private val NPAD = 15 + // @todo: equals test for same constant + class MixEquals(val pats: Patterns, val rest: Rep) extends RuleApplication { + /** condition (to be used in IF), success and failure Rep */ + final def getTransition(): (Branch[Tree], Symbol) = { + val vlue = (head.tpe: @unchecked) match { + case TypeRef(_,_,List(SingleType(pre,sym))) => REF(pre, sym) + case TypeRef(_,_,List(PseudoType(o))) => o.duplicate + } + assert(vlue.tpe ne null, "value tpe is null") + val vs = head.boundVariables + val nsuccFst = rest.row.head.insert2(List(EmptyTree), vs, scrut.sym) + val failLabel = owner.newLabel(scrut.pos, newName(scrut.pos, "failCont%")) // warning, untyped + val sx = shortCut(failLabel) // register shortcut + val nsuccRow = nsuccFst :: Row(getDummies( 1 /* scrutinee */ + rest.temp.length), NoBinding, NoGuard, sx) :: Nil + + // todo: optimize if no guard, and no further tests + val nsucc = mkNewRep(Nil, rest.temp, nsuccRow) + val nfail = mkFail(List.map2(rest.row.tail, pats.tail.ps)(_ insert _)) + + (Branch(typer typed (scrut.id ANY_== vlue), nsucc, Some(nfail)), failLabel) + } - private def typeToString(t: Type): String = t match { - case NoType => "x" - case x => x.toString + final def tree() = { + val (Branch(cond, srep, Some(frep)), failLabel) = this.getTransition + val fail = typer typed frep.toTree + failLabel setInfo MethodType(Nil, fail.tpe) + + typer typed( + IF (handleOuter(cond)) THEN srep.toTree ELSE LabelDef(failLabel, Nil, fail) + ) + } } - private def symbolToString(s: Symbol): String = s match { - case x => x.toString + + /** mixture rule for type tests + **/ + class MixTypes(val pats: Patterns, val rest: Rep) extends RuleApplication { + private def subpatterns(p: Tree): List[Tree] = p match { + case Bind(_, p) => subpatterns(p) + case app @ Apply(fn, ps) if app.tpe.isCaseClass && fn.isType => if (pats.isCaseHead) ps else pats.dummies + case Apply(fn, xs) if !xs.isEmpty || fn.isType => abort("strange Apply") + case _ => pats.dummies + } + + // moreSpecific: more specific patterns + // subsumed: more general patterns (subsuming current), row index and subpatterns + // remaining: remaining, row index and pattern + def join[T](xs: List[Option[T]]): List[T] = xs.flatMap(x => x) + val (moreSpecific, subsumed, remaining) : (List[Tree], List[(Int, List[Tree])], List[(Int, Tree)]) = unzip3( + for ((pat @ Stripped(spat), j) <- pats.zip) yield { + def eqHead(tpe: Type) = pats.headType =:= tpe + def alts(yes: Tree, no: Tree) = if (eqHead(pat.tpe)) yes else no + + lazy val isDef = isDefaultPattern(pat) + lazy val cmp: TypeComparison = spat.tpe cmp pats.headType // contains type info about pattern's type vs. head pattern + lazy val dummy = (j, pats.dummies) + lazy val pass = (j, pat) + lazy val subs = (j, subpatterns(pat)) + + import cmp._ // imports xIsaY, etc. + + // each pattern will yield a triple of options corresponding to the three lists, + // which will be flattened down to the values + implicit def mkOpt[T](x: T): Option[T] = Some(x) // limits noise from Some(value) + (spat match { + case LIT(null) if !eqHead(spat.tpe) => (None, None, pass) // special case for constant null + case _ if pats.isObjectTest(pat) => (EmptyTree, dummy, None) // matching an object + case Typed(p @ Stripped(_: UnApply), _) if xIsaY => (p, dummy, None) // <:< is never + case q @ Typed(pp, _) if xIsaY => (alts(pp, q), dummy, None) // never =:= for + // this next line inflicted great suffering upon innocents + // case z: UnApply => (None, None, pass) + // XXX note - while removing the above line fixed the abhorrent "wrong answer" behavior + // illustrated in bug #1697, it then led to "consistency problem in target generation" + // failures with extractors in the first position (see classifyPat.) + case z: UnApply => (EmptyTree, dummy, pass) + case _ if erased.xIsaY || xIsaY && !isDef => (alts(EmptyTree, pat), subs, None) // never =:= for + case _ if erased.yIsaX || yIsaX || isDef => (EmptyTree, dummy, pass) // subsuming (matched *and* remaining pattern) + case _ => (None, None, pass) + }) : (Option[Tree], Option[(Int, List[Tree])], Option[(Int, Tree)]) + } + ) match { case (x,y,z) => (join(x), join(y), join(z)) } + + override def toString = { + "MixTypes(%s: %s) {\n moreSpecific: %s\n subsumed: %s\n remaining: %s\n}".format( + scrut, scrut.tpe, moreSpecific, subsumed, remaining + ) + } + + /** returns casted symbol, success matrix and optionally fail matrix for type test on the top of this column */ + final def getTransition(): Branch[Scrutinee] = { + val casted = scrut casted pats.headType + + // succeeding => transition to translate(subsumed) (taking into account more specific) + val nmatrix = { + val ms = moreSpecific exists (_ != EmptyTree) + val accessorTemps = + if (!pats.isCaseHead) Nil + else casted.accessors map (meth => newVar(scrut.pos, (casted.tpe memberType meth).resultType, scrut.flags)) + val subtestTemps = if (!ms) Nil else List(casted.sym) + val subtests = + if (!ms) subsumed + else moreSpecific.zip(subsumed) map { case (mspat, (j, pats)) => (j, mspat::pats) } + val ntriples = + for ((j, ps) <- subtests ; val Strip(vs, thePat) = pats(j)) yield + (rest row j).insert2(ps, vs, casted.sym) + + make(subtestTemps ::: accessorTemps ::: rest.temp, ntriples) + } + + // fails => transition to translate(remaining) + val nmatrixFail: Option[Rep] = { + val ntriples = for ((j, pat) <- remaining) yield (rest row j) insert pat + if (ntriples.isEmpty) None else Some(mkFail(ntriples)) + } + + Branch(casted, nmatrix, nmatrixFail) + } + + final def tree(): Tree = { + val Branch(casted, srep, frep) = this.getTransition + val cond = condition(casted.tpe, scrut) + val succ = srep.toTree + val fail = frep map (_.toTree) getOrElse (failTree) + + // dig out case field accessors that were buried in (***) + val cfa = if (!pats.isCaseHead) Nil else casted.accessors + val caseTemps = srep.temp match { case x :: xs if x == casted.sym => xs ; case x => x } + def needCast = if (casted.sym ne scrut.sym) List(VAL(casted.sym) === (scrut.id AS_ANY casted.tpe)) else Nil + val vdefs = needCast ::: ( + for ((tmp, accessor) <- caseTemps zip cfa) yield + typedValDef(tmp, typer typed fn(casted.id, accessor)) + ) + + typer typed (IF (cond) THEN squeezedBlock(vdefs, succ) ELSE fail) + } } - private def treeToString(t: Tree): String = t.stripped match { - case EmptyTree => "?" - case WILD() => "_" - case Literal(Constant(x)) => "LIT(%s)".format(x) - case Apply(fn, args) => "%s(%s)".format(treeToString(fn), args map treeToString mkString ",") - case x: TypeTree => "TT(%s)".format(symbolToString(x.symbol)) - case Typed(expr, tpt) => "%s: %s".format(treeToString(expr), treeToString(tpt)) - case x => x.toString + " (" + x.getClass + ")" + + case class Row(pat: List[Tree], subst: Bindings, guard: Guard, bx: Int) { + def insert(h: Tree) = copy(pat = h :: pat) + def insert(hs: List[Tree]) = copy(pat = hs ::: pat) // prepends supplied tree + def replace(hs: List[Tree]) = copy(pat = hs) // substitutes for patterns + def rebind(b: Bindings) = copy(subst = b) // substitutes for bindings + def insert2(hs: List[Tree], vs: Iterable[Symbol], temp: Symbol) = // prepends and prepends + copy(pat = hs ::: pat, subst = subst.add(vs, temp)) + + def insert(p: Pattern) = copy(pat = p.tree :: pat) // transitioning to patterns + + /** returns true if the patterns in this row cover a type symbols "combination" and there is no guard + * @param comb pairs of (column index, type symbol) + */ + def covers(comb: List[Combo]) = { + val results = for (Combo(i, sym) <- comb ; val p = pat(i).stripped) yield p match { + case _ if isDefaultPattern(p) => true + case _: UnApply | _: ArrayValue => true + case _ => p.tpe coversSym sym + } + + guard.isEmpty && (results forall (true ==)) + } + + // returns this row with alternatives expanded + def expand(classifyPat: (Tree, Int) => Tree): List[Row] = { + def isAlternative(p: Tree) = cond(p.stripped) { case Alternative(_) => true } + def getAlternativeBranches(p: Tree): List[Tree] = { + def get_BIND(pctx: TreeFunction1, p:Tree): List[Tree] = p match { + case b @ Bind(n,p) => get_BIND((x: Tree) => pctx(treeCopy.Bind(b, n, x) setType x.tpe), p) + case Alternative(ps) => ps map pctx + } + logAndReturn("get_BIND: ", get_BIND(x => x, p)) + } + + val indexOfAlternative = pat findIndexOf isAlternative + val pats: List[Tree] = List.map2(pat, pat.indices.toList)(classifyPat) + lazy val (prefix, alts :: suffix) = pats splitAt indexOfAlternative + lazy val alternativeBranches = getAlternativeBranches(alts) map (x => replace(prefix ::: x :: suffix)) + + if (indexOfAlternative == -1) List(replace(pats)) else alternativeBranches + } + override def toString() = { + val patStr = pat.mkString + val others = List(subst, guard) map (_.toString) filter (_ != "") + val otherStr = if (others.isEmpty) "" else " // " + others.mkString(" ") + + "Row(%d) %s%s".format(bx, patStr, otherStr) + } } + case class Combo(index: Int, sym: Symbol) {} + case class SetCombo(index: Int, syms: Set[Symbol]) {} + case class Branch[T](action: T, succ: Rep, fail: Option[Rep]) + case class UnapplyCall(ua: Tree, args: List[Tree]) + + case class Rep(val temp: List[Symbol], val row: List[Row]) { + /** converts this to a tree - performs recursive call to translation in the process to get sub reps + */ + final def toTree(): Tree = + this.applyRule.tree + + private def toUse(s: Symbol) = + (s hasFlag Flags.MUTABLE) && // indicates that have not yet checked exhaustivity + !(s hasFlag Flags.TRANS_FLAG) && // indicates @unchecked + (s.tpe.typeSymbol hasFlag Flags.SEALED) + + // the superclass is taken if it is not abstract + private def countSuper(s: Symbol): Set[Symbol] = if (s hasFlag Flags.ABSTRACT) emptySymbolSet else Set(s) + private def countSymbol(s: Symbol): Set[Symbol] = candidates(s) ++ countSuper(s) + private def candidates(s: Symbol): Set[Symbol] = + if (s hasFlag Flags.SEALED) s.children flatMap countSymbol + else emptySymbolSet + + private def setsToCombine: List[(Int, Set[Symbol])] = + for ((sym, i) <- temp.zipWithIndex ; if toUse(sym)) yield { + sym resetFlag Flags.MUTABLE + (i, candidates(sym.tpe.typeSymbol)) + } - private def pad(s: Any): String = pad(s match { - case x: Tree => treeToString(x) - // case x: AnyRef => x.toString + " (" + x.getClass + ")" - case x => x.toString - }) - private def pad(s: String): String = "%%%ds" format (NPAD - 1) format s - } + // computes cartesian product, keeps indices available + private def combine(colcom: List[(Int, Set[Symbol])]): List[List[Combo]] = colcom match { + case Nil => Nil + case (i, syms) :: Nil => syms.toList map (s => List(Combo(i, s))) + case (i, syms) :: cs => for (s <- syms.toList; rest <- combine(cs)) yield Combo(i, s) :: rest + } + + private def comboCovers(combo: List[Combo]) = row exists (_ covers combo) - /** creates initial clause matrix - */ - final def initRep(roots: List[Symbol], cases: List[Tree], rep: RepFactory)(implicit theOwner: Symbol) = { - val (rows, targets, vss): (List[Option[Row]], List[Tree], List[List[Symbol]]) = unzip3( - for ((CaseDef(pat, g, b), bx) <- cases.zipWithIndex) yield { // stash away pvars and bodies for later - - def mkRow(ps: List[Tree]) = Some(Row(ps, NoBinding, Guard(g), bx)) - def rowForPat: Option[Row] = pat match { - case _ if roots.length <= 1 => mkRow(List(pat)) - case Apply(fn, pargs) => mkRow(pargs) - case Ident(nme.WILDCARD) => mkRow(getDummies(roots.length)) - case _ => None + def init: this.type = { + val allcomb = combine(setsToCombine) + if (allcomb forall comboCovers) return this + + // if we reach here, patterns were not exhaustive + def mkPad(xs: List[Combo], i: Int): String = xs match { + case Nil => pad("*") + case Combo(j, sym) :: rest => if (j == i) pad(sym.name.toString) else mkPad(rest, i) } + def mkMissingStr(open: List[Combo]) = + "missing combination " + temp.indices.map(mkPad(open, _)).mkString + "\n" - (rowForPat, b, definedVars(pat)) + val missingCombos = (allcomb filter (open => row.forall(!_.covers(open))) map mkMissingStr).mkString + cunit.warning(temp.head.pos, "match is not exhaustive!\n" + missingCombos) + this } - ) - // flatMap the list of options yields the list of values - rep.make(roots, rows.flatMap(x => x), targets, vss) - } + /* internal representation is (temp:List[Symbol], row:List[Row]) + * + * tmp1 tmp_m + */ + final def applyRule(): RuleApplication = { + def dropIndex[T](xs: List[T], n: Int) = (xs take n) ::: (xs drop (n + 1)) + if (row.isEmpty) + return ErrorRule() + + val Row(pats, subst, g, bx) :: xs = row + var bnd = subst + for (((rpat, t), px) <- pats zip temp zipWithIndex) { + val Strip(vs, p) = rpat + + if (isDefaultPattern(p)) bnd = bnd.add(vs, t) + else { + // Row( _ ... _ p_1i ... p_1n g_m b_m ) :: rows + // cut out column px that contains the non-default pattern + val column = rpat :: (row.tail map (_ pat px)) + val restTemp = dropIndex(temp, px) + val restRows = row map (r => r replace dropIndex(r.pat, px)) + val mr = MixtureRule(new Scrutinee(t), column, make(restTemp, restRows)) + + // TRACE("Mixture rule is = " + mr.getClass) + return mr + } + } + // Row( _ ... _ g_1 b_1 ) :: rows it's all default patterns + val rest = if (g.isEmpty) null else make(temp, xs) // TODO - why null? + VariableRule(bnd, g, rest, bx) + } - final def newVar( - pos: Position, - tpe: Type, - flags: List[Long] = Nil, - name: Name = null - )(implicit theOwner: Symbol): Symbol = { - val n: Name = if (name == null) newName(pos, "temp") else name - // careful: pos has special meaning - theOwner.newVariable(pos, n) setInfo tpe setFlag (0L /: flags)(_|_) - } + // a fancy toString method for debugging + override def toString() = { + val tempStr = (temp map (t => pad(t.name))).mkString + val underlines = tempStr.replaceAll("""\S""", "-") + val rowStr = ( + for (Row(pat, subst, guard, bx) <- row) yield { + val extraStr: String = guard.toString + subst + "%s %s\n".format(pat map pad mkString, extraStr) + } + ) mkString - /** returns the condition in "if (cond) k1 else k2" - */ - final def condition(tpe: Type, scrut: Scrutinee)(implicit typer: Typer, theOwner: Symbol, rep: RepFactory): Tree = { - assert(scrut.isDefined) - val cond = rep handleOuter (typer typed condition(tpe, scrut.id)) + if (temp.size == 0) "Rep(%dx%d)".format(temp.size, row.size) + else "Rep(%dx%d)\n%s\n%s\n%s".format(temp.size, row.size, tempStr, underlines, rowStr) + } - if (!needsOuterTest(tpe, scrut.tpe, theOwner)) cond - else addOuterCondition(cond, tpe, scrut.id, rep.handleOuter) - } + private val NPAD = 15 - final def condition(tpe: Type, scrutTree: Tree)(implicit typer: Typer): Tree = { - assert((tpe ne NoType) && (scrutTree.tpe ne NoType)) - def equalsRef = REF(tpe.termSymbol) ANY_== scrutTree - def isInst = scrutTree IS tpe - def isAnyRef(t: Type) = t <:< definitions.AnyRefClass.tpe + private def typeToString(t: Type): String = t match { + case NoType => "x" + case x => x.toString + } + private def symbolToString(s: Symbol): String = s match { + case x => x.toString + } + private def treeToString(t: Tree): String = t.stripped match { + case EmptyTree => "?" + case WILD() => "_" + case Literal(Constant(x)) => "LIT(%s)".format(x) + case Apply(fn, args) => "%s(%s)".format(treeToString(fn), args map treeToString mkString ",") + case x: TypeTree => "TT(%s)".format(symbolToString(x.symbol)) + case Typed(expr, tpt) => "%s: %s".format(treeToString(expr), treeToString(tpt)) + case x => x.toString + " (" + x.getClass + ")" + } + + private def pad(s: Any): String = pad(s match { + case x: Tree => treeToString(x) + // case x: AnyRef => x.toString + " (" + x.getClass + ")" + case x => x.toString + }) + private def pad(s: String): String = "%%%ds" format (NPAD - 1) format s + } + + /** Executes the match algorithm. */ + final def execute(roots: List[Symbol], cases: List[Tree]) = { + val (rows, targets, vss): (List[Option[Row]], List[Tree], List[List[Symbol]]) = unzip3( + for ((CaseDef(pat, g, b), bx) <- cases.zipWithIndex) yield { // stash away pvars and bodies for later + + def mkRow(ps: List[Tree]) = Some(Row(ps, NoBinding, Guard(g), bx)) + def rowForPat: Option[Row] = pat match { + case _ if roots.length <= 1 => mkRow(List(pat)) + case Apply(fn, pargs) => mkRow(pargs) + case Ident(nme.WILDCARD) => mkRow(getDummies(roots.length)) + case _ => None + } - tpe match { - case ct: ConstantType => ct.value match { // constant - case v @ Constant(null) if isAnyRef(scrutTree.tpe) => scrutTree ANY_EQ NULL - case v => scrutTree ANY_== Literal(v) + (rowForPat, b, definedVars(pat)) } - case _: SingletonType => - if (tpe.termSymbol.isModule) equalsRef // object - else typer typed { if (tpe.prefix ne NoPrefix) isInst else equalsRef } - case _ => - if (scrutTree.tpe <:< tpe && isAnyRef(tpe)) typer typed (scrutTree OBJ_!= NULL) - else isInst + ) + + // flatMap the list of options yields the list of values + make(roots, rows.flatMap(x => x), targets, vss) } - } - /** adds a test comparing the dynamic outer to the static outer */ - final def addOuterCondition(cond: Tree, tpe2test: Type, scrut: Tree, handleOuter: Tree=>Tree) = { - val theRef = handleOuter(tpe2test match { - case TypeRef(NoPrefix, _, _) => abort("assertion failed: NoPrefix") - case TypeRef(ThisType(clazz), _, _) => THIS(clazz) - case TypeRef(prefix, _, _) => REF(prefix.prefix, prefix.termSymbol) - }) - - outerAccessor(tpe2test.typeSymbol) match { - case NoSymbol => ifDebug(cunit.warning(scrut.pos, "no outer acc for "+tpe2test.typeSymbol)) ; cond - case outerAcc => cond AND (((scrut AS_ANY tpe2test) DOT outerAcc)() ANY_EQ theRef) + /** returns the condition in "if (cond) k1 else k2" + */ + final def condition(tpe: Type, scrut: Scrutinee): Tree = { + assert(scrut.isDefined) + val cond = handleOuter(condition(tpe, scrut.id)) + + if (!needsOuterTest(tpe, scrut.tpe, owner)) cond + else addOuterCondition(cond, tpe, scrut.id, handleOuter) + } + + final def condition(tpe: Type, scrutTree: Tree): Tree = { + assert((tpe ne NoType) && (scrutTree.tpe ne NoType)) + + def isAnyRef(t: Type) = t <:< definitions.AnyRefClass.tpe + def useEqTest = tpe.termSymbol.isModule || (tpe.prefix eq NoPrefix) + + typer typed (tpe match { + case ct: ConstantType => ct.value match { + case v @ Constant(null) if isAnyRef(scrutTree.tpe) => scrutTree ANY_EQ NULL + case v => scrutTree ANY_== Literal(v) + } + case _: SingletonType if useEqTest => REF(tpe.termSymbol) ANY_== scrutTree + case _ if scrutTree.tpe <:< tpe && isAnyRef(tpe) => scrutTree OBJ_!= NULL + case _ => scrutTree IS tpe + }) + } + + /** adds a test comparing the dynamic outer to the static outer */ + final def addOuterCondition(cond: Tree, tpe2test: Type, scrut: Tree, handleOuter: Tree=>Tree) = { + val theRef = handleOuter(tpe2test match { + case TypeRef(NoPrefix, _, _) => abort("assertion failed: NoPrefix") + case TypeRef(ThisType(clazz), _, _) => THIS(clazz) + case TypeRef(prefix, _, _) => REF(prefix.prefix, prefix.termSymbol) + }) + + outerAccessor(tpe2test.typeSymbol) match { + case NoSymbol => ifDebug(cunit.warning(scrut.pos, "no outer acc for "+tpe2test.typeSymbol)) ; cond + case outerAcc => cond AND (((scrut AS_ANY tpe2test) DOT outerAcc)() ANY_EQ theRef) + } } } } diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala index be92626aef..4eabab920a 100644 --- a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala +++ b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala @@ -105,8 +105,6 @@ trait PatternNodes extends ast.TreeDSL } } - final def DBG(x: => String) = if (settings.debug.value) Console.println(x) - final def getDummies(i: Int): List[Tree] = List.fill(i)(EmptyTree) def makeBind(vs: List[Symbol], pat: Tree): Tree = vs match { diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala index 3fe0f908a9..c4c5cbf047 100644 --- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala +++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala @@ -5,6 +5,26 @@ */ // $Id$ +/** + * Simple pattern types: + * + * 1 Variable x + * 3 Literal 56 + * + * Types which must be decomposed into conditionals and simple types: + * + * 2 Typed x: Int + * 4 Stable Identifier Bob + * 5 Constructor Symbol("abc") + * 6 Tuple (5, 5) + * 7 Extractor List(1, 2) + * 8 Sequence List(1, 2, _*) + * 9 Infix 5 :: xs + * 10 Alternative "foo" | "bar" + * 11 XML -- + * 12 Regular Expression -- + */ + package scala.tools.nsc.matching import util.Position @@ -18,7 +38,7 @@ import scala.util.NameTransformer.decode * @author Burak Emir */ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter { - self: transform.ExplicitOuter with PatternNodes with ParallelMatching with CodeFactory => + self: transform.ExplicitOuter with PatternNodes with ParallelMatching => import global.{ typer => _, _ } import analyzer.Typer; @@ -33,9 +53,95 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter { final val settings_squeeze = settings.Xsqueeze.value == "on" - // check special case Seq(p1,...,pk,_*) - protected def isRightIgnoring(p: ArrayValue): Boolean = - !p.elems.isEmpty && cond(unbind(p.elems.last)) { case Star(q) => isDefaultPattern(q) } + /** Contains data structures which the match algorithm implementation + * requires but which aren't essential to the algorithm itself. + */ + case class MatchMatrixContext( + handleOuter: TreeFunction1, + typer: Typer, + owner: Symbol) + { + def newVar( + pos: Position, + tpe: Type, + flags: List[Long] = Nil, + name: Name = null): Symbol = + { + val n: Name = if (name == null) newName(pos, "temp") else name + // careful: pos has special meaning + owner.newVariable(pos, n) setInfo tpe setFlag (0L /: flags)(_|_) + } + + def typedValDef(x: Symbol, rhs: Tree) = { + val finalRhs = x.tpe match { + case WildcardType => + rhs setType null + x setInfo (typer typed rhs).tpe + rhs + case _ => + typer.typed(rhs, x.tpe) + } + typer typed (VAL(x) === finalRhs) + } + + def squeezedBlock(vds: List[Tree], exp: Tree): Tree = + if (settings_squeeze) Block(Nil, squeezedBlock1(vds, exp)) + else Block(vds, exp) + + private def squeezedBlock1(vds: List[Tree], exp: Tree): Tree = { + class RefTraverser(sym: Symbol) extends Traverser { + var nref, nsafeRef = 0 + override def traverse(tree: Tree) = tree match { + case t: Ident if t.symbol eq sym => + nref += 1 + if (sym.owner == currentOwner) // oldOwner should match currentOwner + nsafeRef += 1 + + case LabelDef(_, args, rhs) => + (args dropWhile(_.symbol ne sym)) match { + case Nil => + case _ => nref += 2 // cannot substitute this one + } + traverse(rhs) + case t if nref > 1 => // abort, no story to tell + case t => + super.traverse(t) + } + } + + class Subst(sym: Symbol, rhs: Tree) extends Transformer { + var stop = false + override def transform(tree: Tree) = tree match { + case t: Ident if t.symbol == sym => + stop = true + rhs + case _ => if (stop) tree else super.transform(tree) + } + } + + lazy val squeezedTail = squeezedBlock(vds.tail, exp) + def default = squeezedTail match { + case Block(vds2, exp2) => Block(vds.head :: vds2, exp2) + case exp2 => Block(vds.head :: Nil, exp2) + } + + if (vds.isEmpty) exp + else vds.head match { + case vd: ValDef => + val sym = vd.symbol + val rt = new RefTraverser(sym) + rt.atOwner (owner) (rt traverse squeezedTail) + + rt.nref match { + case 0 => squeezedTail + case 1 if rt.nsafeRef == 1 => new Subst(sym, vd.rhs) transform squeezedTail + case _ => default + } + case _ => + default + } + } + } /** handles all translation of pattern matching */ @@ -44,12 +150,13 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter { cases: List[CaseDef], doCheckExhaustive: Boolean, owner: Symbol, - handleOuter: Tree => Tree) - (implicit typer: Typer): Tree = + handleOuter: TreeFunction1, + localTyper: Typer): Tree = { - implicit val theOwner = owner - implicit val rep = new RepFactory(handleOuter, typer) - val flags = if (doCheckExhaustive) Nil else List(Flags.TRANS_FLAG) + val flags = if (doCheckExhaustive) Nil else List(Flags.TRANS_FLAG) + val context = MatchMatrixContext(handleOuter, localTyper, owner) + + import context._ def matchError(obj: Tree) = atPos(selector.pos)(THROW(MatchErrorClass, obj)) def caseIsOk(c: CaseDef) = cond(c.pat) { case _: Apply | Ident(nme.WILDCARD) => true } @@ -80,9 +187,9 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter { (List(root), List(vdef), failTree) } - implicit val fail: Tree = theFailTree - val irep = initRep(tmps, cases, rep) - val mch = typer typed irep.toTree + val matrix = new MatchMatrix(context, theFailTree) + val rep = matrix.execute(tmps, cases) + val mch = typer typed rep.toTree var dfatree = typer typed Block(vds, mch) // TRACE("handlePattern(\n tmps = %s\n cases = %s\n rep = %s\n initRep = %s\n)", @@ -91,9 +198,9 @@ trait TransMatcher extends ast.TreeDSL with CompactTreePrinter { // cannot use squeezedBlock because of side-effects, see t275 for ((cs, bx) <- cases.zipWithIndex) - if (!rep.isReached(bx)) cunit.error(cs.body.pos, "unreachable code") + if (!matrix.isReached(bx)) cunit.error(cs.body.pos, "unreachable code") - dfatree = rep cleanup dfatree + dfatree = matrix cleanup dfatree resetTraverser traverse dfatree // TRACE("dfatree(2) = " + toCompactString(dfatree)) dfatree diff --git a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala index a27f6989e1..bd5e71d23c 100644 --- a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala +++ b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala @@ -8,8 +8,8 @@ package scala.tools.nsc.transform import symtab._ import Flags.{ CASE => _, _ } -import scala.collection.mutable.{HashMap, ListBuffer} -import matching.{TransMatcher, PatternNodes, CodeFactory, ParallelMatching} +import scala.collection.mutable.ListBuffer +import matching.{ TransMatcher, PatternNodes, ParallelMatching } /** This class ... * @@ -19,7 +19,6 @@ import matching.{TransMatcher, PatternNodes, CodeFactory, ParallelMatching} abstract class ExplicitOuter extends InfoTransform with TransMatcher with PatternNodes - with CodeFactory with ParallelMatching with TypingTransformers with ast.TreeDSL @@ -460,7 +459,7 @@ abstract class ExplicitOuter extends InfoTransform ExplicitOuter.this.resultType = tree.tpe val t = atPos(tree.pos) { - val t_untyped = handlePattern(nselector, ncases, checkExhaustive, currentOwner, transform)(localTyper) + val t_untyped = handlePattern(nselector, ncases, checkExhaustive, currentOwner, transform, localTyper) /* if @switch annotation is present, verify the resulting tree is a Match */ if (requireSwitch) t_untyped match { case Block(_, Match(_, _)) => // ok -- cgit v1.2.3