From c1a73878ea860e834ed9348c179b879d8e187ca0 Mon Sep 17 00:00:00 2001 From: Massimiliano Culpo Date: Thu, 22 Jun 2023 19:43:08 +0200 Subject: Deduplicate trigger and effect conditions in packages This refactor introduces extra indices for triggers and effect of a condition, so that the corresponding clauses are evaluated once for every condition they apply to. --- lib/spack/spack/solver/asp.py | 64 +++++++++++++++++++++++++++++++++--- lib/spack/spack/solver/concretize.lp | 59 ++++++++++++++++++++------------- 2 files changed, 95 insertions(+), 28 deletions(-) diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py index 0522cfc4fc..5b174904e1 100644 --- a/lib/spack/spack/solver/asp.py +++ b/lib/spack/spack/solver/asp.py @@ -890,6 +890,10 @@ class SpackSolverSetup: # id for dummy variables self._condition_id_counter = itertools.count() + self._trigger_id_counter = itertools.count() + self._trigger_cache = collections.defaultdict(dict) + self._effect_id_counter = itertools.count() + self._effect_cache = collections.defaultdict(dict) # Caches to optimize the setup phase of the solver self.target_specs_cache = None @@ -1152,6 +1156,32 @@ class SpackSolverSetup: self.package_requirement_rules(pkg) + # trigger and effect tables + self.trigger_rules(pkg.name) + self.effect_rules(pkg.name) + + def trigger_rules(self, name): + self.gen.h2("Trigger conditions") + cache = self._trigger_cache[name] + for spec_str, (trigger_id, requirements) in cache.items(): + self.gen.fact(fn.facts(name, fn.trigger_id(trigger_id))) + self.gen.fact(fn.facts(name, fn.trigger_msg(spec_str))) + for predicate in requirements: + self.gen.fact(fn.condition_requirement(trigger_id, *predicate.args)) + self.gen.newline() + cache.clear() + + def effect_rules(self, name): + self.gen.h2("Imposed requirements") + cache = self._effect_cache[name] + for spec_str, (effect_id, requirements) in cache.items(): + self.gen.fact(fn.facts(name, fn.effect_id(effect_id))) + self.gen.fact(fn.facts(name, fn.effect_msg(spec_str))) + for predicate in requirements: + self.gen.fact(fn.imposed_constraint(effect_id, *predicate.args)) + self.gen.newline() + cache.clear() + def variant_rules(self, pkg): for name, entry in sorted(pkg.variants.items()): variant, when = entry @@ -1265,16 +1295,35 @@ class SpackSolverSetup: # Check if we can emit the requirements before updating the condition ID counter. # In this way, if a condition can't be emitted but the exception is handled in the caller, # we won't emit partial facts. - requirements = self.spec_clauses(named_cond, body=True, required_from=name) condition_id = next(self._condition_id_counter) self.gen.fact(fn.facts(named_cond.name, fn.condition(condition_id))) self.gen.fact(fn.condition_reason(condition_id, msg)) - for pred in requirements: - self.gen.fact(fn.condition_requirement(condition_id, *pred.args)) - if imposed_spec: - self.impose(condition_id, imposed_spec, node=node, name=name) + cache = self._trigger_cache[named_cond.name] + if named_cond not in cache: + trigger_id = next(self._trigger_id_counter) + requirements = self.spec_clauses(named_cond, body=True, required_from=name) + cache[named_cond] = (trigger_id, requirements) + trigger_id, requirements = cache[named_cond] + self.gen.fact(fn.facts(named_cond.name, fn.condition_trigger(condition_id, trigger_id))) + + if not imposed_spec: + return condition_id + + cache = self._effect_cache[named_cond.name] + if imposed_spec not in cache: + effect_id = next(self._effect_id_counter) + requirements = self.spec_clauses(imposed_spec, body=False, required_from=name) + if not node: + requirements = list( + filter(lambda x: x.args[0] not in ("node", "virtual_node"), requirements) + ) + cache[imposed_spec] = (effect_id, requirements) + effect_id, requirements = cache[imposed_spec] + self.gen.fact(fn.facts(named_cond.name, fn.condition_effect(condition_id, effect_id))) + + # FIXME: self.gen.fact(fn.imposed_constraint(condition_id, *predicate.args)) return condition_id @@ -1375,6 +1424,8 @@ class SpackSolverSetup: virtual_str, requirements, kind=RequirementKind.VIRTUAL ) self.emit_facts_from_requirement_rules(rules) + self.trigger_rules(virtual_str) + self.effect_rules(virtual_str) def emit_facts_from_requirement_rules(self, rules: List[RequirementRule]): """Generate facts to enforce requirements. @@ -2332,9 +2383,12 @@ class SpackSolverSetup: self.preferred_variants(pkg) self.target_preferences(pkg) + self.gen.h1("Develop specs") # Inject dev_path from environment for ds in dev_specs: self.condition(spack.spec.Spec(ds.name), ds, msg="%s is a develop spec" % ds.name) + self.trigger_rules(ds.name) + self.effect_rules(ds.name) self.gen.h1("Spec Constraints") self.literal_specs(specs) diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp index ad5418b4be..a11cbfee5a 100644 --- a/lib/spack/spack/solver/concretize.lp +++ b/lib/spack/spack/solver/concretize.lp @@ -251,26 +251,28 @@ condition_set(ID, VirtualNode, Type) :- condition_set(ID, PackageNode, Type), pr condition_set(ID, PackageNode) :- condition_set(ID, PackageNode, _). +condition_set(VirtualNode, X) :- provider(PackageNode, VirtualNode), condition_set(PackageNode, X). + condition_packages(ID, A1) :- condition_requirement(ID, _, A1). condition_packages(ID, A1) :- condition_requirement(ID, _, A1, _). condition_packages(ID, A1) :- condition_requirement(ID, _, A1, _, _). condition_packages(ID, A1) :- condition_requirement(ID, _, A1, _, _, _). -node_condition(ID, node(PackageID, Package)) :- facts(Package, condition(ID)), attr("node", node(PackageID, Package)). -node_condition(ID, node(PackageID, Package)) :- facts(Virtual, condition(ID)), provider(node(PackageID, Package), node(_, Virtual)). +trigger_node(ID, node(PackageID, Package), node(PackageID, Package)) :- facts(Package, trigger_id(ID)), attr("node", node(PackageID, Package)). +trigger_node(ID, node(PackageID, Package), node(VirtualID, Virtual)) :- facts(Virtual, trigger_id(ID)), provider(node(PackageID, Package), node(VirtualID, Virtual)). -condition_nodes(ConditionID, PackageNode, node(X, A1)) - :- condition_packages(ConditionID, A1), +condition_nodes(TriggerID, PackageNode, node(X, A1)) + :- condition_packages(TriggerID, A1), condition_set(PackageNode, node(X, A1)), - node_condition(ConditionID, PackageNode). + trigger_node(TriggerID, PackageNode, _). -cannot_hold(ConditionID, PackageNode) - :- condition_packages(ConditionID, A1), - not condition_set(PackageNode, node(_, A1), _), - node_condition(ConditionID, PackageNode). +cannot_hold(TriggerID, PackageNode) + :- condition_packages(TriggerID, A1), + not condition_set(PackageNode, node(_, A1)), + trigger_node(TriggerID, PackageNode, _). -condition_holds(ID, PackageNode) :- - node_condition(ID, PackageNode); +trigger_condition_holds(ID, RequestorNode) :- + trigger_node(ID, PackageNode, RequestorNode); attr(Name, node(X, A1)) : condition_requirement(ID, Name, A1), condition_nodes(ID, PackageNode, node(X, A1)); attr(Name, node(X, A1), A2) : condition_requirement(ID, Name, A1, A2), condition_nodes(ID, PackageNode, node(X, A1)); attr(Name, node(X, A1), A2, A3) : condition_requirement(ID, Name, A1, A2, A3), condition_nodes(ID, PackageNode, node(X, A1)), not special_case(Name); @@ -279,14 +281,21 @@ condition_holds(ID, PackageNode) :- attr("node_flag_source", node(X, A1), A2, node(Y, A3)) : condition_requirement(ID, "node_flag_source", A1, A2, A3), condition_nodes(ID, PackageNode, node(X, A1)), condition_nodes(ID, PackageNode, node(Y, A3)); not cannot_hold(ID, PackageNode). -condition_holds(ID, node(VirtualID, Virtual)) - :- condition_holds(ID, PackageNode), - facts(Virtual, condition(ID)), - provider(PackageNode, node(VirtualID, Virtual)). +condition_holds(ConditionID, node(X, Package)) + :- facts(Package, condition_trigger(ConditionID, TriggerID)), + trigger_condition_holds(TriggerID, node(X, Package)). + +trigger_and_effect(Package, TriggerID, EffectID) + :- facts(Package, condition_trigger(ID, TriggerID)), + facts(Package, condition_effect(ID, EffectID)). % condition_holds(ID, node(ID, Package)) implies all imposed_constraints, unless do_not_impose(ID, node(ID, Package)) % is derived. This allows imposed constraints to be canceled in special cases. -impose(ID, PackageNode) :- condition_holds(ID, PackageNode), node_condition(ID, PackageNode), not do_not_impose(ID, PackageNode). +impose(EffectID, node(X, Package)) + :- trigger_and_effect(Package, TriggerID, EffectID), + trigger_node(TriggerID, _, node(X, Package)), + trigger_condition_holds(TriggerID, node(X, Package)), + not do_not_impose(EffectID, node(X, Package)). imposed_packages(ID, A1) :- imposed_constraint(ID, _, A1). imposed_packages(ID, A1) :- imposed_constraint(ID, _, A1, _). @@ -294,17 +303,20 @@ imposed_packages(ID, A1) :- imposed_constraint(ID, _, A1, _, _). imposed_packages(ID, A1) :- imposed_constraint(ID, _, A1, _, _, _). imposed_packages(ID, A1) :- imposed_constraint(ID, "depends_on", _, A1, _). -imposed_nodes(ConditionID, PackageNode, node(X, A1)) - :- imposed_packages(ConditionID, A1), - condition_set(PackageNode, node(X, A1), _), - node_condition(ConditionID, PackageNode). +imposed_nodes(EffectID, node(NodeID, Package), node(X, A1)) + :- facts(Package, condition_trigger(ID, TriggerID)), + facts(Package, condition_effect(ID, EffectID)), + imposed_packages(EffectID, A1), + condition_set(node(NodeID, Package), node(X, A1)), + trigger_node(TriggerID, _, node(NodeID, Package)). imposed_nodes(ConditionID, PackageNode, node(X, A1)) :- imposed_packages(ConditionID, A1), - condition_set(PackageNode, node(X, A1), _), + condition_set(PackageNode, node(X, A1)), attr("hash", PackageNode, ConditionID). :- imposed_packages(ID, A1), impose(ID, PackageNode), not condition_set(PackageNode, node(_, A1)). +:- imposed_packages(ID, A1), impose(ID, PackageNode), not imposed_nodes(ID, PackageNode, node(_, A1)). % Conditions that hold impose may impose constraints on other specs attr(Name, node(X, A1)) :- impose(ID, PackageNode), imposed_constraint(ID, Name, A1), imposed_nodes(ID, PackageNode, node(X, A1)). @@ -375,10 +387,11 @@ dependency_holds(node(NodeID, Package), Dependency, Type) :- % We cut off dependencies of externals (as we don't really know them). % Don't impose constraints on dependencies that don't exist. -do_not_impose(ID, node(NodeID, Package)) :- +do_not_impose(EffectID, node(NodeID, Package)) :- not dependency_holds(node(NodeID, Package), Dependency, _), attr("node", node(NodeID, Package)), - facts(Package, dependency_condition(ID, Dependency)). + facts(Package, dependency_condition(ID, Dependency)), + facts(Package, condition_effect(ID, EffectID)). % If a dependency holds on a package node, there must be one and only one dependency node satisfying it 1 { attr("depends_on", PackageNode, node(0..Y-1, Dependency), Type) : max_nodes(Dependency, Y) } 1 -- cgit v1.2.3-60-g2f50