Generic blanket impls (details 5)

Pull request

Table of contents

Problem

There are cases where an impl definition should apply to more than a single type and interface combination. The solution is to parameterize the impl definition, so it applies to a family of types, interfaces, or both. This includes:

  • Declaring an impl for a parameterized type, which may be external or declared out-of-line.
  • “Conditional conformance” where a parameterized type implements some interface if the parameter to the type satisfies some criteria, like implementing the same interface.
  • “Blanket” impls where an interface is implemented for all types that implement another interface, or some other criteria beyond being a specific type.
  • “Wildcard” impls where a family of interfaces are implemented for single type.

In addition to a syntax for defining parameterized impls, we need rules for coherence:

  • Orphan rules ensure that an impl is imported in any code that might use it.
  • Overlap rules pick a specific impl when more than one impl declaration matches a specific query about whether a type implements an interface.

Background

Rust supports parameterized impls, but has not stabilized the specialization feature that resolves multiple impls applying.

Proposal

This is a proposal to add a “parameterized impls” section to the generics design details.

Rationale based on Carbon’s goals

Much of this rationale for generics was captured in the Generics goals proposal. This proposal is particularly concerned with achieving the goal of making generics coherent.

Alternatives considered

Different syntax

This conditional interface implementation syntax was decided in issue #575, and clarified in a Discord discussion in #syntax. A large part of what was decided in that issue is the syntax used for non-parameterized impls, and incorporated into the Carbon generics design in proposal #553: Generics details part 1.

Inconsistent syntax

Our primary concern with the syntax for parameterized impls was that it be consistent with non-parameterized impls, and consistent between lexically inline and out-of-line definitions. Consistency was the basis for rejecting a number of conditional conformance options:

  • The extend syntax inline in a class definition to establish a more specific Self type for conditional conformance choice was eliminated along with the extend syntax for external impls.

  • Consistency excluded using deduced arguments in square brackets after the impl keyword, and an if or where clause to add constraints:

    class FixedArray(T:! Type, N:! Int) {
  impl as [U:! Printable] Printable if T == U {
    // Here `T` and `U` have the same value and so you can freely
    // cast between them. The difference is that you can call the
    // `Print` method on values of type `U`.
  }
}

class Pair(T:! Type, U:! Type) {
  impl as Foo(T) if T == U {
    // Can cast between `Pair(T, U)` and `Pair(T, T)` since `T == U`.
  }
}

    This was too different from how those same impls would be declared out-of-line.

  • Another approach that was too different between inline and out-of-line, is to use pattern matching instead of boolean conditions. This might look like:

    class FixedArray(T:! Type, N:! Int) {
  @if let P:! Printable = T {
    impl as Printable { ... }
  }
}

interface Foo(T:! Type) { ... }
class Pair(T:! Type, U:! Type) {
  @if let Pair(T, T) = Self {
    impl as Foo(T) { ... }
  }
}

Members defined out-of-line

We rejected options that declared unqualified member names outside of the scope defining the class. This would have allowed us to consistently use an out-of-line syntax, but starting with something other than external when it affected the names in the class.

Context sensitivity

We rejected options for conditional conformance where the meaning of names declared in the class scope would have a more specific meaning in an inner scope. This would be much like how a language with flow-sensitive typing might affect the types in an inner scope as part of control flow. For example, a where clause on an impl declaration might add constraints to a class parameter only inside the scope of the impl it was applied to:

class FixedArray(T:! Type, N:! Int) {
  impl as Printable where T is Printable {
    // Inside this scope, `T` has type `Printable` instead of `Type`.
  }
}

These options were rejected based on the low-context-sensitivity principle.

Orphan rule could consider interface requirements in blanket impls

The orphan rule states that a rule like

impl [T:! Interface1] T as Interface2 { ... }

can only live in the library that defines Interface2, not the library that defines Interface1. To see that the alternative is not coherent, consider this example where we have three libraries, with one a common library imported by the other two:

  • Library Common

    interface ICommon { ... }
class S { ... }

  • Library A:

    import Common
interface IA { ... }
// Local interface only used as a constraint
impl [T:! IA] T as ICommon { ... }
// Fine: implementation of a local interface
impl S as IA { ... }

  • Library B:

    import Common
interface IB { ... }
// Local interface only used as a constraint
impl [T:! IB] T as ICommon { ... }
// Fine: implementation of a local interface
impl S as IB { ... }

Inside another library that imports the Common library:

  • Does S implement ICommon? If you just import ICommon, no implementations are visible
  • Does the answer change if you import libraries A or B?
  • Which implementation of ICommon should S use if you import both?

We avoid these problems by requiring the use of a local type or interface outside of constraints.

Child trumps parent rule

Rust has considered a “child trumps parent” rule. This rule would say that a library Child importing library Parent is enough to prioritize impl definitions in Child over Parent when they would otherwise overlap without one matching a strict subset of the other. The goal would be to resolve overlaps in a way that is both easy to understand and more often matches what implementations users actually want prioritized.

One caveat of this rule is that a simple interpretation is not transitive. If we define three impls in three different libraries, with these type structures:

  • impl (A, ?, ?) as I
  • impl (?, B, ?) as I
  • impl (?, ?, C) as I

then the type structure rule would prioritize A over B over C. If the library with C had a dependency on the one with A, though, then C would have priority over A, and we would not be able to decide which impl to use for (A, B, C).

The fix is to change the rule to be “Child trumps parent on their intersection”. With that rule, it would be as if there was another implementation defined on the intersection of (A, ?, ?) and (?, ?, C), that is it would match (A, ?, C), that had the highest priority and delegated to the (?, ?, C) impl for the definition of the body.

Without some child trumps parent rule: If I define a new type, then all impl lookup for interfaces implemented by that type as Self will consider impl from my library first, at the time I define it until some other library adds an impl of that type as Self. However, adding the “child trumps parent on their intersection” rule removes this property.

This is something we would consider in the future once we have more experience. Note that this rule has not yet been implemented in Rust, so we don’t know how it works out in practice.

Impls could limit specialization

This would allow greater reasoning in generic functions, requiring less specification. For example, there may be a blanket implementation of PartiallyOrdered provided for types that implement Ordered. If that blanket implementation could not be specialized, a generic function could rely on the implementations of the two interfaces being consistent with each other.

This feature has been left for a future proposal. Note this feature needs to be limited to those cases where the implementation that limits specialization will be guaranteed to be a dependency of all implementations that are prioritized as more specific.

Libraries for orphan impls

The orphan rule means that there may be no library that can define an impl with a particular type structure. Rust has encountered this problem already, see Rust RFC #1856: “Orphan rules are stricter than we would like”. Carbon does not currently address this problem, but we would consider future changes that do as long as coherence was maintained. For example, we’d consider a mechanism that allowed libraries to be defined that must be imported, either implicitly or explicitly, depending on whether specific other libraries are imported or linked into the project.

Different traversal order for overlap rule

The overlap rule uses a depth-first traversal of the type tree to identify the first difference between two different type structures. We could also do another order, such as breadth-first, but this order is both simple and reflects some experience from the Rust community that the Self type is particularly important to prioritize.

Intersection rule in addition to prioritization

Another approach for selecting between impls with the same type structure is to require that there is an impl matching the intersection of any two impls with the same type structure, and then prioritize by containment. This approach is being considered for Rust, see Baby Steps: “Intersection Impls” and Aaron Turon: “Specialization, coherence, and API evolution. Instead of requiring that impls with the same type structure are always in the same prioritization block, that requirement could be only when the intersection isn’t defined. The advantage of the prioritization block is that it can express everything that intersection impls can express, and generally can do so without having to write an exponential number of impl declarations. Prioritization blocks do require you to write all the impls together in a block, though, so we might want to support the option of allowing developers to explicitly write out intersections instead. This might be convenient in cases where the intersection is defined anyway, such as when there is already strict subset relationship between the impls.

Name lookup into conditional impls

We considered the possibility that name lookup would fail to find the members of that impl when a conditional impl’s condition does not apply. This would allow

class X(T:! Type) {
  impl X(i32) as Foo {
    fn F[me: Self]();
  }
  impl X(i64) as Bar {
    fn F[me: Self](n: i64);
  }
}

where X(T).F means different things for different T, which could be an unpleasant surprise. This seemed against the Carbon philosophy of making the code behave consistently and predictably, and didn’t have a motivating use case.

Automatic implicit conversions

We considered adding two features to support operator overloading use cases, where the language would select the interface parameter using the type of the second argument without considering implicit conversions. The intent of these features was to, for example, make it convenient to support addition with anything that implicitly converted to i32 by implementing addition with just i32.

One feature was to support implementing an interface using a function with a different signature, as long as the compiler could automatically generate a wrapper that bridged the two signatures using implicit conversions. This raised concerns about accidentally implementing interfaces with functions that had the wrong signature, evolution problems when new overloads were introduced, and surprises and confusing errors from a single function considered to have two different signatures.

The other feature was to allow a wildcard implementation as long as it could be implemented using functions that did not vary with the wildcard parameter, by implicitly converting to a common type. This introduced concerns about what to do with other members of the interface, particularly those with defaults. Perhaps we would allow functions as long as the interface parameters could be deduced from the types of the arguments? Perhaps we would require explicit qualification to call functions where the interface parameter couldn’t be deduced? In particular we were worried about evolution, and allowing users to add functions to an interface as long as they had defaults.

These problems were discussed in 2021-12-08 open discussion. We concluded that we will later find other mechanisms to support this use case.