Rework rules for provider weights (#25331)

Preferred providers had a non-zero weight because in an earlier formulation of the logic program that was needed to prefer external providers over default providers. With the current formulation for externals this is not needed anymore, so we can give a weight of zero to both default choices and providers that are externals. _Using zero ensures that we don't introduce any drift towards having less providers, which was happening when minimizing positive weights_.

Modifications:

- [x] Default weight for providers starts at 0 (instead of 10, needed before to prefer externals)
- [x] Rules to compute the `provider_weight` have been refactored. There are multiple possible weights for a given `Virtual`. Only one gets selected by the solver (the one that minimizes the objective function).
- [x] `provider_weight` are now accounting for each different `Virtual`. Before there was a single weight per provider, even if the package was providing multiple virtuals.

* Give preferred providers a weight of zero

Preferred providers had a non-zero weight because in an earlier
formulation of the logic program that was needed to prefer
external providers over default providers.

With the current formulation for externals this is not needed anymore,
so we can give a weight of zero to default choices. Using zero
ensures that we don't introduce any drift towards having
less providers, which was happening when minimizing positive weights.

* Simplify how we compute weights for providers

Rewrite rules so that specific events (i.e. being
an external) unlock the possibility to use certain
weights. The weight being considered is then selected
by the minimization process to be the one that gives
the best score.

* Allow providers to have different weights for different virtuals

Before this change we didn't differentiate providers based on
the virtual they provide, which meant that packages providing
more than one virtual had nonetheless a single weight.

With this change there will be a weight per virtual.

7 files changed, 75 insertions, 44 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 35181d69c9..2c0a072548 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -767,7 +767,7 @@ class SpackSolverSetup(object):
 
             for i, provider in enumerate(providers):
                 provider_name = spack.spec.Spec(provider).name
-                func(vspec, provider_name, i + 10)
+                func(vspec, provider_name, i)
 
     def provider_defaults(self):
         self.gen.h2("Default virtual providers")
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 9bc0d42516..0ee2e08a18 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -193,45 +193,37 @@ provides_virtual(Provider, Virtual) :-
 %-----------------------------------------------------------------------------
 % Virtual dependency weights
 %-----------------------------------------------------------------------------
-% give dependents the virtuals they want
-provider_weight(Dependency, 0)
- :- virtual(Virtual), depends_on(Package, Dependency),
-    provider(Dependency, Virtual),
-    external(Dependency).
-
-provider_weight(Dependency, Weight)
- :- virtual(Virtual), depends_on(Package, Dependency),
-    provider(Dependency, Virtual),
-    pkg_provider_preference(Package, Virtual, Dependency, Weight),
-    not external(Dependency).
-
-provider_weight(Dependency, Weight)
- :- virtual(Virtual), depends_on(Package, Dependency),
-    provider(Dependency, Virtual),
-    not pkg_provider_preference(Package, Virtual, Dependency, _),
-    not external(Dependency),
-    default_provider_preference(Virtual, Dependency, Weight).
-
-% if there's no preference for something, it costs 100 to discourage its
-% use with minimization
-provider_weight(Dependency, 100)
- :- virtual(Virtual),
-    provider(Dependency, Virtual),
-    depends_on(Package, Dependency),
-    not external(Dependency),
-    not pkg_provider_preference(Package, Virtual, Dependency, _),
-    not default_provider_preference(Virtual, Dependency, _).
-
-% Do the same for virtual roots
-provider_weight(Package, Weight)
- :- virtual_root(Virtual),
-    provider(Package, Virtual),
-    default_provider_preference(Virtual, Package, Weight).
-
-provider_weight(Package, 100)
- :- virtual_root(Virtual),
-    provider(Package, Virtual),
-    not default_provider_preference(Virtual, Package, _).
+
+% A provider may have different possible weights depending on whether it's an external
+% or not, or on preferences expressed in packages.yaml etc. This rule ensures that
+% we select the weight, among the possible ones, that minimizes the overall objective function.
+1 { provider_weight(Dependency, Virtual, Weight, Reason) :
+    possible_provider_weight(Dependency, Virtual, Weight, Reason) } 1
+ :- provider(Dependency, Virtual).
+
+% Get rid or the reason for enabling the possible weight (useful for debugging)
+provider_weight(Dependency, Virtual, Weight) :- provider_weight(Dependency, Virtual, Weight, _).
+
+% A provider that is an external can use a weight of 0
+possible_provider_weight(Dependency, Virtual, 0, "external")
+  :- provider(Dependency, Virtual),
+     external(Dependency).
+
+% A provider mentioned in packages.yaml can use a weight
+% according to its priority in the list of providers
+possible_provider_weight(Dependency, Virtual, Weight, "packages_yaml")
+  :- provider(Dependency, Virtual),
+     depends_on(Package, Dependency),
+     pkg_provider_preference(Package, Virtual, Dependency, Weight).
+
+% A provider mentioned in the default configuration can use a weight
+% according to its priority in the list of providers
+possible_provider_weight(Dependency, Virtual, Weight, "default")
+  :- provider(Dependency, Virtual),
+     default_provider_preference(Virtual, Dependency, Weight).
+
+% Any provider can use 100 as a weight, which is very high and discourage its use
+possible_provider_weight(Dependency, Virtual, 100, "fallback") :- provider(Dependency, Virtual).
 
 #defined possible_provider/2.
 #defined provider_condition/3.
@@ -747,8 +739,8 @@ opt_criterion(13, "multi-valued variants").
 opt_criterion(12, "preferred providers for roots").
 #minimize{ 0@12 : #true }.
 #minimize{
-    Weight@12,Provider
-    : provider_weight(Provider, Weight), root(Provider)
+    Weight@12,Provider,Virtual
+    : provider_weight(Provider, Virtual, Weight), root(Provider)
 }.
 
 % Try to use default variants or variants that have been set
@@ -764,8 +756,8 @@ opt_criterion(11, "number of non-default variants (non-roots)").
 opt_criterion(9, "preferred providers (non-roots)").
 #minimize{ 0@9 : #true }.
 #minimize{
-    Weight@9,Provider
-    : provider_weight(Provider, Weight), not root(Provider)
+    Weight@9,Provider,Virtual
+    : provider_weight(Provider, Virtual, Weight), not root(Provider)
 }.
 
 % Try to minimize the number of compiler mismatches in the DAG.
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 757fdc2706..0becb4d55b 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -1260,3 +1260,17 @@ class TestConcretize(object):
         s = spack.spec.Spec('unsat-virtual-dependency')
         with pytest.raises((RuntimeError, spack.error.UnsatisfiableSpecError)):
             s.concretize()
+
+    @pytest.mark.regression('23951')
+    def test_newer_dependency_adds_a_transitive_virtual(self):
+        # Ensure that a package doesn't concretize any of its transitive
+        # dependencies to an old version because newer versions pull in
+        # a new virtual dependency. The possible concretizations here are:
+        #
+        # root@1.0 <- middle@1.0 <- leaf@2.0 <- blas
+        # root@1.0 <- middle@1.0 <- leaf@1.0
+        #
+        # and "blas" is pulled in only by newer versions of "leaf"
+        s = spack.spec.Spec('root-adds-virtual').concretized()
+        assert s['leaf-adds-virtual'].satisfies('@2.0')
+        assert 'blas' in s
diff --git a/lib/spack/spack/test/data/config/packages.yaml b/lib/spack/spack/test/data/config/packages.yaml
index 496c3623cc..b2c3a33b42 100644
--- a/lib/spack/spack/test/data/config/packages.yaml
+++ b/lib/spack/spack/test/data/config/packages.yaml
@@ -2,6 +2,7 @@ packages:
   all:
     providers:
       mpi: [openmpi, mpich]
+      blas: [openblas]
   externaltool:
     buildable: False
     externals:
diff --git a/var/spack/repos/builtin.mock/packages/leaf-adds-virtual/package.py b/var/spack/repos/builtin.mock/packages/leaf-adds-virtual/package.py
new file mode 100644
index 0000000000..be4cc17711
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/leaf-adds-virtual/package.py
@@ -0,0 +1,9 @@
+# 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 LeafAddsVirtual(Package):
+    version('2.0', sha256='abcde')
+    version('1.0', sha256='abcde')
+
+    depends_on('blas', when='@2.0')
diff --git a/var/spack/repos/builtin.mock/packages/middle-adds-virtual/package.py b/var/spack/repos/builtin.mock/packages/middle-adds-virtual/package.py
new file mode 100644
index 0000000000..884d8737c0
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/middle-adds-virtual/package.py
@@ -0,0 +1,7 @@
+# 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 MiddleAddsVirtual(Package):
+    version('1.0', sha256='abcde')
+    depends_on('leaf-adds-virtual')
diff --git a/var/spack/repos/builtin.mock/packages/root-adds-virtual/package.py b/var/spack/repos/builtin.mock/packages/root-adds-virtual/package.py
new file mode 100644
index 0000000000..167a81ca67
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/root-adds-virtual/package.py
@@ -0,0 +1,8 @@
+# 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 RootAddsVirtual(Package):
+    version('1.0', sha256='abcde')
+
+    depends_on('middle-adds-virtual')