aboutsummaryrefslogtreecommitdiff
path: root/src/dotty
diff options
context:
space:
mode:
Diffstat (limited to 'src/dotty')
-rw-r--r--src/dotty/tools/dotc/transform/PatternMatcher.scala190
1 files changed, 74 insertions, 116 deletions
diff --git a/src/dotty/tools/dotc/transform/PatternMatcher.scala b/src/dotty/tools/dotc/transform/PatternMatcher.scala
index f3fca47d0..de2503b6a 100644
--- a/src/dotty/tools/dotc/transform/PatternMatcher.scala
+++ b/src/dotty/tools/dotc/transform/PatternMatcher.scala
@@ -138,73 +138,28 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
}
- object Substitution {
- def apply(from: Symbol, to: Tree) = new Substitution(List(from), List(to))
+ object Rebindings {
+ def apply(from: Symbol, to: Symbol) = new Rebindings(List(from), List(ref(to)))
// requires sameLength(from, to)
def apply(from: List[Symbol], to: List[Tree]) =
- if (from nonEmpty) new Substitution(from, to) else EmptySubstitution
+ if (from nonEmpty) new Rebindings(from, to) else NoRebindings
}
- class Substitution(val from: List[Symbol], val to: List[Tree]) {
-
- // We must explicitly type the trees that we replace inside some other tree, since the latter may already have been typed,
- // and will thus not be retyped. This means we might end up with untyped subtrees inside bigger, typed trees.
- def apply(tree: Tree): Tree = {
- // according to -Ystatistics 10% of translateMatch's time is spent in this method...
- // since about half of the typedSubst's end up being no-ops, the check below shaves off 5% of the time spent in typedSubst
- /*if (!tree.exists { case i@Ident(_) => from contains i.symbol case _ => false}) tree
- else*/
-
- var replaced = 0
- val toAdapted = (from zip to) map {
- case (orig, nw) =>
- if (nw.tpe <:< orig.info) nw else nw.ensureConforms(orig.info & nw.tpe)
- }
-
- val identReplace: Ident => Tree = { ident =>
- def subst(from: List[Symbol], to: List[Tree]): Tree =
- if (from.isEmpty) ident
- else if (ident.symbol == from.head) {
- replaced += 1
- to.head //typedIfOrigTyped(to.head.shallowDuplicate.setPos(tree.pos), tree.tpe)
- }
- else subst(from.tail, to.tail)
- subst(from, toAdapted)
- }
- val start = System.currentTimeMillis()
- val res = new tpd.TreeMap() {
- override def transform(tree: tpd.Tree)(implicit ctx: Context): tpd.Tree = tree match{
- case s: Ident => identReplace(s)
- case _ => super.transform(tree)
- }
- }.transform(tree)
- //new TreeTypeMap(treeMap = identReplace/*, substFrom = from, substTo = to.map(_.symbol)*/).transform(tree)
-
- ctx.debuglog(s"${id} TreeTM replacing ${from.size} elems took ${(System.currentTimeMillis() - start)/1000.0} replaced:$replaced")
- def treeSize = new ShallowFolder[Int]((a,b) => a + 1).apply(0, tree)
-
- ctx.debuglog(s"location: ${ctx.owner.showFullName}, size: ${treeSize}")
- res
- }
-
-
- // the substitution that chains `other` before `this` substitution
- // forall t: Tree. this(other(t)) == (this >> other)(t)
- def >>(other: Substitution): Substitution = {
- if (other == EmptySubstitution) this
- else if (this == EmptySubstitution) other
+ class Rebindings(val lhs: List[Symbol], val rhs: List[Tree]) {
+ def >>(other: Rebindings) = {
+ if (other eq NoRebindings) this
+ else if (this eq NoRebindings) other
else {
- 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
+ assert((lhs.toSet ++ other.lhs.toSet).size == lhs.length + other.lhs.length, "no double assignments")
+ new Rebindings(this.lhs ++ other.lhs, this.rhs ++ other.rhs)
}
}
- override def toString = (from.map(_.name) zip to) mkString("Substitution(", ", ", ")")
- }
- object EmptySubstitution extends Substitution(Nil, Nil) {
- override def apply(tree: Tree): Tree = tree
- override def >>(other: Substitution): Substitution = other
+ def emitValDefs: List[ValDef] = {
+ Collections.map2(lhs, rhs)((symbol, tree) => ValDef(symbol.asTerm, tree.ensureConforms(symbol.info)))
+ }
}
+ object NoRebindings extends Rebindings(Nil, Nil)
trait OptimizedCodegen extends CodegenCore {
@@ -271,25 +226,27 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
// next: MatchMonad[U]
// returns MatchMonad[U]
def flatMap(prev: Tree, b: Symbol, next: Tree): Tree = {
- val prevSym = freshSym(prev.pos, prev.tpe, "o")
+
val getTp = extractorMemberType(prev.tpe, nme.get)
val isDefined = extractorMemberType(prev.tpe, nme.isDefined)
if ((isDefined isRef defn.BooleanClass) && getTp.exists) {
- val prevValue = ref(prevSym).select("get".toTermName).ensureApplied
+ val tmpSym = freshSym(prev.pos, prev.tpe, "o")
+ val prevValue = ref(tmpSym).select("get".toTermName).ensureApplied
+
Block(
- List(ValDef(prevSym, prev)),
+ List(ValDef(tmpSym, prev)),
// must be isEmpty and get as we don't control the target of the call (prev is an extractor call)
ifThenElseZero(
- ref(prevSym).select(nme.isDefined),
- Substitution(b, prevValue)(next)
+ ref(tmpSym).select(nme.isDefined),
+ Block(List(ValDef(b.asTerm, prevValue)), next)
)
)
} else {
assert(defn.isProductSubType(prev.tpe))
Block(
- List(ValDef(prevSym, prev)),
- Substitution(b, ref(prevSym))(next)
+ List(ValDef(b.asTerm, prev)),
+ next //Substitution(b, ref(prevSym))(next)
)
}
}
@@ -342,23 +299,23 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
abstract class TreeMaker {
def pos: Position
- private[this] var currSub: Substitution = null
+ private[this] var currSub: Rebindings = null
/** captures the scope and the value of the bindings in patterns
* important *when* the substitution happens (can't accumulate and do at once after the full matcher has been constructed)
*/
- def substitution: Substitution =
- if (currSub eq null) localSubstitution
+ def rebindings: Rebindings =
+ if (currSub eq null) introducedRebindings
else currSub
- protected def localSubstitution: Substitution
+ protected def introducedRebindings: Rebindings
- private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
+ private[TreeMakers] def incorporateOuterRebinding(outerSubst: Rebindings): Unit = {
if (currSub ne null) {
- ctx.debuglog("BUG: incorporateOuterSubstitution called more than once for "+ ((this, currSub, outerSubst)))
+ ctx.debuglog("BUG: incorporateOuterRebinding called more than once for "+ ((this, currSub, outerSubst)))
Thread.dumpStack()
}
- else currSub = outerSubst >> substitution
+ else currSub = outerSubst >> rebindings
}
/** The substitution that specifies the trees that compute the values of the subpattern binders.
@@ -373,14 +330,14 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
* TODO: clean this up, would be nicer to have some higher-level way to compute
* the binders bound by this tree maker and the symbolic values that correspond to them
*/
- def subPatternsAsSubstitution: Substitution = substitution
+ def subPatternsAsRebindings: Rebindings = rebindings
// build Tree that chains `next` after the current extractor
def chainBefore(next: Tree)(casegen: Casegen): Tree
}
sealed trait NoNewBinders extends TreeMaker {
- protected val localSubstitution: Substitution = EmptySubstitution
+ protected val introducedRebindings: Rebindings = NoRebindings
}
case class TrivialTreeMaker(tree: Tree) extends TreeMaker with NoNewBinders {
@@ -393,7 +350,7 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
def pos = body.pos
def chainBefore(next: Tree)(casegen: Casegen): Tree = // assert(next eq EmptyTree)
- /*atPos(body.pos)*/(casegen.one(substitution(body))) // since SubstOnly treemakers are dropped, need to do it here
+ /*atPos(body.pos)*/(casegen.one(body)) // since SubstOnly treemakers are dropped, need to do it here
override def toString = "B"+((body, matchPt))
}
@@ -419,8 +376,8 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
case class SubstOnlyTreeMaker(prevBinder: Symbol, nextBinder: Symbol) extends TreeMaker {
val pos = Positions.NoPosition
- val localSubstitution = EmptySubstitution
- def chainBefore(next: Tree)(casegen: Casegen): Tree = Block(List(ValDef(prevBinder.asTerm, ref(nextBinder))), next)
+ val introducedRebindings = Rebindings(prevBinder, nextBinder)
+ def chainBefore(next: Tree)(casegen: Casegen): Tree = next
//override def toString = "S" + localSubstitution
}
@@ -436,12 +393,12 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
val res: Tree
val nextBinder: Symbol
- lazy val localSubstitution =
- if(nextBinder ne prevBinder) Substitution(List(prevBinder), List(ref(nextBinder)))
- else EmptySubstitution
+ lazy val introducedRebindings =
+ if(nextBinder ne prevBinder) Rebindings(prevBinder, nextBinder)
+ else NoRebindings
def chainBefore(next: Tree)(casegen: Casegen): Tree =
- /*atPos(pos)(*/casegen.flatMapCond(cond, res, nextBinder, substitution(next))//)
+ /*atPos(pos)(*/casegen.flatMapCond(cond, res, nextBinder, next)//)
}
// unless we're optimizing, emit local variable bindings for all subpatterns of extractor/case class patterns
@@ -469,10 +426,10 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
private lazy val (stored, substed) = (subPatBinders, subPatRefs).zipped.partition{ case (sym, _) => storedBinders(sym) }
- protected lazy val localSubstitution: Substitution = if (!emitVars) Substitution(subPatBinders, subPatRefs)
+ protected lazy val introducedRebindings: Rebindings = if (!emitVars) Rebindings(subPatBinders, subPatRefs)
else {
val (subPatBindersSubstituted, subPatRefsSubstituted) = substed.unzip
- Substitution(subPatBindersSubstituted.toList, subPatRefsSubstituted.toList)
+ Rebindings(subPatBindersSubstituted.toList, subPatRefsSubstituted.toList)
}
/** The substitution that specifies the trees that compute the values of the subpattern binders.
@@ -480,8 +437,8 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
* We pretend to replace the subpattern binders by subpattern refs
* (Even though we don't do so anymore -- see SI-5158, SI-5739 and SI-6070.)
*/
- override def subPatternsAsSubstitution =
- Substitution(subPatBinders, subPatRefs) >> super.subPatternsAsSubstitution
+ override def subPatternsAsRebindings =
+ Rebindings(subPatBinders, subPatRefs) >> super.subPatternsAsRebindings
def bindSubPats(in: Tree): Tree =
if (!emitVars) in
@@ -549,13 +506,13 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
def chainBefore(next: Tree)(casegen: Casegen): Tree = {
val condAndNext = extraCond match {
case Some(cond: Tree) =>
- casegen.ifThenElseZero(substitution(cond), bindSubPats(substitution(next)))
+ casegen.ifThenElseZero(cond, bindSubPats(next))
case _ =>
- bindSubPats(substitution(next))
+ bindSubPats(next)
}
if (extractorReturnsBoolean) casegen.flatMapCond(extractor, unitLiteral, nextBinder, condAndNext)
- else casegen.flatMap(extractor, nextBinder, condAndNext)
+ else casegen.flatMap(extractor, nextBinder, condAndNext) // getType?
}
@@ -605,13 +562,13 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
cond match {
case Some(cond: Tree) =>
- casegen.ifThenElseZero(cond, bindSubPats(substitution(next)))
+ casegen.ifThenElseZero(cond, bindSubPats(next))
case _ =>
- bindSubPats(substitution(next))
+ bindSubPats(next)
}
}
- override def toString = "P"+((prevBinder.name, extraCond getOrElse "", localSubstitution))
+ override def toString = "P"+((prevBinder.name, extraCond getOrElse "", introducedRebindings))
}
object IrrefutableExtractorTreeMaker {
@@ -747,7 +704,7 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
}
}
- override lazy val localSubstitution: Substitution = EmptySubstitution
+ override lazy val introducedRebindings = NoRebindings
def outerTestNeeded = {
val np = expectedTp.normalizedPrefix
@@ -842,9 +799,9 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
case class AlternativesTreeMaker(prevBinder: Symbol, var altss: List[List[TreeMaker]], pos: Position) extends TreeMaker with NoNewBinders {
// don't substitute prevBinder to nextBinder, a set of alternatives does not need to introduce a new binder, simply reuse the previous one
- override private[TreeMakers] def incorporateOuterSubstitution(outerSubst: Substitution): Unit = {
- super.incorporateOuterSubstitution(outerSubst)
- altss = altss map (alts => propagateSubstitution(alts, substitution))
+ override private[TreeMakers] def incorporateOuterRebinding(outerSubst: Rebindings): Unit = {
+ super.incorporateOuterRebinding(outerSubst)
+ altss = altss map (alts => propagateRebindings(alts, rebindings))
}
def chainBefore(next: Tree)(codegenAlt: Casegen): Tree = {
@@ -856,7 +813,7 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
)
val findAltMatcher = codegenAlt.matcher(EmptyTree, NoSymbol, defn.BooleanType)(combinedAlts, Some((x: Symbol) => Literal(Constant(false))))
- codegenAlt.ifThenElseZero(findAltMatcher, substitution(next))
+ codegenAlt.ifThenElseZero(findAltMatcher, next)
}
}
}
@@ -864,25 +821,26 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
case class GuardTreeMaker(guardTree: Tree) extends TreeMaker with NoNewBinders {
val pos = guardTree.pos
- def chainBefore(next: Tree)(casegen: Casegen): Tree = casegen.flatMapGuard(substitution(guardTree), next)
+ def chainBefore(next: Tree)(casegen: Casegen): Tree = casegen.flatMapGuard(guardTree, next)
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])
-
+ def combineExtractors(treeMakers: List[TreeMaker])(casegen: Casegen): Tree = {
+ val (testsMakers, guardAndBodyMakers) = treeMakers.span(t => !(t.isInstanceOf[NoNewBinders]))
+ val body = guardAndBodyMakers.foldRight(EmptyTree: Tree)((a, b) => a.chainBefore(b)(casegen))
+ val rebindings = guardAndBodyMakers.last.rebindings.emitValDefs
+ testsMakers.foldRight(Block(rebindings, body): Tree)((a, b) => a.chainBefore(b)(casegen))
+ }
// a foldLeft to accumulate the localSubstitution left-to-right
// unlike in scalace it does not drop SubstOnly tree makers,
- // as there could types having them as prefix
- def propagateSubstitution(treeMakers: List[TreeMaker], initial: Substitution): List[TreeMaker] = {
- var accumSubst: Substitution = initial
+ // as there could be types having them as prefix
+ def propagateRebindings(treeMakers: List[TreeMaker], initial: Rebindings): List[TreeMaker] = {
+ var accumSubst: Rebindings = initial
treeMakers foreach { maker =>
- maker incorporateOuterSubstitution accumSubst
- accumSubst = maker.substitution
+ maker incorporateOuterRebinding accumSubst
+ accumSubst = maker.rebindings
}
treeMakers
}
@@ -890,11 +848,11 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
// calls propagateSubstitution on the treemakers
def combineCases(scrut: Tree, scrutSym: Symbol, casesRaw: List[List[TreeMaker]], pt: Type, owner: Symbol, matchFailGenOverride: Option[Symbol => Tree]): Tree = {
// unlike in scalac SubstOnlyTreeMakers are maintained.
- val casesSubstitutionPropagated = casesRaw map (propagateSubstitution(_, EmptySubstitution))
+ val casesRebindingPropagated = casesRaw map (propagateRebindings(_, NoRebindings))
def matchFailGen = matchFailGenOverride orElse Some((arg: Symbol) => Throw(New(defn.MatchErrorType, List(ref(arg)))))
- ctx.debuglog("combining cases: "+ (casesSubstitutionPropagated.map(_.mkString(" >> ")).mkString("{", "\n", "}")))
+ ctx.debuglog("combining cases: "+ (casesRebindingPropagated.map(_.mkString(" >> ")).mkString("{", "\n", "}")))
val (suppression, requireSwitch): (Suppression, Boolean) =
/*if (settings.XnoPatmatAnalysis)*/ (Suppression.NoSuppression, false)
@@ -913,10 +871,10 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
(Suppression.NoSuppression, false)
}*/
- emitSwitch(scrut, scrutSym, casesSubstitutionPropagated, pt, matchFailGenOverride, suppression.exhaustive).getOrElse{
+ emitSwitch(scrut, scrutSym, casesRebindingPropagated, pt, matchFailGenOverride, suppression.exhaustive).getOrElse{
if (requireSwitch) ctx.warning("could not emit switch for @switch annotated match", scrut.pos)
- if (casesSubstitutionPropagated nonEmpty) {
+ if (casesRebindingPropagated 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
@@ -924,15 +882,16 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
// ("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: Option[Symbol => Tree] =
- if (casesSubstitutionPropagated.nonEmpty && {
- val nonTrivLast = casesSubstitutionPropagated.last
+ if (casesRebindingPropagated.nonEmpty && {
+ val nonTrivLast = casesRebindingPropagated.last
nonTrivLast.nonEmpty && nonTrivLast.head.isInstanceOf[BodyTreeMaker]
}) None
else matchFailGen
- analyzeCases(scrutSym, casesSubstitutionPropagated, pt, suppression)
+ analyzeCases(scrutSym, casesRebindingPropagated, pt, suppression)
+
+ val (cases, toHoist) = optimizeCases(scrutSym, casesRebindingPropagated, pt)
- val (cases, toHoist) = optimizeCases(scrutSym, casesSubstitutionPropagated, pt)
val matchRes = codegen.matcher(scrut, scrutSym, pt)(cases.map(x => combineExtractors(x) _), synthCatchAll)
@@ -1104,7 +1063,6 @@ class PatternMatcher extends MiniPhaseTransform with DenotTransformer {thisTrans
case _: UnApply | _: Apply| Typed(_: UnApply | _: Apply, _) => extractorStep()
case SymbolAndTypeBound(sym, tpe) => typeTestStep(sym, tpe)
case TypeBound(tpe) => typeTestStep(binder, tpe)
- case SymbolAndValueBound(sym, const) => equalityTestStep(binder, sym, const)
case SymbolBound(sym, expr) => bindingStep(sym, expr)
case WildcardPattern() => noStep()
case ConstantPattern(const) => equalityTestStep(binder, binder, const)
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-02 16:27:20 +0000