Scoped Class Extensions

In response to #40, this is a proposal for a mechanism, _scoped class extensions_, that allows class type hierarchies to be extended with new instance methods. This proposal is intended to be compatible with the scoped static extension method mechanism (#41), in the sense that those two proposals can be combined into a single one, or they can be adopted one after the other. Scoped static extension methods can do things that are not possible with scoped class extensions, and vice versa, so it makes sense to have both.

[Edit Jan 22 2019: Generalized this mechanism to apply to all sets of target classes whose subtyping is a tree, rather than only a set of targets which are related by the _subclass_ relation. Changed `eval` to be a method, based on bitter complaints about using the name `eval` for a getter. But they are right, that is a bad name for a getter. ;-]

[Edit Mar 26 2019: Adjusted the description of generic extensions, the constraints previously mentioned are more strict than they have to be.]

[Edit Apr 1 2019: Clarified that an implements relationship must hold from case to case.]

## Motivation

**Like #41**, this is a proposal for a mechanism that allows developers to add new methods to existing receivers without editing the corresponding existing declarations.

The special **advantage of this proposal** is the ability to enhance an existing class type hierarchy with new methods that are subject to object-oriented dispatch. In other words, whereas scoped static extension methods are similar to static methods, this proposal enables something which is similar to adding instance methods to the target class type hierarchy, without editing it.

The [**visitor** design pattern](https://en.wikipedia.org/wiki/Visitor_pattern) is a well-known software engineering idiom for which a main selling point is that it allows developers to, sort of, add a new instance method to an existing class hierarchy. This is considerably less convenient than a real instance method, however:

- With a visitor, the target hierarchy (that is, the classes whose instances we wish to visit) must implement special support for double dispatch. That is, if we wish to visit instances of a class `C` with a visitor of type `Visitor`, then the class `C` must declare an `accept(Visitor v)` method that invokes the method in the visitor that corresponds to `C`.
- With a visitor, extra ceremony must be applied in order to specify a behavior which is similar to object-oriented overriding (e.g., every visit method must have a default implementation that makes an emulated "superinvocation", and care must be taken for repeated overrides).
- With a visitor, it is necessary for clients to use a different syntax in order to "invoke the added method": (they typically need to do `myVisitor.accept(myReceiver)`), and with a given visitor type, it is impossible to directly specify different signatures, so the approach taken could often be to make the visitor generic and use that to specify the return type, and then to store arguments to the invocation in the visitor itself, etc.
- Finally, it is necessary to _edit_ the visitor itself in order to broaden the support such that the visitor can be used on any new kinds of objects that weren't taken into account (and maybe weren't even written) when the visitor was written.

In other words, we already have a design pattern that is well-known for being able to "add a new method" to a given class type hierarchy, but it is quite inconvenient to use.

**This proposal** offers a more smooth mechanism: The target hierarchy need not be edited at all in order to allow for adding an extension instance method (so there's nothing like an `accept` method); invocation of the extension instance methods (each one corresponding to a visitor) uses the same syntax as invocation of ordinary instance methods; extension instance methods can receive arguments and return results of any expressible type, using the familiar syntax and semantics of instance member declarations; and inheritance and overriding work in the same way for extension instance methods as it does for ordinary instance methods.

We will discuss the non-generic case first, but scoped class extensions allow for extending generic classes and capturing the actual value of the type arguments of the receiver.

## Example

Here is an example of a target class type hierarchy that we will later extend with some extension instance methods:

```dart
// This is 'expr.dart'.

abstract class Expr {}

class Literal extends Expr {
final int value;
Literal(this.value);
toString() => "$value";
}

class Sum implements Expr {
final Expr leftOperand, rightOperand;
Sum(this.leftOperand, this.rightOperand);
toString() => "($leftOperand + $rightOperand)";
}
```

This is a Dart version of the standard example for the topic area known as [_the expression problem_](https://en.wikipedia.org/wiki/Expression_problem), using `toString()` to express a pretty-printing method just because that's a rather natural choice for Dart.

Now we want to extend that class hierarchy with an evaluation method, `eval()`. This is a method, but the treatment of getters, operators, etc. follows naturally from that. Here is such an example extension:

```dart
// This is 'eval-extension.dart'.

import 'expr.dart';

extension Eval on Expr {
int eval() {
if (this is EvalThirdParty) return this.evalThirdParty();
throw "Unsupported subtype";
}
}
on Literal {
eval() => value;
}
on Sum {
eval() => leftOperand.eval() + rightOperand.eval();
}

abstract class EvalThirdParty implements Expr {
int evalThirdParty();
}
```

In general, a given class type hierarchy (like {`Expr`, `Literal`, `Sum`}) can be extended by a sequence of extension blocks, so the declaration of the extension above is _one_ declaration. This ensures that the static class extension mechanism can be subject to separate compilation. We use the phrase 'an extension' to refer to the entity corresponding to each of these syntactic extension blocks, just like we'd use the phrase 'a class' to refer to the entity declared by a class declaration.

The class `EvalThirdParty` is not necessary, but it is used to illustrate how we can add support for "third party" classes that are not known by the developer who writes the extension. It is possible to import a scoped class extension that covers a set of "standard" classes, and then you can write your own additional ("third party") classes implementing or extending some of the standard classes, and you can write them in such a way that they support the extension. This would not be possible with a visitor: You would need to edit the visitor in order to make it visit a larger set of types.

In order to run an extension method, an invocation of the form `e.m(arguments)` is checked and compiled as follows:

- The static type of `e` does not have a member `m` (statically known regular instance members always win over extension instance members).
- A scoped class extension `Ext` targeting the static type of `e` is in scope.
- `Ext` declares a member `m`; it is a compile-time error if the `arguments` passed to `m` do not conform to the declaration `Ext.m`, and otherwise we have now decided that this is an invocation of `m` on the extension `Ext`.
- At run time, `e` is evaluated, let `o` be the resulting value, then the dynamic type of `o` is used to look up the corresponding extension object `oExt`, and the invocation is performed as `oExt.m(o, arguments)`.

The notion of _corresponding extension objects_ is crucial; it is explained below in a separate section.

For now, we just consider the simple case illustrated by the `Eval` example above. So here is a snippet of code where that extension is being used:

```dart
import 'expr.dart';
import 'eval-extension.dart';

// The `Eval` extension doesn't know about `Subtraction`, but we can still
// add a new receiver type to that extension: We just need to implement
// `EvalThirdParty`, which means that we need to implement an `evalThirdParty()`
// method.
class Subtraction implements EvalThirdParty {
final Expr leftOperand, rightOperand;
Subtraction(this.leftOperand, this.rightOperand);
prettyPrint() => "($leftOperand - $rightOperand)";
evalThirdParty() => leftOperand.eval() - rightOperand.eval();
}

main() {
Expr e = Sum(Literal(3), Literal(4));
print(e); // Prints '(3 + 4)'.
print(e.eval()); // Prints '7'.
Expr e2 = Subtraction(Literal(8), e);
print(e2); // Prints '(8 - (3 + 4))'.
print(e2.eval()); // Prints '1'.
}
```

This illustrates that we can add a new class to the set of target classes of the extension `Eval` (here: `Subtraction`), even though that new class is not in scope at the declaration of the extension, so the developer who wrote `Eval` had no way of knowing about that new class. We can mix and match the "standard" class instances with the "added" class instances, because they are all of type `Expr`, and `evalThirdParty()` will transparently be invoked via the extension method `eval` when `Eval` does not have an implementation.

With that example in place, here's a "desugared" version of the code, which shows how it works. Note that the extension and call sites get desugared, but `expr.dart` remains unchanged (which is true in general, because we do not change a class hierarchy in any way when we extend it). Some comments were added to the desugared code, in order to explain what is going on.

```dart
// Desugared version of 'eval-extension.dart'.

import 'expr.dart';

// ----------------------------------------------------------------------
// Code corresponding to the scoped class extension `Eval`.

// For each block in the scoped extension declaration, implicitly generate
// a class which will be used to hold the desugared extension methods.

class Eval_Expr {
// Generated code to support the mechanism.
const Eval_Expr();
static Eval_Expr extensionObject(Expr e) {
// Handle types that are addressed directly.
var result = eval_extensionObject[e];
if (result != null) return result;
// Other types are resolved according to the
// declaration order: Last match wins.
if (e is Sum) return eval_Sum;
if (e is Literal) return eval_Literal;
return eval_Expr;
}

// Transformed user-code.
int eval(covariant Expr _this) {
if (_this is EvalThirdParty) return _this.evalThirdParty();
throw "Unsupported subtype";
}
}

class Eval_Literal extends Eval_Expr {
const Eval_Literal();
static Eval_Literal extensionObject(Literal e) =>
Eval_Expr.extensionObject(e);
eval(Literal _this) => _this.value;
}

class Eval_Sum extends Eval_Expr {
const Eval_Sum();
static Eval_Sum extensionObject(Sum e) => Eval_Expr.extensionObject(e);
eval(Sum _this) =>
Eval_Expr.extensionObject(_this.leftOperand).eval(_this.leftOperand) +
Eval_Expr.extensionObject(_this.rightOperand).eval(_this.rightOperand);
}

// Implicitly generate a dispatch mapping from types to extension objects:
// For every concrete class `G` known at the declaration of the extension which
// is a subtype of the first target (here: `Expr`) add a mapping from `G`
// to the corresponding extension object to this map.
const Map eval_extensionObject = {
Literal: eval_Literal,
Sum: eval_Sum,
};

// Implicitly generate constant extension objects.
const eval_Expr = const Eval_Expr();
const eval_Literal = const Eval_Literal();
const eval_Sum = const Eval_Sum();

// No desugaring needed for `EvalThirdParty`.
abstract class EvalThirdParty implements Expr {
int evalThirdParty();
}
```

One thing to note is that there is a static method `extensionObject` in each class which is the desugaring of an an extension block in the original scoped class extension declaration. These static methods all do the same, but the ones that are associated with extensions targeting a subclass have a more specific argument type and return type. This is needed in order to allow the call site on an instance of, say, `Literal` to statically know that all extension methods declared for or inherited by the `Literal` target are available, and not just the ones which are declared for the target `Expr`. The associated downcasts are safe (so a compiler can omit them), because of the design of the mapping `eval_extensionObject`.

The mapping `eval_extensionObject` is a "dispatch map" which maps every receiver type to the corresponding extension object. It is described in the next section how to create it.

The main implementation of the static methods `extensionObject` is the one in the first extension block (here: the one for `Expr`), and it uses the mapping `eval_extensionObject` to dispatch directly to the extension object for each known target class.

If the given receiver `o` is not a direct instance of any of these classes, we check, in reverse order, whether `o` is an instance of each target type (using `is`, that is, allowing for proper subtypes). This means that if a third party class implements `Sum` or `Literal`, an instance thereof just get the implementation which is written for `Sum` respectively `Literal` (and that would presumably work, because said class actually promises to work like a `Sum` respectively a `Literal`); in the ambiguous case where the third party class implements _both_ `Sum` and `Literal`, the developer who wrote the extension made the choice to put `Sum` after `Literal`, and this is used to disambiguate: `Sum` wins because it is "more specific".

Finally, if the dynamic receiver type does not implement anything more specific than `Expr`, we may choose to say that there is no meaningful implementation of `eval()` for such an object; but in this case we can actually push the task back onto the receiver by means of the `EvalThirdParty` supertype: Whoever implements `EvalThirdParty` has made a commitment to support this extension by implementing some instance methods. This fits with the situation where the receiver class `C` was actually written by a "third party", and the writer of the extension has no idea that `C` exists.

Here is the desugared version of the main library:

```dart
import 'expr.dart';
import 'eval-extension.dart';

// Only extension method invocations need desugaring here.
class Subtraction implements EvalThirdParty {
final Expr leftOperand, rightOperand;
Subtraction(this.leftOperand, this.rightOperand);
toString() => "($leftOperand - $rightOperand)";
// Being lazy, we evaluate `this.leftOperand` twice; real desugaring
// will use local variables to ensure that such expressions are only
// evaluated once; same for `rightOperand`.
get evalThirdParty =>
Eval_Expr.extensionObject(this.leftOperand).eval(this.leftOperand) -
Eval_Expr.extensionObject(this.rightOperand).eval(this.rightOperand);
}

main() {
Expr e = Sum(Literal(3), Literal(4));
print(e);
print(Eval_Expr.extensionObject(e).eval(e));
Expr e2 = Subtraction(Literal(8), e);
print(e2);
print(Eval_Expr.extensionObject(e2).eval(e2));
}
```

This example illustrates the core ideas: A target class type hierarchy is supplemented by an extension class hierarchy, and extension instance method invocation proceeds in two steps: (1) compute the receiver `o` and find the corresponding extension object `oExt`; (2) invoke the extension method as `oExt.m(o, ...)`.

## Corresponding Extension Objects

A scoped class extension can be declared for a set of types whose subtype relation is a tree, and it introduces an ordering on this type hierarchy which is not a contradiction of the subtype relationship. This means a few things:

It is a compile-time error to declare a scoped class extension with a target which is `dynamic` or `void`. It is a compile-time error to declare a scoped class extension whose initial target is a type `T`, if a subsequent target `D` is not a subtype of `T`. It is a compile-time error for a scoped class extension to have two targets `D1` and `D2` in that order (but not necessarily consecutively) if `D1 <: D2`.

Finally, assume that a scoped class extension with initial target class `C` and subsequent targets `D1` and `D2` and `D3` (where `D1` can be `C`, but `D1`, `D2` and `D3` are distinct) is such that `D3 <: D1` and `D3 <: D1`; it is then a compile-time error if `D2 <: D1` does not hold. (*This ensures that the subtype relationships among all targets is a tree.*)

In other words, a scoped class extension must have a list of targets which is a topologically sorted enumeration of a subset of the subtypes of the first target, and the set of target types must be a tree according to the subtype order.

The point is that this makes it easy to see that we can create a _shadow hierarchy_ of extension classes corresponding to the given hierarchy of target classes; this would not be so straightforward if we had allowed the subtyping structure on the targets to be a general directed acyclic graph, rather than a tree.

So, during desugaring we will create a class for each extension target, and the inheritance structure among the extension classes is a "coarsened" version of the inheritance structure among the target classes.

The approach taken is: For each extension class `Ce` with target `Ct`, let `S` be the minimal proper supertype of `Ce` among all targets of the extension, and let `Ce2` be the corresponding extension class (*`S` is guaranteed to exist because the target types is a tree.*). Then `Ce2` is the superclass of `Ce`.

Moreover, each extension class after the first one `implements` the one that is associated with the previous case, except when that previous case is already its direct superclass.

*This approach guarantees that whenever a target has static type `T` and dynamically matches a target `S`, the corresponding extension types are such that when `Ce` corresponds to `T` and `Ce2` corresponds to `S`, it is guaranteed that `Ce2 <: Ce`. This ensures that if static analysis predicts that a receiver can have a method `m` invoked on an instance of `Ce`, such an invocation will also be possible on an instance of `Ce2`, and the usual override rules ensure that the invocation has the same soundness guarantees as we have for ordinary instance method invocations. For instance, parameter passing is guaranteed to be statically safe, except when the invoked method has one or more parameters which are covariant.*

## On Static Type Safety

Scoped class extensions allow for adding a new instance method to some or all classes in a class hierarchy (that is, a set of classes where each pair has a subclass relationship to each other, direct or indirect). It does _not_ require the target classes to be modified in any way in order to allow this.

Consequently, it needs to have _some_ treatment of the case where the dynamic type of the receiver is a subtype of the initial target class (so in the example it is a subtype of `Expr`), but not a subtype of any of the types (`Literal` and `Sum`) for which there is an implementation.

We could make this a compile-time error (so if you only know that `e` is an `Expr`, you cannot call its `eval`, you have to know statically that it's a `Literal` or a `Sum`). This would allow the initial target (and in desugared code: the class `Eval_Expr`) to be abstract, and the developer could declare `eval` as abstract. This would be safe, but quite inconvenient.

So we have chosen to say that no extension blocks are abstract, and every extension block hence needs to implement every method that it supports. In some cases that's possible; In fact, it isn't worse than it would be to write a static scoped extension method, because such a method always relies on the statically known receiver type.

However, just like `eval` on a receiver which is an `Expr` and not a `Literal` nor a `Sum`, there will be cases where it is just not possible to come up with a reasonable implementation.

The crucial point here is that we are actually defining a method, with implementations, for _all subtypes_ of the initial target (here: `Expr`), not just for a subclass hierarchy, and there is no way we can get this kind of concept without a certain trade-off. The trade-off is that it may be necessary for an extension method like `eval` in the initial extension block of `Eval` to throw at some point: We just don't know what to do for this particular receiver. The other side of this trade-off is that it is a more powerful concept than an ordinary instance method to cover all subtypes.

However, the use of `EvalThirdParty` in the example shows that it is actually quite easy to come up with a programming idiom that allows all those third parties to write their classes in such a way that they will be supported by a given extension like `Eval`: Just implement `EvalThirdParty`.

## Generics

When one or more of the target classes is generic, a scoped class extension can use a type pattern (#170) to declare type parameters for the extension, which provides access to the actual type arguments of the run-time type of the receiver, in the body of the extension.

These type patterns can be _irrefutable_, which means that they are guaranteed to match for any given instance of the underlying type.

*For instance, `List` is an irrefutable type pattern, because _every_ instance of type `List` for any `T` will match that pattern. Similarly, `C` is an irrefutable type pattern in the case where `C` declares a type parameter with bound `num`.

```dart
// Target class declaration.
class A> {...}

// Examples of irrefutable type patterns for `A`.
A>
A // Renaming and omission of bounds is OK.
A // Using a raw type means "I don't care about the actual type arguments".
```

The first pattern may be the most useful one, because it allows the extension to get access to the dynamic value of all the type arguments of the target, and it equips each of them with the best possible bound. However, the last one may yield better performance at run time (because there is no need to perform matching and binding any type parameters to a value, it's just a plain subtype test).

However, we may also use refutable type patterns (that is, patterns which are not irrefutable). In this case we require that the greatest closure of the type patterns (that is, the transformation which erases `var X` to `Object` and `var X extends B` to `B`) form a tree with respect to the subtype relation.

*Here is an example:*

```dart
// Greatest closure is a topologically sorted traversal of a subtype tree: OK.
extension E1 on List {...}
on List {...}
on List {...}
```

It is worth noting that is allowed for multiple cases to match the same type, based on the type pattern. So there is nothing wrong with having a case for `List` which is applied if we actually have a `List`, and also a case for `List` which will be applied for an instance of `List`, `List`, or `List`. There is no ambiguity for the `List` because the later case is considered more specific, so the case `List` gets to work with the instance of `List`.

At run time, matching proceeds from the most specific end (the one at the end, textually), and upwards through less and less specific type patterns, until there is one that matches. For instance, a `List` gets dispatched to the first extension (the one with `List`), because the others do not match.

It does matter whether a scoped class extension uses irrefutable type patterns or not, because the ones that have one or more refutable type patterns are likely to require a compilation strategy which is more costly (in terms of run-time performance). So we'd expect irrefutably type patterns to be the most common approach, and refutable ones are used when we want something more fancy, and are willing to pay for it.

In particular, every scoped class extension which has no type parameters at all will have irrefutable type patterns.

As an example of a case that admits optimal performance, any scoped class extension which has irrefutable type patterns for a tree-shaped subset of a subclass hierarchy allows for a direct mapping from each receiver type to the corresponding extension object. So, whenever the receiver is an instance of one of the classes in that hierarchy (that is, the ones for which we have a case, plus the intermediate ones that we have no case for, but which are in scope at the declaration of the extension), we can directly map from the receiver type to the extension object, like a vtable. Let's say that the classes in this "extension vtable" are called _well-known_ classes. For classes that are not well-known, e.g., a third-party class that `implements` a well-known class, we still have to perform a linear search in order to find the most specific case of the extension that matches, but we are likely to get the fast (vtable-ish) dispatch in the majority of cases.

Note that it is important that we can determine at compile-time that a given type pattern will match the actual receiver:

```dart
extension E on List { Object foo() {...}}
on List { num foo() {...}}

main() {
List xs = [1];
num n = xs.foo(); // We get the type from the second case of the extension.
}
```

This is a sound typing because a receiver of static type `List` is guaranteed to match the type pattern `List` at run time.

Here is another example:

```dart
abstract class Expr {}

class Literal extends Expr {
final X value;
Literal(this.value);
toString() => "$value";
}

class Sum extends Expr {
final Expr leftOperand, rightOperand;
Sum(this.leftOperand, this.rightOperand);
toString() => "($leftOperand + $rightOperand)";
}

// Extension.

extension Eval on Expr {
int eval() { ... } // Nothing new about this.
bool get isEven {
X x = eval();
if (x is int) return x.isEven;
return false;
}
}
on Literal {
eval() => value;
int intValue() => value is int ? value : value.round();
}
on Sum {
eval() => leftOperand.eval() + rightOperand.eval();
List get operands => [leftOperand.eval(), rightOperand.eval()];
}
```

The semantics of this kind of extension could be specified in terms of generic extension objects, or it could use non-generic extension objects.

With generic extension objects, an instance of `Sum` would have an instance of `Eval_Sum` as its corresponding extension object, and an instance of `Literal` would have an instance of `Eval_Literal`. This means that it would be necessary for the implementation to deliver these instances of generic classes upon dispatch on an instance of a target class (because it is not known statically which actual type arguments we will have ... except of course when it can only be `num`, `int`, `double`, and `Null`, but it _is_ true in general ;-). With compiler support, it may be an operation with rather good performance to create these instances (of `Eval_...` for some `T`), because they have no state, and the type argument list may be shared.

With non-generic extension methods, we would pass all the type arguments that are made accessible to the body of the extension as (additional) type arguments to the extension method itself. This approach is suitable for static extension methods because it allows us to avoid allocating "an extension object" at all, but with a scoped class extension the extension object is crucial, and it may or may not be a good implementation strategy to make it generic.

The reason why we can use both of these strategies is that there is no state in an extension object, and user-written code can never get explicit access to an extension object. So there is no way for user-written code to detect whether any given mechanism that offers access to these type variables is based on method type parameters or on class type parameters.

Start with this proposal and its linked issues #40 and #41; the examples use expr.dart and eval-extension.dart to define the intended semantics. Compare the scoped class-extension rules with the scoped static-extension mechanism and the existing Dart language specification. Done means an agreed design and corresponding specification changes, but this issue does not name implementation files or tests.

Written by the indexing model from the issue text.