From a410b220980ac136cd90f55c64b8dbea7561d484 Mon Sep 17 00:00:00 2001 From: Massimiliano Culpo Date: Fri, 23 Jun 2023 10:42:04 +0200 Subject: Make cycle detection optional, to speed-up grounding and solving --- lib/spack/spack/solver/asp.py | 24 ++++++++++++++++++++++-- lib/spack/spack/solver/concretize.lp | 9 --------- lib/spack/spack/solver/cycle_detection.lp | 13 +++++++++++++ 3 files changed, 35 insertions(+), 11 deletions(-) create mode 100644 lib/spack/spack/solver/cycle_detection.lp 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). -- cgit v1.2.3-60-g2f50