diff options
Diffstat (limited to 'src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala')
| -rw-r--r-- | src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala | 285 |
1 files changed, 285 insertions, 0 deletions
diff --git a/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala new file mode 100644 index 0000000000..ad79562362 --- /dev/null +++ b/src/compiler/scala/tools/nsc/transform/patmat/MatchCodeGen.scala @@ -0,0 +1,285 @@ +/* NSC -- new Scala compiler + * + * Copyright 2011-2013 LAMP/EPFL + * @author Adriaan Moors + */ + +package scala.tools.nsc.transform.patmat + +import scala.tools.nsc.{ast, symtab, typechecker, transform, Global} +import transform._ +import typechecker._ +import symtab._ +import Flags.{MUTABLE, METHOD, LABEL, SYNTHETIC, ARTIFACT} +import scala.language.postfixOps +import scala.tools.nsc.transform.TypingTransformers +import scala.tools.nsc.transform.Transform +import scala.collection.mutable +import scala.reflect.internal.util.Statistics +import scala.reflect.internal.Types +import scala.reflect.internal.util.HashSet + +trait CodeGen { self: PatternMatching => + import PatternMatchingStats._ + val global: Global + import global.{Tree, Type, Symbol, CaseDef, Position, atPos, NoPosition, + Select, Block, ThisType, SingleType, NoPrefix, NoType, definitions, needsOuterTest, + ConstantType, Literal, Constant, gen, This, analyzer, EmptyTree, map2, NoSymbol, Traverser, + Function, Typed, treeInfo, DefTree, ValDef, nme, appliedType, Name, WildcardType, Ident, TypeRef, + UniqueType, RefinedType, currentUnit, SingletonType, singleType, ModuleClassSymbol, + nestedMemberType, TypeMap, EmptyScope, Apply, If, Bind, lub, Alternative, deriveCaseDef, Match, MethodType, LabelDef, TypeTree, Throw, newTermName} + import definitions._ +// import analyzer.{Typer, ErrorUtils, formalTypes} + + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + // generate actual trees + /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + trait CodegenCore extends MatchMonadInterface { + private var ctr = 0 + def freshName(prefix: String) = {ctr += 1; vpmName.counted(prefix, ctr)} + + // assert(owner ne null); assert(owner ne NoSymbol) + def freshSym(pos: Position, tp: Type = NoType, prefix: String = "x") = + NoSymbol.newTermSymbol(freshName(prefix), pos, newFlags = SYNTHETIC) setInfo tp + + def newSynthCaseLabel(name: String) = + NoSymbol.newLabel(freshName(name), NoPosition) setFlag treeInfo.SYNTH_CASE_FLAGS + + // codegen relevant to the structure of the translation (how extractors are combined) + trait AbsCodegen { + def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], matchFailGen: Option[Tree => Tree]): Tree + + // local / context-free + def _asInstanceOf(b: Symbol, tp: Type): Tree + def _equals(checker: Tree, binder: Symbol): Tree + def _isInstanceOf(b: Symbol, tp: Type): Tree + def drop(tgt: Tree)(n: Int): Tree + def index(tgt: Tree)(i: Int): Tree + def mkZero(tp: Type): Tree + def tupleSel(binder: Symbol)(i: Int): Tree + } + + // structure + trait Casegen extends AbsCodegen { import CODE._ + def one(res: Tree): Tree + + def flatMap(prev: Tree, b: Symbol, next: Tree): Tree + def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, next: Tree): Tree + def flatMapGuard(cond: Tree, next: Tree): Tree + def ifThenElseZero(c: Tree, thenp: Tree): Tree = IF (c) THEN thenp ELSE zero + protected def zero: Tree + } + + def codegen: AbsCodegen + + def typesConform(tp: Type, pt: Type) = ((tp eq pt) || (tp <:< pt)) + + // we use subtyping as a model for implication between instanceof tests + // i.e., when S <:< T we assume x.isInstanceOf[S] implies x.isInstanceOf[T] + // unfortunately this is not true in general: + // SI-6022 expects instanceOfTpImplies(ProductClass.tpe, AnyRefClass.tpe) + def instanceOfTpImplies(tp: Type, tpImplied: Type) = { + val tpValue = tp.typeSymbol.isPrimitiveValueClass + + // pretend we're comparing to Any when we're actually comparing to AnyVal or AnyRef + // (and the subtype is respectively a value type or not a value type) + // this allows us to reuse subtyping as a model for implication between instanceOf tests + // the latter don't see a difference between AnyRef, Object or Any when comparing non-value types -- SI-6022 + val tpImpliedNormalizedToAny = + if (tpImplied =:= (if (tpValue) AnyValClass.tpe else AnyRefClass.tpe)) AnyClass.tpe + else tpImplied + + tp <:< tpImpliedNormalizedToAny + } + + abstract class CommonCodegen extends AbsCodegen { import CODE._ + def fun(arg: Symbol, body: Tree): Tree = Function(List(ValDef(arg)), body) + def tupleSel(binder: Symbol)(i: Int): Tree = (REF(binder) DOT nme.productAccessorName(i)) // make tree that accesses the i'th component of the tuple referenced by binder + def index(tgt: Tree)(i: Int): Tree = tgt APPLY (LIT(i)) + def drop(tgt: Tree)(n: Int): Tree = (tgt DOT vpmName.drop) (LIT(n)) + def _equals(checker: Tree, binder: Symbol): Tree = checker MEMBER_== REF(binder) // NOTE: checker must be the target of the ==, that's the patmat semantics for ya + + // the force is needed mainly to deal with the GADT typing hack (we can't detect it otherwise as tp nor pt need contain an abstract type, we're just casting wildly) + def _asInstanceOf(b: Symbol, tp: Type): Tree = if (typesConform(b.info, tp)) REF(b) else gen.mkCastPreservingAnnotations(REF(b), tp) + def _isInstanceOf(b: Symbol, tp: Type): Tree = gen.mkIsInstanceOf(REF(b), tp.withoutAnnotations, true, false) + + // duplicated out of frustration with cast generation + def mkZero(tp: Type): Tree = { + tp.typeSymbol match { + case UnitClass => Literal(Constant()) + case BooleanClass => Literal(Constant(false)) + case FloatClass => Literal(Constant(0.0f)) + case DoubleClass => Literal(Constant(0.0d)) + case ByteClass => Literal(Constant(0.toByte)) + case ShortClass => Literal(Constant(0.toShort)) + case IntClass => Literal(Constant(0)) + case LongClass => Literal(Constant(0L)) + case CharClass => Literal(Constant(0.toChar)) + case _ => gen.mkAsInstanceOf(Literal(Constant(null)), tp, any = true, wrapInApply = false) // the magic incantation is true/false here + } + } + } + } + + trait PureMatchMonadInterface extends MatchMonadInterface { + val matchStrategy: Tree + + def inMatchMonad(tp: Type): Type = appliedType(oneSig, List(tp)).finalResultType + def pureType(tp: Type): Type = appliedType(oneSig, List(tp)).paramTypes.headOption getOrElse NoType // fail gracefully (otherwise we get crashes) + protected def matchMonadSym = oneSig.finalResultType.typeSymbol + + import CODE._ + def _match(n: Name): SelectStart = matchStrategy DOT n + + private lazy val oneSig: Type = typer.typedOperator(_match(vpmName.one)).tpe // TODO: error message + } + + trait PureCodegen extends CodegenCore with PureMatchMonadInterface { + def codegen: AbsCodegen = pureCodegen + + object pureCodegen extends CommonCodegen with Casegen { import CODE._ + //// methods in MatchingStrategy (the monad companion) -- used directly in translation + // __match.runOrElse(`scrut`)(`scrutSym` => `matcher`) + // TODO: consider catchAll, or virtualized matching will break in exception handlers + def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], matchFailGen: Option[Tree => Tree]): Tree = + _match(vpmName.runOrElse) APPLY (scrut) APPLY (fun(scrutSym, cases map (f => f(this)) reduceLeft typedOrElse)) + + // __match.one(`res`) + def one(res: Tree): Tree = (_match(vpmName.one)) (res) + // __match.zero + protected def zero: Tree = _match(vpmName.zero) + // __match.guard(`c`, `then`) + def guard(c: Tree, thenp: Tree): Tree = _match(vpmName.guard) APPLY (c, thenp) + + //// methods in the monad instance -- used directly in translation + // `prev`.flatMap(`b` => `next`) + def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = (prev DOT vpmName.flatMap)(fun(b, next)) + // `thisCase`.orElse(`elseCase`) + def typedOrElse(thisCase: Tree, elseCase: Tree): Tree = (thisCase DOT vpmName.orElse) APPLY (elseCase) + // __match.guard(`cond`, `res`).flatMap(`nextBinder` => `next`) + def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, next: Tree): Tree = flatMap(guard(cond, res), nextBinder, next) + // __match.guard(`guardTree`, ()).flatMap((_: P[Unit]) => `next`) + def flatMapGuard(guardTree: Tree, next: Tree): Tree = flatMapCond(guardTree, CODE.UNIT, freshSym(guardTree.pos, pureType(UnitClass.tpe)), next) + } + } + + trait OptimizedMatchMonadInterface extends MatchMonadInterface { + override def inMatchMonad(tp: Type): Type = optionType(tp) + override def pureType(tp: Type): Type = tp + override protected def matchMonadSym = OptionClass + } + + trait OptimizedCodegen extends CodegenCore with TypedSubstitution with OptimizedMatchMonadInterface { + override def codegen: AbsCodegen = optimizedCodegen + + // when we know we're targetting Option, do some inlining the optimizer won't do + // for example, `o.flatMap(f)` becomes `if(o == None) None else f(o.get)`, similarly for orElse and guard + // this is a special instance of the advanced inlining optimization that takes a method call on + // an object of a type that only has two concrete subclasses, and inlines both bodies, guarded by an if to distinguish the two cases + object optimizedCodegen extends CommonCodegen { import CODE._ + + /** Inline runOrElse and get rid of Option allocations + * + * runOrElse(scrut: scrutTp)(matcher): resTp = matcher(scrut) getOrElse ${catchAll(`scrut`)} + * the matcher's optional result is encoded as a flag, keepGoing, where keepGoing == true encodes result.isEmpty, + * if keepGoing is false, the result Some(x) of the naive translation is encoded as matchRes == x + */ + def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], matchFailGen: Option[Tree => Tree]): Tree = { + val matchEnd = newSynthCaseLabel("matchEnd") + val matchRes = NoSymbol.newValueParameter(newTermName("x"), NoPosition, newFlags = SYNTHETIC) setInfo restpe.withoutAnnotations + matchEnd setInfo MethodType(List(matchRes), restpe) + + def newCaseSym = newSynthCaseLabel("case") setInfo MethodType(Nil, restpe) + var _currCase = newCaseSym + + val caseDefs = cases map { (mkCase: Casegen => Tree) => + val currCase = _currCase + val nextCase = newCaseSym + _currCase = nextCase + + LabelDef(currCase, Nil, mkCase(new OptimizedCasegen(matchEnd, nextCase))) + } + + // must compute catchAll after caseLabels (side-effects nextCase) + // catchAll.isEmpty iff no synthetic default case needed (the (last) user-defined case is a default) + // if the last user-defined case is a default, it will never jump to the next case; it will go immediately to matchEnd + val catchAllDef = matchFailGen map { matchFailGen => + val scrutRef = if(scrutSym ne NoSymbol) REF(scrutSym) else EmptyTree // for alternatives + + LabelDef(_currCase, Nil, matchEnd APPLY (matchFailGen(scrutRef))) + } toList // at most 1 element + + // scrutSym == NoSymbol when generating an alternatives matcher + val scrutDef = if(scrutSym ne NoSymbol) List(VAL(scrutSym) === scrut) else Nil // for alternatives + + // the generated block is taken apart in TailCalls under the following assumptions + // the assumption is once we encounter a case, the remainder of the block will consist of cases + // the prologue may be empty, usually it is the valdef that stores the scrut + // val (prologue, cases) = stats span (s => !s.isInstanceOf[LabelDef]) + Block( + scrutDef ++ caseDefs ++ catchAllDef, + LabelDef(matchEnd, List(matchRes), REF(matchRes)) + ) + } + + class OptimizedCasegen(matchEnd: Symbol, nextCase: Symbol) extends CommonCodegen with Casegen { + def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], matchFailGen: Option[Tree => Tree]): Tree = + optimizedCodegen.matcher(scrut, scrutSym, restpe)(cases, matchFailGen) + + // only used to wrap the RHS of a body + // res: T + // returns MatchMonad[T] + def one(res: Tree): Tree = matchEnd APPLY (res) // a jump to a case label is special-cased in typedApply + protected def zero: Tree = nextCase APPLY () + + // prev: MatchMonad[T] + // b: T + // next: MatchMonad[U] + // returns MatchMonad[U] + def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = { + val tp = inMatchMonad(b.tpe) + val prevSym = freshSym(prev.pos, tp, "o") + val isEmpty = tp member vpmName.isEmpty + val get = tp member vpmName.get + + BLOCK( + VAL(prevSym) === prev, + // must be isEmpty and get as we don't control the target of the call (prev is an extractor call) + ifThenElseZero(NOT(prevSym DOT isEmpty), Substitution(b, prevSym DOT get)(next)) + ) + } + + // cond: Boolean + // res: T + // nextBinder: T + // next == MatchMonad[U] + // returns MatchMonad[U] + def flatMapCond(cond: Tree, res: Tree, nextBinder: Symbol, next: Tree): Tree = { + val rest = + // only emit a local val for `nextBinder` if it's actually referenced in `next` + if (next.exists(_.symbol eq nextBinder)) + BLOCK( + VAL(nextBinder) === res, + next + ) + else next + ifThenElseZero(cond, rest) + } + + // guardTree: Boolean + // next: MatchMonad[T] + // returns MatchMonad[T] + def flatMapGuard(guardTree: Tree, next: Tree): Tree = + ifThenElseZero(guardTree, next) + + def flatMapCondStored(cond: Tree, condSym: Symbol, res: Tree, nextBinder: Symbol, next: Tree): Tree = + ifThenElseZero(cond, BLOCK( + condSym === mkTRUE, + nextBinder === res, + next + )) + } + + } + } +}
\ No newline at end of file |