Strong updates status

TLDR: It seems to me strong updates would be quite beneficial and might not be "too hard" to provide given what Rust already provides. This thread aims at gauging where the community stands in that regard. (Is it something that could be considered 10 years from now? Or is it something better suited for a new language?)

I call strong update the operation of assigning both a value and a type to a place, while weak update only assigns a value (which must thus have the same type). For example:

fn main() {
    let mut foo = MaybeUninit::uninit();
    // Here, foo has type MaybeUninit<Foo>.
    Foo::new_in_place(&mut foo);
    // Here, foo has type Foo.
    foo.process();
}

impl Foo {
    // The mutable reference has type MaybeUninit<Foo> now and
    // type Foo at the end of the borrow. See the unsafe mental model
    // for more information.
    fn new_in_place(foo: &mut [MaybeUninit<Foo> .. Foo]) {
        *foo = Foo;
    }
    fn process(&self) {}
}

Link to the unsafe mental model, in particular the mutable reference section.

Strong updates would benefit MaybeUninit, Pin, NonNull, NonZero, and any other repr(transparent) types, where wrapping types are used to track properties of the wrapped value. Those properties could be modified in place without copy or move (and without relying on the compiler to optimize such copy/move). Type states are a general category of such "wrapping types adding/removing static properties", replacing by-value functions like fn close(door: Door<Open>) -> Door<Closed> to by-ref functions like fn close(self: &mut [Door<Open> .. Door<Closed>]).

Design questions:

  • The new type must have the same layout as the old one. This is a constraint of using the same place.
  • How to deal with control flow branches (think strong updates inside if-branches)? The abstract interpretation answer would be to use the least upper bound (with respect to subtyping), but a simpler initial solution would be to require the type to be the same when control flow joins. See first example below.
  • Moved-out places could have a "no access" type and could thus be rassigned later. See second example below.
  • Modifying the type of a place has a recursive effect to its container stack. For example changing the type of a field with a generic type, would also change the associated type parameter of its containing struct (and so recursively up to the allocation containing that place). This action-at-a-distance might initially be surprising.
let mut x: MaybeUninit<i32> = MaybeUninit::uninit();
if b {
    x = NonZero::new(42).unwrap(); // x: NonZero<i32>
} else {
    x = 13;  // x: i32
}
// This could be rejected because x has different types.
// Or this could be accepted by using i32 as the least upper bound of
// NonZero<i32> and i32 (since the former is a subtype of the second).

Example for moved-out places (not convinced it's useful, but it's possible). Strong updates is just a generalization of moved-out places.

let mut x: NotCopy = NotCopy::default();
consume(x);
// Now x could have type NoAccess (which provides to valid operations).
x = MaybeUninit::new(NotCopy::default());
// Now x has type MaybeUninit<NotCopy> and can be used again.
3 Likes

The general term for this would be flow-dependent typing, as the type of a place depends on where in the control flow you are.

There's a fundamental problem with arbitrary cross-routine flow typing — what happens in the case of an unwind?

fn transform(it: &mut [T .. S]) { /* … */ }

let mut place = T::new();
let _ = catch_unwind(|| {
    transform(&mut place);
});

// what is the type of `place` here?
// how do we drop `place`?
// which happens even without a catch!

It also causes issues when trying to integrate into a language because &mut [T .. S] isn't actually a type, it's a property of flow pretending to be a usual type. You can't properly do type things to it like put it in a Box<_> or Option<_>. C++ has all sorts of oddities due to its references being not quite full types; type transforming references would be even less standard in their behavior compared to usual affine types.

While value and flow dependent typing is a strong way to reason about code correctness properties, encoding them into a static type system (especially one with unwinding) is a hard problem.

3 Likes

How does Typescript work around those issues? It has exceptions at least

Primarily TypeScript sidesteps the issues by not having arbitrary flow typing across routines — in signatures you're mostly limited to type narrowing, and what's produced is actually a predicate used for flow typing in the caller, not a change of type in the caller. Assertion functions can impact the type in the caller, but not by themselves, only by telling the caller that certain input values throw.

TypeScript also benefits from the fact that it's a fully reflection enabled dynamic type system at runtime, so the value can be typed as T | S and cleaned up without any problem, unlike in Rust's type system where the type must be known (or tagged separately) in order to properly manipulate the value.

1 Like

This is the "How to deal with control flow branches" design question I wrote. Unwinding panics is just control flow to exit the function (recursively) so it merges with the other function exit points (like after the then and else branch of an if). The 2 options I described are: least upper bound (hard to do because it needs a strong subtyping story which Rust doesn't really have at the moment) or equality (easy to do and understand but not as expressive). To illustrate in your example, transform() can only panic if:

  • (least upper bound) T (or whatever is the current type of the value in the reference) is a subtype of S
  • (equality) the mutable reference has been written with a value of type S

Otherwise, it is a type error to panic. This will need some improvement on how Rust handles panic. But such feature requests already exist since crates like no-panic exist. One could also imagine a way to assign a dummy value of the correct type in case of panics, but that can get complicated. My personal opinion is that using panics as control flow is a bug and panics should always abort, but that's sadly not the case since panics were considered closer to exceptions than controlled segfaults.

I don't follow the second part of the sentence. &mut [T .. S] is not a type in today's Rust. This is a hypothetical backward-compatible extension where &mut T is a syntactic sugar for &mut [T .. T]. The definition of &mut [T .. S] is the set of places with temporary exclusive access holding a value of type T which will hold a value of type S when giving back the exclusive access (i.e. on the last write access of the temporary exclusive access). Note that this obviously composes:

fn bar(x: &mut [T .. S]) {
    foo::<T, U>(x); // reborrow at &mut [T .. U]
    // x: &mut [U .. S]
    bar::<U, S>(x); // reborrow at &mut [U .. S] but could also just be a move
    // x: &mut [S .. S] so it's ok to return
}
fn foo::<A, B: Default)(x: &mut [A .. B]) {
    let _: &A = x;
    *x = B::default();
}

I don't see any issues there. That type already exists in Rust semantically (usually called prophecies), it just doesn't exist syntactically. Here's an example with Option<&mut [MaybeUninit<Rest> .. Rest]> (Rest must have no niches, see below):

/// Processes as much foo as possible.
///
/// If `rest` is `Some`, any remaining unprocessed `foo` is stored there.
fn process(foo: Foo, rest: Option<&mut [MaybeUninit<Rest> .. Rest]>) {
    let actual_rest = process_with_rest(foo);
    if let Some(rest_place) = rest {
        *rest_place = actual_rest;
    }
}

let mut rest: MaybeUninit<Rest> = MaybeUninit::uninit();
process(Foo::from_stdin(), Some(&mut rest));
// We now have `rest: Rest` without unsafe.

Yes. It's a hard problem, but as I said in the initial post, Rust is in a very good position to solve it (because it has a strong notion of exclusive access, which is close to linearity, which is what strong updates need). But I agree that this only makes it easier, not easy, which is why I believe that at least 10 years are needed to get there. The question of this thread is whether the community sees value there. See There should be a way to unwrap MaybeUninits without moving them · Issue #61011 · rust-lang/rust · GitHub for a user that would actually like something like this.

As noted in that issue, it's not enough to have the same layout, one also needs the same niches (which in the case of MaybeUninit means no niches). Said otherwise, it's not enough for the strong update source and destination types to have the same layout, but the allocation type, which the place is in, to have the same layout. For example:

let mut x = Box::new(Some(MaybeUninit::<bool>::uninit()));
let r = x.as_mut().as_mut().unwrap();
*r = true; // INVALID: can't update type from MaybeUninit<bool> to bool within Option

Semantically, your

fn new_in_place(foo: &mut [MaybeUninit<Foo> .. Foo]) {
    *foo = Foo;
}

Foo::new_in_place(&mut foo);

Behaves like:

fn new_in_place(_: MaybeUninit<Foo>) -> Foo {
    Foo
}

let foo = Foo::new_in_place(foo);

So wouldn't it be better to think of this feature as "output parameters", like the ones in C#? The special behavior justifies a keyword for passing them (&mut is not good enough, unless you want to breach some layers of semantics) - I'll use let because it signals that we are creating a binding:

fn new_in_place(_: MaybeUninit<Foo>, let output: Foo) {
    output = Foo;
}

Foo::new_in_place(foo, let foo);

The point is that you are not "assigning a type" to foo - you are moving foo into the function and binding a new foo with the new type.

2 Likes

This is true for the MaybeUninit example. But strong updates are more general than that. Here is an example with type-state that is not simply output parameter:

struct Door<State> {
    dimensions: Dimensions,
    weight: Weight,
    angle: f32,
    // ... lots of fields
    state: PhantomData<State>,
}
enum Open {}
enum Closed {}

impl<T> Door<T> {
    fn open(self: &mut [Door<Closed> .. Door<Open>]) {
        // Modify relevant runtime fields.
        self.angle = 42.;
        // Update (strongly) the type-state from Closed to Open.
        self.state = PhantomData::<Open>;
        // self.state changed from PhantomData<Closed> to PhantomData<Open>
        // which in turn changed the Door<Closed> container to Door<Open>
        // self is now &mut [Door<Open> .. Door<Open>] which permits returning from the function
    }
}

Usually with type-state you need to move/copy the whole struct just to change its type-state. Here you can do it in place.

1 Like

This is for the optimizer to decide.

2 Likes

That's why I wrote "without relying on the compiler to optimize such copy/move" in the first post. I usually like to rely on the compiler to optimize because it's maintenable. But it is sometimes necessary to help the compiler when it matters.

Besides and more importantly, this is not just about optimization, but also about describing intent and about ergonomics.

// This type describes that the function opens a closed door.
fn open(self: &mut [Door<Closed> .. Door<Open>]) {
    self.state = PhantomData;
}

// This type describes that a closed door is consumed and an open door is returned.
fn open(self: Door<Closed>) -> Door<Open> {
    Door {
        dimensions: self.dimensions,
        weight: self.weight,
        // etc with many fields
        state: PhantomData,
    }
}
3 Likes

I'm all for better ergonomics, and I'm not trying to dismiss your idea entirely. My points are:

  1. Semantically, this should be desugared to moving&shadowing. It already has well established scoping rules, relieving us of the need to come up with new one. This also solves some of the design questions in your proposal.

  2. Syntactically, this should not use &mut. &mut implies that I'm sending a mutable reference, which means that if I can get a mutable reference by other means - like from a function or from a slice - I should be able to send it to the function. Which is not the case here - consider this:

    let mut foos: [MaybeUninit<Foo>; 2] = [MaybeUninit::uninit(), MaybeUninit::uninit()];
    
    Foo::new_in_place(&mut foos[0]);
    

    foos[0] should now be Foo while foos[1] is still MaybeUninit<Foo>? This makes no sense. Better use a new syntax, that associates with the argument passing rather than the value that gets passed as an argument.

  3. The decision of whether or not to do it in-place should be left to the optimizer, and the code should at most hint it with annotations. This is the premature optimization Knuth warned us about. Forcing the optimizer to do things one way should be a last resort, and only done after profiling and verifying that it really does the wrong thing.

    I'll agree though that it's a good idea, when using this new construct, to nudge the optimizer to reuse the memory. But this should be done by (lowering to) annotations that one could use even without this construct.

  4. There should not be a "same layout" requirement. The optimizer should be smart enough to bridge changes in the layout. For example - a function that appends a value to a fixed sized array.

  5. There should not be a requirement to pass in a binding. At most, this could be syntactic sugar (just like Foo { foo } can be syntactic sugar for Foo { foo: foo }). And there is certainly no reason to require mutability for this!

1 Like

This doesn't use &mut. It uses places, which &mut is one option. But it also works with other places like mutable variables. See the second and third examples in the first post.

Regarding the array problem, it's the same (or similar) issue as moving out an element of an array. The type system should prevent you to create a &mut [T .. S] to an array element if T != S. One could imagine extending array types to heterogeneous types with the same layout for each element (e.g. [i32, i32, MaybeUninit<i32>] for a partially initialized array or [i32, NoAccess, i32] for a partially moved-out array), and then it would be possible to move out a single element and create a strong mutable reference to a single element.

I don't understand what you mean, but I suspect it's because you think strong updates are about mutable references while it's actually about places.

&mut is not a place though - it's a reference to a place (and, yes, a place by itself - but the place that holds the reference is not mutated, neither its value not its type)

Consider:

let mut bar = MaybeUninit::uninit();
let mut baz = MaybeUninit::uninit();

let qux = if cond {
    &mut bar
} else {
    &mut baz
};

Foo::new_in_place(qux);

bar and baz are the places, and only one of them has its type changed. Which one? That only gets decided at runtime. But the type is a compile-time thing - so after we call Foo::new_in_place(qux), which one gets changed?

Another issue with the whole notion of a &mut [T .. S] type is that Rust has affine typing rather than true linear typing. Consider this:

let mut foo = MaybeUninit::uninit();
let bar: &mut [MaybeUninit<Foo> .. Foo] = &mut foo;

bar here is a reference to foo, but it's a reference that can be used to change foo's type, so as long as the reference is alive we can't tell what foo's type really is because it could be changed at any moment. So far, this works well with the borrow checker = we are not allowed to use foo anyway as long as a mutable reference to it is alive, so it doesn't matter that its type can change. But what if we do this?

if cond {
    Foo::new_in_place(bar);
} else {
    let _ = bar; // will be done anyway at the end of the scope, but let's make it official
}

Rust's affine typing allows us to either use bar once - or discard it. If we use it, foo's type should change. If we discard it, it should remain the same. But... this is only decided at runtime...


&mut [T .. S] is not a type that plays well with Rust's type system. That's why I think it shouldn't be a type of its own, but a property of a function argument. Which also means it should look quite different syntactically - most importantly, you shouldn't be able to take such a "reference" and play with it, you should only be allowed (and required!) to annotate it as such while invoking the function.

1 Like

It doesn't seem that different from how drops are currently handled:

  • After the if-else, bar may have been moved, so you can't use it
  • Drop flags are used when initialization state is not statically known

With strong updates the compiler would just need additional states for the binding.

I do think this feature would work better in conjunction with owning references, since you're giving the T away, and getting a U back. The unwinding issue is also easier when whoever is holding an active &move T .. U will drop whatever value it currently has.

1 Like

I believe that's actually the same issue as the bar/baz example. Strong updates need linear types. The &mut [T .. S] type would need to be linear and thus you wouldn't be able to return it from an if-statement. You would need to use swap_if(cond, &mut bar, &mut baz) instead and thus also initialize the other mutable reference.

This example is actually rejected by typing. It's not a problem of linearity.

// bar: &mut [MaybeUninit<Foo> .. Foo]
if cond {
    Foo::new_in_place(bar); // reborrow
    // bar: &mut [Foo .. Foo]
} else {
    drop(bar); // type error
    // Only &mut [T .. T] types can be dropped, otherwise the contract is not fulfilled.
    // This branch should leave bar with type &mut [Foo .. Foo] so that it unifies with the other branch.
}
// The type of bar is the least upper bound of both branch (more simply the same type), i.e. &mut [Foo .. Foo]. The borrow can end without type error.

Yes, this is true today because Rust doesn't have proper linear types yet. That would be one of the many requirements for this feature. But I believe Rust is particularly well-placed to get there, and this doesn't seem infeasible to me to get there in 10 years if there's demand.

What are owning references? I believe exclusive access should be enough, but curious to learn more.

To me it does seem considerably more complicated than how drops work, because the question of whether bar is dropped or used affects the type of foo. But maybe someone more familiar with the compiler's internals should determine if it really is as complex as I imagine or as simple as you imagine.

Still - syntactically I'm strongly against &mut because it already has a meaning and you are giving it a very different meaning here. You wrote &move T .. U in the end, and it's possible that this is a typo and you meant mut, but I think move is a more descriptive keyword. Maybe change the .. to -> to make it clearer though? &move T -> U. Disambiguities with function/closure types can be resolved with parenthesis.

One other problem, which is present in both the original model and my model, and that's also a result of affine typing vs linear typing - early returns. Consider (I'll still use the original syntax):

fn parse_foo(foo: &mut [MaybeFoo<Foo> .. Foo], text: &str) -> Result<(), ParseFooError> {
    *foo = text.parse()?;
}

let mut foo = MaybeUninit::uninit();
parse_foo(&mut foo)?;
foo.process();

We can only reach foo.process(); if parse_foo returned Ok, and in that case the type will be initialized - but nothing in parse_foo's signature indicates that, so how can the caller know that it's okay to call foo.process()?

Your comment in the else clause is about not allowing to drop bar - which is the very definition of linearity.

This is extremely difficult and borders on untenable. It's the same issue with any linear type support where dropping the type isn't allowed. Linear type support is an entire bundle of problematic issues on their own that would need to be solved before type updates could exist as part of the language.

Forbidding the use of unwinding panics and requiring that panics abort the process or leak their thread is maybe the most realistic way to solve the issue with unwinding edge drops, but it's a conceptual shift that I don't personally see ever happening at this stage in Rust's evolution.

I do agree that type updates compose in a similar manner to type composition. But they still aren't full types, because they represent a type transition and aren't an actual type themselves.

Illustrated:

fn f(it: &mut [T .. S]) {
    // here, it: &mut T
    f(it);
    // here, it: &mut S
}
// at no point, it: &mut [T .. S]

You could describe the initial type as "being" &mut [T .. S], but what you can do with it is only what you can do with &mut [T .. T]. Applying a type transition impacts the "current" type but never the "target" type. It's nonsensical to have impl Trait for [T .. S].

That's not what I'm referring to. I'm referring to having &mut Option<[T .. S]>. You could argue that Option<[u8]> also isn't possible, but [u8] is still a proper type, and, yes, but you can have types like Box<[u8]> which do support DSTs, but you can't have a "strong update type" in a generic container. Box is a special pseudo-primitive type, so maybe it could be special case allowed, but any user defined type has the immediate issue for type updates that you don't have a guarantee that there's only one usage of the type; at a minimum you'd be restricted to positions where unsizing coercion is permitted.

You're discussing the update as a property of a referenced place, and I actually fully agree with that. But Rust's references are just another generic type. E.g. what does it mean to have &mut &mut [T .. S]? Semantics like this actually lend themselves more to C++'s second-class lvalue references than they do to Rust's reference types.

I could maybe see Rust growing narrow support for typestate that looks similar to this, but it'd be limited to typestate annotation that sits on top of the current type system and not allowed to impact type dispatch, only the availability of names after name resolution.

Unfortunately there is a semantic element to it (at the optimization level, at least) because of the fact that addresses are observable. If two places are "live" at the same time, then they have disjoint addresses, and if there's any chance that the address is observed, then the optimizer mustn't allow the two places to actually end up with the same address.

When you write let new = f(/* move */ old);, the semantic order is ideally[1]

  • Evaluate the expression f, producing the function to call.
  • Move the value from place old to the function argument, deallocating old before allocating the argument place (thus allowing colocation).
  • Evaluate the body of the function f.
  • Move the return value of the function to place new, deallocating the return place before allocating new (thus allowing colocation).

But at the level LLVM sees, for nontrivial types f actually looks like fn f(in: *mut T, out: *mut T) and both the input and output places exist concurrently, thus must have disjoint addresses.

When everything gets inlined early, this is less of an issue, since the optimizer can tell that the address isn't observed, so fold the two places into one, despite a small overlap in liveness. For cases where inlining doesn't happen, this means that a copy is, as far as LLVM is aware, semantically required to exist.

Rust's semantics are quite ideologically pure in most ways, but this does make it quite reliant on optimization to fold away a lot of temporaries.

This might be the most workable approach. It also directly mirrors the fn(T) -> U semantics directly, just differing in that the input and output place are known to be the same.


  1. I am a member of T-opsem, but am not speaking for the team. The exact operational semantics are not yet fully decided. ↩︎

3 Likes

Thanks for the detailed answer!

Yes, I agree with this. To address the untenable aspect, I believe linear types could be seen as an orthogonal feature for experts the same way unsafe is. You can write Rust without linear types and without unsafe. They just add expressivity if you want.

I guess I can see the idea but I'm not convinced yet. If you have x: &mut [T .. S] in your linear context, you can do the following things:

  • *x = U changing its type to &mut [U .. S]
  • &mut *x reborrow at &mut [T .. U] changing its type to &mut [U .. S] after the borrow
  • drop(x) if T is a subtype of S (but more practically in today's Rust, if T = S)

In particular, the reborrow temporarily gives the type &mut [T .. U] to that same linear pointer, so in some sense you can change the contra-variant type. But I agree that you can't change the contra-variant type of the initial linear variable, because that's the whole point: when you have such variable, you promise whoever lent it to you that you will return a value of type S. You can't change your promise. And the promise must be tracked somehow. I'm doing it in the type, and I guess you want to do it at function level. Maybe that's enough to get most of the benefits, but I'm usually not a fan of second-class type system features, they ultimately bite you because they don't compose.

Yes, but not because of your argument, simply because [T .. S] is not a type (and not an unsized type either). The notation &mut [T .. S] is the notation of mutable references, replacing &mut T which is now a syntactic sugar for &mut [T .. T].

Same as above. This is not a type, because [T .. S] is not a type. The closest I could guess you mean is &mut [Option<T> .. Option<S>].

You can or cannot do the following operations on this type:

  • You can drop it any time because it's not linear.
  • You cannot write to it because its content is linear (unless T = S which makes it non-linear) and you cannot drop a linear type.
  • You can swap its content (with one of the same type) because that's a linear operation.
  • You can dereference it twice to access a place of type T.
  • You can dereference it twice to write a value of a type with the same layout and niches as T (and thus S).
  • You can dereference it twice to write a value of type S making the inner type non-linear and the whole type just &mut &mut S.

So &mut &mut [T .. S] is just an exclusive reference to an exclusive reference that currently holds T and must hold S when the borrow ends (or when dropped).

I've just seen this in This Week in Rust. It's another proof of the demand of linear types for things like type state. Let's see if it results in a new language or if Rust will be able to catch up in 10 years.

1 Like

I just want to add, that mutable references can't cross unwind boundaries. So that is no problem.