Least upper bound type inference

[degory]

The compiler currently uses a heuristic to determine a common type across multiple element types in a number of scenarios. This heuristic is only able to infer a common type that actually appears as an element type. This is sufficient in most cases, but there are times when there is no common element type assignable from all elements, and some common ancestor type would be the correct choice. When this occurs, the compiler either infers object or requires an explicit type, depending on context.

Ideally we would pick the least common bound - i.e. the most derived type that is an ancestor to all element types. However, in practice on .NET there are many interfaces that relatively derived and are also ancestors of many framework types.

To avoid picking unsuitable interface types when better alternatives exist we can try a narrow search first and only broaden if we don't find a suitable common type:

• 1. Only the types of elements, picking the most derived type that is assignable from all the others (this is similar to the current heuristic, except it will prefer more derived types where possible, rather than whichever common element type is encountered first)
• 2. All concrete ancestor types (classes or structs)
• 3. All implemented traits

We will also need

• A mechanism for resolving ties. I don't believe ties are possible for concrete types, because ghūl has only single inheritance for classes and structs, but it will be an issue for traits). We may need another measure of specificity as well as or instead of 'most derived' (i.e. furthest from object) we might want to look at which matches are closest to the most element types or some similar heuristic.

We should replace the existing common element type inference heuristic with LUB when:

• Inferring the element type of list literals
• Inferring the type of generic function type arguments
• Inferring the type of generic class, struct and union type arguments in constructor expressions
• Inferring the return type of function literals with multiple return statements
• Inferring the type of if expressions from the types of their branches

Where the elements are all tuple literals, we could also optionally:

• Infer the tuple elements independently rather than inferring the type for the tuple as a whole (because this will end up inferring object because tuples types are type invariant and the different tuple types for the different elements will all be incompatible with each other)
• Infer tuple element types recursively, so lists of tuples of lists for example get consistent common element types all the way down. For example l should be inferred as having type (int, object, Base[])[]

class Base is
si

class DERIVED: Base is
si

let l = [
    (1234, "hello", [DERIVED(), DERIVED()]),
    (1234, 1.0D, [Base(), Base()]),
    (5678, object(), [Base(), DERIVED()])
];

It may be necessary to pass all the element types up to the top level LUB, or it may be that alternately inferring the element types and then constraining them at each level, working outwards and then back in, will naturally give the desired result

If we do infer tuple elements independently, we need to push the inferred element type back into the tuple literal constructor expressions to override the normal tuple type inference from tuple element types, and ensure they create tuples of the element type (see #1166 - otherwise the resulting tuples will not actually be type compatible with the element type, due to tuple type invariance)