Add rustc flag to disable mutable no-aliasing optimizations?

[RalfJung]

(There seem to be at least two parallel discussions going on in this thread; I am responding to the one about "simpler aliasing models".)

@tcsc

In particular, my belief is that IMO, &T and &mut T should only impact what raw pointers are allowed to do for the duration of the lifetime of the &T or &mut T .

This is indeed what Stacked Borrows does! (With one exception, "protectors", but those are not relevant for the discussion here.) So the aliasing model you are asking for already exists, it is called Stacked Borrows, and Miri helps you check it (with some caveats around interger-ptr casts).

@tcsc

For example, the stdlib had this bug for many years slice::swap violates the aliasing rules · Issue #80682 · rust-lang/rust · GitHub (which, to be clear, is an exact issue of the problem I'm discussing), and it was fixed by using addr_of_mut , a tool that was only added recently.

That code is not correct under a model where "references only impact raw pointers during their lifetime". That code creates a reference, and then creates a raw pointer from that reference, which means the reference's lifetime is at least as big as "however long the raw pointer is being used". (If not, then we would have a derived pointer outlive its parent pointer, at which point the entire concept of a "lifetime" doesn't really make much sense any more -- &*ptr cannot possibly have a lifetime longer than ptr.) Then it creates a second reference that overlaps the first reference which is still alive due to the raw pointer. Ergo, this code violates even these simple aliasing rules.

So, I think you are contradicting yourself here -- you are asking for an aliasing model that is a lot like Stacked Borrows, and then bring up examples that are wrong under such an aliasing model. Or more likely, you are using some terms like "lifetimes" in a very specific way which is different from how I use that term. But I hope this makes it clear that your "simple aliasing model" is a lot less simple than you might have thoughts, and that precisely defining the terms involved is subtle.

Stacked Borrows started with basically the premise you are asking for: raw pointers can do whatever they want, as long as that does not interfere with "live" references. Working out what exactly that means in all possible circumstances is non-trivial and the consequences are sometimes surprising.

Now, this is no to say that Stacked Borrows cannot be improved; it certainly can. I have some ideas that might fix the most prominent problem. Whether the improved model will be perceived as any simpler I cannot predict.

@tcsc

And so I'd like a way to opt out of that.

I am strongly opposed to adding flags that change the UB rules. This leads to more-or-less compatible language dialects and libraries that are "only correct under some flags", which quickly becomes messy. Instead, we should strive to develop UB rules that everyone can live with.

[RalfJung]

@tcsc

this happened once in the past with things like mem::uninitialized::<[u8; N]>() (which used to be considered well-defined so long as you didn't read from it, and now is considered UB),

It wasn't really considered well-defined, it was just something some people did and nobody realized that it is in fundamental contradiction with assumptions other people (in particular those in charge of the LLVM backend) made. The map of where UB starts in Rust used to have a lot of white spots, and people raced into those uncharted areas at full speed -- and then later we realized that some of them went too far into territory that we have little choice but declare UB. For uninit integers specifically though, the discussion is still open.

Could Rust have done better? Certainly. It would have been better to apply more care when venturing into the unknown parts of this map. But with hindsight, this is much easier to say. To tie ourselves forever to code patterns developed without design or consent from the language team would not necessarily make the language any better, I think. I am not proposing to ignore the existence of these patterns -- in fact I spent a lot of time to help find and fix instances where uninit memory is used incorrectly -- but I think we should not let those patterns unilaterally dictate UB decisions.

[mjbshaw]

@RalfJung I want to respond to the two parts about "slice::swap violates the aliasing rules " and "the most prominent problem".

I think these kinds of issues point to Rust's aliasing model/rules being too strict or complex. Or rather, they're unintuitive. That leads to misunderstandings and incorrect code, which kinda defeats the whole point of Rust's memory safety guarantees since it's way, way too easy to violate.

I think it's important for Rust's model to be simplified or adjusted so that these two examples are well-defined and work as people intend them too, without requiring code changes. People clearly think they're following the aliasing rules. The code is, IMO, the "intuitive" way to do many things. Making code like this UB means that in some ways, Rust is less safe than C IMO.

[tcsc]

@RalfJung

But I hope this makes it clear that your "simple aliasing model" is a lot less simple than you might have thoughts, and that precisely defining the terms involved is subtle

So, I should have probably used the term minimal rather than simple, and the simplicity was intended in terms of reasoning, not necessarily formal semantics. That said, I can see how it might be offensive, sorry.

And for sure, I'm aware that precisely defining it would be subtle and difficult. It was not intended as such a definition (I prefaced it by saying I did not have the programming language experience to provide such a thing), just as a vague description of a strawman.

That code creates a reference, and then creates a raw pointer from that reference, which means the reference's lifetime is at least as big as "however long the raw pointer is being used".

Yes, this is part of why I provided the example. By "the lifetime of a &mut T", I mean the time when the &mut T exists in the program, statically. (For clarity, when I say "time", I'm speaking entirely abstractly, and not about any real clock or anything like that)

Specifically, consider any (other) type: there's a point at which that type comes into existence, and a point when it goes out of existence. That range is what I'm considering the lifetime. That is, in let x = (1i32 + 2i32) as f32;, I would consider there to be a temporary 3i32 which starts existence after the evaluation of the addition, and which goes out of existence during the cast (of course, one could argue about when during the cast, e.g. start/end/middle, which obviously doesn't make a difference).

The thing I had referred to as its lifetime is the range between those two times for any type. For the sake of removing ambiguity, I'll try referring to this as "lifespan" rather than "lifetime" for the rest of this.

I understand how this is confusing, as there are several things called lifetimes could be described for a reference:

1. The 'a in &'a mut T, which can't be used for aliasing rules, as it is allowed to be a lie (so long as you don't use it outside the lifespan of the T).
2. The lifespan of the referenced T, which is also the upper bound of basically any of these.
3. What I used it to mean, the lifespan of the &mut T itself.
4. What you're describing, which I think could be explained as the time range:
   • from the start of the lifespan of the reference.
   • until the last use of pointer derived from that reference
   • or the end of the lifepan of the reference, whichever is later

So 3 is what I meant, which is probably a bit c++-programmer of me, hopefully it clarifies the intent of my strawman before as well, why it's not the same as stacked borrows, and why under it, the broken code from swap would be correct.

What I've described is also far closer to how unsafe code that I've seen reasons about &T, and &mut T, (hopefully) preserves the idea of raw pointers as free to manipulate so long as the references that exist preserve their guarantees, and has the significant benefit of not requiring nonlocal reasoning the way that stacked borrows does, which requires being able to track the origin of each pointer, and how it was granted.

(Because of the non-local reasoning, I'm comfortable saying stacked borrows, at least as it is now, is far harder to reason about than C and C++'s type based strict aliasing, which is has no real equivalent to that (and manages to still be hard to reason about in some cases). And hell, the swap case I mentioned isn't even the tip of the iceberg for these sorts of bugs I fear, as the usage is entirely local)

---

For uninit integers specifically though, the discussion is still open.

Right, I was talking about those, the choice of [u8; N] was not a coincidence. It's very surprising that LLVM motivated a change there, given that I can have a uninit array of bytes in C without issue just by uint8_t foo[N];. This is off topic though.

[tcsc]

@RalfJung

I am strongly opposed to adding flags that change the UB rules. This leads to more-or-less compatible language dialects and libraries that are "only correct under some flags", which quickly becomes messy. Instead, we should strive to develop UB rules that everyone can live with.

FWIW I do agree with this, although the notion of relaxing the UB comes up very rarely, and potential missed optimizations generally shoot it down immediately. The same contention exists in the C and C++ communities, but perhaps we can be better then them.

(There was definitely a time when unsafe Rust code felt far easier to write than unsafe C, since it had no strict aliasing, and the rules were easy to think through. Unfortunately...)

[2e71828]

@tcsc

Yes, this is part of why I provided the example. By "the lifetime of a &mut T", I mean the time when the &mut T exists in the program, statically. (For clarity, when I say "time", I'm speaking entirely abstractly, and not about any real clock or anything like that)

Let me try to apply this to a concrete piece of code (of dubious usefulness):

unsafe fn f<T>(ptr: *mut Rc<T>)->Option<*mut T> {
    Rc::get_mut(&mut * ptr).map(|t_ref| t_ref as *mut T)
}

As I understand it, stacked borrows says that the caller must not dereference ptr until after the last use of the returned *mut T, but can freely use ptr after that point.

Under your proposed model, any use of either ptr or the returned *mut T should be allowed after the function returns, as there are no extant exclusive references at that point in time.

Is that correct?

---

And a slight variant:

unsafe fn f<'a,T:'a>(ptr: *mut Rc<T>)->Option<&'a mut T> {
    Rc::get_mut(&mut * ptr)
}

Here, stacked borrows forbids further use of ptr within the region 'a. Under your model, it's unrestricted because the &mut Rc<T> itself never escapes f.

[steffahn]

@2e71828

As I understand it, stacked borrows says that the caller must not dereference ptr until after the last use of the returned *mut T , but can freely use ptr after that point.

I don’t think it does, since

pub struct Rc<T: ?Sized> {
    ptr: NonNull<RcBox<T>>,
    phantom: PhantomData<RcBox<T>>,
}

is itself using a raw pointer internally. Something like e.g. using the *mut Rc<T> to replace the Rc with another one (making sure not to deallocate or otherwise dereference the old Rc), and afterwards using the Option<*mut T> that you still kept around should (probably) be 100% fine.

Also regarding your variant:

@2e71828

And a slight variant:

unsafe fn f<'a,T:'a>(ptr: *mut Rc<T>)->Option<&'a mut T> {
    Rc::get_mut(&mut * ptr)
}

Here, stacked borrows forbids further use of ptr within the region 'a .

Even if there was a restriction, I don’t think that lifetime annotations have anything to do with it. AFAIK, lifetime annotations have no semantics at all w.r.t. compilation output, including compiler-UB. Having a &'a mut T with a lifetime that’s longer than you could ever legally keep that reference alive without UB doesn’t instantly result in UB itself. If you make sure that you never give out such a reference to untrusted code and make sure to get rid of it early enough, it should be fine.

[2e71828]

That's a good point. I probably shouldn't have used something as complicated as Rc in my example:

struct S( usize, usize );

unsafe fn f(ptr: *mut S)->*mut usize {
    (&mut (&mut *ptr).1) as *mut usize
}

unsafe fn g<'a>(ptr: *mut S)->&'a mut usize {
    &mut (&mut *ptr).1
}

And, for the reference version, my analysis assumes you're handing the produced reference to safe, unaudited code.

[tcsc]

So, starting with the second one. Here's the trouble: if called twice with the same *mut Rc<T> (if its unique) will produce two &'a mut T, which is definitely forbidden by all models. If only used once, then yes, I believe this is fine under at least mine.

The first has the no such restriction, however you do have to be careful not to use those raw pointers violate the aliasing rules elsewhere, cause data races, or cause library code to unwittingly do so. That said, that's normal table stakes for unsafe Rust, since it's always possible to use unsafe code to violate arbitrary library invariants and make it do dangerous stuff.

I find Rc pretty confusing in these. It also would help if you could elaborate at the point you're getting at a little more, as it is it feels like either a quiz or trying to get someone to walk into a contradiction — not saying thats deliberate though.

[2e71828]

@tcsc

It also would help if you could elaborate at the point you're getting at a little more, as it is it feels like either a quiz or trying to get someone to walk into a contradiction — not saying thats deliberate though.

I don't have a point, except that I find it hard to compare this sort of thing in the abstract. I'm just trying to understand how the two competing models differ with some kind of concrete example, and verifying that everyone actually agrees on what's being discussed.

[tcsc]

The first should be totally safe, as it's just a field projection, I think. That said, it's also a bit symbol soupy, so maybe I'm missing something.

If you're providing the reference in the 2nd to safe code it depends on more than this function. Are there any &S/&mut S/&usize/&mut usize for the same instance/field? If there would be then its UB, otherwise it shouldn't be unless you end up using it to cause unrelated UB.

Note that the other caveat to this is that you can't have &mut T to constant/static data, or data that was declared as non-mut, or didn't come from an unsafe cell. This is required by any model of rust as well.

[2e71828]

Right. I was trying to enumerate the pre- and post-conditions on the usage of both ptr and the return value, around code that calls one of these functions. Not just analyze the safety of calling it once or multiple times on the same value.

In other words, given that a call to f or g is present, what do I as a code auditor need to verify about the surrounding code to determine that the usage is safe? In particular, what operations are allowed on ptr while the return value exists?

Stacked borrows generally says that I need to not dereference ptr within a defined region, which is simple but restrictive. Your model is more permissive (a strict superset), but I find it hard to enumerate what, specifically, the extra capabilities are without accidentally including something that definitely shouldn't be allowed (like producing a concurrent &mut T)

[RalfJung]

@mjbshaw

I think these kinds of issues point to Rust's aliasing model/rules being too strict or complex. Or rather, they're unintuitive. That leads to misunderstandings and incorrect code, which kinda defeats the whole point of Rust's memory safety guarantees since it's way, way too easy to violate.

I don't disagree. There is a reason that I am not pushing for making Stacked Borrows the official memory model.

@tcsc

So, I should have probably used the term minimal rather than simple, and the simplicity was intended in terms of reasoning, not necessarily formal semantics. That said, I can see how it might be offensive, sorry.

No offense taken.

@tcsc

Yes, this is part of why I provided the example. By "the lifetime of a &mut T", I mean the time when the &mut T exists in the program, statically. (For clarity, when I say "time", I'm speaking entirely abstractly, and not about any real clock or anything like that)

I don't think that is coherent. That is, I think when considering the "lifetime" of a reference in the sense of "the time for which the reference and its aliasing matters", you have to consider all pointers that are derived from this reference, otherwise your model ceases to be self-consistent, or it ceases to provide any useful guarantees.

There is a reason that the borrow checker, when encountering y = &mut *x, enforces the lifetime of x to outlive that of y, even if x is not used again. Rust would be unsound if it did not do this. For the same reason, the aliasing model has to "extend" the lifetime of a reference to also encompass that of all of its derived pointers.

I don't think your analogy with integers works. Integers do not have provenance, it does not matter how you compute 3, it'll always be the same 3. With pointers, different ways to compute a pointer to the same location in memory can produce different results. A pointer essentially "remembers its history", so even if a reference is never used again, the fact that some pointer was created by casting that reference to a raw pointer is recorded in the value of that pointer, and thus "lives on".

@tcsc

(Because of the non-local reasoning, I'm comfortable saying stacked borrows, at least as it is now, is far harder to reason about than C and C++'s type based strict aliasing, which is has no real equivalent to that (and manages to still be hard to reason about in some cases). And hell, the swap case I mentioned isn't even the tip of the iceberg for these sorts of bugs I fear, as the usage is entirely local)

So, I won't argue against Stacked Borrows being complicated, and we have not yet developed a nice logic with reasoning principles for Stacked Borrows (and when taking into account ptr-int-casts, the current model might not admit a nice logic), but unlike for C/C++, there is a precise formal spec and there are proofs that some optimizations are correct for this spec. Nobody has carried out such profs for C/C++. (The closest we have is Robbert Krebbers who verified an alias analysis based on strict aliasing, but it turns out the analysis real compilers do is much stronger and not even justified by what the standard says.) So as far as constructive evidence goes, it looks like Stacked Borrows is easier to reason about than C/C++. Certainly I have not seen a nice set of formal reasoning principles proven correct against a precise spec of the C/C++ model -- the kind of thing I would accept as evidence that C/C++ can be reasonably reasoned about.

Also, note that Stacked Borrows is not as non-local as you make it -- the apparent non-locality arises because of the "history" that I mentioned above; it can be explained in an entirely local way by adding some extra state. Arguably, the mere existence of that state is confusing. However, I am pretty sure it is unavoidable -- we can simplify Stacked Borrows and make some things less surprising, but such a "history" will still exist.

@tcsc

(There was definitely a time when unsafe Rust code felt far easier to write than unsafe C, since it had no strict aliasing, and the rules were easy to think through. Unfortunately...)

Rust never had no strict aliasing, people just had no clue what the aliasing rules were and thus ignored them. I am hopeful that we can make things simpler as they currently are. Also note that now that we have addr_of!, there is a fairly straight-forward recipe for writing Rust without any aliasing hassles: use raw pointers everywhere, never create a reference. That should be simpler than C. Sadly it is currently not very ergonomic...

[RalfJung]

Okay @tcsc so you think this code should be allowed? (based on the example by @2e71828)

let mut s = 0;
unsafe {
  let ref1 = &mut s;
  let ptr1 = ref1 as *mut _;
  let ref2 = &mut s;
  let ptr2 = ref2 as *mut _;
  // now use ptr1 and ptr2 in arbitrary ways
}

If yes, I will see if I can come up with some concrete examples for the consequences of this decision, to explain why Stacked Borrows rejects this code.

Before I try that, one more question -- do we agree that this must be UB?

let mut s = 0;
unsafe {
  let ref1 = &mut s;
  let ptr1 = ref1 as *mut _;
  *ref1 = 2;
  *ptr1 = 3; // UB, the write above invalidated this raw ptr
  assert_eq!(*ref1, 2);
}

This must be UB to allow the following optimization:

*ref1 = $const;
// any code that does not use ref1
let x = *ref1; // will definitely load $const

[tcsc]

(Caveat in advance, I think I repeated myself a bit here, sorry)

Okay @tcsc so you think this code should be allowed

I think for some definition of "arbitrary", sure. They can't use those to have multiple &mut T of course. But something not that different than this ends up being required in some definitions of intrusive double linked lists on the stack, so yeah, I would like this to work.

// UB, the write above invalidated this raw ptr.

That line is UB because ref1's lifespan hasn't ended yet. Once ref1's lifespan ends, ptr1 would be usable (it's not invalidated, just temporarily restricted by the existence of that mutable reference).

unlike for C/C++, there is a precise formal spec and there are proofs that some optimizations are correct for this spec

This is nice, but in practice the downside of having to maintain the stacked borrows model in your head, (or figure out what it might be during a code review) massively outweighs this. Most programmers will not read formal models, it's nice if one exists because it means the semantics aren't completely incoherent, but I would guess most C++ programmers are happy enough with the C++ spec — I'm not sure I've ever met one who would reach for such a model over the spec text.

So as far as constructive evidence goes, it looks like Stacked Borrows is easier to reason about than C/C++.

Yeah, in particular, easier to formally model is a totally different thing from how easy code written using it is to reason about.

While C++ has no formal model for this, when writing and reviewing code very rarely are people thinking of a formal model, instead of a set of rules, heuristics, caveats, and other such ad-hoc stuff. This is true for all models, I think. It's relatively easy to come up with a viable model like this for C++ that's probably a bit too conservative, and very likely bans many parts of the language (very easy and common in an enormous language like c++).

So, while for stacked borrows there is a formal model, it does little good, as evaluating correctness under SB requires a lot of mental overhead. You must develop the runtime "history" to reason about, which is very difficult (and hard to come up with rules to drastically simplify this that can be followed without defeating the point).

I don't think your analogy with integers works. Integers do not have provenance

Well, you may have noticed that my model tries (perhaps unsuccessfully) to eliminate alias-based provenance from raw pointers as much as possible, except during concrete, statically visible regions of time where references exist. It instead push everything onto ensuring that those references fully follow the "&T is immutable, &mut T is unique and mutable" rules.

Specifically, there's (intended to be) no permanent invalidating of a raw pointer, only temporarily restricting it, as the alternative is unintuitive, hard to reason about, and nonlocal.

---

That said, I do want to note that it would really surprise me very little if the approach I came up with above in around 10 minutes falls apart in some cases. I can already see cracks at the edge, but the point was more to move the discussion in this direction and start from what wants to be aggressively simpler to reason about than SB, rather than continue with discussions about stuff that won't happen and is easy to dismiss¹.

Specifically I wanted to push back against the idea that the solution here is to just accept SB, and find ways to live with a complex model. The goals for the model I came up with are/were basically:

• Eliminate several of the things about stacked borrows I find impossible to reason about, or that seem too limiting³

• Specifically, it ditches as much of raw pointer provenance as I can, only keeping it if a reference exists or the rules would otherwise violate rust (e.g. writing to a non-mut non-unsafecell thing, etc).

• Where provenance can't be removed, make it as trivial as possible to reason about:

  • That is, it can be determined from reading code, without maintaining a bunch of mental state or knowing about a pointer's history.
    • The current state is a nightmare auditing and reviewing, and can be very hard to explain in unsafe contracts²

• Preserve everything that is, IMO, "required" for rust to keep working as rust. E.g. don't change the semantics of &T, &mut T, ...

• Completely ignore optimizations in most of this, with the hope that being able to apply them to code that never takes raw pointers to things is enough.

I'd like to discuss ways something that achieves some of these things is possible.

---

¹ Like allowing multiple &mut Ts — Additionally I also was hoping it would turn into a discussion about simpler semantics (as it has), rather than just under a flag, although I'd have accepted a flag as a conciliation prize

² There's a failure mode where you end having part of the contract be "must not use the pointer in a way that violates its provenance" which is practically a tautology (i hit this a few times in my patch that made anyhow follow SB/pass under miri)

³ Excluding bits that I have confidence that even under the current model will get worked out, like the size stuff, and probably ptr2int

[RalfJung]

@tcsc

While C++ has no formal model for this, when writing and reviewing code very rarely are people thinking of a formal model, instead of a set of rules, heuristics, caveats, and other such ad-hoc stuff. This is true for all models, I think. It's relatively easy to come up with a viable model like this for C++ that's probably a bit too conservative, and very likely bans many parts of the language (very easy and common in an enormous language like c++).

Yeah, C++ programmers do all this -- and C++ programs are full of UB, as evidenced by the never-ending stream of security issues caused by memory safety violations. I thus have little confidence that those rules and heuristics really help to avoid UB. I'd feel better if at least there was some way to know for sure that the heuristics are correct, but there isn't, since the spec is not precise enough.

Give us a few years and let the Rust aliasing rules settle a bit; I am sure people will come up with good heuristics and approximations for how to write correct Rust code. And they'll do it based on a solid foundation, with a way to actually check if those heuristics are correct.

/End of my usual rant for why we need formal specs. I appreciate not everyone shares my opinion, and it's probably not terribly on-topic for us to go on about this.

@tcsc

Well, you may have noticed that my model tries (perhaps unsuccessfully) to eliminate alias-based provenance from raw pointers as much as possible, except during concrete, statically visible regions of time where references exist. It instead push everything onto ensuring that those references fully follow the "&T is immutable, &mut T is unique and mutable" rules.

Specifically, there's (intended to be) no permanent invalidating of a raw pointer, only temporarily restricting it, as the alternative is unintuitive, hard to reason about, and nonlocal.

Note that C/C++ have provenance. They just don't talk about it much, and hence many programmers don't know and get it wrong all the time. This provenance is not restricted to syntactic scopes in any meaningful way. So there's no question if Rust will have provenance, just how detailed it will be.

I think this is far more intuitive than coming up with some ad-hoc rules to enforce syntactic restrictions. (And I am reasonably sure that the only way to achieve these restrictions is ad-hoc -- any principled treatment of provenance that has been proposed so far makes it a proper part of the value of a pointer, and thus not scoped in any meaningful way.) So you should at least accept that your notion of what is "intuitive" or "local" is a very subjective one. ("local" sounds like a technical term, but I don't know of a technical way in which Stacked Borrows provenance is any less local than C/C++ provenance -- certainly this is the case once you consider C's restrict.)

[comex]

@tcsc

Similarly, add a way to mark a struct as being able to have container_of soundly used on it.

This one in particular probably just has to be fixed by adjusting the model, since the most common offender here is stuff like allocators, which have to work on all types. Also, if you could modify the type, you could just put the other stuff at the start anyway. There's a lot of other stuff that's broken by forbidding this too.

So, what would have to be annotated is probably the container type – that is, the return value of container_of – not the field type. The desired optimization is in a scenario like this:

fn unknown(x: &mut i32) { … }

struct Pair { a: i32, b: i32 }
fn foo() {
    let mut p = Pair { a: 10, b: 42 };
    unknown(&mut p.a);
    println!("{}", p.b);
    //             ^^^ known to be 42?

Ideally the compiler should be able to, without knowing the contents of unknown, optimize println!("{}", p.b) to println!("{}", 42). After doing so, it could also elide the write to p.b entirely, since nothing ever reads it. It currently doesn't do these optimizations, but if it could, it would help ensure some abstractions are really zero-cost.

However, this optimization is invalid if unknown can legally use container_of to go from a reference to p.a to a reference to p, and then modify p.b. Thus, I think it should be UB by default for unknown to do this, but Pair could have an attribute to opt into having &mut p.a carry permission for all of p.

Most allocators wouldn't be affected by this at all, since the data pointers they return are not references to a field of a struct. But if an allocator does do so, e.g. if it uses a structure like

#[repr(C)]
struct Allocated<T> {
    metadata: AllocationMetadata,
    data: T,
}

then it is Allocated that would need to be annotated, not T.

FWIW, I haven't talked this through with others before; I'm not sure what people would think of the idea that a reference could carry extra permissions beyond its own type's bounds. But from an optimization perspective I think it fundamentally makes sense.

[tcsc]

@RalfJung

Yeah, C++ programmers do all this -- and C++ programs are full of UB, as evidenced by the never-ending stream of security issues caused by memory safety violations.

This is true, but while I cannot prove it, I strongly believe it would continue to be true if C++ had a formal model — this is not the thing that makes it hard to write correct C++ code, not even close.

So you should at least accept that your notion of what is "intuitive" or "local" is a very subjective one

So, from before you said "the apparent non-locality arises because of the "history" that I mentioned above; it can be explained in an entirely local way by adding some extra state"

For clarity, I'm inerpreting this as: 'reasoning about stacked borrows becomes local reasoning if you model the pointer as having extra state having to do with it's history.'

So, this seems to not help. It seems to say to me to be equivalent to "it can be reasoned about locally so long as you bring all that non-local historical state around with each pointer". Which is probably a useful way to reason about the model formally, but less so for reasoning about code running under the model.

Specifically, to your assertion that "non-local" and "unintuitive" are subjective (probably):

1. How do I reason about the history of a pointer (well enough to decide "this pointer here is indeed sound to use in this way") without that reasoning requiring a great deal of non-locality? To me, this seems like there's no way. To be clear: my concern is whether or not programmers in practice can write, extend, and audit unsafe code. If they must mentally construct the set all possible histories of a pointers, with respect to the histories of all other pointers to the same value... Well. it seems bad.

2. As to whether or not the unintuitiveness is subjective... I think it's fairly self-evident that provenance is unintuitive. The fact that your article is named "pointers are complicated" is something of a citation of that. That said, I'll withdraw this since I don't think intuitiveness is as required of property for a good solution here, as almost everything else I've mentioned.

---

Anyway, I'm not married to the idea of it being syntactic either, that's just a way that makes it easy to verify when auditing, reviewing, or extending code (which may be old or you may not have written in the first place). I'm open to other options that don't throw these away entirely, and believe you if you say there's no coherent way to make this work syntactically.

But please understand: The problem with it being the history of the pointer is that it leads a combinatorial explosion the further back you track a pointer mentally, especially given that all pointers to the value could potentially can invalidate each-other. This is a very bad problem.

If basing it on history in this way is the only possible way an aliasing model can work, then honestly the whole thing feels a bit hopeless for humans ever being able to write correct unsafe Rust without it being full of UB.

I don't know. Even if it's less UB than C++, that's a small mercy.

[comex]

@tcsc

That line is UB because ref1 's lifespan hasn't ended yet. Once ref1 's lifespan ends, ptr1 would be usable (it's not invalidated, just temporarily restricted by the existence of that mutable reference).

So, modifying the example, this would be well-defined?

let mut s = 0;
unsafe {
  let ref1 = &mut s;
  let ptr1 = ref1 as *mut _;
  *ref1 = 2;
  *ptr1 = 3;
  // assert_eq!(*ref1, 2); // Removed from Ralf's example
  assert_eq!(*ptr1, 3); // I added this
}

Which means it would presumably also be well-defined when factoring out the raw pointer stuff to functions:

static mut PTR1: *mut i32;
// "Unknown" in the sense that the compiler may not be
// able to see these functions' bodies while compiling the
// caller code.
unsafe fn unknown1(r: &mut i32) {
    PTR1 = r;
}
unsafe fn unknown2() {
    *PTR1 = 3;
}
unsafe fn unknown3() {
    assert_eq!(*PTR1, 3);
}

let mut s = 0;
unsafe {
  let ref1 = &mut s;
  unknown1(ref1);
  *ref1 = 2;
  unknown2();
  unknown3();
}

But that means we cannot move *ref1 = 2; past unknown accesses/calls:

unsafe {
  let ref1 = &mut s;
  unknown1(ref1);
  // *ref1 = 2; // Moved from here...
  unknown2();
  *ref1 = 2; // ...to here...
  unknown3(); // ...causing an assertion failure here!
}

This may be an acceptable loss; indeed, this transformation isn't justifiable by LLVM noalias alone, so the compiler doesn't currently do it. But it is a loss. And the compiler would have to refrain from performing such a transformation even though it doesn't see any code taking raw pointers to things.

(Which is a more general problem: special-casing code that never takes raw pointers to things doesn't work well in the presence of calls to unknown functions. There is a possible world where the compiler does a global interprocedural analysis that tracks some sort of "doesn't do anything weird with this reference" flag. This would be a lot of work to implement on top of LLVM, and it would have to assume the worst when dynamic dispatch is involved, or when references are stashed inside other data structures in a way that's too complex to track. But it's not completely impossible.)

On another note, we presumably do want to treat a local variable or temporary like a reference, in requiring uniqueness at least as long as the last access to that variable. After all, it's extremely important to optimize away redundant local variables. Here's the original example again:

let mut s = 0;
unsafe {
  let ref1 = &mut s;
  let ptr1 = ref1 as *mut _;
  *ref1 = 2;
  *ptr1 = 3; // You say this is UB because of the later access
  assert_eq!(*ref1, 2); // Later access can be optimized away
}

Then, changing the reference to a local variable, this should be equally UB:

let mut s = 0;
unsafe {
  let ptr1 = &mut s as *mut _;
  s = 2;
  *ptr1 = 3; // You say this is UB because of the later access
  assert_eq!(s, 2); // Later access can be optimized away
}

However, if s is any type that has a nontrivial Drop impl, it will always be accessed at the end of its scope, so its "lifespan", as you call it, will always be its entire scope. This seems to reduce the benefit of your proposed relaxation of semantics - though it doesn't eliminate it.

[tcsc]

So, modifying the example, this would be well-defined?

Yes, modulo the note at the end.

indeed, this transformation isn't justifiable by LLVM noalias alone, so the compiler doesn't currently do it. But it is a loss

Sure, although... this optimization seems only situationally useful at best, and you go on to point out that there are ways we could imaging getting most of these optimizations back in a future where we know if a function squirrels away pointers passed into it.

Regardless, I think if the requirement is that we can never give up any possible optimizations (not even ones we don't use now), we'll never get anywhere. There are tradeoffs to enabling those optimizations.

Making things UB so that you can exploit that via optimizations should be more concretely justifiable IMO

@comex

On another note, we presumably do want to treat a local variable or temporary like a reference, in requiring uniqueness at least as long as the last access to that variable

Yes, I agree, that makes sense and actually seems intuitive. I actually thought about saying in the examples that I'd honestly treat the let mut s = 0 in scope as causing the pointers to be in violation of the same kind of thing.

But I also wasn't sure if we technically allowed that today, and didn't want to make my model stricter than the current semantics accidentally.