Spec: prefer a splice-specific method to `__len__` (#47585)

Automatic splicing say `Spec` grow a `__len__` method but it's only used
in one place and it's not clear the semantics are useful elsewhere. It also
runs the risk of Specs one day being confused for other types of containers.

Rather than introduce a new function for one algorithm, let's use a more
specific method in the splice code.

- [x] Use topological ordering in `_resolve_automatic_splices` instead of 
      sorting by node count
- [x] delete `Spec.__len__()` and `Spec.__bool__()`

---------

Signed-off-by: Todd Gamblin <tgamblin@llnl.gov>
Co-authored-by: Greg Becker <becker33@llnl.gov>
Co-authored-by: Massimiliano Culpo <massimiliano.culpo@gmail.com>

5 files changed, 37 insertions, 25 deletions

diff --git a/lib/spack/spack/solver/asp.py b/lib/spack/spack/solver/asp.py
index 32db03f5cf..5310c4e3a8 100644
--- a/lib/spack/spack/solver/asp.py
+++ b/lib/spack/spack/solver/asp.py
@@ -3839,12 +3839,21 @@ class SpecBuilder:
         self._splices.setdefault(parent_node, []).append(splice)
 
     def _resolve_automatic_splices(self):
-        """After all of the specs have been concretized, apply all immediate
-        splices in size order. This ensures that all dependencies are resolved
+        """After all of the specs have been concretized, apply all immediate splices.
+
+        Use reverse topological order to ensure that all dependencies are resolved
         before their parents, allowing for maximal sharing and minimal copying.
+
         """
         fixed_specs = {}
-        for node, spec in sorted(self._specs.items(), key=lambda x: len(x[1])):
+
+        # create a mapping from dag hash to an integer representing position in reverse topo order.
+        specs = self._specs.values()
+        topo_order = list(traverse.traverse_nodes(specs, order="topo", key=traverse.by_dag_hash))
+        topo_lookup = {spec.dag_hash(): index for index, spec in enumerate(reversed(topo_order))}
+
+        # iterate over specs, children before parents
+        for node, spec in sorted(self._specs.items(), key=lambda x: topo_lookup[x[1].dag_hash()]):
             immediate = self._splices.get(node, [])
             if not immediate and not any(
                 edge.spec in fixed_specs for edge in spec.edges_to_dependencies()
diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 63a5a71175..9bb237754e 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -1455,7 +1455,7 @@ attr("node_flag", PackageNode, NodeFlag) :- attr("node_flag_set", PackageNode, N
 #defined installed_hash/2.
 #defined abi_splice_conditions_hold/4.
 
-% These are the previously concretized attributes of the installed package as 
+% These are the previously concretized attributes of the installed package as
 % a hash. It has the general form:
 % hash_attr(Hash, Attribute, PackageName, Args*)
 #defined hash_attr/3.
@@ -1479,12 +1479,12 @@ hash_attr(Hash, "node_version_satisfies", PackageName, Constraint) :-
 
 % This recovers the exact semantics for hash reuse hash and depends_on are where
 % splices are decided, and virtual_on_edge can result in name-changes, which is
-% why they are all treated separately. 
+% why they are all treated separately.
 imposed_constraint(Hash, Attr, PackageName) :-
   hash_attr(Hash, Attr, PackageName).
 imposed_constraint(Hash, Attr, PackageName, A1) :-
   hash_attr(Hash, Attr, PackageName, A1), Attr != "hash".
-imposed_constraint(Hash, Attr, PackageName, Arg1, Arg2) :- 
+imposed_constraint(Hash, Attr, PackageName, Arg1, Arg2) :-
   hash_attr(Hash, Attr, PackageName, Arg1, Arg2),
   Attr != "depends_on",
   Attr != "virtual_on_edge".
@@ -1492,16 +1492,16 @@ imposed_constraint(Hash, Attr, PackageName, A1, A2, A3) :-
   hash_attr(Hash, Attr, PackageName, A1, A2, A3).
 imposed_constraint(Hash, "hash", PackageName, Hash) :- installed_hash(PackageName, Hash).
 % Without splicing, we simply recover the exact semantics
-imposed_constraint(ParentHash, "hash", ChildName, ChildHash) :- 
+imposed_constraint(ParentHash, "hash", ChildName, ChildHash) :-
   hash_attr(ParentHash, "hash", ChildName, ChildHash),
   ChildHash != ParentHash,
   not abi_splice_conditions_hold(_, _, ChildName, ChildHash).
-  
+
 imposed_constraint(Hash, "depends_on", PackageName, DepName, Type) :-
   hash_attr(Hash, "depends_on", PackageName, DepName, Type),
   hash_attr(Hash, "hash", DepName, DepHash),
   not attr("splice_at_hash", _, _, DepName, DepHash).
-  
+
 imposed_constraint(Hash, "virtual_on_edge", PackageName, DepName, VirtName) :-
   hash_attr(Hash, "virtual_on_edge", PackageName, DepName, VirtName),
   not attr("splice_at_hash", _, _, DepName,_).
@@ -1511,7 +1511,7 @@ imposed_constraint(Hash, "virtual_on_edge", PackageName, DepName, VirtName) :-
 
 impose(Hash, PackageNode) :- attr("hash", PackageNode, Hash), attr("node", PackageNode).
 
-% If there is not a hash for a package, we build it. 
+% If there is not a hash for a package, we build it.
 build(PackageNode) :- attr("node", PackageNode), not concrete(PackageNode).
 
 
diff --git a/lib/spack/spack/spec.py b/lib/spack/spack/spec.py
index 03a372be4e..926f35a704 100644
--- a/lib/spack/spack/spec.py
+++ b/lib/spack/spack/spec.py
@@ -1431,8 +1431,6 @@ def tree(
 class Spec:
     #: Cache for spec's prefix, computed lazily in the corresponding property
     _prefix = None
-    #: Cache for spec's length, computed lazily in the corresponding property
-    _length = None
     abstract_hash = None
 
     @staticmethod
@@ -3702,18 +3700,6 @@ class Spec:
 
         return child
 
-    def __len__(self):
-        if not self.concrete:
-            raise spack.error.SpecError(f"Cannot get length of abstract spec: {self}")
-
-        if not self._length:
-            self._length = 1 + sum(len(dep) for dep in self.dependencies())
-        return self._length
-
-    def __bool__(self):
-        # Need to define this so __len__ isn't used by default
-        return True
-
     def __contains__(self, spec):
         """True if this spec or some dependency satisfies the spec.
 
@@ -4472,7 +4458,7 @@ class Spec:
             if h.attr not in ignore:
                 if hasattr(self, h.attr):
                     setattr(self, h.attr, None)
-        for attr in ("_dunder_hash", "_prefix", "_length"):
+        for attr in ("_dunder_hash", "_prefix"):
             if attr not in ignore:
                 setattr(self, attr, None)
 
diff --git a/lib/spack/spack/test/abi_splicing.py b/lib/spack/spack/test/abi_splicing.py
index b36c285b13..d647647797 100644
--- a/lib/spack/spack/test/abi_splicing.py
+++ b/lib/spack/spack/test/abi_splicing.py
@@ -229,3 +229,19 @@ def test_spliced_build_deps_only_in_build_spec(splicing_setup):
         assert _has_build_dependency(build_spec, "splice-z")
         # Spliced build dependencies are removed
         assert len(concr_goal.dependencies(None, dt.BUILD)) == 0
+
+
+def test_spliced_transitive_dependency(splicing_setup):
+    cache = ["splice-depends-on-t@1.0 ^splice-h@1.0.1"]
+    goal_spec = Spec("splice-depends-on-t^splice-h@1.0.2")
+
+    with CacheManager(cache):
+        spack.config.set("packages", _make_specs_non_buildable(["splice-depends-on-t"]))
+        _enable_splicing()
+        concr_goal = goal_spec.concretized()
+        # Spec has been spliced
+        assert concr_goal._build_spec is not None
+        assert concr_goal["splice-t"]._build_spec is not None
+        assert concr_goal.satisfies(goal_spec)
+        # Spliced build dependencies are removed
+        assert len(concr_goal.dependencies(None, dt.BUILD)) == 0
diff --git a/lib/spack/spack/test/cmd/pkg.py b/lib/spack/spack/test/cmd/pkg.py
index 1811b1a617..8dfdf4773d 100644
--- a/lib/spack/spack/test/cmd/pkg.py
+++ b/lib/spack/spack/test/cmd/pkg.py
@@ -315,6 +315,7 @@ def test_pkg_grep(mock_packages, capfd):
             "depends-on-manyvariants",
             "manyvariants",
             "splice-a",
+            "splice-depends-on-t",
             "splice-h",
             "splice-t",
             "splice-vh",