From 1dbcbd5326a7aae7d5ce9eef87117a18c9ae5240 Mon Sep 17 00:00:00 2001 From: Adriaan Moors Date: Fri, 17 Feb 2012 14:39:45 +0100 Subject: [vpm] PF's missingCase, cleaned up isDefinedAt gen --- src/compiler/scala/reflect/internal/StdNames.scala | 1 + src/compiler/scala/tools/nsc/ast/TreeGen.scala | 83 ++++++++++++-- .../scala/tools/nsc/transform/UnCurry.scala | 127 ++++++++------------- .../tools/nsc/typechecker/PatMatVirtualiser.scala | 5 +- 4 files changed, 122 insertions(+), 94 deletions(-) (limited to 'src/compiler') diff --git a/src/compiler/scala/reflect/internal/StdNames.scala b/src/compiler/scala/reflect/internal/StdNames.scala index 1f67bbc0ac..b4c404a80c 100644 --- a/src/compiler/scala/reflect/internal/StdNames.scala +++ b/src/compiler/scala/reflect/internal/StdNames.scala @@ -330,6 +330,7 @@ trait StdNames extends NameManglers { self: SymbolTable => val freeValue : NameType = "freeValue" val genericArrayOps: NameType = "genericArrayOps" val get: NameType = "get" + val getOrElse: NameType = "getOrElse" val hasNext: NameType = "hasNext" val hashCode_ : NameType = if (forMSIL) "GetHashCode" else "hashCode" val hash_ : NameType = "hash" diff --git a/src/compiler/scala/tools/nsc/ast/TreeGen.scala b/src/compiler/scala/tools/nsc/ast/TreeGen.scala index 265d017653..3467292f28 100644 --- a/src/compiler/scala/tools/nsc/ast/TreeGen.scala +++ b/src/compiler/scala/tools/nsc/ast/TreeGen.scala @@ -13,7 +13,7 @@ import symtab.SymbolTable /** XXX to resolve: TreeGen only assumes global is a SymbolTable, but * TreeDSL at the moment expects a Global. Can we get by with SymbolTable? */ -abstract class TreeGen extends reflect.internal.TreeGen { +abstract class TreeGen extends reflect.internal.TreeGen with TreeDSL { val global: Global import global._ @@ -66,18 +66,81 @@ abstract class TreeGen extends reflect.internal.TreeGen { case _ => tree } - def withDefaultCase(matchExpr: Tree, defaultAction: Tree/*scrutinee*/ => Tree): Tree = matchExpr match { - case Match(scrutinee, cases) => - if (cases exists treeInfo.isDefaultCase) matchExpr - else { - val defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, defaultAction(scrutinee)) - Match(scrutinee, cases :+ defaultCase) + // must be kept in synch with the codegen in PatMatVirtualiser + object VirtualCaseDef { + def unapply(b: Block): Option[(Assign, Tree, Tree)] = b match { + case Block(List(assign@Assign(keepGoingLhs, falseLit), matchRes), zero) => Some((assign, matchRes, zero)) // TODO: check tree annotation + case _ => None + } + } + + // TODO: would be so much nicer if we would know during match-translation (i.e., type checking) + // whether we should emit missingCase-style apply (and isDefinedAt), instead of transforming trees post-factum + class MatchMatcher { + def caseMatch(orig: Tree, selector: Tree, cases: List[CaseDef], wrap: Tree => Tree): Tree = unknownTree(orig) + def caseVirtualizedMatch(orig: Tree, _match: Tree, targs: List[Tree], scrut: Tree, matcher: Tree): Tree = unknownTree(orig) + def caseVirtualizedMatchOpt(orig: Tree, zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], epilogue: Tree, wrap: Tree => Tree): Tree = unknownTree(orig) + + def apply(matchExpr: Tree): Tree = (matchExpr: @unchecked) match { + // old-style match or virtpatmat switch + case Match(selector, cases) => // println("simple match: "+ (selector, cases) + "for:\n"+ matchExpr ) + caseMatch(matchExpr, selector, cases, identity) + // old-style match or virtpatmat switch + case Block((vd: ValDef) :: Nil, orig@Match(selector, cases)) => // println("block match: "+ (selector, cases, vd) + "for:\n"+ matchExpr ) + caseMatch(matchExpr, selector, cases, m => copyBlock(matchExpr, List(vd), m)) + // virtpatmat + case Apply(Apply(TypeApply(Select(tgt, nme.runOrElse), targs), List(scrut)), List(matcher)) if opt.virtPatmat => // println("virt match: "+ (tgt, targs, scrut, matcher) + "for:\n"+ matchExpr ) + caseVirtualizedMatch(matchExpr, tgt, targs, scrut, matcher) + // optimized version of virtpatmat + case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, epilogue) if opt.virtPatmat => // TODO: check tree annotation // println("virtopt match: "+ (zero, x, matchRes, keepGoing, stats) + "for:\n"+ matchExpr ) + caseVirtualizedMatchOpt(matchExpr, zero, x, matchRes, keepGoing, stats, epilogue, identity) + // optimized version of virtpatmat + case Block(outerStats, orig@Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, epilogue)) if opt.virtPatmat => // TODO: check tree annotation // println("virt opt block match: "+ (zero, x, matchRes, keepGoing, stats, outerStats) + "for:\n"+ matchExpr ) + caseVirtualizedMatchOpt(matchExpr, zero, x, matchRes, keepGoing, stats, epilogue, m => copyBlock(matchExpr, outerStats, m)) + case other => + unknownTree(other) + } + + def unknownTree(t: Tree): Tree = throw new MatchError(t) + def copyBlock(orig: Tree, stats: List[Tree], expr: Tree): Block = Block(stats, expr) + + def dropSyntheticCatchAll(cases: List[CaseDef]): List[CaseDef] = + if (!opt.virtPatmat) cases + else cases filter { + case CaseDef(pat, EmptyTree, Throw(Apply(Select(New(exTpt), nme.CONSTRUCTOR), _))) if (treeInfo.isWildcardArg(pat) && (exTpt.tpe.typeSymbol eq MatchErrorClass)) => false + case CaseDef(pat, guard, body) => true + } + } + + def withDefaultCase(matchExpr: Tree, defaultAction: Tree/*scrutinee*/ => Tree): Tree = { + object withDefaultTransformer extends MatchMatcher { + override def caseMatch(orig: Tree, selector: Tree, cases: List[CaseDef], wrap: Tree => Tree): Tree = { + val casesNoSynthCatchAll = dropSyntheticCatchAll(cases) + if (casesNoSynthCatchAll exists treeInfo.isDefaultCase) orig + else { + val defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, defaultAction(selector.duplicate)) + wrap(Match(selector, casesNoSynthCatchAll :+ defaultCase)) + } + } + override def caseVirtualizedMatch(orig: Tree, _match: Tree, targs: List[Tree], scrut: Tree, matcher: Tree): Tree = { import CODE._ + ((matcher APPLY (scrut)) DOT nme.getOrElse) APPLY (defaultAction(scrut.duplicate)) // TODO: pass targs } - case _ => - matchExpr - // [Martin] Adriaan: please fill in virtpatmat transformation here + override def caseVirtualizedMatchOpt(orig: Tree, zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], epilogue: Tree, wrap: Tree => Tree): Tree = { import CODE._ + wrap(Block( + zero :: + x :: + matchRes :: + keepGoing :: + stats, + // replace `if (keepGoing) throw new MatchError(...) else matchRes` by `if (keepGoing) ${defaultAction(`x`)} else matchRes` + (IF (REF(keepGoing.symbol)) THEN defaultAction(x.rhs.duplicate) ELSE REF(matchRes.symbol)) + )) + } + } + withDefaultTransformer(matchExpr) } + def mkCached(cvar: Symbol, expr: Tree): Tree = { val cvarRef = mkUnattributedRef(cvar) Block( diff --git a/src/compiler/scala/tools/nsc/transform/UnCurry.scala b/src/compiler/scala/tools/nsc/transform/UnCurry.scala index 94e562b82f..841cd4a204 100644 --- a/src/compiler/scala/tools/nsc/transform/UnCurry.scala +++ b/src/compiler/scala/tools/nsc/transform/UnCurry.scala @@ -228,9 +228,9 @@ abstract class UnCurry extends InfoTransform * case P_1 if G_1 => E_1 * ... * case P_n if G_n => true - * case _ => this.missingCase(x) + * case _ => this.missingCase(expr) * } - * def isDefinedAtCurrent(x: T): boolean = (x: @unchecked) match { + * def _isDefinedAt(x: T): boolean = (x: @unchecked) match { * case P_1 if G_1 => true * ... * case P_n if G_n => true @@ -240,7 +240,7 @@ abstract class UnCurry extends InfoTransform * new $anon() * * However, if one of the patterns P_i if G_i is a default pattern, - * drop the last default clause in tghe definition of `apply` and generate for `isDefinedAtCurrent` instead + * drop the last default clause in the definition of `apply` and generate for `_isDefinedAt` instead * * def isDefinedAtCurrent(x: T): boolean = true */ @@ -291,80 +291,26 @@ abstract class UnCurry extends InfoTransform val substParam = new TreeSymSubstituter(fun.vparams map (_.symbol), params) def substTree[T <: Tree](t: T): T = substParam(resetLocalAttrs(t)) - // waiting here until we can mix case classes and extractors reliably (i.e., when virtpatmat becomes the default) - // object VirtPatmatOpt { - // object Last { - // def unapply[T](xs: List[T]) = xs.lastOption - // } - // // keep this in synch by what's generated by combineCases/runOrElse - // object MatcherBlock { - // def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree])] = matcher match { // TODO: BUG the unapplySeq version of the case below does not seem to work in virtpatmat?? - // case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) => Some(zero, x, matchRes, keepGoing, stats) - // case _ => None - // } - // } - // // TODO: virtpatmat use case: would be nice if could abstract over the repeated pattern more easily - // // case Block(Last(P)) => - // // case P => - // def unapply(matcher: Tree): Option[(ValDef, ValDef, ValDef, ValDef, List[Tree], Tree => Tree)] = matcher match { - // case MatcherBlock(zero, x, matchRes, keepGoing, stats) => Some(zero, x, matchRes, keepGoing, stats, identity[Tree]) - // case Block(outerStats, MatcherBlock(zero, x, matchRes, keepGoing, stats)) => Some(zero, x, matchRes, keepGoing, stats, inner => Block(outerStats, inner)) - // case b => treeBrowser browse b; None - // } - // } - - // TODO: optimize duplication, but make sure ValDef's introduced by wrap are treated correctly - def dupMatch(selector: Tree, cases: List[CaseDef], wrap: Match => Tree = identity) = { - def transformCase(cdef: CaseDef): CaseDef = - CaseDef(cdef.pat, cdef.guard, Literal(Constant(true))) - def defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, Literal(Constant(false))) - - gen.mkUncheckedMatch( - if (cases exists treeInfo.isDefaultCase) Literal(Constant(true)) - else substTree(wrap(Match(selector, (cases map transformCase) :+ defaultCase)).duplicate) - ) - } + object isDefinedAtTransformer extends gen.MatchMatcher { + // TODO: optimize duplication, but make sure ValDef's introduced by wrap are treated correctly + override def caseMatch(orig: Tree, selector: Tree, cases: List[CaseDef], wrap: Tree => Tree): Tree = { + def transformCase(cdef: CaseDef): CaseDef = + CaseDef(cdef.pat, cdef.guard, Literal(Constant(true))) - def dupVirtMatch(zero: ValDef, x: ValDef, matchRes: ValDef, keepGoing: ValDef, stats: List[Tree], wrap: Block => Tree = identity) = { - 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 Block(List(matchRes, ass@Assign(keepGoingLhs, falseLit)), zero) if keepGoingLhs.symbol eq keepGoing.symbol => - Block(List(ass), zero) - case _ => - super.transform(tree) - } + def defaultCase = CaseDef(Ident(nme.WILDCARD), EmptyTree, Literal(Constant(false))) + + val casesNoSynthCatchAll = dropSyntheticCatchAll(cases) + + gen.mkUncheckedMatch( + if (casesNoSynthCatchAll exists treeInfo.isDefaultCase) Literal(Constant(true)) + else substTree(wrap(Match(selector, (casesNoSynthCatchAll map transformCase) :+ defaultCase)).duplicate) + ) } - 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` by `!keepGoing` - )) - substTree(idaBlock.duplicate) // duplicate on block as a whole to ensure valdefs are properly cloned and substed - } - def dropMatchErrorCatchAll(cases: List[CaseDef]): List[CaseDef] = - if (!opt.virtPatmat) cases - else cases filter { - case CaseDef(pat, EmptyTree, Throw(Apply(Select(New(exTpt), nme.CONSTRUCTOR), _))) if (treeInfo.isWildcardArg(pat) && (exTpt.tpe.typeSymbol eq MatchErrorClass)) => false - case CaseDef(pat, guard, body) => true - } - - DefDef(m, (fun.body: @unchecked) match { - case Match(selector, cases) => - dupMatch(selector, dropMatchErrorCatchAll(cases)) - case Block((vd: ValDef) :: Nil, Match(selector, cases)) => // can't factor this out using an extractor due to bugs in the old pattern matcher - dupMatch(selector, dropMatchErrorCatchAll(cases), m => Block(List(vd), m)) - // virtpatmat -- TODO: find a better way to keep this in synch with the code generated by patmatvirtualizer - case Apply(Apply(TypeApply(Select(tgt, nme.runOrElse), targs), args_scrut), args_pm) if opt.virtPatmat => + 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 = tgt.tpe member newTermName("one") + 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 @@ -374,15 +320,34 @@ abstract class UnCurry extends InfoTransform super.transform(tree) } } - substTree(Apply(Apply(TypeApply(Select(tgt.duplicate, tgt.tpe.member(newTermName("isSuccess"))), targs map (_.duplicate)), args_scrut map (_.duplicate)), args_pm map (noOne.transform))) - // for the optimized version of virtpatmat - case Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _) if opt.virtPatmat => - dupVirtMatch(zero, x, matchRes, keepGoing, stats) - case Block(outerStats, Block((zero: ValDef) :: (x: ValDef) :: (matchRes: ValDef) :: (keepGoing: ValDef) :: stats, _)) if opt.virtPatmat => // can't factor this out using an extractor due to bugs in the old pattern matcher - dupVirtMatch(zero, x, matchRes, keepGoing, stats, m => Block(outerStats, m)) - // case other => - // treeBrowser browse other - }) + 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 + } + } + + DefDef(m, isDefinedAtTransformer(fun.body)) } val members = diff --git a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala index 9bdeb4d387..d31d9ba207 100644 --- a/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala +++ b/src/compiler/scala/tools/nsc/typechecker/PatMatVirtualiser.scala @@ -1701,9 +1701,8 @@ class Foo(x: Other) { x._1 } // no error in this order // only used to wrap the RHS of a body def one(res: Tree, bodyPt: Type, matchPt: Type): Tree = { BLOCK( - if (dontStore(matchPt)) res // runOrElse hasn't been called yet, so matchRes.isMutable is irrelevant, also, tp may be a subtype of resTp used in runOrElse... - else (REF(matchRes) === res), // TODO -- move this statement after the keepGoing-assignment and mark the matchRes-assignment as a tailposition somehow -- _asInstanceOf(res, tp.widen, force = true) - REF(keepGoing) === FALSE, + REF(keepGoing) === FALSE, // comes before assignment to matchRes, so the latter is in tail positions (can ignore the trailing zero -- will disappear when we flatten blocks, which is TODO) + if (dontStore(matchPt)) res else (REF(matchRes) === res), // runOrElse hasn't been called yet, so matchRes.isMutable is irrelevant, also, tp may be a subtype of resTp used in runOrElse... zero // to have a nice lub for lubs -- otherwise we'll get a boxed unit here -- TODO: get rid of all those dangling else zero's ) } -- cgit v1.2.3