generation problems with Arena::clear() and Arena::drain(), and other drain() problems

[zdanz]

Looking at the code I was a bit surprised to see that Arena's generation isn't incremented each time an element is inserted; rather, it's incremented only when an item is removed. So generation doesn't climb quite as quickly as it would have, which is nice; but also, there are more special cases. Some of them aren't handled properly:

1. If you add some elements and then use Arena::clear(), this should bump the arena's generation, but it doesn't. So if you add some more elements afterwards, you can have a new element with the exact same Index as one of the cleared elements, and so you can access it with a stale Index, which is wrong.
2. If you add some elements and then use Arena::drain(), again, this should bump the generation and it doesn't, which is a similar bug.
3. There may be more special cases which aren't handled properly; I'm not sure. (For example, is there a way to swap a new element in in-place? If so it needs to bump generation, too.) I was just looking at the crate to see if I want to use it, so I don't have a stress test for it or anything. But I'd recommend adding some more testing to make sure that once an Index becomes stale, it won't ever fetch an element anymore.

While checking 2., I hit another bug with drain():

4. drain() doesn't fix up the free list or other state. After you drain the whole arena, is still has a positive len(). Then you'll get asserts when you try to use the arena. I'm not sure what exactly will be involved to fix this.

Here is some code which I added to the end of the example from README.md, to demonstrate the problems:

println!("murray is {}", arena[murray]);
println!("Arena = {:?}", arena);    // shows that arena.generation == 1 here
arena.clear();
println!("Cleared, len = {}", arena.len());
println!("Arena = {:?}", arena);    // shows that arena.generation still == 1 here
arena.insert("n1");
arena.insert("n2");
arena.insert("n3");

for (idx, value) in &arena {
    println!("{:?} is at {:?}", value, idx);
}
assert!(arena.contains(murray));
println!("murray is {}", arena[murray]);    // this is already a bug: the index murray still works when it should not

for (idx, value) in arena.drain() {
    println!("Draining {:?} from {:?}", value, idx);
}
println!("Drained, len = {}.", arena.len());    // Another bug, unrelated to first: len = 3 here

println!("Arena = {:?}", arena);    // but as I wanted to see, this shows that arena.generation STILL == 1 here

for (idx, value) in &arena {
    println!("{:?} is at {:?}", value, idx);    // And now this asserts
}

With this code added, the example generates the following output:

The gza gza genius: Gary Grice
"Robert Fitzgerald Diggs" is at Index { index: 0, generation: 0 }
"Gary Grice" is at Index { index: 1, generation: 0 }
"Bill Murray" is at Index { index: 2, generation: 1 }
murray is Bill Murray
Arena = Arena { items: [Occupied { generation: 0, value: "Robert Fitzgerald Diggs" }, Occupied { generation: 0, value: "Gary Grice" }, Occupied { generation: 1, value: "Bill Murray" }, Free { next_free: None }], generation: 1, free_list_head: Some(3), len: 3 }
Cleared, len = 0
Arena = Arena { items: [Free { next_free: Some(1) }, Free { next_free: Some(2) }, Free { next_free: Some(3) }, Free { next_free: None }], generation: 1, free_list_head: Some(0), len: 0 }
"n1" is at Index { index: 0, generation: 1 }
"n2" is at Index { index: 1, generation: 1 }
"n3" is at Index { index: 2, generation: 1 }
murray is n3
Draining "n1" from Index { index: 0, generation: 1 }
Draining "n2" from Index { index: 1, generation: 1 }
Draining "n3" from Index { index: 2, generation: 1 }
Drained, len = 3.
Arena = Arena { items: [], generation: 1, free_list_head: Some(3), len: 3 }
thread 'main' panicked at 'assertion failed: (left == right)
left: 3,
right: 0', [elided]\generational-arena-0.2.7\src\lib.rs:995:21

[fitzgen]

Thanks for filing a bug report!

Are you interested in making a PR to add these generation bumps?

[zdanz]

I'm not familiar enough with the crate to be sure it's the right solution:

• As I mentioned above, there might be cases I'm not aware of which also need a bump added.
• Maybe it would be better to bump on insertion rather than removal (perhaps bumping the generation currently stored there, rather than an Arena-wide generation).
• Since drain() seems to be more seriously broken, it might be that whatever fix it requires will interact somehow.

If you're nevertheless interested in a PR that does nothing except the bare minimum right now (bump generation in these two spots), I could make one. :-)

ETA: For the more serious drain() issue, it might be possible to PPYP by setting arena.len to 0 and arena.free_list_head to None before invoking Vec::drain(). I don't know if this will really work, or if it's the best thing. It might be better to give up on using Vec::drain() and "just" implement a drain() which turns Occupied entries into Free ones as it iterates through them. But this is above my pay grade; I wouldn't feel confident trying to implement either one of these solutions.

[Herschel]

I was just bit by this bug from an arena.clear() -- I could take a shot at a PR for some of these issues if desired?

[taiki-e]

1. will be fixed in #44, 2. and 4. will be fixed in #45.