rust-inference.md

Basics of type inference in Rust

Rust's type inference was inspired by the Hindley-Milner type inference system, but prior to 1.0 changed to a novel system based on a concept of "narrowing" the possible type of each expression. Narrowing was (to my knowledge) first publicly explained here: http://smallcultfollowing.com/babysteps/blog/2014/07/09/an-experimental-new-type-inference-scheme-for-rust/

What is a type?

For the purpose of this document, I'll define "type" as the information that allows a language's runtime to determine how member (field and function) access to a value behaves. In "dynamically typed" languages, this information is present at runtime. In some "statically typed" languages, it is only present at compile-time, and is reflected in the generated assembly as offsets, labels, function pointers, and so on. Other languages, such as Java and Go, use a combination of static and dynamic typing.

Rust's types

Rust is statically typed. However, like C++, it provides mechanisms to explicitly use dynamic polymorphism, making some (static) types behave more like dynamic types. These are types that act somewhat like base-class pointers/references/objects in traditional object-oriented languages such as C++, C#, and Java, though their implementation is a bit different. The dyn keyword is typically used to denote such types.

Lifetimes

Rust has one very unique feature in its type system: lifetimes. The type information of every value includes a lifetime. Lifetimes may seem somewhat abstract or obscure, because they differ from the rest of the type system and from other languages' type systems in some important ways:

• Usually, lifetimes are implicit, meaning that the compiler infers them.
• Lifetimes can be named, but new lifetimes cannot be defined by the user. They are only generated by the compiler.
• Lifetimes can never be made "dynamic". They are entirely a compile-time construct.
• Lifetimes are the only part of Rust's type system that closely follow traditional struct-inheritance rules. However, this relationship to inheritance is not very intuitive: a "sub-lifetime" actually "lives" longer than its "parent's" lifetime.

In source code, the "lifetime" of a value is simply the area of the code in which that value is considered valid, i.e., it can be accessed within expressions. Until the introduction of the 2018 edition, lifetimes were lexical, meaning that the "areas of code" in which lifetimes existed were simply scopes (i.e. code surrounded by curly braces). The 2018 edition introduced "non-lexical lifetimes", which permits lifetimes to be distinct from scopes. (This feature has now been backported to the 2015 edition as well.) This generally makes lifetimes intuitively easier to work with, at the cost of making the exact rules about lifetimes somewhat more complicated.

The lifetime annotation syntax (which names a lifetime) is 'foo, where foo is the name of a lifetime. Naming a lifetime is most often useful when dealing with references; a reference with a named lifetime is denoted &'foo or &'foo mut. There is one special lifetime, 'static, which is the "longest" lifetime: it is valid until the program ends. This a little bit stranger than it sounds: any object that does not include any non-'static references is actually 'static, even though it may be dropped before the program ends. For example, a String is considered 'static. Much like non-lexical lifetimes, as a formal rule, this is somewhat non-intuitive, but it actually makes 'static the easiest lifetime to use: 'static lifetimes may be "ignored" by treating objects with the 'static lifetime essentially like values in a garbage-collected language such as Java.

Some rules

• Function signatures must always include explicit types, excluding lifetime information. There are three cases (which may occur together for a particular function) that permit the signature not to include full static type information:
  • Generics: much like C++ templates, these are "monomorphized", meaning that for each specific combination of types used to call the function, a "specialized" copy of the function is generated that uses those types in place of the generic type parameters.
  • impl Trait in parameter types: these are somewhat like a shorthand for generics and will thus be monomorphized.
  • impl Trait in return types: this is merely a way of eliding type information that would otherwise be visible to the caller. The actual type returned is determined by the function body. impl Trait does not permit functions to conditionally return different types or to use the return type for type inference within the function (see below).
• Lambda (closure) signatures don't count as function signatures for the purpose of the above rule that function signatures must be fully typed.
• Additionally, as mentioned above, some types represent dynamic polymorphism. These are not relevant to type inference; for the purpose of compilation, a dynamic type such as Box<dyn Clone+Debug> is fully specified and does not require inference.
• Type inference must not conflict with any type information provided by the source code (of course).
• There are a variety of conversions in Rust that can happen implicitly or explicitly; for instance, the Deref trait permits calling Foo's methods on Box<Foo>, and the ? operator makes use of the From trait to facilitate creating "chains" of typed errors without explicitly building new error objects wherever a function returns an error.

Lifetimes

• As mentioned above, lifetimes are generated automatically by the compiler, never by the user's source code.
  • Local reference values rarely require lifetime annotations.
  • Function signatures require lifetime inference, meaning that lifetime annotations could be explicitly provided for every parameter and the return value, but in practice this is rarely necessary.
• All values have lifetimes, but values of non-reference types (such as String and Box) typically have the 'static lifetime, which is safe to "ignore" (as explained above).
• Structs may have associated lifetime specifiers (i.e. lifetime labels). This allows structs to contain references. Lifetimes for such structs follow essentially the same rules as lifetimes for bare references, with the exception that a single struct may have multiple associated lifetime specifiers.
  • Lifetimes of structs are notated with <> alongside generic type parameters, but such structs do not require monomorphization: i.e., the compiler does not generate a separate struct definition for every lifetime with which the struct is instantiated. This is because lifetimes are associated with values rather than types, though as noted above, some types necessarily have the 'static lifetime regardless of how the value is instantiated or used.
• Lifetime inference for function signatures is fairly simple:
  • If a function doesn't return a value, or only returns values with 'static lifetimes, the lifetimes of the input parameters are arbitrary, i.e., the only requirement for calling the function is that the input values be valid at the call-site.
  • If the function returns a value with a single lifetime:
    • If only one input parameter includes a non-'static lifetime, the return value is assigned that parameter's lifetime.
    • If the function is a method call whose receiver (self) is a reference (&self or &mut self), the return value is assigned the same lifetime as the receiver, even if other parameters have non-'static lifetimes.
    • Otherwise, lifetime annotations are required.
  • These rules still apply to un-annotated elements of a partially-annotated function signature. For instance, fn Apply<'a>(&self, foo: &'a mut Foo) -> (&usize, &'a mut Bar) is a valid method signature, and the lifetime of &usize will automatically match the lifetime of &self.
• As mentioned above, a lifetime "inherits from" another lifetime if and only if it "lasts" at least as long as the parent lifetime. The syntax for indicating that a lifetime outlives another is similar to the syntax for a generic type implementing a trait: <'a, 'b, 'c: 'a+'b> means that 'c must outlive both 'a and 'b.

The fun part: narrowing inference is intuitive

Writing expressions and statements without explicit types is actually rather similar to writing in a dynamically-typed language such as JavaScript or Python: types are rarely needed. If you can look at a piece of code without explicit type information and figure out what the types must be in order to make the code "work" with the given function signature, then the compiler can probably figure it out, too.

If you want to think of it more formally, think of type inference proceeding forward from the start of the function and backwards from the end and from any return statements (or ?s) and labeling each value with a set of restrictions (such as "must be convertible to a specific error type" or "must have a lifetime that is valid at this point"). If, after analyzing all of the expressions, the restrictions are specific enough to provide concrete types to all values in the function, and there are no conflicts, then type inference is complete; otherwise, explicit type annotations may be necessary, or there may simply be a type error.