Mercurial > projects > dil
diff trunk/src/cmd/ImportGraph.d @ 698:1564e41f454e
Revised modules cmd.ImportGraph and dil.semantic.Module.
author | Aziz K?ksal <aziz.koeksal@gmail.com> |
---|---|
date | Sat, 26 Jan 2008 20:08:03 +0100 |
parents | 39fac5531b85 |
children | 4c0ea78a7f8b |
line wrap: on
line diff
--- a/trunk/src/cmd/ImportGraph.d Fri Jan 25 20:20:06 2008 +0100 +++ b/trunk/src/cmd/ImportGraph.d Sat Jan 26 20:08:03 2008 +0100 @@ -7,6 +7,7 @@ import dil.ast.Node; import dil.ast.Declarations; import dil.semantic.Module; +import dil.parser.ImportParser; import dil.File; import dil.Settings; import tango.text.Regex : RegExp = Regex; @@ -31,49 +32,171 @@ MarkCyclicModules = 1<<8, } -string findModulePath(string moduleFQN, string[] importPaths) +string findModulePath(string moduleFQNPath, string[] importPaths) { - string modulePath; - foreach (path; importPaths) + auto filePath = new FilePath(); + foreach (importPath; importPaths) { - modulePath = path ~ dirSep ~ moduleFQN ~ ".d"; - // TODO: also check for *.di? - if ((new FilePath(modulePath)).exists()) - return modulePath; + filePath.set(importPath); + filePath.append(moduleFQNPath); + foreach (moduleSuffix; [".d", ".di"/*interface file*/]) + { + filePath.suffix(moduleSuffix); + if (filePath.exists()) + return filePath.toString(); + } } return null; } +class Graph +{ + Vertex[] vertices; + Edge[] edges; + + void addVertex(Vertex vertex) + { + vertex.id = vertices.length; + vertices ~= vertex; + } + + void addEdge(Vertex from, Vertex to) + { + edges ~= new Edge(from, to); + from.outgoing ~= to; + to.incoming ~= from; + } + + /// Walks the graph and marks cyclic vertices and edges. + void detectCycles() + { // Cycles could also be detected in the GraphBuilder, + // but having the code here makes things much clearer. + void visit(Vertex vertex) + { + if (vertex.status == Vertex.Status.Visiting) + { + vertex.isCyclic = true; + return; + } + vertex.status = Vertex.Status.Visiting; + foreach (outVertex; vertex.outgoing) + visit(outVertex); + vertex.status = Vertex.Status.Visited; + } + // Start visiting vertices. + visit(vertices[0]); + + foreach (edge; edges) + if (edge.from.isCyclic && edge.to.isCyclic) + edge.isCyclic = true; + } +} + +/// Represents a directed connection between two vertices. class Edge { - Vertex outgoing; - Vertex incoming; + Vertex from; /// Coming from vertex. + Vertex to; /// Going to vertex. bool isCyclic; - this(Vertex o, Vertex i) + + this(Vertex from, Vertex to) { - this.outgoing = o; - this.incoming = i; + this.from = from; + this.to = to; } } -class Vertex : Module +/// Represents a module in the graph. +class Vertex { - uint id; - Vertex[] incoming; + Module modul; /// The module represented by this vertex. + uint id; /// The nth vertex in the graph. + Vertex[] incoming; /// Also called predecessors. + Vertex[] outgoing; /// Also called successors. bool isCyclic; /// Whether this vertex is in a cyclic relationship with other vertices. - this(string filePath) + enum Status : ubyte + { None, Visiting, Visited } + Status status; /// Used by the cycle detection algorithm. +} + +class GraphBuilder +{ + Graph graph; + IGraphOption options; + string[] importPaths; /// Where to look for modules. + Vertex[string] loadedModulesTable; /// Maps FQN paths to modules. + bool delegate(string) filterPredicate; + + this() { - super(filePath, true); + this.graph = new Graph; + } + + /// Start building the graph and return that. + Graph start(string fileName) + { + loadModule(fileName); + return graph; } - Vertex[] outgoing() + /++ + Loads all modules recursively and builds the graph at the same time. + Params: + moduleFQNPath = e.g.: dil/ast/Node (module FQN = dil.ast.Node) + +/ + Vertex loadModule(string moduleFQNPath) { - return cast(Vertex[])super.modules; + // Filter out modules. + if (filterPredicate(moduleFQNPath)) + return null; + + // Look up in table if the module is already loaded. + auto pVertex = moduleFQNPath in loadedModulesTable; + if (pVertex !is null) + return *pVertex; // Return already loaded module. + + // Locate the module in the file system. + auto moduleFilePath = findModulePath(moduleFQNPath, importPaths); + + Vertex vertex; + + if (moduleFilePath is null) + { // Module not found. + if (options & IGraphOption.IncludeUnlocatableModules) + { // Include module nevertheless. + vertex = new Vertex; + vertex.modul = new Module(""); + vertex.modul.setFQN(replace(moduleFQNPath, dirSep, '.')); + graph.addVertex(vertex); + loadedModulesTable[moduleFQNPath] = vertex; + } + } + else + { + auto modul = new Module(moduleFilePath); + // Use lightweight ImportParser. + modul.parser = new ImportParser(loadFile(moduleFilePath), moduleFilePath); + modul.parse(); + + vertex = new Vertex; + vertex.modul = modul; + + graph.addVertex(vertex); + loadedModulesTable[modul.getFQNPath()] = vertex; + // Load modules which this module depends on. + foreach (moduleFQNPath_; modul.getImportPaths()) + { + auto loaded = loadModule(moduleFQNPath_); + if (loaded !is null) + graph.addEdge(vertex, loaded); + } + } + return vertex; } } -void execute(string filePath, string[] importPaths, string[] strRegexps, uint levels, IGraphOption options) +void execute(string filePathString, string[] importPaths, string[] strRegexps, uint levels, IGraphOption options) { // Init regular expressions. RegExp[] regexps; @@ -81,169 +204,100 @@ regexps ~= new RegExp(strRegexp); // Add directory of file and global directories to import paths. - auto fileDir = (new FilePath(filePath)).folder(); + auto filePath = new FilePath(filePathString); + auto fileDir = filePath.folder(); if (fileDir.length) importPaths ~= fileDir; importPaths ~= GlobalSettings.importPaths; - Vertex[string] loadedModules; - Vertex[] loadedModulesList; // Ordered list of loaded modules. - Edge edges[]; - Vertex loadModule(string moduleFQNPath) - { - auto mod_ = moduleFQNPath in loadedModules; - if (mod_ !is null) - return *mod_; // Return already loaded module. - - // Ignore module names matching regular expressions. - foreach (rx; regexps) - if (rx.test(replace(moduleFQNPath, dirSep, '.'))) - return null; - - auto modulePath = findModulePath(moduleFQNPath, importPaths); - Vertex mod; - if (modulePath is null) - { - if (options & IGraphOption.IncludeUnlocatableModules) - { - mod = new Vertex(null); - mod.setFQN(replace(moduleFQNPath, dirSep, '.')); - loadedModules[moduleFQNPath] = mod; - loadedModulesList ~= mod; - mod.id = loadedModulesList.length -1; - } - } - else - { -// writefln(modulePath); - mod = new Vertex(modulePath); - mod.parse(); - - loadedModules[moduleFQNPath] = mod; - loadedModulesList ~= mod; - mod.id = loadedModulesList.length -1; - - auto moduleFQNs = mod.getImports(); + auto gbuilder = new GraphBuilder; - foreach (moduleFQN_; moduleFQNs) - { - auto loaded_mod = loadModule(moduleFQN_); - if (loaded_mod !is null) - { - edges ~= new Edge(mod, loaded_mod); - mod.modules ~= loaded_mod; - loaded_mod.incoming ~= mod; - } - } - } - return mod; - } - - auto mod = new Vertex(filePath); - mod.parse(); - - auto moduleFQNs = mod.getImports(); + gbuilder.importPaths = importPaths; + gbuilder.options = options; + gbuilder.filterPredicate = (string moduleFQNPath) { + foreach (rx; regexps) + // Replace slashes: dil/ast/Node -> dil.ast.Node + if (rx.test(replace(moduleFQNPath, dirSep, '.'))) + return true; + return false; + }; - loadedModules[mod.getFQNPath()] = mod; - loadedModulesList ~= mod; - mod.id = 0; // loadedModulesList.length -1 - - foreach (moduleFQN_; moduleFQNs) - { - auto loaded_mod = loadModule(moduleFQN_); - if (loaded_mod !is null) - { - edges ~= new Edge(mod, loaded_mod); - mod.modules ~= loaded_mod; - loaded_mod.incoming ~= mod; - } - } - // Finished loading modules. - - // Check that every module has at least one incoming or outgoing edge. - assert( - delegate { - foreach (mod; loadedModulesList) - if (mod.incoming.length == 0 && mod.outgoing.length == 0) - throw new Exception("module "~mod.getFQN()~" has no edges in the graph."); - return true; - }() == true - ); + auto graph = gbuilder.start(filePath.name()); if (options & (IGraphOption.PrintList | IGraphOption.PrintPaths)) { if (options & IGraphOption.MarkCyclicModules) - analyzeGraph(loadedModulesList, edges.dup); + graph.detectCycles(); if (options & IGraphOption.PrintPaths) - printPaths(loadedModulesList, levels+1, ""); + printModulePaths(graph.vertices, levels+1, ""); else - printList(loadedModulesList, levels+1, ""); + printModuleList(graph.vertices, levels+1, ""); } - else - printDot(loadedModulesList, edges, options); + else + printDotDocument(graph, options); } -void printPaths(Vertex[] vertices, uint level, char[] indent) +void printModulePaths(Vertex[] vertices, uint level, char[] indent) { - if (!level) + if (level == 0) return; foreach (vertex; vertices) { - Stdout(indent)((vertex.isCyclic?"*":"")~vertex.filePath).newline; + Stdout(indent)((vertex.isCyclic?"*":"")~vertex.modul.filePath).newline; if (vertex.outgoing.length) - printPaths(vertex.outgoing, level-1, indent~" "); + printModulePaths(vertex.outgoing, level-1, indent~" "); } } -void printList(Vertex[] vertices, uint level, char[] indent) +void printModuleList(Vertex[] vertices, uint level, char[] indent) { - if (!level) + if (level == 0) return; foreach (vertex; vertices) { - Stdout(indent)((vertex.isCyclic?"*":"")~vertex.getFQN()).newline; + Stdout(indent)((vertex.isCyclic?"*":"")~vertex.modul.getFQN()).newline; if (vertex.outgoing.length) - printList(vertex.outgoing, level-1, indent~" "); + printModuleList(vertex.outgoing, level-1, indent~" "); } } -void printDot(Vertex[] loadedModulesList, Edge[] edges, IGraphOption options) +void printDotDocument(Graph graph, IGraphOption options) { Vertex[][string] verticesByPckgName; if (options & IGraphOption.GroupByFullPackageName) - foreach (module_; loadedModulesList) - verticesByPckgName[module_.packageName] ~= module_; + foreach (vertex; graph.vertices) + verticesByPckgName[vertex.modul.packageName] ~= vertex; if (options & (IGraphOption.HighlightCyclicVertices | IGraphOption.HighlightCyclicEdges)) - analyzeGraph(loadedModulesList, edges.dup); - - Stdout("Digraph ModuleDependencies\n{\n"); + graph.detectCycles(); - if (options & IGraphOption.HighlightCyclicVertices) - foreach (i, module_; loadedModulesList) - Stdout.format(` n{0} [label="{1}"{2}];`, i, module_.getFQN(), (module_.isCyclic ? ",style=filled,fillcolor=tomato" : "")).newline; - else - foreach (i, module_; loadedModulesList) - Stdout.format(` n{0} [label="{1}"];`, i, module_.getFQN()).newline; - - foreach (edge; edges) - Stdout.format(` n{0} -> n{1}{2};`, edge.outgoing.id, edge.incoming.id, (edge.isCyclic ? "[color=red]" : "")).newline; + // Output header of the dot document. + Stdout("Digraph ImportGraph\n{\n"); + // Output nodes. + // 'i' and vertex.id should be the same. + foreach (i, vertex; graph.vertices) + Stdout.formatln(` n{} [label="{}"{}];`, i, vertex.modul.getFQN(), (vertex.isCyclic ? ",style=filled,fillcolor=tomato" : "")); + // Output edges. + foreach (edge; graph.edges) + Stdout.formatln(` n{} -> n{}{};`, edge.from.id, edge.to.id, (edge.isCyclic ? "[color=red]" : "")); if (options & IGraphOption.GroupByFullPackageName) foreach (packageName, vertices; verticesByPckgName) - { - Stdout.format(` subgraph "cluster_{0}" {`\n` label="{1}";color=blue;`"\n ", packageName, packageName); - foreach (module_; vertices) - Stdout.format(`n{0};`, module_.id); + { // Output nodes in a cluster. + Stdout.format(` subgraph "cluster_{}" {`\n` label="{}";color=blue;`"\n ", packageName, packageName); + foreach (vertex; vertices) + Stdout.format(`n{};`, vertex.id); Stdout("\n }\n"); } Stdout("}\n"); } +/+ +// This is the old algorithm that was used to detect cycles in a directed graph. void analyzeGraph(Vertex[] vertices_init, Edge[] edges) { void recursive(Vertex[] vertices) @@ -253,9 +307,9 @@ uint outgoing, incoming; foreach (j, edge; edges) { - if (edge.outgoing is vertex) + if (edge.from is vertex) outgoing++; - if (edge.incoming is vertex) + if (edge.to is vertex) incoming++; } @@ -268,7 +322,7 @@ alias incoming j; // Reuse // Remove edges. for (i=j=0; i < edges.length; i++) - if (edges[i].incoming !is vertex) + if (edges[i].to !is vertex) edges[j++] = edges[i]; edges.length = j; vertices = vertices[0..idx] ~ vertices[idx+1..$]; @@ -291,7 +345,7 @@ alias incoming j; // Reuse // Remove edges. for (i=j=0; i < edges.length; i++) - if (edges[i].outgoing !is vertex) + if (edges[i].from !is vertex) edges[j++] = edges[i]; edges.length = j; vertices = vertices[0..idx] ~ vertices[idx+1..$]; @@ -314,3 +368,4 @@ } recursive(vertices_init); } ++/