A read only no alias reference

language design
1

Pre-RFC: Exclusive shared references for read-only noalias borrows

## Summary

Rust currently has two main reference modes:

&T // shared, read-only-ish

&mut T // exclusive, mutable

This post proposes exploring a third reference mode:

&^T // exclusive, read-only

The syntax is only a placeholder, names like &uniq T, &noalias T, or something else may be better.

The basic idea is simple: this would be a reference that is read-only like &T, but exclusive/non-overlapping like &mut T.

If rustc cannot prove that the borrow is exclusive and non-overlapping, creating the borrow should be rejected.

reasons

Rust already has strong aliasing information, but today exclusivity and mutability are mostly bundled together in &mut T.

Sometimes a function does not want to mutate a value, but it still wants to know that the value does not alias anything else. In those cases, using &mut T works mechanically, but it communicates the wrong thing at the API level.

For example:

fn compute(input: &^[f32], output: &mut [f32]) {

*// input is read-only*

*// output is mutable*

*// input and output are guaranteed non-overlapping*

}

The intent is:

  • input will only be read;
  • input does not overlap with output;
  • the compiler can optimize based on that exclusivity.

This is somewhat similar to C’s const T * restrict, except checked by Rust’s borrow checker instead of being trusted as an unsafe programmer promise.

Proposed semantics

For a live &^T borrow:

  1. The referenced bytes must be live, initialized, aligned, non-null, and valid for T.
  2. The borrow may read from T.
  3. The borrow may not write to T.
  4. No other live reference may overlap the pointed-to bytes.
  5. No non-derived raw pointer may read or write the pointed-to bytes while the borrow is live.
  6. Pointers or references derived from the &^T may only read.
  7. &^T is not Copy, because copying it would create two exclusive aliases.
  8. &^T may be reborrowed as &T for a shorter lifetime, but the original &^T is suspended while that reborrow is live.
  9. For DSTs and slices, the exclusivity applies to the whole dynamic byte span.
  10. If rustc cannot prove the borrow is exclusive/non-overlapping, the program is rejected.

The intended distinction is:

&T // shared + read-only-ish

&mut T // exclusive + mutable

&^T // exclusive + read-only

Interaction with

UnsafeCell

For the strongest optimization value, &^T should probably require that T contains no UnsafeCell, or use some kind of Freeze-like property.

Without this restriction, &^T would be read-only through the reference, but the underlying memory could still be mutated through interior mutability. That would make the optimization guarantees much weaker.

So the strongest useful version is something like:

&^T where T: FreezeLike

Meaning: no interior mutable bytes are reachable through this reference.

Potential LLVM lowering

An exclusive shared reference could let rustc safely give LLVM stronger information than it can give for a normal shared reference.

At function boundaries, where valid, &^T could potentially lower to pointer arguments with attributes like:

ptr noalias readonly nonnull noundef align N dereferenceable(M)

Possible LLVM attributes or metadata enabled by this reference kind:

  • noalias: the referenced memory does not alias other active accesses.
  • readonly: the function does not write through this pointer argument.
  • nonnull: references are non-null.
  • noundef: references must be valid values.
  • align N: reference alignment is known.
  • dereferenceable(M): the pointed-to span is known to be dereferenceable.
  • captures(none): when rustc can prove the pointer does not escape.
  • captures(address, read_provenance): when only limited read-only provenance can escape.
  • !alias.scope / !noalias metadata: for scoped noalias information inside function bodies, reborrows, loops, and disjoint slice/range borrows.
  • potentially memory(argmem: read) for functions or calls whose memory effects are limited to reading argument memory.

For example:

fn sum(a: &^[u64], b: &^[u64]) -> u64 {

*// ...*

}

This could tell LLVM that:

  • a and b are readable;
  • neither a nor b is written through;
  • a and b do not overlap;
  • both spans are dereferenceable for their slice lengths.

That could help with vectorization, load hoisting, redundant-load elimination, and alias analysis.

Why not just use

&mut T

?

&mut T already provides exclusivity, but it also means mutable access at the API level.

This proposal is about separating exclusivity from mutability:

exclusive + mutable => &mut T

exclusive + read-only => &^T

shared + read-only => &T

Using &mut T for read-only noalias access works in some cases, but it makes APIs less clear. A function that only reads from a value should not need to request mutable access just to express that the value is unique.

The goal is to allow APIs to say exactly what they mean: this memory is read-only, but it is also exclusive and non-overlapping.

2

Why, what capability does this give the function? (Ignoring the optimization metadata angle).

3

This motivation/explanation is probably missing the fact that &T is already fully compatible with noalias in LLVM?

↝ compiler explorer demo ⮺

Edit: In fact, looking at your list

and checking what actually happens for something like &(i32, i32) in the linked code

ptr noalias noundef readonly align 4 captures(none) dereferenceable(8) %x

that’s essentially the exact same list already. (Minus nonnull, but nonnull is implied by dereferenceable anyway!)

however dereferenceable(<n>) does imply nonnull in addrspace(0) (which is the default address space), except if the null_pointer_is_valid function attribute is present (from the LLVM Manual)

Edit2: Actually, those were the things left after LLM was done optimizing. What Rustc produced was apparently

ptr noalias noundef readonly align 4 captures(address, read_provenance) dereferenceable(8) %0

containing these extra captures(address, read_provenance) annotations[1].

  1. by the looks of it, these make the guarantees actually weaker - the deduction of captures(none) happened by LLVM during its own analysis of the function body ↩︎

1 Like
4

It would allow dropping a superfluous mut on some variables, for instance:

fn f() {
    let vector = Mutex::new(vec![1,2,3]);
    let mut vector_guard = vector.lock().unwrap();
    vector_guard.push(4);
}

The variable vector_guard needs to be marked mut because MutexGuard::deref_mut takes a &mut self where it only really needs a &^ self. The guard doesn't actually get modified.

By way of analogy a variable of type &mut T doesn't need to be mutable to be dereferenced, it only needs to be unique. The variable vector_ref does not need to be marked mut:

fn g() {
    let mut vector = vec![1,2,3];
    let vector_ref = &mut vector;
    vector_ref.push(4);
}
1 Like
5

If that’s the goal, then to be more precise, I think multiple &T and at most one &^T could exist at the same time. Edit: hmm, that would depend on the design of the type, nevermind. Wouldn’t apply to MutexGuard or Cell. I do have some concurrent data structures where only one special handle is allowed to write (or read) through a & reference and the others can only read, but that doesn’t come for free.

6

To clarify: this only works without any UnsafeCell contained in T of course!

Whereas like &mut T, an exclusive immutable reference (wouldn’t be immutable w.r.t. the contents of that cell, but) could still be noalias for this case.

(Then again, using UnsafeCell is meant to be limited to those cases where you do really need it, anyway; so a new type mainly for (arguably a bit unclear) “performance” reasons sounds not really worth the downside in added complexity.)

LLVM's noalias does mean something different than no overlaps (in access), after all.

noalias

This indicates that memory locations accessed via pointer values based on the argument or return value are not also accessed, during the execution of the function, via pointer values not based on the argument or return value. This guarantee only holds for memory locations that are modified, by any means, during the execution of the function.

Accessing the same object through different pointers is allowed if no access to the object (neither there nor anywhere else) is mutating it. The C99 restrict keyword does the same, by the way.[1]

  1. And T const * restrict with a const qualifier basically enforces no mutation strictly, from anywhere, while you have that thing in your scope; but that also means that sharing the address with other (accessed, equally immutable) is never actually problematic. ↩︎

7

on top of the fact that this goes completely against the OP's original idea of making a reference even more read-only than regular references, this looks to me like a horrible design.

it seems its sole objective is to lie about wether mutation is happening ? it is a core part of the design of rust that you need mut if a variable will ever be modified, but with your idea any &^self method could suddenly be modifying non mut variable.

i would hope that "having DerefMut::deref_mut not take &mut" sounds as absurd to everyone else as it sounds to me.

but at least for your specific case it could be that the reborrow rfc would take care of it, not sure on the details. if vector_guard gets reborrowed, that creates a new local, which i would imagine would be mut, on which there would be no issue with calling deref_mut

8

Somewhat tangentially, I wish Rust had "write-only" references and a way to "prove" at compile time that the provided reference was fully written.

I disagree. mut in patterns is just a hard-coded lint. Removing it will have a minimal impact on the language design (as opposed to removing mut in references) and AFAIK it's erased very early during compilation. Finally, do not forget about interior mutability, you may be able "modify" a non-mut variable if its type contains UnsafeCell somewhere inside.

9

Note that we already have a similar behaviour:

fn main() {
    let mut a = 1;
    
    let r = &mut a;
    *r += 1; // Look ma, I can mutate through r even though r is not marked as mut!
}

I wouldn't say that this is a valid motivation for &^ references, but having to mark guards as mut is a relatively common pain point.

1 Like
10

Another example:

struct Wrapper<'a>(&'a mut u8);

impl<'a> Wrapper<'a> {
    fn increment(&mut self) {
        *self.0 += 1;
    }
}

fn main() {
    let mut a = 13;
    let b = &mut a;
    *b += 1;
    let mut c = Wrapper(b);
    c.increment();
}

b doesn't have to be marked mut, but c has to be marked mut.

With read-only unique references the Wrapper could work like the built-in &mut type and c wouldn't need to be mut:

struct Wrapper<'a>(&'a mut u8);

impl<'a> Wrapper<'a> {
    fn increment(&^ self) {
        *self.0 += 1;
    }
}

fn main() {
    let mut a = 13;
    let b = &mut a;
    *b += 1;
    let c = Wrapper(b);
    c.increment();
}

That's not true. Only mut variables (such as a here) or things inside types with interior mutability (such as Mutex in the previous example) could be modified, just like today.

11

i can hear that point, but i don't think a "read-only" reference that is actually used for mutation is a reasonable solution.

as i mentionned above, i do believe the reborrow feature, which aims to increase parity between custom Mut<'_,T> and &mut T does have the ability to fix this issue if the right design decision are taken.

12

It is already possible to do that:

pub struct ExclusiveReadOnly<'a, T: ?Sized>(&'a mut T);

impl<'a, T: ?Sized> ExclusiveReadOnly<'a, T> {
    pub fn new(r: &'a mut T) -> Self {
        Self(r)
    }
}

impl<T: ?Sized> std::ops::Deref for ExclusiveReadOnly<'_, T> {
    type Target = T;
    
    fn deref(&self) -> &T {
        self.0
    }
}

Compiler optimizations will treat this struct like &mut T, but it's impossible to write into it.

However this doesn't enable any additional optimizations, in fact it enables less: &T is already noalias, and this struct will not be readonly. noalias in LLVM means that if there are writes to this memory, they will be done from this pointer only. If there are no writes, this is trivially satisfied. LLVM just doesn't have any attribute for "readonly exclusive pointer", and I doubt such attribute has any optimization utility. Furthermore, the current memory models proposed for Rust also have no such thing, so it will require extending them for very dubious benefit.

13

This doesn't quite work:

    let a = 42u8;
    let r = ExclusiveReadOnly::new(&a);

error[E0308]: mismatched types
  --> src/main.rs:19:36
   |
19 |     let r = ExclusiveReadOnly::new(&a);
   |             ---------------------- ^^ types differ in mutability
   |             |
   |             arguments to this function are incorrect

    let a = 42u8;
    let r = ExclusiveReadOnly::new(&mut a);

error[E0596]: cannot borrow `a` as mutable, as it is not declared as mutable
  --> src/main.rs:19:36
   |
19 |     let r = ExclusiveReadOnly::new(&mut a);
   |                                    ^^^^^^ cannot borrow as mutable
   |
14

Unfortunately, it turns out to be very hard to construct that kind of proof, because it’s similar to wanting to prove that the write-only references are neither dropped nor leaked, and the pervasive possibility of panics makes that hard to prove. However, the in-place initialization project might bring us some kind of solution to this kind of problem.

15

You need to pass a mutable reference, like the second snippet, and yes, you need to mark it mut. That's not a reason for a language feature IMO, even if there would be such reason in the complete absence of a solution like mine (which I don't think there is).

16

This reminds me of (and may be equivalent to) the proposal for references that cannot themselves be mutated, but which allow safe mutation of the things they point to. I think it was discussed in this thread, using the placeholder syntax &in.

This is read-only in the sense that the bytes it directly points to cannot be mutated, but needs to guarantee uniqueness to make it safe for the bytes that it indirectly points to to be mutated.

The concept does seem to have some uses (you can create one in Rust at the moment by capturing a variable declared like let x: &mut T in a closure: x is borrowed by the closure rather than moved into it, but x can't be mutated from within the closure, whilst *x can be). I'm not sure whether it's useful enough to worth adding as a first-class type of reference, though.