On 6/3/11 2:07 PM, Graydon Hoare wrote:
I like the line of reasoning; let me try phrasing in a slightly more
terse/pithy fashion:
"Alias-formation must preserve unique ownership of the referent"
So in a discussion on IRC we found a several issues with this scheme.
Taking them one by one:
(1) It's important to be able to take aliases to the interior of a box,
because it's how we abstract over interior and exterior types. For
example, the list functions in list.rs have signatures of the form:
fn f[T](&list[T] l, ...)
But it's often desired to pass in a @list as the first parameter to
these utility functions. To do this, we need to be able to call these
functions as f(*l, ...) with l : @list. The alias analysis rules as
stated forbid this: there could be multiple aliases to the interior of a
box. However, in many cases, we can prove that the caller will keep a
reference to the box for the duration of the call and therefore will
keep its contents alive. So I propose relaxing the restrictions
slightly; the caller can pass the interior of a box *stored in a local
variable* as an alias.
(2) "alt" behaves much as a function call with alias parameters. To see
why this is true, consider this code:
var x = some("foo");
alt (x) {
case (some(?s)) {
x = none;
log s; // crash
}
}
This crashes on the line marked "// crash" above. The reason is that "s"
is an *alias* to the string, which has its last reference removed by the
assignment "x = none;" above. Switching destructuring to use copying
instead of aliasing won't work for several reasons orthogonal to this
post (although I can go into them if anyone is interested).
The solution is to treat "s" the same as any other alias; in particular,
it must temporarily render "x" inaccessible for the duration of the
"alt" statement. We also have to mandate that lvalues used in the
expression position of an "alt" statement are unique, so that rendering
them inaccessible really does make it impossible to affect the lifetime
of their subparts (IOW, in this example, we have to make sure there's no
other way to get to the contents of "x", i.e. "s").
(3) Putting points (1) and (2) together, we have to ensure that two
alias parameters passed into the same function don't, well, alias. This
is so that alias parameters can be treated as unique in the callee. To
see why this is necessary, consider this code:
fn f(&mutable option::t[str] x, &mutable option::t[str] y) {
alt (x) {
case (some(?s)) {
y = none;
log s; // crash
}
}
}
fn g() {
var x = "foo";
f(x, x);
}
fn h() {
var x = "foo";
var y = x;
f(*x, *y);
}
Calls to g() and h() will crash at the line marked "// crash", because
they both manage to perform a call to f() with the same value for both
parameters x and y. It's easy to see how to statically forbid the call
to f() inside g(); the two parameters clearly refer to the same local
variable, so we can reject the call.
Proving the same for h() is more difficult, since h() takes advantage of
the relaxed rules proposed in point (1) above. So in this case, and this
case only--namely, when the interior of a box is passed to two
type-compatible aliases--a dynamic check will be performed that the two
boxes do not alias (note that this is a shallow check), and we can emit
a warning.
If the user doesn't want the warning, he or she can copy one of the
values before the call. This check allows users to pass box contents as
aliases as expected, while (as far as I know anyway) preserving type
safety and runtime performance.
Patrick
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
