Unreachable components in phase assembly

som-snytt · som-snytt · commit 84d4940e1403 · 2024-11-02T19:48:34.000-07:00
diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala
@@ -41,6 +41,7 @@ import scala.tools.nsc.transform.async.AsyncPhase
 import scala.tools.nsc.transform.patmat.PatternMatching
 import scala.tools.nsc.typechecker._
 import scala.tools.nsc.util.ClassPath
+import scala.util.chaining._
 
 class Global(var currentSettings: Settings, reporter0: Reporter)
     extends SymbolTable
@@ -749,6 +750,7 @@ class Global(var currentSettings: Settings, reporter0: Reporter)
     computePlatformPhases()             // backend/Platform.scala
     computePluginPhases()               // plugins/Plugins.scala
     cullPhases(computePhaseAssembly())  // PhaseAssembly.scala
+      .tap { _ => if (settings.fatalWarnings.value && reporter.hasWarnings) runReporting.summarizeErrors() }
   }
 
   /* The phase descriptor list. Components that are phase factories. */
diff --git a/src/compiler/scala/tools/nsc/PhaseAssembly.scala b/src/compiler/scala/tools/nsc/PhaseAssembly.scala
@@ -12,7 +12,6 @@
 
 package scala.tools.nsc
 
-import java.util.concurrent.atomic.AtomicInteger
 import scala.collection.mutable, mutable.ArrayDeque, mutable.ListBuffer
 import scala.reflect.io.{File, Path}
 import scala.util.chaining._
@@ -45,10 +44,14 @@ trait PhaseAssembly {
  *
  *  Each vertex is labeled with its phase name.
  */
-class DependencyGraph(order: Int, start: String, val components: Map[String, SubComponent]) {
-  import DependencyGraph.{FollowsNow, Weight}
+class DependencyGraph(start: String, val components: Map[String, SubComponent]) {
+  import DependencyGraph.{FollowsNow, Weight, weightedArrow}
 
-  //private final val debugging = false
+  require(components.contains(start), s"Start $start is not a component in ${components.keys.mkString(", ")}")
+
+  private final val debugging = false
+
+  private val order = components.size
 
   private var messages: List[String] = Nil
   def warning(message: String): Unit = messages ::= message
@@ -61,34 +64,29 @@ class DependencyGraph(order: Int, start: String, val components: Map[String, Sub
   private case class Edge(from: Int, to: Int, weight: Weight)
 
   // phase names and their vertex index
-  private val nodeCount = new AtomicInteger
-  private val nodes = mutable.HashMap.empty[String, Int] // name to index
-  private val names = Array.ofDim[String](order)         // index to name
+  private val names = components.keys.toArray
+  private val nodes = names.zipWithIndex.toMap
 
   /** Add the edge between named phases, where `to` follows `from`.
    */
   private def addEdge(from: String, to: String, weight: Weight): Unit = {
-    def getNode(name: String): Int = {
-      def installName(name: String, n: Int): Unit =
-        if (n >= names.length) throw new FatalError(names.mkString(s"Extra name $name; names [",",","]"))
-        else names(n) = name
-      nodes.getOrElseUpdate(name, nodeCount.getAndIncrement().tap(installName(name, _)))
-    }
-    val v = getNode(from)
-    val w = getNode(to)
+    val v = nodes(from)
+    val w = nodes(to)
+    if (debugging) println(s"add edge $from ${weightedArrow(weight)} $to")
     adjacency(v).find(_.to == w) match {
       case None =>
         adjacency(v) ::= Edge(from = v, to = w, weight)
       case Some(_) if weight == FollowsNow => // retain runsRightAfter if there is a competing constraint
         adjacency(v) = Edge(from = v, to = w, weight) :: adjacency(v).filterNot(_.to == w)
-      case _ =>
+      case _ => // ignore duplicate
     }
   }
 
   /** Find unreachable vertices.
+   *
    *  Input must be acyclic and a vertex can have only one outgoing FollowsNow edge.
    */
-  private def validate(warn: Boolean): Set[String] = if (order == 1) Set.empty else {
+  private def validated(): List[String] = {
     def checkFollowsNow(v: Int): Unit =
       adjacency(v).foldLeft(-1) { (w, e) =>
         if (e.weight != FollowsNow) w
@@ -125,13 +123,14 @@ class DependencyGraph(order: Int, start: String, val components: Map[String, Sub
       }
     }
     walk()
-    names.iterator.zipWithIndex.collect { case (n, i) if !seen(i) =>
-      if (warn) warning(s"Dropping phase ${names(i)}, it is not reachable from $start")
-      n
-    }.toSet
+    val unseen = ListBuffer.empty[String]
+    for (i <- 0.until(order) if !seen(i))
+      unseen.addOne(names(i))
+    unseen.toList
   }
 
   def compilerPhaseList(): List[SubComponent] = if (order == 1) List(components(start)) else {
+
     // distance from source to each vertex
     val distance = Array.fill[Int](order)(Int.MinValue)
 
@@ -148,11 +147,13 @@ class DependencyGraph(order: Int, start: String, val components: Map[String, Sub
 
     def dequeue(): Int = queue.dequeue().tap(v => enqueued(v) = false)
 
-    //def namedEdge(e: Edge): String = if (e == null) "[no edge]" else s"${names(e.from)} ${if (e.weight == FollowsNow) "=" else "-"}> ${names(e.to)}"
+    def namedEdge(e: Edge): String =
+      if (e == null) "[no edge]"
+      else s"${names(e.from)}<${distance(e.from)}> ${weightedArrow(e.weight)} ${names(e.to)}<${distance(e.to)}>"
 
     /** Remove a vertex from the queue and check outgoing edges:
-     *  if an edge improves (increases) the distance at the terminal,
-     *  record that as the new incoming edge and enqueue that vertex
+     *  if an edge improves (increases) the distance at the terminus of the edge,
+     *  record that as the new incoming edge to the terminus and enqueue that vertex
      *  to propagate updates.
      */
     def relax(): Unit = {
@@ -162,7 +163,7 @@ class DependencyGraph(order: Int, start: String, val components: Map[String, Sub
       }
       while (!queue.isEmpty) {
         val v = dequeue()
-        //if (debugging) println(s"deq ${names(v)}")
+        if (debugging) println(s"deq ${names(v)}")
         for (e <- adjacency(v)) {
           val w = e.to
           /* cannot happen as `runsRightAfter: Option[String]` is the only way to introduce a `FollowsNow`
@@ -174,15 +175,16 @@ class DependencyGraph(order: Int, start: String, val components: Map[String, Sub
             distance(w) = distance(v) + e.weight
             edgeTo(w) = e
             enqueue(w)
-            //if (debugging) println(s"update ${namedEdge(e)} dist = ${distance(w)}, enq ${names(w)}")
+            if (debugging) println(s"update ${namedEdge(e)} dist = ${distance(w)}, enq ${names(w)}")
           }
         }
       }
-      //if (debugging) edgeTo.foreach(e => println(namedEdge(e)))
+      if (debugging) edgeTo.foreach(e => println(namedEdge(e)))
     }
+
     /** Put the vertices in a linear order.
      *
-     *  `Follows` edges increase the level, `FollowsNow` don't.
+     *  `Follows` edges increase the "level", `FollowsNow` don't.
      *  Partition by "level" or distance from start.
      *  Partition the level into "anchors" that follow a node in the previous level, and "followers" (nodes
      *    with a `FollowsNow` edge).
@@ -196,13 +198,14 @@ class DependencyGraph(order: Int, start: String, val components: Map[String, Sub
         /*c.internal && !d.internal ||*/ c.phaseName.compareTo(d.phaseName) < 0
       def sortVertex(i: Int, j: Int): Boolean = sortComponents(componentOf(i), componentOf(j))
 
-      distance.zipWithIndex.groupBy(_._1).toList.sortBy(_._1)
-      .flatMap { case (_, dis) =>
-        val vs = dis.map { case (_, i) => i }
+      val res = ListBuffer.empty[SubComponent]
+      val levels = distance.zipWithIndex.groupBy(_._1) // distance -> (distance, node)
+      for (level <- levels.keysIterator.filter(_ >= 0).toArray.sorted) {
+        val vs = levels(level).map(_._2)
         val (anchors, followers) = vs.partition(v => edgeTo(v) == null || edgeTo(v).weight != FollowsNow)
-        //if (debugging) println(s"d=$d, anchors=${anchors.toList.map(n => names(n))}, followers=${followers.toList.map(n => names(n))}")
+        if (debugging) println(s"d=$level, anchors={${anchors.map(names(_)).mkString(",")}}, followers={${followers.map(names(_)).mkString(",")}}")
         if (followers.isEmpty)
-          anchors.toList.map(componentOf).sortWith(sortComponents)
+          anchors.toArray.map(componentOf).sortWith(sortComponents).foreach(res.addOne(_))
         else {
           val froms = followers.map(v => edgeTo(v).from).toSet
           val ends = followers.iterator.filterNot(froms).toList
@@ -213,10 +216,13 @@ class DependencyGraph(order: Int, start: String, val components: Map[String, Sub
               case _ => chains.find(_.apply(0) == v).foreach(deque => path.foreach(deque.append))
             }
           ends.foreach(drill(_, Nil))
-          chains.sortWith((p, q) => sortVertex(p(0), q(0))).toList.flatten.map(componentOf)
+          for (chain <- chains.sortWith((p, q) => sortVertex(p(0), q(0))); v <- chain)
+            res.addOne(componentOf(v))
         }
       }
+      res.toList
     }
+    for (p <- validated()) warning(s"Dropping phase $p, which is not reachable from $start")
     relax()
     traverse()
   }
@@ -226,50 +232,92 @@ object DependencyGraph {
   type Weight = Int
   final val FollowsNow = 0
   final val Follows = 1
+  def weightedArrow(w: Weight) = w match {
+    case FollowsNow => "=>"
+    case Follows    => "->"
+    case _          => "?>"
+  }
 
   final val Parser = "parser"
   final val Terminal = "terminal"
 
+  private val compilerPhases = List(
+    "parser", "namer", "packageobjects", "typer", "superaccessors", "extmethods", "pickler",
+    "refchecks", "patmat", "uncurry", "fields", "tailcalls", "specialize", "explicitouter",
+    "erasure", "posterasure", "lambdalift", "constructors", "flatten", "mixin", "cleanup",
+    "delambdafy", "jvm", "terminal",
+  )
+
   /** Create a DependencyGraph from the given phases. The graph must be acyclic.
    *
    *  A component must be declared as "initial".
    *  If no phase is "initial" but a phase is named "parser", it is taken as initial.
    *  If no phase is "terminal" but a phase is named "terminal", it is taken as terminal.
-   *  Warnings are issued for invalid constraints (runsAfter / runsRightAfter / runsBefore) if `warn` is true.
-   *  Components without a valid "runsAfter" or "runsRightAfter" are dropped with an "unreachable" warning.
+   *
+   *  If a component declares that it follows (runsAfter or runsRightAfter)
+   *  a phase that is not named in this run, then the component is omitted.
+   *
+   *  If a component declares that it precedes (runsBefore)
+   *  a phase that is not named in this run, then the constraint is dropped.
+   *
+   *  Therefore, the graph contains only edges between the input components.
+   *
+   *  On construction (compilerPhaseList), unreachable components will incur warnings.
+   *
+   *  Apparent typos of phase names incur warnings.
    */
-  def apply(phases: Iterable[SubComponent], warn: Boolean = true): DependencyGraph = {
+  def apply(components: Iterable[SubComponent], warnAll: Boolean = true): DependencyGraph = {
+    val warnings = ListBuffer.empty[String]
+    val phases = components.iterator.filter { p =>
+      p.phaseName.nonEmpty.tap(b => if (!b) warnings.addOne(s"Dropped component with empty name (class ${p.getClass})"))
+    }.toArray
+    val phaseNames = phases.iterator.map(_.phaseName).toSet
+    def isPhaseName(s: String): Boolean = phaseNames.contains(s)
     val start = phases.find(_.initial)
       .orElse(phases.find(_.phaseName == Parser))
       .getOrElse(throw new AssertionError("Missing initial component"))
     val end = phases.find(_.terminal)
       .orElse(phases.find(_.phaseName == Terminal))
       .getOrElse(throw new AssertionError("Missing terminal component"))
-    val graph = new DependencyGraph(phases.size, start.phaseName, phases.map(p => p.phaseName -> p).toMap)
-    def phaseTypo(name: String) =
-      if (graph.components.contains(name)) ""
-      else graph.components.keysIterator.filter(util.EditDistance.levenshtein(name, _) < 3).toList match {
-        case Nil => ""
-        case close => s" - did you mean ${util.StringUtil.oxford(close, "or")}?"
+    var dropped = Set.empty[String]
+    val constraints = ListBuffer.empty[(String, String, Weight)]
+    def addConstraint(from: String, to: String, weight: Weight): Unit = constraints.addOne((from, to, weight))
+    def checkConstraint(p: SubComponent)(name: String, constraint: String, warn: Boolean): Boolean = isPhaseName(name) || {
+      if (warn) {
+        val knownNames = phaseNames ++ compilerPhases
+        val help = if (knownNames.contains(name)) "" else
+          knownNames.filter(util.EditDistance.levenshtein(name, _) < 3).toList match {
+            case Nil => ""
+            case close => s" - did you mean ${util.StringUtil.oxford(close, "or")}?"
+          }
+        warnings.addOne(s"No phase `$name` for ${p.phaseName}.$constraint$help")
       }
-    for (p <- phases) {
-      require(p.phaseName.nonEmpty, "Phase name must be non-empty.")
-      def checkConstraint(name: String, constraint: String): Boolean =
-        graph.components.contains(name).tap(ok => if (!ok && warn) graph.warning(s"No phase `$name` for ${p.phaseName}.$constraint${phaseTypo(name)}"))
-      for (after <- p.runsRightAfter if after.nonEmpty && checkConstraint(after, "runsRightAfter"))
-        graph.addEdge(after, p.phaseName, FollowsNow)
-      for (after <- p.runsAfter if after.nonEmpty && !p.runsRightAfter.contains(after) && checkConstraint(after, "runsAfter"))
-        graph.addEdge(after, p.phaseName, Follows)
-      for (before <- p.runsBefore if before.nonEmpty && checkConstraint(before, "runsBefore"))
-        graph.addEdge(p.phaseName, before, Follows)
-      // Add "runsBefore terminal" to phases without (or with invalid) runsBefore
+      false
+    }
+    for ((p, i) <- phases.zipWithIndex) {
+      for (after <- p.runsRightAfter if after.nonEmpty)
+        if (checkConstraint(p)(after, "runsRightAfter", warn=warnAll)) addConstraint(after, p.phaseName, FollowsNow)
+        else dropped += p.phaseName
+      for (after <- p.runsAfter if after.nonEmpty && !p.runsRightAfter.contains(after))
+        if (checkConstraint(p)(after, "runsAfter", warn=warnAll)) addConstraint(after, p.phaseName, Follows)
+        else dropped += p.phaseName
+      for (before <- p.runsBefore if before.nonEmpty)
+        if (checkConstraint(p)(before, "runsBefore", warn=warnAll)) addConstraint(p.phaseName, before, Follows)
+      // terminal follows every phase; parser is not before every phase because traverse uses edgeTo to find "anchors"
       if (p != end || p == end && p == start)
-        if (!p.runsBefore.exists(graph.components.contains))
-          graph.addEdge(p.phaseName, end.phaseName, Follows)
+        addConstraint(p.phaseName, end.phaseName, Follows)
+    }
+    if (warnAll)
+      dropped.foreach(p => warnings.addOne(s"Component ${p} dropped due to bad constraint"))
+    val purgedConstraints = constraints.filterInPlace {
+      case (from, to, w) => !dropped.contains(from) && !dropped.contains(to)
+    }.toList
+    new DependencyGraph(start.phaseName, phases.iterator.map(p => p.phaseName -> p).toMap).tap { graph =>
+      for ((from, to, weight) <- purgedConstraints)
+        graph.addEdge(from, to, weight)
+      for (warning <- warnings)
+        graph.warning(warning)
     }
-    val unreachable = graph.validate(warn)
-    if (unreachable.isEmpty) graph
-    else apply(phases.filterNot(p => unreachable(p.phaseName)), warn).tap(res => graph.warnings.foreach(res.warning))
   }
 
   /** Emit a graphviz dot file for the graph.
diff --git a/test/files/neg/t7494-before-parser.check b/test/files/neg/t7494-before-parser.check
@@ -1,7 +1,4 @@
-warning: Dropping phase beforeparser, it is not reachable from parser
-sample_2.scala:8: error: type mismatch;
- found   : String("")
- required: Int
-  def f: Int = ""
-               ^
+warning: Dropping phase beforeparser, which is not reachable from parser
+error: No warnings can be incurred under -Werror.
+1 warning
 1 error
diff --git a/test/files/neg/t7494-before-parser/sample_2.scala b/test/files/neg/t7494-before-parser/sample_2.scala
@@ -1,4 +1,4 @@
-//> using options -Xplugin:. -Xplugin-require:beforeparser
+//> using options -Xplugin:. -Xplugin-require:beforeparser -Werror
 package sample
 
 // just a sample that is compiled with the sample plugin enabled
diff --git a/test/files/neg/t8755.check b/test/files/neg/t8755.check
@@ -1,6 +1,8 @@
 warning: No phase `refchicks` for ploogin.runsAfter - did you mean refchecks?
 warning: No phase `java` for ploogin.runsBefore - did you mean jvm?
-warning: Dropping phase ploogin, it is not reachable from parser
+warning: Component ploogin dropped due to bad constraint
+warning: Dropping phase ploogin, which is not reachable from parser
+error: No warnings can be incurred under -Werror.
     phase name  id  description
     ----------  --  -----------
         parser   1  parse source into ASTs, perform simple desugaring
diff --git a/test/files/neg/t8755b.check b/test/files/neg/t8755b.check
@@ -1,4 +1,5 @@
-warning: Dropping phase ploogin, it is not reachable from parser
+warning: Dropping phase ploogin, which is not reachable from parser
+error: No warnings can be incurred under -Werror.
     phase name  id  description
     ----------  --  -----------
         parser   1  parse source into ASTs, perform simple desugaring
diff --git a/test/junit/scala/tools/nsc/PhaseAssemblyTest.scala b/test/junit/scala/tools/nsc/PhaseAssemblyTest.scala
@@ -82,7 +82,8 @@ class PhaseAssemblyTest {
     val components = names.foldLeft(parserAndTerminal(global)) { (comps, nm) =>
       component(global, nm, rra(nm), ra(comps, nm), runsBefore = beforeTerminal) :: comps
     }
-    assertThrows[FatalError](DependencyGraph(components), _ == "Phases kerfuffle and konflikt both immediately follow phooey")
+    val graph = DependencyGraph(components)
+    assertThrows[FatalError](graph.compilerPhaseList(), _ == "Phases kerfuffle and konflikt both immediately follow phooey")
   }
   @Test def `trivial cycle`: Unit = {
     val settings = new Settings
@@ -99,7 +100,8 @@ class PhaseAssemblyTest {
     val components = names.foldLeft(parserAndTerminal(global)) { (comps, nm) =>
       component(global, nm, rra(nm), ra(comps, nm), runsBefore = beforeTerminal) :: comps
     }
-    assertThrows[FatalError](DependencyGraph(components), _ == "Phases form a cycle: phooey -> kerfuffle -> konflikt -> phooey")
+    val graph = DependencyGraph(components)
+    assertThrows[FatalError](graph.compilerPhaseList(), _ == "Phases form a cycle: phooey -> kerfuffle -> konflikt -> phooey")
   }
   @Test def `run before tightly bound phases`: Unit = {
     val settings = new Settings
diff --git a/test/scaladoc/run/t8755.check b/test/scaladoc/run/t8755.check
@@ -1,5 +1,6 @@
 warning: No phase `refchecks` for ploogin.runsAfter
-warning: Dropping phase ploogin, it is not reachable from parser
+warning: Component ploogin dropped due to bad constraint
+warning: Dropping phase ploogin, which is not reachable from parser
 parser -> namer -> packageobjects -> typer -> terminal
 [running phase parser on newSource]
 [running phase namer on newSource]
diff --git a/test/scaladoc/run/t8755b.check b/test/scaladoc/run/t8755b.check
@@ -1,10 +1,10 @@
 warning: No phase `refchecks` for ploogin.runsAfter
 warning: No phase `jvm` for ploogin.runsBefore
-parser -> namer -> packageobjects -> typer -> ploogin -> terminal
+warning: Component ploogin dropped due to bad constraint
+warning: Dropping phase ploogin, which is not reachable from parser
+parser -> namer -> packageobjects -> typer -> terminal
 [running phase parser on newSource]
 [running phase namer on newSource]
 [running phase packageobjects on newSource]
 [running phase typer on newSource]
-[running phase ploogin on newSource]
-running plugin
 Done.
diff --git a/test/scaladoc/run/t8755b/ploogin_1.scala b/test/scaladoc/run/t8755b/ploogin_1.scala
@@ -23,7 +23,7 @@ class Ploogin(val global: Global) extends Plugin {
     def newPhase(prev: Phase) = new TestPhase(prev)
     class TestPhase(prev: Phase) extends StdPhase(prev) {
       override def description = TestComponent.this.description
-      def apply(unit: CompilationUnit): Unit = println("running plugin")
+      def apply(unit: CompilationUnit): Unit = ???
     }
   }
 }
diff --git a/test/scaladoc/run/t8755c.check b/test/scaladoc/run/t8755c.check
@@ -1,5 +1,5 @@
 warning: No phase `refchecks` for ploogin.runsBefore
-warning: Dropping phase ploogin, it is not reachable from parser
+warning: Dropping phase ploogin, which is not reachable from parser
 parser -> namer -> packageobjects -> typer -> terminal
 [running phase parser on newSource]
 [running phase namer on newSource]

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,4 @@`
`1`		`-//> using options -Xplugin:. -Xplugin-require:beforeparser`
	`1`	`+//> using options -Xplugin:. -Xplugin-require:beforeparser -Werror`
`2`	`2`	`package sample`
`3`	`3`
`4`	`4`	`// just a sample that is compiled with the sample plugin enabled`
Original file line number	Diff line number	Diff line change
`@@ -82,7 +82,8 @@ class PhaseAssemblyTest {`
`82`	`82`	`val components = names.foldLeft(parserAndTerminal(global)) { (comps, nm) =>`
`83`	`83`	`component(global, nm, rra(nm), ra(comps, nm), runsBefore = beforeTerminal) :: comps`
`84`	`84`	`}`
`85`		`- assertThrows[FatalError](DependencyGraph(components), _ == "Phases kerfuffle and konflikt both immediately follow phooey")`
	`85`	`+ val graph = DependencyGraph(components)`
	`86`	`+ assertThrows[FatalError](graph.compilerPhaseList(), _ == "Phases kerfuffle and konflikt both immediately follow phooey")`
`86`	`87`	`}`
`87`	`88`	@Test def `trivial cycle`: Unit = {
`88`	`89`	`val settings = new Settings`
`@@ -99,7 +100,8 @@ class PhaseAssemblyTest {`
`99`	`100`	`val components = names.foldLeft(parserAndTerminal(global)) { (comps, nm) =>`
`100`	`101`	`component(global, nm, rra(nm), ra(comps, nm), runsBefore = beforeTerminal) :: comps`
`101`	`102`	`}`
`102`		`- assertThrows[FatalError](DependencyGraph(components), _ == "Phases form a cycle: phooey -> kerfuffle -> konflikt -> phooey")`
	`103`	`+ val graph = DependencyGraph(components)`
	`104`	`+ assertThrows[FatalError](graph.compilerPhaseList(), _ == "Phases form a cycle: phooey -> kerfuffle -> konflikt -> phooey")`
`103`	`105`	`}`
`104`	`106`	@Test def `run before tightly bound phases`: Unit = {
`105`	`107`	`val settings = new Settings`
Original file line number	Diff line number	Diff line change
`@@ -23,7 +23,7 @@ class Ploogin(val global: Global) extends Plugin {`
`23`	`23`	`def newPhase(prev: Phase) = new TestPhase(prev)`
`24`	`24`	`class TestPhase(prev: Phase) extends StdPhase(prev) {`
`25`	`25`	`override def description = TestComponent.this.description`
`26`		`- def apply(unit: CompilationUnit): Unit = println("running plugin")`
	`26`	`+ def apply(unit: CompilationUnit): Unit = ???`
`27`	`27`	`}`
`28`	`28`	`}`
`29`	`29`	`}`