Get rid of Substitution.

Substitution was creating more problems than solving.
Instead the symbols in tree aren't rewriten anymore,
and pattern matcher collects Rebindings and generates ValDefs
for them just before the guard & body of the generated case.

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)