garro95/priority-queue

DoublePriorityQueue panicked at 'called `Option::unwrap()` on a `None` value'

kleinesfilmroellchen opened this issue · 7 comments

kleinesfilmroellchen commented

I have now convinced myself that this is a bug in the library, as I'm commonly hitting this unwrap() that's inside priority_queue code. My use case is a Dijkstra implementation that uses

while let Some((current_node, current_distance)) = queue.pop_min() {

to get the next node out of a DoublePriorityQueue<usize, u32>. For several of my data sets and queue sizes of >~ 1 million elements, I'm hitting a None unwrap here:

thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', priority-queue-1.2.0\src\double_priority_queue\mod.rs:611:22
stack backtrace:
   0: std::panicking::begin_panic_handler
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\/library\std\src\panicking.rs:495
   1: core::panicking::panic_fmt
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\/library\core\src\panicking.rs:107
   2: core::panicking::panic
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\/library\core\src\panicking.rs:50
   3: enum$<core::option::Option<tuple$<ref$<usize>,ref$<usize>,ref$<u32> > >, 1, 18446744073709551615, Some>::unwrap<tuple$<ref$<usize>,ref$<usize>,ref$<u32> > >  
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\option.rs:746
   4: priority_queue::double_priority_queue::impl$8::heapify_min::closure$1<usize,u32,std::collections::hash::map::RandomState>
             at priority-queue-1.2.0\src\double_priority_queue\mod.rs:607
   5: core::iter::adapters::map::map_fold::closure$0<tuple$<ref$<usize>,ref$<usize> >,tuple$<ref$<usize>,ref$<usize>,ref$<u32> >,tuple$<ref$<u32>,tuple$<ref$<usize>,ref$<usize>,ref$<u32> > >,priority_queue::double_priority_queue::impl$8::heapify_min::closure$1,
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\adapters\map.rs:84
   6: core::iter::adapters::filter_map::filter_map_fold::closure$0<ref$<usize>,tuple$<ref$<usize>,ref$<usize> >,tuple$<ref$<u32>,tuple$<ref$<usize>,ref$<usize>,ref$<u32> > >,priority_queue::double_priority_queue::impl$8::heapify_min::closure$0,core::iter::adapt
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\adapters\filter_map.rs:37
   7: core::iter::traits::iterator::Iterator::fold<core::slice::iter::Iter<usize>,tuple$<ref$<u32>,tuple$<ref$<usize>,ref$<usize>,ref$<u32> > >,core::iter::adapters::filter_map::filter_map_fold::closure$0>
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\traits\iterator.rs:2171
   8: core::iter::adapters::filter_map::impl$2::fold<tuple$<ref$<usize>,ref$<usize> >,core::slice::iter::Iter<usize>,priority_queue::double_priority_queue::impl$8::heapify_min::closure$0,tuple$<ref$<u32>,tuple$<ref$<usize>,ref$<usize>,ref$<u32> > >,core::iter::
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\adapters\filter_map.rs:85
   9: core::iter::adapters::map::impl$2::fold<tuple$<ref$<usize>,ref$<usize>,ref$<u32> >,core::iter::adapters::filter_map::FilterMap<core::slice::iter::Iter<usize>,priority_queue::double_priority_queue::impl$8::heapify_min::closure$0>,priority_queue::double_pri
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\adapters\map.rs:124
  10: core::iter::adapters::map::impl$2::fold<tuple$<ref$<u32>,tuple$<ref$<usize>,ref$<usize>,ref$<u32> > >,core::iter::adapters::map::Map<core::iter::adapters::filter_map::FilterMap<core::slice::iter::Iter<usize>,priority_queue::double_priority_queue::impl$8::
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\adapters\map.rs:124
  11: core::iter::traits::iterator::Iterator::reduce<core::iter::adapters::map::Map<core::iter::adapters::map::Map<core::iter::adapters::filter_map::FilterMap<core::slice::iter::Iter<usize>,priority_queue::double_priority_queue::impl$8::heapify_min::closure$0>,
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\traits\iterator.rs:2216
  12: core::iter::traits::iterator::Iterator::min_by<core::iter::adapters::map::Map<core::iter::adapters::map::Map<core::iter::adapters::filter_map::FilterMap<core::slice::iter::Iter<usize>,priority_queue::double_priority_queue::impl$8::heapify_min::closure$0>,
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\traits\iterator.rs:2791
  13: core::iter::traits::iterator::Iterator::min_by_key<core::iter::adapters::map::Map<core::iter::adapters::filter_map::FilterMap<core::slice::iter::Iter<usize>,priority_queue::double_priority_queue::impl$8::heapify_min::closure$0>,priority_queue::double_prio
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\iter\traits\iterator.rs:2763
  14: priority_queue::double_priority_queue::DoublePriorityQueue<usize,u32,std::collections::hash::map::RandomState>::heapify_min<usize,u32,std::collections::hash::map::RandomState>
             at priority-queue-1.2.0\src\double_priority_queue\mod.rs:596
  15: priority_queue::double_priority_queue::DoublePriorityQueue<usize,u32,std::collections::hash::map::RandomState>::heapify<usize,u32,std::collections::hash::map::RandomState>
             at priority-queue-1.2.0\src\double_priority_queue\mod.rs:585
  16: priority_queue::double_priority_queue::impl$5::pop_min::closure$0<usize,u32,std::collections::hash::map::RandomState>
             at priority-queue-1.2.0\src\double_priority_queue\mod.rs:290
  17: enum$<core::option::Option<usize> >::and_then<usize,tuple$<usize,u32>,priority_queue::double_priority_queue::impl$5::pop_min::closure$0>
             at /rustc/efd0483949496b067cd5f7569d1b28cd3d5d3c72\library\core\src\option.rs:1055
  18: priority_queue::double_priority_queue::DoublePriorityQueue<usize,u32,std::collections::hash::map::RandomState>::pop_min<usize,u32,std::collections::hash::map::RandomState>
             at priority-queue-1.2.0\src\double_priority_queue\mod.rs:288
  19: [above caller code]

I'm too unfamiliar with the library internals to track the cause down. However, this is an example of a queue state that seems to cause it:

{
    2: (
        13,
        12183,
    ),
    4: (
        572405,
        12885,
    ),
    5: (
        5146,
        12947,
    ),
    1: (
        572406,
        12473,
    ),
    0: (
        570354,
        12327,
    ),
    12: (
        572397,
        12302,
    ),
    9: (
        569824,
        12186,
    ),
    7: (
        572381,
        12569,
    ),
    10: (
        572342,
        12712,
    ),
    11: (
        119993,
        12350,
    ),
    3: (
        572398,
        12495,
    ),
    6: (
        572382,
        12496,
    ),
    8: (
        572408,
        12675,
    ),
}

Happens on Rust Nightly 2021-10-27 and Rust Stable 1.56.0 x86_64-pc-windows-msvc.

kleinesfilmroellchen commented

To clarify: I was using the priority queue differently beforehand, inserting all graph nodes which means about 50 million for my largest dataset. However, this new method keeps the number of current nodes commonly below 100, which either way didn't solve the issue described.

garro95 commented

Hi @kleinesfilmroellchen, sorry for the delay, but I have been very busy and I could not respond to this issue as promptly as I wanted.
Can you please provide me a sequence of operations that make the queue crash? It would be very useful to find the bug.
Thanks in advance

kleinesfilmroellchen commented

That's hard to do, as the bug usually occurs after several thousand operations on the queue. However, through some debugging I found the following:

  • When an element is pushed into the queue, it appears to be added to the IndexMap correctly.
  • However, when later the queue is heapified, this element is missing. When debug printing self.store.map in the closure after map.rs line 651, it crashes. Modifying the debug implementation to not unwrap, the output data structure has a single None at the newly added item. As far as I can tell (the internal data structures are hard to understand) this means that the element is in the heap, but not in the index map (or something? idk). The element is currently at the end after being inserted, so maybe that also plays into it. Honestly, the control flow is too hard for me to understand and I gave up.
  • The bug appears both with heapify_min and heapify_max, though I have only deeply investigated heapify_max. It also happens when manually heapify()-ing the priority queue (I made the function public for testing) after performing push(). Though I don't know if that should just be no-oping or if the data structure can't handle multiple (manual) heapifications.

Hope this helps. I have to switch to standard library BinaryHeap because deadline, but thanks for investigating this.

garro95 commented

Thank you for your report. Could you post at least the full log? It would be very helpful

kleinesfilmroellchen commented

I don't quite understand. What I posted above is the full log, everything else is stuff from my application. I just added a {:#?} to print the queue. To print all queue states is impossible; they easily fill up my terminal history by the time it crashes.

garro95 commented

@kleinesfilmroellchen I think I fixed the bug and I could not reproduce it anymore. I would be very grateful if you could confirm it. Thank you in advance for your time

kleinesfilmroellchen commented

Just verified, yes, it doesn't crash now and the algorithm results are fully correct. Thank you so much, our project will probably switch back to priority_queue!

  • 🎉1