Avoid O(2^N) complexity when reformating an incompatibility-tree of depth N. (#2615)
For incompatibilities with a `ConflictCause` the `reformatRanges` called itself
on each branch `ConflictCause.conflict` and `ConflictCause.other`.
Then it also `_reformatCause` which again calls `reformatRanges` for
each branch of a `ConflictCause`.
This means `reformatRanges` was called 2^N times for any node at depth N
in an `Incompatibility`-tree. Hence, a degenerate incompatibility tree
could effective cause `pub get` to hang, instead of printing an error
signaling a resolution conflict.
This bug has not affected `pub get` invocations where a resolution was
possible.
diff --git a/lib/src/solver/reformat_ranges.dart b/lib/src/solver/reformat_ranges.dart
index 76711c4..8b46c30 100644
--- a/lib/src/solver/reformat_ranges.dart
+++ b/lib/src/solver/reformat_ranges.dart
@@ -25,21 +25,16 @@
/// the release version (`<2.0.0`) if no pre-releases exist or with an inclusive
/// bound on the last pre-release version that actually exists
/// (`<=2.0.0-dev.1`).
-Incompatibility reformatRanges(Map<PackageRef, PackageLister> packageListers,
- Incompatibility incompatibility) {
- var cause = incompatibility.cause;
- if (cause is ConflictCause) {
- var conflict = cause as ConflictCause;
- cause = ConflictCause(reformatRanges(packageListers, conflict.conflict),
- reformatRanges(packageListers, conflict.other));
- }
-
- return Incompatibility(
+Incompatibility reformatRanges(
+ Map<PackageRef, PackageLister> packageListers,
+ Incompatibility incompatibility,
+) =>
+ Incompatibility(
incompatibility.terms
.map((term) => _reformatTerm(packageListers, term))
.toList(),
- _reformatCause(packageListers, cause));
-}
+ _reformatCause(packageListers, incompatibility.cause),
+ );
/// Returns [term] with the upper and lower bounds of its package range
/// reformatted if necessary.
