Rust borrow and lifetimes
arthurtw.github.io
arthurtw.github.io
I looked at this problem a decade ago for C/C++, and got as far as borrow semantics (I used the term "keep", as the opposite of borrow). But there were ownership cases I couldn't figure out a good way to handle. This sort of thing is why the C++ committee beat their head against the wall with "auto_ptr". Rust has the same problems, and the solutions don't seem to be entirely clean.
Living with strict single ownership semantics is hard. One amusing approach is to have an atomic "swap" as a primitive. Swap is safe as regards single ownership. With enough swaps, you can do things like move the contents of an array to a new, larger space. This is an inefficient way to do it, but easy to prove sound. "Move semantics" can be viewed as a special case of swap, where one of the moved pointers is known to be null.
It can be useful to view something like moving the contents of an array as a sequence of swaps, which are then optimized. If the destination array is all NULL at the start, each swap operation becomes a pointer copy followed by a store of NULL into the source pointer. Then, if we can show that all the swap operations are non-overlapping, we can do all the pointer copies before all the stores of NULL. Then, if the source buffer is about to be discarded and is never read again, we can omit the stores of NULL. Then if the pointer copies are all adjacent, they can be rolled up into one MOV operation.
This may be a way to avoid using "unsafe" so much.
> But it's apparently necessary in Rust to use "unsafe"
> code in libraries to implement basic structures like
> re-sizable arrays.
> Living with strict single ownership semantics is hard.
> This may be a way to avoid using "unsafe" so much.
For new work, most efforts are going forward to C# or D or Go or Java, all of which solve this problem by using a garbage collector. The claim for Rust is that it's memory-safe without a garbage collector. This claim does not appear to stand scrutiny. If 10% of a browser has to be "unsafe", the language is seriously flawed.
The implementations of C#/Go/Java are also 100% unsafe, as they're in the same boat.
Getting that 100% down to 10%, where the 10% is clearly marked and sequestered behind safe interfaces that are well-tested and well-audited, is a much better solution than giving up on one or the other of performance or safety entirely.
No, because there are(will be in Go's case) meta-circular implementations available.
C and C++ aren't the only way to implement compilers.
Rust's unsafe-with-safe-interfaces style is just another way to do that, which honestly is a lot more straightforward.
Sorry for not getting your point fully.
In C#, D, Go, and Java, arrays are implemented as language primitives in the runtime. Their runtimes are implemented in raw C or C++ and are not formally verified. So my question is: Why is implementing an array in C as a language primitive safer than implementing it in the standard library via unsafe code?
There's a similar story for the swap operation. Rust in fact used to have a swap operation, as you suggested, but it was removed because such an operation can easily be implemented in the library. We could have moved the code back into the compiler, but how would that have made the language safer? (In fact, I would be tempted to argue that implementing language primitives in codegen is less safe, since programmatically generating LLVM IR is more difficult than writing essentially C with a different syntax.)
(This is, as I explained downthread, part of the reason why I dislike going around quoting "X% of the code in Y app is unsafe." Your application code shouldn't be unsafe.)
This is not true of all implementations. There are meta-circular implementations of Java and C# compilers, that people keep forgetting about.
10% seems higher than any number I've seen.
In any case, it matters quite a bit where the unsafe code is, and that's why I don't like just counting numbers of lines of unsafe code. Empirically, a large number of security-critical bugs in browsers are in layout code, often due to use-after-free. Servo core layout code denies unsafe via `#[deny(unsafe_block)]`. We do not allow unsafe core layout code to be checked into the tree; the only unsafe code in layout is general code that manages relatively simple invariants.
The question that matters is: Can you write high-performance code in Rust without writing unsafe code of your own? I'm confident that the answer is yes.
Servo isn't just "a browser engine written in Rust"; it's a project that serves as the largest driving force for the language. As a result, many abstractions that will in the future end up in the standard library or one or more packages will show up in Servo first. And I'd expect the implementation of the standard library to contain a significant amount of unsafe code, as part of implementing abstractions usable without invoking "unsafe".
I would expect other application projects to have far less unsafe code on average. New Rust libraries wrapping C libraries, or creating new low-level abstractions around memory, will have quite a bit of unsafe code, with a safe exported API.
Historically, swap actually was a part of Rust language (operator <->). It was removed from the language as a primitive, because it can be implemented in a library.
There's no entirely clean solution, just as there is no perfect GC algorithm. There's a big design space where the type-system restricts aliasing, and pointers carry static type information about what they can point to. Rust represents one point in that design space, one tuned towards memory management. There's all sorts of other design points: http://ilyasergey.net/papers/ownership-survey.pdf.
Most of the work in this area has actually been done in a Java context, and focus more on access control than on memory management. These other type systems can enforce properties that are useful for encapsulation, but aren't necessarily all that useful for memory management.
* std::mem::replace, http://doc.rust-lang.org/std/mem/fn.replace.html
* Option::take http://doc.rust-lang.org/core/option/enum.Option.html#method...
I think the lifetime guides should be more explicit about how memory management occurs.
Something like this:
When the instance X of type T is freed in rust and its destructor (if any)
is invoked, we refer to this as 'dropping' X.
X will be dropped if:
- It goes out of a scope
- It's immediate parent is dropped
*T in rust is a 'raw' pointer, like a C pointer.
*T can result in a segmentation fault like in C, if the memory it points
to has already been dropped (Use after free).
&T is a special type in rust that prevents use after free errors by
applying compile time guards enforcing safe usage.
Typically the compile time guards are automatically determined using
static analysis, but sometimes ambiguities require explicit hints when
writing an API. In these cases it is necessary to hint to static type
checker what the the appropriate lifetime for a &T is.
A lifetime is a static approximation of the span of
execution during which the pointer is valid
It needs to be explicit 1) that lifetimes are for the static type checker, and 2) that they are more than just for borrowed pointers.
For example, for a trait or closure, the lifetime is not the duration during which the pointer is valid. It's a lower bound on the possible lifetimes of other types that can go into either that closure or trait.
For example, to pass a closure to a thread it must be 'static, which means that the lower bound for any lifetime used in the closure is static. This for example:
let foo = 0u;
let bar = |:| { let y = foo + 1; ... }
The same is true of structures and traits. A boxed trait Box<Foo + 'a> means the struct implementing Foo contained in the box must have an lifetime of at least 'a.
It's almost like we have two completely separate ideas:
1) Lifetime <--- The lifetime of a borrowed pointer
2) Lifetime bound <---- The lifetime on a closure, struct, trait, etc.
The issue is &'a is so common in Rust code. We simply call it lifetime 'a, which is misleading. It is not any object’s or pointer’s lifetime, but a set of lifetime requirements (or lifetime bound in your term) that every borrower imposes on the borrowed resources. It is the B I mentioned in the last section of my blog post:
When we talk about borrow, there are three different kinds of “lifetime” involved:
A: the lifetime of the resource owner (or the owned/borrowed resource)
B: the “lifetime” of the whole borrow, i.e. from the first borrow to the last return
C: the lifetime of an individual borrower or borrowed pointer
The required condition is A >= B, where B = C1 U C2 U ... U Cn.
I think scope is a great word, because my own important insight was that "lifetimes" represent the scope a borrowed reference lives in -- it's not really about the life of the value you borrow from.
Yes if you have a lifetime 'a, it will correspond to some reference on the stack in a scope somewhere up the callchain.
I don't know Rust, so the question may be non-sensical, still, an explanation would be much appreciated :)
* You can use Arc (Atomically reference counted smart pointer), to share immutable data with all your tasks, without needing any locking. You may generate this data, and either hand tasks an Arc pointer at their creation, or send it out using channels.
* You can use RWLock or Mutex to share owned data with limited/locked mutable access between several tasks. These types are smart wrappers that only allow access to their protected value while properly locked.
Oh, and fyi the borrow checker is strictly local to a function or method. Other features of the Rust language, like the type kinds Send and Sync, are involved in checking which values are safe to share between tasks. Normal rust references (&T) only point across tasks if you get them through one of the primitives Arc, Mutex, RWLock or similar.