From f20f480fca746286135bb0c40a34f992fca992a5 Mon Sep 17 00:00:00 2001 From: David MacIver Date: Thu, 13 Nov 2008 22:14:16 +0000 Subject: Starting on improving the abstraction level of ... Starting on improving the abstraction level of the pattern matcher (code from paul) Still needs a fair bit of work. --- .../scala/tools/nsc/matching/CodeFactory.scala | 8 +- .../scala/tools/nsc/matching/MatchUtil.scala | 26 +- .../tools/nsc/matching/ParallelMatching.scala | 870 +++++++++++---------- .../scala/tools/nsc/matching/PatternNodes.scala | 162 +++- .../scala/tools/nsc/matching/TransMatcher.scala | 10 +- test/files/neg/patmatexhaust.check | 1 + 6 files changed, 606 insertions(+), 471 deletions(-) diff --git a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala index 13fc7f830c..f7a28aa140 100644 --- a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala +++ b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala @@ -96,12 +96,8 @@ trait CodeFactory { final def Equals (left: Tree, right: Tree): Tree = fn(left, nme.EQ, right) final def Eq (left: Tree, right: Tree): Tree = fn(left, nme.eq, right) final def GTE (left: Tree, right: Tree): Tree = fn(left, nme.GE, right) // >= - - final def Not(arg: Tree) = - Select(arg, NOT) - - final def And(left: Tree, right: Tree): Tree = - fn(left, AND, right) + final def And (left: Tree, right: Tree): Tree = fn(left, AND, right) + final def Not (arg: Tree): Tree = Select(arg, NOT) final def ThrowMatchError(pos: Position, obj: Tree) = atPos(pos) { Throw( New(TypeTree(MatchErrorClass.tpe), List(List(obj))) ) diff --git a/src/compiler/scala/tools/nsc/matching/MatchUtil.scala b/src/compiler/scala/tools/nsc/matching/MatchUtil.scala index 529e217cec..12f1108f70 100644 --- a/src/compiler/scala/tools/nsc/matching/MatchUtil.scala +++ b/src/compiler/scala/tools/nsc/matching/MatchUtil.scala @@ -13,16 +13,30 @@ object MatchUtil def impossible: Nothing = abort("this never happens") def abort(msg: String): Nothing = throw new RuntimeException(msg) + // def classifyPatString(pat: Tree) = pat match { + // case _: Alternative => "Alternative" + // case Typed(Strip2(_: UnApply), _) => "Typed" + // case Ident_Or_Empty() => "Ident(_)|EmptyTree" + // case _: Ident => "Ident" + // case _: Select => "Select" + // case UnApply_TypeApply(_, _) => "Unapply(...TypeApply...)" + // case UnApply(_: Apply, _) => "Unapply(Apply())" + // case Apply_Function(_) => "Apply !isCaseClass" + // case Apply_Value(_, _) => "Apply_Value" + // case Apply_CaseClass_NoArgs(_) => "Apply_CaseClass_NoArgs" + // case Apply_CaseClass_WithArgs() => "Apply_CaseClass_WithArgs" + // case _: ArrayValue => "ArrayValue" + // case _ => "Unknown!" + // } + object Implicits { implicit def listPlusOps[T](xs: List[T]) = new ListPlus(xs) } - object Flags { - import symtab.Flags - import symtab.Symbols - - def propagateFlag(from: Symbols#Symbol, to: Symbols#Symbol, flag: Long) = if (from hasFlag flag) to setFlag flag - } + // object Flags { + // import symtab.Flags + // import symtab.Symbols + // } class ListPlus[A](list: List[A]) { /** Returns the list without the element at index n. diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala index 40bc0c6203..0f760aa372 100644 --- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala +++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala @@ -9,11 +9,10 @@ package scala.tools.nsc.matching import util.Position import collection._ -import collection.mutable.BitSet -import collection.immutable.IntMap +import mutable.BitSet +import immutable.IntMap import MatchUtil.ListPlus._ import MatchUtil.Implicits._ -import MatchUtil.Flags._ import MatchUtil._ /** Translation of match expressions. @@ -36,80 +35,178 @@ trait ParallelMatching { import global.{typer => _, _} import analyzer.Typer; import symtab.Flags - - // used as argument to `EqualsPatternClass' - case class PseudoType(o: Tree) extends SimpleTypeProxy { - override def underlying: Type = o.tpe - override def safeToString: String = "PseudoType("+o+")" + import Types._ + import Code.{ fn, Const } + + class Scrutinee(val sym: Symbol) { + import definitions._ + + def mkList(xs: List[Symbol]) = sym :: xs + def mkList(prefix: List[Symbol], suffix: List[Symbol]) = prefix ::: sym :: suffix + def isDefined = sym ne NoSymbol + def accessors = sym.caseFieldAccessors + def id = mkIdent(sym) + def tpe = sym.tpe + def pos = sym.pos + def isChar = tpe.widen.isChar + def isSimple = isChar || tpe.widen.isInt + lazy val sequenceType = tpe.widen.baseType(SeqClass) + lazy val elementType = sequenceType match { + case NoType => Predef.error("arg " + tpe + " not subtype of Seq[A]") + case _ => tpe.typeArgs(0) + } + // 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)) } - /** picks which rewrite rule to apply - * @precondition: column does not contain alternatives (ensured by initRep) - */ - def MixtureRule(scrutinee: Symbol, column: List[Tree], rest: Rep)(implicit rep: RepFactory): RuleApplication = { - - def isSimpleSwitch: Boolean = { - val simpleSwitchCandidate = (tree : Tree) => strip2(tree) match { - case Literal(const : Constant) if isNumeric(const.tag) => - const.tag match { - case FloatTag | DoubleTag | LongTag => false; - case _ => true; - } - case _ => false; - } + case class Pattern(tree: Tree) { + implicit def mkPattern(t: Tree) = Pattern(t) + import definitions._ + lazy val sym = tree.symbol + lazy val tpe = tree.tpe + lazy val symtpe = sym.tpe + lazy val prefix = tpe.prefix + lazy val stripped = strip2 + lazy val tpeIfHead = stripped.tree match { + case p @ (_:Ident | _:Select) => singleType(stripped.prefix, stripped.sym) //should be singleton object + case __UnApply(_,argtpe,_) => argtpe + case _ => tpe + } - ((scrutinee.tpe.widen =:= definitions.IntClass.tpe) || - (scrutinee.tpe.widen =:= definitions.CharClass.tpe)) && - column.init.forall(simpleSwitchCandidate) && { - val last = column.last; - // TODO: This needs to also allow the case that the last is a compatible - // type pattern. - simpleSwitchCandidate(last) || isDefaultPattern(last) + // true if this pattern allows for a simple switch statement to be generated + lazy val isSimpleSwitchCandidate = stripped.tree match { + case Literal(const : Constant) if isNumeric(const.tag) => + const.tag match { + case FloatTag | DoubleTag | LongTag => false + case _ => true } + case _ => false } - // an unapply for which we don't need a type test - def isUnapplyHead(): Boolean = column.head match { - case __UnApply(_,argtpe,_) => scrutinee.tpe <:< argtpe + /** returns if pattern can be considered a no-op test ??for expected type?? */ + final def isDefault: Boolean = tree match { + case Bind(_, t) => t.isDefault + case EmptyTree => true // dummy + case Ident(nme.WILDCARD) => true case _ => false + // -- what about the following? still have to test "ne null" :/ + // case Typed(nme.WILDCARD,_) => pattern.tpe <:< scrut.tpe } - // true if pattern type is direct subtype of scrutinee (can't use just <:< cause have to take variance into account) - def directSubtype(ptpe: Type) = - ptpe.parents.exists(x => (x.typeSymbol eq scrutinee.tpe.typeSymbol) && (x <:< scrutinee.tpe)) - - // true if each pattern type is case and direct subtype of scrutinee - def isFlatCases(col:List[Tree]): Boolean = (col eq Nil) || { - strip2(col.head) match { - case a @ Apply(fn,_) => - isCaseClass(a.tpe) && directSubtype( a.tpe ) && isFlatCases(col.tail) - case t @ Typed(_,tpt) => - isCaseClass(tpt.tpe) && directSubtype( t.tpe ) && isFlatCases(col.tail) - case Ident(nme.WILDCARD) => - isFlatCases(col.tail) // treat col.tail specially? - case p => - false + final def isEquals = tpe match { + case TypeRef(_, sym, _) => sym eq EqualsPatternClass + case _ => false + } + + final def isAlternative: Boolean = tree match { + case Bind(_, t) => t.isAlternative + case _: Alternative => true + case _ => false + } + + final def getAlternativeBranches: List[Tree] = { + def get_BIND(pctx: Tree => Tree, p: Tree): List[Tree] = p match { + case b @ Bind(n, p) => get_BIND((x: Tree) => pctx(copy.Bind(b, n, x) setType x.tpe), p) + case Alternative(ps) => ps map pctx } + get_BIND(x => x, tree) + } + + /** returns all variables that are binding the given pattern + * @param x a pattern + * @return vs variables bound, p pattern proper + */ + final def strip: (immutable.Set[Symbol], Pattern) = tree match { + case b @ Bind(_, t) => val (vs, p) = Pattern(t).strip ; (vs + b.symbol, p) + case _ => (emptySymbolSet, this) + } + final def strip1: Set[Symbol] = strip._1 + final def strip2: Pattern = strip._2 + + final def definedVars: List[Symbol] = { + implicit def listToStream[T](xs: List[T]): Stream[T] = xs.toStream + def definedVars1(x: Tree): Stream[Symbol] = x match { + case Apply(_, args) => definedVars2(args) + case b @ Bind(_,p) => Stream.cons(b.symbol, definedVars1(p)) + case Typed(p,_) => definedVars1(p) // otherwise x @ (_:T) + case UnApply(_,args) => definedVars2(args) + case ArrayValue(_,xs) => definedVars2(xs) + case _ => Nil + } + def definedVars2(args: Stream[Tree]): Stream[Symbol] = args flatMap definedVars1 + + definedVars1(tree).reverse.toList + } + + /** returns true if pattern tests an object */ + final def isObjectTest(head: Type) = + (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 = head.tree match { + case __UnApply(_,argtpe,_) => scrut.tpe <:< argtpe + case _ => false } - column.head match { - case x if isEqualsPattern(x.tpe) => new MixEquals(scrutinee, column, rest); - case (x : ArrayValue) => if (isRightIgnoring(x)) new MixSequenceStar(scrutinee, column, rest) - else new MixSequence(scrutinee, column, rest); - case _ if isSimpleSwitch => new MixLiterals(scrutinee, column, rest) - case _ if isUnapplyHead() => new MixUnapply(scrutinee, column, rest) - case _ => new MixTypes(scrutinee, column, rest) + 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 = 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) } } + case class Guard(tree: Tree) { + def isEmpty = tree eq EmptyTree + def duplicate = Guard(tree.duplicate) + + def mkIf(thenPart: Tree, elsePart: Tree) = If(tree.duplicate, thenPart, elsePart) + } + 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) { - def scrutinee:Symbol - implicit def typer = rep.typer; + def scrut: Scrutinee + implicit def typer = rep.typer // used in MixEquals and MixSequence - final protected def repWithoutHead(col: List[Tree],rest: Rep)(implicit theOwner: Symbol): Rep = { - val nfailrow = List.map2(col.tail, rest.row.tail)((p, r) => r.insert(p)) - rep.make(scrutinee::rest.temp, nfailrow) + final protected def repWithoutHead(pats: Patterns, rest: Rep)(implicit theOwner: Symbol): Rep = { + val nfailrow = List.map2(pats.tail.ps, rest.row.tail)((p, r) => r.insert(p)) + rep.make(scrut.mkList(rest.temp), nfailrow) } /** translate outcome of the rule application into code (possible involving recursive application of rewriting) */ @@ -117,56 +214,52 @@ trait ParallelMatching { } case class ErrorRule(implicit rep:RepFactory) extends RuleApplication(rep) { - def scrutinee: Symbol = impossible + def scrut: Scrutinee = impossible final def tree(implicit theOwner: Symbol, failTree: Tree) = failTree } /** {case ... if guard => bx} else {guardedRest} */ - case class VariableRule(subst: Bindings, guard: Tree, guardedRest: Rep, bx: Int)(implicit rep:RepFactory) extends RuleApplication(rep) { - def scrutinee: Symbol = impossible + case class VariableRule(subst: Bindings, guard: Guard, guardedRest: Rep, bx: Int)(implicit rep:RepFactory) extends RuleApplication(rep) { + def scrut: Scrutinee = impossible final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = { val body = typer.typed { rep.requestBody(bx, subst) } - if (guard eq EmptyTree) - return body - val vdefs = subst.targetParams - val typedElse = repToTree(guardedRest) - val typedIf = typer.typed { If(guard.duplicate, body, typedElse) } + lazy val vdefs = subst.targetParams + lazy val typedElse = repToTree(guardedRest) + lazy val typedIf = typer.typed(guard.mkIf(body, typedElse)) - typer.typed { squeezedBlock(vdefs, typedIf) } + if (guard.isEmpty) body + else typer.typed(squeezedBlock(vdefs, typedIf)) } } /** superclass of mixture rules for case classes and literals (both translated to switch on an integer) */ abstract class CaseRuleApplication(rep: RepFactory) extends RuleApplication(rep) { - def column: List[Tree] - def rest: Rep + val pats: Patterns + val rest: Rep - // e.g. (1,1) (1,3) (42,2) for column {case ..1.. => ;; case ..42..=> ;; case ..1.. => } - var defaultV: collection.immutable.Set[Symbol] = emptySymbolSet - var defaultIndexSet = new BitSet(column.length) + // e.g. (1,1) (1,3) (42,2) for column { case ..1.. => ;; case ..42..=> ;; case ..1.. => } + var defaultV: immutable.Set[Symbol] = emptySymbolSet + var defaultIndexSet = new BitSet(pats.size) def insertDefault(tag: Int, vs: Set[Symbol]) { defaultIndexSet += tag defaultV = defaultV ++ vs } - def haveDefault: Boolean = !defaultIndexSet.isEmpty - lazy val defaultRows: List[Row] = defaultIndexSet.toList.reverseMap(grabRow); + def haveDefault: Boolean = !defaultIndexSet.isEmpty + lazy val defaultRows: List[Row] = defaultIndexSet.toList reverseMap grabRow protected var tagIndices = IntMap.empty[List[Int]] - protected def grabTemps: List[Symbol] = rest.temp protected def grabRow(index: Int): Row = { - val r @ Row(_,s,_,_) = rest.row(index) - if (defaultV.isEmpty) r else { - val vs = strip1(column(index)) // get vars - r.insert2(Nil, s.add(vs, scrutinee)) - } + val r = rest.row(index) + if (defaultV.isEmpty) r + else r.insert2(Nil, strip1(pats(index)), 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(grabTemps, v.reverseMap(grabRow) ::: defaultRows)) } toList + 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) @@ -184,63 +277,52 @@ trait ParallelMatching { /** mixture rule for literals */ - class MixLiterals(val scrutinee:Symbol, val column:List[Tree], val rest:Rep)(implicit rep:RepFactory) extends CaseRuleApplication(rep) { - var varMap: List[(Int,List[Symbol])] = Nil + class MixLiterals(val pats: Patterns, val rest:Rep)(implicit rep:RepFactory) extends CaseRuleApplication(rep) { + val Patterns(scrut, patterns) = pats - private def sanity(pos:Position, tag: Int, pvars:List[Symbol]) { - varMap = (tag,pvars)::varMap - } + val varMap: List[(Int, List[Symbol])] = + (for ((x, i) <- pats.zip) yield strip2(x) match { + case p @ Const(c: Int) => insertTagIndexPair(c, i) ; Some(c, definedVars(x)) + case p @ Const(c: Char) => insertTagIndexPair(c.toInt, i) ; Some(c.toInt, definedVars(x)) + case p if isDefaultPattern(p) => insertDefault(i, strip1(x)) ; None + }) . flatMap(x => x) . reverse - //lazy + // 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, scrutinee)) + case (Tag,vs)::xs => myBindVars(xs, bnd.add(vs, scrut.sym)) case (_, vs)::xs => myBindVars(xs, bnd) } myBindVars(varMap, orig) } - for ((x, i) <- column.zipWithIndex) strip(x) match { - case (pvars, p @ Literal(Constant(c:Int))) => sanity(p.pos, c , definedVars(x)); insertTagIndexPair(c,i) - case (pvars, p @ Literal(Constant(c:Char))) => sanity(p.pos, c.toInt, definedVars(x)); insertTagIndexPair(c.toInt,i) - case (pvars, p ) if isDefaultPattern(p) => insertDefault(i,pvars) - } - 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.insert2(Nil, bindVars(tag, x.subst)))) - val t2 = repToTree(r2) - CaseDef(Literal(tag), EmptyTree, t2) + val r2 = rep.make(r.temp, r.row.map(x => x.rebind(bindVars(tag, x.subst)))) + CaseDef(Literal(tag), EmptyTree, repToTree(r2)) } - lazy val ndefault = defaultRep.map(repToTree) getOrElse failTree - lazy val defCase = CaseDef(mk_(definitions.IntClass.tpe), EmptyTree, ndefault) + lazy val casesWithDefault = cases ::: List(CaseDef(mk_(definitions.IntClass.tpe), EmptyTree, ndefault)) cases match { - case CaseDef(lit,_,body) :: Nil => - If(Equals(mkIdent(this.scrutinee),lit), body, ndefault) - case _ if isSameType(this.scrutinee.tpe.widen, definitions.CharClass.tpe) => // coerce chars to ints - Match(Select(mkIdent(this.scrutinee), nme.toInt), cases ::: List(defCase)) - case _ => - Match(mkIdent(this.scrutinee), cases ::: List(defCase)) + case CaseDef(lit,_,body) :: Nil => If(Equals(scrut.id, lit), body, ndefault) + case _ if scrut.isChar => Match(Select(scrut.id, nme.toInt), casesWithDefault) // chars to ints + case _ => Match(scrut.id, casesWithDefault) } } } /** mixture rule for unapply pattern */ - class MixUnapply(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) + class MixUnapply(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { - val (vs, unapp) = strip(column.head) + val Patterns(scrut, patterns) = pats + val Strip(vs, unapp) = pats.head.tree lazy val ua @ UnApply(app @ Apply(fxn, appargs), args) = unapp - def newVarCapture(pos:Position,tpe:Type)(implicit theOwner:Symbol) = { - val v = newVar(pos,tpe) - propagateFlag(scrutinee, v, Flags.TRANS_FLAG) // propagate "unchecked" - v - } + def newVarCapture(pos: Position,tpe: Type)(implicit theOwner:Symbol) = newVar(pos, tpe, scrut.flags) /** returns (unapply-call, success-rep, optional fail-rep*/ final def getTransition(implicit theOwner: Symbol): (Tree, List[Tree], Rep, Option[Rep]) = { @@ -253,33 +335,34 @@ trait ParallelMatching { } } val ures = newVarCapture(ua.pos, app.tpe) - val rhs = Apply(fxn, mkIdent(scrutinee) :: appargs.tail) setType ures.tpe + val rhs = Apply(fxn, scrut.id :: appargs.tail) setType ures.tpe val uacall = typedValDef(ures, rhs) - val zipped = column zip rest.row + val zipped = pats.zip(rest.row) val nrowsOther = zipped.tail flatMap { case (Strip2(sameUnapplyCall(_)), _) => Nil ; case (pat, r) => List(r.insert(pat)) } val nrepFail = if (nrowsOther.isEmpty) None - else Some(rep.make(scrutinee::rest.temp, nrowsOther)) + else Some(rep.make(scrut.mkList(rest.temp), nrowsOther)) def mkTransition(vdefs: List[Tree], ntemps: List[Symbol], nrows: List[Row]) = - (uacall, vdefs, rep.make(ntemps ::: scrutinee :: rest.temp, nrows), nrepFail) + (uacall, vdefs, rep.make(scrut.mkList(ntemps, rest.temp), nrows), nrepFail) - def mkNewRows(sameFilter: (List[Tree]) => List[Tree], defaultTrees: List[Tree]) = + // 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), r.subst.add(vs, scrutinee)) - case _ => r.insert(defaultTrees ::: List(pat)) + case sameUnapplyCall(args) => r.insert2(sameFilter(args) ::: List(EmptyTree), vs, scrut.sym) + case _ => r.insert(getDummies(dum) ::: List(pat)) } args.length match { case 0 => // special case for unapply(), app.tpe is boolean - mkTransition(Nil, Nil, mkNewRows((xs) => Nil, Nil)) + mkTransition(Nil, Nil, mkNewRows((xs) => Nil, 0)) case 1 => // special case for unapply(p), app.tpe is Option[T] val vtpe = app.tpe.typeArgs(0) val vsym = newVarCapture(ua.pos, vtpe) - val nrows = mkNewRows((xs) => List(xs.head), List(EmptyTree)) + val nrows = mkNewRows((xs) => List(xs.head), 1) val vdef = typedValDef(vsym, Get(mkIdent(ures))) mkTransition(List(vdef), List(vsym), nrows) @@ -287,7 +370,7 @@ trait ParallelMatching { val uresGet = newVarCapture(ua.pos, app.tpe.typeArgs(0)) val vdefHead = typedValDef(uresGet, Get(mkIdent(ures))) val ts = definitions.getProductArgs(uresGet.tpe).get - val nrows = mkNewRows(identity, getDummies(ts.size)) + 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 = newVarCapture(ua.pos, vtpe) @@ -305,23 +388,20 @@ trait ParallelMatching { val succ = repToTree(srep) val fail = frep.map(repToTree) getOrElse failTree val cond = - if (uacall.symbol.tpe.typeSymbol eq definitions.BooleanClass) - typer.typed{ mkIdent(uacall.symbol) } - else - nonEmptinessCheck(uacall.symbol) - typer.typed { squeezedBlock(List(rep.handleOuter(uacall)), If(cond,squeezedBlock(vdefs,succ),fail)) } + if (uacall.symbol.tpe.isBoolean) typer.typed(mkIdent(uacall.symbol)) + else nonEmptinessCheck(uacall.symbol) + + typer.typed( squeezedBlock(List(rep.handleOuter(uacall)), If(cond,squeezedBlock(vdefs,succ),fail)) ) } } /** handle sequence pattern and ArrayValue (but not star patterns) */ - sealed class MixSequence(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { - - private val sequenceType = scrutinee.tpe.widen.baseType(definitions.SeqClass) - private val elementType = getElemType_Sequence(scrutinee.tpe) + sealed class MixSequence(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { + val Patterns(scrut, patterns) = pats final def removeStar(xs: List[Tree]): List[Tree] = - xs.init ::: makeBind(strip1(xs.last).toList, mk_(sequenceType)) :: Nil + xs.init ::: makeBind(strip1(xs.last).toList, mk_(scrut.sequenceType)) :: 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)) @@ -330,7 +410,7 @@ trait ParallelMatching { case _ => None } - protected def makeSuccRep(vs:List[Symbol], tail:Symbol, nrows:List[Row])(implicit theOwner: Symbol) = + 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 @@ -348,27 +428,26 @@ trait ParallelMatching { }) // context (to be used in IF), success and failure Rep def getTransition(implicit theOwner: Symbol): (Tree => Tree => Tree, Rep, Rep) = { - assert(isSubType(scrutinee.tpe, column.head.tpe), "problem "+scrutinee.tpe+" not <: "+column.head.tpe) - - val treeAsSeq = mkIdent(scrutinee) // scrutinee.tpe <:< column.head.tpe confirmed by assertion - val av @ ArrayValue(_, xs) = column.head + scrut.assertIsSubtype(pats.head.tpe) + val treeAsSeq = scrut.id // scrut.tpe <:< column.head.tpe confirmed by assertion + val av @ ArrayValue(_, xs) = pats.head.tree val ys = if (isRightIgnoring(av)) xs.init else xs - val vs = ys map(y => newVar(strip2(y).pos, elementType)) + val vs = ys map(y => newVar(strip2(y).pos, scrut.elementType)) - lazy val tail = newVar(scrutinee.pos, sequenceType) - lazy val lastBinding = if (ys.size > 0) seqDrop(treeAsSeq.duplicate, ys.size) else mkIdent(scrutinee) + lazy val tail = newVar(scrut.pos, scrut.sequenceType) + lazy val lastBinding = if (ys.size > 0) seqDrop(treeAsSeq.duplicate, ys.size) else scrut.id val bindings = (for ((v, i) <- vs.zipWithIndex) yield typedValDef(v, seqElement(treeAsSeq.duplicate, i))) ::: List(typedValDef(tail, lastBinding)) - val (nrows, frows)/* : (List[Option[Row]], List[Option[Row]]) */ = List.unzip( - for ((c, row) <- column.zip(rest.row)) yield getSubPatterns(ys.size, c) match { + 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 succRep = makeSuccRep(vs, tail, nrows.flatMap(x => x)) - val failRep = rep.make(scrutinee :: rest.temp, frows.flatMap(x => x)) + val failRep = rep.make(scrut.mkList(rest.temp), frows.flatMap(x => x)) // fixed length val cond = getCond(treeAsSeq, xs.length) @@ -377,7 +456,7 @@ trait ParallelMatching { } // lengthArg is exact length - protected def getCond(tree:Tree, lengthArg:Int) = seqHasLength(tree.duplicate, column.head.tpe, lengthArg) + protected def getCond(tree:Tree, lengthArg:Int) = seqHasLength(tree.duplicate, pats.head.tpe, lengthArg) final def tree(implicit theOwner: Symbol, failTree: Tree) = { val (cx,srep,frep) = this.getTransition @@ -389,7 +468,7 @@ trait ParallelMatching { /** handle sequence pattern and ArrayValue with star patterns */ - final class MixSequenceStar(scrutinee:Symbol, column:List[Tree], rest:Rep)(implicit rep:RepFactory) extends MixSequence(scrutinee,column,rest) { + 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) @@ -406,33 +485,36 @@ trait ParallelMatching { } override protected def makeSuccRep(vs:List[Symbol], tail:Symbol, nrows:List[Row])(implicit theOwner: Symbol) = - rep.make(vs ::: tail :: scrutinee :: rest.temp, nrows) + rep.make(scrut.mkList(vs ::: List(tail), rest.temp), nrows) // lengthArg is minimal length - override protected def getCond(tree:Tree, lengthArg:Int) = seqLongerThan(tree.duplicate, column.head.tpe, lengthArg - 1) + override protected def getCond(tree:Tree, lengthArg:Int) = seqLongerThan(tree.duplicate, pats.head.tpe, lengthArg - 1) } // @todo: equals test for same constant - class MixEquals(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { + class MixEquals(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { + val Patterns(scrut, patterns) = pats + val head = pats.head + /** condition (to be used in IF), success and failure Rep */ final def getTransition(implicit theOwner: Symbol): (Tree, Rep, Symbol, Rep) = { - val vlue = (column.head.tpe: @unchecked) match { + val vlue = (head.tpe: @unchecked) match { case TypeRef(_,_,List(SingleType(pre,sym))) => gen.mkAttributedRef(pre,sym) case TypeRef(_,_,List(PseudoType(o))) => o.duplicate } assert(vlue.tpe ne null, "value tpe is null") - val vs = strip1(column.head) - val nsuccFst = rest.row.head match { case r => r.insert2(List(EmptyTree), r.subst.add(vs, scrutinee)) } - val fLabel = theOwner.newLabel(scrutinee.pos, cunit.fresh.newName(scrutinee.pos, "failCont%")) // warning, untyped + val vs = head.strip1.toList + val nsuccFst = rest.row.head.insert2(List(EmptyTree), vs, scrut.sym) + val fLabel = theOwner.newLabel(scrut.pos, cunit.fresh.newName(scrut.pos, "failCont%")) // warning, untyped val sx = rep.shortCut(fLabel) // register shortcut - val nsuccRow = nsuccFst :: Row(getDummies( 1 /*scrutinee*/ + rest.temp.length), NoBinding, EmptyTree, sx) :: Nil + 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 = rep.make(scrutinee :: rest.temp, nsuccRow) - val nfail = repWithoutHead(column, rest) + val nsucc = rep.make(scrut.mkList(rest.temp), nsuccRow) + val nfail = repWithoutHead(pats, rest) - (typer.typed(Equals(mkIdent(scrutinee), vlue)), nsucc, fLabel, nfail) + (typer.typed(Equals(scrut.id, vlue)), nsucc, fLabel, nfail) } final def tree(implicit theOwner: Symbol, failTree: Tree) = { @@ -447,43 +529,14 @@ trait ParallelMatching { /** mixture rule for type tests **/ - class MixTypes(val scrutinee: Symbol, val column: List[Tree], val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { - private val headPatternType = strip2(column.head) match { - case p @ (_:Ident | _:Select) => singleType(p.symbol.tpe.prefix, p.symbol) //should be singleton object - case __UnApply(_,argtpe,_) => argtpe - case _ => column.head.tpe - } - - private val isCaseHead = isCaseClass(headPatternType) - private val dummies = if (!isCaseHead) Nil else getDummies(headPatternType.typeSymbol.caseFieldAccessors.length) - - private def subpatterns(pat: Tree): List[Tree] = pat match { - case Bind(_,p) => subpatterns(p) - case app @ Apply(fn, pats) if isCaseClass(app.tpe) && fn.isType => if (isCaseHead) pats else dummies - case Apply(fn, xs) => // named constant - assert(xs.isEmpty && !fn.isType, "strange Apply"); dummies - // case _: UnApply => dummies - case _ => dummies - } - - /** an approximation of _tp1 <:< tp2 that ignores _ types. this code is wrong, - * ideally there is a better way to do it, and ideally defined in Types.scala - */ - def subsumes_erased(_tp1:Type, tp2:Type) = { - val tp1 = patternType_wrtEquals(_tp1) - lazy val eqSymbolsNotArray = (tp1.typeSymbol eq tp2.typeSymbol) && (tp1.typeSymbol ne definitions.ArrayClass) - tp1.isInstanceOf[TypeRef] && - tp2.isInstanceOf[TypeRef] && - ((tp1.prefix =:= tp2.prefix) && eqSymbolsNotArray || tp1.parents.exists(_.typeSymbol eq tp2.typeSymbol)) - // rather: tp1.baseTypes.exists...? - } + class MixTypes(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { + val Patterns(scrut, patterns) = pats - /** returns true if pattern tests an object */ - final def objectPattern(pat:Tree): Boolean = { - (pat.symbol ne null) && - (pat.symbol != NoSymbol) && - pat.symbol.tpe.prefix.isStable && - headPatternType =:= singleType(pat.symbol.tpe.prefix, pat.symbol) + 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 @@ -491,94 +544,89 @@ trait ParallelMatching { // 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, j) <- column.zipWithIndex) yield { - val spat = strip2(pat) - val patType = spat.tpe - - // each pattern will yield a triple of options corresponding to the three lists, which will be flattened down to the values - spat match { - case Literal(Constant(null)) if !(headPatternType =:= patType) => // special case for constant null pattern - (None, None, Some((j, pat))) - case _ if objectPattern(pat) => // matching an object - (Some(EmptyTree), Some((j, dummies)), None) - case Typed(p, _) if (strip2(p).isInstanceOf[UnApply] && (patType <:< headPatternType)) => // <:< is never - (Some(p), Some((j, dummies)), None) - case q @ Typed(pp, _) if patternType_wrtEquals(patType) <:< headPatternType => - (Some(if (pat.tpe =:= headPatternType) pp else q), Some((j, dummies)), None) // never =:= for - case z: UnApply => - (None, None, Some((j, pat))) - case qq if subsumes_erased(patType, headPatternType) || (patternType_wrtEquals(patType) <:< headPatternType) && !isDefaultPattern(pat) => - (Some(if (pat.tpe =:= headPatternType) EmptyTree else pat), Some((j, subpatterns(pat))), None) // never =:= for - case _ if subsumes_erased(headPatternType, patType) || (headPatternType <:< patType) || isDefaultPattern(pat) => // never <:< for - (Some(EmptyTree), Some((j, dummies)), Some((j, pat))) // subsuming (matched *and* remaining pattern) - case _ => - (None, None, Some((j, pat))) - } + for ((pat @ Strip2(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 Const(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 @ Strip2(_: UnApply), _) if xIsaY => (p, dummy, None) // <:< is never + case q @ Typed(pp, _) if xIsaY => (alts(pp, q), dummy, None) // never =:= for + case z: UnApply => (None, None, 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("+scrutinee+":"+scrutinee.tpe+") {\n moreSpecific:"+moreSpecific+"\n subsumed:"+subsumed+"\n remaining"+remaining+"\n}" + "MixTypes("+scrut+":"+scrut.tpe+") {\n moreSpecific:"+moreSpecific+"\n subsumed:"+subsumed+"\n remaining"+remaining+"\n}" } /** returns casted symbol, success matrix and optionally fail matrix for type test on the top of this column */ - final def getTransition(implicit theOwner: Symbol): (Symbol, Rep, Option[Rep]) = { - val casted = if (scrutinee.tpe =:= headPatternType) scrutinee else newVar(scrutinee.pos, headPatternType) - propagateFlag(scrutinee, casted, Flags.TRANS_FLAG) + final def getTransition(implicit theOwner: Symbol): (Scrutinee, Rep, Option[Rep]) = { + val casted = scrut.casted(pats.headType) + // succeeding => transition to translate(subsumed) (taking into account more specific) val nmatrix = { - var ntemps = - if (!isCaseHead) Nil - else for (meth <- casted.caseFieldAccessors) yield { - val ctemp = newVar(scrutinee.pos, casted.tpe.memberType(meth).resultType) - propagateFlag(scrutinee, ctemp, Flags.TRANS_FLAG) - ctemp - } + 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 (!moreSpecific.exists(_ != EmptyTree)) subsumed - else { - ntemps = casted :: ntemps - moreSpecific.zip(subsumed) map { case (mspat, (j, pats)) => (j, mspat::pats) } - } - - ntemps = ntemps ::: rest.temp - val ntriples = for ((j, pats) <- subtests) yield { - val (vs, thePat) = strip(column(j)) - val r = rest.row(j) - val nsubst = r.subst.add(vs, casted) - r.insert2(pats, nsubst) + if (!ms) subsumed + else moreSpecific.zip(subsumed) map { case (mspat, (j, pats)) => (j, mspat::pats) } + val ntriples = for ((j, ps) <- subtests) yield { + val (vs, thePat) = strip(pats(j)) + rest.row(j).insert2(ps, vs, casted.sym) } - rep.make(ntemps, ntriples) + rep.make(subtestTemps ::: accessorTemps ::: rest.temp, ntriples) } + // fails => transition to translate(remaining) val nmatrixFail: Option[Rep] = { - val ntemps = scrutinee :: rest.temp + val ntemps = scrut.mkList(rest.temp) val ntriples = for ((j, pat) <- remaining) yield rest.row(j).insert(pat) if (ntriples.isEmpty) None else Some(rep.make(ntemps, ntriples)) } + (casted, nmatrix, nmatrixFail) } final def tree(implicit theOwner: Symbol, failTree: Tree): Tree = { val (casted, srep, frep) = this.getTransition - val cond = condition(casted.tpe, this.scrutinee) + val cond = condition(casted.tpe, scrut) val succ = repToTree(srep) val fail = frep.map(repToTree) getOrElse failTree // dig out case field accessors that were buried in (***) - val cfa = if (!isCaseHead) Nil else casted.caseFieldAccessors - val caseTemps = (if (!srep.temp.isEmpty && srep.temp.head == casted) srep.temp.tail else srep.temp).zip(cfa) + 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 } - var vdefs = for ((tmp, accessorMethod) <- caseTemps) yield { - val untypedAccess = Code.fn(mkIdent(casted), accessorMethod) + var vdefs = for ((tmp, accessorMethod) <- caseTemps.zip(cfa)) yield { + val untypedAccess = Code.fn(casted.id, accessorMethod) val typedAccess = typer.typed(untypedAccess) typedValDef(tmp, typedAccess) } - if (casted ne this.scrutinee) - vdefs = ValDef(casted, gen.mkAsInstanceOf(mkIdent(this.scrutinee), casted.tpe)) :: vdefs + if (casted.sym ne scrut.sym) + vdefs = ValDef(casted.sym, gen.mkAsInstanceOf(scrut.id, casted.tpe)) :: vdefs - return typer.typed( If(cond, squeezedBlock(vdefs, succ), fail) ) + typer.typed( If(cond, squeezedBlock(vdefs, succ), fail) ) } } @@ -587,12 +635,54 @@ trait ParallelMatching { final def repToTree(r: Rep)(implicit theOwner: Symbol, failTree: Tree, rep: RepFactory): Tree = r.applyRule.tree - case class Row(pat: List[Tree], subst: Bindings, guard: Tree, bx: Int) { - def insert(h: Tree) = Row(h :: pat, subst, guard, bx) // prepends supplied tree - def insert(hs: List[Tree]) = Row(hs ::: pat, subst, guard, bx) - def insert2(hs: List[Tree], b: Bindings) = Row(hs ::: pat, b, guard, bx) // prepends and substitutes - def replace(hs: List[Tree]) = Row(hs, subst, guard, bx) // replaces pattern list + case class Row(pat: List[Tree], subst: Bindings, guard: Guard, bx: Int) { + def insert(h: Tree) = Row(h :: pat, subst, guard, bx) + def insert(hs: List[Tree]) = Row(hs ::: pat, subst, guard, bx) // prepends supplied tree + def replace(hs: List[Tree]) = Row(hs, subst, guard, bx) // substitutes for patterns + def rebind(b: Bindings) = Row(pat, b, guard, bx) // substitutes for bindings + def insert2(hs: List[Tree], vs: Iterable[Symbol], temp: Symbol) = // prepends and prepends + Row(hs ::: pat, subst.add(vs, temp), guard, bx) + + def insert(p: Pattern) = Row(p.tree :: pat, subst, guard, bx) // 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[(Int, Symbol)]) = { + lazy val results = for ((i, sym) <- comb ; val p = strip2(pat(i))) 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): Boolean = p match { + case Bind(_,p) => isAlternative(p) + case Alternative(ps) => true + case _ => false + } + def getAlternativeBranches(p: Tree): List[Tree] = { + def get_BIND(pctx:Tree => Tree, p:Tree): List[Tree] = p match { + case b @ Bind(n,p) => get_BIND((x: Tree) => pctx(copy.Bind(b, n, x) setType x.tpe), p) + case Alternative(ps) => ps map pctx + } + get_BIND(x => x, p) + } + + val indexOfAlternative = pat findIndexOf isAlternative + val pats: List[Tree] = List.map2(pat, pat.indices)(classifyPat) + lazy val (prefix, alts :: suffix) = pats.splitAt(indexOfAlternative) + lazy val alternativeBranches = getAlternativeBranches(alts) map { p => replace(prefix ::: p :: suffix) } + + if (indexOfAlternative == -1) List(replace(pats)) else alternativeBranches + } } + case class Columns(cols: Column*) + case class Column(pat: Tree, index: Int) class RepFactory(val handleOuter: Tree => Tree)(implicit val typer : Typer) { var vss: List[List[Symbol]] = _ @@ -624,7 +714,7 @@ trait ParallelMatching { if (bx >= 0 && !isReachedTwice(bx)) squeezedBlock(vdefs,body) else blck - case If(cond, Literal(Constant(true)), Literal(Constant(false))) => + case If(cond, Const(true), Const(false)) => super.transform(cond) case If(cond1, If(cond2, thenp, elsep1), elsep2) if (elsep1 equalsStructure elsep2) => super.transform(If(And(cond1,cond2), thenp, elsep1)) @@ -668,13 +758,15 @@ trait ParallelMatching { 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.typeSymbol eq definitions.NothingClass) body.tpe else resultType + val tpe = if (body.tpe.isNothing) body.tpe else resultType val label = theOwner.newLabel(body.pos, "body%"+bx) setInfo MethodType(argts, tpe) + // TODO - newLabel doesn't get a fresh name, is that okay? or should it be more like this: + // val label = theOwner.newLabel(body.pos, cunit.fresh.newName(body.pos, "body%"+bx)) setInfo MethodType(argts, tpe) labels(bx) = label return body match { - case _: Throw | _: Literal => squeezedBlock(vdefs, body.duplicate setType tpe) - case _ => squeezedBlock(vdefs.reverse, LabelDef(label, vsyms, body setType tpe)) + case _: Throw | _: Literal => squeezedBlock(vdefs, body.duplicate setType tpe) + case _ => squeezedBlock(vdefs.reverse, LabelDef(label, vsyms, body setType tpe)) } } @@ -707,113 +799,61 @@ trait ParallelMatching { /** the injection here handles alternatives and unapply type tests */ final def make(temp: List[Symbol], row1: List[Row])(implicit theOwner: Symbol): Rep = { - var unchanged: Boolean = true // 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. // so first, extend exhaustivity check to equalspattern def sType(o: Tree) = singleType(o.tpe.prefix, o.symbol) - def equalsCheck(o: Tree) =if (o.symbol.isValue) singleType(NoPrefix, o.symbol) else sType(o) - - def classifyPat(opat: Tree, j: Int): Tree = { - val (vs, strippedPat) = strip(opat) match { case (vset, pat) => (vset.toList, pat) } - - (strippedPat: @unchecked) match { - case p @ Alternative(ps) => - DBG("Alternative") ; opat - case typat @ Typed(p @ Strip2(_: UnApply), tpt) => - DBG("Typed") - if (temp(j).tpe <:< tpt.tpe) makeBind(vs, p) else opat - - case Ident(nme.WILDCARD) | EmptyTree | _:Literal | _:Typed => - DBG("Ident(_)|EmptyTree") ; opat - case o @ Ident(n) => // n != nme.WILDCARD - DBG("Ident") - val tpe = equalsCheck(o) - makeBind(vs, Typed(mk_(tpe), TypeTree(tpe)) setType tpe) - - case o @ Select(stor,_) => - DBG("Select") - val stpe = equalsCheck(o) - makeBind(vs, Typed(mk_(stpe), TypeTree(stpe)) setType stpe) - - case UnApply(Apply(TypeApply(sel @ Select(stor, nme.unapplySeq), List(tptArg)),_),ArrayValue(_,xs)::Nil) - if (stor.symbol eq definitions.ListModule) => - DBG("Unapply(...TypeApply...)") - // @pre: is not right-ignoring (no star pattern) - // no exhaustivity check, please - temp(j) setFlag Flags.TRANS_FLAG - val listType = typeRef(mkThisType(definitions.ScalaPackage), definitions.ListClass, List(tptArg.tpe)) - makeBind(vs, normalizedListPattern(xs, tptArg.tpe)) - - // @todo: rewrite, using __UnApply instead of UnApply like so: - // case ua @ __UnApply(_,argtpe,_) => - // val ua = prepat - // val npat = (if (temp(j).tpe <:< argtpe) ua else Typed(ua,TypeTree(argtpe)).setType(argtpe)) - // pats = (makeBind(vs, npat) setType argtpe)::pats - case ua @ UnApply(Apply(fn, _), _) => - DBG("Unapply(Apply())") - val MethodType(List(argtpe, _*), _) = fn.tpe - val npat = if (temp(j).tpe <:< argtpe) ua else Typed(ua, TypeTree(argtpe)) setType argtpe - makeBind(vs, npat) setType argtpe - - case o @ Apply(fn, Nil) if !isCaseClass(o.tpe) || /*see t301*/ !Apply_Value.unapply(o).isEmpty => - DBG("Apply !isCaseClass") - val stpe: Type = fn match { - case _ if o.symbol.isModule || o.tpe.termSymbol.isModule => sType(o) - case Select(path, sym) => path.tpe match { - case t @ ThisType(sym) => singleType(t, o.symbol) - // next two cases: e.g. `case Some(p._2)' in scala.collection.jcl.Map - case _ if path.isInstanceOf[Apply] => PseudoType(o) // outer-matching: test/files/pos/t154.scala - case _ => singleType(sType(path), o.symbol) // old - } - case o: Ident => equalsCheck(o) - } - val ttst = typeRef(NoPrefix, definitions.EqualsPatternClass, List(stpe)) - makeBind(vs, Typed(mk_(ttst), TypeTree(stpe)) setType ttst) - - case Apply_Value(pre, sym) => - DBG("Apply_Value") - val tpe = typeRef(NoPrefix, definitions.EqualsPatternClass, List(singleType(pre, sym))) - makeBind(vs, Typed(EmptyTree, TypeTree(tpe)) setType tpe) - - case Apply_CaseClass_NoArgs(tpe) => // no-args case class pattern - DBG("Apply_CaseClass_NoArgs") - makeBind(vs, Typed(EmptyTree, TypeTree(tpe)) setType tpe) - - case Apply_CaseClass_WithArgs() => // case class pattern with args - DBG("Apply_CaseClass_WithArgs") ; opat - case ArrayValue(_,_) => - DBG("ArrayValue") ; opat + def equalsCheck(o: Tree) = if (o.symbol.isValue) singleType(NoPrefix, o.symbol) else sType(o) + def isModule(o: Tree) = o.symbol.isModule || o.tpe.termSymbol.isModule + def applyType(o: Tree, fn: Tree): Type = fn match { + case _ if isModule(o) => sType(o) + case Select(path, sym) => (path, path.tpe) match { + case (_, t: ThisType) => singleType(t, o.symbol) // cases 2/3 are e.g. `case Some(p._2)' in s.c.jcl.Map + case (_: Apply, _) => PseudoType(o) // outer-matching: test/files/pos/t154.scala + case (_, _) => singleType(sType(path), o.symbol) // old } + case o: Ident => equalsCheck(o) } - val row = row1 flatMap { xx => - def isAlternative(p: Tree): Boolean = p match { - case Bind(_,p) => isAlternative(p) - case Alternative(ps) => true - case _ => false - } - def getAlternativeBranches(p: Tree): List[Tree] = { - def get_BIND(pctx:Tree => Tree, p:Tree):List[Tree] = p match { - case b @ Bind(n,p) => get_BIND({ x:Tree => pctx(copy.Bind(b, n, x) setType x.tpe) }, p) - case Alternative(ps) => ps map pctx - } - get_BIND(x => x, p) - } - val Row(opats, subst, g, bx) = xx - val indexOfAlternative = opats.findIndexOf(isAlternative) - if (indexOfAlternative != -1) unchanged = false - val pats: List[Tree] = List.map2(opats, opats.indices)(classifyPat) - - if (indexOfAlternative == -1) List(xx.replace(pats)) - else { - val (prefix, alts :: suffix) = pats.splitAt(indexOfAlternative) - getAlternativeBranches(alts) map { p => xx.replace(prefix ::: p :: suffix) } + def classifyPat(opat: Tree, j: Int): Tree = { + val (vs, strippedPat) = strip(opat) match { case (vset, pat) => (vset.toList, pat) } + // @todo: rewrite UnApply(Apply(fn, _), _) case, using __UnApply instead of UnApply like so: + // case ua @ __UnApply(_,argtpe,_) => + // val ua = prepat + // val npat = (if (temp(j).tpe <:< argtpe) ua else Typed(ua,TypeTree(argtpe)).setType(argtpe)) + // pats = (makeBind(vs, npat) setType argtpe)::pats + + strippedPat match { + case _: Alternative => opat + case Typed(p @ Strip2(_: UnApply), tpt) => if (temp(j).tpe <:< tpt.tpe) makeBind(vs, p) + else opat + // case Ident_Or_Empty() => opat // this doesn't work - see notes in PatternNode + case Ident(nme.WILDCARD) | EmptyTree => opat + case _: Literal | _: Typed => opat + case o: Ident => mkTypedBind(vs, equalsCheck(o)) // Ident(_) != nme.WILDCARD + case o: Select => mkTypedBind(vs, equalsCheck(o)) + // @pre for UnApply_TypeApply: is not right-ignoring (no star pattern) ; no exhaustivity check + case UnApply_TypeApply(tptArg, xs) => temp(j) setFlag Flags.TRANS_FLAG + makeBind(vs, normalizedListPattern(xs, tptArg.tpe)) + case ua @ UnApply(Apply(fn, _), _) => val MethodType(List(argtpe, _*), _) = fn.tpe + val npat = if (temp(j).tpe <:< argtpe) ua + else Typed(ua, TypeTree(argtpe)) setType argtpe + makeBind(vs, npat) setType argtpe + case o @ Apply_Function(fn) => val stpe = applyType(o, fn) + val ttst = mkEqualsRef(List(stpe)) + makeBind(vs, Typed(mk_(ttst), TypeTree(stpe)) setType ttst) + case Apply_Value(pre, sym) => mkEmptyTreeBind(vs, mkEqualsRef(List(singleType(pre, sym)))) + case Apply_CaseClass_NoArgs(tpe) => mkEmptyTreeBind(vs, tpe) + case Apply_CaseClass_WithArgs() => opat + case _: ArrayValue => opat + case x => throw new Exception("Unexpected pattern: " + x.getClass + " => " + x) } } - if (unchanged) Rep(temp, row).init else make(temp, row) // recursive call + val row = row1 flatMap { _.expand(classifyPat) } + if (row.length != row1.length) make(temp, row) // recursive call if any change + else Rep(temp, row).init } } @@ -832,7 +872,7 @@ trait ParallelMatching { else emptySymbolSet } (i, candidates(sym.tpe.typeSymbol)) - } // .reverse ? XXX + } // computes cartesian product, keeps indices available private def combine(colcom: List[(Int, Set[Symbol])]): List[List[(Int, Symbol)]] = colcom match { @@ -841,48 +881,26 @@ trait ParallelMatching { case (i,syms)::cs => for (s <- syms.toList; rest <- combine(cs)) yield (i,s) :: rest } - /** returns true if pattern vector pats covers a type symbols "combination" - * @param pats pattern vector - * @param comb pairs of (column index, type symbol) - */ - private def covers(pats: List[Tree], comb: List[(Int, Symbol)]) = { - val results = for ((i, sym) <- comb ; val p = strip2(pats(i))) yield p match { - case _ if isDefaultPattern(p) => true - case _: UnApply | _: ArrayValue => true - case _ => - val ptpe = patternType_wrtEquals(p.tpe) - val symtpe = - if ((sym hasFlag Flags.MODULE) && (sym.linkedModuleOfClass ne NoSymbol)) - singleType(sym.tpe.prefix, sym.linkedModuleOfClass) // e.g. None, Nil - else sym.tpe - - (ptpe.typeSymbol == sym) || - (symtpe <:< ptpe) || - (symtpe.parents.exists(_.typeSymbol eq ptpe.typeSymbol)) || // e.g. Some[Int] <: Option[&b] - (ptpe.prefix.memberType(sym) <:< ptpe) // outer, see combinator.lexical.Scanner - } - results.forall(_ == true) - } - - private def comboCovers(combo: List[(Int, Symbol)]) = row exists { r => (r.guard eq EmptyTree) && covers(r.pat, combo) } + private def comboCovers(combo: List[(Int, Symbol)]) = row exists { r => r.covers(combo) } def init: this.type = { - combine(setsToCombine) match { - case allcomb if (!(allcomb forall comboCovers)) => // not exhaustive - def mkMissingStr(xs: List[(Int, Symbol)], i: Int) = xs.find(_._1 == i) match { - case None => pad("*") - case Some(pair) => pad(pair._2.name.toString) - } + val allcomb = combine(setsToCombine) + if (allcomb forall comboCovers) return this - val missingCombos = - (for (open <- allcomb ; if row.forall(r => !covers(r.pat, open))) yield - "missing combination " + - (for (i <- 0 until temp.length) yield - mkMissingStr(open, i)).mkString + "\n").mkString - - cunit.warning(temp.head.pos, "match is not exhaustive!\n" + missingCombos) - case _ => + // if we reach here, patterns were not exhaustive + def mkPad(xs: List[(Int, Symbol)], i: Int): String = xs match { + case Nil => pad("*") + case (j, sym) :: rest => if (j == i) pad(sym.name.toString) else mkPad(rest, i) } + def mkMissingStr(open: List[(Int, Symbol)]) = + "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 } @@ -891,9 +909,8 @@ trait ParallelMatching { * tmp1 tmp_m */ final def applyRule(implicit theOwner: Symbol, rep: RepFactory): RuleApplication = row match { - case Nil => - ErrorRule() - case Row(pats, subst, g, bx) :: xs => + case Nil => ErrorRule() + case Row(pats, subst, g, bx) :: xs => var bnd = subst for (((rpat, t), px) <- pats.zip(temp).zipWithIndex) { val (vs, p) = strip(rpat) @@ -904,13 +921,13 @@ trait ParallelMatching { val column = rpat :: row.tail.map(_.pat(px)) val restTemp = temp.dropIndex(px) val restRows = row.map(r => r.replace(r.pat.dropIndex(px))) - val mr = MixtureRule(t, column, rep.make(restTemp, restRows)) + val mr = MixtureRule(new Scrutinee(t), column, rep.make(restTemp, restRows)) DBG("\n---\nmixture rule is = " + mr.getClass) return mr } } - //Row( _ ... _ g_1 b_1 ) :: rows it's all default patterns - val rest = if (g eq EmptyTree) null else rep.make(temp, xs) + // 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? DBG("\n---\nmixture rule is = VariableRule") VariableRule (bnd, g, rest, bx) } @@ -934,9 +951,9 @@ trait ParallelMatching { 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 rowForPat: Option[Row] = pat match { - case _ if roots.length <= 1 => Some(Row(List(pat), NoBinding, g, bx)) - case Apply(fn, pargs) => Some(Row(pargs, NoBinding, g, bx)) - case Ident(nme.WILDCARD) => Some(Row(getDummies(roots.length), NoBinding, g, bx)) + case _ if roots.length <= 1 => Some(Row(List(pat), NoBinding, Guard(g), bx)) + case Apply(fn, pargs) => Some(Row(pargs, NoBinding, Guard(g), bx)) + case Ident(nme.WILDCARD) => Some(Row(getDummies(roots.length), NoBinding, Guard(g), bx)) case _ => None } (rowForPat, b, definedVars(pat)) @@ -947,48 +964,50 @@ trait ParallelMatching { rep.make(roots, rows.flatMap(x => x), targets, vss) } - final def newVar(pos: Position, name: Name, tpe: Type)(implicit theOwner: Symbol): Symbol = { + final def newVar(pos: Position, name: Name, tpe: Type, flags: List[Long])(implicit theOwner: Symbol): Symbol = { assert(tpe ne null, "newVar("+name+", null)") val sym = theOwner.newVariable(pos, name) // careful: pos has special meaning sym setInfo tpe - sym + sym setFlag flags.foldLeft(Flags.SYNTHETIC.toLong)(_|_) } + final def newVar(pos: Position, tpe: Type, flags: List[Long])(implicit theOwner: Symbol): Symbol = + newVar(pos, cunit.fresh.newName(pos, "temp"), tpe, flags) + final def newVar(pos: Position, tpe: Type)(implicit theOwner: Symbol): Symbol = - newVar(pos, cunit.fresh.newName(pos, "temp"), tpe) setFlag Flags.SYNTHETIC + newVar(pos, tpe, Nil) /** returns the condition in "if (cond) k1 else k2" */ - final def condition(tpe: Type, scrut: Symbol)(implicit typer: Typer, theOwner: Symbol, rep: RepFactory): Tree = { - assert(scrut ne NoSymbol) - val cond = rep.handleOuter(typer.typed(condition(tpe, mkIdent(scrut)))) + 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 (!needsOuterTest(tpe, scrut.tpe, theOwner)) cond - else addOuterCondition(cond, tpe, mkIdent(scrut), rep.handleOuter) + else addOuterCondition(cond, tpe, scrut.id, rep.handleOuter) } - final def condition(tpe: Type, scrutineeTree: Tree)(implicit typer : Typer): Tree = { - assert((tpe ne NoType) && (scrutineeTree.tpe ne NoType)) - lazy val equalsRef = Equals(gen.mkAttributedRef(tpe.termSymbol), scrutineeTree) - lazy val isInst = gen.mkIsInstanceOf(scrutineeTree, tpe) - def isAnyRef(t: Type) = t <:< definitions.AnyRefClass.tpe + final def condition(tpe: Type, scrutTree: Tree)(implicit typer : Typer): Tree = { + assert((tpe ne NoType) && (scrutTree.tpe ne NoType)) + lazy val equalsRef = Equals(gen.mkAttributedRef(tpe.termSymbol), scrutTree) + lazy val isInst = gen.mkIsInstanceOf(scrutTree, tpe) tpe match { case _: SingletonType if !tpe.isInstanceOf[ConstantType] => - if (tpe.termSymbol.isModule) equalsRef // object - else if (tpe.prefix ne NoPrefix) typer.typed(isInst) - else typer.typed(equalsRef) - case ct: ConstantType => ct.value match { // constant - case v @ Constant(null) if isAnyRef(scrutineeTree.tpe) => Eq(scrutineeTree, Literal(v)) - case v => Equals(scrutineeTree, Literal(v)) + if (tpe.termSymbol.isModule) equalsRef // object + else if (tpe.prefix ne NoPrefix) typer.typed(isInst) + else typer.typed(equalsRef) + case ct: ConstantType => ct.value match { // constant + case v @ Constant(null) if scrutTree.tpe.isAnyRef => Eq(scrutTree, Literal(v)) + case v => Equals(scrutTree, Literal(v)) } - case _ if scrutineeTree.tpe <:< tpe && isAnyRef(tpe) => NotNull(scrutineeTree) - case _ => gen.mkIsInstanceOf(scrutineeTree, tpe) + case _ if scrutTree.tpe <:< tpe && tpe.isAnyRef => NotNull(scrutTree) + case _ => gen.mkIsInstanceOf(scrutTree, tpe) } } /** adds a test comparing the dynamic outer to the static outer */ - final def addOuterCondition(cond:Tree, tpe2test: Type, scrutinee: Tree, handleOuter: Tree=>Tree) = { + 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), _, _) => gen.mkAttributedThis(clazz) @@ -996,8 +1015,9 @@ trait ParallelMatching { }) outerAccessor(tpe2test.typeSymbol) match { - case NoSymbol => if (settings.debug.value) cunit.warning(scrutinee.pos, "no outer acc for "+tpe2test.typeSymbol) ; cond - case outerAcc => And(cond, Eq(Code.fn(gen.mkAsInstanceOf(scrutinee, tpe2test, true), outerAcc), theRef)) + case NoSymbol => if (settings.debug.value) cunit.warning(scrut.pos, "no outer acc for "+tpe2test.typeSymbol) ; cond + case outerAcc => And(cond, Eq(Code.fn(gen.mkAsInstanceOf(scrut, tpe2test, true), outerAcc), theRef)) } } + } diff --git a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala index 43b8af7da8..0482cfb7e9 100644 --- a/src/compiler/scala/tools/nsc/matching/PatternNodes.scala +++ b/src/compiler/scala/tools/nsc/matching/PatternNodes.scala @@ -11,10 +11,96 @@ import scala.tools.nsc.util.{Position, NoPosition} /** * @author Burak Emir */ -trait PatternNodes { self: transform.ExplicitOuter => - import global.{typer => _, _} - import analyzer.Typer; +trait PatternNodes { + self: transform.ExplicitOuter => + + import global.{ typer => _, _ } + import analyzer.Typer import symtab.Flags + import Types._ + + case class TypeComparison(x: Type, y: Type) { + def xIsaY = x <:< y + def yIsaX = y <:< x + def xEqY = y =:= x + def xIgnY = !xIsaY && !yIsaX && !xEqY + def eqSymbol = cmpSymbols(x, y) + def eqPrefix = x.prefix =:= y.prefix + + private def cmpSymbols(t1: Type, t2: Type) = t1.typeSymbol eq t2.typeSymbol + // true if t2 is a parent of t1. Should this be rather: tpe.baseTypes.exists...? + private def parenthood(t1: Type, t2: Type) = t1.parents.exists(p => cmpSymbols(p, t2)) + // true if t1 is direct subtype of t2 (can't use just <:< cause have to take variance into account) + private def subtypehood(t1: Type, t2: Type) = t1.parents.exists(p => cmpSymbols(p, t2) && p <:< t2) + + def yParentsX = parenthood(x, y) + def xParentsY = parenthood(y, x) + def xExtendsY = subtypehood(x, y) + def yExtendsX = subtypehood(y, x) + + object erased { + import Types._ + /** an approximation of _tp1 <:< tp2 that ignores _ types. this code is wrong, + * ideally there is a better way to do it, and ideally defined in Types.scala + */ + private def cmpErased(t1: Type, t2: Type) = (t1, t2) match { + case (_: TypeRef, _: TypeRef) => (eqPrefix && eqSymbol && !t1.isArray) || parenthood(t1, t2) + case _ => false + } + + def xIsaY = cmpErased(x, y) + def yIsaX = cmpErased(y, x) + } + } + + object Types { + import definitions._ + implicit def enrichType(_tpe: Type): RichType = new RichType(_tpe) + + class RichType(_tpe: Type) { + /* equality checks for named constant patterns like "Foo()" are encoded as "_:[Foo().type]" + * and later compiled to "if(Foo() == scrutinee) ...". This method extracts type information from + * such an encoded type, which is used in optimization. If the argument is not an encoded equals + * test, it is returned as is. + */ + private def tpeWRTEquality(t: Type) = t match { + case TypeRef(_, sym, arg::Nil) if sym eq EqualsPatternClass => arg + case _ => t + } + lazy val tpe = tpeWRTEquality(_tpe) + + // The several different logics in these tests are intentionally grouped here to + // draw attention to them. To the extent that the differences are intentional, + // the thinking behind the distinctions needs to be documented. + def isInt = tpe =:= IntClass.tpe + def isChar = tpe =:= CharClass.tpe + def isAnyRef = tpe <:< AnyRefClass.tpe + def isBoolean = tpe.typeSymbol eq BooleanClass + def isArray = tpe.typeSymbol eq ArrayClass + def isNothing = tpe.typeSymbol eq NothingClass + def isCaseClass = tpe.typeSymbol hasFlag Flags.CASE + + def cmp(other: Type): TypeComparison = TypeComparison(tpe, tpeWRTEquality(other)) + + def coversSym(sym: Symbol) = { + val symtpe = + if ((sym hasFlag Flags.MODULE) && (sym.linkedModuleOfClass ne NoSymbol)) + singleType(sym.tpe.prefix, sym.linkedModuleOfClass) // e.g. None, Nil + else sym.tpe + + (tpe.typeSymbol == sym) || + (symtpe <:< tpe) || + (symtpe.parents.exists(_.typeSymbol eq tpe.typeSymbol)) || // e.g. Some[Int] <: Option[&b] + (tpe.prefix.memberType(sym) <:< tpe) // outer, see combinator.lexical.Scanner + } + } + + // used as argument to `EqualsPatternClass' + case class PseudoType(o: Tree) extends SimpleTypeProxy { + override def underlying: Type = o.tpe + override def safeToString: String = "PseudoType("+o+")" + } + } final def DBG(x: => String) = if (settings.debug.value) Console.println(x) @@ -23,6 +109,14 @@ trait PatternNodes { self: transform.ExplicitOuter => def makeBind(vs:List[Symbol], pat:Tree): Tree = if (vs eq Nil) pat else Bind(vs.head, makeBind(vs.tail, pat)) setType pat.tpe + def mkTypedBind(vs: List[Symbol], tpe: Type) = + makeBind(vs, Typed(mk_(tpe), TypeTree(tpe)) setType tpe) + + def mkEmptyTreeBind(vs: List[Symbol], tpe: Type) = + makeBind(vs, Typed(EmptyTree, TypeTree(tpe)) setType tpe) + + def mkEqualsRef(xs: List[Type]) = typeRef(NoPrefix, definitions.EqualsPatternClass, xs) + def normalizedListPattern(pats:List[Tree], tptArg:Type): Tree = pats match { case Nil => gen.mkNil case (sp @ Strip(_, _: Star)) :: xs => makeBind(definedVars(sp), mk_(sp.tpe)) @@ -39,33 +133,50 @@ trait PatternNodes { self: transform.ExplicitOuter => } object Apply_Value { - def unapply(x:Apply) = if (!x.fun.isType && x.args.isEmpty) Some(x.tpe.prefix, x.symbol) else None + def unapply(x: Apply) = if (!x.fun.isType && x.args.isEmpty) Some(x.tpe.prefix, x.symbol) else None + } + + object Apply_Function { + def isApplyFunction(o: Apply) = !o.tpe.isCaseClass || !Apply_Value.unapply(o).isEmpty /*see t301*/ + def unapply(x: Apply) = if (x.args.isEmpty && isApplyFunction(x)) Some(x.fun) else None } object Apply_CaseClass_NoArgs { - def unapply(x:Apply) = if (x.fun.isType && x.args.isEmpty) Some(x.tpe) else None + def unapply(x: Apply) = if (x.fun.isType && x.args.isEmpty) Some(x.tpe) else None } object Apply_CaseClass_WithArgs { - def unapply(x:Apply) = x.fun.isType + def unapply(x: Apply) = x.fun.isType } - object __UnApply { - def unapply(x: Tree) = x match { - case Strip(vs, UnApply(Apply(fn, _), args)) => - val argtpe = fn.tpe.asInstanceOf[MethodType].paramTypes.head - Some((vs, argtpe, args)) - case _ => None + // TODO - this doesn't work! For some reason this sometimes returns false when encapsulated + // in an object like this, when it returns true if the same logic is applied literally in + // the classifyPat match in ParallelMatching. I couldn't figure out why, and it concerns + // me - if this isn't working maybe other unapply objects aren't working right either. The big + // problem with using unapply and type matching is that if something's amiss, it will simply fail + // silently, with the bug most likely manifesting at some unknown later point. + object Ident_Or_Empty { + def unapply(x: Any) = x match { + case Ident(nme.WILDCARD) | EmptyTree | _: Typed | _: Literal => true + // this returns false, and then a line identical the one above will match + // back in PM.scala. + case _ => false } } - /* equality checks for named constant patterns like "Foo()" are encoded as "_:[Foo().type]" - * and later compiled to "if(Foo() == scrutinee) ...". This method extracts type information from - * such an encoded type, which is used in optimization. If the argument is not an encoded equals - * test, it is returned as is. - */ - def patternType_wrtEquals(pattpe:Type) = pattpe match { - case TypeRef(_, sym, arg::Nil) if sym eq definitions.EqualsPatternClass => arg - case _ => pattpe + object UnApply_TypeApply { + def unapply(x: UnApply) = x match { + case UnApply(Apply(TypeApply(sel @ Select(stor, nme.unapplySeq), List(tptArg)), _), ArrayValue(_, xs)::Nil) + if (stor.symbol eq definitions.ListModule) => Some(tptArg, xs) + case _ => None + } + } + + object __UnApply { + private def paramType(fn: Tree) = fn.tpe match { case m: MethodType => m.paramTypes.head } + def unapply(x: Tree) = x match { + case Strip(vs, UnApply(Apply(fn, _), args)) => Some(vs, paramType(fn), args) + case _ => None + } } /** returns if pattern can be considered a no-op test ??for expected type?? */ @@ -75,7 +186,7 @@ trait PatternNodes { self: transform.ExplicitOuter => case Ident(nme.WILDCARD) => true case _ => false // -- what about the following? still have to test "ne null" :/ -// case Typed(nme.WILDCARD,_) => pattern.tpe <:< scrutinee.tpe +// case Typed(nme.WILDCARD,_) => pattern.tpe <:< scrut.tpe } /** returns all variables that are binding the given pattern @@ -90,16 +201,9 @@ trait PatternNodes { self: transform.ExplicitOuter => final def strip2(x: Tree): Tree = strip(x)._2; object Strip { def unapply(x: Tree): Option[(Set[Symbol], Tree)] = Some(strip(x)) } + object Strip1 { def unapply(x: Tree): Option[Set[Symbol]] = Some(strip1(x)) } object Strip2 { def unapply(x: Tree): Option[Tree] = Some(strip2(x)) } - final def isCaseClass(tpe: Type): Boolean = - tpe.typeSymbol hasFlag Flags.CASE - - final def isEqualsPattern(tpe: Type): Boolean = tpe match { - case TypeRef(_, sym, _) => sym eq definitions.EqualsPatternClass - case _ => false - } - final def definedVars(x: Tree): List[Symbol] = { implicit def listToStream[T](xs: List[T]): Stream[T] = xs.toStream def definedVars1(x: Tree): Stream[Symbol] = x match { diff --git a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala index 2772cb5edb..9e3046e0f5 100644 --- a/src/compiler/scala/tools/nsc/matching/TransMatcher.scala +++ b/src/compiler/scala/tools/nsc/matching/TransMatcher.scala @@ -45,6 +45,7 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with Parall implicit val theOwner = owner implicit val rep = new RepFactory(handleOuter) + val flags = if (doCheckExhaustive) Nil else List(Flags.TRANS_FLAG) def caseIsOk(c: CaseDef) = c match { case CaseDef(_: Apply, _, _) => true @@ -57,8 +58,9 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with Parall val Apply(fn, args) = app val (tmps, vds) = List.unzip( for ((ti, i) <- args.zipWithIndex) yield { - val v = newVar(ti.pos, cunit.fresh.newName(ti.pos, "tp"), selector.tpe.typeArgs(i)) - if (!doCheckExhaustive) v setFlag Flags.TRANS_FLAG + // These type parameter vars were not being set as synthetic. + // Temporarily noted on the off chance it was intentional. + val v = newVar(ti.pos, cunit.fresh.newName(ti.pos, "tp"), selector.tpe.typeArgs(i), flags) (v, typedValDef(v, ti)) } ) @@ -69,9 +71,7 @@ trait TransMatcher { self: transform.ExplicitOuter with PatternNodes with Parall val (tmps, vds, theFailTree) = selector match { case app @ Apply(fn, _) if isTupleType(selector.tpe) && doApply(fn) => processApply(app) case _ => - val root: Symbol = newVar(selector.pos, selector.tpe) - if (!doCheckExhaustive) - root setFlag Flags.TRANS_FLAG + val root: Symbol = newVar(selector.pos, selector.tpe, flags) val vdef: Tree = typer.typed(ValDef(root, selector)) val failTree: Tree = ThrowMatchError(selector.pos, mkIdent(root)) (List(root), List(vdef), failTree) diff --git a/test/files/neg/patmatexhaust.check b/test/files/neg/patmatexhaust.check index 2011e4afaf..66b0f3c8ea 100644 --- a/test/files/neg/patmatexhaust.check +++ b/test/files/neg/patmatexhaust.check @@ -21,6 +21,7 @@ missing combination Gp def ma4(x:Deep) = x match { // missing cases: Gu, Gp ^ patmatexhaust.scala:53: warning: match is not exhaustive! +missing combination Gp def ma5(x:Deep) = x match { // Gp ^ -- cgit v1.2.3