Make cycle detection optional, to speed-up grounding and solving

3 files changed, 35 insertions, 11 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 5b174904e1..f7bf939d32 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -781,6 +781,9 @@ 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
@@ -903,6 +906,7 @@ 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
@@ -2797,10 +2801,17 @@ class SpecBuilder:
         # fix flags after all specs are constructed
         self.reorder_flags()
 
+        # cycle detection
+        try:
+            roots = [spec.root for spec in self._specs.values() if not spec.root.installed]
+        except RecursionError as e:
+            raise CycleDetectedError(
+                "detected cycles using a fast solve, falling back to slower algorithm"
+            ) from e
+
         # inject patches -- note that we' can't use set() to unique the
         # roots here, because the specs aren't complete, and the hash
         # function will loop forever.
-        roots = [spec.root for spec in self._specs.values() if not spec.root.installed]
         roots = dict((id(r), r) for r in roots)
         for root in roots.values():
             spack.spec.Spec.inject_patches_variant(root)
@@ -2932,7 +2943,12 @@ 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)
-        result, _, _ = self.driver.solve(setup, specs, reuse=reusable_specs, output=output)
+        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)
         return result
 
     def solve_in_rounds(self, specs, out=None, timers=False, stats=False, tests=False):
@@ -3012,3 +3028,7 @@ 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/concretize.lp b/lib/spack/spack/solver/concretize.lp
index a11cbfee5a..8eedc72823 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -407,15 +407,6 @@ error(10, "'{0}' is not a valid dependency for any package in the DAG", Package)
   :- attr("node", node(ID, Package)),
      not needed(node(ID, Package)).
 
-% Avoid cycles in the DAG
-% some combinations of conditional dependencies can result in cycles;
-% this ensures that we solve around them
-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).
-
 #defined dependency_type/2.
 
 %-----------------------------------------------------------------------------
diff --git a/lib/spack/spack/solver/cycle_detection.lp b/lib/spack/spack/solver/cycle_detection.lp
new file mode 100644
index 0000000000..c1be8d7011
--- /dev/null
+++ b/lib/spack/spack/solver/cycle_detection.lp
@@ -0,0 +1,13 @@
+% 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)
+
+% Avoid cycles in the DAG
+% some combinations of conditional dependencies can result in cycles;
+% this ensures that we solve around them
+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).