diff options
author | Adriaan Moors <adriaan.moors@epfl.ch> | 2011-11-22 23:10:19 +0000 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@epfl.ch> | 2011-11-22 23:10:19 +0000 |
commit | ae054a1663381ada248ab020ea4993452664cd83 (patch) | |
tree | f7a86f3a460fe38507a8b79deea160de92b78131 | |
parent | 1189476b0e48bb0e82565b75d7997b33a67c31e9 (diff) | |
download | scala-ae054a1663381ada248ab020ea4993452664cd83.tar.gz scala-ae054a1663381ada248ab020ea4993452664cd83.tar.bz2 scala-ae054a1663381ada248ab020ea4993452664cd83.zip |
a wider variety of treemakers
optimized combining substitutions
why we substitute in EqualityTestTreeMaker
-rw-r--r-- | src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala | 311 |
1 files changed, 163 insertions, 148 deletions
diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala index 38c97e8828..e3ac21469e 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala @@ -94,7 +94,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("something wrong during match translation: empty scrutinee"); NoType} val scrutSym = freshSym(tree.pos, scrutType) - matchFromCases(scrut, scrutSym, (cases map translateCase(scrutSym)) ++ List(pmgen.zero), repeatedToSeq(pt)) // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala with -Xexperimental + combineCases(scrut, scrutSym, (cases map translateCase(scrutSym)) ++ List(pmgen.zero), repeatedToSeq(pt)) // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala with -Xexperimental case t => t } @@ -179,7 +179,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // so that we can return Option's from a match without ambiguity whether this indicates failure in the monad, or just some result in the monad // 2) body.tpe is the type of the body after applying the substitution that represents the solution of GADT type inference // need the explicit cast in case our substitutions in the body change the type to something that doesn't take GADT typing into account - TreeMaker.combine(translatePattern(scrutSym, pattern) ++ translateGuard(guard), pmgen.caseResult(body, body.tpe), tree.pos) + combineTreeMakers(translatePattern(scrutSym, pattern) ++ translateGuard(guard), pmgen.caseResult(body, body.tpe), tree.pos) } def translatePattern(patBinder: Symbol, patTree: Tree): List[TreeMaker] = { @@ -204,13 +204,12 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // TODO: extractor.paramType may contain unbound type params (run/t2800, run/t3530) val (typeTestTreeMaker, patBinderOrCasted) = if (needsTypeTest(patBinder.info.widen, extractor.paramType)) { - val castedBinder = freshSym(pos, extractor.paramType, "cp") // chain a type-testing extractor before the actual extractor call // it tests the type, checks the outer pointer and casts to the expected type // the outer check is mandated by the spec for case classes, but we do it for user-defined unapplies as well // (the prefix of the argument passed to the unapply must equal the prefix of the type of the binder) - - (List(TreeMaker.typeTest(patBinder, extractor.paramType, castedBinder)), castedBinder) + val treeMaker = TypeTestTreeMaker(patBinder, extractor.paramType, pos) + (List(treeMaker), treeMaker.nextBinder) } else (Nil, patBinder) withSubPats(typeTestTreeMaker :+ extractor.treeMaker(patBinderOrCasted, pos), extractor.subBindersAndPatterns: _*) @@ -265,7 +264,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // must treat Typed and Bind together -- we need to know the patBinder of the Bind pattern to get at the actual type case MaybeBoundTyped(subPatBinder, pt) => // a typed pattern never has any subtrees - noFurtherSubPats(TreeMaker.typeAndEqualityTest(patBinder, subPatBinder, pt, pos)) + noFurtherSubPats(TypeAndEqualityTestTreeMaker(subPatBinder, patBinder, pt, pos)) /** A pattern binder x@p consists of a pattern variable x and a pattern p. The type of the variable x is the static type T of the pattern p. @@ -276,7 +275,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => case Bound(subpatBinder, p) => // TreeMaker with empty list of trees only performs the substitution subpatBinder --> patBinder // println("rebind "+ subpatBinder +" to "+ patBinder) - withSubPats(List(TreeMaker.substOnly(List(subpatBinder), List(CODE.REF(patBinder)))), + withSubPats(List(SubstOnlyTreeMaker(Substitution(subpatBinder, CODE.REF(patBinder)))), // 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 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 @@ -293,7 +292,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => The type of r must conform to the expected type of the pattern. **/ case Literal(Constant(_)) | Ident(_) | Select(_, _) => - noFurtherSubPats(TreeMaker.equalityTest(patBinder, patTree, pos)) + noFurtherSubPats(EqualityTestTreeMaker(patBinder, patTree, pos)) case Alternative(alts) => val altTrees = alts map { alt => @@ -302,10 +301,10 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // `one(x) : T` where x is the binder before this pattern, which will be replaced by the binder for the alternative by TreeMaker.singleBinder below // T is the widened type of the previous binder -- this ascription is necessary to infer a clean type for `or` -- the alternative combinator -- in the presence of existential types // see pos/virtpatmat_exist1.scala - TreeMaker.combine(translatePattern(patBinder, alt), pmgen.one(CODE.REF(patBinder), patBinder.info.widen), pos) + combineTreeMakers(translatePattern(patBinder, alt), pmgen.one(CODE.REF(patBinder), patBinder.info.widen), pos) } - noFurtherSubPats(TreeMaker.alternatives(patBinder, altTrees : _*)) + noFurtherSubPats(AlternativesTreeMaker(patBinder, altTrees : _*)) /* TODO: Paul says about future version: I think this should work, and always intended to implement if I can get away with it. case class Foo(x: Int, y: String) @@ -332,7 +331,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => def translateGuard(guard: Tree): List[TreeMaker] = if (guard == EmptyTree) List() - else List(TreeMaker.guard(guard)) + else List(GuardTreeMaker(guard)) // helper methods: they analyze types and trees in isolation, but they are not (directly) concerned with the structure of the overall translation @@ -344,6 +343,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // that we need to preserve, so we supply the scrutinee as Ident(nme.SELECTOR_DUMMY), // and replace that dummy by a reference to the actual binder in translateExtractorPattern def fromCaseClass(fun: Tree, args: List[Tree]): Option[ExtractorCall] = { + // TODO: can we rework the typer so we don't have to do all this twice? // undo rewrite performed in (5) of adapt val orig = fun match {case tpt: TypeTree => tpt.original case _ => fun} val origSym = orig.symbol @@ -448,8 +448,8 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => val subpatRefs = if (subPatBinders isEmpty) Nil else subPatRefs(binder) lengthGuard(binder) match { - case None => TreeMaker(List(patTreeLifted), binder, subPatBinders, subpatRefs) - case Some(lenGuard) => TreeMaker.filtered(patTreeLifted, lenGuard, binder, subPatBinders, subpatRefs) + case None => ExtractorTreeMaker(patTreeLifted, binder, Substitution(subPatBinders, subpatRefs)) + case Some(lenGuard) => FilteredExtractorTreeMaker(patTreeLifted, lenGuard, binder, Substitution(subPatBinders, subpatRefs)) } } @@ -549,7 +549,6 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // TODO: also need to test when erasing pt loses crucial information (and if we can recover it using a manifest) def needsTypeTest(tp: Type, pt: Type) = !(tp <:< pt) def typeTest(binder: Symbol, pt: Type) = maybeWithOuterCheck(binder, pt)(pmgen._isInstanceOf(binder, pt)) - def typeTestExtractor(binder: Symbol, pt: Type) = pmgen.condCast(typeTest(binder, pt), binder, pt) /** Type patterns consist of types, type variables, and wildcards. A type pattern T is of one of the following forms: - A reference to a class C, p.C, or T#C. @@ -577,35 +576,30 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // generate the tree for the run-time test that follows from the fact that // a `scrut` of known type `scrutTp` is expected to have type `expectedTp` // uses maybeWithOuterCheck to check the type's prefix - def typeAndEqualityTest(scrut: Symbol, expectedTp: Type): Tree = { import CODE._ + def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree = { import CODE._ // TODO: `null match { x : T }` will yield a check that (indirectly) tests whether `null ne null` // don't bother (so that we don't end up with the warning "comparing values of types Null and Null using `ne' will always yield false") def genEqualsAndInstanceOf(sym: Symbol): Tree - = pmgen._equals(REF(sym), scrut) AND pmgen._isInstanceOf(scrut, expectedTp.widen) + = pmgen._equals(REF(sym), patBinder) AND pmgen._isInstanceOf(patBinder, pt.widen) def isRefTp(tp: Type) = tp <:< AnyRefClass.tpe - val scrutTp = scrut.info.widen - def isMatchUnlessNull = isRefTp(expectedTp) && !needsTypeTest(scrutTp, expectedTp) + val patBinderTp = patBinder.info.widen + def isMatchUnlessNull = isRefTp(pt) && !needsTypeTest(patBinderTp, pt) // TODO: [SPEC] type test for Array // TODO: use manifests to improve tests (for erased types we can do better when we have a manifest) - expectedTp match { + pt match { case SingleType(_, sym) /*this implies sym.isStable*/ => genEqualsAndInstanceOf(sym) // TODO: [SPEC] the spec requires `eq` instead of `==` here case ThisType(sym) if sym.isModule => genEqualsAndInstanceOf(sym) // must use == to support e.g. List() == Nil - case ThisType(sym) => REF(scrut) OBJ_EQ This(sym) - case ConstantType(Constant(null)) if isRefTp(scrutTp) => REF(scrut) OBJ_EQ NULL - case ConstantType(const) => pmgen._equals(Literal(const), scrut) - case _ if isMatchUnlessNull => maybeWithOuterCheck(scrut, expectedTp)(REF(scrut) OBJ_NE NULL) - case _ => typeTest(scrut, expectedTp) + case ThisType(sym) => REF(patBinder) OBJ_EQ This(sym) + case ConstantType(Constant(null)) if isRefTp(patBinderTp) => REF(patBinder) OBJ_EQ NULL + case ConstantType(const) => pmgen._equals(Literal(const), patBinder) + case _ if isMatchUnlessNull => maybeWithOuterCheck(patBinder, pt)(REF(patBinder) OBJ_NE NULL) + case _ => typeTest(patBinder, pt) } } - def typeAndEqualityTestExtractor(patBinder: Symbol, pt: Type): (Tree, Type) = { - val accumType = glb(List(patBinder.info.widen, pt)) - (pmgen.condCast(typeAndEqualityTest(patBinder, pt), patBinder, accumType), accumType) - } - /** A conservative approximation of which patterns do not discern anything. * They are discarded during the translation. */ @@ -631,160 +625,181 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => } trait TreeMakers { - def matchingMonadType: Type - def typedSubst(from: List[Symbol], to: List[Tree]): Transformer - def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x"): Symbol - def typeAndEqualityTestExtractor(patBinder: Symbol, pt: Type): (Tree, Type) - def typeTestExtractor(binder: Symbol, pt: Type): Tree + trait TreeMaker { + def substitution: Substitution ={ + if (currSub eq null) currSub = initialSubstitution + currSub + } - // codegen relevant to the structure of the translation (how extractors are combined) - trait AbsCodeGen { import CODE.UNIT - 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 typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree - def guard(c: Tree): Tree - // TODO: defaults in traits + self types == broken? - // def guard(c: Tree, then: Tree, tp: Type): Tree - // def cond(c: Tree): Tree = cond(c, UNIT, NoType) - def cond(c: Tree, then: Tree, tp: Type): Tree - def condOptimized(c: Tree, then: Tree): Tree - def _equals(checker: Tree, binder: Symbol): Tree + protected def initialSubstitution: Substitution + + private[TreeMakers] def addOuterSubstitution(outerSubst: Substitution): TreeMaker = { + currSub = outerSubst >> substitution + this + } + private[this] var currSub: Substitution = null + + def chainBefore(next: Tree): Tree } - def pmgen: AbsCodeGen + case class SubstOnlyTreeMaker(initialSubstitution: Substitution) extends TreeMaker { + def chainBefore(next: Tree): Tree = substitution(next) + } - object Substitution { - // requires sameLength(from, to) - def apply(from: List[Symbol], to: List[Tree]) = - if (from nonEmpty) new Substitution(from, to) else EmptySubstitution + trait FunTreeMaker extends TreeMaker { + val nextBinder: Symbol + // wrap a Fun (with binder nextBinder) around the next tree (unless nextBinder == NoSymbol) and perform our substitution + protected def wrapFunSubst(next: Tree): Tree = pmgen.fun(nextBinder, substitution(next)) } - class Substitution(val from: List[Symbol], val to: List[Tree]) { - def apply(tree: Tree): Tree = typedSubst(from, to).transform(tree) - // forall t: Tree. this(other(t)) == (this >> other)(t) - def >>(other: Substitution): Substitution = { - new Substitution(other.from ++ from, other.to.map(apply) ++ to) // a quick benchmarking run indicates the `.map(apply)` is not too costly - } + trait FreshFunTreeMaker extends FunTreeMaker { + val pos: Position + val nextBinderTp: Type + lazy val nextBinder = freshSym(pos, nextBinderTp) } - object EmptySubstitution extends Substitution(Nil, Nil) { - override def apply(tree: Tree): Tree = tree - override def >>(other: Substitution): Substitution = other + trait SingleExtractorTreeMaker extends FunTreeMaker { + val extractor: Tree + // build Tree that chains `next` after the current extractor + def chainBefore(next: Tree): Tree = pmgen.flatMap(extractor, wrapFunSubst(next)) setPos extractor.pos } - // TODO: these factory methods should instantiate different subclasses of TreeMaker, - // so analyses and optimizations have the necessary information readily available, - // instead of having to (only) analyze the generated tree directly - object TreeMaker { - /** - * Make a TreeMaker that will result in an extractor call specified by `patTrees` (see TreeMaker), - * the next TreeMaker (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 TreeMaker - * 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): TreeMaker = - new StdTreeMakerImpl(Substitution(from, to), patTrees, funBinder) - - def typeTest(patBinder: Symbol, pt: Type, castedBinder: Symbol): TreeMaker = TreeMaker( - List(typeTestExtractor(patBinder, pt)), - castedBinder, - // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case) - List(patBinder), - List(CODE.REF(castedBinder))) - - def filtered(extractor: Tree, guard: Tree, funBinder: Symbol, from: List[Symbol] = Nil, to: List[Tree] = Nil): TreeMaker = - new FilteredTreeMaker(Substitution(from, to), extractor, guard, funBinder) - - def typeAndEqualityTest(patBinder: Symbol, subpatBinder: Symbol, tpe: Type, pos: Position): TreeMaker = { - // implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations) - val (extractor, accumType) = typeAndEqualityTestExtractor(patBinder, tpe) - - singleBinderWithTp(subpatBinder, accumType, atPos(pos)(extractor)) - } + trait SingleBinderTreeMaker extends FunTreeMaker { + val prevBinder: Symbol + lazy val initialSubstitution = Substitution(List(prevBinder), List(CODE.REF(nextBinder))) + } - def equalityTest(patBinder: Symbol, patTree: Tree, pos: Position) = { - val prevTp = patBinder.info.widen + abstract class SimpleTreeMaker extends SingleExtractorTreeMaker with SingleBinderTreeMaker with FreshFunTreeMaker - // NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null) - // equals need not be well-behaved, so don't intersect with pattern's (stabilized) type (unlike MaybeBoundTyped's accumType, where it's required) - val extractor = atPos(pos)(pmgen.cond(pmgen._equals(patTree, patBinder), CODE.REF(patBinder), prevTp)) + /** + * Make a TreeMaker that will result in an extractor call specified by `extractor` + * the next TreeMaker (here, we don't know which it'll be) is chained after this one by flatMap'ing + * a function with binder `nextBinder` over our extractor's result + * the function's body is determined by the next TreeMaker + * 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` + */ + case class ExtractorTreeMaker(extractor: Tree, nextBinder: Symbol, initialSubstitution: Substitution) extends SingleExtractorTreeMaker - singleBinderWithTp(patBinder, prevTp, extractor) - } + case class FilteredExtractorTreeMaker(extractor: Tree, guard: Tree, nextBinder: Symbol, initialSubstitution: Substitution) extends FunTreeMaker { + def chainBefore(next: Tree): Tree = + pmgen.flatMap(extractor, wrapFunSubst(pmgen.condOptimized(guard, next))) setPos extractor.pos + } + + // need to substitute since binder may be used outside of the next extractor call (say, in the body of the case) + case class TypeTestTreeMaker(prevBinder: Symbol, nextBinderTp: Type, pos: Position) extends SimpleTreeMaker { + val extractor = pmgen.condCast(typeTest(prevBinder, nextBinderTp), prevBinder, nextBinderTp) + } - def alternatives(binderToSubst: Symbol, patTrees: Tree*): TreeMaker = - singleBinderWithTp(binderToSubst, binderToSubst.info.widen, patTrees : _*) + // implements the run-time aspects of (§8.2) (typedPattern has already done the necessary type transformations) + case class TypeAndEqualityTestTreeMaker(prevBinder: Symbol, patBinder: Symbol, pt: Type, pos: Position) extends SimpleTreeMaker { + val nextBinderTp = glb(List(patBinder.info.widen, pt)) + val extractor = pmgen.condCast(typeAndEqualityTest(patBinder, pt), patBinder, nextBinderTp) + } - def substOnly(from: List[Symbol], to: List[Tree]): TreeMaker = - new StdTreeMakerImpl(Substitution(from, to)) + // need to substitute to deal with existential types -- TODO: deal with existentials better, don't substitute (see RichClass during quick.comp) + case class EqualityTestTreeMaker(prevBinder: Symbol, patTree: Tree, pos: Position) extends SimpleTreeMaker { + val nextBinderTp: Type = prevBinder.info.widen - def guard(guardTree: Tree): TreeMaker = { - val binder = freshSym(guardTree.pos, UnitClass.tpe) - apply(List(pmgen.guard(guardTree)), binder) - } + // NOTE: generate `patTree == patBinder`, since the extractor must be in control of the equals method (also, patBinder may be null) + // equals need not be well-behaved, so don't intersect with pattern's (stabilized) type (unlike MaybeBoundTyped's accumType, where it's required) + val extractor = atPos(pos)(pmgen.cond(pmgen._equals(patTree, prevBinder), CODE.REF(prevBinder), nextBinderTp)) + } - def combine(treeMakers: List[TreeMaker], body: Tree, pos: Position) = - atPos(pos)(propagateSubstitution(treeMakers).foldRight (body) (_ chainBefore _)) + case class AlternativesTreeMaker(prevBinder: Symbol, alts: Tree*) extends SingleBinderTreeMaker with FreshFunTreeMaker { + val nextBinderTp: Type = prevBinder.info.widen + val pos = alts.head.pos + def chainBefore(next: Tree): Tree = + pmgen.or(wrapFunSubst(next), alts.toList) setPos alts.head.pos + } - private def singleBinderWithTp(binderToSubst: Symbol, binderType: Type, patTrees: Tree*): TreeMaker = { // assert(patTrees.head.pos != NoPosition, "tree for "+(binderToSubst, patTrees.toList)) - val binder = freshSym(patTrees.head.pos, binderType) - TreeMaker(patTrees.toList, binder, List(binderToSubst), List(CODE.REF(binder))) - } + case class GuardTreeMaker(guardTree: Tree) extends SingleExtractorTreeMaker { + val initialSubstitution: Substitution = EmptySubstitution + val nextBinder = freshSym(guardTree.pos, UnitClass.tpe) + val extractor = pmgen.guard(guardTree) + } - // a foldLeft to accumulate the substitution left-to-right, but written using a map and a var for clarity - private def propagateSubstitution(treeMakers: List[TreeMaker]): List[TreeMaker] = { + // combineTreeMakers changes the current substitution's of the tree makers in `treeMakers` + def combineTreeMakers(treeMakers: List[TreeMaker], body: Tree, pos: Position): Tree = { + // a foldLeft to accumulate the initialSubstitution left-to-right, but written using a map and a var for clarity + def propagateSubstitution(treeMakers: List[TreeMaker]): List[TreeMaker] = { var accumSubst: Substitution = EmptySubstitution - treeMakers map { maker => + treeMakers foreach { maker => // could mutate maker instead, but it doesn't seem to shave much time off of quick.comp - val newMaker = maker withOuterSubstitution accumSubst - accumSubst = newMaker.substitution - newMaker + maker addOuterSubstitution accumSubst + accumSubst = maker.substitution } + treeMakers } + + atPos(pos)(propagateSubstitution(treeMakers).foldRight (body) (_ chainBefore _)) + // this optimization doesn't give us much + // var accumSubst: Substitution = EmptySubstitution + // var revMakers: List[TreeMaker] = Nil + // treeMakers foreach { maker => + // accumSubst = accumSubst >> maker.substitution + // maker.substitution = accumSubst + // revMakers ::= maker + // } + // + // var accumTree = body + // revMakers foreach { maker => + // accumTree = maker chainBefore accumTree + // } + // + // atPos(pos)(accumTree) } - abstract class TreeMaker(val substitution: Substitution, funBinder: Symbol = NoSymbol) { - def withOuterSubstitution(outerSubst: Substitution): TreeMaker + def combineCases(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))) + } - // build Tree that chains `next` after the current extractor - def chainBefore(next: Tree): Tree + object Substitution { + def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to)) + // requires sameLength(from, to) + def apply(from: List[Symbol], to: List[Tree]) = + if (from nonEmpty) new Substitution(from, to) else EmptySubstitution + } - // wrap a Fun (with binder funBinder) around the next tree (unless funBinder == NoSymbol) and perform our substitution - protected def wrapFunSubst(next: Tree): Tree = funBinder match { - case NoSymbol => substitution(next) - case b => pmgen.fun(b, substitution(next)) + class Substitution(val from: List[Symbol], val to: List[Tree]) { + def apply(tree: Tree): Tree = typedSubst(tree, from, to) + // forall t: Tree. this(other(t)) == (this >> other)(t) + def >>(other: Substitution): Substitution = { + val (fromFiltered, toFiltered) = (from, to).zipped filter { (f, t) => !other.from.contains(f) } + new Substitution(other.from ++ fromFiltered, other.to.map(apply) ++ toFiltered) // a quick benchmarking run indicates the `.map(apply)` is not too costly } } - // TODO: factor out in SubstTreeMaker, SingleTreeMaker, AltTreeMaker? - class StdTreeMakerImpl(substitution: Substitution, extractors: List[Tree] = Nil, funBinder: Symbol = NoSymbol) extends TreeMaker(substitution, funBinder) { - def withOuterSubstitution(outerSubst: Substitution): StdTreeMakerImpl = - new StdTreeMakerImpl(outerSubst >> substitution, extractors, funBinder) - - // build Tree that chains `next` after the current extractor - def chainBefore(next: Tree): Tree = extractors match { - case Nil => wrapFunSubst(next) - case List(extractor) => pmgen.flatMap(extractor, wrapFunSubst(next)) setPos extractor.pos - case alts => pmgen.or(wrapFunSubst(next), alts) setPos alts.head.pos - } + object EmptySubstitution extends Substitution(Nil, Nil) { + override def apply(tree: Tree): Tree = tree + override def >>(other: Substitution): Substitution = other } - class FilteredTreeMaker(substitution: Substitution, extractor: Tree, guard: Tree, funBinder: Symbol) extends TreeMaker(substitution, funBinder) { - def withOuterSubstitution(outerSubst: Substitution): FilteredTreeMaker = - new FilteredTreeMaker(outerSubst >> substitution, extractor, guard, funBinder) + def matchingMonadType: Type + def typedSubst(tree: Tree, from: List[Symbol], to: List[Tree]): Tree + def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x"): Symbol + def typeAndEqualityTest(patBinder: Symbol, pt: Type): Tree + def typeTest(binder: Symbol, pt: Type): Tree - def chainBefore(next: Tree): Tree = - pmgen.flatMap(extractor, wrapFunSubst(pmgen.condOptimized(guard, next))) setPos extractor.pos + // codegen relevant to the structure of the translation (how extractors are combined) + trait AbsCodeGen { import CODE.UNIT + 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 typedOrElse(pt: Type)(thisCase: Tree, elseCase: Tree): Tree + def guard(c: Tree): Tree + // TODO: defaults in traits + self types == broken? + // def guard(c: Tree, then: Tree, tp: Type): Tree + // def cond(c: Tree): Tree = cond(c, UNIT, NoType) + def cond(c: Tree, then: Tree, tp: Type): Tree + def condOptimized(c: Tree, then: Tree): Tree + def condCast(c: Tree, binder: Symbol, expectedTp: Type): Tree + def _equals(checker: Tree, binder: Symbol): Tree } - 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))) - } + def pmgen: AbsCodeGen } // generate actual trees |