Improve handling of cases with cycles

To avoid paying the cost of setup and of a full grounding again,
move cycle detection into a separate program and check first if
the solution has cycles.

If it has, ground only the integrity constraint preventing cycles
and solve again.

5 files changed, 88 insertions, 28 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 5bc9df5d6d..e8717c9e38 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -8,6 +8,7 @@ import copy
 import enum
 import itertools
 import os
+import pathlib
 import pprint
 import re
 import types
@@ -790,9 +791,6 @@ class PyclingoDriver:
         self.control.load(os.path.join(parent_dir, "display.lp"))
         if not setup.concretize_everything:
             self.control.load(os.path.join(parent_dir, "when_possible.lp"))
-
-        if setup.use_cycle_detection:
-            self.control.load(os.path.join(parent_dir, "cycle_detection.lp"))
         timer.stop("load")
 
         # Grounding is the first step in the solve -- it turns our facts
@@ -820,6 +818,14 @@ class PyclingoDriver:
 
         timer.start("solve")
         solve_result = self.control.solve(**solve_kwargs)
+
+        if solve_result.satisfiable and self._model_has_cycles(models):
+            warnings.warn(f"cycles detected, falling back to slower algorithm [specs={specs}]")
+            self.control.load(os.path.join(parent_dir, "cycle_detection.lp"))
+            self.control.ground([("no_cycle", [])])
+            models.clear()
+            solve_result = self.control.solve(**solve_kwargs)
+
         timer.stop("solve")
 
         # once done, construct the solve result
@@ -872,6 +878,26 @@ class PyclingoDriver:
 
         return result, timer, self.control.statistics
 
+    def _model_has_cycles(self, models):
+        """Returns true if the best model has cycles in it"""
+        cycle_detection = clingo.Control()
+        parent_dir = pathlib.Path(__file__).parent
+        lp_file = parent_dir / "cycle_detection.lp"
+
+        min_cost, best_model = min(models)
+        with cycle_detection.backend() as backend:
+            for atom in best_model:
+                if atom.name == "attr" and str(atom.arguments[0]) == '"depends_on"':
+                    symbol = fn.depends_on(atom.arguments[1], atom.arguments[2])
+                    atom_id = backend.add_atom(symbol.symbol())
+                    backend.add_rule([atom_id], [], choice=False)
+
+            cycle_detection.load(str(lp_file))
+            cycle_detection.ground([("base", []), ("no_cycle", [])])
+            cycle_result = cycle_detection.solve()
+
+        return cycle_result.unsatisfiable
+
 
 class SpackSolverSetup:
     """Class to set up and run a Spack concretization solve."""
@@ -915,7 +941,6 @@ class SpackSolverSetup:
 
         # If False allows for input specs that are not solved
         self.concretize_everything = True
-        self.use_cycle_detection = False
 
         # Set during the call to setup
         self.pkgs = None
@@ -2741,7 +2766,7 @@ class SpecBuilder:
         else:
             return (-1, 0)
 
-    def _build_specs(self, function_tuples):
+    def build_specs(self, function_tuples):
         # Functions don't seem to be in particular order in output.  Sort
         # them here so that directives that build objects (like node and
         # node_compiler) are called in the right order.
@@ -2831,14 +2856,6 @@ class SpecBuilder:
 
         return self._specs
 
-    def build_specs(self, function_tuples):
-        try:
-            return self._build_specs(function_tuples)
-        except RecursionError as e:
-            raise CycleDetectedError(
-                "detected cycles using a fast solve, falling back to slower algorithm"
-            ) from e
-
 
 def _develop_specs_from_env(spec, env):
     dev_info = env.dev_specs.get(spec.name, {}) if env else {}
@@ -2940,12 +2957,7 @@ class Solver:
         reusable_specs.extend(self._reusable_specs(specs))
         setup = SpackSolverSetup(tests=tests)
         output = OutputConfiguration(timers=timers, stats=stats, out=out, setup_only=setup_only)
-        try:
-            result, _, _ = self.driver.solve(setup, specs, reuse=reusable_specs, output=output)
-        except CycleDetectedError as e:
-            warnings.warn(e)
-            setup.use_cycle_detection = True
-            result, _, _ = self.driver.solve(setup, specs, reuse=reusable_specs, output=output)
+        result, _, _ = self.driver.solve(setup, specs, reuse=reusable_specs, output=output)
         return result
 
     def solve_in_rounds(self, specs, out=None, timers=False, stats=False, tests=False):
@@ -3025,7 +3037,3 @@ class InternalConcretizerError(spack.error.UnsatisfiableSpecError):
         # Add attribute expected of the superclass interface
         self.required = None
         self.constraint_type = None
-
-
-class CycleDetectedError(spack.error.SpackError):
-    pass
diff --git a/lib/spack/spack/solver/cycle_detection.lp b/lib/spack/spack/solver/cycle_detection.lp
index c1be8d7011..b148591760 100644
--- a/lib/spack/spack/solver/cycle_detection.lp
+++ b/lib/spack/spack/solver/cycle_detection.lp
@@ -6,8 +6,10 @@
 % Avoid cycles in the DAG
 % some combinations of conditional dependencies can result in cycles;
 % this ensures that we solve around them
+
+#program no_cycle.
 path(Parent, Child) :- depends_on(Parent, Child).
 path(Parent, Descendant) :- path(Parent, A), depends_on(A, Descendant).
-error(100, "Cyclic dependency detected between '{0}' and '{1}' (consider changing variants to avoid the cycle)", A, B)
-  :- path(A, B),
-     path(B, A).
+:- path(A, A).
+
+#defined depends_on/2.
diff --git a/lib/spack/spack/test/concretize.py b/lib/spack/spack/test/concretize.py
index 415262085b..c272c6bddc 100644
--- a/lib/spack/spack/test/concretize.py
+++ b/lib/spack/spack/test/concretize.py
@@ -2209,7 +2209,7 @@ class TestConcretizeSeparately:
         o gmake@4.1
 
         """
-        spack.config.config.set("concretizer:duplicates:strategy", strategy)
+        spack.config.CONFIG.set("concretizer:duplicates:strategy", strategy)
         s = Spec("hdf5").concretized()
 
         # Check that hdf5 depends on gmake@=4.1
@@ -2245,7 +2245,7 @@ class TestConcretizeSeparately:
         o gmake@4.1
 
         """
-        spack.config.config.set("concretizer:duplicates:strategy", strategy)
+        spack.config.CONFIG.set("concretizer:duplicates:strategy", strategy)
         s = Spec("py-shapely").concretized()
         # Requirements on py-shapely
         setuptools = s["py-shapely"].dependencies(name="py-setuptools", deptype="build")
@@ -2260,3 +2260,19 @@ class TestConcretizeSeparately:
         # Requirements on python
         gmake = s["python"].dependencies(name="gmake", deptype="build")
         assert len(gmake) == 1 and gmake[0].satisfies("@=3.0")
+
+    @pytest.mark.skipif(
+        os.environ.get("SPACK_TEST_SOLVER") == "original",
+        reason="Not supported by the original concretizer",
+    )
+    def test_solution_without_cycles(self):
+        """Tests that when we concretize a spec with cycles, a fallback kicks in to recompute
+        a solution without cycles.
+        """
+        s = Spec("cycle-a").concretized()
+        assert s["cycle-a"].satisfies("+cycle")
+        assert s["cycle-b"].satisfies("~cycle")
+
+        s = Spec("cycle-b").concretized()
+        assert s["cycle-a"].satisfies("~cycle")
+        assert s["cycle-b"].satisfies("+cycle")
diff --git a/var/spack/repos/duplicates.test/packages/cycle-a/package.py b/var/spack/repos/duplicates.test/packages/cycle-a/package.py
new file mode 100644
index 0000000000..207f5aac44
--- /dev/null
+++ b/var/spack/repos/duplicates.test/packages/cycle-a/package.py
@@ -0,0 +1,17 @@
+# 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 CycleA(Package):
+    """Package that would lead to cycles if default variant values are used"""
+
+    homepage = "http://www.example.com"
+    url = "http://www.example.com/tdep-1.0.tar.gz"
+
+    version("2.0", md5="0123456789abcdef0123456789abcdef")
+
+    variant("cycle", default=True, description="activate cycles")
+    depends_on("cycle-b", when="+cycle")
diff --git a/var/spack/repos/duplicates.test/packages/cycle-b/package.py b/var/spack/repos/duplicates.test/packages/cycle-b/package.py
new file mode 100644
index 0000000000..ef190a5649
--- /dev/null
+++ b/var/spack/repos/duplicates.test/packages/cycle-b/package.py
@@ -0,0 +1,17 @@
+# 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 CycleB(Package):
+    """Package that would lead to cycles if default variant values are used"""
+
+    homepage = "http://www.example.com"
+    url = "http://www.example.com/tdep-1.0.tar.gz"
+
+    version("2.0", md5="0123456789abcdef0123456789abcdef")
+
+    variant("cycle", default=True, description="activate cycles")
+    depends_on("cycle-a", when="+cycle")