Add library tree traversal capabilities to ModuleDef. Change-Id: I9b33e6bf691c0f58a01abb9a9a0384867d7dbe85

diff --git a/dev/core/src/com/google/gwt/dev/cfg/ModuleDef.java b/dev/core/src/com/google/gwt/dev/cfg/ModuleDef.java
index af2feb6..264abe0 100644
--- a/dev/core/src/com/google/gwt/dev/cfg/ModuleDef.java
+++ b/dev/core/src/com/google/gwt/dev/cfg/ModuleDef.java

@@ -39,9 +39,12 @@
 import com.google.gwt.dev.util.log.speedtracer.SpeedTracerLogger.Event;
 import com.google.gwt.thirdparty.guava.common.base.Preconditions;
 import com.google.gwt.thirdparty.guava.common.base.Predicates;
+import com.google.gwt.thirdparty.guava.common.collect.HashMultimap;
 import com.google.gwt.thirdparty.guava.common.collect.ImmutableList;
 import com.google.gwt.thirdparty.guava.common.collect.Iterators;
 import com.google.gwt.thirdparty.guava.common.collect.Lists;
+import com.google.gwt.thirdparty.guava.common.collect.Multimap;
+import com.google.gwt.thirdparty.guava.common.collect.Queues;
 import com.google.gwt.thirdparty.guava.common.collect.Sets;
 
 import java.io.File;
@@ -59,6 +62,7 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Map.Entry;
+import java.util.Queue;
 import java.util.Set;
 
 /**
@@ -66,7 +70,6 @@
  * XML for unit tests.
  */
 public class ModuleDef {
-
   /**
    * Marks a module in a way that can be used to calculate the effective bounds of a library module
    * in a module tree.
@@ -204,6 +207,17 @@
    */
   private String nameOverride;
 
+
+  /**
+   * The canonical module names of dependency library modules per depending library module.
+   */
+  private Multimap<String, String> directDependentsModuleNamesByModuleName = HashMultimap.create();
+
+  /**
+   * Records the canonical module names for filesets.
+   */
+  private Set<String> filesetModuleNames = Sets.newHashSet();
+
   private final Properties properties = new Properties();
 
   private PathPrefixSet publicPrefixSet = new PathPrefixSet();
@@ -248,6 +262,20 @@
     defaultFilters = new DefaultFilters();
   }
 
+  /**
+   * Register a {@code dependentModuleName} as a directDependent of {@code currentModuleName}
+   */
+  public void addDirectDependent(String currentModuleName, String dependentModuleName) {
+    directDependentsModuleNamesByModuleName.put(currentModuleName, dependentModuleName);
+  }
+
+  /**
+   * Registers a module as a fileset.
+   */
+  public void addFileset(String filesetModuleName) {
+    filesetModuleNames.add(filesetModuleName);
+  }
+
   public synchronized void addEntryPointTypeName(String typeName) {
     if (!attributeIsForTargetLibrary()) {
       return;
@@ -386,6 +414,9 @@
    * modules ModuleType to updates its idea of attribute source.
    */
   public void enterModule(ModuleType moduleType, String canonicalModuleName) {
+    if (moduleType == ModuleType.FILESET) {
+      addFileset(canonicalModuleName);
+    }
     if (monolithic) {
       // When you're monolithic the module tree is all effectively one giant library.
       currentAttributeSource.push(AttributeSource.TARGET_LIBRARY);
@@ -544,6 +575,14 @@
     return compilationState;
   }
 
+  /**
+   * The module names for its direct non fileset dependents.
+   */
+  public Collection<String> getDirectDependencies(String libraryModuleName) {
+    assert !filesetModuleNames.contains(libraryModuleName);
+    return directDependentsModuleNamesByModuleName.get(libraryModuleName);
+  }
+
   public synchronized String[] getEntryPointTypeNames() {
     final int n = entryPointTypeNames.size();
     return entryPointTypeNames.toArray(new String[n]);
@@ -747,6 +786,10 @@
   synchronized void normalize(TreeLogger logger) {
     Event moduleDefNormalize =
         SpeedTracerLogger.start(CompilerEventType.MODULE_DEF, "phase", "normalize");
+
+    // Compute compact dependency graph;
+    computeLibraryDependencyGraph();
+
     // Normalize property providers.
     //
     for (Property current : getProperties()) {
@@ -835,6 +878,47 @@
     }
   }
 
+  /**
+   * Reduce the direct dependency graph to exclude filesets.
+   */
+  private void computeLibraryDependencyGraph() {
+    for (String moduleName : Lists.newArrayList(directDependentsModuleNamesByModuleName.keySet())) {
+      Set<String> libraryModules = Sets.newHashSet();
+      Set<String> filesetsProcessed = Sets.newHashSet();
+
+      // Direct dependents might be libraries or fileset, so add them to a queue of modules
+      // to process.
+      Queue<String> modulesToProcess =
+          Queues.newArrayDeque(directDependentsModuleNamesByModuleName.get(moduleName));
+      while (!modulesToProcess.isEmpty()) {
+        String dependentModuleName = modulesToProcess.poll();
+
+        boolean isLibrary = !filesetModuleNames.contains(dependentModuleName);
+        if (isLibrary) {
+          // Current dependent is not a fileset so it will be in the list of dependents unless it is
+          // the library itself.
+          if (!moduleName.equals(dependentModuleName)) {
+            libraryModules.add(dependentModuleName);
+          }
+          continue;
+        }
+        // Mark the module as processed to avoid an infinite loop.
+        filesetsProcessed.add(dependentModuleName);
+
+        // Get the dependencies of the dependent module under consideration and add all those
+        // that have not been already processed to the queue of modules to process.
+        Set<String> notAlreadyProcessed =
+            Sets.newHashSet(directDependentsModuleNamesByModuleName.get(dependentModuleName));
+        notAlreadyProcessed.removeAll(filesetsProcessed);
+        modulesToProcess.addAll(notAlreadyProcessed);
+      }
+      // Rewrite the dependents with the set just computed.
+      directDependentsModuleNamesByModuleName.replaceValues(moduleName, libraryModules);
+    }
+    // Remove all fileset entries.
+    directDependentsModuleNamesByModuleName.removeAll(filesetModuleNames);
+  }
+
   private synchronized void ensureResourcesScanned() {
     if (resourcesScanned) {
       return;

diff --git a/dev/core/src/com/google/gwt/dev/cfg/ModuleDefSchema.java b/dev/core/src/com/google/gwt/dev/cfg/ModuleDefSchema.java
index 1b6ba0d..cb36293 100644
--- a/dev/core/src/com/google/gwt/dev/cfg/ModuleDefSchema.java
+++ b/dev/core/src/com/google/gwt/dev/cfg/ModuleDefSchema.java

@@ -500,6 +500,7 @@
     @SuppressWarnings("unused") // called reflectively
     protected Schema __inherits_begin(String name)
         throws UnableToCompleteException {
+      moduleDef.addDirectDependent(moduleName, name);
       loader.nestedLoad(logger, name, moduleDef);
       return null;
     }
@@ -1445,7 +1446,8 @@
 
   @SuppressWarnings("unused")
   protected Schema __module_begin(NullableName renameTo, String type) {
-    moduleDef.enterModule(ModuleType.valueOf(type.toUpperCase(Locale.ENGLISH)), moduleName);
+    ModuleType moduleType = ModuleType.valueOf(type.toUpperCase(Locale.ENGLISH));
+    moduleDef.enterModule(moduleType, moduleName);
     return bodySchema;
   }
 

diff --git a/dev/core/test/com/google/gwt/dev/cfg/ModuleDefLoaderTest.java b/dev/core/test/com/google/gwt/dev/cfg/ModuleDefLoaderTest.java
index 3d1083d..ea9712b 100644
--- a/dev/core/test/com/google/gwt/dev/cfg/ModuleDefLoaderTest.java
+++ b/dev/core/test/com/google/gwt/dev/cfg/ModuleDefLoaderTest.java

@@ -22,6 +22,7 @@
 import com.google.gwt.dev.javac.testing.impl.MockResource;
 import com.google.gwt.dev.resource.Resource;
 import com.google.gwt.dev.util.UnitTestTreeLogger;
+import com.google.gwt.thirdparty.guava.common.collect.ImmutableSet;
 import com.google.gwt.thirdparty.guava.common.collect.Lists;
 import com.google.gwt.thirdparty.guava.common.collect.Sets;
 
@@ -99,6 +100,24 @@
   }
 
   /**
+   * Tests that the tree representation for a module is correct.
+   */
+  public void testLibraryTree() throws Exception {
+    TreeLogger logger = TreeLogger.NULL;
+    ModuleDef six = ModuleDefLoader.loadFromClassPath(
+        logger, compilerContext, "com.google.gwt.dev.cfg.testdata.dependents.Six");
+
+    assertTrue(six.getDirectDependencies("com.google.gwt.dev.cfg.testdata.dependents.Six")
+        .equals(ImmutableSet.of("com.google.gwt.dev.cfg.testdata.dependents.Five")));
+    assertTrue("Contains " + six.getDirectDependencies(
+        "com.google.gwt.dev.cfg.testdata.dependents.Five"),
+        six.getDirectDependencies("com.google.gwt.dev.cfg.testdata.dependents.Five")
+        .equals(ImmutableSet.of("com.google.gwt.dev.cfg.testdata.dependents.One",
+            "com.google.gwt.dev.cfg.testdata.dependents.Two",
+            "com.google.gwt.dev.cfg.testdata.dependents.Four")));
+  }
+
+  /**
    * Test of merging multiple modules in the same package space.
    * This exercises the interaction of include, exclude, and skip attributes.
    */

diff --git a/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/FileSet.gwt.xml b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/FileSet.gwt.xml
new file mode 100644
index 0000000..a73cd3c
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/FileSet.gwt.xml

@@ -0,0 +1,3 @@
+<module type="fileset" rename-to="B">
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.Two"/>
+</module>

diff --git a/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Five.gwt.xml b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Five.gwt.xml
new file mode 100644
index 0000000..be5513f
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Five.gwt.xml

@@ -0,0 +1,5 @@
+<module rename-to="A">
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.FileSet"/>
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.One"/>
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.Four"/>
+</module>

diff --git a/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Four.gwt.xml b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Four.gwt.xml
new file mode 100644
index 0000000..a852bfc
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Four.gwt.xml

@@ -0,0 +1,3 @@
+<module rename-to="C">
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.FileSet"/>
+</module>

diff --git a/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/One.gwt.xml b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/One.gwt.xml
new file mode 100644
index 0000000..ea43b34
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/One.gwt.xml

@@ -0,0 +1,2 @@
+<module rename-to="D">
+</module>

diff --git a/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Six.gwt.xml b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Six.gwt.xml
new file mode 100644
index 0000000..a01bc97
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Six.gwt.xml

@@ -0,0 +1,3 @@
+<module rename-to="E">
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.Five"/>
+</module>

diff --git a/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Three.gwt.xml b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Three.gwt.xml
new file mode 100644
index 0000000..b374133
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Three.gwt.xml

@@ -0,0 +1,3 @@
+<module rename-to="F">
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.One"/>
+</module>

diff --git a/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Two.gwt.xml b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Two.gwt.xml
new file mode 100644
index 0000000..98b235c
--- /dev/null
+++ b/dev/core/test/com/google/gwt/dev/cfg/testdata/dependents/Two.gwt.xml

@@ -0,0 +1,3 @@
+<module rename-to="G">
+  <inherits name="com.google.gwt.dev.cfg.testdata.dependents.One"/>
+</module>