Fix `Bump::shrink` illegal copies

[overlookmotel]

Fixes #230.

Or at least I think I've understood what the problem is here. Previously could end up with overlapping copies when old_size is an odd number.

[fitzgen]

Would you be up for sending a follow up pull request to implement these additional two things?

@overlookmotel can you confirm whether or not you are planning to do this? It is 100% totally fine if you are not, but in that case I want to know so that I can put it on my TODO list.

[overlookmotel]

I'd be happy to do the first, but I haven't got a clue how quickcheck works. Am reading the docs now. If I can figure it out, I'll be happy to do that too.

[overlookmotel]

2 questions on the first:

Do you mean for all copy_nonoverlapping usage in bumpalo, or just the specific one in shrink?

Is debug_assert! required? In debug mode, it seems that copy_nonoverlapping does exactly that anyway (hence the test failure): https://doc.rust-lang.org/src/core/intrinsics.rs.html#2684-2704 https://doc.rust-lang.org/src/core/intrinsics.rs.html#2536-2557

[fitzgen]

The quickcheck tests live in tests/all/quickchecks.rs. Here is a simple quickcheck test: https://github.com/fitzgen/bumpalo/blob/7b3fd17f73b48ed874ec68ebc7970354c8c74be8/tests/all/quickchecks.rs#L231-L237

It is "property-based testing" (which is pretty much the same as fuzzing, but kind of a separate community due to historical accidents) where you write a "property" which is a function that takes some input, runs your program/library on it, and asserts something about the result. The quickcheck library itself is responsible for generating a bunch of inputs and running them through the property. In bumpalo, our properties are often just "no assertions were triggered when allocating the given stuff", but there are a few others if you read through the tests.

[fitzgen]

Do you mean for all copy_nonoverlapping usage in bumpalo, or just the specific one in shrink?

I had been thinking about just this particular case, but since we do call it in multiple places, it would make sense to define a helper that does the assert and use that everywhere we currently call copy_nonoverlapping directly. But...

Is debug_assert! required? In debug mode, it seems that copy_nonoverlapping does exactly that anyway (hence the test failure): https://doc.rust-lang.org/src/core/intrinsics.rs.html#2684-2704

You're right that actually this probably isn't necessary. It actually didn't used to be the case that debug assertions in std/core methods would trigger in downstream crates that used those methods because std/core is always pre-compiled in release mode, and then linked into downstream crates (even when the downstream crate is compiled in development mode).

But it seems that has changed or they have a new kind of assert that is preserved? So yeah I guess this debug assertion isn't necessary for us to write, since it already exists (and can be triggered) upstream.

[overlookmotel]

I'm sorry, but I'm not having luck with this. I don't think I understand the logic of when can shrink or grow, while also changing alignment.

This is where I got to, but it fails on the case ((2, 0), (0, 2)):

fn allocator_grow_or_shrink(layouts: Vec<((usize, usize), (usize, usize))>) -> bool {
    fn to_layout(size: usize, align: usize) -> Layout {
        const MIN_SIZE: usize = 1;
        const MAX_SIZE: usize = 1024;
        const MIN_ALIGN: usize = 1;
        const MAX_ALIGN: usize = 64;

        let align = usize::min(usize::max(align, MIN_ALIGN), MAX_ALIGN);
        let align = usize::next_power_of_two(align);

        let size = usize::min(usize::max(size, MIN_SIZE), MAX_SIZE);
        let size = size.next_multiple_of(align);

        Layout::from_size_align(size, align).unwrap()
    }

    let mut layout_iter = layouts.into_iter();
    while let Some(((initial_size, initial_align), (new_size, new_align))) = layout_iter.next() {
        let initial_layout = to_layout(initial_size, initial_align);
        let new_layout = to_layout(new_size, new_align);

        let b = AllocatorDebug::new(Bump::new());

        let pointer = b.allocate(initial_layout).unwrap();
        if !is_pointer_aligned_to(pointer, initial_layout.align()) {
            return false;
        }

        let new_pointer = if new_layout.size() <= initial_layout.size() {
            unsafe { b.shrink(pointer.cast(), initial_layout, new_layout) }.unwrap()
        } else {
            unsafe { b.grow(pointer.cast(), initial_layout, new_layout) }.unwrap()
        };

        if !is_pointer_aligned_to(new_pointer, new_layout.align()) {
            return false;
        }
    }

    true
}

Also, the test allocator_shrink_align_change includes:

let size = usize::min(usize::max(size, MIN_SIZE), MAX_SIZE);
let size = usize::max(size, align);

But don't all allocations have to have size a multiple of align (i.e. size = size.next_multiple_of(align)) not just size >= align?

I'm afraid I think I need to bail out at this point! I only really wanted to get #229 merged, and made this fix to get CI to pass. But I'm afraid I'm now a bit short of time to continue on. Sorry.