Recursive types may be incomplete

[LeonPuchinger]

Taking a look at the Option type from the stdlib, a problem can be identified:

  type Option<T> {
      has_value: Function() -> Boolean,
      get_value: Function(Option<T>) -> T,
      map: Function(Option<T>, Function(T) -> T) -> Option<T>,
      or: Function(Option<T>, Option<T>) -> Option<T>,
      get_value_or: Function(Option<T>, T) -> T,
      flat_map: Function<U>(Option<T>, Function(T) -> Option<U>) -> Option<U>,
  }

The flat_map method references Option<T> and Option<U> where U is a placeholder that is owned by the method type itself. During initialization of the type, all fields are created as placeholders that are set to IgnoreSymbolType. This initial type with the placeholders set to IgnoreSymbolType is referred to as a barebones type. Some early analysis is performed on this barebone type, but it needs to be completed (turned into a type with all of its type information). To do this, the types of each field are resolved, which, in the case of Option<T> from the above example, is done by resolving the types of the type literals associated with those fields.

This works well until flat_map is resolved. This field is set to a function type literal, which contains recursive type literals to the enclosing type (Option<T> and Option<U>). To create a truly recursive type structure, the Option type must be the same instance as its parent. The type-resolving logic of composite type literals usually forks types when placeholders need to be assumed. It does this so that the placeholders are not set in the original instance, where they would have side effects. There is one exception, however, where the type is not forked when placeholders are involved, which is when the supplied placeholders are the exact same instances as the empty placeholders already present on the type. This is the case for Option<T>, making the type truly recursive at those points. With Option<U>, however, it's a different story. U is a different instance, causing a fork of the type. The problem is: the Option<T> type is not fully complete at this point. The interpreter will complete the original instance of the type, but that does not affect the forked copy of the type.

In the greater picture, Option<T> is now a truly recursive symbol type, except for the return type of flat_map and the callback passed to it. This becomes a problem when flat_map is called multiple times in a chain. The first time flat_map is called, everything works fine. however, the return type of that call is now the incomplete type, where flat_map is still set to IgnoreSymbolType. Trying to call flat_map again on that instance will result in an error.