summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
authorMassimiliano Culpo <massimiliano.culpo@gmail.com>2023-07-04 11:57:14 +0200
committerTodd Gamblin <tgamblin@llnl.gov>2023-08-15 15:54:37 -0700
commit1de5117ef10ecb391e7d93316c21f8792bcc6b41 (patch)
tree0808a0a9b1099f75adf5f9498869c21feac508c1 /lib
parentcf8f44ae5aef5b6e751ddf9f99e44712f7781de1 (diff)
downloadspack-1de5117ef10ecb391e7d93316c21f8792bcc6b41.tar.gz
spack-1de5117ef10ecb391e7d93316c21f8792bcc6b41.tar.bz2
spack-1de5117ef10ecb391e7d93316c21f8792bcc6b41.tar.xz
spack-1de5117ef10ecb391e7d93316c21f8792bcc6b41.zip
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.
Diffstat (limited to 'lib')
-rw-r--r--lib/spack/spack/solver/asp.py54
-rw-r--r--lib/spack/spack/solver/cycle_detection.lp8
-rw-r--r--lib/spack/spack/test/concretize.py20
3 files changed, 54 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")