diff options
author | Adriaan Moors <adriaan.moors@epfl.ch> | 2011-11-14 16:28:51 +0000 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@epfl.ch> | 2011-11-14 16:28:51 +0000 |
commit | 85e7755ef6767ebb6733c10a90006a71d97ddc9b (patch) | |
tree | c21bdaea852826618a1e3e978f9addd13847e241 /src | |
parent | 7e643d3e4abd561c9fa5a9cc75744f8ac2be3d12 (diff) | |
download | scala-85e7755ef6767ebb6733c10a90006a71d97ddc9b.tar.gz scala-85e7755ef6767ebb6733c10a90006a71d97ddc9b.tar.bz2 scala-85e7755ef6767ebb6733c10a90006a71d97ddc9b.zip |
factoring more into ProtoTreeMakers
contemplating the demise of ProtoTreeMaker, could TreeMaker be all we
need?
no review, but with apologies if this generates merge conflicts for
those exhausting themselves
Diffstat (limited to 'src')
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala | 149 |
1 files changed, 82 insertions, 67 deletions
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala index 4201eede6b..5c65f554ef 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala @@ -32,7 +32,6 @@ import Flags.{ CASE => _, _ } d => body)))))(scrut) TODO: - - check test suite (pos/t602.scala, pos/t3856.scala, jvm/t3412, jvm/t3412-channel, ...) - optimizer loops on virtpatmat compiler? - don't orElse a failure case at the end if there's a default case @@ -93,7 +92,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => case Match(scrut, cases) => val scrutType = if(scrut.tpe ne null) repeatedToSeq(elimAnonymousClass(scrut.tpe.widen)) else {error("TODO: support match with empty scrut"); NoType} // TODO: ErrorTree val scrutSym = freshSym(tree.pos, scrutType) - pmgen.matchFromCases(scrut, scrutSym, (cases map translateCase(scrutSym)) ++ List(pmgen.zero), pt) + matchFromCases(scrut, scrutSym, (cases map translateCase(scrutSym)) ++ List(pmgen.zero), pt) case t => t } @@ -219,13 +218,13 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // val cond = genTypeDirectedEquals(prevBinder, prevBinder.info.widen, extractor.paramType) -- this seems to slow down compilation A LOT // chain a cast before the actual extractor call // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case) - ( - List(ProtoTreeMaker(List(pmgen.condCast(cond, prevBinder, extractor.paramType)), { outerSubst: TreeSubst => - val theSubst = typedSubst(List(prevBinder), List(CODE.REF(castedBinder))) - def nextSubst(tree: Tree): Tree = outerSubst(theSubst(tree)) - (nestedTree => pmgen.fun(castedBinder, nextSubst(nestedTree)), nextSubst)})), - castedBinder - ) + val typeTestProtoTreeMaker = ProtoTreeMaker( + List(pmgen.condCast(cond, prevBinder, extractor.paramType)), + castedBinder, + List(prevBinder), + List(CODE.REF(castedBinder))) + + (List(typeTestProtoTreeMaker), castedBinder) } else (Nil, prevBinder) // the extractor call (applied to the binder bound by the flatMap corresponding to the previous (i.e., enclosing/outer) pattern) @@ -237,19 +236,9 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // println("patTreeLifted= "+ patTreeLifted) - val extractorProtoTreeMaker = ProtoTreeMaker(List(patTreeLifted), - if(patBinders isEmpty) - { outerSubst: TreeSubst => - val binder = freshSym(pos, extractor.resultInMonad) // UnitClass.tpe is definitely wrong when extractor.isSeq, and extractor.resultInMonad should always be correct since it comes directly from the extractor's result type - (nestedTree => pmgen.fun(binder, extractor.lengthGuard(binder, outerSubst(nestedTree))), outerSubst) - } - else - { outerSubst: TreeSubst => - val binder = freshSym(pos, extractor.resultInMonad) - val theSubst = typedSubst(patBinders, extractor.subPatRefs(binder)) - def nextSubst(tree: Tree): Tree = outerSubst(theSubst(tree)) - (nestedTree => pmgen.fun(binder, extractor.lengthGuard(binder, nextSubst(nestedTree))), nextSubst) - }) + val binder = freshSym(pos, extractor.resultInMonad) // can't simplify this when patBinders.isEmpty, since UnitClass.tpe is definitely wrong when extractor.isSeq, and extractor.resultInMonad should always be correct since it comes directly from the extractor's result type + val patRefs = if(patBinders isEmpty) Nil else extractor.subPatRefs(binder) + val extractorProtoTreeMaker = ProtoTreeMaker(List(patTreeLifted), binder, patBinders, patRefs, extractor.lengthGuard(binder)) withSubPats(typeTestProtoTreeMaker :+ extractorProtoTreeMaker, sub.zip: _*) } @@ -328,12 +317,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => case BoundSym(patBinder, p) => // TreeMaker with empty list of trees only performs the substitution patBinder --> prevBinder // println("rebind "+ patBinder +" to "+ prevBinder) - withSubPats(List(ProtoTreeMaker(List(), { outerSubst: TreeSubst => - val theSubst = typedSubst(List(patBinder), List(CODE.REF(prevBinder))) - // println("proto subst of: "+ patBinder) - def nextSubst(tree: Tree): Tree = outerSubst(theSubst(tree)) - (nestedTree => nextSubst(nestedTree), nextSubst) - })), + withSubPats(List(ProtoTreeMaker.substOnly(List(patBinder), List(CODE.REF(prevBinder)))), // the symbols are markers that may be used to refer to the result of the extractor in which the corresponding tree is nested // it's the responsibility of the proto treemaker to replace this symbol by a reference that // selects that result on the function symbol of the flatMap call that binds to the result of this extractor @@ -399,12 +383,10 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => def translateGuard(guard: Tree): List[ProtoTreeMaker] = { if (guard == EmptyTree) List() - else List( - ProtoTreeMaker(List(pmgen.guard(guard)), - { outerSubst => - val binder = freshSym(guard.pos, UnitClass.tpe) - (nestedTree => pmgen.fun(binder, outerSubst(nestedTree)), outerSubst) // guard does not bind any variables, so next subst is the current one - })) + else { + val binder = freshSym(guard.pos, UnitClass.tpe) + List(ProtoTreeMaker(List(pmgen.guard(guard)), binder)) + } } @@ -548,7 +530,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => else ((1 to nbSubPats) map pmgen.tupleSel(binder))).toList } - def lengthGuard(binder: Symbol, then: Tree) = + def lengthGuard(binder: Symbol)(then: Tree) = // no need to check unless it's an unapplySeq and the minimal length is non-trivially satisfied if (!isSeq || (expectedLength < minLenToCheck)) then else { import CODE._ @@ -680,13 +662,18 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // the intermediate language -- can we make this rich enough to do analyses on (exhaustivity/reachability), without looking at the concrete trees? trait PatternLanguage { + def matchingMonadType: Type + def typedSubst(from: List[Symbol], to: List[Tree]): TreeSubst def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x"): Symbol + // codegen relevant to the structure of the translation (how extractors are combined) trait AbsCodeGen { + def runOrElse(scrut: Tree, matcher: Tree): Tree + def flatMap(a: Tree, b: Tree): Tree def fun(arg: Symbol, body: Tree): Tree def or(f: Tree, as: List[Tree]): Tree - def flatMap(a: Tree, b: Tree): Tree + def typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree } def pmgen: AbsCodeGen @@ -694,12 +681,48 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => type TreeSubst = Tree => Tree type TreeXForm = Tree => Tree + object ProtoTreeMaker { + /** + * Make a ProtoTreeMaker that will result in an extractor call specified by `patTrees` (see TreeMaker), + * the next ProtoTreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing + * a function with binder `funBinder` over our extractor's result + * the function's body is determined by the next ProtoTreeMaker, but it can be transformed by the current proto-treemaker (specified by `xform`) + * in this function's body, and all the subsequent ones, references to the symbols in `from` will be replaced by the corresponding tree in `to` + */ + def apply(patTrees: List[Tree], funBinder: Symbol, from: List[Symbol] = Nil, to: List[Tree] = Nil, xform: TreeXForm = identity[Tree]) = { + if(from isEmpty) + new ProtoTreeMaker(patTrees, { outerSubst: TreeSubst => + (nestedTree => pmgen.fun(funBinder, outerSubst(xform(nestedTree))), outerSubst) + }) + else + new ProtoTreeMaker(patTrees, { outerSubst: TreeSubst => + def nextSubst(tree: Tree): Tree = outerSubst(typedSubst(from, to)(tree)) + (nestedTree => pmgen.fun(funBinder, nextSubst(xform(nestedTree))), nextSubst) + }) + } + + def singleBinder(binderToSubst: Symbol, patTrees: Tree*): ProtoTreeMaker = + singleBinderWithTp(binderToSubst, binderToSubst.info.widen, patTrees : _*) + + def singleBinderWithTp(binderToSubst: Symbol, binderType: Type, patTrees: Tree*): ProtoTreeMaker = { // assert(patTrees.head.pos != NoPosition, "proto-tree for "+(binderToSubst, patTrees.toList)) + val binder = freshSym(patTrees.head.pos, binderType) + ProtoTreeMaker(patTrees.toList, binder, List(binderToSubst), List(CODE.REF(binder))) + } + + def substOnly(from: List[Symbol], to: List[Tree]) = new ProtoTreeMaker(List(), { outerSubst: TreeSubst => + def nextSubst(tree: Tree): Tree = outerSubst(typedSubst(from, to)(tree)) + (nestedTree => nextSubst(nestedTree), nextSubst) + }) + } + /** * substTreeMaker: takes a subst and returns the following pair: * - a transform that wraps a one-argument Function around a tree * and that replaces the binders that referred to subpatterns in that tree * by the corresponding selection on the function's argument (a tuple selection, a seq-index, or a seq-drop) * - the substitution to be applied by the next proto-tree maker + * + * TODO: can we get rid of ProtoTreeMaker, and just have TreeMaker? */ case class ProtoTreeMaker(extractors: List[Tree], substTreeMaker: TreeSubst => (TreeXForm, TreeSubst)) { def threadSubst(subst: TreeSubst): (TreeMaker, TreeSubst) = { @@ -708,23 +731,28 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => } } - object ProtoTreeMaker { - def singleBinder(binderToSubst: Symbol, patTrees: Tree*): ProtoTreeMaker = singleBinderWithTp(binderToSubst, binderToSubst.info.widen, patTrees : _*) - def singleBinderWithTp(binderToSubst: Symbol, binderType: Type, patTrees: Tree*): ProtoTreeMaker = { - assert(patTrees.head.pos != NoPosition, "proto-tree for "+(binderToSubst, patTrees.toList)) - - ProtoTreeMaker(patTrees.toList, - { outerSubst: TreeSubst => - val binder = freshSym(patTrees.head.pos, binderType) - val theSubst = typedSubst(List(binderToSubst), List(CODE.REF(binder))) - // println("theSubst: "+ theSubst) - def nextSubst(tree: Tree): Tree = outerSubst(theSubst(tree)) - (nestedTree => pmgen.fun(binder, nextSubst(nestedTree)), nextSubst) - }) + // (o => (o(foo), newO)) :: (o => (o(foo), newO')) :: (o => (o(foo), newO'')) :: (o => (o(foo), newO''')) + // (identity(foo), newO) :: (newO(foo), newO') :: (newO'(foo), newO'') :: (newO''(foo), newO''') + def makeTreeMakers(protoTreeMakers: List[ProtoTreeMaker]): List[TreeMaker] = { + // run the state monad (subst is the state) and get out a list of TreeMakers + val (treeMakers, subst) = protoTreeMakers.foldLeft((List[TreeMaker](), identity[Tree](_))){ + case ((accumTreeMakers, accumSubst), protoTreeMaker) => + val (treeMaker, newSubst) = protoTreeMaker threadSubst accumSubst + (treeMaker :: accumTreeMakers, newSubst) } + + treeMakers.reverse } object TreeMaker { + /** + * Construct a TreeMaker given the trees that represent the extractor call + * and the transformation to be transformed on the trees of the sub-patterns + * meaning of `trees`: + * - none: only doing substitution, + * - one: a regular extractor call, + * - many: alternatives to be fused by MatchingStrategy.or + */ def apply(trees: List[Tree], genFunAndSubst0: TreeXForm): TreeMaker = trees match { case Nil => new NoTreeMaker{def genFunAndSubst(next: Tree) = genFunAndSubst0(next)} case List(tree) => new SingleTreeMaker(tree){def genFunAndSubst(next: Tree) = genFunAndSubst0(next)} @@ -734,6 +762,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => def combine(treeMakers: List[TreeMaker], body: Tree, pos: Position) = atPos(pos)(treeMakers.foldRight (body) (_ genFlatMap _)) } + abstract class TreeMaker { // wrap a Fun (with binder x) around the next tree and do aggregated substitution (which // replaces old pattern bindings by the appropriate tuple element selection on the new binders, @@ -756,24 +785,16 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => def genFlatMap(tree: Tree) = pmgen.or(genFunAndSubst(tree), alts) setPos alts.head.pos } - // (o => (o(foo), newO)) :: (o => (o(foo), newO')) :: (o => (o(foo), newO'')) :: (o => (o(foo), newO''')) - // (identity(foo), newO) :: (newO(foo), newO') :: (newO'(foo), newO'') :: (newO''(foo), newO''') - def makeTreeMakers(protoTreeMakers: List[ProtoTreeMaker]): List[TreeMaker] = { - // run the state monad (subst is the state) and get out a list of TreeMakers - val (treeMakers, subst) = protoTreeMakers.foldLeft((List[TreeMaker](), identity[Tree](_))){ - case ((accumTreeMakers, accumSubst), protoTreeMaker) => - val (treeMaker, newSubst) = protoTreeMaker threadSubst accumSubst - (treeMaker :: accumTreeMakers, newSubst) - } - - treeMakers.reverse + def matchFromCases(scrut: Tree, scrutSym: Symbol, cases: List[Tree], pt: Type): Tree = { + // when specified, need to propagate pt explicitly, type inferencer can't handle it + val optPt = if(!isFullyDefined(pt)) NoType else appliedType(matchingMonadType, List(pt)) + pmgen.runOrElse(scrut, pmgen.fun(scrutSym, cases reduceLeft pmgen.typedOrElse(optPt))) } } // generate actual trees trait MatchCodeGen extends PatternLanguage { def matchingStrategy: Tree - def matchingMonadType: Type lazy val pmgen: CommonCodeGen with MatchingStrategyGen with MonadInstGen = if (matchingMonadType.typeSymbol eq OptionClass) (new CommonCodeGen with MatchingStrategyGenOpt with MonadInstGenOpt {}) @@ -823,12 +844,6 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // TODO: optimize to if (!needsTypeTest(b.info.widen, repackExistential(tp))) REF(b) else ... def _asInstanceOf(b: Symbol, tp: Type): Tree = gen.mkAsInstanceOf(REF(b), repackExistential(tp), true, false) def _isInstanceOf(b: Symbol, tp: Type): Tree = gen.mkIsInstanceOf(REF(b), repackExistential(tp), true, false) - - def matchFromCases(scrut: Tree, scrutSym: Symbol, cases: List[Tree], pt: Type): Tree = { - // when specified, need to propagate pt explicitly, type inferencer can't handle it - val optPt = if(!isFullyDefined(pt)) NoType else appliedType(matchingMonadType, List(pt)) - runOrElse(scrut, fun(scrutSym, cases reduceLeft typedOrElse(optPt))) - } } trait MatchingStrategyGen { self: CommonCodeGen with MatchingStrategyGen with MonadInstGen => |