While fuzzing some of my own code, I ran across a bug in imbl::Vector: append somehow panics!

This happens when appending together big imbl::Vector<u8>s:

thread 'main' panicked at 'Chunk::pop_front: can't pop from empty chunk', /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/sized-chunks-0.6.5/src/sized_chunk/mod.rs:399:13
stack backtrace:
   0: std::panicking::begin_panic
             at /rustc/c8dfcfe046a7680554bf4eb612bad840e7631c4b/library/std/src/panicking.rs:541:12
   1: sized_chunks::sized_chunk::Chunk<A,N>::pop_front
             at /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/sized-chunks-0.6.5/src/sized_chunk/mod.rs:399:13
   2: imbl::nodes::rrb::Size::pop
             at /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/imbl-1.0.1/./src/nodes/rrb.rs:110:37
   3: imbl::nodes::rrb::Size::pop
             at /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/imbl-1.0.1/./src/nodes/rrb.rs:126:9
   4: imbl::nodes::rrb::Node<A>::push_chunk
             at /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/imbl-1.0.1/./src/nodes/rrb.rs:610:25
   5: imbl::nodes::rrb::Node<A>::push_chunk
             at /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/imbl-1.0.1/./src/nodes/rrb.rs:646:23
   6: imbl::vector::RRB<A>::push_middle
             at /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/imbl-1.0.1/./src/vector/mod.rs:1637:19
   7: imbl::vector::Vector<A>::append
             at /home/miyuruasuka/.cargo/registry/src/github.com-1ecc6299db9ec823/imbl-1.0.1/./src/vector/mod.rs:1053:21

Does this ring a bell? I will try to find a minimal reproducible case tomorrow --- unfortunately, the fuzzing input that led to this is long and complicated.

This is just something I was wondering about, having used im on a number of projects, Sometimes there is just minor differences of naming between im and the std::collections.

for instance in im difference in HashSet, and OrdSet is an alias for symmetric_difference, while in std difference is equivalent to the im function relative_complement.

I'm not sure how I would go about aligning more closely in this case, probably deprecate, difference, remove it. then after a period of time introduce a feature to enable a difference alias for relative complement.

I figured it was at least worth considering, if only to gauge reaction, but definitely feel free to close if compat is considered more important.

This is my own rust formatting style file, fixed to try to keep everything within 80 columns wide so that I can see multiple files side by side. At this point, all trailing whitespace has been removed, every file ends with a newline, and all tabs have been converted to spaces.

Hello, I'm wondering if the trait bound A: Clone when implementing Debug for Vector<A> is necessary. https://github.com/jneem/imbl/blob/3fd258cee59499cac0243822903497c83fb00e6a/src/vector/mod.rs#L1784 Previously those bounds are removed for maps and sets (see https://github.com/bodil/im-rs/issues/81). Can the same thing be done to Vector?

As seen here, src/lib.rs currently contains the following line.

#![deny(unsafe_code, nonstandard_style)]

However, imbl (as a fork of im) makes frequent use of #[allow(unsafe_code)]. A quick rg -cF '#[allow(unsafe_code)]' reveals the following 24 instances of allowed unsafe code throughout the library.

src/vector/focus.rs:7
src/vector/mod.rs:8
src/nodes/hamt.rs:5
src/nodes/btree.rs:3
src/util.rs:1

I think it's a little misleading to have the deny(unsafe_code) when we just go ahead and allow(unsafe_code) wherever we need it. It also adds a small development burden to have to add allow(unsafe_code) if you want/need to use unsafe.

Hey, thank you for forking and taking your time to merge the fixes!

Judging the commit e84fe764003a924bd5c04d4dd2f1e0accc3c3654 I assume that you've decided to only keep the arc version of im and ditch im-rc.

So I am surprised to see, that the following code

use std::sync::Mutex;
use std::thread;

extern crate imbl;

fn main() {
    let x : Mutex<imbl::Vector<u32>> = Mutex::new(imbl::Vector::new());

    thread::spawn(move || {
      let _ = x;
    });
}

Compiles fine with the commit right before removing the Rc implementation

[dependencies]
imbl = {git="https://github.com/jneem/imbl.git", rev="67ce8b5976941fbf2d1c96f5c68e868a497237d8"}

But doesn't compile after removing the Rc implementation

[dependencies]
imbl = {git="https://github.com/jneem/imbl.git", rev="e84fe764003a924bd5c04d4dd2f1e0accc3c3654"}

error[E0277]: `Rc<sized_chunks::sized_chunk::Chunk<usize>>` cannot be sent between threads safely
   --> src/main.rs:10:5
    |
10  |     thread::spawn(move || {
    |     ^^^^^^^^^^^^^ `Rc<sized_chunks::sized_chunk::Chunk<usize>>` cannot be sent between threads safely
    |
    = help: within `Vector<u32>`, the trait `Send` is not implemented for `Rc<sized_chunks::sized_chunk::Chunk<usize>>`

I am using rustc 1.54.0 (a178d0322 2021-07-26) on Ubuntu 21.4

• [ ] 104 (improve vec iterator performance. Has some bugs, but probably worthwhile fixing it up)
• [x] 150
• [x] 154
• [x] 155 (clone for by-ref iterators. Blocked on changes to sized-chunks)
• [x] 158
• [x] 160 (Make empty hashmaps not depend on random state. I think this is better fixed by making hashmaps non-Hash (and maybe also non-Ord, see #175)
• [x] 161 (Adds a convenience method, seems worthwhile. Get it in after 1.0, because 1.0 shouldn't change API)
• [x] 163 (Merge smaller maps into larger ones)
• [x] 164
• [x] 165
• [x] 168 (Lifetime change; not sem-ver compatible, so after 1.0)
• [x] 170
• [x] 173
• [x] 176
• [x] 177
• [x] 178
• [x] 179
• [x] 180
• [x] 183
• [x] 184
• [x] 186
• [x] 189
• [x] 191
• [x] 192
• [x] 193

Here is a PR as promised in issue #56

I'd still like to go through the docs, and see if anything else jumps out at me, and wait for feedback from others though.

Edit: The only usages of it are in the doctests for the alias itself afaict.

When using a type with a lifetime parameter as key for imbl::HashMap, read-only methods like get will not accept keys with shorter lifetimes. For example:

use imbl::HashMap;
use std::borrow::Cow;

#[derive(Clone, Debug, Hash, PartialEq, Eq)]
struct Key<'a> {
    key1: Cow<'a, str>,
    key2: Cow<'a, str>,
}

fn main() {
    let mut map: HashMap<Key<'static>, String> = HashMap::new();
    map.insert(
        Key {
            key1: Cow::Borrowed("some key 1"),
            key2: Cow::Borrowed("some key 2"),
        },
        String::from("some value"),
    );

    let key1 = String::from("some key 1");
    let key2 = String::from("some key 2");

    eprintln!(
        "{:?}",
        map.get(&Key {
            key1: Cow::Borrowed(&key1),
            key2: Cow::Borrowed(&key2)
        })
    );
}

When compiling this, the compiler complains that key1 and key2 do not live long enough; it requires that they are borrowed for 'static, even though it seems get should only need the key being available for the duration of the function call. I believe this is due to imbl::HashMap being invariant over its key parameter. The same example compiles and works as expected using std::collections::HashMap.

Would it be possible to make imbl::HashMap covariant over the key type? Or is there a reason this is not possible?

Updates the requirements on arbitrary to permit the latest version.

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

#[derive(Debug, Clone, Hash, PartialEq, Eq)]
pub struct Node {
    pub ord: u32,
    pub id: u32,
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.ord.cmp(&other.ord)
    }
}

fn main() {
    use imbl::ordset::OrdSet;
    let mut s = OrdSet::<Node>::new();
    s.insert(Node { ord: 2, id: 1 });
    s.insert(Node { ord: 2, id: 2 });
    println!("{:?}", s.len()); // 1
}

The output is 1.

It looks like im is starting to get some maintenance again, so might be useful to feed the bug fixes you've made (to Vector IIRC?) back upstream. And more broadly seeing if you can collaborate.

A bunch of things critical for pooling to actually be used are gated under the pool feature (ex. HashMap::with_pool(), but the pool feature doesn't exist

Prompted by #33, I dug into Vector some more this weekend and I'm not super encouraged by what I found. I made some tweaks to support smaller branching factors (because when the branching factor is large then it's really hard to hit corner cases with proptesting and fuzzing), and I immediately ran into some failed tests. In particular, test_inserts caused a panic, and when debugging the panic I found that it was producing very large skinny trees. Now some issues may have been caused by my amateurish attempts to support smaller branching factors, but the skinny tree thing seems to be an issue in unmodified im also: if I modify test_inserts to make larger vectors, I see that vectors of length 40000ish already have tree height 7. But with a branching factor of 64, height 3 should already get us to 200k!

Part of my difficulty is that I don't really understand the RRB merge algorithm. The description in the original paper is not really complete, in my opinion, and neither is the one in L'orange's Masters thesis. It appears I'm not the first person with this complaint, see this, and also this and this for more background. @nomad010 you said you had an independent re-implementation of the RRB algorithm -- do you have any thoughts on this?

We have unsafe code in a few places, and the invariants that need to be upheld are not always well-documented.

• [x] in Vector::swap we use unsafe because rust doesn't know that pointers to different indices are non-overlapping. I think this is fine, although it could be removed at the cost of a clone() and an extra swap.
• [ ] in the hash table, there is unsafe code in insert, because we need to move out of something before we're ready to move a new value in. This could be removed at the cost of an additional "uninitialized" enum variant in Entry. I'm not sure what the cost of that is.
• [ ] there's some unsafe code related to the "pool" feature. This code is currently disabled in imbl (it's only relevant when using Rc instead of Arc, and we don't have that yet). This part is therefore a lower priority.
• [ ] there is a bunch of unsafe code dealing with Focus and FocusMut. This will take some time to figure out. There's some subtlety in FocusMut::split_at and FocusMut::unmut.