Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Resolving takes hours #3878

Open
blegat opened this issue Apr 23, 2024 · 3 comments · May be fixed by #3887
Open

Resolving takes hours #3878

blegat opened this issue Apr 23, 2024 · 3 comments · May be fixed by #3887

Comments

@blegat
Copy link

blegat commented Apr 23, 2024

In the following dionysos-dev/Dionysos.jl#352, resolving the environment Dionysos/BipedRobot/Project.toml takes hours.
You can see in the following log that it took 6 hours to do Pkg.instantiate() with Julia v1.10.2:
https://github.com/dionysos-dev/Dionysos.jl/actions/runs/8783197708/job/24099651447?pr=352
Steps to reproduce:

$ git clone git@github.com:dionysos-dev/Dionysos.jl.git
$ cd Dionysos.jl
$ git checkout pkg_stuck
$ julia --project=BipedRobot

then

(BipedRobot) pkg> instantiate
    Updating registry at `~/.julia/registries/General.toml`
    Updating `~/git/Dionysos.jl/BipedRobot/Project.toml`
 (... omitted ...)

(BipedRobot) pkg> dev .
   Resolving package versions...

It should be stuck resolving for hours.

@KristofferC
Copy link
Sponsor Member

Seems we are infinitely recursing in

converge!(graph, msgs, strace, perm, params) && (pop_snapshot!(graph); return true)
.

@carlobaldassi, any ideas about this one?

@carlobaldassi
Copy link
Member

I'll look into this.

@carlobaldassi
Copy link
Member

carlobaldassi commented Apr 28, 2024

I've been investigating this (for quite a while). Unfortunately, it's not a bug, strictly speaking. The solver is not infinitely recursing, it's just taking an inordinate amount of time because the problem is unsatisfiable but the algorithm keeps backtracking the partial heuristic solutions and attempting new ones. It's hitting a combinatorial wall - which is something I knew was possible but was hoping would be rare enough.

In fact, the issue can be triggered even just with a subset of the original requirements, like this: get in pkg mode and activate --temp, then

add MeshCatMechanisms ModelingToolkit Symbolics@5

It will seemingly get stuck.

Now a bit of analysis shows that under the circumstances ModelingToolkit is restricted to major version 8, so we can bisect its version range. Both of these return an error almost immedately:

add MeshCatMechanisms ModelingToolkit@8.65-8 Symbolics@5
add MeshCatMechanisms ModelingToolkit@8-8.64 Symbolics@5

Which shows that the problem is indeed unsatisfiable. Just to give an idea of how intricate this is here are the error messsages in both cases. (If you notice some log entries about packages having been fixed by the MaxSum heuristic: I checked that those are irrelevant, the problem truly is unsatisfiable.)

I'm not sure how to fix this; one unsatisfactory (at least to me) but straightforward solution would be adding some form of timeout, with an environment variable to control it.

carlobaldassi added a commit to carlobaldassi/Pkg3.jl that referenced this issue May 2, 2024
carlobaldassi added a commit to carlobaldassi/Pkg3.jl that referenced this issue May 2, 2024
carlobaldassi added a commit to carlobaldassi/Pkg3.jl that referenced this issue May 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

3 participants