diff options
Diffstat (limited to 'SIP')
50 files changed, 2600 insertions, 0 deletions
diff --git a/SIP/compiler-phase-init/sip-00002-1.dia b/SIP/compiler-phase-init/sip-00002-1.dia Binary files differnew file mode 100644 index 0000000000..94e4ffa3b3 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-1.dia diff --git a/SIP/compiler-phase-init/sip-00002-1.png b/SIP/compiler-phase-init/sip-00002-1.png Binary files differnew file mode 100644 index 0000000000..f4bbf67e79 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-1.png diff --git a/SIP/compiler-phase-init/sip-00002-10.scala b/SIP/compiler-phase-init/sip-00002-10.scala new file mode 100644 index 0000000000..2065a7035d --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-10.scala @@ -0,0 +1,521 @@ +/* Package information */ +package depgraph + + +/* Simple import of data structures and IO */ +import scala.collection.mutable.{HashSet,HashMap} +import java.io.{BufferedWriter,FileWriter} + + + +/* Class made to model the internal compiler phases + * + * All internal phases inherits from SubComponent + */ +abstract class SubComponent { + val phaseName: String + val runsAfter: List[String] + val runsRightAfter: Option[String] + val internal: Boolean = true +} + +/* + * + */ +class Global extends Plugins with PhaseAssembly { + + /* Simple option value to hold the compiler phase chain */ + private var phasesCache : Option[List[SubComponent]] = None + + /* The set of phase objects that is the basis for the compiler phase chain */ + protected val phasesSet : HashSet[SubComponent] = new HashSet[SubComponent] + + /* All the internal phase objects + * + */ + object parser extends { + val phaseName = "nsc::parser" + val runsAfter = List[String]() + val runsRightAfter = None + } with SubComponent + + object typer extends { + val phaseName = "nsc::typer" + val runsAfter = List[String]("nsc::parser") + val runsRightAfter = None + } with SubComponent + + object pickler extends { + val phaseName = "nsc::pickler" + val runsAfter = List[String]("nsc::typer") + val runsRightAfter = None + } with SubComponent + + object liftcode extends { + val phaseName = "nsc::liftcode" + val runsAfter = List[String]("nsc::pickler") + val runsRightAfter = None + } with SubComponent + + object tailcalls extends { + val phaseName = "nsc::tailcalls" + val runsAfter = List[String]("nsc::pickler","nsc::liftcode") + val runsRightAfter = None + } with SubComponent + + object erasure extends { + val phaseName = "nsc::erasure" + val runsAfter = List[String]() + val runsRightAfter = Some("nsc::tailcalls") + } with SubComponent + + object cleanup extends { + val phaseName = "nsc::cleanup" + val runsAfter = List[String]("nsc::erasure") + val runsRightAfter = None + } with SubComponent + + object jvm extends { + val phaseName = "nsc::jvm" + val runsAfter = List[String]("nsc::cleanup") + val runsRightAfter = None + } with SubComponent + + object terminal extends { + val phaseName = "nsc::terminal" + val runsAfter = List[String]("nsc::jvm","nsc::msil") + val runsRightAfter = None + } with SubComponent + + /* Helper method + */ + private def computePhaseDescriptors: List[SubComponent] = { + computeInternalPhases() // Global.scala + computePluginPhases() // plugins/Plugins.scala + buildCompilerFromPhasesSet() // PhaseAssembly.scala + } + + /* Will add the internal compiler phases to the phases set + */ + protected def computeInternalPhases() { + phasesSet += parser + phasesSet += typer + phasesSet += pickler + phasesSet += liftcode + phasesSet += tailcalls + phasesSet += erasure + phasesSet += cleanup + phasesSet += jvm + phasesSet += terminal + } + + /* Getter method for the compiler phases chain + */ + def phaseDescriptors : List[SubComponent] = { + if (phasesCache.isEmpty) { + phasesCache = Some(computePhaseDescriptors) + } + phasesCache.get + } + +} + + +/* Class make to model the Plug-in supplied phases + * + * All external phases inherits from PluginComponent + */ +abstract class PluginComponent extends SubComponent { + override val internal = false + val runsRightAfter: Option[String] = None +} + +/* Trait made to model the behavior of the plugins + * + */ +trait Plugins { self: Global => + + /* Example plugin phases + * + */ + object plugin1 extends { + val phaseName = "plug1::optimization1" + val runsAfter = List[String]("nsc::typer") + } with PluginComponent + + object plugin2 extends { + val phaseName = "plug2::optimization1" + val runsAfter = List[String]("nsc::liftcode") + } with PluginComponent + + object plugin3 extends { + val phaseName = "plug2::optimization2" + val runsAfter = List[String]("plug2::optimization1","nsc::cleanup") + } with PluginComponent + + /* Add plug-in supplied phase objects to the phases set + */ + def computePluginPhases() { + phasesSet += plugin1 + phasesSet += plugin2 + phasesSet += plugin3 + } + +} + + +/* Trait made to seperate the constraint solving from the rest of the compiler + * + */ +trait PhaseAssembly { self: Global => + + /* Aux datastructure for solving the constraint system + * Simple edge with to and from refs + */ + class Edge(f: Node, t: Node, h: Boolean) { + var frm = f + var to = t + var hard = h + } + + /* Aux datastructure for solving the constraint system + * Simple node with name and object ref for the phase object, + * also sets of in and out going dependencies + */ + class Node(phs:SubComponent, name:String) { + var phasename: String = name + var phaseobj: SubComponent = phs + var after: HashSet[Edge] = new HashSet[Edge]() + var deps: HashSet[Edge] = new HashSet[Edge]() + } + + /* Aux datastructure for solving the constraint system + * The depency graph container with helper methods for node and edge creation + */ + class DependencyGraph { + + 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) + if (node.phaseobj == null) { + node.phaseobj = phs + } + 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 = { + var node : Node = null + this.nodes.get(name) match { + case None => + node = new Node(null,name) + nodes += (name->node) + case Some(n) => + node = n + } + 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.deps += 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.deps += e + } + } + + /* This method will simplify the graph, by removing unneeded edges and turning the graph into + * a tree. + */ + private def simplifyGraphFromNode(node : Node, graph : DependencyGraph) : Unit = { + var removal : List[Edge] = Nil + for(edge <- node.deps) { + if (edge.frm.after.size > 1) + removal = edge :: removal + } + for(edge <- removal) { + println("[removing edge: " + edge.frm.phasename + " => " + edge.to.phasename + "]") + node.deps -= edge + edge.frm.after -= edge + graph.edges -= edge + } + + var nodes = dependencyOrder(node.deps) + for(nd <- nodes) { + simplifyGraphFromNode(nd, graph) + } + } + + /* This is a simple method that tests for cycles in the graph. If a cycle is found, a fatal error + * will be produced. + */ + private def testForCycles(node : Node, names : HashSet[String]) : Unit = { + + if (names.contains( node.phasename ) ) { + println("There is a cycle in this graph! The algorithm was able to reach the node " + node.phasename + " twice!") + System.exit(1) + } + + names += node.phasename + + var nodes = dependencyOrder(node.deps) + for(nd <- nodes) { + testForCycles(nd, names) + } + + names -= node.phasename + } + + /* Given the dependency list of a node, return a list so that first come the reversed + * external phases sorted alphabetically, followed by the internal phase + */ + private def dependencyOrder(deps : HashSet[Edge]) : List[Node] = { + var external = deps.filter(e => (! e.frm.phaseobj.internal)) + var internal = deps.filter(e => e.frm.phaseobj.internal) + + var extnodes = (Nil ++ external.map(e => e.frm)).sort((n1,n2) => (n1.phasename compareTo n2.phasename) < 0) + extnodes = extnodes.reverse + + var nodes = Nil ++ internal.map(e => e.frm) ++ extnodes + nodes = nodes.reverse + return nodes + } + + /* 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 + */ + private def enforceHardlinks(graph : DependencyGraph) : Unit = { + var rerun = true + while(rerun) { + rerun = false + var hardlinks = graph.edges.filter(e => e.hard) + for(hl <- hardlinks) { + var sanity = Nil ++ hl.to.deps.filter(e => e.hard) + if (sanity.length == 0) { + + println("This is not supposed to happen!") + System.exit(1) + // throw new FataError() + } else if (sanity.length > 1) { + + println("Multiple phases want to run right after the same phase") + println("Phases:") + for (edge <- sanity) { + println(" - " + edge.frm.phasename) + } + System.exit(1) + + } else { + + var promote = hl.to.deps.filter(e => (!e.hard)) + hl.to.deps.clear + sanity foreach (edge => hl.to.deps += edge) + for (edge <- promote) { + rerun = true + println("[promote the dependency of " + edge.frm.phasename + ": " + edge.to.phasename + " => " + hl.frm.phasename + "]") + edge.to = hl.frm + hl.frm.deps += 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 + */ + private def removeDanglingNodes(graph : DependencyGraph) : Unit = { + var dnodes = graph.nodes.values.filter(n => (n.phaseobj == null)) + for(node <- dnodes) { + println("[dropping depend on node with no phase: " + node.phasename + "]") + graph.nodes -= node.phasename + for(edge <- node.deps) { + graph.edges -= edge + edge.frm.after -= edge + } + } + } + + /* 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[Node]() + sbuf.append("digraph G {\n") + for(edge <- graph.edges) { + sbuf.append("\"" + edge.frm.phasename + "\"->\"" + edge.to.phasename + "\"") + if (! edge.frm.phaseobj.internal) { + extnodes += edge.frm + } + if (edge.hard) { + sbuf.append(" [color=\"#0000ff\"]\n") + } else { + sbuf.append(" [color=\"#000000\"]\n") + } + } + for(node <- extnodes) { + sbuf.append("\"" + node.phasename + "\" [color=\"#00ff00\"]\n") + } + sbuf.append("}\n") + var out = new BufferedWriter(new FileWriter(filename)) + out.write(sbuf.toString) + out.flush() + out.close() + } + + + /* 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 equals "terminal")) { + var tonode = graph.getNodeByPhase(phsname) + graph.softConnectNodes(fromnode, tonode) + } else { + println("[depends on terminal not allowed, dropping depend: " + fromnode.phasename + " => "+ phsname +"]") + } + } + case Some(phsname) => + if (! (phsname equals "terminal")) { + var tonode = graph.getNodeByPhase(phsname) + graph.hardConnectNodes(fromnode, tonode) + } else { + println("[depends on terminal not allowed, dropping depend: " + fromnode.phasename + " => "+ phsname +"]") + } + } + + } + + return graph + } + + + /* Simple transformation function, that given a dependency graph transforms it into a dependency tree + * Will return the root of the tree + */ + private def depGraphToDepTree(graph : DependencyGraph) : Node = { + + graphToDotFile(graph, "depgraph1.dot") + + // Remove nodes without phaseobj + removeDanglingNodes(graph) + + graphToDotFile(graph, "depgraph2.dot") + + // Enforce hardlinks / runsRightAfter and promote nodes down the tree + enforceHardlinks(graph) + + graphToDotFile(graph, "depgraph3.dot") + + var root = graph.getNodeByPhase("nsc::parser") + + // Test for cycles in graph, if found will generate fatal error + testForCycles(root, new HashSet[String]()) + + // Simplify graph by removing edges starting from the root + simplifyGraphFromNode(root, graph) + + graphToDotFile(graph, "depgraph4.dot") + + root + } + + + /* Given a node and a list of phases, it will traverse the dependencies of the node object and + * call itself recursively + * + */ + private def depTree2CompilerPhaseList(node : Node, pchain : List[SubComponent]) : List[SubComponent] = { + var chain : List[SubComponent] = pchain + chain = chain ::: List(node.phaseobj) + if (node.deps.size == 0) + return chain + + else if (node.deps.size == 1) { + for(edge <- node.deps) + chain = depTree2CompilerPhaseList(edge.frm, chain) + return chain + + } else { + + var nodes = dependencyOrder(node.deps) + for(nd <- nodes) { + chain = depTree2CompilerPhaseList(nd, chain) + } + return chain + } + } + + + /* Method called from computePhaseDescriptors in class Global + * This method will call three aux. methods to convert the phases set into a dependency graph + * Convert the dependency graph into a dependency tree and return the root of the tree + * Assemble the compiler phase chain from the root of the dependency tree + */ + def buildCompilerFromPhasesSet() : List[SubComponent] = { + + // Add all phases in the set to the graph + val graph = phasesSetToDepGraph(phasesSet) + + val root = depGraphToDepTree(graph) + + return depTree2CompilerPhaseList(root, Nil) + } + +} + + +/** + * Test object that will create a new object from the Global class + * and call the method phaseDescriptors to get the list of phase objects + * and print the phase names to stdout + * + */ +object DepGraphTest extends Application { + + val global = new Global() + + var compilerchain = global.phaseDescriptors + + for(phase <- compilerchain) { + println(" - " + phase.phaseName) + } + +} + diff --git a/SIP/compiler-phase-init/sip-00002-11.png b/SIP/compiler-phase-init/sip-00002-11.png Binary files differnew file mode 100644 index 0000000000..c26f056d86 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-11.png diff --git a/SIP/compiler-phase-init/sip-00002-12.png b/SIP/compiler-phase-init/sip-00002-12.png Binary files differnew file mode 100644 index 0000000000..b4e59a08f7 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-12.png diff --git a/SIP/compiler-phase-init/sip-00002-13.png b/SIP/compiler-phase-init/sip-00002-13.png Binary files differnew file mode 100644 index 0000000000..9cfc543190 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-13.png diff --git a/SIP/compiler-phase-init/sip-00002-14.png b/SIP/compiler-phase-init/sip-00002-14.png Binary files differnew file mode 100644 index 0000000000..d81df6dae3 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-14.png diff --git a/SIP/compiler-phase-init/sip-00002-15.dia b/SIP/compiler-phase-init/sip-00002-15.dia Binary files differnew file mode 100644 index 0000000000..2b08cafc33 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-15.dia diff --git a/SIP/compiler-phase-init/sip-00002-15.png b/SIP/compiler-phase-init/sip-00002-15.png Binary files differnew file mode 100644 index 0000000000..a9b0ce4db2 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-15.png diff --git a/SIP/compiler-phase-init/sip-00002-16.dia b/SIP/compiler-phase-init/sip-00002-16.dia Binary files differnew file mode 100644 index 0000000000..e05924ac67 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-16.dia diff --git a/SIP/compiler-phase-init/sip-00002-16.png b/SIP/compiler-phase-init/sip-00002-16.png Binary files differnew file mode 100644 index 0000000000..7351e6e7c9 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-16.png diff --git a/SIP/compiler-phase-init/sip-00002-17.dia b/SIP/compiler-phase-init/sip-00002-17.dia Binary files differnew file mode 100644 index 0000000000..2e4068f82a --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-17.dia diff --git a/SIP/compiler-phase-init/sip-00002-17.png b/SIP/compiler-phase-init/sip-00002-17.png Binary files differnew file mode 100644 index 0000000000..e2026e51b4 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-17.png diff --git a/SIP/compiler-phase-init/sip-00002-18.dia b/SIP/compiler-phase-init/sip-00002-18.dia Binary files differnew file mode 100644 index 0000000000..b1eb5003b4 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-18.dia diff --git a/SIP/compiler-phase-init/sip-00002-18.png b/SIP/compiler-phase-init/sip-00002-18.png Binary files differnew file mode 100644 index 0000000000..1f743e549b --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-18.png diff --git a/SIP/compiler-phase-init/sip-00002-19.dia b/SIP/compiler-phase-init/sip-00002-19.dia Binary files differnew file mode 100644 index 0000000000..fc05ac6a2a --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-19.dia diff --git a/SIP/compiler-phase-init/sip-00002-19.png b/SIP/compiler-phase-init/sip-00002-19.png Binary files differnew file mode 100644 index 0000000000..ffd8930b59 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-19.png diff --git a/SIP/compiler-phase-init/sip-00002-2.dia b/SIP/compiler-phase-init/sip-00002-2.dia Binary files differnew file mode 100644 index 0000000000..d08ee35f46 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-2.dia diff --git a/SIP/compiler-phase-init/sip-00002-2.png b/SIP/compiler-phase-init/sip-00002-2.png Binary files differnew file mode 100644 index 0000000000..66a0eb695b --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-2.png diff --git a/SIP/compiler-phase-init/sip-00002-20.dia b/SIP/compiler-phase-init/sip-00002-20.dia Binary files differnew file mode 100644 index 0000000000..fb16133aa9 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-20.dia diff --git a/SIP/compiler-phase-init/sip-00002-20.png b/SIP/compiler-phase-init/sip-00002-20.png Binary files differnew file mode 100644 index 0000000000..5290bb1d83 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-20.png diff --git a/SIP/compiler-phase-init/sip-00002-21.dia b/SIP/compiler-phase-init/sip-00002-21.dia Binary files differnew file mode 100644 index 0000000000..65b16a99a0 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-21.dia diff --git a/SIP/compiler-phase-init/sip-00002-21.png b/SIP/compiler-phase-init/sip-00002-21.png Binary files differnew file mode 100644 index 0000000000..152f0d7c0c --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-21.png diff --git a/SIP/compiler-phase-init/sip-00002-22.dia b/SIP/compiler-phase-init/sip-00002-22.dia Binary files differnew file mode 100644 index 0000000000..7ce832d3fa --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-22.dia diff --git a/SIP/compiler-phase-init/sip-00002-22.png b/SIP/compiler-phase-init/sip-00002-22.png Binary files differnew file mode 100644 index 0000000000..42cf265fcf --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-22.png diff --git a/SIP/compiler-phase-init/sip-00002-23.dia b/SIP/compiler-phase-init/sip-00002-23.dia Binary files differnew file mode 100644 index 0000000000..ae89016ca2 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-23.dia diff --git a/SIP/compiler-phase-init/sip-00002-23.png b/SIP/compiler-phase-init/sip-00002-23.png Binary files differnew file mode 100644 index 0000000000..1b0ea408dc --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-23.png diff --git a/SIP/compiler-phase-init/sip-00002-24.dia b/SIP/compiler-phase-init/sip-00002-24.dia Binary files differnew file mode 100644 index 0000000000..d96f9cd319 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-24.dia diff --git a/SIP/compiler-phase-init/sip-00002-24.png b/SIP/compiler-phase-init/sip-00002-24.png Binary files differnew file mode 100644 index 0000000000..cdb4c91223 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-24.png diff --git a/SIP/compiler-phase-init/sip-00002-3.dia b/SIP/compiler-phase-init/sip-00002-3.dia Binary files differnew file mode 100644 index 0000000000..e8c883917e --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-3.dia diff --git a/SIP/compiler-phase-init/sip-00002-3.png b/SIP/compiler-phase-init/sip-00002-3.png Binary files differnew file mode 100644 index 0000000000..b464735965 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-3.png diff --git a/SIP/compiler-phase-init/sip-00002-4.dia b/SIP/compiler-phase-init/sip-00002-4.dia Binary files differnew file mode 100644 index 0000000000..9927a1291b --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-4.dia diff --git a/SIP/compiler-phase-init/sip-00002-4.png b/SIP/compiler-phase-init/sip-00002-4.png Binary files differnew file mode 100644 index 0000000000..043520450b --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-4.png diff --git a/SIP/compiler-phase-init/sip-00002-5.dia b/SIP/compiler-phase-init/sip-00002-5.dia Binary files differnew file mode 100644 index 0000000000..b5bac4613f --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-5.dia diff --git a/SIP/compiler-phase-init/sip-00002-5.png b/SIP/compiler-phase-init/sip-00002-5.png Binary files differnew file mode 100644 index 0000000000..18a4b73dac --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-5.png diff --git a/SIP/compiler-phase-init/sip-00002-6.dia b/SIP/compiler-phase-init/sip-00002-6.dia Binary files differnew file mode 100644 index 0000000000..9e8f0a56bf --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-6.dia diff --git a/SIP/compiler-phase-init/sip-00002-6.png b/SIP/compiler-phase-init/sip-00002-6.png Binary files differnew file mode 100644 index 0000000000..8da5b03efe --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-6.png diff --git a/SIP/compiler-phase-init/sip-00002-7.dia b/SIP/compiler-phase-init/sip-00002-7.dia Binary files differnew file mode 100644 index 0000000000..9a35df0ee1 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-7.dia diff --git a/SIP/compiler-phase-init/sip-00002-7.png b/SIP/compiler-phase-init/sip-00002-7.png Binary files differnew file mode 100644 index 0000000000..382a505c79 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-7.png diff --git a/SIP/compiler-phase-init/sip-00002-8.dia b/SIP/compiler-phase-init/sip-00002-8.dia Binary files differnew file mode 100644 index 0000000000..6ccfa0f2d8 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-8.dia diff --git a/SIP/compiler-phase-init/sip-00002-8.png b/SIP/compiler-phase-init/sip-00002-8.png Binary files differnew file mode 100644 index 0000000000..97a4c20fcb --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-8.png diff --git a/SIP/compiler-phase-init/sip-00002-9.dia b/SIP/compiler-phase-init/sip-00002-9.dia Binary files differnew file mode 100644 index 0000000000..da22427789 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-9.dia diff --git a/SIP/compiler-phase-init/sip-00002-9.png b/SIP/compiler-phase-init/sip-00002-9.png Binary files differnew file mode 100644 index 0000000000..17109c13b6 --- /dev/null +++ b/SIP/compiler-phase-init/sip-00002-9.png diff --git a/SIP/compiler-phase-init/sip.xhtml b/SIP/compiler-phase-init/sip.xhtml new file mode 100644 index 0000000000..10cb4c3189 --- /dev/null +++ b/SIP/compiler-phase-init/sip.xhtml @@ -0,0 +1,1546 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"> +<head> + <title>Scala Compiler Phase and Plug-In Initialization</title> + <meta name="sip" content="00002"/> + <meta name="author" content="Anders Bach Nielsen"/> + <meta name="version" content="0"/> + <meta name="type" content="standards"/> + <meta name="status" content="submission"/> + <meta name="created" content="2008-08-25"/> + <meta name="updated" content="2008-10-09"/> + <meta name="scala-version" content="2.8.0.final-"/> + <meta name="owner-contact" content="mailto:andersbach.nielsen@epfl.ch"/> + <meta name="discussion" content="http://www.nabble.com/SIP-00002%3A-Compiler-Phase-Initialization-and-Plugins-td19677473.html"/> + <!-- <link rel="auxiliary" href="[URI]" type="[mime type]"/> --> + <!-- <link rel="replaces" href="[URI]" type="application/xhtml+xml"/> --> + <!-- <link rel="depends-on" href="[URI]" type="application/xhtml+xml"/> --> + <!-- Stylesheet --> + <link rel="stylesheet" href="http://lampsvn.epfl.ch/svn-repos/scala/sip/trunk/sip.css" type="text/css"/> +</head> +<body> + <a name="top"></a> + <h1>Scala Compiler Phase and Plug-In Initialization</h1> + + <h2>Abstract</h2> + + <p>This document describes the design and implementation of a more + uniform way of handling internal compiler phases and external user + supplied phases via plug-ins in the Scala compiler.</p> + + <h2>Contents</h2> + + <ul> + <li><a href="#motivation">Motivation</a> + <ul> + <li><a href="#goalsandreq">Goals</a></li> + <li><a href="#usecases">Use Cases</a></li> + <li><a href="#detailedusecases">Detailed Use Cases</a> + <ul> + <li><a href="#usecase1">Assembling compiler internal phases for the JVM target ...</a></li> + <li><a href="#usecase2">Assembling compiler internal phases for the MSIL target ...</a></li> + <li><a href="#usecase3">Adding one plug-in supplied phase to the JVM target ...</a></li> + <li><a href="#usecase4">Adding two plug-in supplied phase to the JVM target ...</a></li> + <li><a href="#usecase5">Adding two plug-in supplied phases, where one has a ...</a></li> + <li><a href="#usecase6">Adding plug-in supplied phases with dependencies to ...</a></li> + <li><a href="#usecase7">Two separate phases that should be handled as a single ...</a></li> + <li><a href="#usecase8">A cyclic dependency among phases is a fatal error.</a></li> + <li><a href="#usecase9">Special handling of the <code>parser</code> and <code>terminal</code> phases.</a></li> + <li><a href="#usecase10">Larger compiler example with three plug-in supplied phases.</a></li> + </ul> + </li> + <li><a href="#futuregoals">Future Goals That Extend Beyond This Proposal</a></li> + </ul> + </li> + <li><a href="#description">Description</a> + <ul> + <li><a href="#presentdesign">The Present Design</a></li> + <li><a href="#proposeddesign">The Proposed Design</a> + <ul> + <li><a href="#propdesign1">Internal Phases</a></li> + <li><a href="#propdesign2">External Phases</a></li> + <li><a href="#propdesign3">Phases Set</a></li> + <li><a href="#propdesign4">Phase Assembly</a></li> + <li><a href="#propdesign5">Constraint System</a></li> + <li><a href="#constsolver">Constraint Solving Algorithm</a></li> + </ul> + </li> + <li><a href="#namingscheme">Naming Scheme for Internal and External Phases</a></li> + <li><a href="#implications">Implications of This Proposal</a></li> + </ul> + </li> + <li><a href="#implementation">Implementation</a></li> + </ul> + + + <a name="motivation"></a> + <h2>Motivation</h2> + + <p>This section will cover the motivating goals of creating this + proposal and some use cases emphasizing these goals. There will also + be a section on goals that extend beyond this proposal and will + therefore not be covered by this proposal.</p> + + <a name="goalsandreq"></a> + <h3>Goals</h3> + + <ul> + <li>Handle inclusion and constraints for internal compiler phases + and external user supplied phases via plug-ins in a uniform + way.</li> + + <li>Phase ordering is based on a simple, but sufficient powerful + and solvable constraint system.</li> + + <li>Phase ordering of internal compiler phases and external user + supplied phases should retain as much compatibility with the + current scheme as possible.</li> + + <li>Phase ordering is fully determined by the set of input phases. + It does not matter, for example, what order the compiler processes + the individual plug-ins that supply the external phases.</li> + + <li>Ordering of the internal compiler phases should always succeed + in a valid compiler phase chain. Adding two plug-ins, which by + themselves give a valid compiler phase chain, should also give a + valid compiler phase chain.</li> + + </ul> + + <a name="usecases"></a> <h3>Use Cases</h3> + + <ol> + <li><a href="#usecase1">Assembling compiler internal phases for + the JVM target and no plug-ins are loaded.</a></li> + + <li><a href="#usecase2">Assembling compiler internal phases for + the MSIL target and no plug-ins are loaded.</a></li> + + <li><a href="#usecase3">Adding one plug-in supplied phase to the + JVM target compiler after type checking.</a></li> + + <li><a href="#usecase4">Adding two plug-in supplied phase to the + JVM target compiler after type checking.</a></li> + + <li><a href="#usecase5">Adding two plug-in supplied phases, where + one has a dependency on the other, to the JVM target + compiler.</a></li> + + <li><a href="#usecase6">Adding plug-in supplied phases with + dependencies to both plug-in supplied and internal phases to the + JVM target compiler.</a></li> + + <li><a href="#usecase7">Two separate phases that should be handled + as a single phase.</a></li> + + <li><a href="#usecase8">A cyclic dependency among phases is a + fatal error.</a></li> + + <li><a href="#usecase9">Special handling of the + <code>parser</code> and <code>terminal</code> phases.</a></li> + + <li><a href="#usecase10">Larger compiler example with three + plug-in supplied phases.</a></li> + + + </ol> + + <a name="detailedusecases"></a> + <h3>Detailed Use Cases</h3> + + <a name="usecase1"></a> + <h4>[1] Assembling compiler internal phases for the JVM target and + no plug-ins are loaded.</h4> + + <p>All phases have to declare a <code>runsAfter</code> list of phase + names that should be run before the phase itself in the final + compiler phase chain. In this use case there are no plug-in supplied + phases, that have to be included. Depending on the command line + options and the JVM target the for this target default phases are + added to the phases set. This is a set, because a phase may only + occur once in the compiler phase chain.</p> + + <p>Following these basic <code>runsAfter</code> constraints the + compiler phase chain is build from the phases set. In the example + below a simple set of phase constraints can be converted into a + graph, that in turn can be converted into a list of phases. + </p> + <div style="text-align: center;"> + <img src="sip-00002-1.png" alt="" border="0" width="100%" height="" /> + </div> + + <p>Using the <code>runsAfter</code> list as the basic ordering + constraints there are some more properties that have to be + full filled. + </p> + <ul> + <li>The phases <code>liftcode</code> and <code>flatten</code> are + only included for the JVM target. They have <code>runsAfter</code> + dependencies on the <code>refchecks</code> phase and the + <code>constructors</code> phase, respectively. Because they are + only included in the JVM target the <code>uncurry</code> phase and + the <code>mixin</code> phase, respectively, need to have multiple + dependencies as seen in the example below. + + <p>This example shows the desired transformation steps of a small + dependency graph taken from the actual compiler phase graph. When + processing <code>refchecks</code> we notice that it has two + dependencies to it. One dependency comes from + <code>liftcode</code> and the other from <code>uncurry</code>. We + now look if any of these phases have more then one outgoing + dependency. The <code>liftcode</code> phase has one outgoing + dependency, but the <code>uncurry</code> phase has two, so one of + the outgoing dependencies of <code>uncurry</code> has to go to + <code>refchecks</code> and the other dependency has to go to some + place we have not visited yet. So by this reasoning, we can safely + remove the dependency from <code>uncurry</code> to + <code>refchecks</code> (marked red).</p> + + <div style="text-align: center;"> + <img src="sip-00002-21.png" alt="" border="0" width="85%" height="" /> + </div> + <p></p> + </li> + + <li>Some internal phase pairs have very strong dependencies, like + the phases <code>explicitouter</code> and <code>erasure</code> and + also the <code>namer</code> and <code>typer</code> phases. See <a + href="#usecase7">use case 7</a> for more information on this + problem.</li> + </ul> + + + <a name="usecase2"></a> + <h4>[2] Assembling compiler internal phases for the MSIL target and + no plug-ins are loaded.</h4> + + <p>Like in <a href="usecase1">use case 1</a> depending on command + line options and that the target being MSIL, the proper phases are + added to the phases set. Again there are no plug-in supplied phases + to be included. There are however some differences to use case 1. + </p> + <ul> + <li>The phases <code>liftcode</code> and <code>flatten</code> are + not included for the MSIL target. This makes the + <code>runsAfter</code> list of the phases <code>uncurry</code> and + <code>mixer</code> special by containing dependencies to phases + that are found in the phases set. + + <p>For instance the <code>uncurry</code> phase has to specify that + it wants to run after both <code>refchecks</code> and + <code>liftcode</code>. <i>(For the JVM target this will force the + <code>liftcode</code> phase before <code>uncurry</code>.)</i> For + the MSIL target the phase <code>liftcode</code> is not present as + shown in the example diagram below. One solution that will work is + to silently drop all dependencies to phases, where there was no + phase object in the phases set.</p> + + <div style="text-align: center;"> + <img src="sip-00002-22.png" alt="" border="0" width="55%" height="" /> + </div> + </li> + </ul> + + + + <a name="usecase3"></a> + <h4>[3] Adding one plug-in supplied phase to the JVM target + compiler after type checking.</h4> + + <p>Like in <a href="#usecase1">use case 1</a> the internal phases + are added to the phases set. In this use case a plug-in is loaded + that will supply one phase to the phases set with a constraint that + it wants to run after the <code>refchecks</code> phase. The original + plug-in handling code will still handle loading plug-ins, disabling + plug-ins, but will no longer have the responsibility of assembling + the compiler chain. The plug-in is loaded and the phase is added + to the phases set together with the internal phases.</p> + <p>When assembling the compiler phase chain in this use case, there + will be two phases directly after the <code>refchecks</code> phase + and the dependencies can not be removed as described in <a + href="#usecasee1">use case 1</a>. This situation is shown in the + example below.</p> + + <div style="text-align: center;"> + <img src="sip-00002-2.png" alt="" border="0" width="100%" height="" /> + </div> + + <p>One of the goals of this proposal is to be as compatible with the + current behavior of the compiler as possible. So if the situation is + as shown above that after including A, we can either take B or R, we + need a deterministic scheme for always constructing the same phase + chain. This is done by taking the plug-in supplied phases first and + then the internal phase after wards. + </p> + + + + <a name="usecase4"></a> + <h4>[4] Adding two plug-in supplied phase to the JVM target + compiler after type checking.</h4> + + <p>This use case is very similar to <a href="#usecase3">use case + 3</a>, however instead of having one internal and one external phase + after the <code>refchecks</code> phase, we have one internal and two + external phases after the <code>refchecks</code> phase. This + situation is shown in the example below.</p> + + <div style="text-align: center;"> + <img src="sip-00002-23.png" alt="" border="0" width="100%" height="" /> + </div> + + <p>To be able to deterministically create the compiler phase chain + we need a rule to handle multiple external phases at the same + level. The simplest rule it to include the external phases + alphabetically order, as shown in the example above.</p> + + + <a name="usecase5"></a> + <h4>[5] Adding two plug-in supplied phases, where one has a + dependency on the other, to the JVM target compiler.</h4> + + <p>This use case is very similar to <a href="#usecase4">use case + 4</a>, however instead of the two plug-in supplied phases having a + dependency on the same internal, one of the plug-in supplied phases + has a dependency on the other and the other has a dependency on an + internal phase. This is the example shown in the diagram below.</p> + + <div style="text-align: center;"> + <img src="sip-00002-3.png" alt="" border="0" width="100%" height="" /> + </div> + + <p>As described in <a href="#usecase3">use case 3</a>, after + inclusion of phase A the next phase to include is phase T. In the + example above phase R is dependent on phase T, so the next to + include is phase R. This means that including phase T, means to + include T and the ordered sub tree, under phase T.</p> + + <p>The example shown below, can be solved applying the same logic as + described above.</p> + + <div style="text-align: center;"> + <img src="sip-00002-4.png" alt="" border="0" width="100%" height="" /> + </div> + + + <a name="usecase6"></a> + <h4>[6] Adding plug-in supplied phases with dependencies to both + plug-in supplied and internal phases to the JVM target + compiler.</h4> + + <p>This use case builds upon <a href="#usecase1">use case 1</a>, <a + href="#usecase3">use case 3</a>, <a href="#usecase4">use case 4</a> + and <a href="#usecase5">use case 5</a> and shows how to handle + plug-in supplied phases with dependencies on other plug-in supplied + and internal phases.</p> + + <p>In the example shown below the plug-in supplied phase T has + dependencies on the plug-in supplied phase P and the internal phase + B. The transformation shown below is made by applying the logic from + <a href="#usecase1">use case 1</a> to this example and using the + assumption that the dependencies of the internal phases will not + contain cycles and internal phases are visited last on each + level.</p> + + <div style="text-align: center;"> + <img src="sip-00002-5.png" alt="" border="0" width="100%" height="" /> + </div> + + <a name="usecase7"></a> + <h4>[7] Two separate phases that should be handled as a single + phase.</h4> + + <p>In <a href="#usecase1">use case 1</a> we specified the assembly + of the compiler phase chain based on runs after + constraints. However, the compiler contains some phase pairs that + have very strong dependencies on each other or it simply does not + make sense to put a phase in between. In this use case we will focus + on the situation that we have two individual phase objects, but one + needs to run right after the other and thereby act as one large + phase.</p> + + <p>The solution to this is to introduce a new runs right after + constraint to all phases. To keep the compatibility with current + plug-ins as high as possible, this runs right after constraint is + only mandatory for internal phases. In the example below the + <code>runsRightAfter</code> constraint is marked as a blue arrow and + behaves as a normal runs after constraint. + </p> + <div style="text-align: center;"> + <img src="sip-00002-7.png" alt="" border="0" width="100%" height="" /> + </div> + + <p>In the example shown below, we can see the first four phases of + the Scala compiler. There is a <code>runsRightAfter</code> + constraint between <code>typer</code> and <code>namer</code>. There + is in this example a plug-in supplied phase (plugin1) that want to + run after the <code>namer</code> phase. The semantics of the run + after constraint is that is should run somewhere after a specified + phase, but as soon as possible. With this in mind it is perfectly + valid to change the dependency of <code>plugin1</code> from + <code>namer</code> to <code>typer</code>. </p> + <div style="text-align: center;"> + <img src="sip-00002-8.png" alt="" border="0" width="100%" height="" /> + </div> + + <p>If the phase <code>plugin1</code> had declared to + <code>runRightAfter</code> the <code>namer</code> phase, this would + result in a unsolvable graph and would therefore generate an error, + because only one phase can come right after another phase. + </p> + + <a name="usecase8"></a> + <h4>[8] A cyclic dependency among phases is a fatal error.</h4> + + <p>Running the compiler without loading plug-ins, it is guaranteed + that there are do cyclic dependencies among the internal phases, so + the only way to introduce cycles in the phase graph is by loading + one or more plug-ins. If a cycle is detected in the phase graph the + compiler should refuse to start and give a proper error message.</p> + + <p>In the example shown below a cycle is detected and marked in + pink. A cycle like this would generate a cyclic dependency error and + outputting the names of the involved phases.</p> + + <div style="text-align: center;"> + <img src="sip-00002-20.png" alt="" border="0" width="35%" /> + </div> + + <a name="usecase9"></a> + <h4>[9] Special handling of the <code>parser</code> and + <code>terminal</code> phases.</h4> + + <p>There are two very special phase objects in the phase graph. The + first phase is the <code>parser</code> phase. This phase will be the + head of the compiler phase chain, there are however no other + restrictions on this phase.</p> + + <p>The other special phase is the <code>terminal</code> phase, which + has to be the last phase in the compiler phase chain. For this + reason it is not allowed to run after or run right after the + <code>terminal</code> phase. Any phase that specifies a runs after + or runs right after dependency on the <code>terminal</code> phase + will have that dependency dropped silently.</p> + + + <a name="usecase10"></a> + <h4>[10] Larger compiler example with three plug-in supplied phases.</h4> + + <p>This example is implemented in the <a + href="#implementation">reference implementation</a> of the algorithm + below. In this example the compiler consists of nine internal phases + and two plug-ins are loaded adding a total of three phases to the + compiler. + </p> + + <table width="100%" border="1"> + <tr> + <td><strong>Phase name</strong></td> + <td><strong>Runs after</strong></td> + <td><strong>Runs right after</strong></td> + </tr> + <tr> + <td colspan="3" align="center"><strong><i>Internal phases</i></strong></td> + </tr> + <tr> + <td>nsc::parser</td> + <td></td> + <td></td> + </tr> + <tr> + <td>nsc::typer</td> + <td>nsc::parser</td> + <td></td> + </tr> + <tr> + <td>nsc::pickler</td> + <td>nsc::typer</td> + <td></td> + </tr> + <tr> + <td>nsc::liftcode</td> + <td>nsc::pickler</td> + <td></td> + </tr> + <tr> + <td>nsc::tailcalls</td> + <td>nsc::pickler<br />nsc::liftcode</td> + <td></td> + </tr> + <tr> + <td>nsc::erasure</td> + <td></td> + <td>nsc::tailcalls</td> + </tr> + <tr> + <td>nsc::cleanup</td> + <td>nsc::erasure</td> + <td></td> + </tr> + <tr> + <td>nsc::jvm</td> + <td>nsc::cleanup</td> + <td></td> + </tr> + <tr> + <td>nsc::terminal</td> + <td>nsc::jvm<br />nsc::msil</td> + <td></td> + </tr> + <tr> + <td colspan="3" align="center"><strong><i>Plug-in supplied phases</i></strong></td> + </tr> + <tr> + <td>plug1::optimization1</td> + <td>nsc::typer</td> + <td></td> + </tr> + <tr> + <td>plug2::optimization1</td> + <td>nsc::liftcode</td> + <td></td> + </tr> + <tr> + <td>plug2::optimization2</td> + <td>plug2::optimization1<br />nsc::cleanup</td> + <td></td> + </tr> + </table> + + <p>Using the phases in the table above as the basis for the + dependency graph, the following graph will be constructed. This + graph contains all the information that is also present in the + phases set. As seen in the diagram below there are nodes without + phase objects (marked with dotted lines) and nodes with multiple + dependencies. There could also be cycles at this stage, but there + are non in this example. + </p> + + <div style="text-align: center;"> + <img src="sip-00002-6.png" alt="" border="0" width="60%" height="" /> + </div> + + <p>The transformation of the dependency graph into a dependency tree + is the basis of this proposal. The resulting dependency tree is + shown below. This tree is then the basis for generating the compiler + phase list. + </p> + + <div style="text-align: center;"> + <img src="sip-00002-24.png" alt="" border="0" width="60%" height="" /> + </div> + + <p>The resulting compiler phase list of traversing the tree above is + shown below. It is ensured that the <code>parser</code> phase is the + first and that the <code>terminal</code> phase is the last in this list.</p> + + <ul> + <li>nsc::parser</li> + <li>nsc::typer</li> + <li>plug1::optimization1</li> + <li>nsc::pickler</li> + <li>nsc::liftcode</li> + <li>plug2::optimization1</li> + <li>nsc::tailcalls</li> + <li>nsc::erasure</li> + <li>nsc::cleanup</li> + <li>plug2::optimization2</li> + <li>nsc::jvm</li> + <li>nsc::terminal</li> + </ul> + + <a name="futuregoals"></a> + <h3>Future Goals That Extend Beyond This Proposal</h3> + + <ul> + <li>Create and add new backends to the compiler that will replace + the JVM or MSIL specific phases using plug-ins.</li> + <li>Creating internal tools by subclassing the class + <code>Global</code>.</li> + <li>The constraint system should not contain support for the + following constraints. + <ul> + <li>A phase should be able to declare that it will replace a + given phase and thereby ignoring other constraints declared by + this phase and taking over the constraints from the replaced + phase.</li> + <li>A phase should be able to declare that if included it will + remove a given number of phases and removing constraints to + these phases.</li> + <li>A phase should be able to declare that it only wants to be + included if a given phase is also present or else it will be + silently dropped.</li> + </ul> + </li> + </ul> + + <a href="#top">To the top</a> + + <a name="description"></a> + <h2>Description</h2> + + <p>This section will cover a short description of the present design + and the full description of the proposed design changes, including + the constraint system and algorithm for solving the constraint + system. + </p> + + <a name="presentdesign"></a> + <h3>The Present Design</h3> + + <p>Currently phases in the compiler are ordered statically by a hard + coded list structure in <code>class Global</code> (found in + Global.scala), where the method <code>builtInPhaseDescriptors</code> + returns the list of phase objects. The resulting list from invoking + this method is then extended with the phases from the plug-in + supplied by the user. This is done in the + <code>computePhaseDescriptors</code> method in <code>class + Plugins</code> (found in plugins/Plugins.scala). This method is + then again called from the method <code>phaseDescriptors</code> in + <code>class Global</code>. So all together the process of + calculating the phases of the compiler is spread over several files + and quite complicated.</p> + + <p>A plug-in can supply a number of phases to the compiler and the + architecture of the plug-in subsystem already supply some of the + functionality that will be added to all internal phases. All phases + are a subclass of <code>class SubComponent</code> and all phases + supplied by plug-ins are subclasses of <code>class + PluginComponent</code> (which is a subclass of <code>class + SubComponent</code>).</p> + + <a name="proposeddesign"></a> + <h3>The Proposed Design</h3> + + <p>This section will cover the design of the proposed system for + handling inclusion of internal and external phases uniformly. It + will also cover a description of the constraint system and a + algorithm for solving these constraint for generating the compiler + phase chain. This design will focus on satisfying the use cases <a + href="#usecases">described earlier</a>. + </p> + + <p>From the use cases above it is possible to identify two kinds of + constraints. The first constraint is the <i>runs after</i> + dependency and the second constraint is the <i>runs right after</i> + dependency. It is necessary to declare that a given phase has to + <i>runs after</i> a list of phase names, however the <i>runs right + after</i> constraint only needs to declare the name one phase. + </p> + <ul> + <li>Lets define the <i>runs after</i> constraint using the + <code>runsAfter</code> variable with the Scala type + <code>List[String]</code>. Using this constraint, phase B would + declare <code>runsAfter=List(A)</code>, meaning that phase B would + like to run somewhere after phase A, but as early as possible.</li> + + <li>Lets define the <i>runs right after</i> constraint using the + <code>runsRightAfter</code> variable with the Scala type + <code>Option[String]</code>. Using this constraint, phase B would + declare <code>runsRightAfter=Some(A)</code>, meaning that phase B + wants to run right after phase A and no other phases are allowed to + come between phase A and B. From a larger perspective meaning that + phase A and B can be regarded as on large phase with one input and + one output.</li> + </ul> + + <p>A goal of this work is to handle the inclusion and constraint + resolution of internal and plug-in supplied phases in a uniform way, + this also means that the responsibility of phase assembly should not + be handled by the plug-in subsystem any more, but by a separate + instance. For this separate instance we create a new + <code>PhaseAssembly</code> trait that is mixed into the + <code>Global</code> class in the same way as <code>Plug-Ins</code> + is mixed in. + </p> + + <p>In the diagram below a schematic overview of the proposed system + is shown. A description of the individual components and the + modification needed are given below. + </p> + + <div style="text-align: center;"> + <img src="sip-00002-9.png" alt="" border="0" width="55%" /> + </div> + + <a name="propdesign1"></a> + <h4>1. Internal Phases</h4> + + <p>All internal phase objects are declared in class + <code>Global</code> and will be extended to include the + <code>runsAfter</code> and the <code>runsRightAfter</code> variables + with the types described above. This will ensure that the internal + phases will always succeed in creating a compiler phase chain + depending on the compiler target. + </p> + <p>The phase objects that are needed for a given target will be + added to the phases set. See <a href="#propdesign3">3. Phases + Set</a> for more information. + </p> + + + <a name="propdesign2"></a> + <h4>2. External Phases</h4> + + <p>All external phases are supplied through plug-ins. All these + phases inherit from class <code>PluginComponent</code>. Defining the + <code>runsRightAfter=None</code> in class + <code>PluginComponent</code> will make the changes to the existing + plug-ins minimal, but makes it possible for external phases to use + the feature by simple overriding the variable if needed. + </p> + <p>It is still the responsibility of the plug-in subsystem to load + the actual plug-ins from the jar files and also the processing of + all the <code>-Xplugin*</code> compiler options available at the + command line. The phase assembly code currently present in the + plug-in subsystem will be replaced by code that adds all plug-in + supplied phases to the phases set. See <a + href="#propdesign3">3. Phases Set</a> for more information. + </p> + + <a name="propdesign3"></a> + <h4>3. Phases Set</h4> + + <p>The phases set contains all the phase objects that should be + taken into consideration when performing compiler phase chain + assembly. This phases set would located in the class + <code>Global</code>. A proper Scala declaration of such a phases set + is shown below. + </p> + <pre>protected val phasesSet : HashSet[SubComponent] = new HashSet[SubComponent]()</pre> + + <p>Ensuring that all phase objects are unique with respect to the + phase names, the <code>hashCode</code> method in class + <code>SubComponent</code> will be overridden to return the hash code + of the phase name and not the object itself. + </p> + + <a name="propdesign4"></a> + <h4>4. Phase Assembly</h4> + + <p>From a compiler design perspective this component will include + the data structures and implementation of the constraint solving + algorithm that are needed to implement this proposal. It would be + integrated as a <code>trait PhaseAssembly</code> that is mixed into + <code>class Global</code> with this self type <code>self: Global + =></code>. + </p> + + <p>A very high level description of the actions performed by this + component can be split into three distinct parts. A detailed + algorithm that implements this high level description can be found + below in the <a href="#constsolver">section on the constraint + solving algorithm</a>. + </p> + + <ol> + <li><strong>Phases Set to Dependency Graph</strong><br /> + <p>From the phase objects in the phases set a dependency graph is + created, where the edges in this graph are constructed from the + <code>runsAfter</code> and <code>runsRightAfter</code> + constraints. Each node in the dependency graph has both a phase + name and a phase object, because all constraints in the phase + objects are only given by name. + </p> + </li> + <li><strong>Dependency Graph to Dependency Tree</strong><br /> + <p>To be able to create the compiler phase chain the dependency + graph has to be converted into a dependency tree. The dependency + graph contains nodes that have a phase name, but no phase + object. These nodes have to be removed. Also all edges in the + graph that are generated from <code>runsRightAfter</code> + constraints have to be handled special to enforce this constraint + and the graph is checked for cycles. If a cycle is found, the + algorithm will terminal with a fatal error, preventing the + compiler from starting. If no cycles are found in the dependency + graph is simplified with respect to what will become the root in + the dependency tree, by removing unneeded dependency edges. This + will transform the dependency graph into a dependency tree. + </p> + </li> + <li><strong>Dependency Tree to Compiler Phase List</strong><br /> + <p>The compiler phase list is constructed by traversing the + dependency tree from the root. The traversal algorithm will be + described below. + </p> + </li> + </ol> + + + <a name="propdesign5"></a> + <h4>5. Constraint System</h4> + + <p>The constraint system is implemented as a graph structure where + phases are modeled as nodes and the constraints are modeled as + directed edges. This section will describe the basic entities of the + constraint system and how they are modeled in the dependency graph.</p> + <table> + <tr> + <td colspan="2"> + <p>Each node in the dependency graph contains several items of + information about the phase object and the dependencies to and + from it.</p> + </td> + </tr> + <tr> + <td> + <ul> + <li><strong>phaseobj:</strong> <i>(type: + SubComponent)</i><br /> A reference to the actual phase + object, if there is any. If there is a phase object then + there is also a phase name, but the constraints are only + given by name, so some nodes may have a phase name and no + phase object. + </li> + <li><strong>phasename:</strong> <i>(type: String)</i><br /> + The name of the phase object. This is always set. + </li> + <li><strong>after:</strong> <i>(type: HashSet[Edge]())</i> + <br /> + This is the set of <code>Edge</code> object that point to + <code>Node</code> objects that have to come before this + <code>Node</code>. So all <code>runsAfter</code> and + <code>runsRightAfter</code> constraints given by a phase + object are present in this <code>after</code> list. + </li> + <li><strong>deps:</strong> <i>(type: HashSet[Edge]())</i> + <br /> + This is the set of <code>Edge</code> object that points to + this <code>Node</code> object. So its the opposite of the + <code>after</code> list. + </li> + </ul> + </td> + <td> + <div style="text-align: center;"> + <img src="sip-00002-15.png" alt="" border="0" width="235" height="186" /> + </div> + </td> + </tr> + <tr> + <td colspan="2"> + <p>Each edge in the dependency graph is directed, so it has + references to its to and from <code>Node</code> objects and + knows if it is created from a <code>runsAfter</code> + constraint (soft) or created from a + <code>runsRightAfter</code> constraint (hard). </p> + </td> + </tr> + <tr> + <td> + <ul> + <li><strong>to:</strong> <i>(type: Node)</i> + <br /> + This is a reference to the <code>Node</code> object this + <code>Edge</code> object is pointing to. This means that the + <code>frm</code> node has a dependency on the + <code>to</code> node. + </li> + <li><strong>frm:</strong> <i>(type: Node)</i> + <br /> + This is a reference to the <code>Node</code> object this + <code>Edge</code> object is pointing from. + </li> + <li><strong>hard:</strong> <i>(type: Boolean)</i> + <br /> + In the dependency graph we have soft and hard + dependencies. The soft dependencies are created from the + <code>runsAfter</code> list of constraints. The hard + dependencies are created from the + <code>runsRightAfter</code> constraint, if any. + </li> + </ul> + </td> + <td> + <div style="text-align: center;"> + <img src="sip-00002-16.png" alt="" border="0" width="152" height="186" /> + </div> + </td> + </tr> + </table> + + <p>Below is the interface implementation of the dependency graph in + Scala. There are classes implementing the edges and nodes and the + container for storing the edges and nodes and aux. method for easy + access to the stored information. + </p> + <pre> +class Edge(f: Node, t: Node, h: Boolean) { + var frm = f + var to = t + var hard = h +} + +class Node(phs:SubComponent, name:String) { + var phasename: String = name + var phaseobj: SubComponent = phs + var after: HashSet[Edge] = new HashSet[Edge]() + var deps: HashSet[Edge] = new HashSet[Edge]() +} + +class DependencyGraph { + + val nodes = new HashMap[String,Node]() + val edges = new HashSet[Edge]() + + def getNodeByPhase(name : String) : Node + def getNodeByPhase(phs : SubComponent) : Node + def softConnectNodes(frm: Node, to: Node) : Unit + def hardConnectNodes(frm: Node, to: Node) : Unit +} + </pre> + + + <a name="constsolver"></a> + <h4>Constraint Solving Algorithm</h4> + + <p>This algorithm will build a list of phase objects from a set of + phase objects with constraints. The position of each phase object in + the final list will ensure that all its constraints are + satisfied. The algorithm does this by constructing a dependency + graph from the set of phase objects. This dependency graph is then + over a series of steps converted into a dependency tree with a root + node. To construct the final compiler phase list the dependency tree + is traversed from the root building the list of phase objects.</p> + + <p>The function below is the top most function of this algorithm + that transforms the set of phase objects into a ordered list of + phase objects so all constraints are satisfied. This function + follows the description given about the <a href="#propdesign4">phase + assembly component</a>. All the auxiliary functions will be covered + below.</p> + +<pre> <b>function</b> phasesSetToPhasesList(phasesSet) + + <i>// call function to generate dependency graph from phases set</i> + graph <- phasesSetToDepGraph( phaseSet ) + + <i>// call function to transform the dependency graph to a dependency tree.</i> + <i>// if the dependency graph contains a cycle a fatal error will be generated.</i> + rootnode <- depGraphToDepTree( graph ) + + <i>// call function to recursively build phase list from the root of </i> + <i>// the dependency tree</i> + phaselist <- depTreeToPhaseList( rootnode, <b>new</b> List() ) + + <b>return</b> phaselist +</pre> + + <p> List of functions called:</p> + <ul> + <li><a href="#func1">The <code>phasesSetToDepGraph</code> function</a></li> + <li><a href="#func2">The <code>depGraphToDepTree</code> function</a></li> + <li><a href="#func3">The <code>depTreeToPhaseList</code> function</a></li> + </ul> + + <a name="func1"></a> + <h5>The <code>phasesSetToDepGraph</code> function</h5> + + <p>The dependency graph, with the elements described in the <a + href="#propdesign5">section about the constraint system</a>, is + build from the phase objects in the phases set.<br /> + It works as follows: + </p> + <ul> + <li>create a new dependency graph</li> + <li>foreach phase in the phasesSet + <ul> + <li>create a new graph node <i>fromnode</i> from the phase object and add the + ndoe to the graph</li> + <li>if the phase object has a runs right after constraint, then + create a node <i>tonode</i> from the phase name of the constraint and create a + hard edge between <i>fromnode</i> and <i>tonode</i>. Eventual + runs after constraints are ignored.</li> + <li>if the phase object has no runs right after constraints a + node <i>tonode</i> is created from each runs after constraint + and connected with a soft edge to the <i>fromnode</i>.</li> + </ul> + </li> + </ul> + + <p>A pseudo code version of this algorithm is shown below.</p> + +<pre> <b>function</b> phasesSetToDepGraph( phaseSet ) + <i>// create new graph structure to hold data</i> + graph <- <b>new</b> DependencyGraph + <i>// iterate over all phase objects in the phasesSet</i> + <b>for</b> phs <b>in</b> phasesSet + <i>// create a node from the phase object</i> + fromnode <- graph.getNodeByName(phs) + <i>// test if the phase object has a runs right after constraint</i> + <b>if</b> phs.runRightAfter <b>not eq</b> "" + <i>// create a node from the phase constraint name and connect with hard edge</i> + tonode <- graph.getNodeByName( phs.runRightAfter ) + graph.hardConnectNodes( fromnode, tonode ) + <b>else</b> + <i>// the phase object did not have a runs right after constraint</i> + <i>// iterate over all phase constraints in the runs after constraint list</i> + <b>for</b> phsname <b>in</b> phs.runsAfter + <i>// create a node from the phase constraint name and connect with soft edge</i> + tonode <- graph.getNodeByName( phsname ) + graph.softConnectNodes( fromnode, tonode ) + + <b>return</b> graph +</pre> + + + + <a name="func2"></a> + <h5>The <code>depGraphToDepTree</code> function</h5> + + <p>The process of converting the dependency graph into a dependency + tree is complex, so to simplify the algorithm the individual steps + are split into functions.<br /> + It works as follows: + </p> + + <ul> + <li>call method that will remove all nodes from the graph that + have no phase object attached</li> + <li>call method that will find all edges in the graph that are + marked as hard and enforce that the <code>deps</code> list of the + edges <code>to</code> node reference only contains this + edge. Other edges are moved down to the edges <code>frm</code> + node reference</li> + <li>What is to become the root of the dependency tree and also the + first element in the phase list is extracted from the graph.</li> + <li>call method to check if there are cycles in the graph starting + from the root node, if there are cycles a fatal error is generated</li> + <li>call method to simplify graph into a tree by removing edges + that will not break the constraints given</li> + </ul> + + <p>Below is shown a pseudo code version of the function.</p> + + <pre> <b>function</b> depGraphToDepTree( graph ) + + <i>// Remove all nodes where phaseobj == null</i> + removeDanglingNodes( graph ) + + <i>// Enforce hardlinks / runsRightAfter and promote nodes down the tree</i> + enforceHardlinks( graph ) + + <i>// Extract the root node from the graph</i> + root <- graph.getNodeByPhase( ROOTNAME ) + + <i>// Test for cycles in the graph, if found generate fatal error</i> + testForCycles( root, <b>new</b> Set() ) + + <i>// Simplify graph by removing edges, starting from the given root node</i> + simplifyGraphFromNode( root, graph ) + + <b>return</b> root + </pre> + + <p> List of functions called:</p> + <ul> + <li><a href="#func4">Helper function <code>removeDanglingNodes</code></a></li> + <li><a href="#func5">Helper function <code>enforceHardlinks</code></a></li> + <li><a href="#func6">Helper function <code>testForCycles</code></a></li> + <li><a href="#func7">Helper function <code>simplifyGraphFromNode</code></a></li> + </ul> + + <a name="func3"></a> + <h5>The <code>depTreeToPhaseList</code> function</h5> + + <p>The graph has been transformed into a tree and a reference to the + root node is identified. The tree is now traversed from the root + node, by calling itself recursively on each node object. The empty + list is given to the function together with the root node and the + phase objects are added to the list as the function traverses the + tree.<br /> + It works as follows:</p> + + <ul> + <li>the function is called with a node object and a list</li> + <li>the phase object of the node object, the function was call + with, is added to the list</li> + <li>if this node has no nodes that depend on it, the list of phase + objects is returned</li> + <li>if this node has only one node that depends on it, we call + recursively with that node and the list as arguments, the result + of this is returned</li> + <li>if this node has more then one node that depends upon it, + these dependent nodes are ordered. We now iterate over this + ordered list of nodes and call recursively the function.</li> + </ul> + + <p>Below is shown a pseudo code version of the function.</p> + + <pre> <b>function</b> depTreeToPhaseList( node, chain ) + <i>// add the phase object of the node to the chain list</i> + chain <- chain.append( node.phaseobj ) + <i>// no more depends, return the chain</i> + <b>if</b> node.deps.length == 0 + <b>return</b> chain + <i>// only one depend, so no need to order one element, just call recursively </i> + <b>else if</b> node.deps.length == 1 + <b>return</b> depTreeToPhaseList( node.deps.getFirst().frm, chain ) + <i>// more then one depend</i> + <b>else</b> + <i>// the depends are ordered and saved as a list</i> + order <- dependencyOrder( node.deps ) + <i>// iterate over the list of ordered depend nodes and call recursively </i> + <b>for</b> nd <b>in</b> order + chain <- depTreeToPhaseList( nd, chain ) + <i>// return the complete chain</i> + return chain + </pre> + + <p> List of functions called:</p> + <ul> + <li><a href="#func8">Helper function <code>dependencyOrder</code></a></li> + </ul> + + <a name="func4"></a> + <h5>Helper function <code>removeDanglingNodes</code></h5> + + <p>This helper function will given a dependency graph find all nodes + that have no reference to a phase object and remove these nodes from + the graph. (See <a href="#usecase2">use caes 2</a>) These nodes that + have no phase object are generated from runs after or runs right + after constraints to phases that are not loaded.<br /> It is done as + follows:</p> + + <ul> + <li>create a list L of all nodes in the given graph that have no + phase object</li> + <li>foreach node in L + <ul> + <li>remove the node from the graph</li> + <li>foreach edge in the nodes deps list, remove this edge from + the graph</li> + </ul> + </li> + </ul> + + <p>Below is shown a pseudo code version of the function.</p> + + <pre> <b>function</b> removeDanglingNodes( graph ) + <i>// find all nodes with no phase object</i> + dnodes <- filter( lambda node: node.phaseobj == null, graph.nodes ) + <i>// iterate over these nodes and remove them one by one</i> + <b>for</b> node <b>in</b> dnodes + graph.nodes.remove( node ) + <i>// also remove all edge objects related to this node object</i> + <b>for</b> edge <b>in</b> node.deps + graph.edges.remove( edge ) + edge.frm.after.remove( edge ) + </pre> + + + <a name="func5"></a> + <h5>Helper function <code>enforceHardlinks</code></h5> + + <p>This helper function will given a dependency graph find all edges + in the graph that are marked as hard. It will then ensure that the + <code>to</code> node the edge is pointing to only has this edge in + its deps list. (See <a href="#usecase7">use case 7</a>).<br /> + It works as follows: + </p> + + <ul> + <li>loop until no edges are moved + <ul> + <li>create list L of all edges in the given graph that are marked + as hard</li> + <li>foreach edge in L + <ul> + <li>create list HE of edges marked as hard in the deps list of + the node object this edge is pointing to</li> + <li>if there is more then one element in HE it will not be possible + to generate a compiler phase list and a fatal error is + generated</li> + <li>if there is only one element in HE, create a list E of all + the edges not marked as hard in the deps list of + the node object this edge is pointing to</li> + <li>override the deps list of the node object this edge is + pointing to with the HE list</li> + <li>foreach pedge in E + <ul> + <li>attach the pedge to the deps list of the node object this + edge is pointing from</li> + </ul> + </li> + </ul> + </li> + </ul> + </li> + </ul> + + <p>Below is shown a pseudo code version of the function.</p> + + <pre> <b>function</b> enforceHardlinks( graph ) + <b>do</b> + <i>// lets assume that no edges are moved until proven otherwise</i> + rerun <- <b>false</b> + <i>// find all edges in the graph that are marked as hard</i> + hardlinks <- <b>filter</b>( <b>lambda</b> e: e.hard, graph.edges ) + <i>// iterate over all hard edges found</i> + <b>for</b> edge <b>in</b> hardlinks + <i>// find all hard edges in the deps list of the node this edge points to</i> + sanity <- <b>filter</b>( <b>lambda</b> e: e.hard, edge.to.deps ) + <b>if</b> sanity.length > 1 + <i>// generate fatal error, there is more then one runs right + // after constraint on the same node</i> + <b>else</b> + <i>// find all non hard edges in the deps list of the node this edge points to</i> + promote <- <b>filter</b>( <b>lambda</b> e: not e.hard, edge.to.deps ) + <i>// assign the list of hard edges to the deps list of the node this + // edge points to</i> + edge.to.deps <- sanity + <i>// iterate over all non hard edges and attach them to the deps list of the + // node this edge points from</i> + <b>for</b> pedge <b>in</b> promote + <i>// we have moved an edge - we need to rerun this to check</i> + rerun <- true + <i>// move the edge object down along the hard edge</i> + pedge.to <- edge.frm + edge.frm.deps.attach(pedge) + <i>// if edges where moved, then rerun to make sure the structure is valid</i> + <b>while</b> rerun + </pre> + + <p>To better understand this little function, lets look at some + diagrams and how this function works on these examples. The first + example is shown below. Here phase B wants to run right after phase + A and phase C just wants to run somewhere after phase A, so there is + no problem in pushing phase C down to run after phase B. The + function does this be first finding all the hard edges (the blue + edges). It then inspects the edges one by one and in this example we + have only one hard edge. The edge goes from phase B to phase A, + meaning that phase B want to run right after phase A. The algorithm + now looks at the <code>deps</code> list of phase A and finds that + there is only one hard edges (this is very good). The algorithm now + filters out the non-hard edges and finds the edge to phase C. This + edge is now detached from phase A and attached to phase B. + </p> + + <div style="text-align: center;"> + <img src="sip-00002-17.png" alt="" border="0" width="40%" /> + </div> + + <p>With the same arguments can we also handle the situation shown + below.</p> + + <div style="text-align: center;"> + <img src="sip-00002-18.png" alt="" border="0" width="45%" /> + </div> + + + <a name="func6"></a> + <h5>Helper function <code>testForCycles</code></h5> + + <p>This helper function will, given a node in the graph and a set + containing node names, determine of there are any cycles in the + graph. This will ensure that <a href="#usecase8">use case 8</a> is + addressed. Please note that this function will call itself + recursively and is called the first time with the root node and an + empty set of node names. + <br /> + It is done as follows: + </p> + + <ul> + <li>test if the name of the node is already contained in the set, + if it is a cycle is found and a fatal error is generated.</li> + <li>if the name is not in the set, the name of the node is added + to the set</li> + <li>the deps list of the node is ordered and stored in nodes</li> + <li>foreach nd in nodes + <ul> + <li>call the function recursively with the node nd and the set + of node names</li> + </ul> + </li> + <li>remove the name of the node from the set</li> + </ul> + + <p>Below is shown a pseudo code version of the function.</p> + + <pre> <b>function</b> testForCycles( node, names ) + <i>// test if the name of the node is already in the set</i> + <b>if</b> names.contains( node.phasename ) + <i>// names are unique, so this is a fatal error, there is a cycle + // the same name has been visited twice</i> + + <i>// add the name of the node to the set</i> + names.add( node.phasename ) + <i>// use the dependencyOrder function to sort the deps of the node</i> + nodes <- dependencyOrder( node.deps ) + <i>// iterate over all deps nodes and call recursively</i> + <b>for</b> nd <b>in</b> nodes + testForCycles(nd, names) + + <i>// remove the name of the node from the set</i> + names.remove( node.phasename ) + </pre> + + <p> List of functions called:</p> + <ul> + <li><a href="#func8">Helper function <code>dependencyOrder</code></a></li> + </ul> + + <p>There are other ways of detecting cycles in graphs, that are + faster and more efficient, please <a + href="http://www.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK2/NODE68.HTM">read + here</a> for more information.</p> + + <a name="func7"></a> + <h5>Helper function <code>simplifyGraphFromNode</code></h5> + + <p>This helper function will, given a node in the graph and a + reference to the graph structure, remove unneeded edges and + transforming the graph into a tree. Please note that this + function will call itself recursively and is called the first time + with the root node and the full graph. + <br /> + It is done as follows: + </p> + + <ul> + <li>create an empty list RM</li> + <li>foreach edge in the deps list of the node, if the node this + edge is pointing from has mode then one dependencies then add this + edge to RM</li> + <li>foreach edge in RM, remove this edge from the graph</li> + <li>the deps list of the node is ordered and stored in nodes</li> + <li>foreach nd in nodes + <ul> + <li>call the function recursively with the node nd and the + updated graph</li> + </ul> + </li> + </ul> + + <p>Below is shown a pseudo code version of the function.</p> + + <pre> <b>function</b> simplifyGraphFromNode( node, graph ) + removal <- <b>new</b> List() + <b>for</b> edge <b>in</b> node.deps + <b>if</b> edge.frm.after.length > 1 + removal.append( edge ) + + <b>for</b> edge <b>in</b> removal + node.deps.remove( edge ) + edge.frm.after.remove( edge ) + graph.edges.remove( edge ) + + nodes <- dependencyOrder( node.deps ) + <b>for</b> nd <b>in</b> nodes + simplifyGraphFromNode( nd, graph ) + </pre> + + <p> List of functions called:</p> + <ul> + <li><a href="#func8">Helper function <code>dependencyOrder</code></a></li> + </ul> + + + <p>In the example shown below we simplify this graph into a tree + from the node A. This means that we start the traversal from node A + and uses the <code>A.deps</code> list to continue the traversal. If + <code>A.deps</code> contains more then one element, the list is + sorted so we first visit all plug-in supplied phases in alphabetical + order and then the internal phase. In this example this gives the + order <code>[P,R,B]</code>. Before the algorithm traverses to a new + node it checks that node for its number of <code>after</code> + links. If it has more then one after link, it simply deletes the + link to it so it can carry on. In the example below this is the case + of node P and T. When the algorithm visits node P and wants to + traverse on to node T, it checks the number of <code>after</code> + constraints in node T. Node T has two after constraints so it can + safely delete the edge between node P and T, because there must be + another node that we have not included yet, that will include this + node T.</p> + + <div style="text-align: center;"> + <img src="sip-00002-19.png" alt="" border="0" width="70%" /> + </div> + + + <a name="func8"></a> + <h5>Helper function <code>dependencyOrder</code></h5> + + <p>This helper function will given a list of edges sort them + according to a specific scheme are return them as a list. The + sorting scheme is as follows. The returned list is the reverse of + first having the plug-in supplied phases in alphabetical order + followed by the internal phases. <br /> + This is done as follows: + </p> + <ul> + <li>nodes for internal and external phases are filtered from the + deps list</li> + <li>the external nodes are ordered by the phase name and + reversed</li> + <li>the external nodes are appended to the internal nodes list and + the resulting list is reversed</li> + </ul> + + <p>Below is shown a pseudo code version of the function.</p> + + <pre> <b>function</b> dependencyOrder( deps ) + external <- <b>filter</b>(<b>lambda</b> e: (! e.frm.phaseobj.internal), deps) + internal <- <b>filter</b>(<b>lambda</b> e: e.frm.phaseobj.internal, deps) + + extnodes <- <b>map</b>(<b>lambda</b> e: e.frm, external) + extnodes <- extnodes.sort(<b>lambda</b> (n1,n2): (n1.phasename compareTo n2.phasename) < 0) + extnodes <- extnodes.reverse + + nodes <- (<b>map</b>(<b>lambda</b> e: e.frm, internal)).<b>extend</b>( extnodes ) + nodes <- nodes.reverse + <b>return</b> nodes + </pre> + + + + <a name="namingscheme"></a> + <h3>Naming Scheme for Internal and External Phases</h3> + + <p>Having the ability to load a large number of plug-ins, where each + plug-in can supply several named phases, gives a high possibility of + name clashes. There is no way to enforce unique names in plug-in + supplied phases because they can have inter dependencies. The best + solution is to suggest a naming scheme for phase names.</p> + + <p>This naming scheme composes all names from the package/plug-in + name, then a double colon <code>::</code> and then the actual phase + name. So for the internal compiler phase names this would be:</p> + + <pre> val phaseName = "nsc::tailcalls"</pre> + + <p>For a plug-in with name <code>unit</code> that supplies a phase + with name <code>convert</code> the full phase name would be:</p> + + <pre> val phaseName = "unit::convert"</pre> + + <p>By using this naming scheme for all phases there is a namespace + for phase names within each plug-in and external phases will never + clash with internal phase names.</p> + + <a name="implications"></a> + <h3>Implications of This Proposal</h3> + + <p>All plug-ins need to be updated to the design in this + proposal. This means that all current plug-ins will not be able to + load. However the modifications to the existing plug-ins are + minor. Current variables and types: + </p> + <pre> val runsAfter: String</pre> + <p>The proposed changes are:</p> + <pre> val runsAfter: List[String]</pre> + + <p>All internal phases in the compiler need to declare there + ordering. This means that instead of having the ordering very + explicit in the list structure, the ordering is encoded into each + phase object. The following signatures will be added to the + <code>SubComponent</code> class.</p> + + <pre> val runsAfter: List[String] + val runsRightAfter: Option[String]</pre> + + <p>The following items must be added to each phase + object to implement the signatures (however they must be adapted to + the individual phase object).</p> + + <pre> val runsAfter = List[String]("phasename") + val runsRightAfter = None</pre> + + <p>There is no reason to change the names of the phases as suggested in + the section above, but it will minimize the chance of name clashes + and will also minimize the chance of accidental dependencies.</p> + + <a href="#top">To the top</a> + + <a name="implementation"></a> + <h2>Implementation</h2> + + <p>An example implementation has been created that follows the + algorithm sketched in this proposal and models the compilers + internal structure. This implementation can be found in the file <a + href="sip-00002-10.scala">sip-00002-10.scala</a>. The example + implementation uses the phases from <a href="#usecase10">use case + 10</a> as its data. + </p> + + <p>Running the example code</p> + + <ul> + <li>Compile the code using <code>scalac + sip-00002-10.scala</code></li> + <li>Run the example using <code>scala + depgraph.DepGraphTest</code></li> + <li>This will generate the console output as seen below and <a + href="http://www.graphviz.org/">Graphviz</a> dot files that can be + compiled into png images. These png images are also shown + below.</li> + </ul> + + <a name="consoleexample"></a> + <p>Console output</p> + + <pre>$ scalac sip-00002-10.scala +$ scala depgraph.DepGraphTest +[dropping depend on node with no phase: nsc::msil] +[removing edge: nsc::tailcalls => nsc::pickler] +[removing edge: plug2::optimization2 => plug2::optimization1] + - nsc::parser + - nsc::typer + - plug1::optimization1 + - nsc::pickler + - nsc::liftcode + - plug2::optimization1 + - nsc::tailcalls + - nsc::erasure + - nsc::cleanup + - plug2::optimization2 + - nsc::jvm + - nsc::terminal +$ </pre> + + <p>PNG images of the generated dot files showing the graph + structure. Internal phases are marked as black circles and plug-in + phases are marked as green circles. The hard links (runsRightAfter + constraints) are marked as blue arrows. Click on the pictures to + enlarge.</p> + <a name="examples"></a> + <table> + <tr> + <td valign="top"><strong>1. </strong><br /> + <div style="text-align: center;"> + <a href="sip-00002-11.png"> + <img src="sip-00002-11.png" alt="" border="0" width="100%"/> + </a> + </div> + </td> + + <td valign="top"><strong>2. </strong><br /> + <div style="text-align: center;"> + <a href="sip-00002-12.png"> + <img src="sip-00002-12.png" alt="" border="0" width="100%" /> + </a> + </div> + </td> + <td valign="top"><strong>3. </strong><br /> + <div style="text-align: center;"> + <a href="sip-00002-13.png"> + <img src="sip-00002-13.png" alt="" border="0" width="100%" /> + </a> + </div> + </td> + <td valign="top"><strong>4. </strong><br /> + <div style="text-align: center;"> + <a href="sip-00002-14.png"> + <img src="sip-00002-14.png" alt="" border="0" width="100%" /> + </a> + </div> + </td> + </tr> + </table> + + <a href="#top">To the top</a> + +</body> +</html> diff --git a/SIP/presip-classic.xhtml b/SIP/presip-classic.xhtml new file mode 100644 index 0000000000..3dac7c6e1d --- /dev/null +++ b/SIP/presip-classic.xhtml @@ -0,0 +1,29 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"> +<head> + <title>The Scala Classic Calculus</title> + <meta name="sip" content="XXXXX"/> + <meta name="author" content="Geoffrey Washburn"/> + <meta name="version" content="0"/> + <meta name="type" content="informational"/> + <meta name="status" content="submission"/> + <meta name="created" content="2008-08-21"/> + <meta name="updated" content="2008-08-21"/> + <!-- Stylesheet --> + <link rel="stylesheet" href="http://lampsvn.epfl.ch/svn-repos/scala/sip/trunk/sip.css" type="text/css"/> +</head> +<body> + <h1>The Scala Classic Calculus</h1> + + <p>Copyright © 2008, Geoffrey Washburn</p> + + <h2>Abstract</h2> + + This document describes the Scala Classic calculus that provides a + verified formal modal for a subset of the Scala language. This + calculus can be useful in understanding the Scala language + independently of the Scala Language Specification. + +</body> +</html> diff --git a/SIP/presip-constraints.xhtml b/SIP/presip-constraints.xhtml new file mode 100644 index 0000000000..a53d32e97a --- /dev/null +++ b/SIP/presip-constraints.xhtml @@ -0,0 +1,29 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"> +<head> + <title>Generalized type constraints</title> + <meta name="sip" content="XXXXX"/> + <meta name="author" content="Geoffrey Washburn"/> + <meta name="version" content="0"/> + <meta name="type" content="standards"/> + <meta name="status" content="submission"/> + <meta name="created" content="2008-08-21"/> + <meta name="updated" content="2008-08-21"/> + <meta name="scala-version" content="2.8.0"/> + <!-- <meta name="owner-contact" content="[URI]"/> --> + <!-- <meta name="discussion" content="[URI]"/> --> + <!-- <link rel="auxiliary" href="[URI]" type="[mime type]"/> --> + <!-- <link rel="replaces" href="[URI]" type="application/xhtml+xml"/> --> + <!-- <link rel="depends-on" href="[URI]" type="application/xhtml+xml"/> --> + <!-- Stylesheet --> + <link rel="stylesheet" href="http://lampsvn.epfl.ch/svn-repos/scala/sip/trunk/sip.css" type="text/css"/> +</head> +<body> + <h1>Generalized type constraints</h1> + <p>Copyright © 2008, Geoffrey Washburn</p> + + <h2>Abstract</h2> + +</body> +</html> diff --git a/SIP/presip-depmethods.xhtml b/SIP/presip-depmethods.xhtml new file mode 100644 index 0000000000..170a018423 --- /dev/null +++ b/SIP/presip-depmethods.xhtml @@ -0,0 +1,29 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"> +<head> + <title>Dependent method types</title> + <meta name="sip" content="XXXXX"/> + <meta name="author" content="Geoffrey Washburn"/> + <meta name="version" content="0"/> + <meta name="type" content="standards"/> + <meta name="status" content="submission"/> + <meta name="created" content="2008-08-21"/> + <meta name="updated" content="2008-08-21"/> + <meta name="scala-version" content="2.8.0"/> + <!-- <meta name="owner-contact" content="[URI]"/> --> + <!-- <meta name="discussion" content="[URI]"/> --> + <!-- <link rel="auxiliary" href="[URI]" type="[mime type]"/> --> + <!-- <link rel="replaces" href="[URI]" type="application/xhtml+xml"/> --> + <!-- <link rel="depends-on" href="[URI]" type="application/xhtml+xml"/> --> + <!-- Stylesheet --> + <link rel="stylesheet" href="http://lampsvn.epfl.ch/svn-repos/scala/sip/trunk/sip.css" type="text/css"/> +</head> +<body> + <h1>Dependent method types</h1> + <p>Copyright © 2008, Geoffrey Washburn</p> + + <h2>Abstract</h2> + +</body> +</html> diff --git a/SIP/sip.css b/SIP/sip.css new file mode 100644 index 0000000000..6c1a877fc9 --- /dev/null +++ b/SIP/sip.css @@ -0,0 +1,5 @@ +/* Default stylesheet for SIPs */ + +body { + width: 40em; +}
\ No newline at end of file diff --git a/SIP/virtual-traits/sip-0000X-1.xhtml b/SIP/virtual-traits/sip-0000X-1.xhtml new file mode 100644 index 0000000000..e9cda55ae6 --- /dev/null +++ b/SIP/virtual-traits/sip-0000X-1.xhtml @@ -0,0 +1,100 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"> + <head> + <title>Virtual Traits for Scala : Bibtex</title> + <link rel="stylesheet" href="http://lampsvn.epfl.ch/svn-repos/scala/sip/trunk/sip.css" type="text/css"/> + </head> +<body> + +<a name="madsen93:_objec_orien_progr_beta_progr_languag"></a><pre> +@book{<a href="used.html#madsen93:_objec_orien_progr_beta_progr_languag">madsen93:_objec_orien_progr_beta_progr_languag</a>, + author = {Madsen, Ole Lehrmann and Nygaard, Kristen and M\o{}ller-Pedersen, Birger}, + title = {Object-Oriented Programming in The Beta Programming Language}, + publisher = {Addison-Wesley}, + year = 1993 +} +</pre> + +<a name="Mads89a"></a><pre> +@inproceedings{<a href="used.html#Mads89a">Mads89a</a>, + author = {Ole Lehrmann Madsen and Birger M{\o}ller-Pedersen}, + title = {Virtual Classes: {A} Powerful Mechanism + in Object-Oriented Programming}, + booktitle = {Proceedings {OOPSLA}'89, {ACM SIGPLAN Notices}}, + pages = {397--406}, + volume = {24, 10}, + month = oct, + year = {1989} +} +</pre> + +<a name="ernst99b"></a><pre> +@phdthesis{<a href="used.html#ernst99b">ernst99b</a>, + author = {Erik Ernst}, + title = {gbeta -- a Language with Virtual Attributes, Block Structure, and Propagating, Dynamic Inheritance}, + school = {Department of Computer Science, University of Aarhus, \AA{}rhus, Denmark}, + year = {1999} +} +</pre> + +<a name="1111062"></a><pre> +@inproceedings{<a href="used.html#1111062">1111062</a>, + author = {Erik Ernst and Klaus Ostermann and William R. Cook}, + title = {A virtual class calculus}, + booktitle = {POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages}, + year = 2006, + isbn = {1-59593-027-2}, + pages = {270--282}, + location = {Charleston, South Carolina, USA}, + doi = {<a href="http://doi.acm.org/10.1145/1111037.1111062">http://doi.acm.org/10.1145/1111037.1111062</a>}, + publisher = {ACM Press}, + address = {New York, NY, USA} +} +</pre> + +<a name="Erns01a"></a><pre> +@inproceedings{<a href="used.html#Erns01a">Erns01a</a>, + author = {Erik Ernst}, + booktitle = {ECOOP 2001}, + editor = {J. L. Knudsen}, + number = {2072}, + pages = {303--326}, + publisher = {Springer Verlag}, + series = {LNCS}, + title = {Family Polymorphism}, + year = {2001} +} +</pre> + +<a name="EE99"></a><pre> +@inproceedings{<a href="used.html#EE99">EE99</a>, + author = {Erik Ernst}, + title = {Propagating Class and Method Combination}, + pages = {67--91}, + editor = {Rachid Guerraoui}, + booktitle = {Proceedings {ECOOP}'99}, + address = {Lisboa, Portugal}, + month = jun, + year = 1999, + series = {LNCS 1628}, + publisher = {Springer-Verlag}, + isbn = {ISBN 3-540-66156-5} +} +</pre> + +<a name="aracic06:_overv_of_caesarj"></a><pre> +@inproceedings{<a href="used.html#aracic06:_overv_of_caesarj">aracic06:_overv_of_caesarj</a>, + author = {Ivica Aracic and Vaidas Gasiunas and Mira Mezini and Klaus Ostermann}, + title = { An Overview of CaesarJ}, + booktitle = {Transactions on Aspect-Oriented Software Development I}, + pages = {135-173}, + year = 2006, + volume = {3880/2006}, + series = {Lecture Notes in Computer Science}, + publisher = {Springer Berlin / Heidelberg} +} +</pre> + +</body> +</html> diff --git a/SIP/virtual-traits/sip-0000X.xhtml b/SIP/virtual-traits/sip-0000X.xhtml new file mode 100644 index 0000000000..170a1ec436 --- /dev/null +++ b/SIP/virtual-traits/sip-0000X.xhtml @@ -0,0 +1,341 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"> +<head> + <title>Virtual Traits for Scala</title> + <meta name="sip" content="0000X"/> + <meta name="author" content="Anders Bach Nielsen"/> + <meta name="version" content="0"/> + <meta name="type" content="standards"/> + <meta name="status" content="submission"/> + <meta name="created" content="2008-08-21"/> + <meta name="updated" content="2008-11-24"/> + <meta name="scala-version" content="2.8.0.final-"/> + <meta name="owner-contact" content="mailto:andersbach.nielsen@epfl.ch"/> + <!-- <meta name="discussion" content="[URI]"/> --> + <!-- <link rel="auxiliary" href="[URI]" type="[mime type]"/> --> + <!-- <link rel="replaces" href="[URI]" type="application/xhtml+xml"/> --> + <link rel="depends-on" href="PATH-TO-TRAIT-PARAMETERS-SIP" type="application/xhtml+xml"/> + <!-- Stylesheet --> + <link rel="stylesheet" href="http://lampsvn.epfl.ch/svn-repos/scala/sip/trunk/sip.css" type="text/css"/> +</head> +<body> + <a name="top"></a> + <h1>Virtual Traits for Scala</h1> + + <h2>Abstract</h2> + + <p>This document describes the design, integration and implementation + of Virtual Traits (VT) into the Scala language. Virtual traits in + Scala are modeled after the BETA [<a + href="#madsen93:_objec_orien_progr_beta_progr_languag">1</a>] and + gbeta [<a href="#ernst99b">3</a>] notion of virtual classes [<a + href="#Mads89a">2</a>, <a href="#1111062">4</a>]. </p> + + <h2>Contents</h2> + + <ul> + <li><a href="#motivation">Motivation</a> + <ul> + <li><a href="#goals">Goals</a></li> + <li><a href="#usecases">Use cases</a></li> + <li><a href="#usecasedetail">Use cases in detail</a></li> + <li><a href="#futuregoals">Future goals that extend beyond this proposal</a></li> + </ul> + </li> + <li><a href="#languagespec">Language specification changes</a></li> + <li><a href="#implementation">Implementation</a></li> + <li><a href="#references">References</a></li> + </ul> + + + <a name="motivation"></a> + <h2>Motivation</h2> + + <p>The Scala language already has abstract type members that behave + like the types of virtual classes, however this is only for + types. Scala supports both classes and traits, where traits act as + mixins that can be composed together to create classes. The reason + why there are both classes and traits, is to support the + interoperability with Java which has only classes and for this + reason classes are treated specially in the compiler.</p> + + <p>Using abstract type members and a complicated rewriting scheme it + is possible to create virtual classes manually, but there are + several typing issues which will be covered later. We will in this + proposal show the extensions to the Scala language specification to + include virtual traits, the rewriting scheme for translating virtual + trait programs into regular Scala programs and discuss the + implementation of this in the Scala compiler.</p> + + <p>This proposal builds upon the parametrized traits.</p> + + <a name="goals"></a> + <h3>Goals</h3> + + <ul> + <li>Present the additions and changes to the Scala Language + Specification to cover Virtual Traits.</li> + <li>Show in detail the rewriting scheme used in the translation of + Scala programs with virtual traits to programs in Scala + proper.</li> + <li>Present a sample implementation in the Scala compiler.</li> + </ul> + + + <a name="usecases"></a> + <h3>Use cases</h3> + + <ol> + <li><a href="#usecase1">Initial binding of virtual trait</a></li> + <li><a href="#usecase2">Further binding of a virtual trait</a></li> + <li><a href="#usecase3">Final binding of a virtual trait</a></li> + <li><a href="#usecase4">Diamond inheritance involving virtual traits</a></li> + <li><a href="#usecase5">Virtual traits with nested virtual traits</a></li> + </ol> + + <a name="usecasedetail"></a> + <h3>Use cases in detail</h3> + + <a name="usecase1"></a> + <h4>(1) Initial binding of virtual trait</h4> + + <p></p> + + <pre> + <b>trait</b> A <: { ... } + <b>trait</b> B <: A { ... } + <b>trait</b> C <: Foo <b>with</b> B { ... } + </pre> + + <a name="usecase2"></a> + <h4>(2) Further binding of a virtual trait</h4> + + <p></p> + + <pre> + <b>override trait</b> A <: { ... } + <b>override trait</b> B <: { ... } + <b>override trait</b> C <: Bar { ... } + </pre> + + <a name="usecase3"></a> + <h4>(3) Final binding of a virtual trait</h4> + + <p></p> + + <pre> + <b>override trait</b> A + <b>override trait</b> B { ... } + <b>override trait</b> C <b>extends</b> Baz { ... } + </pre> + + <a name="usecase4"></a> + <h4>(4) Diamond inheritance involving virtual traits</h4> + + <p></p> + + <pre> + <b>trait</b> A { + <b>trait</b> V <: { ... } + } + <b>trait</b> B <b>extends</b> A { + <b>override trait</b> V <: { ... } + } + <b>trait</b> C <b>extends</b> A { + <b>override trait</b> V <: { ... } + } + <b>trait</b> D <b>extends</b> B <b>with</b> C { + <b>override trait</b> V <: { ... } + } + </pre> + + <a name="usecase5"></a> + <h4>(5) Virtual traits with nested virtual traits</h4> + + <p></p> + + <pre> + <b>trait</b> A { + <b>trait</b> V <: { + <b>trait</b> W <: { ... } + } + } + <b>trait</b> B <b>extends</b> A { + <b>override trait</b> V <: { + <b>override trait</b> W <: { ... } + } + } + </pre> + + <a name="futuregoals"></a> + <h3>Future goals that extend beyond this proposal</h3> + + <ul> + <li>Having virtual classes, these would have to be converted from + classes to traits and so</li> + </ul> + + <a name="languagespec"></a> + <h2>Language specification changes</h2> + + This section will cover the changes to the Scala language, both the + syntactic and sematic changes that are nessesary to make virtual + traits work under Scala. + + <p> + Normal declaration of a trait in Scala. + </p> + <pre> + trait Foo { ... } + </pre> + + <pre> + TmplDef ::= ['case'] 'class' ClassDef + | ['case'] 'object' ObjectDef + | ['override'] 'trait' TraitDef + +TraitDef ::= id [TypeParamClause] TraitTemplateOpt + +TraitTemplateOpt ::= TraitExtends TraitTemplate + | [['extends'] TemplateBody ] + | '<:' TemplateBody + +TraitExtends ::= 'extends' | '<:' + + +---------- FLAGS ------------- + +TRAIT + DEFERED + ! OVERRIDE => Initial binding +TRAIT + DEFERED + OVERRIDE => Further binding +TRAIT + ! DEFERED + OVERRIDE => Final binding + +classes that extend virtuals are marked with a VIRTUALSUBCLASS + + </pre> + + <h3>Syntactic</h3> + + From the virtual class litterateur there is a distinction between + the initial binding and the further binding of a virtual class. To + have the same expressiveness in Scala this is the way to declare a + initial binding of a virtual trait. + <pre> + trait Bar <: { ... } + </pre> + To be able to tell the difference between a initial and a further + binding of a trait on the syntactical level, further bindings are + written as. + <pre> + override trait Bar <: { ... } + </pre> + + <h3>Semantic</h3> + + + <a name="implementation"></a> + <h2>Implementation</h2> + + + + <a name="references"></a> + <h2>References</h2> + + <table> + <tr valign="top"> + <td align="right"> + [<a name="madsen93:_objec_orien_progr_beta_progr_languag">1</a>] + </td> + <td> + Ole Lehrmann Madsen, Kristen Nygaard, and Birger Møller-Pedersen. + <em>Object-Oriented Programming in The Beta Programming Language</em>. + Addison-Wesley, 1993. + [ <a href="sip-0000X-1.xhtml#madsen93:_objec_orien_progr_beta_progr_languag">bib</a> ] + </td> + </tr> + + <tr valign="top"> + <td align="right"> + [<a name="Mads89a">2</a>] + </td> + <td> + Ole Lehrmann Madsen and Birger Møller-Pedersen. + Virtual classes: A powerful mechanism in object-oriented + programming. + In <em>Proceedings OOPSLA'89, ACM SIGPLAN Notices</em>, volume 24, + 10, pages 397-406, October 1989. + [ <a href="sip-0000X-1.xhtml#Mads89a">bib</a> ] + </td> + </tr> + + <tr valign="top"> + <td align="right"> + [<a name="ernst99b">3</a>] + </td> + <td> + Erik Ernst. + <em>gbeta - a Language with Virtual Attributes, Block Structure, + and Propagating, Dynamic Inheritance</em>. + PhD thesis, Department of Computer Science, University of Aarhus, + Århus, Denmark, 1999. + [ <a href="sip-0000X-1.xhtml#ernst99b">bib</a> ] + </td> + </tr> + + <tr valign="top"> + <td align="right"> + [<a name="1111062">4</a>] + </td> + <td> + Erik Ernst, Klaus Ostermann, and William R. Cook. + A virtual class calculus. + In <em>POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT + symposium on Principles of programming languages</em>, pages 270-282, New York, + NY, USA, 2006. ACM Press. + [ <a href="sip-0000X-1.xhtml#1111062">bib</a> ] + </td> + </tr> + + <tr valign="top"> + <td align="right"> + [<a name="Erns01a">5</a>] + </td> + <td> + Erik Ernst. + Family polymorphism. + In J. L. Knudsen, editor, <em>ECOOP 2001</em>, number 2072 in LNCS, + pages 303-326. Springer Verlag, 2001. + [ <a href="sip-0000X-1.xhtml#Erns01a">bib</a> ] + </td> + </tr> + + <tr valign="top"> + <td align="right"> + [<a name="EE99">6</a>] + </td> + <td> + Erik Ernst. + Propagating class and method combination. + In Rachid Guerraoui, editor, <em>Proceedings ECOOP'99</em>, LNCS 1628, + pages 67-91, Lisboa, Portugal, June 1999. Springer-Verlag. + [ <a href="sip-0000X-1.xhtml#EE99">bib</a> ] + </td> + </tr> + + <tr valign="top"> + <td align="right"> + [<a name="aracic06:_overv_of_caesarj">7</a>] + </td> + <td> + Ivica Aracic, Vaidas Gasiunas, Mira Mezini, and Klaus Ostermann. + An overview of caesarj. + In <em>Transactions on Aspect-Oriented Software Development I</em>, + volume 3880/2006 of <em>Lecture Notes in Computer Science</em>, pages 135-173. + Springer Berlin / Heidelberg, 2006. + [ <a href="sip-0000X-1.xhtml#aracic06:_overv_of_caesarj">bib</a> ] + </td> + </tr> + </table> + +</body> +</html> |
