Enforce uniqueness of the version_weight atom per node

fixes #22565

This change enforces the uniqueness of the version_weight
atom per node(Package) in the DAG. It does so by applying
FTSE and adding an extra layer of indirection with the
possible_version_weight/2 atom.

Before this change it may have happened that for the same
node two different version_weight/2 were in the answer set,
each of which referred to a different spec with the same
version, and their weights would sum up.

This lead to unexpected result like preferring to build a
new version of an external if the external version was
older.

4 files changed, 32 insertions, 7 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 020e1620a6..179dff2052 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -393,6 +393,8 @@ class SpackSolverSetup(object):
     def __init__(self):
         self.gen = None  # set by setup()
         self.possible_versions = {}
+        self.versions_in_package_py = {}
+        self.versions_from_externals = {}
         self.possible_virtuals = None
         self.possible_compilers = []
         self.variant_values_from_specs = set()
@@ -446,9 +448,18 @@ class SpackSolverSetup(object):
             #    c) Numeric or string comparison
             v)
 
-        most_to_least_preferred = sorted(
-            self.possible_versions[pkg.name], key=keyfn, reverse=True
-        )
+        # Compute which versions appear only in packages.yaml
+        from_externals = self.versions_from_externals[pkg.name]
+        from_package_py = self.versions_in_package_py[pkg.name]
+        only_from_externals = from_externals - from_package_py
+
+        # These versions don't need a default weight, as they are
+        # already weighted in a more favorable way when accounting
+        # for externals. Assigning them a default weight would be
+        # equivalent to state that they are also declared in
+        # the package.py file
+        considered = self.possible_versions[pkg.name] - only_from_externals
+        most_to_least_preferred = sorted(considered, key=keyfn, reverse=True)
 
         for i, v in enumerate(most_to_least_preferred):
             self.gen.fact(fn.version_declared(pkg.name, v, i))
@@ -780,6 +791,7 @@ class SpackSolverSetup(object):
                 self.gen.fact(
                     fn.possible_external(condition_id, pkg_name, local_idx)
                 )
+                self.versions_from_externals[spec.name].add(spec.version)
                 self.possible_versions[spec.name].add(spec.version)
                 self.gen.newline()
 
@@ -988,11 +1000,14 @@ class SpackSolverSetup(object):
 
     def build_version_dict(self, possible_pkgs, specs):
         """Declare any versions in specs not declared in packages."""
-        self.possible_versions = collections.defaultdict(lambda: set())
+        self.possible_versions = collections.defaultdict(set)
+        self.versions_in_package_py = collections.defaultdict(set)
+        self.versions_from_externals = collections.defaultdict(set)
 
         for pkg_name in possible_pkgs:
             pkg = spack.repo.get(pkg_name)
             for v in pkg.versions:
+                self.versions_in_package_py[pkg_name].add(v)
                 self.possible_versions[pkg_name].add(v)
 
         for spec in specs:
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 6ef9deef12..8fdc0acb77 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -19,13 +19,15 @@ version_declared(Package, Version) :- version_declared(Package, Version, _).
 1 { version(Package, Version) : version_declared(Package, Version) } 1
  :- node(Package).
 
-version_weight(Package, Weight)
+possible_version_weight(Package, Weight)
  :- version(Package, Version), version_declared(Package, Version, Weight),
     not preferred_version_declared(Package, Version, _).
 
-version_weight(Package, Weight)
+possible_version_weight(Package, Weight)
   :- version(Package, Version), preferred_version_declared(Package, Version, Weight).
 
+1 { version_weight(Package, Weight) : possible_version_weight(Package, Weight) } 1 :- node(Package).
+
 % version_satisfies implies that exactly one of the satisfying versions
 % is the package's version, and vice versa.
 1 { version(Package, Version) : version_satisfies(Package, Constraint, Version) } 1
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 8636be75e7..9070f8bb67 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -1088,6 +1088,9 @@ class TestConcretize(object):
         # having an additional dependency, but the dependency shouldn't
         # appear in the answer set
         ('external-buildable-with-variant@0.9 +baz', True, '@0.9'),
+        # This package has an external version declared that would be
+        # the least preferred if Spack had to build it
+        ('old-external', True, '@1.0.0'),
     ])
     def test_external_package_versions(self, spec_str, is_external, expected):
         s = Spec(spec_str).concretized()
diff --git a/lib/spack/spack/test/data/config/packages.yaml b/lib/spack/spack/test/data/config/packages.yaml
index 83f8cf1bb3..6ad8200837 100644
--- a/lib/spack/spack/test/data/config/packages.yaml
+++ b/lib/spack/spack/test/data/config/packages.yaml
@@ -35,4 +35,9 @@ packages:
       - spec: external-buildable-with-variant@1.1.special +baz
         prefix: /usr
       - spec: external-buildable-with-variant@0.9 +baz
-        prefix: /usr
\ No newline at end of file
+        prefix: /usr
+  'old-external':
+    buildable: True
+    externals:
+      - spec: old-external@1.0.0
+        prefix: /usr