[L] Change in bazel/bazel[master]: Selection with max_compatibility_level
0 views
Skip to first unread message
Copybara Service (Gerrit)
Apr 21, 2023, 4:18:46 PM4/21/23
to Xudong Yang
Copybara Service uploaded patch set #5 to this change.
Selection with max_compatibility_level
See code comments for more details. tl;dr: we use the new `bazel_dep(max_compatibility_level=)` attribute to influence version selection.
Fixes https://github.com/bazelbuild/bazel/issues/17378
RELNOTES: Added a new `max_compatibility_level` attribute to the `bazel_dep` directive, which allows version selection to upgrade a dependency up to the specified compatibility level.
Co-authored-by: Brentley Jones <git...@brentleyjones.com>
PiperOrigin-RevId: 526118928
Change-Id: I332eb3761e0dee0cb7f318cb5d8d1780fca91be8
---
M src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Selection.java
M src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodTestUtil.java
M src/test/java/com/google/devtools/build/lib/bazel/bzlmod/SelectionTest.java
3 files changed, 571 insertions(+), 48 deletions(-)
To view, visit change 217010. To unsubscribe, or for help writing mail filters, visit settings.
Copybara Service (Gerrit)
Apr 21, 2023, 4:18:48 PM4/21/23
to Xudong Yang
Copybara Service submitted this change.
Selection with max_compatibility_level
See code comments for more details. tl;dr: we use the new `bazel_dep(max_compatibility_level=)` attribute to influence version selection.
Fixes https://github.com/bazelbuild/bazel/issues/17378
RELNOTES: Added a new `max_compatibility_level` attribute to the `bazel_dep` directive, which allows version selection to upgrade a dependency up to the specified compatibility level.
Co-authored-by: Brentley Jones <git...@brentleyjones.com>
PiperOrigin-RevId: 526118928
Change-Id: I332eb3761e0dee0cb7f318cb5d8d1780fca91be8
---
M src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Selection.java
M src/test/java/com/google/devtools/build/lib/bazel/bzlmod/BzlmodTestUtil.java
M src/test/java/com/google/devtools/build/lib/bazel/bzlmod/SelectionTest.java
3 files changed, 571 insertions(+), 48 deletions(-)
diff --git a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Selection.java b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Selection.java
index 7db346f..361f523 100644
--- a/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Selection.java
+++ b/src/main/java/com/google/devtools/build/lib/bazel/bzlmod/Selection.java
@@ -15,6 +15,10 @@
package com.google.devtools.build.lib.bazel.bzlmod;
+import static com.google.common.collect.ImmutableList.toImmutableList;
+import static com.google.common.collect.ImmutableSortedMap.toImmutableSortedMap;
+import static java.util.Comparator.naturalOrder;
+
import com.google.auto.value.AutoValue;
import com.google.common.base.Joiner;
import com.google.common.base.Preconditions;
@@ -22,15 +26,19 @@
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSortedSet;
+import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.devtools.build.lib.bazel.bzlmod.InterimModule.DepSpec;
import com.google.devtools.build.lib.server.FailureDetails.ExternalDeps.Code;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
+import java.util.function.Function;
import javax.annotation.Nullable;
/**
@@ -63,6 +71,15 @@
* be removed before the end of selection (by becoming unreachable, for example), otherwise
* it'll be an error since they're not allowed by the override (these versions are in
* selection groups that have no valid target allowed version).
+ * <li>Things get even more complicated with max_compatibility_level. The difference this
+ * introduces is that each "DepSpec" could be satisfied by one of multiple choices. (Without
+ * max_compatibility_level, there is always only one choice.) So what we do is go through all
+ * the combinations of possible choices for each distinct DepSpec, and for each combination,
+ * see if the resulting dep graph is valid. As soon as we find a valid combination, we return
+ * that result. The distinct DepSpecs are sorted by the order they first appear in the dep
+ * graph if we BFS from the root module. The combinations are attempted in the typical
+ * cartesian product order (see {@link Lists#cartesianProduct}); the "version choices" of each
+ * DepSpec are sorted from low to high.
* </ul>
*/
final class Selection {
@@ -176,10 +193,11 @@
module.getName(), module.getCompatibilityLevel()));
if (allowedVersionSet == null) {
// This means that this module has no multiple-version override.
- return SelectionGroup.create(module.getName(), module.getCompatibilityLevel(), Version.EMPTY);
+ return SelectionGroup.create(
+ module.getKey().getName(), module.getCompatibilityLevel(), Version.EMPTY);
}
return SelectionGroup.create(
- module.getName(),
+ module.getKey().getName(),
module.getCompatibilityLevel(),
// We use the `ceiling` method here to quickly locate the lowest allowed version that's
// still no lower than this module's version.
@@ -189,8 +207,92 @@
allowedVersionSet.ceiling(module.getVersion()));
}
+ /**
+ * Computes the possible list of ModuleKeys a single given DepSpec can resolve to. This is
+ * normally just one ModuleKey, but when max_compatibility_level is involved, multiple choices may
+ * be possible.
+ */
+ private static ImmutableList<ModuleKey> computePossibleResolutionResultsForOneDepSpec(
+ DepSpec depSpec,
+ ImmutableMap<ModuleKey, SelectionGroup> selectionGroups,
+ Map<SelectionGroup, Version> selectedVersions) {
+ int minCompatibilityLevel = selectionGroups.get(depSpec.toModuleKey()).getCompatibilityLevel();
+ int maxCompatibilityLevel =
+ depSpec.getMaxCompatibilityLevel() < 0
+ ? minCompatibilityLevel
+ : depSpec.getMaxCompatibilityLevel();
+ // First find the selection groups that this DepSpec could use.
+ return Maps.filterKeys(
+ selectedVersions,
+ group ->
+ group.getModuleName().equals(depSpec.getName())
+ && group.getCompatibilityLevel() >= minCompatibilityLevel
+ && group.getCompatibilityLevel() <= maxCompatibilityLevel
+ && group.getTargetAllowedVersion().compareTo(depSpec.getVersion()) >= 0)
+ .entrySet()
+ .stream()
+ // Collect into an ImmutableSortedMap so that:
+ // 1. The final list is sorted by compatibility level, guaranteeing lowest version first;
+ // 2. Only one ModuleKey is attempted per compatibility level, so that in the case of a
+ // multiple-version override, we only try the lowest allowed version in that
+ // compatibility level (note the Comparators::min call).
+ .collect(
+ toImmutableSortedMap(
+ naturalOrder(),
+ e -> e.getKey().getCompatibilityLevel(),
+ e -> e.getValue(),
+ Comparators::min))
+ .values()
+ .stream()
+ .map(v -> ModuleKey.create(depSpec.getName(), v))
+ .collect(toImmutableList());
+ }
+
+ /**
+ * Computes the possible list of ModuleKeys a DepSpec can resolve to, for all distinct DepSpecs in
+ * the dependency graph.
+ */
+ private static ImmutableMap<DepSpec, ImmutableList<ModuleKey>> computePossibleResolutionResults(
+ ImmutableMap<ModuleKey, InterimModule> depGraph,
+ ImmutableMap<ModuleKey, SelectionGroup> selectionGroups,
+ Map<SelectionGroup, Version> selectedVersions) {
+ // Important that we use a LinkedHashMap here to ensure reproducibility.
+ Map<DepSpec, ImmutableList<ModuleKey>> results = new LinkedHashMap<>();
+ for (InterimModule module : depGraph.values()) {
+ for (DepSpec depSpec : module.getDeps().values()) {
+ results.computeIfAbsent(
+ depSpec,
+ ds ->
+ computePossibleResolutionResultsForOneDepSpec(
+ ds, selectionGroups, selectedVersions));
+ }
+ }
+ return ImmutableMap.copyOf(results);
+ }
+
+ /**
+ * Given the possible list of ModuleKeys each DepSpec can resolve to, enumerate through all the
+ * possible resolution strategies. Each strategy assigns each DepSpec to a single ModuleKey out of
+ * its possible list.
+ */
+ private static List<Function<DepSpec, ModuleKey>> enumerateStrategies(
+ ImmutableMap<DepSpec, ImmutableList<ModuleKey>> possibleResolutionResults) {
+ Map<DepSpec, Integer> depSpecToPosition = new HashMap<>();
+ int position = 0;
+ for (DepSpec depSpec : possibleResolutionResults.keySet()) {
+ depSpecToPosition.put(depSpec, position++);
+ }
+ return Lists.transform(
+ Lists.cartesianProduct(possibleResolutionResults.values().asList()),
+ (List<ModuleKey> choices) ->
+ (DepSpec depSpec) -> choices.get(depSpecToPosition.get(depSpec)));
+ // TODO(wyv): There are some strategies that we could eliminate earlier. For example, the
+ // strategy where (foo@1.1, maxCL=3) resolves to foo@2.0 and (foo@1.2, maxCL=3) resolves to
+ // foo@3.0 is obviously not valid. All foo@? should resolve to the same version (assuming no
+ // multiple-version override).
+ }
+
/** Runs module selection (aka version resolution). */
- // TODO: make use of the max_compatibility_level in DepSpec.
public static Result run(
ImmutableMap<ModuleKey, InterimModule> depGraph,
ImmutableMap<String, ModuleOverride> overrides)
@@ -217,47 +319,55 @@
selectedVersions.merge(selectionGroup, key.getVersion(), Comparators::max);
}
- // Build a new dep graph where deps with unselected versions are removed.
- ImmutableMap.Builder<ModuleKey, InterimModule> newDepGraphBuilder =
- new ImmutableMap.Builder<>();
-
- // Also keep a version of the full dep graph with updated deps.
- ImmutableMap.Builder<ModuleKey, InterimModule> unprunedDepGraphBuilder =
- new ImmutableMap.Builder<>();
- for (InterimModule module : depGraph.values()) {
- // Rewrite deps to point to the selected version.
- ModuleKey key = module.getKey();
- InterimModule updatedModule =
- module.withDepSpecsTransformed(
- depSpec ->
- DepSpec.create(
- depSpec.getName(),
- selectedVersions.get(selectionGroups.get(depSpec.toModuleKey())),
- -1));
-
- // Add all updated modules to the un-pruned dep graph.
- unprunedDepGraphBuilder.put(key, updatedModule);
-
- // Remove any dep whose version isn't selected from the resolved graph.
- Version selectedVersion = selectedVersions.get(selectionGroups.get(module.getKey()));
- if (module.getKey().getVersion().equals(selectedVersion)) {
- newDepGraphBuilder.put(key, updatedModule);
+ // Compute the possible list of ModuleKeys that each DepSpec could resolve to.
+ ImmutableMap<DepSpec, ImmutableList<ModuleKey>> possibleResolutionResults =
+ computePossibleResolutionResults(depGraph, selectionGroups, selectedVersions);
+ for (Map.Entry<DepSpec, ImmutableList<ModuleKey>> e : possibleResolutionResults.entrySet()) {
+ if (e.getValue().isEmpty()) {
+ throw ExternalDepsException.withMessage(
+ Code.VERSION_RESOLUTION_ERROR,
+ "Unexpected error: %s has no valid resolution result",
+ e.getKey());
}
}
- ImmutableMap<ModuleKey, InterimModule> newDepGraph = newDepGraphBuilder.buildOrThrow();
- ImmutableMap<ModuleKey, InterimModule> unprunedDepGraph =
- unprunedDepGraphBuilder.buildOrThrow();
- // Further, removes unreferenced modules from the graph. We can find out which modules are
- // referenced by collecting deps transitively from the root.
- // We can also take this opportunity to check that none of the remaining modules conflict with
- // each other (e.g. same module name but different compatibility levels, or not satisfying
- // multiple_version_override).
- ImmutableMap<ModuleKey, InterimModule> prunedDepGraph =
- new DepGraphWalker(newDepGraph, overrides, selectionGroups).walk();
-
- // Return the result containing both the pruned and un-pruned dep graphs
- return Result.create(prunedDepGraph, unprunedDepGraph);
+ // Each DepSpec may resolve to one or more ModuleKeys. We try out every single possible
+ // combination; in other words, we enumerate through the cartesian product of the "possible
+ // resolution result" set for every distinct DepSpec. Each element of this cartesian product is
+ // essentially a mapping from DepSpecs to ModuleKeys; we can call this mapping a "resolution
+ // strategy".
+ //
+ // Given a resolution strategy, we can walk through the graph from the root module, and see if
+ // the strategy yields a valid graph (only containing the nodes reachable from the root). If the
+ // graph is invalid (for example, because there are modules with different compatibility
+ // levels), we try the next resolution strategy. When all strategies are exhausted, we know
+ // there is no way to achieve a valid selection result, so we report the failure from the time
+ // we attempted to walk the graph using the first resolution strategy.
+ DepGraphWalker depGraphWalker = new DepGraphWalker(depGraph, overrides, selectionGroups);
+ ExternalDepsException firstFailure = null;
+ for (Function<DepSpec, ModuleKey> resolutionStrategy :
+ enumerateStrategies(possibleResolutionResults)) {
+ try {
+ ImmutableMap<ModuleKey, InterimModule> prunedDepGraph =
+ depGraphWalker.walk(resolutionStrategy);
+ // If the call above didn't throw, we have a valid graph. Go ahead and produce a result!
+ ImmutableMap<ModuleKey, InterimModule> unprunedDepGraph =
+ ImmutableMap.copyOf(
+ Maps.transformValues(
+ depGraph,
+ module ->
+ module.withDepSpecsTransformed(
+ depSpec -> DepSpec.fromModuleKey(resolutionStrategy.apply(depSpec)))));
+ return Result.create(prunedDepGraph, unprunedDepGraph);
+ } catch (ExternalDepsException e) {
+ if (firstFailure == null) {
+ firstFailure = e;
+ }
+ }
+ }
+ // firstFailure cannot be null, since enumerateStrategies(...) cannot be empty, since no
+ // element of possibleResolutionResults is empty.
+ throw firstFailure;
}
/**
@@ -269,7 +379,6 @@
private final ImmutableMap<ModuleKey, InterimModule> oldDepGraph;
private final ImmutableMap<String, ModuleOverride> overrides;
private final ImmutableMap<ModuleKey, SelectionGroup> selectionGroups;
- private final HashMap<String, ExistingModule> moduleByName;
DepGraphWalker(
ImmutableMap<ModuleKey, InterimModule> oldDepGraph,
@@ -278,14 +387,15 @@
this.oldDepGraph = oldDepGraph;
this.overrides = overrides;
this.selectionGroups = selectionGroups;
- this.moduleByName = new HashMap<>();
}
/**
* Walks the old dep graph and builds a new dep graph containing only deps reachable from the
* root module. The returned map has a guaranteed breadth-first iteration order.
*/
- ImmutableMap<ModuleKey, InterimModule> walk() throws ExternalDepsException {
+ ImmutableMap<ModuleKey, InterimModule> walk(Function<DepSpec, ModuleKey> resolutionStrategy)
+ throws ExternalDepsException {
+ HashMap<String, ExistingModule> moduleByName = new HashMap<>();
ImmutableMap.Builder<ModuleKey, InterimModule> newDepGraph = ImmutableMap.builder();
Set<ModuleKey> known = new HashSet<>();
Queue<ModuleKeyAndDependent> toVisit = new ArrayDeque<>();
@@ -294,8 +404,12 @@
while (!toVisit.isEmpty()) {
ModuleKeyAndDependent moduleKeyAndDependent = toVisit.remove();
ModuleKey key = moduleKeyAndDependent.getModuleKey();
- InterimModule module = oldDepGraph.get(key);
- visit(key, module, moduleKeyAndDependent.getDependent());
+ InterimModule module =
+ oldDepGraph
+ .get(key)
+ .withDepSpecsTransformed(
+ depSpec -> DepSpec.fromModuleKey(resolutionStrategy.apply(depSpec)));
+ visit(key, module, moduleKeyAndDependent.getDependent(), moduleByName);
for (DepSpec depSpec : module.getDeps().values()) {
if (known.add(depSpec.toModuleKey())) {
@@ -307,7 +421,11 @@
return newDepGraph.buildOrThrow();
}
- void visit(ModuleKey key, InterimModule module, @Nullable ModuleKey from)
+ void visit(
+ ModuleKey key,
+ InterimModule module,
+ @Nullable ModuleKey from,
+ HashMap<String, ExistingModule> moduleByName)
throws ExternalDepsException {
ModuleOverride override = overrides.get(key.getName());
if (override instanceof MultipleVersionOverride) {
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 4fd5a56..fcd4913 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
@@ -44,6 +44,14 @@
}
}
+ public static DepSpec createDepSpec(String name, String version, int maxCompatibilityLevel) {
+ try {
+ return DepSpec.create(name, Version.parse(version), maxCompatibilityLevel);
+ } catch (Version.ParseException e) {
+ throw new IllegalArgumentException(e);
+ }
+ }
+
public static Module.Builder buildModule(String name, String version) throws Exception {
return Module.builder()
.setName(name)
@@ -98,12 +106,24 @@
}
@CanIgnoreReturnValue
+ public InterimModuleBuilder addDep(String depRepoName, DepSpec depSpec) {
+ deps.put(depRepoName, depSpec);
+ return this;
+ }
+
+ @CanIgnoreReturnValue
public InterimModuleBuilder addOriginalDep(String depRepoName, ModuleKey key) {
originalDeps.put(depRepoName, DepSpec.fromModuleKey(key));
return this;
}
@CanIgnoreReturnValue
+ public InterimModuleBuilder addOriginalDep(String depRepoName, DepSpec depSpec) {
+ originalDeps.put(depRepoName, depSpec);
+ return this;
+ }
+
+ @CanIgnoreReturnValue
public InterimModuleBuilder setKey(ModuleKey value) {
this.key = value;
this.builder.setKey(value);
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 68c2d83..5cc7c3b 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
@@ -16,6 +16,7 @@
package com.google.devtools.build.lib.bazel.bzlmod;
import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.createDepSpec;
import static com.google.devtools.build.lib.bazel.bzlmod.BzlmodTestUtil.createModuleKey;
import static org.junit.Assert.assertThrows;
@@ -89,6 +90,124 @@
}
@Test
+ public void diamond_withIgnoredNonAffectingMaxCompatibilityLevel() throws Exception {
+ ImmutableMap<ModuleKey, InterimModule> depGraph =
+ ImmutableMap.<ModuleKey, InterimModule>builder()
+ .put(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createDepSpec("ddd", "1.0", 3))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "2.0", 1).buildEntry())
+ .buildOrThrow();
+
+ Selection.Result selectionResult = Selection.run(depGraph, /* overrides= */ ImmutableMap.of());
+ assertThat(selectionResult.getResolvedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createDepSpec("ddd", "1.0", 3))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 1).buildEntry())
+ .inOrder();
+
+ assertThat(selectionResult.getUnprunedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createDepSpec("ddd", "1.0", 3))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 1).buildEntry());
+ }
+
+ @Test
+ public void diamond_withSelectedNonAffectingMaxCompatibilityLevel() throws Exception {
+ ImmutableMap<ModuleKey, InterimModule> depGraph =
+ ImmutableMap.<ModuleKey, InterimModule>builder()
+ .put(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "1.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createDepSpec("ddd", "2.0", 4))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "2.0", 1).buildEntry())
+ .buildOrThrow();
+
+ Selection.Result selectionResult = Selection.run(depGraph, /* overrides= */ ImmutableMap.of());
+ assertThat(selectionResult.getResolvedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createModuleKey("ddd", "1.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_ccc", createDepSpec("ddd", "2.0", 4))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 1).buildEntry())
+ .inOrder();
+
+ assertThat(selectionResult.getUnprunedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createModuleKey("ddd", "1.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_ccc", createDepSpec("ddd", "2.0", 4))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 1).buildEntry());
+ }
+
+ @Test
public void diamond_withFurtherRemoval() throws Exception {
ImmutableMap<ModuleKey, InterimModule> depGraph =
ImmutableMap.<ModuleKey, InterimModule>builder()
@@ -240,7 +359,7 @@
ExternalDepsException e =
assertThrows(
ExternalDepsException.class,
- () -> Selection.run(depGraph, /*overrides=*/ ImmutableMap.of()));
+ () -> Selection.run(depGraph, /* overrides= */ ImmutableMap.of()));
String error = e.getMessage();
assertThat(error).contains("bbb@1.0 depends on ddd@1.0 with compatibility level 1");
assertThat(error).contains("ccc@2.0 depends on ddd@2.0 with compatibility level 2");
@@ -248,6 +367,272 @@
}
@Test
+ public void differentCompatibilityLevelWithMaxCompatibilityLevelIsRejected() throws Exception {
+ ImmutableMap<ModuleKey, InterimModule> depGraph =
+ ImmutableMap.<ModuleKey, InterimModule>builder()
+ .put(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "1.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createDepSpec("ddd", "2.0", 3))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "2.0", 2).buildEntry())
+ .buildOrThrow();
+
+ ExternalDepsException e =
+ assertThrows(
+ ExternalDepsException.class,
+ () -> Selection.run(depGraph, /* overrides= */ ImmutableMap.of()));
+ String error = e.getMessage();
+ assertThat(error).contains("bbb@1.0 depends on ddd@1.0 with compatibility level 1");
+ assertThat(error).contains("ccc@2.0 depends on ddd@2.0 with compatibility level 2");
+ assertThat(error).contains("which is different");
+ }
+
+ @Test
+ public void maxCompatibilityBasedSelection() throws Exception {
+ ImmutableMap<ModuleKey, InterimModule> depGraph =
+ ImmutableMap.<ModuleKey, InterimModule>builder()
+ .put(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createDepSpec("ddd", "1.0", 2))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "2.0", 2).buildEntry())
+ .buildOrThrow();
+
+ Selection.Result selectionResult = Selection.run(depGraph, /* overrides= */ ImmutableMap.of());
+ assertThat(selectionResult.getResolvedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createDepSpec("ddd", "1.0", 2))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 2).buildEntry())
+ .inOrder();
+
+ assertThat(selectionResult.getUnprunedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createDepSpec("ddd", "1.0", 2))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 2).buildEntry());
+ }
+
+ @Test
+ public void maxCompatibilityBasedSelection_sameVersion() throws Exception {
+ ImmutableMap<ModuleKey, InterimModule> depGraph =
+ ImmutableMap.<ModuleKey, InterimModule>builder()
+ .put(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createDepSpec("ddd", "2.0", 3))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "2.0", 2).buildEntry())
+ .buildOrThrow();
+
+ Selection.Result selectionResult = Selection.run(depGraph, /* overrides= */ ImmutableMap.of());
+ assertThat(selectionResult.getResolvedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createDepSpec("ddd", "2.0", 3))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 2).buildEntry())
+ .inOrder();
+
+ assertThat(selectionResult.getUnprunedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createModuleKey("ddd", "2.0"))
+ .addOriginalDep("ddd_from_bbb", createDepSpec("ddd", "2.0", 3))
+ .buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("ddd", "2.0", 2).buildEntry());
+ }
+
+ @Test
+ public void maxCompatibilityBasedSelection_limitedToMax() throws Exception {
+ ImmutableMap<ModuleKey, InterimModule> depGraph =
+ ImmutableMap.<ModuleKey, InterimModule>builder()
+ .put(
+ InterimModuleBuilder.create("aaa", Version.EMPTY)
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb_from_aaa", createModuleKey("bbb", "1.0"))
+ .addDep("ccc_from_aaa", createModuleKey("ccc", "2.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ddd_from_bbb", createDepSpec("ddd", "1.0", 2))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("ccc", "2.0")
+ .addDep("ddd_from_ccc", createModuleKey("ddd", "3.0"))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "1.0", 1).buildEntry())
+ .put(InterimModuleBuilder.create("ddd", "3.0", 3).buildEntry())
+ .buildOrThrow();
+
+ ExternalDepsException e =
+ assertThrows(
+ ExternalDepsException.class,
+ () -> Selection.run(depGraph, /* overrides= */ ImmutableMap.of()));
+ String error = e.getMessage();
+ assertThat(error).contains("bbb@1.0 depends on ddd@1.0 with compatibility level 1");
+ assertThat(error).contains("ccc@2.0 depends on ddd@3.0 with compatibility level 3");
+ assertThat(error).contains("which is different");
+ }
+
+ @Test
+ public void maxCompatibilityBasedSelection_unreferencedNotSelected() throws Exception {
+ // aaa 1.0 -> bbb 1.0 -> ccc 2.0
+ // \-> ccc 1.0 (max_compatibility_level=2)
+ // \-> ddd 1.0 -> bbb 1.1
+ // \-> eee 1.0 -> ccc 1.1
+ ImmutableMap<ModuleKey, InterimModule> depGraph =
+ ImmutableMap.<ModuleKey, InterimModule>builder()
+ .put(
+ InterimModuleBuilder.create("aaa", "1.0")
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb", createModuleKey("bbb", "1.0"))
+ .addDep("ccc", createDepSpec("ccc", "1.0", 2))
+ .addDep("ddd", createModuleKey("ddd", "1.0"))
+ .addDep("eee", createModuleKey("eee", "1.0"))
+ .buildEntry())
+ .put(
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ccc", createModuleKey("ccc", "2.0"))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ccc", "2.0", 2).buildEntry())
+ .put(InterimModuleBuilder.create("ccc", "1.0", 1).buildEntry())
+ .put(
+ InterimModuleBuilder.create("ddd", "1.0")
+ .addDep("bbb", createModuleKey("bbb", "1.1"))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("bbb", "1.1").buildEntry())
+ .put(
+ InterimModuleBuilder.create("eee", "1.0")
+ .addDep("ccc", createModuleKey("ccc", "1.1"))
+ .buildEntry())
+ .put(InterimModuleBuilder.create("ccc", "1.1", 1).buildEntry())
+ .buildOrThrow();
+
+ // After selection, ccc 2.0 is gone, so ccc 1.0 (max_compatibility_level=2) doesn't upgrade to
+ // ccc 2.0, and only upgrades to ccc 1.1
+ // aaa 1.0 -> bbb 1.1
+ // \-> ccc 1.1
+ // \-> ddd 1.0 -> bbb 1.1
+ // \-> eee 1.0 -> ccc 1.1
+ Selection.Result selectionResult = Selection.run(depGraph, /* overrides= */ ImmutableMap.of());
+ assertThat(selectionResult.getResolvedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", "1.0")
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb", createModuleKey("bbb", "1.1"))
+ .addOriginalDep("bbb", createModuleKey("bbb", "1.0"))
+ .addDep("ccc", createModuleKey("ccc", "1.1"))
+ .addOriginalDep("ccc", createDepSpec("ccc", "1.0", 2))
+ .addDep("ddd", createModuleKey("ddd", "1.0"))
+ .addDep("eee", createModuleKey("eee", "1.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.1").buildEntry(),
+ InterimModuleBuilder.create("ccc", "1.1", 1).buildEntry(),
+ InterimModuleBuilder.create("ddd", "1.0")
+ .addDep("bbb", createModuleKey("bbb", "1.1"))
+ .buildEntry(),
+ InterimModuleBuilder.create("eee", "1.0")
+ .addDep("ccc", createModuleKey("ccc", "1.1"))
+ .buildEntry())
+ .inOrder();
+
+ assertThat(selectionResult.getUnprunedDepGraph().entrySet())
+ .containsExactly(
+ InterimModuleBuilder.create("aaa", "1.0")
+ .setKey(ModuleKey.ROOT)
+ .addDep("bbb", createModuleKey("bbb", "1.1"))
+ .addOriginalDep("bbb", createModuleKey("bbb", "1.0"))
+ .addDep("ccc", createModuleKey("ccc", "1.1"))
+ .addOriginalDep("ccc", createDepSpec("ccc", "1.0", 2))
+ .addDep("ddd", createModuleKey("ddd", "1.0"))
+ .addDep("eee", createModuleKey("eee", "1.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.0")
+ .addDep("ccc", createModuleKey("ccc", "2.0"))
+ .buildEntry(),
+ InterimModuleBuilder.create("bbb", "1.1").buildEntry(),
+ InterimModuleBuilder.create("ccc", "1.0", 1).buildEntry(),
+ InterimModuleBuilder.create("ccc", "1.1", 1).buildEntry(),
+ InterimModuleBuilder.create("ccc", "2.0", 2).buildEntry(),
+ InterimModuleBuilder.create("ddd", "1.0")
+ .addDep("bbb", createModuleKey("bbb", "1.1"))
+ .buildEntry(),
+ InterimModuleBuilder.create("eee", "1.0")
+ .addDep("ccc", createModuleKey("ccc", "1.1"))
+ .buildEntry());
+ }
+
+ @Test
public void differentCompatibilityLevelIsOkIfUnreferenced() throws Exception {
// aaa 1.0 -> bbb 1.0 -> ccc 2.0
// \-> ccc 1.0
To view, visit change 217010. To unsubscribe, or for help writing mail filters, visit settings.
Reply all
Reply to author
Forward
0 new messages