From d14b4a117e477505afa4b2417133d3b8325ba4d3 Mon Sep 17 00:00:00 2001 From: Paul Phillips Date: Tue, 30 Jun 2009 14:37:15 +0000 Subject: More elucidation work on the pattern matcher. --- src/compiler/scala/tools/nsc/ast/TreeDSL.scala | 2 +- .../scala/tools/nsc/matching/CodeFactory.scala | 18 ----- .../tools/nsc/matching/ParallelMatching.scala | 86 +++++++++++----------- .../scala/tools/nsc/transform/ExplicitOuter.scala | 69 ++++++++--------- .../tools/nsc/transform/TypingTransformers.scala | 2 + 5 files changed, 75 insertions(+), 102 deletions(-) (limited to 'src/compiler') diff --git a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala index 52c39e6ada..3dce8148db 100644 --- a/src/compiler/scala/tools/nsc/ast/TreeDSL.scala +++ b/src/compiler/scala/tools/nsc/ast/TreeDSL.scala @@ -90,7 +90,7 @@ trait TreeDSL { /** Assignment */ def ===(rhs: Tree) = Assign(target, rhs) - /** for tree of sequence type, returns tree that drops first i elements */ + /** Methods for sequences **/ def DROP(count: Int): Tree = if (count == 0) target else (target DOT nme.drop)(LIT(count)) DOT nme.toSeq diff --git a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala index c7c2db3cc7..0c81c3d27a 100644 --- a/src/compiler/scala/tools/nsc/matching/CodeFactory.scala +++ b/src/compiler/scala/tools/nsc/matching/CodeFactory.scala @@ -33,24 +33,6 @@ trait CodeFactory extends ast.TreeDSL typer typed (VAL(x) === finalRhs) } - /** for tree of sequence type, returns tree that drops first i elements */ - final def seqDrop(sel: Tree, ix: Int)(implicit typer : Typer) = - typer typed (sel DROP ix) - - /** for tree of sequence type, returns tree that represents element at index i */ - final def seqElement(sel: Tree, ix: Int)(implicit typer : Typer) = - typer typed ((sel DOT (sel.tpe member nme.apply))(LIT(ix))) - - private def lengthCompare(sel: Tree, tpe: Type, i: Int) = ((sel DOT tpe.member(nme.lengthCompare))(LIT(i))) - - /** for tree of sequence type, returns boolean tree testing that the sequence has length i */ - final def seqHasLength(sel: Tree, tpe: Type, i: Int)(implicit typer : Typer) = - typer typed (lengthCompare(sel, tpe, i) ANY_== ZERO) - - /** for tree of sequence type sel, returns boolean tree testing that length >= i */ - final def seqLongerThan(sel:Tree, tpe:Type, i:Int)(implicit typer : Typer) = - typer typed (lengthCompare(sel, tpe, i) ANY_>= ZERO) - final def squeezedBlock(vds: List[Tree], exp: Tree)(implicit theOwner: Symbol): Tree = if (settings_squeeze) Block(Nil, squeezedBlock1(vds, exp)) else Block(vds, exp) diff --git a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala index 14f6f5fd75..3e265c9bfb 100644 --- a/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala +++ b/src/compiler/scala/tools/nsc/matching/ParallelMatching.scala @@ -44,6 +44,8 @@ trait ParallelMatching extends ast.TreeDSL { } import Implicits._ + def DBG(msg: String) = if (settings.debug.value) println(msg) + /** * Encapsulates a symbol being matched on. * @@ -112,12 +114,6 @@ trait ParallelMatching extends ast.TreeDSL { 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(treeCopy.Bind(b, n, x) setType x.tpe), p) @@ -158,10 +154,10 @@ trait ParallelMatching extends ast.TreeDSL { def apply(i: Int): Tree = ps(i).tree def zip() = column.zipWithIndex - def zip[T](ys: List[T]) = column.zip(ys) + def zip[T](ys: List[T]) = column zip ys - def isObjectTest(pat: Pattern) = pat.isObjectTest(headType) - def isObjectTest(pat: Tree) = Pattern(pat).isObjectTest(headType) + 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 @@ -190,9 +186,6 @@ trait ParallelMatching extends ast.TreeDSL { case class Guard(tree: Tree) { def isEmpty = tree eq EmptyTree def duplicate = Guard(tree.duplicate) - - def mkIf(thenPart: Tree, elsePart: Tree) = - IF (tree.duplicate) THEN thenPart ELSE elsePart } val NoGuard = Guard(EmptyTree) @@ -228,16 +221,16 @@ trait ParallelMatching extends ast.TreeDSL { val body = typer.typed { rep.requestBody(bx, subst) } lazy val vdefs = subst.targetParams lazy val typedElse = guardedRest.toTree - lazy val typedIf = typer.typed(guard.mkIf(body, typedElse)) + lazy val typedIf = typer typed (IF (guard.duplicate.tree) THEN body ELSE typedElse) if (guard.isEmpty) body - else typer.typed(squeezedBlock(vdefs, typedIf)) + else typer typed squeezedBlock(vdefs, typedIf) } } /** mixture rule for literals */ - class MixLiterals(val pats: Patterns, val rest:Rep)(implicit rep:RepFactory) extends RuleApplication(rep) { + 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: immutable.Set[Symbol] = emptySymbolSet var defaultIndexSet = new BitSet(pats.size) @@ -247,8 +240,8 @@ trait ParallelMatching extends ast.TreeDSL { defaultV = defaultV ++ vs } - def haveDefault: Boolean = !defaultIndexSet.isEmpty - def defaultRows: List[Row] = defaultIndexSet.toList reverseMap grabRow + 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 = { @@ -296,7 +289,7 @@ trait ParallelMatching extends ast.TreeDSL { 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)))) + val r2 = rep.make(r.temp, r.row map (x => x rebind bindVars(tag, x.subst))) CASE(Literal(tag)) ==> r2.toTree } @@ -400,6 +393,7 @@ trait ParallelMatching extends ast.TreeDSL { */ sealed class MixSequence(val pats: Patterns, val rest: Rep)(implicit rep: RepFactory) extends RuleApplication(rep) { val Patterns(scrut, patterns) = pats + def compareOp = pats.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.sequenceType)) :: Nil @@ -427,19 +421,21 @@ trait ParallelMatching extends ast.TreeDSL { case _ => false }) + // context (to be used in IF), success and failure Rep def getTransition(implicit theOwner: Symbol): (Tree => Tree => Tree, Rep, Rep) = { - 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(y.stripped.pos, scrut.elementType)) - - lazy val tail = newVar(scrut.pos, scrut.sequenceType) - lazy val lastBinding = if (ys.size > 0) seqDrop(treeAsSeq.duplicate, ys.size) else scrut.id + scrut assertIsSubtype pats.head.tpe // 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(y.stripped.pos, scrut.elementType)) + def scrutineeCopy = scrut.id.duplicate + + lazy val tail = newVar(scrut.pos, scrut.sequenceType) + 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 = - (for ((v, i) <- vs.zipWithIndex) yield typedValDef(v, seqElement(treeAsSeq.duplicate, i))) ::: - List(typedValDef(tail, lastBinding)) + (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 { @@ -448,16 +444,16 @@ trait ParallelMatching extends ast.TreeDSL { }) val succRep = makeSuccRep(vs, tail, nrows.flatMap(x => x)) - val failRep = rep.make(scrut.mkList(rest.temp), frows.flatMap(x => x)) - - // fixed length - val cond = getCond(treeAsSeq, xs.length) - return ({thenp:Tree => {elsep:Tree => - If(cond, squeezedBlock(bindings, thenp), elsep)}}, succRep, failRep) + val failRep = rep.make(scrut mkList rest.temp, frows.flatMap(x => x)) + def context = { thenp: Tree => { elsep: Tree => + IF (getPrecondition(scrutineeCopy, xs.length)) THEN squeezedBlock(bindings, thenp) ELSE elsep + }} + (context, succRep, failRep) } - // lengthArg is exact length - protected def getCond(tree:Tree, lengthArg:Int) = seqHasLength(tree.duplicate, pats.head.tpe, lengthArg) + // precondition for matching: sequence is exactly length of arg + protected def getPrecondition(tree: Tree, lengthArg: Int) = + typer typed (((tree.duplicate DOT compareOp)(LIT(lengthArg))) ANY_== ZERO) final def tree(implicit theOwner: Symbol, failTree: Tree) = this.getTransition match { case (cx, succRep, failRep) => cx(succRep.toTree)(failRep.toTree) @@ -485,8 +481,10 @@ trait ParallelMatching extends ast.TreeDSL { override protected def makeSuccRep(vs:List[Symbol], tail:Symbol, nrows:List[Row])(implicit theOwner: Symbol) = 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, pats.head.tpe, lengthArg - 1) + // 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) = + typer typed (((tree.duplicate DOT compareOp)(LIT(lengthArg - 1))) ANY_>= ZERO) } @@ -653,8 +651,7 @@ trait ParallelMatching extends ast.TreeDSL { // 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) + def isAlternative(p: Tree): Boolean = p.stripped match { case Alternative(ps) => true case _ => false } @@ -950,12 +947,15 @@ trait ParallelMatching extends ast.TreeDSL { // communicate whether exhaustiveness-checking is enabled via some flag 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 => 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 _ if roots.length <= 1 => mkRow(List(pat)) + case Apply(fn, pargs) => mkRow(pargs) + case Ident(nme.WILDCARD) => mkRow(getDummies(roots.length)) case _ => None } + (rowForPat, b, definedVars(pat)) } ) diff --git a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala index e4c4ea9fd9..40eeb572cd 100644 --- a/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala +++ b/src/compiler/scala/tools/nsc/transform/ExplicitOuter.scala @@ -164,7 +164,6 @@ abstract class ExplicitOuter extends InfoTransform * The class provides methods for referencing via outer. */ abstract class OuterPathTransformer(unit: CompilationUnit) extends TypingTransformer(unit) { - /** The directly enclosing outer parameter, if we are in a constructor */ protected var outerParam: Symbol = NoSymbol @@ -296,22 +295,17 @@ abstract class ExplicitOuter extends InfoTransform /** The definition tree of the outer accessor of current class */ - def outerFieldDef: Tree = { - val outerFld = outerField(currentClass) - ValDef(outerFld, EmptyTree) - } + def outerFieldDef: Tree = VAL(outerField(currentClass)) === EmptyTree /** The definition tree of the outer accessor of current class */ def outerAccessorDef: Tree = { val outerAcc = outerAccessor(currentClass) - var rhs = if (outerAcc.isDeferred) EmptyTree - else Select(This(currentClass), outerField(currentClass)) - localTyper.typed { - atPos(currentClass.pos) { - DefDef(outerAcc, rhs) - } - } + var rhs: Tree = + if (outerAcc.isDeferred) EmptyTree + else This(currentClass) DOT outerField(currentClass) + + typedPos(currentClass.pos)(DEF(outerAcc) === rhs) } /** The definition tree of the outer accessor for class @@ -328,23 +322,28 @@ abstract class ExplicitOuter extends InfoTransform if (mixinClass.owner.isTerm) gen.mkAttributedThis(mixinClass.owner.enclClass) else gen.mkAttributedQualifier(currentClass.thisType.baseType(mixinClass).prefix) val rhs = ExplicitOuterTransformer.this.transform(path) - rhs.setPos(currentClass.pos) // see note below - localTyper.typed { - atPos(currentClass.pos) { - // @S: atPos not good enough because of nested atPos in DefDef method, which gives position from wrong class! - DefDef(outerAcc, rhs).setPos(currentClass.pos) - } - } + + // @S: atPos not good enough because of nested atPos in DefDef method, which gives position from wrong class! + rhs setPos currentClass.pos + typedPos(currentClass.pos) { (DEF(outerAcc) === rhs) setPos currentClass.pos } + } + + /** If FLAG is set on symbol, sets notFLAG (this exists in anticipation of generalizing). */ + def setNotFlags(sym: Symbol, flags: Int*) { + val notMap = Map( + PRIVATE -> notPRIVATE, + PROTECTED -> notPROTECTED + ) + for (f <- flags ; notFlag <- notMap get f ; if sym hasFlag f) + sym setFlag notFlag } /** The main transformation method */ override def transform(tree: Tree): Tree = { - val sym = tree.symbol - if ((sym ne null) && sym.isType) {//(9) - if (sym hasFlag PRIVATE) sym setFlag notPRIVATE - if (sym hasFlag PROTECTED) sym setFlag notPROTECTED - } + if (sym != null && sym.isType) //(9) + setNotFlags(sym, PRIVATE, PROTECTED) + tree match { case Template(parents, self, decls) => val newDefs = new ListBuffer[Tree] @@ -414,27 +413,17 @@ abstract class ExplicitOuter extends InfoTransform var nselector = transform(selector) def makeGuardDef(vs: List[Symbol], guard: Tree) = { - import symtab.Flags._ val gdname = cunit.fresh.newName(guard.pos, "gd") val method = currentOwner.newMethod(mch.pos, gdname) setFlag SYNTHETIC val fmls = vs map (_.tpe) val tpe = new MethodType(method newSyntheticValueParams fmls, BooleanClass.tpe) method setInfo tpe - // XXX integrate - // localTyper typed (DEF(method) === { - // new ChangeOwnerTraverser(currentOwner, method) traverse guard - // new TreeSymSubstituter(vs, method.paramss.head) traverse guard - // guard - // }) - // - localTyper.typed( - DefDef(method, { - new ChangeOwnerTraverser(currentOwner, method) traverse guard - new TreeSymSubstituter(vs, method.paramss.head) traverse guard - guard - }) - ) + localTyper typed (DEF(method) === { + new ChangeOwnerTraverser(currentOwner, method) traverse guard + new TreeSymSubstituter(vs, method.paramss.head) traverse guard + guard + }) } val nguard = new ListBuffer[Tree] @@ -447,7 +436,7 @@ abstract class ExplicitOuter extends InfoTransform val guardDef = makeGuardDef(vs, guard) nguard += transform(guardDef) // building up list of guards - localTyper typed (Ident(guardDef.symbol) APPLY(vs map Ident)) + localTyper typed (Ident(guardDef.symbol) APPLY (vs map Ident)) } (CASE(transform(p)) IF gdcall) ==> transform(b) diff --git a/src/compiler/scala/tools/nsc/transform/TypingTransformers.scala b/src/compiler/scala/tools/nsc/transform/TypingTransformers.scala index 90281047f4..ee3230c5fa 100644 --- a/src/compiler/scala/tools/nsc/transform/TypingTransformers.scala +++ b/src/compiler/scala/tools/nsc/transform/TypingTransformers.scala @@ -6,6 +6,7 @@ package scala.tools.nsc.transform +import util.Position import scala.collection.mutable.{Map, HashMap} /** A base class for transforms. @@ -20,6 +21,7 @@ trait TypingTransformers { var localTyper: analyzer.Typer = analyzer.newTyper( analyzer.rootContext(unit, EmptyTree, true)) protected var curTree: Tree = _ + protected def typedPos(pos: Position)(tree: Tree) = localTyper typed { atPos(pos)(tree) } /** a typer for each enclosing class */ var typers: Map[Symbol, analyzer.Typer] = new HashMap -- cgit v1.2.3