Implementation
-
Types (
ty.rs):Ty::Arrayholds the mutability and the element type, andTy::Adtholds a struct's mutability after its arguments. An enum's is alwaysImm, and isn't shown. A mutability isTy::Mutability(Mut | Imm), an inference variable of kindVarKind::Mutability, a type parameter, or the error type. -
Lowering (
lower.rs):mut [T],imm [T],mut Pointandimm Pointlower to their mutability, and the rest toTy::Unwritten, which each item then replaces withTy::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
wherepredicate,Imm; - in a type alias, nothing: the type it's used in decides.
A name like
'mlowers 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
'vofstruct VecIter[T, 'v](GenericParams::mutability_params), are parameters after its type parameters and before its own mutability.Ty::Adtholds the arguments for them apart from its type arguments, so that they don't change its kind, andstruct_argsgives them to its field types. In a type likeVecIter[i32, imm], a mutability on its own is one of them; those not given areTy::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
(
-
Unification (
unify.rs): mutabilities are equal or they aren't, except that a place that receivesReadOnlytakes any mutability, withflippedsaying which side receives inside a function's parameters. Amutvalue 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'smutor whose mutability isn't known yet (variance::arg_variance). The variance is a fixed point over the fields, likestruct_atoms, and is found from the fields lowered without it (lower::raw_field_types).Ty::Fnholds its mutability last, andfn(...)lowers withTy::Unwrittenlike 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 isImm, orMutwithmut. Indexing, field access,forand patterns take either.check_placelooks for the innermost index, or field of a struct, in the place that's assigned to. Its array or struct must bemut, and a mutability that isn't known yet becomesMut(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 requiresMut. Without an index or a field of a struct, the variable must bemut, 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 isholds::struct_atoms: the atoms of "the fields are at most the struct's own mutability", like'v ⊑ mandT ⊑ '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, likeT ⊑ 'mforxs: '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,immbelow 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 mostimmis decided right away, unless the function assumes a mutability is, which it could be too. A bound likeT: immor'v: 'mlowers toPredicates::at_most(TypeRef::Mutabilityfor the mutability on its own), the solver follows assumptions through'v: 'mand'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 alet mutone makes itMut. - Once a body's types are resolved,
check_deep_immutabilityreports each type with amutarray, struct or function inside animmone, 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_typeinboltlang-hir).
-
ro: a writtenrolowers toMutability::ReadOnly, andTy::ro_insidemakes the mutabilities that aren't written inside itReadOnlytoo, since aroview is deep. A type parameter under it isTy::Ro,ro T, which aTfits where it's received. OnceTis known,Unifier::shallow_resolveandUnifier::resolvegive 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, soro Box[[i32]]isro Box[ro [i32]]. A type parameter that must be at mostro, like theToffn pass[T: ro](x: T) -> T, is given what may change seen asro, and what can't as it is (Unifier::see_as_ro):pass(mut [1])is aro [i32], andpass([1])animm [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): anImmConstraintfrom the type ofeto that of the copy, solved once the type ofeis known (Solver::solve_imm). An array or struct becomesimm, and a struct or variant's type arguments are whatimmmakes 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 mostimm. It isn't lowered to Conduit yet: a copy toimmthere is the type'sToImmimpl, made ofnewandarray_clone, which Conduit'scopiespass turns into anarray_freezewhen 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):mutbefore an array, a struct literal or a call of a tuple struct's constructor (constructs_struct) makes that literalmut, and is kept inInferenceResult::mut_literals. Before anything else it'sNoMutability(E0222). Copies that can be changed are std'sto_mutandto_mut_deep, not built in.- Defaulting (
solve.rs): a mutability left over when a body is checked, and not generalized, becomesImm. 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 Tfor a named mutability, andTfor a generalized or unknown one.TyNamesgives a name to each generalized, unknown or hidden mutability that appears more than once. Schemes leave mutabilities out of theirforall, and show a field constraint that's assigned to asmut 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.txtandtests/checker/mutability/closures.txthave a case for each rule in this chapter. - Proven:
lean/has a Lean proof of a core of these rules: that nothing reachable from animmvalue ever changes, that a well-typed program never gets stuck, and what a call can change. It coversro, 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 thatSolver::mutability_lefinds 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.