docs/language/informal/mixin-inference.md

# Dart 2.X super mixin inference proposal

**Owner**: leafp@google.com

**Status**: This is now background material.

The current version of this document now resides
[here](https://github.com/dart-lang/language/blob/master/working/0006.%20Super-invocations%20in%20mixins/0007.%20Mixin%20declarations/mixin-inference.md).

This is intended to define a prototype approach to supporting inference of type
arguments in super-mixin applications.  This is not an official part of Dart
2, but is an experimental feature hidden under flags.  When super-mixins are
specified and landed, this feature or some variant of it may be included.

## Syntactic conventions

The meta-variables `X`, `Y`, and `Z` range over type variables.

The meta-variables `T`, and `U` range over types.

The meta-variables `M`, `I`, and `S` range over interface types (that is,
classes instantiated with zero or more type arguments).

The meta-variable `C` ranges over classes.

The meta-variable `B` ranges over types used as bounds for type variables.

Throughout this document, I assume that bound type variables have been suitably
renamed to avoid accidental capture.

## Mixin inference

In Dart 2 syntax, a class definition may also have an interpretation as mixin
under certain restrictions defined elsewhere.

### Mixins and superclass constraints

Given a class of the form:

```
class C<X0, ..., Xn> extends S with M0, ..., Mj implements I0, ..., Ik { ...}
```

we say that the superclass of `C<X0, ..., Xn>` is `S with M0, ..., Mj`.

When interpreted as a mixin, we say that the super class constraints for `C<X0,
..., Xn>` are `S`, `M0`, ..., `Mj`.

Given a mixin application class of the form:

```
class C<X0, ..., Xn> =  S with M0, ..., Mj implements I0, ..., Ik;
```

for we say that the superclass of `C<X0, ..., Xn>` is `S with M0, ..., Mj-1`.

When interpreted as a mixin, we say that the super class constraints for `C<X0,
..., Xn>` are `S`, `M0`, ..., `Mj-1`.

#### Discussion

A class, interpreted as a mixin, is interpreted as a function from its
superclass to its own type.  That is, the actual class onto which the mixin is
applied must be a subtype of the superclass constraint.  When the superclass is
itself a mixin, we interpret each component of the mixin as a separate
constraint, each of which the actual class onto which the mixin is applied must
be a subtype of.

### Mixin type inference

Given a class of the form:

```
class C<T0, ..., Tn> extends S with M0, ..., Mj implements I0, ..., Ik { ...}
```

or of the form

```
class C<T0, ..., Tn> =  S with M0, ..., Mj implements I0, ..., Ik;
```

we say that the superclass of `M0` is `S`, the superclass of `M1` is `S with
M0`, etc.

For a class with one or more mixins of either of the forms above we allow any
or all of the `M0`, ..., `Mj` to have their type arguments inferred.  That is,
if any of the `M0`, ..., `Mj` are references to generic classes with no type
arguments provided, the missing type arguments will be attempted to be
reconstructed in accordance with this specification.

Type inference for a class is done from the innermost mixin application out.
That is, the type arguments for `M0` (if any) are inferred before type arguments
for `M1`, and so on. Each successive inference is done with respect to the
inferred version of its superclass: so if type arguments `T0, ..., Tn` are
inferred for `M0`, `M1` is inferred with respect to `M0<T0, ..., Tn`>, etc.

Type inference for the class hierarchy is done from top down.  That is, in the
example classes above, all mixin inference for the definitions of `S`, the `Mi`,
and the `Ii` is done before mixin inference for `C` is done.

Let be `M` be a mixin applied to a superclass `S` where `M` is a reference to a
generic class with no type arguments provided, and `S` is some class (possibly
generic); and where `M` is defined with type parameters `X0, ..., Xj`.  Let `S0,
..., Sn` be the superclass constraints for `M` as defined above.  Note that the
`Xi` may appear free in the `Si`.  Let `C0, ..., Cn` be the corresponding
classes for the `Si`: that is, each `Si` is of the form `Ci<T0, ..., Tk>` for
some `k >= 0`.  Note that by assumption, the `Xi` are disjoint from any type
parameters in the enclosing scope, since we have assumed that type variables are
suitably renamed to avoid capture.

For each `Si`, find the unique `Ui` in the super-interface graph of `S` such
that the class of `Ui` is `Ci`.  Note that if there is not such a `Ui`, then
there is no instantiation of `M` that will allow its superclass constraint to be
satisfied, and if there is such a `Ui` but it is not unique, then the superclass
hierarchy is ill-formed.  In either case it is an error.

Let *SLN* be the smallest set of pairs of type variables and types `(Z0, T0),
..., (Zl, Tl)` with type variables drawn from `X0, ..., Xj` such that `{T0/Z0,
..., Tl/Zl}Si == Ui`.  That is, replacing each free type variable in the `Si`
with its corresponding type in *SLN* makes `Si` and `Ui` the same.  If no such
set exists, then it is an error.  Note that for well-formed programs, the only
free type variables in the `Ti` must by definition be drawn from the type
parameters to the enclosing class of the mixin application. Hence it follows
both that the `Ti` are well-formed types in the scope of the mixin application,
and that the the `Xi` do not occur free in the `Ti` since we have assumed that
classes are suitably renamed to avoid capture.

Let `[X0 extends B0, ..., Xj extends Bj]` be a set of type variable bounds such
that if `(Xi, Ti)` is in *SLN* then `Bi` is `Ti` and otherwise `Bi` is the
declared bound for `Xi` in the definition of `M`.

Let `[X0 -> T0', ..., Xj -> Tj']` be the default bounds for this set of type
variable bounds as defined in the "instantiate to bounds" specification.

The inferred type arguments for `M` are then `<T0', ..., Ti'>`.

It is an error if the inferred type arguments are not a valid instantiation of
`M` (that is, if they do not satisfy the bounds of `M`).

#### Discussion

For each superclass constraint, there must be a matching interface in the
super-interface hierarchy of the actual superclass.  So for each superclass
constraint of the form `I0<U0, ..., Uk>` there must be some `I0<U0', ..., Uk'>`
in the super-interface hierarchy of the actual superclass `S` (if not, there is
an error in the super class hierarchy, or in the mixin application).  Note that
the `Ui` may have free occurrences of the type variables for which we are
solving, but the `Ui'` may not.  A simple equality traversal comparing `Ui` and
`Ui'` will find all of the type variables which must be equated in order to make
the two interfaces equal.  Once a type variable is solved via such a traversal,
subsequent occurrences must be constrained to an equal type, otherwise there is
no solution.  Type variables which do not appear in any of the superclass
constraints are not constrained by the mixin application.  Some or all of the
type variables may be unconstrained in this manner.  We choose a solution for
these type variables using the instantiate to bounds algorithm.  We construct a
synthetic set of bounds using the chosen constraints for the constrained
variables, and use instantiate to bounds to produce the remaining results.
Since instantiate to bounds may produce a super-bounded type, we must check that
the result satisfies the bounds (or else define a version of instantiate to
bounds which issues an error rather than approximates).

Note that we do not take into account information from later mixins when solving
the constraints: nor from implemented interfaces.  The approach specified here
may therefore fail to find valid instantiations.  We may consider relaxing this
in the future.  Note however that fully using information from other positions
will result in equality constraint queries in which type variables being solved
for appear on both sides of the query, hence leading to a full unification
problem.

The approach specified here is a simplification of the subtype matching
algorithm used in expression level type inference.  In the case that there is no
solution to the declarative specification above, subtype matching may still find
a solution which does not satisfy the property that no generic interface may
occur twice in the class hierarchy with different type arguments.  A valid
implementation of the approach specified here should be to run the subtype
matching algorithm, and then to subsequently check that no generic interface has
been introduced at incompatible type.

## Tests and illustrative examples.

Some examples illustrating key points.

### Inference proceeds outward

```
class I<X> {}

class M0<T> extends I<T> {}

class M1<T> extends I<T> {}

// M1 is inferred as M1<int>
class A extends M0<int> with M1 {}
```

```
class I<X> {}

class M0<T> extends I<T> {}

class M1<T> extends I<T> {}

class M2<T> extends I<T> {}

// M1 is inferred as M1<int>
// M2 is inferred as M1<int>
class A extends M0<int> with M1, M2 {}
```

```
class I<X> {}

class M0<T> extends Object implements I<T> {}

class M1<T> extends I<T> {}

// M0 is inferred as M0<dynamic>
// Error since class hierarchy is inconsistent
class A extends Object with M0, M1<int> {}
```

```
class I<X> {}

class M0<T> extends Object implements I<T> {}

class M1<T> extends I<T> {}

// M0 is inferred as M0<dynamic> (unconstrained)
// M1 is inferred as M1<dynamic> (constrained by inferred argument to M0)
// Error since class hierarchy is inconsistent
class A extends Object with M0, M1 implements I<int> {}
```

### Multiple superclass constraints
```
class I<X> {}

class J<X> {}

class M0<X, Y> extends I<X> with J<Y> {}

class M1 implements I<int> {}
class M2 extends M1 implements J<double> {}

// M0 is inferred as M0<int, double>
class A extends M2 with M0 {}
```

### Instantiate to bounds
```
class I<X> {}

class M0<X, Y extends String> extends I<X> {}

class M1 implements I<int> {}

// M0 is inferred as M0<int, String>
class A extends M1 with M0 {}
```

```
class I<X> {}

class M0<X, Y extends X> extends I<X> {}

class M1 implements I<int> {}

// M0 is inferred as M0<int, int>
class A extends M1 with M0 {}
```

```
class I<X> {}

class M0<X, Y extends Comparable<Y>> extends I<X> {}

class M1 implements I<int> {}

// M0 is inferred as M0<int, Comparable<dynamic>>
// Error since super-bounded type not allowed
class A extends M1 with M0 {}
```

### Non-trivial constraints

```
class I<X> {}

class M0<T> extends I<List<T>> {}

class M1<T> extends I<List<T>> {}

class M2<T> extends M1<Map<T, T>> {}

// M0 is inferred as M0<Map<int, int>>
class A extends M2<int> with M0 {}
```

### Unification
These examples are not inferred given the strategy in this proposal, and suggest
some tricky cases to consider if we consider a broader approach.


```
class I<X, Y> {}

class M0<T> implements I<T, int> {}

class M1<T> implements I<String, T> {}

// M0 inferred as M0<String>
// M1 inferred as M1<int>
class A extends Object with M0, M1 {}
```


```
class I<X, Y> {}

class M0<T> implements I<T, List<T>> {}

class M1<T> implements I<List<T>, T> {}

// No solution, even with unification, since solution
// requires that I<List<U0>, U0> == I<U1, List<U1>>
// for some U0, U1, and hence that:
// U0 = List<U1>
// U1 = List<U0>
// which has no finite solution
class A extends Object with M0, M1 {}
```