proposal: Go 2: allow covariance of interface method parameters & return values

[kent-h]

Proposal / Rational

One of the uses for interfaces, is to provide a reduced-access abstraction, ensuring that a library is used correctly by a caller.

It is not uncommon to have similar interfaces for different classes of users; or, more generally, to have a single implementation for multiple interfaces.

This allows:

• Information hiding
• Interface simplification (from the caller's point of view)

It would be useful to implement a method once, and allow it to implement multiple similar interfaces.

Simple Example

Interface (for this example, the 'subtype')

type ExampleInterface interface {
  // return type covariance
  Clone() ExampleInterface
  // parameter type covariance
  SetParent(*ExampleStruct)
}

Struct (for this example, the 'supertype')

type ExampleStruct struct {
  ...
}

Implementation

// return type covariance (this implementation's return type is a supertype of the interface method's return type)
func (s *ExampleStruct) Clone() *ExampleStruct {
  ... 
}
// parameter type covariance (this implementation's parameter type is a subtype of the interface method's parameter type)
func (s *ExampleStruct) SetParent(newParent ExampleInterface){
  ...
}

In this example, a struct and an interface are used as the supertype and subtype, but it should be equivalently valid for both the supertype and subtype to be interfaces.

Advanced Example

See Covariance of Interface Method Parameters & Return Values - Advanced Example

Implementation Details

• At compile-time, it must be determined which interfaces are sub-interface of other interfaces. (or more precisely, which interfaces are not super-interfaces of other interfaces)
  
  This is non-trivial. As go's syntax does not specify the subtype/supertype hierarchy, loops are possible.
  
  (i.e. - A implements B if and only if C implements D if and only if A implements B...)

• Syntactic sugar:
  
  Allow super-interfaces to override embedded interfaces' methods, so long as the super-method is covariantly reducible to the embedded interface's method.
  
  As an example: Method(interfaceType)implementationStruct could override Method(implementationStruct)interfaceType, because all information required by the embedded interface is there.

Other Considerations

• This change would be GO 1 compatible.
• What about slice/array/map types?
  
  Is it possible to accept []implementationStruct/[]*implementationStruct in lieu of []interfaceType?
  
  It would be helpful to have automatic conversion of arrays/slices/maps of supertypes to arrays/slices/maps of subtypes.
  
  This appears to be related, but may or may not be possible, and is ultimately a separate issue.
  
  See proposal [WIP]: interface-slices #30391

Related

#28254
#8082
#8691

[ianlancetaylor]

See also #21651.

[ianlancetaylor]

The two items under "Implementation Details" sound like big problems that would need to be solved.

I also don't actually understand how to implement this. Code can use type assertions to convert from one interface type to another. Under this proposal, that would mean that we can convert from an interface with a method that returns one type to an interface with a method that returns a different type. The different types can have different memory representations. Where is the code that converts between those representations?

[kent-h]

@ianlancetaylor

1. No type assertions should be needed. Since every assignment is to a narrower type, type safety is already guaranteed.
2. Possible implementation: A thin layer could be added between the interface's method call and the subsequent type's method call. All type information is known at compile time, and will be either static or pass-through at runtime.
   Thus all that this thin layer needs to handle is possibly boxing/unboxing the call's request & response parameters.

Have I misunderstood something?

Edit: Unboxing is never required, since a struct type is always a supertype of an implemented interface, and due to the proposal ensuring this relationship's directionality.

[ianlancetaylor]

When I mentioned a type assertion, I meant that I can write

    var v interface{} = x
    w := v.(ExampleInterface)

In the general case, each statement can be in a different package, and the final type assertion can be in a package that does not import the implementation package. In a case like that, all type information is not known at compile time.

[kent-h]

@ianlancetaylor
But in the case of this proposal, no type assertions are ever necessary, since assignment is always done in the other direction.

var v ExampleInterface = x
var w interface{}
w = v // no assertion is required, since `ExampleInterface` implements (is a supertype of) `interface{}`

This is the core assumption that ensures type safety.

[ianlancetaylor]

You omitted the final type assertion, in a different package:

    x := w.(ExampleInterface)

[kent-h]

@ianlancetaylor
After re-reading this thread, let me take another stab at understanding your concern:

Since it is possible for a value of one type to be assigned to an interface of another type, it becomes possible for the interface's method signature to differ from the implementation's method signature (thus having different memory layouts).
In particular:

• where <value> (of struct/pointer type) is provided as a parameter to an interface's method, it is possible for <type, value> (of interface type, thus having a different memory layout) to be expected by the implementation.
• similarly, where <value> is used as a return value, it is possible for <type, value> to be expected by the caller.

Your issue pertains to how the implementation would handle the conversion between these formats.

Have I described the issue satisfactorily?

[ianlancetaylor]

Sounds about right, yes. It's important to understand that the compiler need never see all the relevant types in the same package, so there is no obvious way that the compiler can handle the situation.

[kent-h]

@ianlancetaylor
The simplest solution that comes to mind:

When calling any interface method

• box all types which have the potential to be converted to interfaces by a caller
  (implicitly convert all structs, pointers, etc. to interfaces: <value>-><type, value>)
  Note that the injected type would always be static. In addition, this type is known to the caller at compile-time.

When receiving a call from an interface method

• briefly pass execution to a small, compiler-generated function, who's job is simply to unbox interfaces as necessary, and pass the unboxed parameters on to the actual implementing function.
  (convert <type, value> -> <value> as required)
  Note that the type-safety of this unboxing can be determined at compile time, with only information about the interface and implementation (no caller information is required).

A nearly identical technique (in reverse) would be used for return values.
(callee returns values ->box-> pass results to caller ->unbox-> continue execution)

Does this address the problem, as you see it? Am I still missing something?

(I can think of several ways to optimize this, but to keep it simple for now...)

[ianlancetaylor]

In Go any type can have a method, so any type can be converted to an interface, so you would have to box all arguments when calling a method of an interface value. I guess it may be doable but it sounds like a very high cost. Boxing an argument in general requires a memory allocation. Calling methods of interface values like io.Reader is very common. I don't think the benefit of this change is worth the performance hit.

[kent-h]

The idea is to simply "include type information in the method call". Optimization was intentionally skipped, for clarity.

To avoid the overhead of unnecessary boxing/unboxing:

For the case of passing struct -> struct (or other boxable type):

1. Caller: sets an extra (known at compile time, static) type variable
2. Code fragment: Ignores type information, passes value as-is
3. Implementation: Receives struct, executes normally

For the case of passing struct(or other boxable type) -> interface:

1. Caller: Sets an extra (known at compile time, static) type variable
2. Code fragment: Boxes the type
   (note that the overhead of boxing is required in this instance to implement the struct->interface conversion.)
3. Implementation: Receives interface, executes normally

For the case of passing interface -> interface:

1. Caller: Sets an extra (static) type variable, special value indicating "interface" type
2. Code fragment: Passes value as-is
3. Implementation: Receives interface, executes normally

Note that the case of interface -> struct (or other boxable type) is not permitted by the proposal.

To summarize the total overhead: (only incurred when calling interface methods)

• Including an extra type value per non-interface variable.
• Cost of altering the parameter list. (check type variables + copy or box parameters)
  A good implementation could do this in-place, and without polluting the stack space.

That's it. No extra boxing or memory allocations required.

To address your example: Ordinary usage of io.Reader would result in the struct -> struct case, and thus would not require any boxing/allocations.

[ianlancetaylor]

What do you mean by a static type variable? How would that work if there are multiple goroutines making simultaneous calls?

I don't understand what you mean by "struct (or other boxable types)". All types are boxable. Do you just mean a non-interface type?

[kent-h]

By "static type variable" I just mean that the caller can determine the type at compile time.
So from the caller's point of view, the extra parameter is static, and thus can be more efficiently saved/stored/cached.

Yes, I just mean a non-interface type. (Structs are the example in my head.)

[ianlancetaylor]

So you are suggesting that we change the calling convention so that for every method parameter we pass an additional parameter, which is the interface type of the argument?

How do we handle result parameters?

[kent-h]

Keep in mind that this calling convention would only be required for interface method calls. (Making the assumption that there is hidden code between the interface and the implementation, that handles the translation between these two conventions.)
In addition, this calling convention is only required for parameters of non-interface type (as specified by the interface definition).

Result parameters would follow the exact same convention, but in reverse.
(Return each parameter with an additional type parameter. The caller uses this value to box iff required.)

[ianlancetaylor]

The implementation cost of passing an additional type parameter for every potentially-covariant parameter in a method call is high.

The complexity cost in the language--requiring all Go programmers to understand the use of covariance when converting a non-interface type to an interface type--is also high.

We are not going to do this.