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, 43 insertions, 6 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 15994b01ea..9ccbbaf9b1 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()
 
@@ -987,11 +999,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 9e66760695..ee69e9798f 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -14,13 +14,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 f5294ae596..437edcb99f 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -1060,6 +1060,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/var/spack/repos/builtin.mock/packages/old-external/package.py b/var/spack/repos/builtin.mock/packages/old-external/package.py
new file mode 100644
index 0000000000..cf414195a2
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/old-external/package.py
@@ -0,0 +1,17 @@
+# Copyright 2013-2021 Lawrence Livermore National Security, LLC and other
+# Spack Project Developers. See the top-level COPYRIGHT file for details.
+#
+# SPDX-License-Identifier: (Apache-2.0 OR MIT)
+class OldExternal(Package):
+    """A package that has an old version declared in packages.yaml"""
+
+    homepage = "https://www.example.com"
+    url = "https://www.example.com/old-external.tar.gz"
+
+    version('1.2.0', '0123456789abcdef0123456789abcdef')
+    version('1.1.4', '0123456789abcdef0123456789abcdef')
+    version('1.1.3', '0123456789abcdef0123456789abcdef')
+    version('1.1.2', '0123456789abcdef0123456789abcdef')
+    version('1.1.1', '0123456789abcdef0123456789abcdef')
+    version('1.1.0', '0123456789abcdef0123456789abcdef')
+    version('1.0.0', '0123456789abcdef0123456789abcdef')