/* __ *\
** ________ ___ / / ___ Scala Compiler **
** / __/ __// _ | / / / _ | (c) 2008-2009 , LAMP/EPFL **
** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ **
** /____/\___/_/ |_/____/_/ | | **
** |/ **
\* */
/**
*
* @author Anders Bach Nielsen
* @version 1.0
* $Id$
*/
package scala.tools.nsc
import scala.collection.mutable.{HashSet,HashMap}
import java.io.{BufferedWriter,FileWriter}
/**
* PhaseAssembly
* Trait made to seperate the constraint solving of the phase order from
* the rest of the compiler. See SIP 00002
*
*/
trait PhaseAssembly { self: Global =>
/**
* Aux datastructure for solving the constraint system
* The depency graph container with helper methods for node and edge creation
*/
class DependencyGraph {
/**
* Simple edge with to and from refs
*/
class Edge(var frm: Node, var to: Node, var hard: Boolean)
/**
* Simple node with name and object ref for the phase object,
* also sets of in and out going dependencies
*/
class Node(name:String) {
val phasename = name
var phaseobj: Option[List[SubComponent]] = None
val after = new HashSet[Edge]()
var before = new HashSet[Edge]()
var visited = false
var level = 0
def allPhaseNames(): String = phaseobj match {
case None => phasename
case Some(lst) => lst.map(sc => sc.phaseName).reduceLeft( (x,y) => x + "," + y)
}
}
val nodes = new HashMap[String,Node]()
val edges = new HashSet[Edge]()
/* Given a phase object, get the node for this phase object. If the
* node object does not exist, then create it.
*/
def getNodeByPhase(phs : SubComponent) : Node = {
var node : Node = getNodeByPhase(phs.phaseName)
node.phaseobj match {
case None =>
node.phaseobj = Some(List[SubComponent](phs))
case _ =>
}
node
}
/* Given the name of a phase object, get the node for that name. If the
* node object does not exits, then create it.
*/
def getNodeByPhase(name : String) : Node = {
nodes.get(name).getOrElse {
val node = new Node(name)
nodes += (name -> node)
node
}
}
/* Connect the frm and to nodes with an edge and make it soft.
* Also add the edge object to the set of edges, and to the dependency
* list of the nodes
*/
def softConnectNodes(frm: Node, to: Node) {
var e = new Edge(frm, to, false)
this.edges += e
frm.after += e
to.before += e
}
/* Connect the frm and to nodes with an edge and make it hard.
* Also add the edge object to the set of edges, and to the dependency
* list of the nodes
*/
def hardConnectNodes(frm: Node, to: Node) {
var e = new Edge(frm, to, true)
this.edges += e
frm.after += e
to.before += e
}
/* Given the entire graph, collect the phase objects at each level, where the phase
* names are sorted alphabetical at each level, into the compiler phase list
*/
def compilerPhaseList() : List[SubComponent] = {
var chain : List[SubComponent] = Nil
var lvl = 1
var nds = nodes.values.filter(n => (n.level == lvl)).toList
while(nds.size > 0) {
nds = nds.sort((n1,n2) => (n1.phasename compareTo n2.phasename) < 0)
for( n <- nds ) {
chain = chain ::: n.phaseobj.get
}
lvl = lvl + 1
nds = nodes.values.filter(n => (n.level == lvl)).toList
}
return chain
}
/* Test if there are cycles in the graph, assign levels to the nodes
* and collapse hard links into nodes
*/
def collapseHardLinksAndLevels(node : Node, lvl: Int) : Unit = {
if (node.visited) {
throw new FatalError("Cycle in compiler phase dependencies detected, phase " + node.phasename + " reacted twice!")
}
if (node.level < lvl) node.level = lvl
var hls = Nil ++ node.before.filter( e => e.hard )
while( hls.size > 0 ) {
for( hl <- hls ) {
node.phaseobj = Some(node.phaseobj.get ++ hl.frm.phaseobj.get)
node.before = hl.frm.before
nodes -= hl.frm.phasename
edges -= hl
for( edge <- node.before ) edge.to = node
}
hls = Nil ++ node.before.filter( e => e.hard )
}
node.visited = true
for( edge <- node.before ) {
collapseHardLinksAndLevels( edge.frm, lvl + 1)
}
node.visited = false
}
/* Find all edges in the given graph that are hard links. For each hard link we
* need to check that its the only dependency. If not, then we will promote the
* other dependencies down
*/
def validateAndEnforceHardlinks() : Unit = {
var hardlinks = edges.filter(e => e.hard)
for(hl <- hardlinks) {
if (hl.frm.after.size > 1) {
throw new FatalError("phase " + hl.frm.phasename + " want to run right after " + hl.to.phasename + ", but some phase has declared to run before " + hl.frm.phasename + ". Re-run with -Xgenerate-phase-graph <filename> to better see the problem.")
}
}
var rerun = true
while(rerun) {
rerun = false
hardlinks = edges.filter(e => e.hard)
for(hl <- hardlinks) {
var sanity = Nil ++ hl.to.before.filter(e => e.hard)
if (sanity.length == 0) {
throw new FatalError("There is no runs right after dependency, where there should be one! This is not supposed to happen!")
} else if (sanity.length > 1) {
var msg = "Multiple phases want to run right after the phase " + sanity.first.to.phasename + "\n"
msg += "Phases: "
sanity = sanity.sort((e1,e2) => (e1.frm.phasename compareTo e2.frm.phasename) < 0)
for (edge <- sanity) {
msg += edge.frm.phasename + ", "
}
msg += "\nRe-run with -Xgenerate-phase-graph <filename> to better see the problem."
throw new FatalError(msg)
} else {
var promote = hl.to.before.filter(e => (!e.hard))
hl.to.before.clear
sanity foreach (edge => hl.to.before += edge)
for (edge <- promote) {
rerun = true
informProgress("promote the dependency of " + edge.frm.phasename + ": " + edge.to.phasename + " => " + hl.frm.phasename)
edge.to = hl.frm
hl.frm.before += edge
}
}
}
}
}
/* Remove all nodes in the given graph, that have no phase object
* Make sure to clean up all edges when removing the node object
* Inform with warnings, if an external phase has a dependency on something that is dropped.
*/
def removeDanglingNodes() : Unit = {
var dnodes = nodes.values.filter(n => n.phaseobj.isEmpty )
for(node <- dnodes) {
informProgress("dropping dependency on node with no phase object: " + node.phasename)
nodes -= node.phasename
for(edge <- node.before) {
edges -= edge
edge.frm.after -= edge
edge.frm.phaseobj match {
case Some(lsc) => if (! lsc.head.internal) warning("dropping dependency on node with no phase object: " + node.phasename)
case _ =>
}
}
}
}
}
/* Method called from computePhaseDescriptors in class Global
*/
def buildCompilerFromPhasesSet() : List[SubComponent] = {
// Add all phases in the set to the graph
val graph = phasesSetToDepGraph(phasesSet)
// Output the phase dependency graph at this stage
if (!(settings.genPhaseGraph.value == "")) graphToDotFile(graph, settings.genPhaseGraph.value + "1.dot")
// Remove nodes without phaseobj
graph.removeDanglingNodes()
// Output the phase dependency graph at this stage
if (!(settings.genPhaseGraph.value == "")) graphToDotFile(graph, settings.genPhaseGraph.value + "2.dot")
// Validate and Enforce hardlinks / runsRightAfter and promote nodes down the tree
graph.validateAndEnforceHardlinks()
// Output the phase dependency graph at this stage
if (!(settings.genPhaseGraph.value == "")) graphToDotFile(graph, settings.genPhaseGraph.value + "3.dot")
// test for cycles, assign levels and collapse hard links into nodes
graph.collapseHardLinksAndLevels(graph.getNodeByPhase("parser"), 1)
// Output the phase dependency graph at this stage
if (!(settings.genPhaseGraph.value == "")) graphToDotFile(graph, settings.genPhaseGraph.value + "4.dot")
// assemble the compiler
return graph.compilerPhaseList()
}
/* Given the phases set, will build a dependency graph from the phases set
* Using the aux. method of the DependencyGraph to create nodes and egdes
*/
private def phasesSetToDepGraph(phsSet : HashSet[SubComponent]) : DependencyGraph = {
val graph = new DependencyGraph()
for(phs <- phsSet) {
var fromnode = graph.getNodeByPhase(phs)
phs.runsRightAfter match {
case None =>
for(phsname <- phs.runsAfter) {
if (! (phsname == "terminal")) {
var tonode = graph.getNodeByPhase(phsname)
graph.softConnectNodes(fromnode, tonode)
} else {
error("[phase assembly, after dependency on terminal phase not allowed: " + fromnode.phasename + " => "+ phsname + "]")
}
}
for(phsname <- phs.runsBefore) {
if (! (phsname == "parser")) {
var tonode = graph.getNodeByPhase(phsname)
graph.softConnectNodes(tonode, fromnode)
} else {
error("[phase assembly, before dependency on parser phase not allowed: " + phsname + " => "+ fromnode.phasename + "]")
}
}
case Some(phsname) =>
if (! (phsname == "terminal")) {
var tonode = graph.getNodeByPhase(phsname)
graph.hardConnectNodes(fromnode, tonode)
} else {
error("[phase assembly, right after dependency on terminal phase not allowed: " + fromnode.phasename + " => "+ phsname + "]")
}
}
}
graph
}
/* This is a helper method, that given a dependency graph will generate a graphviz dot
* file showing its structure.
* Plug-in supplied phases are marked as green nodes and hard links are marked as blue edges.
*/
private def graphToDotFile(graph : DependencyGraph, filename : String) : Unit = {
var sbuf = new StringBuffer()
var extnodes = new HashSet[graph.Node]()
var fatnodes = new HashSet[graph.Node]()
sbuf.append("digraph G {\n")
for(edge <- graph.edges) {
sbuf.append("\"" + edge.frm.allPhaseNames + "(" + edge.frm.level + ")" + "\"->\"" + edge.to.allPhaseNames + "(" + edge.to.level + ")" + "\"")
if (! edge.frm.phaseobj.get.first.internal) {
extnodes += edge.frm
}
edge.frm.phaseobj match { case None => null case Some(ln) => if(ln.size > 1) fatnodes += edge.frm }
edge.to.phaseobj match { case None => null case Some(ln) => if(ln.size > 1) fatnodes += edge.to }
if (edge.hard) {
sbuf.append(" [color=\"#0000ff\"]\n")
} else {
sbuf.append(" [color=\"#000000\"]\n")
}
}
for(node <- extnodes) {
sbuf.append("\"" + node.allPhaseNames + "(" + node.level + ")" + "\" [color=\"#00ff00\"]\n")
}
for(node <- fatnodes) {
sbuf.append("\"" + node.allPhaseNames + "(" + node.level + ")" + "\" [color=\"#0000ff\"]\n")
}
sbuf.append("}\n")
var out = new BufferedWriter(new FileWriter(filename))
out.write(sbuf.toString)
out.flush()
out.close()
}
}
