diff options
author | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-03-14 11:47:59 +0100 |
---|---|---|
committer | Adriaan Moors <adriaan.moors@epfl.ch> | 2012-03-20 19:54:03 +0100 |
commit | b046a6e3316df8b27ac31e71da1a139c800ccce7 (patch) | |
tree | dfbed2ea5620d100a62bbdf39b93488628e8cbb3 /src | |
parent | 2d3b309a36757545901b99da1b77698749fcc0c5 (diff) | |
download | scala-b046a6e3316df8b27ac31e71da1a139c800ccce7.tar.gz scala-b046a6e3316df8b27ac31e71da1a139c800ccce7.tar.bz2 scala-b046a6e3316df8b27ac31e71da1a139c800ccce7.zip |
[vpm] typer synths Function{} for empty-sel match
typedMatchAnonFun is called from typedFunction when the function's body is a match
this is work-in-progres: the compiler currently won't bootstrap under -Yvirtpatmat
see also the pending test
make sure to use the right context in typeFunction when the body is a Match
when typer is set up for type checking a Function, the current owner is the symbol for the function,
but we'll type check a Block(List(ClassDef(cd)), New(cd)) when the function is a match,
and the function symbol is nowhere to be found, so go to outer context
in patmatvirt:
- simplified default case gen (no need for a Casegen instance)
- using CASE | SYNTHETIC to detect generated matches (for switches) and avoid typing them endlessly
more uniform, and necessary for new-style anon Function class instance gen for matches
Diffstat (limited to 'src')
4 files changed, 281 insertions, 161 deletions
diff --git a/src/compiler/scala/reflect/internal/Trees.scala b/src/compiler/scala/reflect/internal/Trees.scala index 9b1712b790..1a40e0105c 100644 --- a/src/compiler/scala/reflect/internal/Trees.scala +++ b/src/compiler/scala/reflect/internal/Trees.scala @@ -350,8 +350,9 @@ trait Trees extends api.Trees { self: SymbolTable => "subst[%s, %s](%s)".format(fromStr, toStr, (from, to).zipped map (_ + " -> " + _) mkString ", ") } - // NOTE: if symbols in `from` occur multiple times in the `tree` passed to `transform`, - // the resulting Tree will be a graph, not a tree... this breaks all sorts of stuff, + // NOTE: calls shallowDuplicate on trees in `to` to avoid problems when symbols in `from` + // occur multiple times in the `tree` passed to `transform`, + // otherwise, the resulting Tree would be a graph, not a tree... this breaks all sorts of stuff, // notably concerning the mutable aspects of Trees (such as setting their .tpe) class TreeSubstituter(from: List[Symbol], to: List[Tree]) extends Transformer { override def transform(tree: Tree): Tree = tree match { diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala index ee565530b7..03bef83a90 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -237,8 +237,10 @@ abstract class UnCurry extends InfoTransform def targs = fun.tpe.typeArgs def isPartial = fun.tpe.typeSymbol == PartialFunctionClass + // if the function was eta-expanded, it's not a match without a selector if (fun1 ne fun) fun1 else { + assert(!(opt.virtPatmat && isPartial)) // empty-selector matches have already been translated into instantiations of anonymous (partial) functions val (formals, restpe) = (targs.init, targs.last) val anonClass = owner.newAnonymousFunctionClass(fun.pos, inConstructorFlag) def parents = @@ -286,52 +288,54 @@ abstract class UnCurry extends InfoTransform def defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, Literal(Constant(false))) - val casesNoSynthCatchAll = dropSyntheticCatchAll(cases) +// val casesNoSynthCatchAll = dropSyntheticCatchAll(cases) gen.mkUncheckedMatch( - if (casesNoSynthCatchAll exists treeInfo.isDefaultCase) Literal(Constant(true)) - else substTree(wrap(Match(selector, (casesNoSynthCatchAll map transformCase) :+ defaultCase)).duplicate) + if (cases exists treeInfo.isDefaultCase) Literal(Constant(true)) + else substTree(wrap(Match(selector, (cases map transformCase) :+ defaultCase)).duplicate) ) } - override def caseVirtualizedMatch(orig: Tree, _match: Tree, targs: List[Tree], scrut: Tree, matcher: Tree): Tree = { - object noOne extends Transformer { - override val treeCopy = newStrictTreeCopier // must duplicate everything - val one = _match.tpe member newTermName("one") - override def transform(tree: Tree): Tree = tree match { - case Apply(fun, List(a)) if fun.symbol == one => - // blow one's argument away since all we want to know is whether the match succeeds or not - // (the alternative, making `one` CBN, would entail moving away from Option) - Apply(fun.duplicate, List(gen.mkZeroContravariantAfterTyper(a.tpe))) - case _ => - super.transform(tree) - } - } - substTree(Apply(Apply(TypeApply(Select(_match.duplicate, _match.tpe.member(newTermName("isSuccess"))), targs map (_.duplicate)), List(scrut.duplicate)), List(noOne.transform(matcher)))) - } - - override def caseVirtualizedMatchOpt(orig: Tree, zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], epilogue: Tree, wrap: Tree => Tree) = { - object dropMatchResAssign extends Transformer { - // override val treeCopy = newStrictTreeCopier // will duplicate below - override def transform(tree: Tree): Tree = tree match { - // don't compute the result of the match -- remove the block for the RHS (emitted by pmgen.one), except for the assignment to keepGoing - case gen.VirtualCaseDef(assignKeepGoing, matchRes, zero) if assignKeepGoing.lhs.symbol eq keepGoing.symbol => - Block(List(assignKeepGoing), zero) - case _ => - super.transform(tree) - } - } - val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList - val idaBlock = wrap(Block( - zero :: - x :: - /* drop matchRes def */ - keepGoing :: - statsNoMatchRes, - NOT(REF(keepGoing.symbol)) // replace `if (keepGoing) throw new MatchError(...) else matchRes` epilogue by `!keepGoing` - )) - substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed - } + override def caseVirtualizedMatch(orig: Tree, _match: Tree, targs: List[Tree], scrut: Tree, matcher: Tree): Tree = {assert(false); orig} + // { + // object noOne extends Transformer { + // override val treeCopy = newStrictTreeCopier // must duplicate everything + // val one = _match.tpe member newTermName("one") + // override def transform(tree: Tree): Tree = tree match { + // case Apply(fun, List(a)) if fun.symbol == one => + // // blow one's argument away since all we want to know is whether the match succeeds or not + // // (the alternative, making `one` CBN, would entail moving away from Option) + // Apply(fun.duplicate, List(gen.mkZeroContravariantAfterTyper(a.tpe))) + // case _ => + // super.transform(tree) + // } + // } + // substTree(Apply(Apply(TypeApply(Select(_match.duplicate, _match.tpe.member(newTermName("isSuccess"))), targs map (_.duplicate)), List(scrut.duplicate)), List(noOne.transform(matcher)))) + // } + + override def caseVirtualizedMatchOpt(orig: Tree, zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], epilogue: Tree, wrap: Tree => Tree) = {assert(false); orig} + // { + // object dropMatchResAssign extends Transformer { + // // override val treeCopy = newStrictTreeCopier // will duplicate below + // override def transform(tree: Tree): Tree = tree match { + // // don't compute the result of the match -- remove the block for the RHS (emitted by pmgen.one), except for the assignment to keepGoing + // case gen.VirtualCaseDef(assignKeepGoing, matchRes, zero) if assignKeepGoing.lhs.symbol eq keepGoing.symbol => + // Block(List(assignKeepGoing), zero) + // case _ => + // super.transform(tree) + // } + // } + // val statsNoMatchRes: List[Tree] = stats map (dropMatchResAssign.transform) toList + // val idaBlock = wrap(Block( + // zero :: + // x :: + // /* drop matchRes def */ + // keepGoing :: + // statsNoMatchRes, + // NOT(REF(keepGoing.symbol)) // replace `if (keepGoing) throw new MatchError(...) else matchRes` epilogue by `!keepGoing` + // )) + // substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed + // } } DefDef(m, isDefinedAtTransformer(fun.body)) diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala index 0422da54e0..34fefd20fe 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala @@ -49,7 +49,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => } object MatchTranslator { - def apply(typer: Typer): MatchTranslation = { + def apply(typer: Typer): MatchTranslation with CodegenCore = { import typer._ // typing `_match` to decide which MatchTranslator to create adds 4% to quick.comp.timer newTyper(context.makeImplicit(reportAmbiguousErrors = false)).silent(_.typed(Ident(vpmName._match), EXPRmode, WildcardType), reportAmbiguousErrors = false) match { @@ -116,10 +116,6 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => trait MatchTranslation extends MatchMonadInterface { self: TreeMakers with CodegenCore => import typer.{typed, context, silent, reallyExists} - private def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match { - case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args) - case _ => tp - } /** Implement a pattern match by turning its cases (including the implicit failure case) * into the corresponding (monadic) extractors, and combining them with the `orElse` combinator. @@ -131,18 +127,15 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => * thus, you must typecheck the result (and that will in turn translate nested matches) * this could probably optimized... (but note that the matchStrategy must be solved for each nested patternmatch) */ - def translateMatch(scrut: Tree, cases: List[CaseDef], pt: Type): Tree = { + def translateMatch(scrut: Tree, cases: List[CaseDef], pt: Type, scrutType: Type, matchFailGenOverride: Option[Tree => Tree] = None): Tree = { // we don't transform after typers // (that would require much more sophistication when generating trees, // and the only place that emits Matches after typers is for exception handling anyway) assert(phase.id <= currentRun.typerPhase.id, phase) - val scrutType = repeatedToSeq(elimAnonymousClass(scrut.tpe.widen)) - - val scrutSym = freshSym(scrut.pos, pureType(scrutType)) - val okPt = repeatedToSeq(pt) + val scrutSym = freshSym(scrut.pos, pureType(scrutType)) setFlag (Flags.CASE | SYNTHETIC) // the flags allow us to detect generated matches by looking at the scrutinee's symbol (needed to avoid recursing endlessly on generated switches) // pt = Any* occurs when compiling test/files/pos/annotDepMethType.scala with -Xexperimental - combineCases(scrut, scrutSym, cases map translateCase(scrutSym, okPt), okPt, matchOwner) + combineCases(scrut, scrutSym, cases map translateCase(scrutSym, pt), pt, matchOwner, matchFailGenOverride) } // return list of typed CaseDefs that are supported by the backend (typed/bind/wildcard) @@ -154,13 +147,12 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => // if they're already simple enough to be handled by the back-end, we're done if (caseDefs forall treeInfo.isCatchCase) caseDefs else { - val okPt = repeatedToSeq(pt) val switch = { val bindersAndCases = caseDefs map { caseDef => // generate a fresh symbol for each case, hoping we'll end up emitting a type-switch (we don't have a global scrut there) // if we fail to emit a fine-grained switch, have to do translateCase again with a single scrutSym (TODO: uniformize substitution on treemakers so we can avoid this) val caseScrutSym = freshSym(pos, pureType(ThrowableClass.tpe)) - (caseScrutSym, propagateSubstitution(translateCase(caseScrutSym, okPt)(caseDef), EmptySubstitution)) + (caseScrutSym, propagateSubstitution(translateCase(caseScrutSym, pt)(caseDef), EmptySubstitution)) } (emitTypeSwitch(bindersAndCases, pt) map (_.map(fixerUpper(matchOwner, pos).apply(_).asInstanceOf[CaseDef]))) @@ -168,7 +160,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => val catches = switch getOrElse { val scrutSym = freshSym(pos, pureType(ThrowableClass.tpe)) - val casesNoSubstOnly = caseDefs map { caseDef => (propagateSubstitution(translateCase(scrutSym, okPt)(caseDef), EmptySubstitution))} + val casesNoSubstOnly = caseDefs map { caseDef => (propagateSubstitution(translateCase(scrutSym, pt)(caseDef), EmptySubstitution))} val exSym = freshSym(pos, pureType(ThrowableClass.tpe), "ex") @@ -177,7 +169,7 @@ trait PatMatVirtualiser extends ast.TreeDSL { self: Analyzer => CaseDef( Bind(exSym, Ident(nme.WILDCARD)), // TODO: does this need fixing upping? EmptyTree, - combineCasesNoSubstOnly(CODE.REF(exSym), scrutSym, casesNoSubstOnly, pt, matchOwner, casegen => scrut => Throw(CODE.REF(exSym))) + combineCasesNoSubstOnly(CODE.REF(exSym), scrutSym, casesNoSubstOnly, pt, matchOwner, Some(scrut => Throw(CODE.REF(exSym)))) ) }) } @@ -706,10 +698,10 @@ class Foo(x: Other) { x._1 } // no error in this order def optimizeCases(prevBinder: Symbol, cases: List[List[TreeMaker]], pt: Type): (List[List[TreeMaker]], List[Tree]) = (cases, Nil) - def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = + def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type, matchFailGenOverride: Option[Tree => Tree]): Option[Tree] = None - // for catch + // for catch (no need to customize match failure) def emitTypeSwitch(bindersAndCases: List[(Symbol, List[TreeMaker])], pt: Type): Option[List[CaseDef]] = None @@ -925,7 +917,7 @@ class Foo(x: Other) { x._1 } // no error in this order ((casegen: Casegen) => combineExtractors(altTreeMakers :+ TrivialTreeMaker(casegen.one(TRUE)))(casegen)) ) - val findAltMatcher = codegenAlt.matcher(EmptyTree, NoSymbol, BooleanClass.tpe)(combinedAlts, Some((casegen: Casegen) => x => casegen.one(FALSE))) + val findAltMatcher = codegenAlt.matcher(EmptyTree, NoSymbol, BooleanClass.tpe)(combinedAlts, Some(x => FALSE)) codegenAlt.ifThenElseZero(findAltMatcher, substitution(next)) } } @@ -936,6 +928,12 @@ class Foo(x: Other) { x._1 } // no error in this order override def toString = "G("+ guardTree +")" } + // combineExtractors changes the current substitution's of the tree makers in `treeMakers` + // requires propagateSubstitution(treeMakers) has been called + def combineExtractors(treeMakers: List[TreeMaker])(casegen: Casegen): Tree = + treeMakers.foldRight(EmptyTree: Tree)((a, b) => a.chainBefore(b)(casegen)) + + def removeSubstOnly(makers: List[TreeMaker]) = makers filterNot (_.isInstanceOf[SubstOnlyTreeMaker]) // a foldLeft to accumulate the localSubstitution left-to-right @@ -950,42 +948,42 @@ class Foo(x: Other) { x._1 } // no error in this order } // calls propagateSubstitution on the treemakers - def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol): Tree = { - val casesNoSubstOnly = casesRaw map (propagateSubstitution(_, EmptySubstitution)) // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them - combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, casegen => CODE.MATCHERROR(_)) + def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = { + // drops SubstOnlyTreeMakers, since their effect is now contained in the TreeMakers that follow them + val casesNoSubstOnly = casesRaw map (propagateSubstitution(_, EmptySubstitution)) + combineCasesNoSubstOnly(scrut, scrutSym, casesNoSubstOnly, pt, owner, matchFailGenOverride) } - def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFail: Casegen => Tree => Tree): Tree = fixerUpper(owner, scrut.pos){ - val ptDefined = if (isFullyDefined(pt)) pt else NoType - - emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt).getOrElse{ - if (casesNoSubstOnly nonEmpty) { - // check casesNoSubstOnly for presence of a default case, since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one - // exhaustivity and reachability must be checked before optimization as well - // TODO: improve, a trivial type test before the body still makes for a default case - // ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op) - val catchAll = - if (casesNoSubstOnly.nonEmpty && { - val nonTrivLast = casesNoSubstOnly.last - nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker] - }) None - else Some(matchFail) - - val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt) - - val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, catchAll) - - if (toHoist isEmpty) matchRes else Block(toHoist, matchRes) - } else { - codegen.matcher(scrut, scrutSym, pt)(Nil, Some(matchFail)) + def combineCasesNoSubstOnly(scrut: Tree, scrutSym: Symbol, casesNoSubstOnly: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Tree => Tree]): Tree = + fixerUpper(owner, scrut.pos){ + val ptDefined = if (isFullyDefined(pt)) pt else NoType + def matchFailGen = (matchFailGenOverride orElse Some(CODE.MATCHERROR(_: Tree))) + + emitSwitch(scrut, scrutSym, casesNoSubstOnly, pt, matchFailGenOverride).getOrElse{ + if (casesNoSubstOnly nonEmpty) { + // before optimizing, check casesNoSubstOnly for presence of a default case, + // since DCE will eliminate trivial cases like `case _ =>`, even if they're the last one + // exhaustivity and reachability must be checked before optimization as well + // TODO: improve notion of trivial/irrefutable -- a trivial type test before the body still makes for a default case + // ("trivial" depends on whether we're emitting a straight match or an exception, or more generally, any supertype of scrutSym.tpe is a no-op) + // irrefutability checking should use the approximation framework also used for CSE, unreachability and exhaustivity checking + val synthCatchAll = + if (casesNoSubstOnly.nonEmpty && { + val nonTrivLast = casesNoSubstOnly.last + nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker] + }) None + else matchFailGen + + val (cases, toHoist) = optimizeCases(scrutSym, casesNoSubstOnly, pt) + + val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases map combineExtractors, synthCatchAll) + + if (toHoist isEmpty) matchRes else Block(toHoist, matchRes) + } else { + codegen.matcher(scrut, scrutSym, pt)(Nil, matchFailGen) + } } } - } - - // combineExtractors changes the current substitution's of the tree makers in `treeMakers` - // requires propagateSubstitution(treeMakers) has been called - def combineExtractors(treeMakers: List[TreeMaker])(casegen: Casegen): Tree = - treeMakers.foldRight(EmptyTree: Tree)((a, b) => a.chainBefore(b)(casegen)) // TODO: do this during tree construction, but that will require tracking the current owner in treemakers // TODO: assign more fine-grained positions @@ -1043,7 +1041,7 @@ class Foo(x: Other) { x._1 } // no error in this order // 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], catchAllGen: Option[Casegen => Tree => Tree]): Tree + 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 @@ -1136,13 +1134,13 @@ class Foo(x: Other) { x._1 } // no error in this order //// 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], catchAllGen: Option[Casegen => Tree => Tree]): Tree = + 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 - def zero: Tree = _match(vpmName.zero) + protected def zero: Tree = _match(vpmName.zero) // __match.guard(`c`, `then`) def guard(c: Tree, then: Tree): Tree = _match(vpmName.guard) APPLY (c, then) @@ -1517,7 +1515,7 @@ class Foo(x: Other) { x._1 } // no error in this order } } - class RegularSwitchMaker(scrutSym: Symbol) extends SwitchMaker { + class RegularSwitchMaker(scrutSym: Symbol, matchFailGenOverride: Option[Tree => Tree]) extends SwitchMaker { val switchableTpe = Set(ByteClass.tpe, ShortClass.tpe, IntClass.tpe, CharClass.tpe) val alternativesSupported = true @@ -1540,14 +1538,14 @@ class Foo(x: Other) { x._1 } // no error in this order } def defaultSym: Symbol = scrutSym - def defaultBody: Tree = { import CODE._; MATCHERROR(REF(scrutSym)) } + def defaultBody: Tree = { import CODE._; matchFailGenOverride map (gen => gen(REF(scrutSym))) getOrElse MATCHERROR(REF(scrutSym)) } def defaultCase(scrutSym: Symbol = defaultSym, body: Tree = defaultBody): CaseDef = { import CODE._; atPos(body.pos) { DEFAULT ==> body }} } - override def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type): Option[Tree] = { import CODE._ - val regularSwitchMaker = new RegularSwitchMaker(scrutSym) + override def emitSwitch(scrut: Tree, scrutSym: Symbol, cases: List[List[TreeMaker]], pt: Type, matchFailGenOverride: Option[Tree => Tree]): Option[Tree] = { import CODE._ + val regularSwitchMaker = new RegularSwitchMaker(scrutSym, matchFailGenOverride) // TODO: if patterns allow switch but the type of the scrutinee doesn't, cast (type-test) the scrutinee to the corresponding switchable type and switch on the result if (regularSwitchMaker.switchableTpe(scrutSym.tpe)) { val caseDefsWithDefault = regularSwitchMaker(cases map {c => (scrutSym, c)}, pt) @@ -1555,7 +1553,7 @@ class Foo(x: Other) { x._1 } // no error in this order else { // match on scrutSym -- converted to an int if necessary -- not on scrut directly (to avoid duplicating scrut) val scrutToInt: Tree = - if(scrutSym.tpe =:= IntClass.tpe) REF(scrutSym) + if (scrutSym.tpe =:= IntClass.tpe) REF(scrutSym) else (REF(scrutSym) DOT (nme.toInt)) Some(BLOCK( VAL(scrutSym) === scrut, @@ -1631,7 +1629,7 @@ class Foo(x: Other) { x._1 } // no error in this order * 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], catchAllGen: Option[Casegen => Tree => Tree]): Tree = { + def matcher(scrut: Tree, scrutSym: Symbol, restpe: Type)(cases: List[Casegen => Tree], matchFailGen: Option[Tree => Tree]): Tree = { val matchEnd = NoSymbol.newLabel(freshName("matchEnd"), NoPosition) setFlag (SYNTHETIC | Flags.CASE) val matchRes = NoSymbol.newValueParameter(newTermName("x"), NoPosition, SYNTHETIC) setInfo restpe matchEnd setInfo MethodType(List(matchRes), restpe) @@ -1645,38 +1643,35 @@ class Foo(x: Other) { x._1 } // no error in this order LabelDef(currCase, Nil, mkCase(casegen)) } - def catchAll = catchAllGen map { catchAllGen => - val casegen = new OptimizedCasegen(matchEnd, NoSymbol) - val scrutRef = if(scrutSym eq NoSymbol) EmptyTree else REF(scrutSym) - LabelDef(nextCase, Nil, catchAllGen(casegen)(scrutRef)) + def catchAll = matchFailGen map { matchFailGen => + val scrutRef = if(scrutSym ne NoSymbol) REF(scrutSym) else EmptyTree // for alternatives + LabelDef(nextCase, Nil, matchEnd APPLY (matchFailGen(scrutRef))) // need to jump to matchEnd with result generated by matchFailGen (could be `FALSE` for isDefinedAt) } toList + // 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 // 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]) - val prologue = if(scrutSym ne NoSymbol) List(VAL(scrutSym) === scrut) else Nil + // scrutSym == NoSymbol when generating an alternatives matcher + val scrutDef = if(scrutSym ne NoSymbol) List(VAL(scrutSym) === scrut) else Nil // for alternatives Block( - prologue ++ (cases map caseDef) ++ catchAll, + scrutDef ++ (cases map caseDef) ++ catchAll, 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], catchAllGen: Option[Casegen => Tree => Tree]): Tree = - optimizedCodegen.matcher(scrut, scrutSym, restpe)(cases, catchAllGen) - - def zero: Tree = nextCase APPLY () + 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) - - - override def ifThenElseZero(c: Tree, then: Tree): Tree = - IF (c) THEN then ELSE zero + protected def zero: Tree = nextCase APPLY () // prev: MatchMonad[T] // b: T diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index 0dd4b37131..506e347828 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -2143,6 +2143,137 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { newTyper(context.makeNewScope(cdef, context.owner)).typedCase(cdef, pattp, pt) } + def adaptCase(cdef: CaseDef, mode: Int, tpe: Type): CaseDef = deriveCaseDef(cdef)(adapt(_, mode, tpe)) + + def translateMatch(selector: Tree, cases: List[CaseDef], mode: Int, resTp: Type, scrutTp: Type = NoType, matchFailGen: Option[Tree => Tree] = None) = { + val selector1 = if(scrutTp eq NoType) checkDead(typed(selector, EXPRmode | BYVALmode, WildcardType)) else selector + val selectorTp = if(scrutTp eq NoType) packCaptured(selector1.tpe.widen) else scrutTp + val casesTyped = typedCases(cases, selectorTp, resTp) + val (ownType, needAdapt) = if (isFullyDefined(resTp)) (resTp, false) else weakLub(casesTyped map (_.tpe.deconst)) + val casesAdapted = if (!needAdapt) casesTyped else casesTyped map (adaptCase(_, mode, ownType)) + // val (owntype0, needAdapt) = ptOrLub(casesTyped map (x => repackExistential(x.tpe))) + // val owntype = elimAnonymousClass(owntype0) + + def repeatedToSeq(tp: Type): Type = (tp baseType RepeatedParamClass) match { + case TypeRef(_, RepeatedParamClass, args) => appliedType(SeqClass.typeConstructor, args) + case _ => tp + } + + def isSynthSelector(selector: Tree): Boolean = selector match { + case Ident(_) if selector.symbol.hasFlag(SYNTHETIC | CASE) => true + case Select(sel, nme.toInt) => isSynthSelector(sel) // switch may need to convert to int first + case _ => false + } + + if (isSynthSelector(selector1)) { // a switch + (Match(selector1, casesAdapted) setType ownType, ownType) // setType of the Match to avoid recursing endlessly + } else { + val scrutType = repeatedToSeq(elimAnonymousClass(selectorTp)) + (MatchTranslator(this).translateMatch(selector1, casesAdapted, repeatedToSeq(ownType), scrutType, matchFailGen), ownType) + } + } + + // TODO: use this to synthesize (partial)function implementation for matches from the get-go, + // instead of the dirty post-factum hacks in uncurry -- typedMatchAnonFun is currently not used due to mindboggling failures (see virtpatmat_anonfun_for.scala) + def typedMatchAnonFun(tree: Tree, cases: List[CaseDef], mode: Int, pt0: Type, selOverride: Option[(List[Symbol], Tree)] = None) = { + val pt = deskolemizeGADTSkolems(pt0) + val targs = pt.normalize.typeArgs + val arity = if (isFunctionType(pt)) targs.length - 1 else 1 + val scrutTp0 = if (arity == 1) targs.head else /* arity > 1 */ tupleType(targs.init) + val scrutTp = packCaptured(scrutTp0) + val ptRes = targs.last // may not be fully defined + val isPartial = pt.typeSymbol == PartialFunctionClass + val cname = tpnme.ANON_FUN_NAME + val funThis = This(cname) + // used to create a new context for pattern matching translation so that + // we can easily rejig the owner structure when we have the actual symbols for these methods + // (after type checking them, but type checking requires translation -- this seems like the easiest way to end this vicious cycle) + val applySentinel = NoSymbol.newMethod(nme.apply) + val idaSentinel = NoSymbol.newMethod(nme._isDefinedAt) + + def mkParams = { + val params = + for (i <- List.range(0, arity)) yield atPos(tree.pos.focusStart) { + ValDef(Modifiers(SYNTHETIC | PARAM), unit.freshTermName("x" + i + "$"), TypeTree(), EmptyTree) + } + val ids = params map (p => Ident(p.name)) + + val paramsRef = selOverride match { + case None => atPos(tree.pos.focusStart) { if (arity == 1) ids.head else gen.mkTuple(ids) } + case Some((_, sel)) => sel.duplicate // we'll replace the symbols that refer to the function's original syms by the ones introduced by the DefDef once the method's been type checked (until then, we don't know them) + } + + (params, paramsRef) // paramsRef can't be typed until after match has been translated, thus supply explicit scrutTp to translate below + } + + import CODE._ + + // need to duplicate the cases before typing them to generate the apply method, or the symbols will be all messed up + val casesTrue = if (isPartial) cases map (c => deriveCaseDef(c)(x => TRUE).duplicate) else Nil + + val (applyMethod, parents) = { + val (params, paramsRef) = mkParams + val (body, resTp) = newTyper(context.make(context.tree, applySentinel)).translateMatch(paramsRef, cases, mode, ptRes, scrutTp, if (isPartial) Some(scrut => (funThis DOT nme.missingCase) (scrut)) else None) + + def abstractFunctionType = { + val sym = AbstractFunctionClass(arity) + typeRef(sym.typeConstructor.prefix, sym, targs.init :+ resTp) + } + + val parents = + if (isFunctionType(pt)) List(abstractFunctionType, SerializableClass.tpe) + else if (isPartial) List(appliedType(AbstractPartialFunctionClass.typeConstructor, List(scrutTp, resTp)), SerializableClass.tpe) + else List(ObjectClass.tpe, pt, SerializableClass.tpe) + + (atPos(tree.pos.focus)(DefDef(Modifiers(FINAL), nme.apply, Nil, List(params), TypeTree() setType resTp, body)), parents) + } + + def isDefinedAtMethod = { + val (params, paramsRef) = mkParams + val (body, _) = newTyper(context.make(context.tree, idaSentinel)).translateMatch(paramsRef, casesTrue, mode, BooleanClass.tpe, scrutTp, Some(scrutinee => FALSE)) + atPos(tree.pos.focus)( + DefDef(Modifiers(FINAL), nme._isDefinedAt, Nil, List(params), TypeTree() setType BooleanClass.tpe, body) + ) + } + + val members = if (!isPartial) List(applyMethod) else List(applyMethod, isDefinedAtMethod) + + val cmods = Modifiers(FINAL | SYNTHETIC /*TODO: when do we need INCONSTRUCTOR ?*/) withAnnotations ( + List(NEW(SerialVersionUIDAttr, LIT(0)))) + val cdef = + ClassDef(cmods, cname, Nil, + Template(parents map (TypeTree() setType _), emptyValDef, Modifiers(0), Nil, List(Nil), members, tree.pos) + ) + val funInst = (Block(List(cdef), Apply(Select(New(Ident(cname)), nme.CONSTRUCTOR), Nil))) + + val res = typed(funInst, mode, pt) + + // now that we have the symbols corresponding to the apply/isDefinedAt methods, + // we can fix up the result of fixerUpper... URGH + // fixerUpper nests the top-level definitions generated in the match under context.owner, but they should be owner by the apply/isDefinedAt method + res foreach { + case d: DefDef if (d.symbol.name == nme.apply) => + d.rhs.changeOwner(applySentinel -> d.symbol) + case d: DefDef if (d.symbol.name == nme._isDefinedAt) => + d.rhs.changeOwner(idaSentinel -> d.symbol) + case _ => + } + + selOverride match { + case None => res + case Some((paramSyms, sel)) => + object substParamSyms extends Transformer { + override def transform(t: Tree): Tree = t match { + case d: DefDef if (d.symbol.name == nme.apply) || (d.symbol.name == nme._isDefinedAt) && (d.symbol.owner == res.tpe.typeSymbol) => + deriveDefDef(d)(rhs => rhs.substTreeSyms(paramSyms, d.vparamss.head.map(_.symbol))) + case _ => + super.transform(t) + } + } + substParamSyms.transform(res) + } + } + /** * @param fun ... * @param mode ... @@ -2155,14 +2286,10 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { return MaxFunctionArityError(fun) def decompose(pt: Type): (Symbol, List[Type], Type) = - if ((isFunctionType(pt) - || - pt.typeSymbol == PartialFunctionClass && - numVparams == 1 && fun.body.isInstanceOf[Match]) - && // see bug901 for a reason why next conditions are needed - (pt.normalize.typeArgs.length - 1 == numVparams - || - fun.vparams.exists(_.tpt.isEmpty))) + if ((isFunctionType(pt) || (pt.typeSymbol == PartialFunctionClass && numVparams == 1 && fun.body.isInstanceOf[Match])) && // see bug901 for a reason why next conditions are needed + ( pt.normalize.typeArgs.length - 1 == numVparams + || fun.vparams.exists(_.tpt.isEmpty) + )) (pt.typeSymbol, pt.normalize.typeArgs.init, pt.normalize.typeArgs.last) else (FunctionClass(numVparams), fun.vparams map (x => NoType), WildcardType) @@ -2204,13 +2331,27 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { // for (vparam <- vparams) { // checkNoEscaping.locals(context.scope, WildcardType, vparam.tpt); () // } - val body1 = typed(fun.body, respt) - val formals = vparamSyms map (_.tpe) - val restpe = packedType(body1, fun.symbol).deconst.resultType - val funtpe = typeRef(clazz.tpe.prefix, clazz, formals :+ restpe) -// body = checkNoEscaping.locals(context.scope, restpe, body) - treeCopy.Function(fun, vparams, body1).setType(funtpe) - } + + def recompose(from: Type, to: Type) = + if(clazz == PartialFunctionClass) appliedType(PartialFunctionClass.typeConstructor, List(from, to)) + else functionType(List(from), to) + + fun.body match { + case Match(sel, cases) if opt.virtPatmat => + val typedSel = typed(sel, EXPRmode | BYVALmode, WildcardType) + // go to outer context -- must discard the context that was created for the Function since we're discarding the function + // thus, its symbol, which serves as the current context.owner, is not the right owner + // you won't know you're using the wrong owner until lambda lift crashes (unless you know better than to use the wrong owner) + newTyper(context.outer).typedMatchAnonFun(fun, cases, mode, recompose(typedSel.tpe, respt), Some((vparamSyms, typedSel))) + case _ => + val body1 = typed(fun.body, respt) + val formals = vparamSyms map (_.tpe) + val restpe = packedType(body1, fun.symbol).deconst.resultType + val funtpe = typeRef(clazz.tpe.prefix, clazz, formals :+ restpe) + // body = checkNoEscaping.locals(context.scope, restpe, body) + treeCopy.Function(fun, vparams, body1).setType(funtpe) + } + } } def typedRefinement(stats: List[Tree]) { @@ -3431,7 +3572,10 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { } def typedMatch(tree: Tree, selector: Tree, cases: List[CaseDef]): Tree = { - if (selector == EmptyTree) { + if (opt.virtPatmat && !isPastTyper) { + if (selector ne EmptyTree) typed(translateMatch(selector, cases, mode, pt)._1, mode, pt) + else typedMatchAnonFun(tree, cases, mode, pt) + } else if (selector == EmptyTree) { val arity = if (isFunctionType(pt)) pt.normalize.typeArgs.length - 1 else 1 val params = for (i <- List.range(0, arity)) yield atPos(tree.pos.focusStart) { @@ -3445,32 +3589,11 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { } else { val selector1 = checkDead(typed(selector, EXPRmode | BYVALmode, WildcardType)) var cases1 = typedCases(cases, packCaptured(selector1.tpe.widen), pt) - - if (isPastTyper || !opt.virtPatmat) { - val (owntype, needAdapt) = ptOrLub(cases1 map (_.tpe)) - if (needAdapt) { - cases1 = cases1 map (adaptCase(_, owntype)) - } - treeCopy.Match(tree, selector1, cases1) setType owntype - } else { // don't run translator after typers (see comments in PatMatVirtualiser) - val (owntype0, needAdapt) = ptOrLub(cases1 map (x => repackExistential(x.tpe))) - val owntype = elimAnonymousClass(owntype0) - if (needAdapt) cases1 = cases1 map (adaptCase(_, owntype)) - - (MatchTranslator(this)).translateMatch(selector1, cases1, owntype) match { - case Block(vd :: Nil, tree@Match(selector, cases)) => - val selector1 = checkDead(typed(selector, EXPRmode | BYVALmode, WildcardType)) - var cases1 = typedCases(cases, packCaptured(selector1.tpe.widen), pt) - val (owntype, needAdapt) = ptOrLub(cases1 map (_.tpe)) - if (needAdapt) - cases1 = cases1 map (adaptCase(_, owntype)) - typed(Block(vd :: Nil, treeCopy.Match(tree, selector1, cases1) setType owntype)) - case translated => - // TODO: get rid of setType owntype -- it should all typecheck - // must call typed, not typed1, or we overflow the stack when emitting switches - typed(translated, mode, WildcardType) setType owntype - } + val (owntype, needAdapt) = ptOrLub(cases1 map (_.tpe)) + if (needAdapt) { + cases1 = cases1 map (adaptCase(_, mode, owntype)) } + treeCopy.Match(tree, selector1, cases1) setType owntype } } @@ -4240,9 +4363,6 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { } } - def adaptCase(cdef: CaseDef, tpe: Type): CaseDef = - deriveCaseDef(cdef)(adapt(_, mode, tpe)) - // begin typed1 val sym: Symbol = tree.symbol if ((sym ne null) && (sym ne NoSymbol)) sym.initialize @@ -4351,7 +4471,7 @@ trait Typers extends Modes with Adaptations with PatMatVirtualiser { val (owntype, needAdapt) = ptOrLub(block1.tpe :: (catches1 map (_.tpe))) if (needAdapt) { block1 = adapt(block1, mode, owntype) - catches1 = catches1 map (adaptCase(_, owntype)) + catches1 = catches1 map (adaptCase(_, mode, owntype)) } if(!isPastTyper && opt.virtPatmat) { |