ASP-based solver: minimize weights over edges (#40632)

With the introduction of multiple build dependencies from the same package in the DAG, we need to minimize a few weights accounting for edges rather than nodes. If we don't do that we might have multiple "optimal" solutions that differ only in how the same nodes are connected together. This commit ensures optimal versions are picked per parent in case of multiple choices for a dependency.

3 files changed, 74 insertions, 0 deletions

diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index da149dd3fa..efca3bfed2 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -1535,6 +1535,17 @@ opt_criterion(5, "non-preferred targets").
       build_priority(PackageNode, Priority)
 }.
 
+% Choose more recent versions for nodes
+opt_criterion(1, "edge wiring").
+#minimize{ 0@201: #true }.
+#minimize{ 0@1: #true }.
+#minimize{
+    Weight@1,ParentNode,PackageNode
+    : version_weight(PackageNode, Weight),
+      not attr("root", PackageNode),
+      depends_on(ParentNode, PackageNode)
+}.
+
 %-----------
 % Notes
 %-----------
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 48334e70a1..04959a19b3 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -2228,6 +2228,43 @@ class TestConcretizeSeparately:
         s = Spec("virtual-build").concretized()
         assert s["pkgconfig"].name == "pkg-config"
 
+    @pytest.mark.regression("40595")
+    def test_no_multiple_solutions_with_different_edges_same_nodes(self):
+        r"""Tests that the root node, which has a dependency on py-setuptools without constraint,
+        doesn't randomly pick one of the two setuptools (@=59, @=60) needed by its dependency.
+
+        o py-floating@1.25.0/3baitsp
+        |\
+        | |\
+        | | |\
+        | o | | py-shapely@1.25.0/4hep6my
+        |/| | |
+        | |\| |
+        | | |/
+        | |/|
+        | | o py-setuptools@60/cwhbthc
+        | |/
+        |/|
+        | o py-numpy@1.25.0/5q5fx4d
+        |/|
+        | |\
+        | o | py-setuptools@59/jvsa7sd
+        |/ /
+        o | python@3.11.2/pdmjekv
+        o | gmake@3.0/jv7k2bl
+         /
+        o gmake@4.1/uo6ot3d
+        """
+        spec_str = "py-floating"
+
+        root = spack.spec.Spec(spec_str).concretized()
+        assert root["py-shapely"].satisfies("^py-setuptools@=60")
+        assert root["py-numpy"].satisfies("^py-setuptools@=59")
+
+        edges = root.edges_to_dependencies("py-setuptools")
+        assert len(edges) == 1
+        assert edges[0].spec.satisfies("@=60")
+
 
 @pytest.mark.parametrize(
     "v_str,v_opts,checksummed",
diff --git a/var/spack/repos/duplicates.test/packages/py-floating/package.py b/var/spack/repos/duplicates.test/packages/py-floating/package.py
new file mode 100644
index 0000000000..2921b617bd
--- /dev/null
+++ b/var/spack/repos/duplicates.test/packages/py-floating/package.py
@@ -0,0 +1,26 @@
+# Copyright 2013-2023 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)
+from spack.package import *
+
+
+class PyFloating(Package):
+    """An extension that depends on:
+    - py-setuptools without further constraints
+    - py-shapely, which depends on py-setuptools@=60
+    - py-numpy, which depends on py-setuptools@=59
+
+    We need to ensure that by default the root node gets the best version
+    of setuptools it could.
+    """
+
+    homepage = "http://www.example.com"
+    url = "http://www.example.com/tdep-1.0.tar.gz"
+
+    version("1.25.0", md5="0123456789abcdef0123456789abcdef")
+
+    extends("python")
+    depends_on("py-numpy", type=("build", "run"))
+    depends_on("py-shapely", type=("build", "run"))
+    depends_on("py-setuptools", type="build")