solver: use a new heuristic (#46548)

This PR introduces a new heuristic for the solver, which behaves better when
compilers are treated as nodes. Apparently, it performs better also on `develop`,
where compilers are still node attributes.

The new heuristic:
- Sets an initial priority for guessing a few attributes. The order is "nodes" (300), 
  "dependencies" (150), "virtual dependencies" (60), "version" and "variants" (30), and
  "targets" and "compilers" (1). This initial priority decays over time during the solve, and
  falls back to the defaults.

- By default, it considers most guessed facts as "false". For instance, by default a node
  doesn't exist in the optimal answer set, or a version is not picked as a node version etc.

- There are certain conditions that override the default heuristic using the _priority_ of
  a rule, which previously we didn't use. For instance, by default we guess that a
  `attr("variant", Node, Variant, Value)` is false, but if we know that the node is already
  in the answer set, and the value is the default one, then we guess it is true.

Signed-off-by: Massimiliano Culpo <massimiliano.culpo@gmail.com>

1 files changed, 27 insertions, 22 deletions

diff --git a/lib/spack/spack/solver/heuristic.lp b/lib/spack/spack/solver/heuristic.lp
index a5d6767ff2..e5d7de4966 100644
--- a/lib/spack/spack/solver/heuristic.lp
+++ b/lib/spack/spack/solver/heuristic.lp
@@ -7,32 +7,37 @@
 % Heuristic to speed-up solves
 %=============================================================================
 
-% No duplicates by default (most of them will be true)
-#heuristic attr("node",         node(PackageID, Package)). [100, init]
-#heuristic attr("node",         node(PackageID, Package)). [  2, factor]
-#heuristic attr("virtual_node", node(VirtualID, Virtual)). [100, init]
-#heuristic attr("node",         node(1..X-1, Package)) : max_dupes(Package, X), not virtual(Package), X > 1. [-1, sign]
-#heuristic attr("virtual_node", node(1..X-1, Package)) : max_dupes(Package, X), virtual(Package)    , X > 1. [-1, sign]
-
-% Pick preferred version
-#heuristic attr("version", node(PackageID, Package), Version) : pkg_fact(Package, version_declared(Version, Weight)), attr("node", node(PackageID, Package)).             [40, init]
-#heuristic version_weight(node(PackageID, Package), 0)        : pkg_fact(Package, version_declared(Version, 0     )), attr("node", node(PackageID, Package)).             [ 1, sign]
-#heuristic attr("version", node(PackageID, Package), Version) : pkg_fact(Package, version_declared(Version, 0     )), attr("node", node(PackageID, Package)).             [ 1, sign]
-#heuristic attr("version", node(PackageID, Package), Version) : pkg_fact(Package, version_declared(Version, Weight)), attr("node", node(PackageID, Package)), Weight > 0. [-1, sign]
+#heuristic attr("node", PackageNode). [300, init]
+#heuristic attr("node", PackageNode). [  2, factor]
+#heuristic attr("node", PackageNode). [ -1, sign]
+#heuristic attr("node", node(0, Dependency)) : attr("dependency_holds", ParentNode, Dependency, Type), not virtual(Dependency). [1@2, sign]
 
-% Use default variants
-#heuristic attr("variant_value", node(PackageID, Package), Variant, Value) : variant_default_value(Package, Variant, Value),     attr("node", node(PackageID, Package)). [40, true]
-#heuristic attr("variant_value", node(PackageID, Package), Variant, Value) : not variant_default_value(Package, Variant, Value), attr("node", node(PackageID, Package)). [40, false]
+#heuristic attr("virtual_node", node(X, Virtual)). [60, init]
+#heuristic attr("virtual_node", node(X, Virtual)). [-1, sign]
+#heuristic attr("virtual_node", node(0, Virtual)) : node_depends_on_virtual(PackageNode, Virtual). [1@2, sign]
+
+#heuristic attr("depends_on", ParentNode, ChildNode, Type). [150, init]
+#heuristic attr("depends_on", ParentNode, ChildNode, Type). [4,  factor]
+#heuristic attr("depends_on", ParentNode, ChildNode, Type). [-1, sign]
+#heuristic attr("depends_on", ParentNode, node(0, Dependency), Type) : attr("dependency_holds", ParentNode, Dependency, Type), not virtual(Dependency). [1@2, sign]
+#heuristic attr("depends_on", ParentNode, ProviderNode       , Type) : node_depends_on_virtual(ParentNode, Virtual, Type), provider(ProviderNode, node(VirtualID, Virtual)). [1@2, sign]
+
+#heuristic attr("version", node(PackageID, Package), Version). [30, init]
+#heuristic attr("version", node(PackageID, Package), Version). [-1, sign]
+#heuristic attr("version", node(PackageID, Package), Version) : pkg_fact(Package, version_declared(Version, 0)), attr("node", node(PackageID, Package)). [ 1@2, sign]
 
-% Use default operating system and platform
-#heuristic attr("node_os", node(PackageID, Package), OS) : os(OS, 0), attr("root", node(PackageID, Package)). [40, true]
-#heuristic attr("node_platform", node(PackageID, Package), Platform) : allowed_platform(Platform), attr("root", node(PackageID, Package)). [40, true]
+#heuristic version_weight(node(PackageID, Package), Weight).                                          [30, init]
+#heuristic version_weight(node(PackageID, Package), Weight).                                          [-1  , sign]
+#heuristic version_weight(node(PackageID, Package), 0     ) : attr("node", node(PackageID, Package)). [ 1@2, sign]
+
+% Use default variants
+#heuristic attr("variant_value", PackageNode, Variant, Value). [30, init]
+#heuristic attr("variant_value", PackageNode, Variant, Value). [-1, sign]
+#heuristic attr("variant_value", PackageNode, Variant, Value) : variant_default_value(PackageNode, Variant, Value), attr("node", PackageNode). [1@2, sign]
 
 % Use default targets
-#heuristic attr("node_target", node(PackageID, Package), Target) : target_weight(Target, Weight), attr("node", node(PackageID, Package)). [30, init]
-#heuristic attr("node_target", node(PackageID, Package), Target) : target_weight(Target, Weight), attr("node", node(PackageID, Package)). [ 2, factor]
-#heuristic attr("node_target", node(PackageID, Package), Target) : target_weight(Target,      0), attr("node", node(PackageID, Package)). [ 1, sign]
-#heuristic attr("node_target", node(PackageID, Package), Target) : target_weight(Target, Weight), attr("node", node(PackageID, Package)), Weight > 0. [-1, sign]
+#heuristic attr("node_target", node(PackageID, Package), Target). [-1, sign]
+#heuristic attr("node_target", node(PackageID, Package), Target) : target_weight(Target, 0), attr("node", node(PackageID, Package)). [1@2, sign]
 
 % Use the default compilers
 #heuristic node_compiler(node(PackageID, Package), ID) : compiler_weight(ID, 0), compiler_id(ID), attr("node", node(PackageID, Package)). [30, init]