Concretizer: put build->run deps in parent unification set (fixes #46034) #46106

muffgaga · 2024-08-29T09:10:07Z

In #46034, a package X build-depends on a build-tools-tagged package, e.g., py-setuptools, as well as another package Y that itself depends (build+run) on the same build-tools tagged package. In this case, the concretizer puts the possibly two versions of the build tool into separate unification sets, but the run-type dependency requires the
build environment of X to have both versions in its environment — which is illegal.
With this fix, the concretizer puts the two build tool nodes into a new common unification set if there is a build→run-type dependency chain on the build tool ⇒ spack now reports the expected error about not being able to find a common concretization of the build tool.

muffgaga · 2024-08-29T13:18:11Z

BTW. the fail in lib/spack/spack/test/concretize.py::TestConcretizeSeparately::test_two_setuptools looks correct to me (in the sense that the test itself is just wrong)… there are two py-setuptools versions that will end up in py-shapely's build environment (I'm trying to get spack build-env working for the duplicates.test repo but have failed so far :/).

After applying this, we end up with only two build-type versions of py-setupstools, which is what should work (and does work):

diff --git a/var/spack/repos/duplicates.test/packages/py-numpy/package.py b/var/spack/repos/duplicates.test/packages/py-numpy/package.py
index 42cb2aecc7..cfccb64b7e 100644
--- a/var/spack/repos/duplicates.test/packages/py-numpy/package.py
+++ b/var/spack/repos/duplicates.test/packages/py-numpy/package.py
@@ -16,5 +16,5 @@ class PyNumpy(Package):
     version("1.25.0", md5="0123456789abcdef0123456789abcdef")
 
     extends("python")
-    depends_on("py-setuptools@=59", type=("build", "run"))
+    depends_on("py-setuptools@=59", type=("build"))
     depends_on("gmake@4.1", type="build")

I think we should also have a inverse test (aka make sure the concretization fails) on the previous state.

muffgaga · 2024-08-29T13:35:05Z

@elenimath suggests this restructuring of the unification sets in order to:

keep the build_generic unification set containing all the non-multiple_unification_sets build dependencies and their run dependencies

and for for each parent, we also have an extra unification set, that contains:

all the multiple_unification_sets and their run deps

all the multiple_unification_sets run deps of the non-multiple_unification_sets build deps

diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 18c82474c9..923c195f35 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -95,12 +95,19 @@ 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", node(X, Child)), node(X, Child))
+unification_set(("build", ParentNode), node(X, Child))
   :- attr("depends_on", ParentNode, node(X, Child), Type),
      Type == "build",
      multiple_unification_sets(Child),
      unification_set(SetID, ParentNode).
 
+unification_set(("build", ParentNode), node(X, Child))
+  :- attr("depends_on", ParentNode, NonDupeNode, "build"),
+     not multiple_unification_sets(NonDupeNode),
+     attr("depends_on", NonDupeNode, node(X, Child), "run"),
+     multiple_unification_sets(Child),
+     unification_set(_, ParentNode).
+
 unification_set("generic_build", node(X, Child))
   :- attr("depends_on", ParentNode, node(X, Child), Type),
      Type == "build",

⇒ that looks like the complete solution to me (but I will stop spamming NOW… and wait for comments :) ).

haampie · 2024-08-29T15:17:55Z

Brave to take on this concretizer stuff ;) @alalazo will take a look

alalazo · 2024-08-29T15:18:05Z

@muffgaga I was looking at the issue, and I think this is what I would apply to develop as a change:

diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 18c82474c9..51dbba68c8 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -95,7 +95,7 @@ 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", node(X, Child)), node(X, Child))
+unification_set(("build", ParentNode), node(X, Child))
   :- attr("depends_on", ParentNode, node(X, Child), Type),
      Type == "build",
      multiple_unification_sets(Child),

There are two tests failing locally for me, I'll try to check them.

As you said in #46106 (comment) I think we should have two tests.

If it's the root to have a pure build dep on py-setuptools and on something that has a run dependency on py-setuptools, the py-setuptools node should be unique and both edges should point to it (if the problem is solvable)
In the opposite case, where the root has the build + run dep on py-setuptools and on something that has only a build dep to py-setuptools, then we should allow for two py-setuptools nodes, when required.

alalazo · 2024-08-29T15:23:00Z

@muffgaga ~~Go with this change you suggested, thanks #46106 (comment) !~~ Possibly a slightly better change:

diff --git a/lib/spack/spack/solver/concretize.lp b/lib/spack/spack/solver/concretize.lp
index 18c82474c9..d0ad292beb 100644
--- a/lib/spack/spack/solver/concretize.lp
+++ b/lib/spack/spack/solver/concretize.lp
@@ -95,10 +95,9 @@ 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", node(X, Child)), node(X, Child))
+unification_set(("build", ParentNode), node(X, Child))
   :- attr("depends_on", ParentNode, node(X, Child), Type),
      Type == "build",
-     multiple_unification_sets(Child),
      unification_set(SetID, ParentNode).
 
 unification_set("generic_build", node(X, Child))

Rationale is:

Each parent gets its own "build environment" where the build deps are unified.
Things that don't allow multiple nodes are also thrown into the "generic_build" unification

alalazo · 2024-08-29T15:53:26Z

This diff instead:

diff --git a/var/spack/repos/duplicates.test/packages/py-numpy/package.py b/var/spack/repos/duplicates.test/packages/py-numpy/package.py
index 42cb2aecc7..e0ca7dfa32 100644
--- a/var/spack/repos/duplicates.test/packages/py-numpy/package.py
+++ b/var/spack/repos/duplicates.test/packages/py-numpy/package.py
@@ -16,5 +16,5 @@ class PyNumpy(Package):
     version("1.25.0", md5="0123456789abcdef0123456789abcdef")
 
     extends("python")
-    depends_on("py-setuptools@=59", type=("build", "run"))
+    depends_on("py-setuptools@=59", type="build")
     depends_on("gmake@4.1", type="build")
diff --git a/var/spack/repos/duplicates.test/packages/py-shapely/package.py b/var/spack/repos/duplicates.test/packages/py-shapely/package.py
index 091f8c9938..f5809d3341 100644
--- a/var/spack/repos/duplicates.test/packages/py-shapely/package.py
+++ b/var/spack/repos/duplicates.test/packages/py-shapely/package.py
@@ -15,4 +15,4 @@ class PyShapely(Package):
 
     extends("python")
     depends_on("py-numpy", type=("build", "link", "run"))
-    depends_on("py-setuptools@=60", type="build")
+    depends_on("py-setuptools@=60", type=("build", "run"))

should make the current tests pass. Then we'd just need a test for the case that should fail.

muffgaga · 2024-08-29T16:13:17Z

@alalazo Thanks for looking into this. I'm currently creating another test that checks some "build-tool with its own build deps" case, and I'm not yet sure that everything works there (we don't catch it in the tests, because py-setuptools doesn't have deps in those). I also added "fixed" tests (and the inverse one) → it's probably better style to keep the package names the same and add variants for +rundep or something like that, right?
(And I'll update the PR according to your suggestions.)

elenimath · 2024-08-29T16:14:44Z

@alalazo about #46106 (comment), I just assumed that smaller unification sets were better performance-wise, but I'm not sure what the actual impact would be :)

muffgaga · 2024-08-29T16:22:09Z

@alalazo about #46106 (comment), I just assumed that smaller unification sets were better performance-wise, but I'm not sure what the actual impact would be :)

I did a quick spack solve --timers -UtI nest on my laptop (develop from this morning) — surely no reproducible state, just to get a rough estimate on the impact:

@alalazo's nice-and-clean patch:

    setup          3.699s
    load           0.460s
    ground         5.080s
    solve         10.756s
    total         20.489s

@elenimath yours :P

    setup          3.757s
    load           0.482s
    ground         4.320s
    solve          6.183s
    total         15.235s

muffgaga · 2024-08-29T16:41:05Z

Updated merge branch:

adapted change in concretize.lp (fixes author :))
duplicates.test repo: PyNumpy has now a rundeps variant but defaults to build-only dependency on py-setuptools
duplicates.test repo: PyShapely now run-depends on py-setuptools (to check that this is possible)

alalazo · 2024-08-29T16:52:07Z

Looks good, thanks. I'll do some performance benchmark asap, and post it.

muffgaga · 2024-08-30T07:52:55Z

I added another test (to cover "chains" of build tools) that looks like there's a problem with "strategy: full".

The test should cover this case here:

#  all build deps
o compiled-tool@1.0
|\
o | seemake@4.0
o | gmake@4.1
 /
o compiled-intermediate-tool@3.0
o seemake@3.0
o gmake@3.0

But in strategy: full when I look at the self.{_link_run,_total_build,_direct_build} members, gmake is there only once, i.e. max_dupes for it is set to one → fails to concretize.
In strategy: minimal it does not happen because gmake is a build tool and a max_dupes of 2 is set for it.

I added another test (to cover "chains" of build tools) that shows that there's a problem with "strategy: full".

The test should cover this case here:

#  all build deps
o compiled-tool@1.0
|\
o | seemake@4.0
o | gmake@4.1
 /
o compiled-intermediate-tool@3.0
o seemake@3.0
o gmake@3.0

But in strategy: full when I look at the self.{_link_run,_total_build,_direct_build} members, gmake is there only once, i.e. max_dupes for it is set to one → fails to concretize.
When I look at the members in FullDuplicatesCounter, it looks like this:

# print(str(list(self._link_run)) + " — " + str(list(self._total_build)) + " — " + str(list(self._direct_build)))
['compiled-tool'] — ['gmake', 'compiled-intermediate-tool', 'seemake'] — ['compiled-intermediate-tool', 'seemake']

⇒ i.e. gmake only appears once, and max_dupes of gmake is set to 1.
In strategy: minimal it does not happen because gmake is a build tool and a max_dupes of 2 is set for it unconditionally.

self._total_build looks like: {'seemake': {'gmake'}, 'gmake': set(), 'compiled-intermediate-tool': {'seemake'}} ⇒ and we traverse this as a graph to count the leaves but we only count keys ⇒ I think that's wrong.
@elenimath tried a (cycle-safe) DFS instead of just counting the keys → test works then; I added the "fix" (which is crude, introduces a DFS after we just performed a DFS via possible_dependencies()… (cycle check is wrong))) as a commit on top of this PR. However…

⇒ I think this is an unrelated issue.
We probably should remove the extra test from there, and create a fresh PR? Yes, no, maybe :) ?

muffgaga · 2024-09-02T11:16:34Z

I removed the "full"-strategy related things from this PR as it is an unrelated issue → @elenimath did a deeper investigation and provided a fresh PR #46169 that covers this separate issue (including the initially failing test and maybe also a fix :) ).

alalazo · 2024-09-03T06:31:24Z

I just benchmarked on:

Spack: 0.23.0.dev0 (1f935ac)
Python: 3.11.5
Platform: linux-ubuntu20.04-icelake

radiuss-pr.csv
radiuss-develop.csv
radiuss.txt

Using unification sets as "build environments" per node comes with a significant performance hit. I'll check later the patch in #46106 (comment), but it seems to me that this one is overly specific to this case (e.g. why only run dependencies and not link dependencies?).

I'll try to think how to optimize this use case 🤔

elenimath · 2024-09-03T06:44:44Z

e.g. why only run dependencies and not link dependencies?

true, it should be Type != "build" instead

muffgaga · 2024-09-03T08:26:51Z

e.g. why only run dependencies and not link dependencies?

true, it should be Type != "build" instead

("run" vs. Type != build doesn't seem to affect solving time much.)

Using unification sets as "build environments" per node comes with a significant performance hit. I'll check later the patch in #46106 (comment), […]

Some single solve --timers -UtI runs of glvis (which shows the hardest impact in your plots) and see for the total times (most of the difference is in the solving time, as your plots also show; test/concretize.py (test state of ba77d3) from this does only fail for "develop"); this is all ± 1s depending on what my browser does in parallel ;):

develop: 22.5s
@alalazo's suggested fix: 38.5s (i.e. +70%)
@alalazo's initially suggested fix: 28s (i.e. +25%)
@elenimath's suggested fix (modified, w/ Type != "build"): 28s (i.e. +25%)

haampie · 2024-09-05T17:19:55Z

I think it was sensible to leave out type=link. Link deps roughly correspond to local search paths or no search at all, run deps have their global search *PATHs, which is the issue being solved.

But of course no reason to not be more restrictive if that improves performance...

alalazo

I'm currently looking at performance vs. correctness.

I think the most correct change is the one in #46106 (comment) but it's really slow (due to an explosion of the rules for unification sets).

I'm fine with the heuristic in #46106 (comment). The limitation there is that it doesn't account for transitive dependencies of NonDupeNode in the link/run subdag. It's also slower than develop due to the same reason as above, but at a lower scale.

TL;DR I'm looking for some alternative heuristic to avoid slowing down the solve. If we can't find it, I'm fine with #46106 (comment). The request for change is for the comment on the test. Can you double check it?

var/spack/repos/duplicates.test/packages/py-shapely/package.py

…fixes spack#46034) * Each parent gets its own "build environment" where the build deps are unified. * Things that don't allow multiple nodes are also thrown into the "generic_build" unification In spack#46034, a package X build-depends on a `build-tools`-tagged package, e.g., `py-setuptools`, as well as another package Y that itself depends (build+run) on the same `build-tools` tagged package. In this case, the concretizer puts the possibly two versions of the build tool into separate unification sets, but the run-type dependency requires the build environment of X to have both versions in its environment — which is illegal. With this fix, the concretizer puts the two build tool nodes into a new common unification set if there is a build→run-type dependency chain on the build tool ⇒ spack now reports the expected error about not being able to find a common concretization of the build tool. Change-Id: I99257b225602c21d4f270fe16e68c1f8bd4b1eba

This introduces `-fixed` packages for py-shapely and py-floating which depend on a `-fixed` py-numpy that does NOT run-depend on py-setuptools. If we allow run deps of build deps, it causes the tool to appear multiple times in the build environment ⇒ fail. Change-Id: I1ef1fa0b8636c23626c7e2ea521d3b5438f97d0a

This introduces a regression test to ensure that the concretizer fails when trying to solve a spec where we have a build tool in two versions and the "lower" (in the DAG) version being also a run-dependency. If this would be allowed, we could end up having multiple paths to different tool versions/variants in the build env. Change-Id: I050efc9471d89580f5546a1c56ab419891bcc792

spackbot-app bot added the core PR affects Spack core functionality label Aug 29, 2024

muffgaga mentioned this pull request Aug 29, 2024

Duplicate package in PYTHONPATH #46034

Open

3 tasks

muffgaga force-pushed the fix_concretizer_buildrun_deps branch from 1e9f035 to 4ef6ce5 Compare August 29, 2024 12:15

spackbot-app bot added dependencies extends new-version stand-alone-tests Stand-alone (or smoke) tests for installed packages tests General test capability(ies) labels Aug 29, 2024

alalazo added this to the v0.22.2 milestone Aug 29, 2024

alalazo self-assigned this Aug 29, 2024

muffgaga force-pushed the fix_concretizer_buildrun_deps branch from 4434880 to 0c22d87 Compare August 29, 2024 16:33

spackbot-app bot added the new-variant label Aug 29, 2024

muffgaga force-pushed the fix_concretizer_buildrun_deps branch from 0c22d87 to f55a9af Compare August 29, 2024 16:40

muffgaga force-pushed the fix_concretizer_buildrun_deps branch 3 times, most recently from ddecbee to 9ac60b3 Compare September 2, 2024 11:15

elenimath mentioned this pull request Sep 2, 2024

Concretizer: fix duplicate count when strategy=full #46169

Open

alalazo requested changes Sep 6, 2024

View reviewed changes

var/spack/repos/duplicates.test/packages/py-shapely/package.py Outdated Show resolved Hide resolved

muffgaga force-pushed the fix_concretizer_buildrun_deps branch from 9ac60b3 to a87fca1 Compare September 13, 2024 15:04

elenimath and others added 3 commits September 13, 2024 17:07

muffgaga force-pushed the fix_concretizer_buildrun_deps branch from a87fca1 to 57e563d Compare September 13, 2024 15:07

haampie modified the milestones: v0.22.2, v0.22.3 Sep 21, 2024

haampie added the v0.22.3 PRs to backport for v0.22.3 label Oct 15, 2024

haampie removed this from the v0.22.3 milestone Oct 15, 2024

haampie mentioned this pull request Oct 31, 2024

Backports v0.22.3 #46984

Merged

32 tasks

haampie removed the v0.22.3 PRs to backport for v0.22.3 label Nov 18, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Concretizer: put build->run deps in parent unification set (fixes #46034) #46106

Concretizer: put build->run deps in parent unification set (fixes #46034) #46106

muffgaga commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 29, 2024 •

edited

Loading

haampie commented Aug 29, 2024

alalazo commented Aug 29, 2024

alalazo commented Aug 29, 2024 •

edited

Loading

alalazo commented Aug 29, 2024

muffgaga commented Aug 29, 2024

elenimath commented Aug 29, 2024

muffgaga commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 29, 2024 •

edited

Loading

alalazo commented Aug 29, 2024

muffgaga commented Aug 30, 2024 •

edited

Loading

muffgaga commented Sep 2, 2024 •

edited

Loading

alalazo commented Sep 3, 2024

elenimath commented Sep 3, 2024

muffgaga commented Sep 3, 2024 •

edited

Loading

haampie commented Sep 5, 2024 •

edited

Loading

alalazo left a comment

Concretizer: put build->run deps in parent unification set (fixes #46034) #46106

Are you sure you want to change the base?

Concretizer: put build->run deps in parent unification set (fixes #46034) #46106

Conversation

muffgaga commented Aug 29, 2024 • edited Loading

muffgaga commented Aug 29, 2024 • edited Loading

muffgaga commented Aug 29, 2024 • edited Loading

haampie commented Aug 29, 2024

alalazo commented Aug 29, 2024

alalazo commented Aug 29, 2024 • edited Loading

alalazo commented Aug 29, 2024

muffgaga commented Aug 29, 2024

elenimath commented Aug 29, 2024

muffgaga commented Aug 29, 2024 • edited Loading

muffgaga commented Aug 29, 2024 • edited Loading

alalazo commented Aug 29, 2024

muffgaga commented Aug 30, 2024 • edited Loading

muffgaga commented Sep 2, 2024 • edited Loading

alalazo commented Sep 3, 2024

elenimath commented Sep 3, 2024

muffgaga commented Sep 3, 2024 • edited Loading

haampie commented Sep 5, 2024 • edited Loading

alalazo left a comment

Choose a reason for hiding this comment

muffgaga commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 29, 2024 •

edited

Loading

alalazo commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 29, 2024 •

edited

Loading

muffgaga commented Aug 30, 2024 •

edited

Loading

muffgaga commented Sep 2, 2024 •

edited

Loading

muffgaga commented Sep 3, 2024 •

edited

Loading

haampie commented Sep 5, 2024 •

edited

Loading