Miri failure in btree::map::test_iter_min_max test #73915
Comments
|
I suspect this is caused by #73627 |
jonas-schievink
added
A-collections
|
Oops, I forgot about Miri while testing. But it baffles me that it fails. |
|
More accurately, the recent test never succeeded (under Miri). The failing part is unrelated to the main change in #73627, I just added lines for the iterators So what next? I could take out these testing lines from #73627 since they're not directly related to the change, create a new test case, but will probably not understand what is wrong. PS it's only |
|
@ssomers could you share an MRE demonstrating the problem, ideally unrelated to your changes? Then I can investigate. |
|
|
Nope, that was not minimal. It fails even without the |
|
This seems to pass Miri on the playground though? fn main() {
let mut a = std::collections::BTreeMap::new();
a.insert(1, 1);
a.insert(2, 2);
a.iter_mut().min();
}This fails: fn main() {
let mut a = std::collections::BTreeMap::new();
a.insert(1, 1);
a.insert(2, 2);
a.iter_mut().map(|(_,v)| v).min();
}So I'll make that the one to investigate. Thanks! |
|
I think it succeeds on playground because #73627 is already on there and that inadvertently fixed |
|
Miri is nightly-only. The stable/beta/nightly selection in the left has no effect at all on the tools menu. |
|
The protector that is being violates is of fn fold<B, F>(mut self, init: B, mut f: F) -> B
where
Self: Sized,
F: FnMut(B, Self::Item) -> B,
The conflict is from this call to rust/src/liballoc/collections/btree/node.rs Line 816 in 9491f18 This calls |
|
Fixing rust/src/liballoc/collections/btree/node.rs Line 511 in 9491f18 Something seems to be very fundamentally wrong here: that code is creating a slice covering all keys and values, but this happens during iteration where the user also has access to some of these keys and/or values! |
|
Here's another way to trigger the same problem: use std::mem;
fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) {
// Gather all thrse references
let mut refs: Vec<&mut T> = iter.collect();
// Use them all. Twice, to be sure we got all interleavings.
for r in refs.iter_mut() {
mem::swap(dummy, r);
}
for r in refs {
mem::swap(dummy, r);
}
}
fn main() {
let mut a = std::collections::BTreeMap::new();
a.insert(1, 1);
a.insert(2, 2);
test_all_refs(&mut 13, a.values_mut());
}Writing |
|
I don't fundamentally understand what's wrong with (internally) creating a slice of references and handing them out to the public one by one carefully, but I mention that it is possible to avoid the slice altogether. This was a way to avoid complicated code that have been dealt with in other ways meanwhile. I'll have a look what Miri says about this and the new test nowadays. |
|
I started in https://github.com/RalfJung/rust/tree/btree-raw to use raw pointers more, but when I realized I'd have to change all that slice code I stopped -- I don't have the time for that right now I'm afraid. And maybe getting rid of slices is indeed better. :)
The problem is that the code is not doing it carefully enough. :) BTree does the equivalent of: let mut data = [1, 2, 3];
let slice = &mut data[..];
let ptr1 = &mut slice[0]; // handing this out to the user
let slice = &mut data[..]; // Uh-oh! This slice *overlaps* with the reference the user got!
let ptr2 = &mut slice[1]; // handing this out to the user
// Now as a user, try using both ptr1 and ptr1...
mem::swap(ptr1, ptr2);
// The borrow checker says "no", because when we created the 2nd "slice", we invalidated "ptr1".BTree does the same thing, except it uses raw pointers so the borrow checker does not see what happens. When it creates the second slice, that overlaps with an existing mutable reference that was previously given to the user, and that is disallowed by the aliasing rules. If BTree created the slice once and then kept giving out references, that would be fine. But when you create a new Does this make sense? |
|
I think I understand, but at some point I thought I understood the #133 discussion on stacked borrows and some of the stacked borrows paper (say 10%, using hexadecimal notation...), but it doesn't stick. Replacing slices with (raw??) pointers doesn't help. I'm guessing because |
|
The code still does Try |
|
I can build on your I don't understand the previous |
disable BTree min_max test in Miri for now Until rust-lang#73915 is fixed, better skip this test in Miri so that we can test the others at least.
disable BTree min_max test in Miri for now Until rust-lang#73915 is fixed, better skip this test in Miri so that we can test the others at least.
Yeah, you cannot... you have to avoid that API. The point of that function is to avoid having to cast raw pointers. Casting raw pointers is extremely fragile, because even if the source type changes, the cast will still work. Thus I think one should try very hard to never directly cast one raw ptr type to another, and instead always go through some method which constrains what the cast can do. |
btree::map::test_iter_min_maxrecently started failing in Miri:(Sorry for the bad spacing, Travis logs are like that...)
The text was updated successfully, but these errors were encountered: