I've been reading through some of the literature on unique types. Here's
where Rust as it stands today fits into the picture, as far as I can tell.
The traditional implementations of unique types (as implemented in N.
Minsky's Eiffel* [1], most notably) follow the logic of Wadler [2], in
which reads to the unique pointer null out the pointer. In this
scenario, whenever you move a unique pointer, the original gets nulled
out, and attempts to access it fail at runtime. This is known as a
"destructive read".
Because passing around unique pointers is very inconvenient when
destructive reading (or copying) is the only option, Eiffel* includes
the concept of "dynamic aliases" to unique pointers, which are basically
our aliases minus the recently-introduced ability to return them (but
including the ability to store aliases in locals). Taking a dynamic
alias to a unique pointer inside a shared object causes the unique
pointer to be nulled out for the lifetime of the dynamic alias. This
means that Eiffel* manages to do without any static analysis to support
aliases for soundness beyond this simple check.
In 2000 John Boyland proposed "alias burying" [3] to avoid destructive
reads, which is similar in spirit to the current alias analysis pass in
rustc (but not implemented using type-based analysis). Alias burying is
a static analysis pass very similar to ours: any read of a unique
pointer (more generally: any operation that changes the unique pointer)
results in invalidation of all its aliases.
Crucially, however, Boyland did not adequately deal with the biggest
problem with our current alias analysis: closures that can close over
arbitrary state. It is treated only in a footnote:
"The analysis also uses (but here does not check) an annotation on
procedures that indicates what variables it may read. **A listing of
fields possibly accessed during the execution of the procedure would
serve well and would also be easy to check modularly. We would prefer
however to use an approach which permitted better information hiding,
such as obtained using our object-oriented effects system or Leino's
data groups."
Essentially, as I understand it Boyland proposes making the set of
variables that a closure closes over part of the *type* of that closure
in some way.
As to how this relates to Rust:
(1) Our alias analysis, at least the part that relates to unique
pointers, isn't new; it's known as "alias burying" in the literature.
Although we implement it using TBAA, which I'm concerned about, this is
good! It has precedent in the literature.
(2) Performing alias burying in an intraprocedural way seems
fundamentally opposed to information hiding via closures. This is the
biggest thing that was making me nervous about alias analysis. It
doesn't seem that the research literature has solved this problem, and I
don't think we have either. In our alias burying, calling a closure
tends to wildly trash aliases, which leads to a lot of confusing error
messages and inexpressivity.
(3) I don't think that Boyland's solution is a good one for Rust. It
only really works in languages like C++ and Java, I think, since callees
can see the set of fields that a method might have access to (i.e.
private fields become part of the interface). It'd also make fn types
even more complicated.
(4) Because of (2), I'm honestly starting to warm up to destructive
reads -- nulling out pointers while they're moved or borrowed via
aliases. It is certainly the simplest solution, although it introduces
null pointers to Rust for the first time. There is a silver lining
though: there's only a small fixed set of operations (aliasing or move,
basically) that can produce the null pointer, and we should be able to
track the origins of null quite easily in debug builds and produce much
error messages than the dreaded NullPointerExceptions. Besides, swapping
with a sentinel "in-use" value is likely to be very common for
parallelism anyhow (farming out elements of an array to subtasks) - and
that's basically a null pointer in all but name.
Thoughts? I expect push-back on (4) :)
Patrick
[1] Minsky N., "Towards alias-free pointers"
[2] Wadler P., "Linear types can change the world!"
[3] Boyland J., "Alias burying: Unique variables without destructive reads"
_______________________________________________
Rust-dev mailing list
[email protected]
https://mail.mozilla.org/listinfo/rust-dev
