Panic when appending two vectors

[nullchinchilla]

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.

[jneem]

Thanks for the report! I'm not aware of the bug, so I'd very much appreciate a test case. Even a long one would be a start.

By the way, did you check whether the panic happens with im? It's fairly likely that it does, because we haven't changed much Vector code, but it would be nice to know...

[nullchinchilla]

I figured out a somewhat close to minimal test case:

    fn testvec(n: usize) -> imbl::Vector<u8> {
        imbl::Vector::from(vec![0u8; n])
    }

    fn append(mut x: imbl::Vector<u8>, y: imbl::Vector<u8>) -> imbl::Vector<u8> {
        x.append(y);
        x
    }

    fn cons(x: u8, mut y: imbl::Vector<u8>) -> imbl::Vector<u8> {
        y.push_front(x);
        y
    }

    fn main() {
        let v7 = append(testvec(0), testvec(0));
        let v7 = append(testvec(32), v7);
        let v7 = append(testvec(0), v7);
        let v7 = cons(0, v7);
        let v7 = append(testvec(4096), v7);
        let v7 = append(testvec(32), v7);
        let v7 = append(testvec(32), v7);
        let v7 = append(testvec(0), v7);
        let v7 = cons(0, v7);
        let v7 = append(testvec(4096), v7);
// CRASHES HERE
    }

[nullchinchilla]

This doesn't happen when cons is replaced by a version that uses append, or if I directly create vectors and append them, so a wild guess is that push_front is somehow messing up the data structure.

[jneem]

Thanks! This reproduces for me too (and also when using im).

[nullchinchilla]

Since we use imbl in production, it's pretty important that this gets fixed ASAP. Is there anything I can help with?

[jneem]

I can have a look starting in around 12 hours. If you want to look before then, I'd put it a test in src/vector/mod.rs and sprinkle calls to assert_invariants around, to try to figure out at which point the invariants are breaking.

[nullchinchilla]

Any leads on this? Sorry I haven't gotten around to looking at this yet

[jneem]

Some leads, but no solution yet. You can see the crash branch (and the crash test in src/vector/mod.rs) for what I have so far. I've narrowed down the bug to promote_front, which for some reason creates an empty subtree of the root (and then later popping on that subtree causes the panic).

I can probably find some more time tomorrow night (i.e. 24 hours from now) to look more.

[jneem]

I think I have a fix. Besides the specific details of this bug, there's a general issue in this crate that the node sizes are so big that the testing doesn't often catch these edge cases. I've been mitigating that in OrdMap and OrdSet by testing it with smaller node sizes, but it's a little more complicated for Vector...

[jneem]

@nullchinchilla have you had a chance to test the PR? I fuzzed it over the weekend without finding any problems.

[nullchinchilla]

Yeah, it does avoid the crash and can certainly be merged, though I've decided to switch to implementing B-tree-based persistent vectors myself due to general code quality concerns with imbl and RRB trees being quite complicated. I will certainly publish what I end up with onto crates.io once done :)

[jneem]

Fair enough! I'm hoping we'll address those issues in #35, but it certainly won't be instant...