Mercurial > projects > dil

comparison trunk/src/cmd/ImportGraph.d @ 702:e10838e0b182

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixed filter delegate in cmd.ImportGraph. Added members isPublic and isStatic to class Edge.
author Aziz K?ksal <aziz.koeksal@gmail.com>
date Sun, 27 Jan 2008 18:21:42 +0100
parents 4c0ea78a7f8b
children bf10602159c1
comparison
equal deleted inserted replaced
701:65ad2f96df1f 702:e10838e0b182
58 { 58 {
59 vertex.id = vertices.length; 59 vertex.id = vertices.length;
60 vertices ~= vertex; 60 vertices ~= vertex;
61 } 61 }
62 62
63 void addEdge(Vertex from, Vertex to) 63 Edge addEdge(Vertex from, Vertex to)
64 { 64 {
65 edges ~= new Edge(from, to); 65 auto edge = new Edge(from, to);
66 edges ~= edge;
66 from.outgoing ~= to; 67 from.outgoing ~= to;
67 to.incoming ~= from; 68 to.incoming ~= from;
69 return edge;
68 } 70 }
69 71
70 /// Walks the graph and marks cyclic vertices and edges. 72 /// Walks the graph and marks cyclic vertices and edges.
71 void detectCycles() 73 void detectCycles()
72 { // Cycles could also be detected in the GraphBuilder, 74 { // Cycles could also be detected in the GraphBuilder,
73 // but having the code here makes things much clearer. 75 // but having the code here makes things much clearer.
76
77 // Returns true if the vertex is in status Visiting.
74 bool visit(Vertex vertex) 78 bool visit(Vertex vertex)
75 { 79 {
76 if (vertex.status == Vertex.Status.Visiting) 80 switch (vertex.status)
77 { 81 {
82 case Vertex.Status.Visiting:
78 vertex.isCyclic = true; 83 vertex.isCyclic = true;
79 return true; 84 return true;
80 } 85 case Vertex.Status.None:
81 if (vertex.status == Vertex.Status.Visited) 86 vertex.status = Vertex.Status.Visiting; // Flag as visiting.
82 return false; 87 foreach (outVertex; vertex.outgoing) // Visit successors.
83 // Flag as visiting. 88 vertex.isCyclic |= visit(outVertex);
84 vertex.status = Vertex.Status.Visiting; 89 vertex.status = Vertex.Status.Visited; // Flag as visited.
85 // Visit successors. 90 break;
86 foreach (outVertex; vertex.outgoing) 91 case Vertex.Status.Visited:
87 vertex.isCyclic |= visit(outVertex); 92 break;
88 // Flag as visited. 93 default:
89 vertex.status = Vertex.Status.Visited; 94 assert(0, "unknown vertex status");
90 return false; 95 }
96 return false; // return (vertex.status == Vertex.Status.Visiting);
91 } 97 }
92 // Start visiting vertices. 98 // Start visiting vertices.
93 visit(vertices[0]); 99 visit(vertices[0]);
94 100
95 foreach (edge; edges) 101 foreach (edge; edges)
99 } 105 }
100 106
101 /// Represents a directed connection between two vertices. 107 /// Represents a directed connection between two vertices.
102 class Edge 108 class Edge
103 { 109 {
104 Vertex from; /// Coming from vertex. 110 Vertex from; /// Coming from vertex.
105 Vertex to; /// Going to vertex. 111 Vertex to; /// Going to vertex.
106 bool isCyclic; 112 bool isCyclic; /// Edge connects cyclic vertices.
113 bool isPublic; /// Public import.
114 bool isStatic; /// Static import.
107 115
108 this(Vertex from, Vertex to) 116 this(Vertex from, Vertex to)
109 { 117 {
110 this.from = from; 118 this.from = from;
111 this.to = to; 119 this.to = to;
113 } 121 }
114 122
115 /// Represents a module in the graph. 123 /// Represents a module in the graph.
116 class Vertex 124 class Vertex
117 { 125 {
118 Module modul; /// The module represented by this vertex. 126 Module modul; /// The module represented by this vertex.
119 uint id; /// The nth vertex in the graph. 127 uint id; /// The nth vertex in the graph.
120 Vertex[] incoming; /// Also called predecessors. 128 Vertex[] incoming; /// Also called predecessors.
121 Vertex[] outgoing; /// Also called successors. 129 Vertex[] outgoing; /// Also called successors.
122 bool isCyclic; /// Whether this vertex is in a cyclic relationship with other vertices. 130 bool isCyclic; /// Whether this vertex is in a cyclic relationship with other vertices.
123 131
124 enum Status : ubyte 132 enum Status : ubyte
125 { None, Visiting, Visited } 133 { None, Visiting, Visited }
126 Status status; /// Used by the cycle detection algorithm. 134 Status status; /// Used by the cycle detection algorithm.
127 } 135 }
151 Params: 159 Params:
152 moduleFQNPath = e.g.: dil/ast/Node (module FQN = dil.ast.Node) 160 moduleFQNPath = e.g.: dil/ast/Node (module FQN = dil.ast.Node)
153 +/ 161 +/
154 Vertex loadModule(string moduleFQNPath) 162 Vertex loadModule(string moduleFQNPath)
155 { 163 {
156 // Filter out modules.
157 if (filterPredicate(moduleFQNPath))
158 return null;
159
160 // Look up in table if the module is already loaded. 164 // Look up in table if the module is already loaded.
161 auto pVertex = moduleFQNPath in loadedModulesTable; 165 auto pVertex = moduleFQNPath in loadedModulesTable;
162 if (pVertex !is null) 166 if (pVertex !is null)
163 return *pVertex; // Return already loaded module. 167 return *pVertex; // Returns null for filtered or unlocatable modules.
168
169 // Filter out modules.
170 if (filterPredicate && filterPredicate(moduleFQNPath))
171 { // Store null for filtered modules.
172 loadedModulesTable[moduleFQNPath] = null;
173 return null;
174 }
164 175
165 // Locate the module in the file system. 176 // Locate the module in the file system.
166 auto moduleFilePath = findModulePath(moduleFQNPath, importPaths); 177 auto moduleFilePath = findModulePath(moduleFQNPath, importPaths);
167 178
168 Vertex vertex; 179 Vertex vertex;
173 { // Include module nevertheless. 184 { // Include module nevertheless.
174 vertex = new Vertex; 185 vertex = new Vertex;
175 vertex.modul = new Module(""); 186 vertex.modul = new Module("");
176 vertex.modul.setFQN(replace(moduleFQNPath, dirSep, '.')); 187 vertex.modul.setFQN(replace(moduleFQNPath, dirSep, '.'));
177 graph.addVertex(vertex); 188 graph.addVertex(vertex);
178 loadedModulesTable[moduleFQNPath] = vertex; 189 }
179 } 190 // Store vertex in the table (vertex may be null.)
191 loadedModulesTable[moduleFQNPath] = vertex;
180 } 192 }
181 else 193 else
182 { 194 {
183 auto modul = new Module(moduleFilePath); 195 auto modul = new Module(moduleFilePath);
184 // Use lightweight ImportParser. 196 // Use lightweight ImportParser.
188 vertex = new Vertex; 200 vertex = new Vertex;
189 vertex.modul = modul; 201 vertex.modul = modul;
190 202
191 graph.addVertex(vertex); 203 graph.addVertex(vertex);
192 loadedModulesTable[modul.getFQNPath()] = vertex; 204 loadedModulesTable[modul.getFQNPath()] = vertex;
193 // Load modules which this module depends on. 205
194 foreach (moduleFQNPath_; modul.getImportPaths()) 206 // Load the modules which this module depends on.
195 { 207 foreach (importDecl; modul.imports)
196 auto loaded = loadModule(moduleFQNPath_); 208 {
197 if (loaded !is null) 209 foreach (moduleFQNPath2; importDecl.getModuleFQNs(dirSep))
198 graph.addEdge(vertex, loaded); 210 {
211 auto loaded = loadModule(moduleFQNPath2);
212 if (loaded !is null)
213 {
214 auto edge = graph.addEdge(vertex, loaded);
215 edge.isPublic = importDecl.isPublic();
216 edge.isStatic = importDecl.isStatic();
217 }
218 }
199 } 219 }
200 } 220 }
201 return vertex; 221 return vertex;
202 } 222 }
203 } 223 }
222 gbuilder.importPaths = importPaths; 242 gbuilder.importPaths = importPaths;
223 gbuilder.options = options; 243 gbuilder.options = options;
224 gbuilder.filterPredicate = (string moduleFQNPath) { 244 gbuilder.filterPredicate = (string moduleFQNPath) {
225 foreach (rx; regexps) 245 foreach (rx; regexps)
226 // Replace slashes: dil/ast/Node -> dil.ast.Node 246 // Replace slashes: dil/ast/Node -> dil.ast.Node
227 if (rx.test(replace(moduleFQNPath, dirSep, '.'))) 247 if (rx.test(replace(moduleFQNPath.dup, dirSep, '.')))
228 return true; 248 return true;
229 return false; 249 return false;
230 }; 250 };
231 251
232 auto graph = gbuilder.start(filePath.name()); 252 auto graph = gbuilder.start(filePath.name());