search

pubgrub-rs / pubgrub

PubGrub version solving algorithm implemented in Rust
https://pubgrub-rs.github.io/pubgrub/pubgrub/
Mozilla Public License 2.0
337 stars 30 forks source link

Panics and infinite loops #102

Closed njsmith closed 2 years ago

njsmith commented 3 years ago

Hello! pubgrub is super cool, thanks for working on it! I hacked together a python package resolver: https://github.com/njsmith/posy/blob/main/src/resolve.rs

It seems to work well for simple cases. However, I've been doing some experiments with feeding my resolver intentionally conflicting constraints, to see what happens, and I've been hitting panics and infinite loops inside pubgrub. Not sure if these are my fault or not, and I haven't managed to reproduce it with a more minimal setup yet, so idk, might not even be your bug. But I figured I'd post here in case you have any ideas :-)

Here's requesting trio == 0.19 and attrs == 19.1, which is impossible because trio v0.19 has a dependency on attrs >= 19.2.0. But pubgrub panics with "this must be a decision":

``` ❯ RUST_BACKTRACE=1 cargo run "trio == 0.19" "attrs == 19.1" Finished dev [unoptimized + debuginfo] target(s) in 0.08s Running `target/debug/posy 'trio == 0.19' 'attrs == 19.1'` user agent: posy/0.1.0 {"ci":null,"cpu":"x86_64","installer":{"name":"posy","version":"0.1.0"},"user_data":null} ----> pubgrub called choose_package_version -> For , allowed range is: 0 Chose package ; now let's decide which version <---- decision: root package magic version 0 ----> pubgrub called get_dependencies v0 adding dependency: trio 0.19 adding dependency: attrs 19.1 <---- dependencies complete ----> pubgrub called choose_package_version -> For attrs, allowed range is: 19.1 -> For trio, allowed range is: 0.19 Chose package attrs; now let's decide which version Version 21.2.0 is out of range Version 20.3.0 is out of range Version 20.2.0 is out of range Version 20.1.0 is out of range Version 19.3.0 is out of range Version 19.2.0 is out of range Considering attrs v19.1.0 Fetching metadata from https://files.pythonhosted.org/packages/23/96/d828354fa2dbdf216eaa7b7de0db692f12c234f7ef888cc14980ef40d1d2/attrs-19.1.0-py2.py3-none-any.whl <---- decision: attrs v19.1.0 ----> pubgrub called get_dependencies attrs v19.1.0 <---- dependencies complete ----> pubgrub called choose_package_version -> For trio, allowed range is: 0.19 Chose package trio; now let's decide which version Considering trio v0.19.0 Fetching metadata from https://files.pythonhosted.org/packages/35/c3/5a4befc3812b3b606e0ae9338bfdd02da3ad0a90df27dc66c37315e94f5c/trio-0.19.0-py3-none-any.whl <---- decision: trio v0.19.0 ----> pubgrub called get_dependencies trio v0.19.0 adding dependency: attrs 19.2.0 <= v adding dependency: sortedcontainers ∗ adding dependency: async-generator 1.9 <= v adding dependency: idna ∗ adding dependency: outcome ∗ adding dependency: sniffio ∗ <---- dependencies complete thread 'main' panicked at 'This must be a decision', /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:410:17 stack backtrace: 0: std::panicking::begin_panic at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:519:12 1: pubgrub::internal::partial_solution::PackageAssignments::satisfier at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:410:17 2: pubgrub::internal::partial_solution::PartialSolution::find_satisfier at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:330:17 3: pubgrub::internal::partial_solution::PartialSolution::satisfier_search at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:283:29 4: pubgrub::internal::core::State::conflict_resolution at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/core.rs:173:58 5: pubgrub::internal::core::State::unit_propagation at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/core.rs:139:52 6: pubgrub::solver::resolve at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/solver.rs:95:9 7: posy::resolve::resolve at ./src/resolve.rs:29:18 8: posy::main at ./src/main.rs:78:9 9: core::ops::function::FnOnce::call_once at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5 note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace. ```

Or, here's a very similar case -- trio >= 0.17, attrs == 19.1. Again, all versions of trio >= 0.17 have a dependency on attrs >= 19.2, so this is unsatisfiable. In this case, I get an infinite loop:

``` ❯ cargo run "trio >= 0.17" "attrs == 19.1" Finished dev [unoptimized + debuginfo] target(s) in 0.10s Running `target/debug/posy 'trio >= 0.17' 'attrs == 19.1'` user agent: posy/0.1.0 {"ci":null,"cpu":"x86_64","installer":{"name":"posy","version":"0.1.0"},"user_data":null} ----> pubgrub called choose_package_version -> For , allowed range is: 0 Chose package ; now let's decide which version <---- decision: root package magic version 0 ----> pubgrub called get_dependencies v0 adding dependency: trio 0.17 <= v adding dependency: attrs 19.1 <---- dependencies complete ----> pubgrub called choose_package_version -> For attrs, allowed range is: 19.1 -> For trio, allowed range is: 0.17 <= v Chose package attrs; now let's decide which version Version 21.2.0 is out of range Version 20.3.0 is out of range Version 20.2.0 is out of range Version 20.1.0 is out of range Version 19.3.0 is out of range Version 19.2.0 is out of range Considering attrs v19.1.0 Fetching metadata from https://files.pythonhosted.org/packages/23/96/d828354fa2dbdf216eaa7b7de0db692f12c234f7ef888cc14980ef40d1d2/attrs-19.1.0-py2.py3-none-any.whl <---- decision: attrs v19.1.0 ----> pubgrub called get_dependencies attrs v19.1.0 <---- dependencies complete ----> pubgrub called choose_package_version -> For trio, allowed range is: 0.17 <= v Chose package trio; now let's decide which version Considering trio v0.19.0 Fetching metadata from https://files.pythonhosted.org/packages/35/c3/5a4befc3812b3b606e0ae9338bfdd02da3ad0a90df27dc66c37315e94f5c/trio-0.19.0-py3-none-any.whl <---- decision: trio v0.19.0 ----> pubgrub called get_dependencies trio v0.19.0 adding dependency: attrs 19.2.0 <= v adding dependency: sortedcontainers ∗ adding dependency: async-generator 1.9 <= v adding dependency: idna ∗ adding dependency: outcome ∗ adding dependency: sniffio ∗ <---- dependencies complete ----> pubgrub called choose_package_version -> For trio, allowed range is: [ 0.17, 0.19.0 [ [ 0.19.0.post1.dev0, ∞ [ Chose package trio; now let's decide which version Version 0.19.0 is out of range Considering trio v0.18.0 Fetching metadata from https://files.pythonhosted.org/packages/5e/ce/1a6e875838058e9df989247ee339daa3d79cec599182a1a836ee1aa74750/trio-0.18.0-py3-none-any.whl <---- decision: trio v0.18.0 ----> pubgrub called get_dependencies trio v0.18.0 adding dependency: attrs 19.2.0 <= v adding dependency: sortedcontainers ∗ adding dependency: async-generator 1.9 <= v adding dependency: idna ∗ adding dependency: outcome ∗ adding dependency: sniffio ∗ <---- dependencies complete ----> pubgrub called choose_package_version -> For trio, allowed range is: [ 0.17, 0.18.0 [ [ 0.18.0.post1.dev0, 0.19.0 [ [ 0.19.0.post1.dev0, ∞ [ Chose package trio; now let's decide which version Version 0.19.0 is out of range Version 0.18.0 is out of range Considering trio v0.17.0 Fetching metadata from https://files.pythonhosted.org/packages/c6/92/46157361bc005fa4a4d190b44ed60377f695dc38d53fc339631eb97fe78a/trio-0.17.0-py3-none-any.whl <---- decision: trio v0.17.0 ----> pubgrub called get_dependencies trio v0.17.0 adding dependency: attrs 19.2.0 <= v adding dependency: sortedcontainers ∗ adding dependency: async-generator 1.9 <= v adding dependency: idna ∗ adding dependency: outcome ∗ adding dependency: sniffio ∗ <---- dependencies complete ----> pubgrub called choose_package_version -> For trio, allowed range is: [ 0.17.0.post1.dev0, 0.18.0 [ [ 0.18.0.post1.dev0, 0.19.0 [ [ 0.19.0.post1.dev0, ∞ [ Chose package trio; now let's decide which version Version 0.19.0 is out of range Version 0.18.0 is out of range Version 0.17.0 is out of range Version 0.16.0 is out of range Version 0.15.1 is out of range Version 0.15.0 is out of range Version 0.14.0 is out of range Version 0.13.0 is out of range Version 0.12.1 is out of range Version 0.12.0 is out of range Version 0.11.0 is out of range Version 0.10.0 is out of range Version 0.9.0 is out of range Version 0.8.0 is out of range Version 0.7.0 is out of range Version 0.6.0 is out of range Version 0.5.0 is out of range Version 0.4.0 is out of range Version 0.3.0 is out of range Version 0.2.0 is out of range Version 0.1.0 is out of range Version 0.0.0 is out of range <---- decision: no versions of trio in range [ program hangs until killed ] ```

Here's a few random backtraces taken from the infinite loop:

``` <---- decision: no versions of trio in range ^C Program received signal SIGINT, Interrupt. core::ptr::const_ptr::::is_null (self=0x8) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/const_ptr.rs:37 37 pub const fn is_null(self) -> bool { (gdb) bt #0 core::ptr::const_ptr::::is_null (self=0x8) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/const_ptr.rs:37 #1 0x0000555555ad9353 in core::slice::iter::Iter::new (slice=...) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/iter.rs:92 #2 0x0000555555acd8b4 in core::slice::::iter (self=...) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/mod.rs:705 #3 0x00005555557c9e65 in ::to_vec (s=..., alloc=...) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/slice.rs:194 #4 0x00005555557afc5b in alloc::slice::hack::to_vec (s=..., alloc=...) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/slice.rs:163 #5 0x00005555557cb74b in alloc::slice::::to_vec_in (self=..., alloc=...) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/slice.rs:477 #6 0x00005555556ef5f5 in as core::clone::Clone>::clone ( self=0x7fffffff0128) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/vec/mod.rs:2336 #7 0x00005555557ca443 in ::clone ( self=0x7fffffff0110) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pep440-0.1.1/src/lib.rs:101 #8 0x00005555557e2a32 in ::clone ( self=0x7fffffff0110) at src/vocab/version.rs:9 #9 0x00005555557c58c6 in ::to_owned (self=0x7fffffff0110) at /home/njs/.rustup/toolchains/stable-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/borrow.rs:87 #10 0x00005555557d2144 in pubgrub::range::Range::intersection (self=0x7fffffff06f8, other=0x7fffffff00b8) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/range.rs:214 #11 0x00005555557335d7 in pubgrub::term::Term::intersection (self=0x7fffffff06f0, other=0x7fffffff0898) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/term.rs:84 #12 0x00005555557d661d in pubgrub::internal::partial_solution::PackageAssignments::satisfier (self=0x555556467270, package=0x7ffff739a048, incompat_term=0x7ffff739a0a8, start_term=..., store=0x7fffffff4330) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:391 #13 0x00005555557d4faf in pubgrub::internal::partial_solution::PartialSolution::find_satisfier (incompat=0x7ffff7399e90, package_assignments=0x7fffffff4308, store=0x7fffffff4330) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:330 #14 0x00005555557d53b6 in pubgrub::internal::partial_solution::PartialSolution::satisfier_search (self=0x7fffffff4308, incompat=0x7ffff7399e90, store=0x7fffffff4330) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:283 #15 0x00005555557d7882 in pubgrub::internal::core::State::conflict_resolution ( self=0x7fffffff4218, incompatibility=...) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/core.rs:173 #16 0x00005555557d71ee in pubgrub::internal::core::State::unit_propagation ( self=0x7fffffff4218, package=...) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/core.rs:139 #17 0x0000555555733f0f in pubgrub::solver::resolve (dependency_provider=0x7fffffffba10, package=..., version=...) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/solver.rs:95 #18 0x00005555557feee4 in posy::resolve::resolve (requirements=0x7fffffffd990, env=0x7fffffffdad8, index=0x7fffffffd860, preferred_versions=0x7fffffffdb10, consider_prereleases=...) at src/resolve.rs:29 #19 0x00005555557938c6 in posy::main () at src/main.rs:78 (gdb) ``` ``` #0 pubgrub::range::Range::intersection (self=0x7fffffff0348, other=0x7fffffff08a0) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/range.rs:236 #1 0x000055555573364d in pubgrub::term::Term::intersection (self=0x7fffffff06f0, other=0x7fffffff0898) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/term.rs:87 #2 0x00005555557d661d in pubgrub::internal::partial_solution::PackageAssignments::satisfier (self=0x5555564676e0, package=0x7ffff6c0f418, incompat_term=0x7ffff6c0f478, start_term=..., store=0x7fffffff4330) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:391 #3 0x00005555557d4faf in pubgrub::internal::partial_solution::PartialSolution::find_satisfier (incompat=0x7ffff6c0f410, package_assignments=0x7fffffff4308, store=0x7fffffff4330) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:330 #4 0x00005555557d53b6 in pubgrub::internal::partial_solution::PartialSolution::satisfier_search (self=0x7fffffff4308, incompat=0x7ffff6c0f410, store=0x7fffffff4330) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/partial_solution.rs:283 #5 0x00005555557d7882 in pubgrub::internal::core::State::conflict_resolution ( self=0x7fffffff4218, incompatibility=...) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/core.rs:173 #6 0x00005555557d71ee in pubgrub::internal::core::State::unit_propagation ( self=0x7fffffff4218, package=...) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/internal/core.rs:139 #7 0x0000555555733f0f in pubgrub::solver::resolve (dependency_provider=0x7fffffffba10, package=..., version=...) at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pubgrub-0.2.1/src/solver.rs:95 #8 0x00005555557feee4 in posy::resolve::resolve (requirements=0x7fffffffd990, env=0x7fffffffdad8, index=0x7fffffffd860, preferred_versions=0x7fffffffdb10, consider_prereleases=...) at src/resolve.rs:29 #9 0x00005555557938c6 in posy::main () at src/main.rs:78 ```

Any suggestions?

Eh2406 commented 3 years ago

Thank you for using our project! The panics and infinite loops are not expected, I don't yet have a good idea of how this is possible. I will look over your linke code and take some notes, in case I spot something:

looking over resolve.rs, I have not found anything suspicious. It looks like for purposes of minimization, you can copy things into a OfflineDependencyProvider and send us a serialization of it for us to add to our tests.

"This must be a decision" is part of satisfier witch is also in your stack traces, and it is mostly doing intersection on a small set of Ranges. So ether we have a bug in our intersection or your Version has some kind of inconsistencies in Ord, Eq, or pubgrub::version::Version. Maybe you can replace the panic in the pubgrub code with something that outputs self.dated_derivations, incompat_term, and start_term. That may give us a small set of Versions to try and find the problem.

njsmith commented 3 years ago

looking over resolve.rs, I have not found anything suspicious. It looks like for purposes of minimization, you can copy things into a OfflineDependencyProvider and send us a serialization of it for us to add to our tests.

That's actually the first thing I tried, but I couldn't reproduce it that way. Which means I'm definitely missing something, but it doesn't point to what...

"This must be a decision" is part of satisfier witch is also in your stack traces, and it is mostly doing intersection on a small set of Ranges. So ether we have a bug in our intersection or your Version has some kind of inconsistencies in Ord, Eq, or pubgrub::version::Version. Maybe you can replace the panic in the pubgrub code with something that outputs self.dated_derivations, incompat_term, and start_term. That may give us a small set of Versions to try and find the problem.

Oo, this is super helpful at narrowing things down, I'll go poke around in there now.

njsmith commented 3 years ago

Ah-hah! It seems that the problem has something to do with 0.19 versus 0.19.0:

accum_term = Positive(Range { segments: [(Version(Version { epoch: 0, release: [0, 19], pre: None, post: None, dev: None, local: [] }), Some(Version(Version { epoch: 0, release: [0, 19], pre: None, post: Some(1), dev: Some(0), local: [] })))] })
incompat_term = Positive(Range { segments: [(Version(Version { epoch: 0, release: [0, 19, 0], pre: None, post: None, dev: None, local: [] }), Some(Version(Version { epoch: 0, release: [0, 19, 0], pre: None, post: Some(1), dev: Some(0), local: [] })))] })

These are supposed to be equivalent for PEP 440's Ord and Eq, but apparently something is going wrong there. And indeed, if I run with trio == 0.19.0 instead of trio == 0.19, then I get a proper failed resolution error. So I think this is my bug, not yours :-).

njsmith commented 3 years ago

Yep, found it: https://github.com/relrod/pep440-rs/issues/2

Eh2406 commented 3 years ago

In payment for the debugging assistants, I would happily accept a PR improving the panic message. :-) It should mention that: