--- 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);
 }
++/

--- a/trunk/src/dil/semantic/Module.d	Fri Jan 25 20:20:06 2008 +0100
+++ b/trunk/src/dil/semantic/Module.d	Sat Jan 26 20:08:03 2008 +0100
@@ -7,10 +7,8 @@
 import dil.ast.Node;
 import dil.ast.Declarations;
 import dil.parser.Parser;
-import dil.parser.ImportParser;
 import dil.lexer.Lexer;
 import dil.File;
-import dil.semantic.Scope;
 import dil.semantic.Symbol;
 import dil.semantic.Symbols;
 import dil.Information;
@@ -22,42 +20,36 @@
 
 class Module : ScopeSymbol
 {
-  bool isLightweight; /// If true an ImportParser is used instead of a full Parser.
   string filePath; /// Path to the source file.
-  string moduleFQN; /// Fully qualified name of the module.
-  string packageName;
-  string moduleName;
+  string moduleFQN; /// Fully qualified name of the module. E.g. dil.ast.Node
+  string packageName; /// E.g. dil.ast
+  string moduleName; /// E.g. Node
 
-  CompoundDeclaration root; /// The root of the AST.
-  ImportDeclaration[] imports;
-  ModuleDeclaration moduleDecl;
-  private Parser parser;
+  CompoundDeclaration root; /// The root of the parse tree.
+  ImportDeclaration[] imports; /// ImportDeclarations found in this file.
+  ModuleDeclaration moduleDecl; /// The optional ModuleDeclaration in this file.
+  Parser parser; /// The parser used to parse this file.
 
   Module[] modules;
 
   InfoManager infoMan;
 
-  this(string filePath, bool isLightweight = false)
+  this()
   {
     super(SYM.Module, null, null);
-
-    this.filePath = filePath;
-    this.isLightweight = isLightweight;
   }
 
-  this(string filePath, InfoManager infoMan)
+  this(string filePath, InfoManager infoMan = null)
   {
-    this(filePath, false);
+    this();
+    this.filePath = filePath;
     this.infoMan = infoMan;
   }
 
   void parse()
   {
-    auto sourceText = loadFile(filePath);
-    if (this.isLightweight)
-      this.parser = new ImportParser(sourceText, filePath);
-    else
-      this.parser = new Parser(sourceText, filePath, infoMan);
+    if (this.parser is null)
+      this.parser = new Parser(loadFile(filePath), filePath, infoMan);
 
     this.root = parser.start();
 
@@ -91,7 +83,7 @@
     return parser.errors.length || parser.lexer.errors.length;
   }
 
-  string[] getImports()
+  string[] getImportPaths()
   {
     string[] result;
     foreach (import_; imports)
@@ -99,6 +91,8 @@
     return result;
   }
 
+  /// Returns the fully qualified name of this module.
+  /// E.g.: dil.ast.Node
   string getFQN()
   {
     return moduleFQN;
@@ -117,11 +111,14 @@
     this.moduleName = moduleFQN[(i == 0 ? 0 : i+1) .. $];
   }
 
+  /// Returns e.g. the FQN with slashes instead of dots.
+  /// E.g.: dil/ast/Node
   string getFQNPath()
   {
-    if (packageName.length)
-      return packageName ~ dirSep ~ moduleName;
-    else
-      return moduleName;
+    string FQNPath = moduleFQN.dup;
+    foreach (i, c; FQNPath)
+      if (c == '.')
+        FQNPath[i] = dirSep;
+    return FQNPath;
   }
 }