Skip to main content

Mutability

The design was decided in #196 and implemented in #195.

Arrays and structs are shared: let ys = xs makes ys another name for the same array, and let q = p another name for the same struct, as in JavaScript, Java and OCaml. Passing one to a function passes a pointer, and a function can fill in what it's given.

Sharing breaks what mut on a variable promises:

let mut xs = [1, 2];
let ys = xs; // not `mut`
xs[0] = 9;
ys[0]; // 9: `ys` changed anyway

This chapter describes how the type checker keeps a promise that sharing can't break. Whether an array or a struct can be changed is part of its type, and every name for it has the same type, so they all agree.

Arrays and structs have a mutability​

The type of an array or a struct has a mutability, which is Mut or Imm:

[τ]  =  Array[μ,τ]S[τ1,…,τn]μμ::=Mut∣Imm∣α[\tau] \;=\; \mathsf{Array}[\mu, \tau] \qquad S[\tau_1, \ldots, \tau_n]^\mu \qquad \mu ::= \mathsf{Mut} \mid \mathsf{Imm} \mid \alpha

Mut and Imm are types of their own kind. A mutability can be an inference variable, like any type, and it's unified and generalized like one. That's all the type checker needs: no subtyping, and no new kind of constraint. A struct's mutability isn't one of its type arguments, so it doesn't change its kind: Box is still of kind Type→Type\mathsf{Type} \to \mathsf{Type}.

In source code, and when types are shown:

WrittenMeans
mut [i32], mut Point, mut (i32, i32)can be changed
imm [i32], imm Point, imm (i32, i32)can never be changed, by anyone
[i32], Point, (i32, i32)either: see annotations

Only arrays, structs and tuples have a mutability. A tuple works like a struct with numeric fields: t.0 = 1 needs t to be a mut tuple, like let t = mut (1, 2), and the variable it's in doesn't matter. The unit type () is always imm. An enum can't be changed in place: match gives the values of its fields, and there's no way to assign to one. mut before anything else, like mut i32 or mut Option[i32], is an error (E0222).

Something can be changed only if its type is mut:

fn push[T](xs: mut [T], x: T); // in `std`

let xs = mut [1, 2];
xs.push(3); // fine
xs[0] = 9; // fine

let p = mut Point { x: 0, y: 0 };
p.x = 5; // fine

let ys = [1, 2];
ys[0] = 9; // error: `ys` is `imm [i32]`, which can't be changed

Assigning to an element, xs[i] = e, needs xs to be a mut array, and assigning to a field, p.x = e, needs p to be a mut struct. So does calling a function whose parameter is mut, like push. What decides is the innermost array or struct of the place that's assigned to: in l.a.x = 1, it's l.a, and in xs[0].x = 1, it's xs[0].

Where the mutability comes from​

The expression that makes an array or a struct decides whether it can be changed. Variables only pass it on:

  • [1, 2], (1, 2) and Point { x: 0, y: 0 } can't be changed: imm [i32], imm (i32, i32) and imm Point.

  • mut [1, 2], mut [], mut (1, 2), mut Point { x: 0, y: 0 } and, for a tuple struct, mut Meters(1.0) can be changed.

  • A function's result has the mutability of its type: Vec.new() could return mut [T], and xs.copy() a new mut [T].

  • mut before a variant's literal, like mut Shape.Circle { radius: 1.0 }, is an error (E0222).

  • mut before anything else, like a variable or the call of a function, is an error (E0222). A copy that can be changed is a call: to_mut(e) copies the value itself and shares what it holds, and to_mut_deep(e) copies all of it. Each type says how with an impl of ToMut or ToMutDeep, so a Vec copies only its elements, not the room it has to grow. imm e stays built in, since it must be deep: it copies what's mut, with the type's impl of ToImmDeep, which it needs: a type without one, or a Vec[Point] without ToImmDeep[Point], is an error, unless imm doesn't change it. to_imm_deep(e) calls the impl itself.

    A literal is told apart by the checker, not the parser: mut before an array, a struct literal or a call of a tuple struct's constructor makes that one mut. mut binds like -, so mut [1].len() is mut of the length, and (mut [1]).len() that of a mut array.

let mut no longer has anything to do with the contents of an array or a struct. It only means the variable can be assigned again:

let xs = mut [1];
xs.push(2); // fine: the array is `mut`
xs = mut [3]; // error: `xs` isn't `mut`

let mut ys = [1];
ys = [2, 3]; // fine: the variable is `mut`
ys.push(4); // error: the array isn't

Aliases share the mutability​

let ys = xs unifies the types of ys and xs, mutability included. So an alias of a mut array or struct is mut too, without saying so:

let xs = mut [1, 2];
let ys = xs; // `mut [i32]`, like `xs`
ys.push(3); // fine, and `xs` sees it

Since this is unification, it works however the alias is made: through a function, a branch, a struct or a closure.

fn id(x) = x;

let a = id(xs); // `mut [i32]`
let b = if c { xs } else { mut [] }; // `mut [i32]`
let get = || xs; // `mut fn() -> mut [i32]`

An alias can't change the mutability. Unifying Mut with Imm is an error:

let xs = mut [1, 2];
let ys: imm [i32] = xs; // error: expected `imm [i32]`, found `mut [i32]`

S { ..base } copies the fields it doesn't give from base, so it can make a struct of another mutability from it, like a mut Point from an imm one. But the copy is shallow: an array, struct or function in a field is shared with base, which would make it an alias with another mutability. So when a field that's copied holds one with the struct's own mutability, base must have the same mutability as the struct:

let q = mut Point { ..p }; // fine, whatever `p` is: the fields are numbers
let l = mut Line { a: mut Point { x: 1, y: 2 }, b: mut Point { x: 3, y: 4 } };
Line { ..l } // error: expected `imm Line`, found `mut Line`
Line { a: Point { x: 0, y: 0 }, b: Point { x: 0, y: 0 }, ..l } // fine: nothing is copied

Deep imm​

What an imm value holds can't be changed either. Otherwise an imm Line could hold a mut Point, and the line would change after all. The tutorial shows the rules from a user's side; this section is about how the checker applies them.

A field has the mutability of its struct. An array or struct in a field without mut or imm has the struct's own mutability, which is a hidden parameter of the struct: struct Line { a: Point, b: Point } is Line^m with a: Point^m. A field can be imm, but not mut (E0224), since a mut field in an imm struct would break the rule. The fields of an enum, which has no mutability, are imm. In a field like imm [Point], the Point is imm too, since an imm array can only hold imm ones.

An imm value can't hold a mut one through a type parameter (E0223): Box { item: mut Point { .. } } is an imm Box[mut Point]. What a struct holds is what its fields hold, not its type arguments: with struct Handler[T] { f: fn(T) -> () }, an imm Handler[mut [i32]] is fine, since a closure doesn't hold what it takes, and with struct Frozen[T] { items: imm [T] }, only an imm T can be held, in a Frozen of either mutability. That's the same as Rust inferring T: 'a from a struct's fields, and it's what makes a struct type well-formed (StructDecl.atMost_ty_iff in lean/BoltMut/Structs.lean).

Unification can't express this, since it's about a type and what's inside it. It's an "at most" constraint instead, with imm ⊑ mut: an array or struct holds only what's at most its own mutability. So [x] needs nothing in the type of x to be more mut than imm. What an array or struct holds must in turn be at most its mutability, and a function's mutability covers what it captured; what it takes and gives isn't looked into, so an imm [fn(mut [i32]) -> ()] is fine.

The constraint decides what's unknown when only one choice works: a mutability that must be at most imm is imm, and one that something mut must be below is mut. What's left about a function's parameters becomes part of an inferred function's type, and its callers must meet it, like class constraints:

fn wrap(x) = Box { item: x }; // forall a. a: imm => fn(a) -> imm Box[a]
wrap(mut [1]); // error (E0230): expected a type that's at most `imm`, found `mut [i32]`

A signature says it with a bound, T: imm, read as "nothing in T is more mut than imm", like Rust's T: 'a for lifetimes. It can be written next to the parameter or in a where clause, and a mutability can be bounded too, as in 'v: 'm:

fn wrap[T: imm](x: T) -> imm Box[T] = Box { item: x };
fn reader(xs: 'v [i32]) -> 'f fn() -> i32 where 'v: 'f = || xs[0];
impl[T: imm] ToImm[[T]] { ... } // checked where the impl is chosen
struct Frozen[T: imm] { item: T } // checked where a value is made

Without the bound, a complete signature is an error where it needs one: in fn hide[T](x: T) -> i32 { let b = Box { item: x }; 0 }, T may be mut. A mut struct can hold anything, so mut Box { item: x } needs nothing. A mutability on its own isn't a type: let x: imm = 1 is an error (E0231). A mut array or struct inside an imm one is still also caught once the types are known (E0223), which shows the whole type.

imm e of a type parameter has the type imm T: what imm makes of T once it's known. The checker gives imm of a known type as that type, with its arrays and structs imm, so imm T only stays for types it can't take apart: type parameters, associated types like C.Item, and types still unknown when an inferred function is generalized. So imm e never needs a constraint:

fn h(x) = imm x; // forall a. fn(a) -> imm a
h(mut [mut [1]]); // imm [imm [i32]]
fn g[T: imm](x: T) -> T = imm x; // imm T is T when T is imm
fn f[T](x: T) -> T = imm x; // error: expected T, found imm T

Like an associated type, imm T only equals itself, since two types can have the same imm: imm (mut [i32]) and imm [i32] are both imm [i32]. In a body, the checker replaces each written imm T by a variable and the same constraint as imm e, which is how imm T becomes T under T: imm. Written imm keeps its meaning before an array, a struct or a function, and is imm T only before a type parameter or an associated type.

mut T and 'm T give a type parameter a mutability (#459). Before a type parameter or an associated type, mut or a name is the T with that outer mutability, whatever its own: mut T with T = imm [i32] is mut [i32], and for a type without a mutability, like i32, it's the type itself. With 'm = ro, 'm T is ro T. A caller that only gives a mut T decides T without its outer mutability:

fn count[I](it: mut I) -> i32 = 0; // count(mut [1]): I is [i32]
fn pick[T](a: 'm T, b: 'm T) -> 'm T = a; // pick(mut [1], mut [2]): mut [i32]
fn leak[T](x: ro T) -> mut T = x; // error: expected mut T, found ro T

Like imm T, it only equals itself, and in a body the checker replaces it by a variable and a constraint, which T decides once it's known, or what the variable is unified with while it isn't. What a 'm T holds is at most 'm, as for a literal of a named mutability; for a T that isn't known, the checker asks for T ⊑ 'm, which is more than needed, but never less.

A closure that can change what it captured is mut. A function type has a mutability like an array's. A closure is mut if it captures a let mut variable, even only to read it, or a value that holds something mut: a mut array, struct or function. Otherwise it's imm, and so is a named function, which captures nothing. By the rules above, an imm value can't hold a mut fn.

Calling a function doesn't need it to be mut, unlike Rust's FnMut: a mut fn can't be reached from an imm value anyway. So a function type written without mut or imm in a signature takes either, like [T], and higher-order functions need no annotations. An imm fn is shown as just fn, since most are, unless that would make two types in a message look the same.

What a closure captures is at most its mutability, by the same "at most" constraint, and a let mut variable makes it mut. So a generic function that makes a closure says how the closure's mutability depends on what it captured:

fn reader(xs: [i32]) = || xs[0]; // 'm: 'n => fn('m [i32]) -> 'n fn() -> i32
fn always[T](x: T) -> fn() -> T = || x; // forall T. T: 'm => fn(T) -> 'm fn() -> T
fn compose(f, g) = |x| f(g(x)); // forall a b c. 'm: 'o => 'n: 'o => fn('m fn(a) -> b, 'n fn(c) -> a) -> 'o fn(c) -> b

In std, an FnIter whose function counts is mut, like the one that for x in xs uses for an array or a Vec.

What this guarantees​

An imm value, and everything it holds, never changes. All the names for a value have the same type, so if one of them can't change it, none can, and an imm value only holds imm ones. A mut value can't be seen as imm, which is what makes imm worth having:

  • code can rely on an imm value it's given staying the same;
  • values that can't be changed can be shared freely, and their literals can be constants: a data segment in Wasm, made once;
  • an imm struct can't be told apart from a copy, so the code generator can store small ones by value;
  • the reactive design knows what can change, and which calls change it, from the types.

It doesn't guarantee what Rust does, that nothing else changes a mut value while you have it. mut values are shared on purpose.

Read-only views: ro​

ro is a view of a value that may or may not change, through which it isn't changed. Without it, a function that only reads takes values of one mutability per call, and two values of different mutabilities can't meet: if c { a } else { b } with a mut and an imm Money is an error. With ro, imm ⊑ ro and mut ⊑ ro: a value of either mutability can be given where a ro one is received.

A ro view is deep. ro [[i32]] is ro [ro [i32]], so a mut [mut [i32]] can be seen as one, and nothing in it can be changed through it. That's sound only because nothing is written through ro: inside a mut value, where an element is both read and written, the mutabilities must be the same, so a mut [mut [i32]] isn't a mut [ro [i32]]. The same goes for function types: a function that takes ro fits where one that takes mut is expected, but not the other way.

ro isn't imm. A ro value can be changed by whoever has it as mut, so an imm value can't hold one (E0223), and imm e of a ro value is a copy. A closure in a ro struct can still be called, since a ro value promises nothing about what its closures change.

ro T is a type parameter seen as ro. A T fits where a ro T is expected, but a ro T isn't a T, so a generic function can't give back what it read through ro [T] as a T. Once T is known, ro T is its view: ro (mut [i32]) is ro [i32], and ro i32 is i32.

A struct's arguments change as its fields use them, its variance. The T of struct Box[T] { item: T } is only held, so a mut Box[mut [i32]] can be seen as a ro Box[ro [i32]], and a written ro Box[[i32]] is that type. The T of struct Handler[T] { f: fn(T) } is in a closure's parameters, so it changes the other way round: an imm Handler[ro [i32]], whose closure only reads, can be used as an imm Handler[mut [i32]], but not the other way, which would give an imm array to a function that changes it. A parameter that's both held and taken can't change at all. A mut struct keeps its arguments as they are, like the elements of a mut array, since what it holds is read and written.

A ro value can't hold a mut one (E0223). Otherwise what's read through it could be changed: through a ro (mut [i32], i32), t.0 would be a mut [i32], and through a ro Box[mut [i32]], so would b.item. Seen as ro, both are ro [i32] instead. A written ro Box[mut [i32]] stays an error, and so does a T that can't be seen as ro, like that of a ro Both[mut [i32]] for struct Both[T] { item: T, f: fn(T) }. A mut closure can still be held, as above.

The rules are proven in lean/BoltMut: in Syntax.lean, Ty.ro is the view and Ty.roParam is ro T; in Subtyping.lean, Sub says where a type fits, and Sub.to_ro that a type fits its view. ReadOnly.lean has the examples. Variance.lean proves when a struct's arguments can change. A parameter in a tuple, or in an object that's imm, ro, or whose mutability is a parameter that becomes ro, is covariant, like the T of Box[T] { item: T }: mut Box[mut [i32]] can be seen as ro Box[ro [i32]]. One in a function's parameters is contravariant, like the T of Handler[T] { f: fn(T) }: an imm Handler[ro [i32]] can be used as an imm Handler[mut [i32]]. One in a mut object, or in one whose mutability is a parameter that's kept, is invariant. The model has function subtyping (Sub.fn), and what an imm object holds can be seen as a supertype of its type (Sub.immCell), as the checker does for an array that isn't mut.

Conduit has a ReadOnly mutability too, which is deep in the same way: under it, an array's elements and a data type's fields fit covariantly, and so does what an imm object holds, while a closure takes its parameters contravariantly. A function called at ro gets an instance of its own, since Conduit doesn't take ReadOnly as a mutability argument.

Named mutabilities​

A name like 'm, written where mut or imm would be, is a mutability that's the same wherever the name is. The tutorial shows how to use them; this section is about how the checker treats them. ' marks the name, as for labels and Rust's lifetimes: without it, m [i32] would be the type m applied to i32.

  • A name is a parameter of the function or impl whose signature it's in, like a hidden one, but shared: every 'm in the signature, its where predicates and its body is the same. Names don't need declaring: using one is enough. Like a hidden parameter, the caller chooses it, so the function can't change what has it, and fn make() -> 'm [i32] = [1] is an error.

  • A name can be written before a literal, as mut can: 'm [1], 'm (a, b) and 'm Point { x: 1 } are of mutability 'm, which the caller may make mut. Nothing is mut unless it's asked for, and writing the name asks for whatever the caller gives. What the literal holds must be at most 'm. Before anything but a literal, a name is an error, as mut is (E0222).

  • A class declares its names (#453), after its type parameters, as a struct does. A name written in a class method's signature must be one of them: it never appears from nowhere.

    class Default[T, 'm] { fn default() -> 'm T; }
    impl[T] Default[[T], 'm] { fn default() = 'm []; } // the impl's 'm
    impl[T] Default[Vec[T], mut] { fn default() = Vec.new(); }

    An impl gives them, as it gives types, and an instance matches them exactly, so an impl for mut alone, like that of Vec, is only for mut, and impl Default[[i32], imm] and impl Default[[i32], mut] don't overlap. An impl that leaves one out, like impl Default[Bool], is for any. The types the class gives an impl's method are well-formed there, so that 'm [] may hold a T: a call checks that what a 'm T holds is at most 'm where it chooses 'm.

    A bound that leaves one out is for any mutability. fn fresh[T: Default]() -> mut T = default() may use Default[T, m] for every m, and a call needs an impl for each, so fresh works for [i32] but not for Vec[i32]. An associated type can depend on the name, so C.Item needs it written, as in where Get[C, 'm].

    A function whose class constraint has one of its mutabilities, like where Freeze[C, 'v], gets an instance for each mutability it's called with, since that can choose the impl.

  • Only functions, impls, classes and structs have names. An impl's associated types can use its names too: impl[T] Iterable['m FnIter[T]] { type Iter = 'm FnIter[T]; ... } is for an FnIter of either mutability, and its Iter has the same one. An impl's names, like its type parameters, must be in its instance, since that's all choosing the impl decides: impl[T, 'v] Iterable[Vec[T]] is an error (E0234), and impl[T] Iterable['v Vec[T]] is what's meant. A name elsewhere, like in a const, a type alias outside an impl, a body that isn't its function's or a field whose struct doesn't declare it, is an error (E0225). A name before a type that can't have a mutability, like 'm i32, is E0222.

  • Types show names, and a name for a mutability that's shared but not written: one that a body decides, or a variable of an inferred function. Such names start at 'm, so that they don't read like the type variables a, b, ...:

    fn pick(c, a, b) = if c { array_len(a); a } else { b }; // forall a. fn(Bool, 'm [a], 'm [a]) -> 'm [a]
    fn same(xs: [i32]) -> [i32] = xs; // fn('m [i32]) -> 'm [i32]
    fn size(xs) = array_len(xs); // forall a. fn([a]) -> i32

    A mutability that appears once isn't named: it's either, and it isn't linked to anything.

Names in structs​

A struct declares its names after its type parameters, like struct VecIter[T, 'v] { data: 'v Vec[T], index: i32 }. A type gives them after its type arguments, like VecIter[i32, imm]. One that isn't given is decided like the mutability before a type: a parameter in a function's signature, an unknown in a body, and the struct's own in a field. More than the struct declares is an error (E0232), and so is a name declared by an item that isn't a struct, a function or an impl (E0233). A function or an impl can declare its names too, but doesn't have to.

A name is at most its struct's mutability. An imm VecIter[i32, mut] would hold a mut Vec, which imm being deep rules out. So making a struct adds 'v ⊑ m for each name its fields have, where m is its mutability, and what a field with a name holds is at most that name: T ⊑ 'v for data: 'v Vec[T]:

mut VecIter { data: mut_vec, index: 0 } // fine: mut VecIter[i32, mut]
VecIter { data: mut_vec, index: 0 } // error (E0223): an `imm VecIter[i32, mut]` can't have a `mut` mutability argument
fn frozen[T](v: 'v Vec[T]) -> imm VecIter[T, 'v] where 'v: imm = VecIter { data: v, index: 0 };

The last one needs 'v: imm, or 'v could be mut. It doesn't need T: imm: v is a 'v Vec[T], so T ⊑ 'v, which it can assume, since v exists. A struct can bound its names, like its type parameters, which is checked where a value is made: struct Frozen['v: imm] { data: 'v [i32] }.

A struct update, VecIter { index: 1, ..it }, keeps the names of it, since the fields it doesn't give are shared. Types show a name that's known, like VecIter[i32, imm], and leave one out that's generic and appears once, like the mutability before a type: VecIter[T]. One that's left out before one that's shown is '_.

Open questions​

  • A name used once says nothing that leaving it out doesn't, and could be a warning.
  • Impls for struct type constructors. impl Functor[Box] is for boxes of either mutability, so fmap must return a Box with the mutability of the one it's given, which it can't make: Box { item: f(b.item) } is imm. Higher-kinded types tie the mutability of the result to that of the argument, and what that should mean isn't decided. imm e gives an imm one, but not one of a caller's mutability.
  • Enums with a mutability, so that a variant can hold something that can be changed without a type parameter, and so that an enum can be changed in place.