originalDeps map added to Module

- `originalDeps` map added to `Module` to keep track of the original dependencies when doing **external dependency graph inspection**, without having to call `SkyFrame` for the `ModuleFileValues`

- `ModuleBuilder` added to simplify creating `Module` object for `UnitTests`

https://github.com/bazelbuild/bazel/issues/15365

PiperOrigin-RevId: 448026884
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Module.java b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Module.java
index 13ae614..5bc8980 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Module.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Module.java
@@ -87,12 +87,21 @@
   public abstract ImmutableList<String> getToolchainsToRegister();
 
   /**
-   * The direct dependencies of this module. The key type is the repo name of the dep, and the value
-   * type is the ModuleKey (name+version) of the dep.
+   * The resolved direct dependencies of this module, which can be either the original ones,
+   * overridden by a {@code single_version_override}, by a {@code multiple_version_override}, or by
+   * a {@link NonRegistryOverride} (the version will be ""). The key type is the repo name of the
+   * dep, and the value type is the ModuleKey (name+version) of the dep.
    */
   public abstract ImmutableMap<String, ModuleKey> getDeps();
 
   /**
+   * The original direct dependencies of this module as they are declared in their MODULE file. The
+   * key type is the repo name of the dep, and the value type is the ModuleKey (name+version) of the
+   * dep.
+   */
+  public abstract ImmutableMap<String, ModuleKey> getOriginalDeps();
+
+  /**
    * Returns a {@link RepositoryMapping} with only Bazel module repos and no repos from module
    * extensions. For the full mapping, see {@link BazelModuleResolutionValue#getFullRepoMapping}.
    */
@@ -174,6 +183,8 @@
     /** Optional; defaults to an empty list. */
     public abstract Builder setToolchainsToRegister(ImmutableList<String> value);
 
+    public abstract Builder setOriginalDeps(ImmutableMap<String, ModuleKey> value);
+
     public abstract Builder setDeps(ImmutableMap<String, ModuleKey> value);
 
     abstract ImmutableMap.Builder<String, ModuleKey> depsBuilder();
@@ -183,6 +194,13 @@
       return this;
     }
 
+    abstract ImmutableMap.Builder<String, ModuleKey> originalDepsBuilder();
+
+    public Builder addOriginalDep(String depRepoName, ModuleKey depKey) {
+      originalDepsBuilder().put(depRepoName, depKey);
+      return this;
+    }
+
     public abstract Builder setRegistry(Registry value);
 
     public abstract Builder setExtensionUsages(ImmutableList<ModuleExtensionUsage> value);
@@ -194,6 +212,6 @@
       return this;
     }
 
-    public abstract Module build();
+    abstract Module build();
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileGlobals.java b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileGlobals.java
index 9b90671..9447925 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileGlobals.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileGlobals.java
@@ -716,6 +716,7 @@
   public Module buildModule() {
     return module
         .setDeps(ImmutableMap.copyOf(deps))
+        .setOriginalDeps(ImmutableMap.copyOf(deps))
         .setExtensionUsages(
             extensionProxies.stream()
                 .map(ModuleExtensionProxy::buildUsage)
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BUILD b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BUILD
index 4a9f224..5dfb4d3 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BUILD
@@ -100,6 +100,7 @@
         "//src/main/java/com/google/devtools/build/lib/bazel/bzlmod:common",
         "//src/main/java/com/google/devtools/build/lib/bazel/bzlmod:module_extension",
         "//src/main/java/com/google/devtools/build/lib/bazel/bzlmod:registry",
+        "//src/main/java/com/google/devtools/build/lib/bazel/bzlmod:resolution",
         "//src/main/java/com/google/devtools/build/lib/cmdline:cmdline-primitives",
         "//src/main/java/com/google/devtools/build/lib/events",
         "//src/main/java/com/google/devtools/build/lib/packages",
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodTestUtil.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodTestUtil.java
index 993ee90..31c9920 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodTestUtil.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodTestUtil.java
@@ -17,9 +17,13 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.bazel.bzlmod.Version.ParseException;
 import com.google.devtools.build.lib.cmdline.RepositoryMapping;
 import com.google.devtools.build.lib.cmdline.RepositoryName;
 import com.google.devtools.build.lib.packages.Attribute;
+import java.util.AbstractMap.SimpleEntry;
+import java.util.Map;
+import java.util.Map.Entry;
 import net.starlark.java.eval.Dict;
 import net.starlark.java.syntax.Location;
 
@@ -36,6 +40,98 @@
     }
   }
 
+  /** Builder class to create a {@code Entry<ModuleKey, Module>} entry faster inside UnitTests */
+  static final class ModuleBuilder {
+    Module.Builder builder;
+    ModuleKey key;
+    ImmutableMap.Builder<String, ModuleKey> deps = new ImmutableMap.Builder<>();
+    ImmutableMap.Builder<String, ModuleKey> originalDeps = new ImmutableMap.Builder<>();
+
+    private ModuleBuilder() {}
+
+    public static ModuleBuilder create(String name, Version version, int compatibilityLevel) {
+      ModuleBuilder moduleBuilder = new ModuleBuilder();
+      ModuleKey key = ModuleKey.create(name, version);
+      moduleBuilder.key = key;
+      moduleBuilder.builder =
+          Module.builder()
+              .setName(name)
+              .setVersion(version)
+              .setKey(key)
+              .setCompatibilityLevel(compatibilityLevel);
+      return moduleBuilder;
+    }
+
+    public static ModuleBuilder create(String name, String version, int compatibilityLevel)
+        throws ParseException {
+      return create(name, Version.parse(version), compatibilityLevel);
+    }
+
+    public static ModuleBuilder create(String name, String version) throws ParseException {
+      return create(name, Version.parse(version), 0);
+    }
+
+    public static ModuleBuilder create(String name, Version version) throws ParseException {
+      return create(name, version, 0);
+    }
+
+    public ModuleBuilder addDep(String depRepoName, ModuleKey key) {
+      deps.put(depRepoName, key);
+      return this;
+    }
+
+    public ModuleBuilder addOriginalDep(String depRepoName, ModuleKey key) {
+      originalDeps.put(depRepoName, key);
+      return this;
+    }
+
+    public ModuleBuilder setKey(ModuleKey value) {
+      this.key = value;
+      this.builder.setKey(value);
+      return this;
+    }
+
+    public ModuleBuilder setRegistry(FakeRegistry value) {
+      this.builder.setRegistry(value);
+      return this;
+    }
+
+    public ModuleBuilder setExecutionPlatformsToRegister(ImmutableList<String> value) {
+      this.builder.setExecutionPlatformsToRegister(value);
+      return this;
+    }
+
+    public ModuleBuilder setToolchainsToRegister(ImmutableList<String> value) {
+      this.builder.setToolchainsToRegister(value);
+      return this;
+    }
+
+    public ModuleBuilder addExtensionUsage(ModuleExtensionUsage value) {
+      this.builder.addExtensionUsage(value);
+      return this;
+    }
+
+    public Map.Entry<ModuleKey, Module> buildEntry() {
+      Module module = this.build();
+      return new SimpleEntry<>(this.key, module);
+    }
+
+    public Module build() {
+      ImmutableMap<String, ModuleKey> builtDeps = this.deps.buildOrThrow();
+
+      /* Copy dep entries that have not been changed to original deps */
+      ImmutableMap<String, ModuleKey> initOriginalDeps = this.originalDeps.buildOrThrow();
+      for (Entry<String, ModuleKey> e : builtDeps.entrySet()) {
+        if (!initOriginalDeps.containsKey(e.getKey())) {
+          originalDeps.put(e);
+        }
+      }
+      ImmutableMap<String, ModuleKey> builtOriginalDeps = this.originalDeps.buildOrThrow();
+
+      return this.builder.setDeps(builtDeps).setOriginalDeps(builtOriginalDeps).build();
+    }
+  }
+
   public static RepositoryMapping createRepositoryMapping(ModuleKey key, String... names) {
     ImmutableMap.Builder<RepositoryName, RepositoryName> mappingBuilder = ImmutableMap.builder();
     for (int i = 0; i < names.length; i += 2) {
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java
index 683b1ec..0c4d2af 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/DiscoveryTest.java
@@ -29,6 +29,7 @@
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
 import com.google.devtools.build.lib.analysis.util.AnalysisMock;
+import com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.ModuleBuilder;
 import com.google.devtools.build.lib.bazel.bzlmod.ModuleFileValue.RootModuleFileValue;
 import com.google.devtools.build.lib.bazel.repository.starlark.StarlarkRepositoryModule;
 import com.google.devtools.build.lib.clock.BlazeClock;
@@ -231,39 +232,22 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
                 .addDep("C", createModuleKey("C", "2.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0")
                 .addDep("D", createModuleKey("D", "3.0"))
                 .setRegistry(registry)
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0")
                 .addDep("D", createModuleKey("D", "3.0"))
                 .setRegistry(registry)
-                .build(),
-            createModuleKey("D", "3.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("3.0"))
-                .setKey(createModuleKey("D", "3.0"))
-                .setRegistry(registry)
-                .build());
+                .buildEntry(),
+            ModuleBuilder.create("D", "3.0").setRegistry(registry).buildEntry());
   }
 
   @Test
@@ -290,30 +274,15 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
                 .addDep("C", createModuleKey("C", "1.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
-                .setRegistry(registry)
-                .build(),
-            createModuleKey("C", "1.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("C", "1.0"))
-                .setRegistry(registry)
-                .build());
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0").setRegistry(registry).buildEntry(),
+            ModuleBuilder.create("C", "1.0").setRegistry(registry).buildEntry());
   }
 
   @Test
@@ -341,22 +310,13 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
-                .setRegistry(registry)
-                .build());
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0").setRegistry(registry).buildEntry());
   }
 
   @Test
@@ -382,31 +342,20 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0")
                 .addDep("C", createModuleKey("C", "2.0"))
                 .setRegistry(registry)
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0")
                 .addDep("B", createModuleKey("B", "1.0"))
                 .setRegistry(registry)
-                .build());
+                .buildEntry());
   }
 
   @Test
@@ -430,23 +379,17 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0")
                 .addDep("A", ModuleKey.ROOT)
+                .addOriginalDep("A", createModuleKey("A", "2.0"))
                 .setRegistry(registry)
-                .build());
+                .buildEntry());
   }
 
   @Test
@@ -472,30 +415,18 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "0.1"))
-                .build(),
-            createModuleKey("B", "0.1"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("0.1"))
-                .setKey(createModuleKey("B", "0.1"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "0.1")
                 .addDep("C", createModuleKey("C", "2.0"))
+                .addOriginalDep("C", createModuleKey("C", "1.0"))
                 .setRegistry(registry)
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
-                .setRegistry(registry)
-                .build());
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0").setRegistry(registry).buildEntry());
   }
 
   @Test
@@ -526,31 +457,20 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "0.1"))
-                .build(),
-            createModuleKey("B", "0.1"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("0.1"))
-                .setKey(createModuleKey("B", "0.1"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "0.1")
                 .addDep("C", createModuleKey("C", "1.0"))
                 .setRegistry(registry1)
-                .build(),
-            createModuleKey("C", "1.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("C", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("C", "1.0")
                 .addDep("B", createModuleKey("B", "0.1"))
                 .setRegistry(registry2)
-                .build());
+                .buildEntry());
   }
 
   @Test
@@ -579,29 +499,18 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "0.1"))
-                .build(),
-            createModuleKey("B", "0.1"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("0.1"))
-                .setKey(createModuleKey("B", "0.1"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "0.1")
                 .addDep("C", createModuleKey("C", ""))
+                .addOriginalDep("C", createModuleKey("C", "1.0"))
                 .setRegistry(registry)
-                .build(),
-            createModuleKey("C", ""),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", ""))
-                .build());
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0").setKey(createModuleKey("C", "")).buildEntry());
   }
 
   @Test
@@ -638,46 +547,31 @@
       fail(result.getError().toString());
     }
     DiscoveryValue discoveryValue = result.get(DiscoveryValue.KEY);
-    assertThat(discoveryValue.getDepGraph())
+    assertThat(discoveryValue.getDepGraph().entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setKey(ModuleKey.ROOT)
+            ModuleBuilder.create("", "")
                 .addDep("bazel_tools", createModuleKey("bazel_tools", ""))
                 .addDep("local_config_platform", createModuleKey("local_config_platform", ""))
                 .addDep("foo", createModuleKey("foo", "2.0"))
-                .build(),
-            createModuleKey("bazel_tools", ""),
-            Module.builder()
-                .setName("bazel_tools")
-                .setVersion(Version.parse("1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("bazel_tools", "1.0")
                 .setKey(createModuleKey("bazel_tools", ""))
                 .addDep("local_config_platform", createModuleKey("local_config_platform", ""))
                 .addDep("foo", createModuleKey("foo", "1.0"))
-                .build(),
-            createModuleKey("local_config_platform", ""),
-            Module.builder()
-                .setName("local_config_platform")
+                .buildEntry(),
+            ModuleBuilder.create("local_config_platform", "")
                 .setKey(createModuleKey("local_config_platform", ""))
                 .addDep("bazel_tools", createModuleKey("bazel_tools", ""))
-                .build(),
-            createModuleKey("foo", "1.0"),
-            Module.builder()
-                .setName("foo")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("foo", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("foo", "1.0")
                 .addDep("bazel_tools", createModuleKey("bazel_tools", ""))
                 .addDep("local_config_platform", createModuleKey("local_config_platform", ""))
                 .setRegistry(registry)
-                .build(),
-            createModuleKey("foo", "2.0"),
-            Module.builder()
-                .setName("foo")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("foo", "2.0"))
+                .buildEntry(),
+            ModuleBuilder.create("foo", "2.0")
                 .addDep("bazel_tools", createModuleKey("bazel_tools", ""))
                 .addDep("local_config_platform", createModuleKey("local_config_platform", ""))
                 .setRegistry(registry)
-                .build());
+                .buildEntry());
   }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java
index a15de71..7ff9331 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleFileFunctionTest.java
@@ -29,6 +29,7 @@
 import com.google.devtools.build.lib.analysis.ConfiguredRuleClassProvider;
 import com.google.devtools.build.lib.analysis.ServerDirectories;
 import com.google.devtools.build.lib.analysis.util.AnalysisMock;
+import com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.ModuleBuilder;
 import com.google.devtools.build.lib.bazel.bzlmod.ModuleFileValue.RootModuleFileValue;
 import com.google.devtools.build.lib.bazel.repository.starlark.StarlarkRepositoryModule;
 import com.google.devtools.build.lib.clock.BlazeClock;
@@ -204,11 +205,8 @@
     RootModuleFileValue rootModuleFileValue = result.get(ModuleFileValue.KEY_FOR_ROOT_MODULE);
     assertThat(rootModuleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("0.1"))
+            ModuleBuilder.create("A", "0.1", 4)
                 .setKey(ModuleKey.ROOT)
-                .setCompatibilityLevel(4)
                 .setExecutionPlatformsToRegister(
                     ImmutableList.of("//my:platform", "//my:platform2"))
                 .setToolchainsToRegister(ImmutableList.of("//my:toolchain", "//my:toolchain2"))
@@ -250,7 +248,7 @@
     RootModuleFileValue rootModuleFileValue = result.get(ModuleFileValue.KEY_FOR_ROOT_MODULE);
     assertThat(rootModuleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
+            ModuleBuilder.create("", "")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
                 .build());
@@ -303,10 +301,7 @@
     ModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+            ModuleBuilder.create("B", "1.0")
                 .addDep("C", createModuleKey("C", "2.0"))
                 .setRegistry(registry2)
                 .build());
@@ -344,9 +339,7 @@
     ModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
+            ModuleBuilder.create("B", "1.0")
                 .setKey(createModuleKey("B", ""))
                 .addDep("C", createModuleKey("C", "2.0"))
                 .build());
@@ -383,11 +376,7 @@
     ModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
-                .setCompatibilityLevel(6)
+            ModuleBuilder.create("B", "1.0", 6)
                 .addDep("C", createModuleKey("C", "3.0"))
                 .setRegistry(registry2)
                 .build());
@@ -425,10 +414,7 @@
     ModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setName("mymod")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("mymod", "1.0"))
+            ModuleBuilder.create("mymod", "1.0")
                 .addDep("rules_jvm_external", createModuleKey("rules_jvm_external", "2.0"))
                 .setRegistry(registry)
                 .addExtensionUsage(
@@ -529,7 +515,7 @@
     ModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
+            ModuleBuilder.create("", "")
                 .setKey(ModuleKey.ROOT)
                 .addExtensionUsage(
                     ModuleExtensionUsage.builder()
@@ -571,10 +557,7 @@
     ModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setName("mymod")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("mymod", "1.0"))
+            ModuleBuilder.create("mymod", "1.0")
                 .setRegistry(registry)
                 .addExtensionUsage(
                     ModuleExtensionUsage.builder()
@@ -673,8 +656,7 @@
     RootModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setKey(ModuleKey.ROOT)
+            ModuleBuilder.create("", "")
                 .addDep("bazel_tools", createModuleKey("bazel_tools", ""))
                 .addDep("local_config_platform", createModuleKey("local_config_platform", ""))
                 .addDep("foo", createModuleKey("foo", "1.0"))
@@ -711,9 +693,7 @@
     ModuleFileValue moduleFileValue = result.get(skyKey);
     assertThat(moduleFileValue.getModule())
         .isEqualTo(
-            Module.builder()
-                .setName("bazel_tools")
-                .setVersion(Version.parse("1.0"))
+            ModuleBuilder.create("bazel_tools", "1.0")
                 .setKey(createModuleKey("bazel_tools", ""))
                 .addDep("local_config_platform", createModuleKey("local_config_platform", ""))
                 .addDep("foo", createModuleKey("foo", "2.0"))
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleTest.java
index e13c265..4e6d7c3 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/ModuleTest.java
@@ -18,6 +18,7 @@
 import static com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.createModuleKey;
 import static com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.createRepositoryMapping;
 
+import com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.ModuleBuilder;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -29,7 +30,7 @@
   @Test
   public void withDepKeysTransformed() throws Exception {
     assertThat(
-            Module.builder()
+            ModuleBuilder.create("", "")
                 .addDep("dep_foo", createModuleKey("foo", "1.0"))
                 .addDep("dep_bar", createModuleKey("bar", "2.0"))
                 .build()
@@ -38,9 +39,11 @@
                         createModuleKey(
                             key.getName() + "_new", key.getVersion().getOriginal() + ".1")))
         .isEqualTo(
-            Module.builder()
+            ModuleBuilder.create("", "")
                 .addDep("dep_foo", createModuleKey("foo_new", "1.0.1"))
+                .addOriginalDep("dep_foo", createModuleKey("foo", "1.0"))
                 .addDep("dep_bar", createModuleKey("bar_new", "2.0.1"))
+                .addOriginalDep("dep_bar", createModuleKey("bar", "2.0"))
                 .build());
   }
 
@@ -48,10 +51,7 @@
   public void getRepoMapping() throws Exception {
     ModuleKey key = createModuleKey("test_module", "1.0");
     Module module =
-        Module.builder()
-            .setName(key.getName())
-            .setVersion(key.getVersion())
-            .setKey(key)
+        ModuleBuilder.create(key.getName(), key.getVersion())
             .addDep("my_foo", createModuleKey("foo", "1.0"))
             .addDep("my_bar", createModuleKey("bar", "2.0"))
             .addDep("my_root", ModuleKey.ROOT)
@@ -73,9 +73,7 @@
   @Test
   public void getRepoMapping_asMainModule() throws Exception {
     Module module =
-        Module.builder()
-            .setName("test_module")
-            .setVersion(Version.parse("1.0"))
+        ModuleBuilder.create("test_module", "1.0")
             .setKey(ModuleKey.ROOT)
             .addDep("my_foo", createModuleKey("foo", "1.0"))
             .addDep("my_bar", createModuleKey("bar", "2.0"))
diff --git a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/SelectionTest.java b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/SelectionTest.java
index e450119..12d7b5a 100644
--- a/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/SelectionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/bazel/bzlmod/SelectionTest.java
@@ -21,6 +21,7 @@
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
+import com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.ModuleBuilder;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
@@ -34,79 +35,38 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("BfromA", createModuleKey("B", "1.0"))
                     .addDep("CfromA", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
+                ModuleBuilder.create("B", "1.0")
                     .addDep("DfromB", createModuleKey("D", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
+                ModuleBuilder.create("C", "2.0")
                     .addDep("DfromC", createModuleKey("D", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("D", "1.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("D", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("D", "2.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("D", "2.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("D", "1.0", 1).buildEntry())
+            .put(ModuleBuilder.create("D", "2.0", 1).buildEntry())
             .buildOrThrow();
 
-    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()))
+    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("BfromA", createModuleKey("B", "1.0"))
                 .addDep("CfromA", createModuleKey("C", "2.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0")
                 .addDep("DfromB", createModuleKey("D", "2.0"))
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
+                .addOriginalDep("DfromB", createModuleKey("D", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0")
                 .addDep("DfromC", createModuleKey("D", "2.0"))
-                .build(),
-            createModuleKey("D", "2.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("D", "2.0"))
-                .setCompatibilityLevel(1)
-                .build())
+                .buildEntry(),
+            ModuleBuilder.create("D", "2.0", 1).buildEntry())
         .inOrder();
   }
 
@@ -115,86 +75,42 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B", createModuleKey("B", "1.0"))
                     .addDep("C", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
+                ModuleBuilder.create("B", "1.0")
                     .addDep("D", createModuleKey("D", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
+                ModuleBuilder.create("C", "2.0")
                     .addDep("D", createModuleKey("D", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("D", "1.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("D", "1.0"))
+                ModuleBuilder.create("D", "1.0")
                     .addDep("E", createModuleKey("E", "1.0"))
-                    .build())
-            .put(
-                createModuleKey("D", "2.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("D", "2.0"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("D", "2.0").buildEntry())
             // Only D@1.0 needs E. When D@1.0 is removed, E should be gone as well (even though
             // E@1.0 is selected for E).
-            .put(
-                createModuleKey("E", "1.0"),
-                Module.builder()
-                    .setName("E")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("E", "1.0"))
-                    .build())
+            .put(ModuleBuilder.create("E", "1.0").buildEntry())
             .build();
 
-    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()))
+    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
                 .addDep("C", createModuleKey("C", "2.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0")
                 .addDep("D", createModuleKey("D", "2.0"))
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
-                .addDep("D", createModuleKey("D", "2.0"))
-                .build(),
-            createModuleKey("D", "2.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("D", "2.0"))
-                .build())
+                .addOriginalDep("D", createModuleKey("D", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0").addDep("D", createModuleKey("D", "2.0")).buildEntry(),
+            ModuleBuilder.create("D", "2.0").buildEntry())
         .inOrder();
   }
 
@@ -203,69 +119,36 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B", createModuleKey("B", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
+                ModuleBuilder.create("B", "1.0")
                     .addDep("C", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
+                ModuleBuilder.create("C", "2.0")
                     .addDep("B", createModuleKey("B", "1.0-pre"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0-pre"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0-pre"))
-                    .setKey(createModuleKey("B", "1.0-pre"))
+                ModuleBuilder.create("B", "1.0-pre")
                     .addDep("D", createModuleKey("D", "1.0"))
-                    .build())
-            .put(
-                createModuleKey("D", "1.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("D", "1.0"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("D", "1.0").buildEntry())
             .buildOrThrow();
 
-    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()))
+    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
-                .addDep("C", createModuleKey("C", "2.0"))
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0").addDep("C", createModuleKey("C", "2.0")).buildEntry(),
+            ModuleBuilder.create("C", "2.0")
                 .addDep("B", createModuleKey("B", "1.0"))
-                .build())
+                .addOriginalDep("B", createModuleKey("B", "1.0-pre"))
+                .buildEntry())
         .inOrder();
     // D is completely gone.
   }
@@ -275,46 +158,21 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("BfromA", createModuleKey("B", "1.0"))
                     .addDep("CfromA", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
+                ModuleBuilder.create("B", "1.0")
                     .addDep("DfromB", createModuleKey("D", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
+                ModuleBuilder.create("C", "2.0")
                     .addDep("DfromC", createModuleKey("D", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("D", "1.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("D", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("D", "2.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("D", "2.0"))
-                    .setCompatibilityLevel(2)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("D", "1.0", 1).buildEntry())
+            .put(ModuleBuilder.create("D", "2.0", 2).buildEntry())
             .buildOrThrow();
 
     ExternalDepsException e =
@@ -336,71 +194,29 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.parse("1.0"))
+                ModuleBuilder.create("A", "1.0")
                     .setKey(ModuleKey.ROOT)
                     .addDep("B", createModuleKey("B", "1.0"))
                     .addDep("C", createModuleKey("C", "1.0"))
                     .addDep("D", createModuleKey("D", "1.0"))
                     .addDep("E", createModuleKey("E", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
+                ModuleBuilder.create("B", "1.0")
                     .addDep("C", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("C", "2.0", 2).buildEntry())
+            .put(ModuleBuilder.create("C", "1.0", 1).buildEntry())
             .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
-                    .setCompatibilityLevel(2)
-                    .build())
-            .put(
-                createModuleKey("C", "1.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("C", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("D", "1.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("D", "1.0"))
+                ModuleBuilder.create("D", "1.0")
                     .addDep("B", createModuleKey("B", "1.1"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("B", "1.1").buildEntry())
             .put(
-                createModuleKey("B", "1.1"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.1"))
-                    .setKey(createModuleKey("B", "1.1"))
-                    .build())
-            .put(
-                createModuleKey("E", "1.0"),
-                Module.builder()
-                    .setName("E")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("E", "1.0"))
+                ModuleBuilder.create("E", "1.0")
                     .addDep("C", createModuleKey("C", "1.1"))
-                    .build())
-            .put(
-                createModuleKey("C", "1.1"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.1"))
-                    .setKey(createModuleKey("C", "1.1"))
-                    .setCompatibilityLevel(1)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("C", "1.1", 1).buildEntry())
             .buildOrThrow();
 
     // After selection, C 2.0 is gone, so we're okay.
@@ -408,45 +224,21 @@
     //       \-> C 1.1
     //        \-> D 1.0 -> B 1.1
     //         \-> E 1.0 -> C 1.1
-    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()))
+    assertThat(Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.parse("1.0"))
+            ModuleBuilder.create("A", "1.0")
                 .setKey(ModuleKey.ROOT)
                 .addDep("B", createModuleKey("B", "1.1"))
+                .addOriginalDep("B", createModuleKey("B", "1.0"))
                 .addDep("C", createModuleKey("C", "1.1"))
+                .addOriginalDep("C", createModuleKey("C", "1.0"))
                 .addDep("D", createModuleKey("D", "1.0"))
                 .addDep("E", createModuleKey("E", "1.0"))
-                .build(),
-            createModuleKey("B", "1.1"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.1"))
-                .setKey(createModuleKey("B", "1.1"))
-                .build(),
-            createModuleKey("C", "1.1"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("1.1"))
-                .setKey(createModuleKey("C", "1.1"))
-                .setCompatibilityLevel(1)
-                .build(),
-            createModuleKey("D", "1.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("D", "1.0"))
-                .addDep("B", createModuleKey("B", "1.1"))
-                .build(),
-            createModuleKey("E", "1.0"),
-            Module.builder()
-                .setName("E")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("E", "1.0"))
-                .addDep("C", createModuleKey("C", "1.1"))
-                .build())
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.1").buildEntry(),
+            ModuleBuilder.create("C", "1.1", 1).buildEntry(),
+            ModuleBuilder.create("D", "1.0").addDep("B", createModuleKey("B", "1.1")).buildEntry(),
+            ModuleBuilder.create("E", "1.0").addDep("C", createModuleKey("C", "1.1")).buildEntry())
         .inOrder();
   }
 
@@ -455,28 +247,13 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B1", createModuleKey("B", "1.0"))
                     .addDep("B2", createModuleKey("B", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
-                    .build())
-            .put(
-                createModuleKey("B", "2.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("B", "2.0"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("B", "1.0").buildEntry())
+            .put(ModuleBuilder.create("B", "2.0").buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -500,28 +277,13 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B1", createModuleKey("B", "1.0"))
                     .addDep("B2", createModuleKey("B", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
-                    .build())
-            .put(
-                createModuleKey("B", "2.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("B", "2.0"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("B", "1.0").buildEntry())
+            .put(ModuleBuilder.create("B", "2.0").buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -529,28 +291,15 @@
             MultipleVersionOverride.create(
                 ImmutableList.of(Version.parse("1.0"), Version.parse("2.0")), ""));
 
-    assertThat(Selection.run(depGraph, overrides))
+    assertThat(Selection.run(depGraph, overrides).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("B1", createModuleKey("B", "1.0"))
                 .addDep("B2", createModuleKey("B", "2.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
-                .build(),
-            createModuleKey("B", "2.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("B", "2.0"))
-                .build())
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0").buildEntry(),
+            ModuleBuilder.create("B", "2.0").buildEntry())
         .inOrder();
   }
 
@@ -559,36 +308,15 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B1", createModuleKey("B", "1.0"))
                     .addDep("B2", createModuleKey("B", "1.3"))
                     .addDep("B3", createModuleKey("B", "1.5"))
-                    .build())
-            .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
-                    .build())
-            .put(
-                createModuleKey("B", "1.3"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.3"))
-                    .setKey(createModuleKey("B", "1.3"))
-                    .build())
-            .put(
-                createModuleKey("B", "1.5"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.5"))
-                    .setKey(createModuleKey("B", "1.5"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("B", "1.0").buildEntry())
+            .put(ModuleBuilder.create("B", "1.3").buildEntry())
+            .put(ModuleBuilder.create("B", "1.5").buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -609,46 +337,21 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("BfromA", createModuleKey("B", "1.0"))
                     .addDep("CfromA", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
+                ModuleBuilder.create("B", "1.0")
                     .addDep("DfromB", createModuleKey("D", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
+                ModuleBuilder.create("C", "2.0")
                     .addDep("DfromC", createModuleKey("D", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("D", "1.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("D", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("D", "2.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("D", "2.0"))
-                    .setCompatibilityLevel(2)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("D", "1.0", 1).buildEntry())
+            .put(ModuleBuilder.create("D", "2.0", 2).buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -656,44 +359,21 @@
             MultipleVersionOverride.create(
                 ImmutableList.of(Version.parse("1.0"), Version.parse("2.0")), ""));
 
-    assertThat(Selection.run(depGraph, overrides))
+    assertThat(Selection.run(depGraph, overrides).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("BfromA", createModuleKey("B", "1.0"))
                 .addDep("CfromA", createModuleKey("C", "2.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0")
                 .addDep("DfromB", createModuleKey("D", "1.0"))
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0")
                 .addDep("DfromC", createModuleKey("D", "2.0"))
-                .build(),
-            createModuleKey("D", "1.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("D", "1.0"))
-                .setCompatibilityLevel(1)
-                .build(),
-            createModuleKey("D", "2.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("D", "2.0"))
-                .setCompatibilityLevel(2)
-                .build())
+                .buildEntry(),
+            ModuleBuilder.create("D", "1.0", 1).buildEntry(),
+            ModuleBuilder.create("D", "2.0", 2).buildEntry())
         .inOrder();
   }
 
@@ -702,44 +382,21 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("BfromA", createModuleKey("B", "1.0"))
                     .addDep("CfromA", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B", "1.0"),
-                Module.builder()
-                    .setName("B")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B", "1.0"))
+                ModuleBuilder.create("B", "1.0")
                     .addDep("DfromB", createModuleKey("D", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
+                ModuleBuilder.create("C", "2.0")
                     .addDep("DfromC", createModuleKey("D", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("D", "1.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("D", "1.0"))
-                    .build())
-            .put(
-                createModuleKey("D", "2.0"),
-                Module.builder()
-                    .setName("D")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("D", "2.0"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("D", "1.0").buildEntry())
+            .put(ModuleBuilder.create("D", "2.0").buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -747,42 +404,21 @@
             MultipleVersionOverride.create(
                 ImmutableList.of(Version.parse("1.0"), Version.parse("2.0")), ""));
 
-    assertThat(Selection.run(depGraph, overrides))
+    assertThat(Selection.run(depGraph, overrides).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("BfromA", createModuleKey("B", "1.0"))
                 .addDep("CfromA", createModuleKey("C", "2.0"))
-                .build(),
-            createModuleKey("B", "1.0"),
-            Module.builder()
-                .setName("B")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B", "1.0")
                 .addDep("DfromB", createModuleKey("D", "1.0"))
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
+                .buildEntry(),
+            ModuleBuilder.create("C", "2.0")
                 .addDep("DfromC", createModuleKey("D", "2.0"))
-                .build(),
-            createModuleKey("D", "1.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("D", "1.0"))
-                .build(),
-            createModuleKey("D", "2.0"),
-            Module.builder()
-                .setName("D")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("D", "2.0"))
-                .build())
+                .buildEntry(),
+            ModuleBuilder.create("D", "1.0").buildEntry(),
+            ModuleBuilder.create("D", "2.0").buildEntry())
         .inOrder();
   }
 
@@ -796,97 +432,39 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B1", createModuleKey("B1", "1.0"))
                     .addDep("B2", createModuleKey("B2", "1.0"))
                     .addDep("B3", createModuleKey("B3", "1.0"))
                     .addDep("B4", createModuleKey("B4", "1.0"))
                     .addDep("B5", createModuleKey("B5", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B1", "1.0"),
-                Module.builder()
-                    .setName("B1")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B1", "1.0"))
+                ModuleBuilder.create("B1", "1.0")
                     .addDep("C", createModuleKey("C", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B2", "1.0"),
-                Module.builder()
-                    .setName("B2")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B2", "1.0"))
+                ModuleBuilder.create("B2", "1.0")
                     .addDep("C", createModuleKey("C", "1.3"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B3", "1.0"),
-                Module.builder()
-                    .setName("B3")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B3", "1.0"))
+                ModuleBuilder.create("B3", "1.0")
                     .addDep("C", createModuleKey("C", "1.5"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B4", "1.0"),
-                Module.builder()
-                    .setName("B4")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B4", "1.0"))
+                ModuleBuilder.create("B4", "1.0")
                     .addDep("C", createModuleKey("C", "1.7"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B5", "1.0"),
-                Module.builder()
-                    .setName("B5")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B5", "1.0"))
+                ModuleBuilder.create("B5", "1.0")
                     .addDep("C", createModuleKey("C", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("C", "1.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("C", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "1.3"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.3"))
-                    .setKey(createModuleKey("C", "1.3"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "1.5"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.5"))
-                    .setKey(createModuleKey("C", "1.5"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "1.7"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.7"))
-                    .setKey(createModuleKey("C", "1.7"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
-                    .setCompatibilityLevel(2)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("C", "1.0", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "1.3", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "1.5", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "1.7", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "2.0", 2).buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -900,75 +478,30 @@
     //   \-> B3@1.0 -> C@1.7  [originally C@1.5]
     //   \-> B4@1.0 -> C@1.7  [allowed]
     //   \-> B5@1.0 -> C@2.0  [allowed]
-    assertThat(Selection.run(depGraph, overrides))
+    assertThat(Selection.run(depGraph, overrides).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("B1", createModuleKey("B1", "1.0"))
                 .addDep("B2", createModuleKey("B2", "1.0"))
                 .addDep("B3", createModuleKey("B3", "1.0"))
                 .addDep("B4", createModuleKey("B4", "1.0"))
                 .addDep("B5", createModuleKey("B5", "1.0"))
-                .build(),
-            createModuleKey("B1", "1.0"),
-            Module.builder()
-                .setName("B1")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B1", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B1", "1.0")
                 .addDep("C", createModuleKey("C", "1.3"))
-                .build(),
-            createModuleKey("B2", "1.0"),
-            Module.builder()
-                .setName("B2")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B2", "1.0"))
-                .addDep("C", createModuleKey("C", "1.3"))
-                .build(),
-            createModuleKey("B3", "1.0"),
-            Module.builder()
-                .setName("B3")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B3", "1.0"))
+                .addOriginalDep("C", createModuleKey("C", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B2", "1.0").addDep("C", createModuleKey("C", "1.3")).buildEntry(),
+            ModuleBuilder.create("B3", "1.0")
                 .addDep("C", createModuleKey("C", "1.7"))
-                .build(),
-            createModuleKey("B4", "1.0"),
-            Module.builder()
-                .setName("B4")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B4", "1.0"))
-                .addDep("C", createModuleKey("C", "1.7"))
-                .build(),
-            createModuleKey("B5", "1.0"),
-            Module.builder()
-                .setName("B5")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B5", "1.0"))
-                .addDep("C", createModuleKey("C", "2.0"))
-                .build(),
-            createModuleKey("C", "1.3"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("1.3"))
-                .setKey(createModuleKey("C", "1.3"))
-                .setCompatibilityLevel(1)
-                .build(),
-            createModuleKey("C", "1.7"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("1.7"))
-                .setKey(createModuleKey("C", "1.7"))
-                .setCompatibilityLevel(1)
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
-                .setCompatibilityLevel(2)
-                .build())
+                .addOriginalDep("C", createModuleKey("C", "1.5"))
+                .buildEntry(),
+            ModuleBuilder.create("B4", "1.0").addDep("C", createModuleKey("C", "1.7")).buildEntry(),
+            ModuleBuilder.create("B5", "1.0").addDep("C", createModuleKey("C", "2.0")).buildEntry(),
+            ModuleBuilder.create("C", "1.3", 1).buildEntry(),
+            ModuleBuilder.create("C", "1.7", 1).buildEntry(),
+            ModuleBuilder.create("C", "2.0", 2).buildEntry())
         .inOrder();
   }
 
@@ -980,63 +513,27 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B1", createModuleKey("B1", "1.0"))
                     .addDep("B2", createModuleKey("B2", "1.0"))
                     .addDep("B3", createModuleKey("B3", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B1", "1.0"),
-                Module.builder()
-                    .setName("B1")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B1", "1.0"))
+                ModuleBuilder.create("B1", "1.0")
                     .addDep("C", createModuleKey("C", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B2", "1.0"),
-                Module.builder()
-                    .setName("B2")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B2", "1.0"))
+                ModuleBuilder.create("B2", "1.0")
                     .addDep("C", createModuleKey("C", "1.7"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B3", "1.0"),
-                Module.builder()
-                    .setName("B3")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B3", "1.0"))
+                ModuleBuilder.create("B3", "1.0")
                     .addDep("C", createModuleKey("C", "2.0"))
-                    .build())
-            .put(
-                createModuleKey("C", "1.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("C", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "1.7"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.7"))
-                    .setKey(createModuleKey("C", "1.7"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
-                    .setCompatibilityLevel(2)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("C", "1.0", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "1.7", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "2.0", 2).buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -1061,63 +558,27 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B1", createModuleKey("B1", "1.0"))
                     .addDep("B2", createModuleKey("B2", "1.0"))
                     .addDep("B3", createModuleKey("B3", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B1", "1.0"),
-                Module.builder()
-                    .setName("B1")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B1", "1.0"))
+                ModuleBuilder.create("B1", "1.0")
                     .addDep("C", createModuleKey("C", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B2", "1.0"),
-                Module.builder()
-                    .setName("B2")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B2", "1.0"))
+                ModuleBuilder.create("B2", "1.0")
                     .addDep("C", createModuleKey("C", "2.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B3", "1.0"),
-                Module.builder()
-                    .setName("B3")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B3", "1.0"))
+                ModuleBuilder.create("B3", "1.0")
                     .addDep("C", createModuleKey("C", "3.0"))
-                    .build())
-            .put(
-                createModuleKey("C", "1.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("C", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
-                    .setCompatibilityLevel(2)
-                    .build())
-            .put(
-                createModuleKey("C", "3.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("3.0"))
-                    .setKey(createModuleKey("C", "3.0"))
-                    .setCompatibilityLevel(3)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("C", "1.0", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "2.0", 2).buildEntry())
+            .put(ModuleBuilder.create("C", "3.0", 3).buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -1145,96 +606,37 @@
     ImmutableMap<ModuleKey, Module> depGraph =
         ImmutableMap.<ModuleKey, Module>builder()
             .put(
-                ModuleKey.ROOT,
-                Module.builder()
-                    .setName("A")
-                    .setVersion(Version.EMPTY)
+                ModuleBuilder.create("A", Version.EMPTY)
                     .setKey(ModuleKey.ROOT)
                     .addDep("B1", createModuleKey("B1", "1.0"))
                     .addDep("B2", createModuleKey("B2", "1.0"))
                     .addDep("B3", createModuleKey("B3", "1.0"))
                     .addDep("B4", createModuleKey("B4", "1.0"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B1", "1.0"),
-                Module.builder()
-                    .setName("B1")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B1", "1.0"))
+                ModuleBuilder.create("B1", "1.0")
                     .addDep("C", createModuleKey("C", "1.0"))
                     .addDep("B2", createModuleKey("B2", "1.1"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B2", "1.0"),
-                Module.builder()
-                    .setName("B2")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B2", "1.0"))
+                ModuleBuilder.create("B2", "1.0")
                     .addDep("C", createModuleKey("C", "1.5"))
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("B2", "1.1").buildEntry())
             .put(
-                createModuleKey("B2", "1.1"),
-                Module.builder()
-                    .setName("B2")
-                    .setVersion(Version.parse("1.1"))
-                    .setKey(createModuleKey("B2", "1.1"))
-                    .build())
-            .put(
-                createModuleKey("B3", "1.0"),
-                Module.builder()
-                    .setName("B3")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B3", "1.0"))
+                ModuleBuilder.create("B3", "1.0")
                     .addDep("C", createModuleKey("C", "2.0"))
                     .addDep("B4", createModuleKey("B4", "1.1"))
-                    .build())
+                    .buildEntry())
             .put(
-                createModuleKey("B4", "1.0"),
-                Module.builder()
-                    .setName("B4")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("B4", "1.0"))
+                ModuleBuilder.create("B4", "1.0")
                     .addDep("C", createModuleKey("C", "3.0"))
-                    .build())
-            .put(
-                createModuleKey("B4", "1.1"),
-                Module.builder()
-                    .setName("B4")
-                    .setVersion(Version.parse("1.1"))
-                    .setKey(createModuleKey("B4", "1.1"))
-                    .build())
-            .put(
-                createModuleKey("C", "1.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.0"))
-                    .setKey(createModuleKey("C", "1.0"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "1.5"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("1.5"))
-                    .setKey(createModuleKey("C", "1.5"))
-                    .setCompatibilityLevel(1)
-                    .build())
-            .put(
-                createModuleKey("C", "2.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("2.0"))
-                    .setKey(createModuleKey("C", "2.0"))
-                    .setCompatibilityLevel(2)
-                    .build())
-            .put(
-                createModuleKey("C", "3.0"),
-                Module.builder()
-                    .setName("C")
-                    .setVersion(Version.parse("3.0"))
-                    .setKey(createModuleKey("C", "3.0"))
-                    .setCompatibilityLevel(3)
-                    .build())
+                    .buildEntry())
+            .put(ModuleBuilder.create("B4", "1.1").buildEntry())
+            .put(ModuleBuilder.create("C", "1.0", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "1.5", 1).buildEntry())
+            .put(ModuleBuilder.create("C", "2.0", 2).buildEntry())
+            .put(ModuleBuilder.create("C", "3.0", 3).buildEntry())
             .buildOrThrow();
     ImmutableMap<String, ModuleOverride> overrides =
         ImmutableMap.of(
@@ -1249,60 +651,29 @@
     //   \          \-> B4@1.1
     //   \-> B4@1.1
     // C@1.5 and C@3.0, the versions violating the allowlist, are gone.
-    assertThat(Selection.run(depGraph, overrides))
+    assertThat(Selection.run(depGraph, overrides).entrySet())
         .containsExactly(
-            ModuleKey.ROOT,
-            Module.builder()
-                .setName("A")
-                .setVersion(Version.EMPTY)
+            ModuleBuilder.create("A", Version.EMPTY)
                 .setKey(ModuleKey.ROOT)
                 .addDep("B1", createModuleKey("B1", "1.0"))
                 .addDep("B2", createModuleKey("B2", "1.1"))
+                .addOriginalDep("B2", createModuleKey("B2", "1.0"))
                 .addDep("B3", createModuleKey("B3", "1.0"))
                 .addDep("B4", createModuleKey("B4", "1.1"))
-                .build(),
-            createModuleKey("B1", "1.0"),
-            Module.builder()
-                .setName("B1")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B1", "1.0"))
+                .addOriginalDep("B4", createModuleKey("B4", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B1", "1.0")
                 .addDep("C", createModuleKey("C", "1.0"))
                 .addDep("B2", createModuleKey("B2", "1.1"))
-                .build(),
-            createModuleKey("B2", "1.1"),
-            Module.builder()
-                .setName("B2")
-                .setVersion(Version.parse("1.1"))
-                .setKey(createModuleKey("B2", "1.1"))
-                .build(),
-            createModuleKey("B3", "1.0"),
-            Module.builder()
-                .setName("B3")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("B3", "1.0"))
+                .buildEntry(),
+            ModuleBuilder.create("B2", "1.1").buildEntry(),
+            ModuleBuilder.create("B3", "1.0")
                 .addDep("C", createModuleKey("C", "2.0"))
                 .addDep("B4", createModuleKey("B4", "1.1"))
-                .build(),
-            createModuleKey("B4", "1.1"),
-            Module.builder()
-                .setName("B4")
-                .setVersion(Version.parse("1.1"))
-                .setKey(createModuleKey("B4", "1.1"))
-                .build(),
-            createModuleKey("C", "1.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("1.0"))
-                .setKey(createModuleKey("C", "1.0"))
-                .setCompatibilityLevel(1)
-                .build(),
-            createModuleKey("C", "2.0"),
-            Module.builder()
-                .setName("C")
-                .setVersion(Version.parse("2.0"))
-                .setKey(createModuleKey("C", "2.0"))
-                .setCompatibilityLevel(2)
-                .build())
+                .buildEntry(),
+            ModuleBuilder.create("B4", "1.1").buildEntry(),
+            ModuleBuilder.create("C", "1.0", 1).buildEntry(),
+            ModuleBuilder.create("C", "2.0", 2).buildEntry())
         .inOrder();
   }
 }