Add solver capability for synthesizing splices of ABI compatible packages. (#46729)

This PR provides complementary 2 features:
1. An augmentation to the package language to express ABI compatibility relationships among packages. 
2. An extension to the concretizer that can synthesize splices between ABI compatible packages.

1.  The `can_splice` directive and ABI compatibility 
We augment the package language with a single directive: `can_splice`. Here is an example of a package `Foo` exercising the `can_splice` directive:

class Foo(Package):
    version("1.0")
    version("1.1")
    variant("compat", default=True)
    variant("json", default=False)
    variant("pic", default=False)
    can_splice("foo@1.0", when="@1.1")
    can_splice("bar@1.0", when="@1.0+compat")
    can_splice("baz@1.0+compat", when="@1.0+compat", match_variants="*")
    can_splice("quux@1.0", when=@1.1~compat", match_variants="json")

Explanations of the uses of each directive: 
- `can_splice("foo@1.0", when="@1.1")`:  If `foo@1.0` is the dependency of an already installed spec and `foo@1.1` could be a valid dependency for the parent spec, then `foo@1.1` can be spliced in for `foo@1.0` in the parent spec.
- `can_splice("bar@1.0", when="@1.0+compat")`: If `bar@1.0` is the dependency of an already installed spec and `foo@1.0+compat` could be a valid dependency for the parent spec, then `foo@1.0+compat` can be spliced in for `bar@1.0+compat` in the parent spec
-  `can_splice("baz@1.0", when="@1.0+compat", match_variants="*")`: If `baz@1.0+compat` is the dependency of an already installed spec and `foo@1.0+compat` could be a valid dependency for the parent spec, then `foo@1.0+compat` can be spliced in for `baz@1.0+compat` in the parent spec, provided that they have the same value for all other variants (regardless of what those values are). 
-  `can_splice("quux@1.0", when=@1.1~compat", match_variants="json")`:If `quux@1.0` is the dependency of an already installed spec and `foo@1.1~compat` could be a valid dependency for the parent spec, then `foo@1.0~compat` can be spliced in for `quux@1.0` in the parent spec, provided that they have the same value for their `json` variant. 

2. Augmenting the solver to synthesize splices
### Changes to the hash encoding in `asp.py`
Previously, when including concrete specs in the solve, they would have the following form:

installed_hash("foo", "xxxyyy")
imposed_constraint("xxxyyy", "foo", "attr1", ...)
imposed_constraint("xxxyyy", "foo", "attr2", ...)
% etc. 

Concrete specs now have the following form:
installed_hash("foo", "xxxyyy")
hash_attr("xxxyyy", "foo", "attr1", ...)
hash_attr("xxxyyy", "foo", "attr2", ...)

This transformation allows us to control which constraints are imposed when we select a hash, to facilitate the splicing of dependencies. 

2.1 Compiling `can_splice` directives in `asp.py`
Consider the concrete spec:
foo@2.72%gcc@11.4 arch=linux-ubuntu22.04-icelake build_system=autotools ^bar ...
It will emit the following facts for reuse (below is a subset)

installed_hash("foo", "xxxyyy")
hash_attr("xxxyyy", "hash", "foo", "xxxyyy")
hash_attr("xxxyyy", "version", "foo", "2.72")
hash_attr("xxxyyy", "node_os", "ubuntu22.04")
hash_attr("xxxyyy", "hash", "bar", "zzzqqq")
hash_attr("xxxyyy", "depends_on", "foo", "bar", "link")

Rules that derive abi_splice_conditions_hold will be generated from 
use of the `can_splice` directive. They will have the following form:
can_splice("foo@1.0.0+a", when="@1.0.1+a", match_variants=["b"]) --->

abi_splice_conditions_hold(0, node(SID, "foo"), "foo", BaseHash) :-
  installed_hash("foo", BaseHash),
  attr("node", node(SID, SpliceName)),
  attr("node_version_satisfies", node(SID, "foo"), "1.0.1"),
  hash_attr("hash", "node_version_satisfies", "foo", "1.0.1"),
  attr("variant_value", node(SID, "foo"), "a", "True"),
  hash_attr("hash", "variant_value", "foo", "a", "True"),
  attr("variant_value", node(SID, "foo"), "b", VariVar0),
  hash_attr("hash", "variant_value", "foo", "b", VariVar0).


2.2 Synthesizing splices in `concretize.lp` and `splices.lp`

The ASP solver generates "splice_at_hash" attrs to indicate that a particular node has a splice in one of its immediate dependencies. 

Splices can be introduced in the dependencies of concrete specs when `splices.lp` is conditionally loaded (based on the config option `concretizer:splice:True`. 

2.3 Constructing spliced specs in `asp.py`

The method `SpecBuilder._resolve_splices` implements a top-down memoized implementation of hybrid splicing. This is an optimization over the more general `Spec.splice`, since the solver gives a global view of exactly which specs can be shared, to ensure the minimal number of splicing operations. 

Misc changes to facilitate configuration and benchmarking 
- Added the method `Solver.solve_with_stats` to expose timers from the public interface for easier benchmarking 
- Added the boolean config option `concretizer:splice` to conditionally load splicing behavior 

Co-authored-by: Greg Becker <becker33@llnl.gov>

9 files changed, 187 insertions, 2 deletions

diff --git a/var/spack/repos/builtin.mock/packages/depends-on-manyvariants/package.py b/var/spack/repos/builtin.mock/packages/depends-on-manyvariants/package.py
new file mode 100644
index 0000000000..f1314471f9
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/depends-on-manyvariants/package.py
@@ -0,0 +1,25 @@
+# Copyright 2013-2024 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)
+
+from spack.package import *
+
+
+class DependsOnManyvariants(Package):
+    """
+    A package with a dependency on `manyvariants`, so that `manyvariants` can
+    be spliced in tests.
+    """
+
+    homepage = "https://www.test.com"
+    has_code = False
+
+    version("1.0")
+    version("2.0")
+
+    depends_on("manyvariants@1.0", when="@1.0")
+    depends_on("manyvariants@2.0", when="@2.0")
+
+    def install(self, spec, prefix):
+        touch(prefix.bar)
diff --git a/var/spack/repos/builtin.mock/packages/depends-on-virtual-with-abi/package.py b/var/spack/repos/builtin.mock/packages/depends-on-virtual-with-abi/package.py
new file mode 100644
index 0000000000..9f281f337b
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/depends-on-virtual-with-abi/package.py
@@ -0,0 +1,19 @@
+# Copyright 2013-2024 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)
+
+from spack.package import *
+
+
+class DependsOnVirtualWithAbi(Package):
+    """
+    This has a virtual dependency on `virtual-with-abi`, mostly for testing
+    automatic splicing of providers.
+    """
+
+    homepage = "https://www.example.com"
+    has_code = False
+
+    version("1.0")
+    depends_on("virtual-with-abi")
diff --git a/var/spack/repos/builtin.mock/packages/manyvariants/package.py b/var/spack/repos/builtin.mock/packages/manyvariants/package.py
new file mode 100644
index 0000000000..4747fab53f
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/manyvariants/package.py
@@ -0,0 +1,33 @@
+# Copyright 2013-2024 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)
+
+from spack.package import *
+
+
+class Manyvariants(Package):
+    """
+    A package with 4 different variants of different arities to test the
+    `match_variants` argument to `can_splice`
+    """
+
+    homepage = "https://www.test.com"
+    has_code = False
+
+    version("2.0.1")
+    version("2.0.0")
+    version("1.0.1")
+    version("1.0.0")
+
+    variant("a", default=True)
+    variant("b", default=False)
+    variant("c", values=("v1", "v2", "v3"), multi=False, default="v1")
+    variant("d", values=("v1", "v2", "v3"), multi=False, default="v1")
+
+    can_splice("manyvariants@1.0.0", when="@1.0.1", match_variants="*")
+    can_splice("manyvariants@2.0.0+a~b", when="@2.0.1~a+b", match_variants=["c", "d"])
+    can_splice("manyvariants@2.0.0 c=v1 d=v1", when="@2.0.1+a+b")
+
+    def install(self, spec, prefix):
+        touch(prefix.bar)
diff --git a/var/spack/repos/builtin.mock/packages/splice-h/package.py b/var/spack/repos/builtin.mock/packages/splice-h/package.py
index a54f1e7f7d..6f86f09f92 100644
--- a/var/spack/repos/builtin.mock/packages/splice-h/package.py
+++ b/var/spack/repos/builtin.mock/packages/splice-h/package.py
@@ -12,17 +12,24 @@ class SpliceH(Package):
     homepage = "http://www.example.com"
     url = "http://www.example.com/splice-h-1.0.tar.gz"
 
-    version("1.0", md5="0123456789abcdef0123456789abcdef")
+    version("1.0.2")
+    version("1.0.1")
+    version("1.0.0")
 
     variant("foo", default=False, description="nope")
     variant("bar", default=False, description="nope")
     variant("baz", default=False, description="nope")
+    variant("compat", default=True, description="nope")
 
     depends_on("splice-z")
     depends_on("splice-z+foo", when="+foo")
 
     provides("something")
     provides("somethingelse")
+    provides("virtual-abi")
+
+    can_splice("splice-h@1.0.0 +compat", when="@1.0.1 +compat")
+    can_splice("splice-h@1.0.0:1.0.1 +compat", when="@1.0.2 +compat")
 
     def install(self, spec, prefix):
         with open(prefix.join("splice-h"), "w") as f:
diff --git a/var/spack/repos/builtin.mock/packages/splice-z/package.py b/var/spack/repos/builtin.mock/packages/splice-z/package.py
index ff73fbaa03..bac33be600 100644
--- a/var/spack/repos/builtin.mock/packages/splice-z/package.py
+++ b/var/spack/repos/builtin.mock/packages/splice-z/package.py
@@ -12,10 +12,16 @@ class SpliceZ(Package):
     homepage = "http://www.example.com"
     url = "http://www.example.com/splice-z-1.0.tar.gz"
 
-    version("1.0", md5="0123456789abcdef0123456789abcdef")
+    version("1.0.2")
+    version("1.0.1")
+    version("1.0.0")
 
     variant("foo", default=False, description="nope")
     variant("bar", default=False, description="nope")
+    variant("compat", default=True, description="nope")
+
+    can_splice("splice-z@1.0.0 +compat", when="@1.0.1 +compat")
+    can_splice("splice-z@1.0.0:1.0.1 +compat", when="@1.0.2 +compat")
 
     def install(self, spec, prefix):
         with open(prefix.join("splice-z"), "w") as f:
diff --git a/var/spack/repos/builtin.mock/packages/virtual-abi-1/package.py b/var/spack/repos/builtin.mock/packages/virtual-abi-1/package.py
new file mode 100644
index 0000000000..60a4c64f9e
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/virtual-abi-1/package.py
@@ -0,0 +1,25 @@
+# Copyright 2013-2024 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)
+
+from spack.package import *
+
+
+class VirtualAbi1(Package):
+    """
+    This package provides `virtual-with-abi` and is conditionally ABI
+    compatible with `virtual-abi-multi`
+    """
+
+    homepage = "https://www.example.com"
+    has_code = False
+
+    version("1.0")
+
+    provides("virtual-with-abi")
+
+    can_splice("virtual-abi-multi@1.0 abi=one", when="@1.0")
+
+    def install(self, spec, prefix):
+        touch(prefix.foo)
diff --git a/var/spack/repos/builtin.mock/packages/virtual-abi-2/package.py b/var/spack/repos/builtin.mock/packages/virtual-abi-2/package.py
new file mode 100644
index 0000000000..5725bf504c
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/virtual-abi-2/package.py
@@ -0,0 +1,25 @@
+# Copyright 2013-2024 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)
+
+from spack.package import *
+
+
+class VirtualAbi2(Package):
+    """
+    This package provides `virtual-with-abi` and is conditionally ABI
+    compatible with `virtual-abi-multi`
+    """
+
+    homepage = "https://www.example.com"
+    has_code = False
+
+    version("1.0")
+
+    provides("virtual-with-abi")
+
+    can_splice("virtual-abi-multi@1.0 abi=two", when="@1.0")
+
+    def install(self, spec, prefix):
+        touch(prefix.foo)
diff --git a/var/spack/repos/builtin.mock/packages/virtual-abi-multi/package.py b/var/spack/repos/builtin.mock/packages/virtual-abi-multi/package.py
new file mode 100644
index 0000000000..87cfd31544
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/virtual-abi-multi/package.py
@@ -0,0 +1,29 @@
+# Copyright 2013-2024 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)
+
+from spack.package import *
+
+
+class VirtualAbiMulti(Package):
+    """
+    This package provides `virtual-with-abi` is ABI compatible with either
+    `virtual-abi-1` or `virtual-abi-2` depending on the value of its `abi`
+    variant
+    """
+
+    homepage = "https://www.example.com"
+    has_code = False
+
+    version("1.0")
+
+    variant("abi", default="custom", multi=False, values=("one", "two", "custom"))
+
+    provides("virtual-with-abi")
+
+    can_splice("virtual-abi-1@1.0", when="@1.0 abi=one")
+    can_splice("virtual-abi-2@1.0", when="@1.0 abi=two")
+
+    def install(self, spec, prefix):
+        touch(prefix.foo)
diff --git a/var/spack/repos/builtin.mock/packages/virtual-with-abi/package.py b/var/spack/repos/builtin.mock/packages/virtual-with-abi/package.py
new file mode 100644
index 0000000000..1147efd202
--- /dev/null
+++ b/var/spack/repos/builtin.mock/packages/virtual-with-abi/package.py
@@ -0,0 +1,16 @@
+# Copyright 2013-2024 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)
+
+from spack.package import *
+
+
+class VirtualWithAbi(Package):
+    """Virtual package for mocking an interface with stable ABI ."""
+
+    homepage = "https://www.abi.org/"
+    virtual = True
+
+    def test_hello(self):
+        print("Hello there!")