Skip to main content

Implementation

  • Types (ty.rs): Ty::Array holds the mutability and the element type, and Ty::Adt holds a struct's mutability after its arguments. An enum's is always Imm, and isn't shown. A mutability is Ty::Mutability(Mut | Imm), an inference variable of kind VarKind::Mutability, a type parameter, or the error type.

  • Lowering (lower.rs): mut [T], imm [T], mut Point and imm Point lower to their mutability, and the rest to Ty::Unwritten, which each item then replaces with Ty::fill_unwritten:

    • in the parameters of a function whose type comes from its class or impl, or that has no body, and in an impl's instance, hidden parameters, numbered after the declared type parameters (FnSig::hidden, ImplHeader::hidden), so that instantiating a scheme and matching an impl handle them like any other parameter;
    • in a body, and in the parameters and the return type of any other function, inference variables, which the body decides (infer.rs, check.rs). So a signature is only complete when it writes every mutability (FnSig::is_complete);
    • in a struct's field, the struct's own hidden parameter (struct_mutability), which a struct's type substitutes with its mutability (struct_args);
    • in an enum's field, the return type of a function without a body, a const and a where predicate, Imm;
    • in a type alias, nothing: the type it's used in decides.

    A name like 'm lowers to a parameter of its function or impl (named_mutabilities), numbered after the declared type parameters and before the hidden ones. A body can use its function's names. A signature whose return type only has written or named mutabilities is complete.

    A struct's names, like the 'v of struct VecIter[T, 'v] (GenericParams::mutability_params), are parameters after its type parameters and before its own mutability. Ty::Adt holds the arguments for them apart from its type arguments, so that they don't change its kind, and struct_args gives them to its field types. In a type like VecIter[i32, imm], a mutability on its own is one of them; those not given are Ty::Unwritten.

  • Unification (unify.rs): mutabilities are equal or they aren't, except that a place that receives ReadOnly takes any mutability, with flipped saying which side receives inside a function's parameters. A mut value shares its contents both ways (Unifier::share_if_mut). A struct's arguments change as its variance says (variance.rs, adt_variance): as they are where they're only held, the other way round in a closure's parameters, and not at all where they're both, or in a struct that's mut or whose mutability isn't known yet (variance::arg_variance). The variance is a fixed point over the fields, like struct_atoms, and is found from the fields lowered without it (lower::raw_field_types). Ty::Fn holds its mutability last, and fn(...) lowers with Ty::Unwritten like an array, so it's a hidden parameter in a signature and the struct's own in a field.

  • Inference (infer.rs): an array or struct literal is Imm, or Mut with mut. Indexing, field access, for and patterns take either.

    • check_place looks for the innermost index, or field of a struct, in the place that's assigned to. Its array or struct must be mut, and a mutability that isn't known yet becomes Mut (Solver::require_mut). A field of a value whose type isn't known yet marks its field constraint as assigned (FieldConstraint::assign), and solving it requires Mut. Without an index or a field of a struct, the variable must be mut, as before.
    • Making an array or struct adds an AtMostConstraint: the element type is at most the array's mutability, and what a struct's fields hold at most theirs, once its fields are checked. What a struct's fields hold is holds::struct_atoms: the atoms of "the fields are at most the struct's own mutability", like 'v ⊑ m and T ⊑ 'v, with a field that's a struct using that one's, as a fixed point for structs that refer to each other. A body assumes what makes its parameter types and its impl's instance well-formed, like T ⊑ 'm for xs: 'm [T], as Rust's implied bounds do (check::implied_assumptions). The solver splits a type into the mutabilities it holds (Solver::solve_at_most), decides what only one choice meets, and keeps the rest. What's left when a group of functions is solved is about their types, and becomes their schemes' bounds; other unknowns are chosen to meet it, imm below first (Solver::settle_at_most). In a body with a complete signature, what's left about its parameters is an error (TypeError::NotAtMost), unless the function or its impl assumes it. A mutability that must be at most imm is decided right away, unless the function assumes a mutability is, which it could be too. A bound like T: imm or 'v: 'm lowers to Predicates::at_most (TypeRef::Mutability for the mutability on its own), the solver follows assumptions through 'v: 'm and 'm: imm (Solver::mutability_le), and a scheme carries them for its callers. A chosen impl's bounds are checked like its class predicates, and a struct's where a value is made.
    • A closure gets a new mutability, the types of the variables it uses from outside (ClosureFrame) are at most it, and a let mut one makes it Mut.
    • Once a body's types are resolved, check_deep_immutability reports each type with a mut array, struct or function inside an imm one, unless an "at most" error already did. The types that no body looks at are reported where they're written, the same way: those of a function without a body, like a class method, of a type alias, and of an impl's instance (written_type in boltlang-hir).
  • ro: a written ro lowers to Mutability::ReadOnly, and Ty::ro_inside makes the mutabilities that aren't written inside it ReadOnly too, since a ro view is deep. A type parameter under it is Ty::Ro, ro T, which a T fits where it's received. Once T is known, Unifier::shallow_resolve and Unifier::resolve give its view instead (Ty::ro_view, Ty::normalize_ro). The view goes into a struct's or enum's arguments where its variance lets them become a supertype, so ro Box[[i32]] is ro Box[ro [i32]]. A type parameter that must be at most ro, like the T of fn pass[T: ro](x: T) -> T, is given what may change seen as ro, and what can't as it is (Unifier::see_as_ro): pass(mut [1]) is a ro [i32], and pass([1]) an imm [i32].

The variables a call gives its callee's parameters are flexible (Solver::begin_call): one that receives a value records it as a lower bound instead of being bound to it, and once the arguments are checked (Solver::end_call), it's settled to the least type of all of them (Unifier::lub, as Ty.lub in lean/BoltMut/Least.lean), then the unifications that gave it lower bounds are done again to check them. So both([1], mut [2]) for fn both[T](a: T, b: T) makes T a ro [i32], whichever comes first. A flexible variable that has to give a value first, like a closure's parameter, is settled with what it has so far.

A parameter like a: [T] links two variables: the array's mutability and T. If T is widened, the array can't stay mut, since a mut array's contents must be what they are, so before the call's variables are settled, the mutability of an object whose contents are widened is made ro, and what a ro object holds at most ro, until that changes nothing (Unifier::force_linked, as LinkedProblem.principal in lean/BoltMut/Linked.lean). So f(mut [mut [1]], mut [[1]]) for fn f[T](a: [T], b: [T]) -> [T] is a ro [ro [i32]].

What a call is expected to be decides its mutabilities before that (Unifier::decide_by), as Sub.none_meet_upper in Linked.lean shows keeps the least solution: longer(mut [1], [2]) for fn longer(a: 'm [i32], b: 'm [i32]) -> 'm [i32] is a ro [i32], but where a mut [i32] is expected, 'm is mut, and the [2] is reported. Only mutabilities: a type that doesn't fit is reported at the call.

A class whose methods only see a parameter as ro, like the T of class Eq[T] { fn eq(a: ro T, b: ro T) -> Bool; }, has the same methods for T and ro T (class_params_seen_as_ro), so the solver compares such constraints, the assumptions and what impls give by their ro views: given Eq[A] and Eq[B], Eq[(ro A, ro B)] holds, as for a tuple of what ro values hold. A class that may change its argument, like Iterator, whose next takes I, doesn't. holds.rs sees ro T as at most ro, so an imm value can't hold it, and ro held by imm is an error (E0223). A mut array or struct held by ro is the same error (infer::mut_inside, with the bound it breaks), also in the parameters of a function's type, so that a generic function called with what makes one of them a ro that holds mut is reported where it's used. Monomorphization gives a function called at ro an instance of its own (Instance::ro), and finds the T of a ro T from where T is written as it is first (uses.rs).

  • imm e (solve.rs): an ImmConstraint from the type of e to that of the copy, solved once the type of e is known (Solver::solve_imm). An array or struct becomes imm, and a struct or variant's type arguments are what imm makes of its fields (solve_imm_adt), so one that's only in a function type stays as it is. A closure, a type parameter, or a type still unknown when the body is solved (Solver::settle_imm) stays as it is, and must be at most imm. It isn't lowered to Conduit yet: a copy to imm there is the type's ToImm impl, made of new and array_clone, which Conduit's copies pass turns into an array_freeze when its region analysis shows nothing else can reach the originals (see Conduit). What such an analysis must show is proven in Lean (below).
  • mut e (infer.rs): mut before an array, a struct literal or a call of a tuple struct's constructor (constructs_struct) makes that literal mut, and is kept in InferenceResult::mut_literals. Before anything else it's NoMutability (E0222). Copies that can be changed are std's to_mut and to_mut_deep, not built in.
  • Defaulting (solve.rs): a mutability left over when a body is checked, and not generalized, becomes Imm. That happens after the errors are resolved, so that an undecided mutability is shown as [T] in them.
  • Showing types: mut T, imm T, 'm T for a named mutability, and T for a generalized or unknown one. TyNames gives a name to each generalized, unknown or hidden mutability that appears more than once. Schemes leave mutabilities out of their forall, and show a field constraint that's assigned to as mut a.x: b.
  • Tests: tests/checker/mutability/arrays.txt, tests/checker/mutability/structs.txt, tests/checker/mutability/named.txt, tests/checker/mutability/params.txt, tests/checker/mutability/readonly.txt and tests/checker/mutability/closures.txt have a case for each rule in this chapter.
  • Proven: lean/ has a Lean proof of a core of these rules: that nothing reachable from an imm value ever changes, that a well-typed program never gets stuck, and what a call can change. It covers ro, variance, imm e, and the solver's shortcuts for "at most" (Solver.lean): how it splits a type, when it can decide an unknown mutability right away, and that Solver::mutability_le finds every chain of assumptions. Proofs has each theorem, with how it links to Bolt.

Vec[T] in std (#197) is a struct, so it gets a mutability like any other, and [T] is shorthand for it. So is a String in std (#199), with mut String taking the place of a separate StringBuilder.