Construct unification sets on demand, improve heuristic

4 files changed, 81 insertions, 31 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index f7bf939d32..61ef17f64d 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -1547,6 +1547,8 @@ class SpackSolverSetup:
                 self.possible_versions[spec.name].add(spec.version)
                 self.gen.newline()
 
+            self.trigger_rules(pkg_name)
+
     def preferred_variants(self, pkg_name):
         """Facts on concretization preferences, as read from packages.yaml"""
         preferences = spack.package_prefs.PackagePrefs
@@ -2347,11 +2349,23 @@ class SpackSolverSetup:
             for reusable_spec in reuse:
                 self._facts_from_concrete_spec(reusable_spec, possible)
 
-        self.gen.h1("Maximum number of nodes")
-        counter = collections.Counter(list(link_run) + list(total_build))
-        for pkg, count in sorted(counter.items()):
-            # FIXME (multiple nodes): should be count
-            self.gen.fact(fn.max_nodes(pkg, 1))
+        self.gen.h1("Generic statements on possible packages")
+        counter = collections.Counter(list(link_run) + list(total_build) + list(set(direct_build)))
+        self.gen.h2("Maximum number of nodes")
+        for pkg, count in sorted(counter.items(), key=lambda x: (x[1], x[0])):
+            count = min(count, 1)
+            self.gen.fact(fn.max_nodes(pkg, count))
+        self.gen.newline()
+
+        self.gen.h2("Build unification sets ")
+        for name in spack.repo.path.packages_with_tags("build-tools"):
+            self.gen.fact(fn.multiple_unification_sets(name))
+        self.gen.newline()
+
+        self.gen.h2("Possible package in link-run subDAG")
+        for name in sorted(link_run):
+            self.gen.fact(fn.possible_in_link_run(name))
+        self.gen.newline()
 
         self.gen.h1("Possible flags on nodes")
         for flag in spack.spec.FlagMap.valid_compiler_flags():
@@ -2747,7 +2761,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.
@@ -2802,12 +2816,7 @@ class SpecBuilder:
         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
+        roots = [spec.root for spec in self._specs.values() if not spec.root.installed]
 
         # inject patches -- note that we' can't use set() to unique the
         # roots here, because the specs aren't complete, and the hash
@@ -2842,6 +2851,14 @@ 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 {}
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 4f6ac55c0a..f810abc592 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -54,16 +54,36 @@ unify(SetID, PackageName) :- unification_set(SetID, node(_, PackageName)).
 
 unification_set("root", PackageNode) :- attr("root", PackageNode).
 unification_set(SetID, ChildNode) :- attr("depends_on", ParentNode, ChildNode, Type), Type != "build", unification_set(SetID, ParentNode).
-unification_set("build", ChildNode) :- attr("depends_on", ParentNode, ChildNode, Type), Type == "build", unification_set("root", ParentNode).
+
+unification_set(("build", node(X, Child)), node(X, Child))
+  :- attr("depends_on", ParentNode, node(X, Child), Type),
+     Type == "build",
+     multiple_unification_sets(Child),
+     unification_set("root", ParentNode).
+
+unification_set("generic_build", node(X, Child))
+  :- attr("depends_on", ParentNode, node(X, Child), Type),
+     Type == "build",
+     not multiple_unification_sets(Child),
+     unification_set("root", ParentNode).
+
+% Any dependency of type "build" in a unification set that is not "root", stays in that unification set
 unification_set(SetID, ChildNode) :- attr("depends_on", ParentNode, ChildNode, Type), Type == "build", SetID != "root", unification_set(SetID, ParentNode).
 unification_set(SetID, VirtualNode) :- provider(PackageNode, VirtualNode), unification_set(SetID, PackageNode).
 
+#defined multiple_unification_sets/1.
+
 %----
 % Rules to break symmetry and speed-up searches
 %----
 
 % In the "root" unification set only ID = 0 are allowed
 :- unification_set("root", node(ID, _)), ID != 0.
+
+% In the "root" unification set we allow only packages from the link-run possible subDAG
+:- unification_set("root", node(_, Package)), not possible_in_link_run(Package), not virtual(Package).
+
+% Each node must belong to at least one unification set
 :- attr("node", PackageNode), not unification_set(_, PackageNode).
 
 % Cannot have a node with an ID, if lower ID of the same package are not used
@@ -114,10 +134,10 @@ error(100, no_value_error, Attribute, Package)
      not attr(Attribute, node(ID, Package), _).
 
 % Error when multiple attr need to be selected
-error(100, multiple_values_error, Attribute, Package)
-  :- attr("node", node(ID, Package)),
+error(100, multiple_values_error, Attribute, PackageNode)
+  :- attr("node", PackageNode),
      attr_single_value(Attribute),
-     2 { attr(Attribute, node(ID, Package), Value) }.
+     2 { attr(Attribute, PackageNode, Value) }.
 
 %-----------------------------------------------------------------------------
 % Version semantics
@@ -1019,11 +1039,6 @@ error(100, "Cannot select a single compiler for package {0}", PackageNode)
  :- attr("node", PackageNode),
     2 { attr("node_compiler_version", PackageNode, C, V) }.
 
-error(100, "Cannot concretize {0} with two compilers {1} and {2}@{3}", PackageNode, Compiler1, Compiler2, Version)
- :- attr("node_compiler", PackageNode, Compiler1),
-    attr("node_compiler_version", PackageNode, Compiler2, Version),
-    Compiler1 != Compiler2.
-
 % If the compiler of a node cannot be satisfied, raise
 error(10, "No valid compiler for {0} satisfies '%{1}'", PackageNode, Compiler)
   :- attr("node", PackageNode),
diff --git a/lib/spack/spack/solver/heuristic.lp b/lib/spack/spack/solver/heuristic.lp
index cd5d94978f..3993d1ac91 100644
--- a/lib/spack/spack/solver/heuristic.lp
+++ b/lib/spack/spack/solver/heuristic.lp
@@ -11,15 +11,31 @@
 #heuristic attr("node", node(0, Package)) : literal(_, "root", Package). [45, true]
 #heuristic attr("node", node(0, Package)) : literal(_, "node", Package). [45, true]
 
-#heuristic attr("version", node(0, Package), Version) : facts(Package, version_declared(Version, 0)), attr("root", node(0, Package)). [40, true]
-#heuristic version_weight(node(0, Package), 0) : facts(Package, version_declared(Version, 0)), attr("root", node(0, Package)). [40, true]
-#heuristic attr("variant_value", node(0, Package), Variant, Value) : variant_default_value(Package, Variant, Value), attr("root", node(0, Package)). [40, true]
-#heuristic attr("node_target", node(0, Package), Target) : facts(Package, target_weight(Target, 0)), attr("root", node(0, Package)). [40, true]
-#heuristic node_target_weight(node(0, Package), 0) : attr("root", node(0, Package)). [40, true]
-#heuristic node_compiler(node(0, Package), CompilerID) : default_compiler_preference(ID, 0), compiler_id(ID), attr("root", node(0, Package)). [40, true]
+% Root node
+#heuristic attr("version", node(0, Package), Version) : facts(Package, version_declared(Version, 0)), attr("root", node(0, Package)). [35, true]
+#heuristic version_weight(node(0, Package), 0) : facts(Package, version_declared(Version, 0)), attr("root", node(0, Package)). [35, true]
+#heuristic attr("variant_value", node(0, Package), Variant, Value) : variant_default_value(Package, Variant, Value), attr("root", node(0, Package)). [35, true]
+#heuristic attr("node_target", node(0, Package), Target) : facts(Package, target_weight(Target, 0)), attr("root", node(0, Package)). [35, true]
+#heuristic node_target_weight(node(0, Package), 0) : attr("root", node(0, Package)). [35, true]
+#heuristic node_compiler(node(0, Package), CompilerID) : default_compiler_preference(ID, 0), compiler_id(ID), attr("root", node(0, Package)). [35, true]
 
-#heuristic version_weight(node(0, Package), 0) : attr("node", node(0, Package)). [20, true]
+% Providers
+#heuristic attr("node", node(0, Package)) : default_provider_preference(Virtual, Package, 0), possible_in_link_run(Package). [30, true]
+%#heuristic provider(node(0, Package), node(0, Virtual)) : default_provider_preference(Virtual, Package, 0), possible_in_link_run(Package). [30, true]
+%#heuristic provider_weight(node(0, Package), node(0, Virtual), 0) : default_provider_preference(Virtual, Package, 0), possible_in_link_run(Package). [30, true]
 
-#heuristic attr("node_target", node(0, Package), Target) : facts(Package, target_weight(Target, 0)), attr("node", node(0, Package)). [20, true]
-#heuristic node_target_weight(PackageNode, 0) : attr("node", PackageNode). [20, true]
-#heuristic node_compiler(node(0, Package), ID) : default_compiler_preference(ID, 0), compiler_id(ID), attr("node", node(0, Package)). [15, true]
+% node(ID, _)
+#heuristic attr("version", node(ID, Package), Version) : facts(Package, version_declared(Version, ID)), attr("node", node(ID, Package)). [25-5*ID, true]
+#heuristic version_weight(node(ID, Package), ID) : facts(Package, version_declared(Version, ID)), attr("node", node(ID, Package)). [25-5*ID, true]
+#heuristic attr("variant_value", node(ID, Package), Variant, Value) : variant_default_value(Package, Variant, Value), attr("node", node(ID, Package)). [25-5*ID, true]
+#heuristic attr("node_target", node(ID, Package), Target) : facts(Package, target_weight(Target, ID)), attr("node", node(ID, Package)). [25-5*ID, true]
+#heuristic node_target_weight(node(ID, Package), ID) : attr("node", node(ID, Package)). [25-5*ID, true]
+#heuristic node_compiler(node(ID, Package), CompilerID) : default_compiler_preference(ID, ID), compiler_id(ID), attr("node", node(ID, Package)). [25-5*ID, true]
+
+% node(ID, _), split build dependencies
+#heuristic attr("version", node(ID, Package), Version) : facts(Package, version_declared(Version, ID)), attr("node", node(ID, Package)), multiple_unification_sets(Package). [25, true]
+#heuristic version_weight(node(ID, Package), ID) : facts(Package, version_declared(Version, ID)), attr("node", node(ID, Package)), multiple_unification_sets(Package). [25, true]
+#heuristic attr("variant_value", node(ID, Package), Variant, Value) : variant_default_value(Package, Variant, Value), attr("node", node(ID, Package)), multiple_unification_sets(Package). [25, true]
+#heuristic attr("node_target", node(ID, Package), Target) : facts(Package, target_weight(Target, ID)), attr("node", node(ID, Package)), multiple_unification_sets(Package). [25, true]
+#heuristic node_target_weight(node(ID, Package), ID) : attr("node", node(ID, Package)), multiple_unification_sets(Package). [25, true]
+#heuristic node_compiler(node(ID, Package), CompilerID) : default_compiler_preference(ID, ID), compiler_id(ID), attr("node", node(ID, Package)), multiple_unification_sets(Package). [25, true]
diff --git a/var/spack/repos/builtin/packages/py-setuptools/package.py b/var/spack/repos/builtin/packages/py-setuptools/package.py
index 9df52dbe2c..ea9150e357 100644
--- a/var/spack/repos/builtin/packages/py-setuptools/package.py
+++ b/var/spack/repos/builtin/packages/py-setuptools/package.py
@@ -14,6 +14,8 @@ class PySetuptools(Package, PythonExtension):
     url = "https://files.pythonhosted.org/packages/py3/s/setuptools/setuptools-62.3.2-py3-none-any.whl"
     list_url = "https://pypi.org/simple/setuptools/"
 
+    tags = ["build-tools"]
+
     version(
         "68.0.0",
         sha256="11e52c67415a381d10d6b462ced9cfb97066179f0e871399e006c4ab101fc85f",