How does the compiler infer types in this Box::leak(node).into()?

Question

I'm trying to understand linked_list.rs and I came across this line in the push_back_node function where node is a Box:

let node = Some(Box::leak(node).into());

This somehow produces an Option<NonNull<Node>>> even though no types were specified. What's going on here and why does it work?

Answer 1

Almost all of the types are determined just by the functions being called. The only tricky one is the into call.

If t has type T, then Some(t) is of type Option<T>. If bx has type Box<T>, then Box::leak(bx) has type &mut T. into uses whatever information available (within reason) to determine the input type and the expected output type and uses the Into trait to determine if a conversion is possible.

So since node (before this rebinding) has type Box<Node<T>>, Box::leak(node) has type &mut Node<T>. The into converts to some type U to be determined, and the Some wraps in an option as type Option<U>.

However, that's not all we know. Later on in push_back_node, we have the line self.head = node. That constrains the type of the new node (which we said was Option<U> for some type U) to be the same as self.head. self.head is known to have type Option<NonNull<Node<T>>>, so U must be NonNull<Node<T>>.

So the into call has to convert from &mut Node<T> to NonNull<Node<T>>. Check if there's an implementation of Into<NonNull<Node<T>>> for &mut Node<T>...and there is! If U implements From<T> then T automatically (via a blanket impl) implements Into<U>, and there's an implementation of From<&mut T> for NonNull<T>!

---

For more (and a more precise overview of how the compiler thinks about this), check out the chapter on type inference and the next chapter on trait solving in the rustc dev guide.