Remember previously failed packages when backtracking.

sdk/lib/_internal/pub/test/version_solver_test.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library pub_upgrade_test;
 
 import 'dart:async';
 
 import 'package:unittest/unittest.dart';
 
@@ skipping 762 matching lines @@
     'foo 2.0.1': {},
     'foo 2.0.2': {},
     'foo 2.0.3': {},
     'foo 2.0.4': {}
   }, result: {
     'myapp from root': '0.0.0',
     'a': '1.0.0',
     'foo': '2.0.4'
   }, maxTries: 2);
 
-  // TODO(rnystrom): More tests. In particular:
-  // - Tests that demonstrate backtracking for every case that can cause a
-  //   solution to fail (no versions, disjoint, etc.)
-  // - Tests where there are multiple valid solutions and "best" is possibly
-  //   ambiguous to nail down which order the backtracker tries solutions.
+  // This is a regression test for #18666. It was possible for the solver to
+  // "forget" that a package had previously led to an error. In that case, it
+  // would backtrack over the failed package instead of trying different
+  // versions of it.
+  testResolve("finds solution with less strict constraint", {
+    "myapp 1.0.0": {
+      "a": "any",
+      "c": "any",
+      "d": "any"
+    },
+    "a 2.0.0": {},
+    "a 1.0.0": {},
+    "b 1.0.0": {"a": "1.0.0"},
+    "c 1.0.0": {"b": "any"},
+    "d 2.0.0": {"myapp": "any"},
+    "d 1.0.0": {"myapp": "<1.0.0"}
+  }, result: {
+    'myapp from root': '1.0.0',
+    'a': '1.0.0',
+    'b': '1.0.0',
+    'c': '1.0.0',
+    'd': '2.0.0'
+  }, maxTries: 3);
 }
 
 sdkConstraint() {
   var badVersion = '0.0.0-nope';
   var goodVersion = sdk.version.toString();
 
   testResolve('root matches SDK', {
     'myapp 0.0.0': {'sdk': goodVersion }
   }, result: {
     'myapp from root': '0.0.0'
@@ skipping 657 matching lines @@
   }
 
   var source = "mock1";
   if (match[7] != null) {
     source = match[7];
     if (source == "root") source = null;
   }
 
   return new PackageId(name, source, parsedVersion, description);
 }