Panics and infinite loops

[njsmith]

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 <root>, allowed range is: 0
Chose package <root>; now let's decide which version
<---- decision: root package magic version 0
----> pubgrub called get_dependencies <root> 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<P,V>::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<P,V>::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<P,V>::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<P,V>::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<P,V>::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 <root>, allowed range is: 0
Chose package <root>; now let's decide which version
<---- decision: root package magic version 0
----> pubgrub called get_dependencies <root> 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::<impl *const T>::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::<impl *const T>::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<T>::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::<impl [T]>::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 <T as alloc::slice::hack::ConvertVec>::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::<impl [T]>::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 <alloc::vec::Vec<T,A> 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 <pep440::Version as core::clone::Clone>::clone (
    self=0x7fffffff0110)
    at /home/njs/.cargo/registry/src/github.com-1ecc6299db9ec823/pep440-0.1.1/src/lib.rs:101
#8  0x00005555557e2a32 in <posy::vocab::version::Version as core::clone::Clone>::clone (
    self=0x7fffffff0110) at src/vocab/version.rs:9
#9  0x00005555557c58c6 in <T as alloc::borrow::ToOwned>::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<V>::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<V>::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<P,V>::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<P,V>::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<P,V>::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<P,V>::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<P,V>::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<V>::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<V>::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<P,V>::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<P,V>::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<P,V>::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<P,V>::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<P,V>::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]

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:

• // XX this error reporting is terrible we can make it send (in 0.3), please open and Issue about that.
• // why can't I call ::new on this? you can call DependencyConstraints::default() but we should probably add a new.
• extras that is the best approach we have found so far. cc "features" advanced_dependency_providers#1 While we are at it, it is not clear how we are going to correctly handle pre releases, so you may want to look at Support for more complex version constraints #86 and linked discussions.

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]

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]

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]

Yep, found it: relrod/pep440-rs#2

[Eh2406]

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

• This should not be possible.
• That it is likely to be inconsistent behavior of your Version with Ord, Eq, or pubgrub::version::Version
• The package where it occurred
• Possibly: accum_term and incompat_term while you are at it