7 ms·
Rust, Lifetimes, and Collections
- kibwen 12y agoThe backstory here is that Alexis is a community member who came to Rust with a strong interest in improving the quality of the data structures in our stdlib, many of which had deteriorated significantly over the years through neglect and language upheaval. He began by compiling an enormous list of general cleanups[1] which eventually sparked an RFC for wide-scale collections reform[2] which was accepted and has begun work in earnest.[3] It's an enormously impressive effort that has engaged tons of new contributors, and goes to show what even a single driven community member can achieve. [1] https://github.com/rust-lang/rust/issues/18009 https://github.com/rust-lang/rust/issues/18009 [2] https://github.com/rust-lang/rfcs/pull/235 https://github.com/rust-lang/rfcs/pull/235 [3] https://github.com/rust-lang/rust/issues/18424 https://github.com/rust-lang/rust/issues/18424
- rdtsc 12y agoI am trying to understand how these two statements work together. 1) > unsafe code is infectious like Java's exceptions. If you call an unsafe function, you need to mark yourself as unsafe, or explicitly state the boundaries where the unsafety is handled. 2) > Unsafe is for the lowest levels of abstraction to deal with So according to 1) unsafe code is infectious but according to 2) you should only use it at the lowest level in your code. By this I understand things like mmap-ing a file, get a value out of shared memory, interacting with C code and so on. Presumably if your high level code depends on low level code, wouldn't the lower level "usafety" bubble all the way to the top. And next thing your main do_top_level_business_logic() function has to be wrapped in an unsafe block? Now while typing this I am thinking of maybe one way to handle is and that is to create a separate task and shuffle data via messages between another unsafe task. If task crashes just restart it...
- Hemospectrum 12y agoIt bubbles up as far as an `unsafe { ... }` block, but no higher.
- vutekst 12y agoYes, presuming that the author of the unsafe code in question has manually verified the effective safety in all relevant scenarios. `unsafe` is an assertion to the Rust compiler that you know what you're doing, and you will preserve its guarantees as far as external observers are concerned. I might point out to the grandparent post that even the basic vector collection in Rust is full of unsafe {} blocks.
- rdtsc 12y agoI understand now, thanks for explaining. It was implied in the article too, by analogy with java's exceptions, I just forgot how that works too.
- kibwen 12y agoTo clarify, there are two places that you can use the `unsafe` keyword: unsafe { /* arbitrary code in here */ } // applied to a block unsafe fn foo() { /* function body */ } // applied to a function It's the second form that is infectious. When applied to a function, that function can only be called from an unsafe block or another unsafe function. The use of this form is to say, "hey, as the author of this function, I have no ability to determine whether or not this function is safe to use; let the caller beware." However if, as the author of a function, you can take steps to ensure that the function is used safely, then you can stop the infection with an unsafe block. For illustration, let's do one of the things mentioned in the post. Here's a function that prints every element in a vector: fn foo1(v: Vec<int>) { let length = v.len(); let mut i = 0; while i < length { println!("{}", v[i]); i += 1; } } That `v[i]` in there is potentially doing bounds checking (in practice a simple case like this would get optimized away by LLVM, but let's ignore that), but note that this is superfluous because we've written this code such that `i` will always be a valid index. So let's turn off bounds checking by using the `unsafe_get` method mentioned in the OP: fn foo2(v: Vec<int>) { let length = v.len(); let mut i = 0; while i < length { println!("{}", unsafe { v.unsafe_get(i) }); i += 1; } } Like I was saying above, `unsafe_get` is a function that is itself marked unsafe, because the author of `unsafe_get` knows that you can cause memory unsafety by passing in an invalid index. But because we've written this program carefully, we know that both foo1 and foo2 are exactly as safe, so we've fenced off the unsafety here with the `unsafe` block. Both foo1 and foo2 can be called from safe Rust code with no special consideration. Now, what happens when, years down the road, someone who isn't paying attention accidentally modifies this function? fn foo3(v: Vec<int>) { let length = v.len(); let mut i = 0; while i <= length { // look carefully println!("{}", unsafe { v.unsafe_get(i) }); i += 1; } } This version of the function contains an off-by-one error. Anyone calling foo3 will try to index beyond the end of the array, and all hell will break loose. What do you do then? Well, you grep for the word "unsafe" and you start auditing unsafe blocks, looking at all the inputs that you send into them. This is generally the same approach you'd take in any other systems language, except that by limiting where unsafe code can appear you reduce the code that can potentially go wrong by 10-100 times, and speed up your auditing commeasurably. And the promise made in the OP stands: if you don't yourself use `unsafe` code and memory safety happens, it's someone else's fault, not yours. :) And how often do you need to resort to unsafe code in Rust? It depends on your domain. Efficient data structures often require all sorts of custom pointer tricks, so maybe a tenth to a third of their code is unsafe in Rust. For application-level programming, I'd expect no more than 1-3% unsafe code (maybe up to 5-10% if you're trying to push performance to the absolute limit, like Servo is doing).
- Animats 12y agoBut, with a little sprinkle of unsafe inside this method, we can make it happen. Uh oh. If you have to turn off subscript checking in Rust for "performance" for simple loop iteration, something is very wrong. The way this ought to work is by the compiler hoisting checks out of the loop. Consider let mut v = vec![1i32, 2, 3, 4, 5]; let vlen = v.len() for i in range(0, vlen) { let x = &mut v[i]; // do some work with x } (Have to double space due to lack of formatting capabilities here.) Subscript checking requires something comparable to "assert(i >= 0 && i < v.len())" at the subscript check v[i] The compiler, knowing how "for" works, can hoist that check out of the loop, so it becomes "assert(0 >= 0 && vlen-1 < v.len())" at the the top of the loop, before the FOR statement is entered. Now the check only has to be executed once. This optimization is valid for all iterative FOR loops where the iteration variable and the array are not modified within the loop, and the compiler has to check that. Then, after hoisting, some algebraic simplification can be applied to the expression in the assert. This requires a small theorem prover, or more cheaply, some rewrite rules for the common cases. "assert(true && vlen <= v.len())" "assert(vlen <= v.len())" Now, flow analysis shows that, at the point of the assert, vlen = v.len(). So we get "assert(v.len() <= v.len())" and finally "assert(true)" which is eliminated as dead code. Zero overhead for subscript checking, yet proved correct. Now that's how it ought to work. One of the Go compilers does this for simple loops like this. Sprinkling "unsafe" around, and making people use funny library constructs for simple loops, is doing it wrong. This seems to be a forgotten technology. There were Pascal compilers in the 1980s which did this. In practice, about 95% of subscript checks could be optimized out for Pascal. You can almost always get checks out of iterative inner loops, which is where they really matter.
- haberman 12y ago> (Have to double space due to lack of formatting capabilities here.) Indent by four spaces to get a <pre> tag: let mut v = vec![1i32, 2, 3, 4, 5]; let vlen = v.len() for i in range(0, vlen) { let x = &mut v[i]; // do some work with x } > This seems to be a forgotten technology. Given what I know about Rust, I strongly suspect that there is a way in Rust to iterate over a vector with only a single hoisted bounds-check. Hopefully other Rust people can chime in on what this is.
- haberman 12y agoThis is long with a lot of detail, but to me the key bit of information is: iterators (as expressed by Rust's Iterator trait) have some noticeable drawbacks. Notably, you can't delete while iterating. However, a different abstraction called Cursors can accommodate this. I asked recently: "does this mean iterators are broken, or are iterators vs. cursors more of a fundamental tradeoff?" I got this very helpful answer in reply: http://www.reddit.com/r/rust/comments/2mkra1/impressions_after_writing_a_little_rust/cm58heh http://www.reddit.com/r/rust/comments/2mkra1/impressions_aft...
- enjoy-your-stay 12y agoAfter reading this bit: // Vec is our growable heap-allocated array type. // This is just a handy way to make one with some fixed data. let mut v = vec![1i32, 2, 3, 4, 5]; let x = v.get(2); v.push(6); // oops, sorry x! I really hope that the Rust compiler has some really good error messages explaining what the problem is because I couldn't see what was wrong with this fragment until I read the explanation. Saying that, after reading the explanation it became a bit more obvious, and I really like the way of describing the relationship to the pointer as a 'view' and 'loan', which as a c++ programmer (though clearly spending too much time with GC languages) I can understand.
- veddan 12y ago> I really hope that the Rust compiler has some really good error messages explaining what the problem is because I couldn't see what was wrong with this fragment until I read the explanation. They're not always perfect, but in this case it's quite good. err.rs:4:9: 4:10 error: cannot borrow `v` as mutable because it is also borrowed as immutable err.rs:4 v.push(6); // oops, sorry x! ^ err.rs:3:17: 3:18 note: previous borrow of `v` occurs here; the immutable borrow prevents subsequent moves or mutable borrows of `v` until the borrow ends err.rs:3 let x = v.get(2); ^ err.rs:5:6: 5:6 note: previous borrow ends here err.rs:1 fn main() { err.rs:2 let mut v = vec![1i32, 2, 3, 4, 5]; err.rs:3 let x = v.get(2); err.rs:4 v.push(6); // oops, sorry x! err.rs:5 } ^ If you want to try out code examples, the Rust playpen is nice: http://play.rust-lang.org http://play.rust-lang.org
- renox 12y agoI'm quite surprised by Rust behaviour here: if x isn't used after 'v.push(6);' (doesn't seem too difficult to know by the compiler) then I would have expected the compiler to allow this code and to reject it only if x is used after the 'v.push(6)'.. Sure as he explained you can do "let mut v = vec![1i32, 2, 3, 4, 5]; { let x = v.get(2); <work with x> } v.push(6);" but this must be quite annoying..
- kibwen 12y ago