Interface extension and final impl update

Pull request

Table of contents

• Abstract
• Problem
• Background
• Proposal
• Details
  • extend require
  • extend impl as with parameterized interfaces
  • extend impl as restrictions
  • Name conflicts
  • Final impl priority
    • Overlapping final impls
    • Using associated constants from impls in a final match_first
    • impl selection algorithm
    • An impl that can never match is an error
  • Impl names for prioritization
• Rationale
• Alternatives considered
  • Allow overlap between a non-final and final impl but only if no queries pick the non-final on the overlap
  • Forbid overlap between final impls
  • Prioritize between final impls using type structure
  • Allow mixing final and non-final impls in the same match_first block
  • No default Self in require Self impls I
  • Different rules for prioritizing between final impls
  • Different final match_first associated constant rules

Abstract

We make 5 changes:

• Allow require Self impls I in an interface or constraint scope to omit the Self, so it can be written require impls I.
• Rename extend I to extend require impls I in an interface or constraint scope.
• Define extend impl as I and extend final impl as I in an interface scope to copy the members of I and define an impl of I in terms of the extending interface.
• Allow a non-final impl to overlap a final impl as long as it isn’t subsumed by the final impl. The final impl will be given priority on the overlap.
• Allow final on a match_first block, used to declare overlapping final impls, which are required to be in a single file.

These features work together to allow a form of interface extension where:

• Types only need to impl the extending interface to also get an impl of the extended interface.
• Multiple interfaces can extend the same interface.
• An interface can extend multiple interfaces.

Problem

As part of investigating leads issue #4566, we discovered problems with using a single impl to implement multiple interfaces. Proposal #5168 (Forward impl declaration of an incomplete interface) removed that, but this changed the experience of impl of an interface that uses extend. Consider two closely coupled interfaces, such as:

interface As(T:! type) {
  fn Convert[self: Self]() -> T;
}

interface ImplicitAs(T:! type) {
  extend As(T);
}

With #5168, you can no longer just impl ImplicitAs(T) with something like

impl ThisType as ImplicitAs(ThatType) {
  fn Convert[self: Self]() -> ThatType { ... }
}

Instead, two impl definitions are needed:

impl ThisType as As(ThatType) {
  fn Convert[self: Self]() -> ThatType { ... }
}
impl ThisType as ImplicitAs(ThatType) { }

This is additional friction, which will increase with the depth of the interface hierarchy, which we would like to eliminate. The suggestion in proposal #5168, is to support the ImplicitAs use case with a final blanket impl of the As(T) interface for any type that impls ImplicitAs(T), as in:

interface As(T:! type) {
  fn Convert[self: Self]() -> T;
}

interface ImplicitAs(T:! type) {
  fn Convert[self: Self]() -> T;
}

final impl
    forall [T:! type, U:! ImplicitAs(T)]
    U as As(T) {
  fn Convert[self: Self]() -> T =
      U.(ImplicitAs(T).Convert);
}

This means that types that impl as ImplicitAs(T) automatically get an impl of As(T), and can’t impl as As(T) themselves. However, there are some concerns:

• There is significant ceremony to express this relationship.
• These semantics are closer to what we expect users will think extend in an interface will do.
• We still want a way to get the current meaning of extend in an interface scope for a few reasons:
  • This final impl requires the two interfaces to be defined in the same file, which won’t always be possible.
  • A final impl doesn’t give much flexibility for situations where you need more control, for example to reuse an impl of a specific interface.
  • Also the current extend matches the semantics of extend in a named constraint.
• Having a final impl of interface As(T) currently makes it quite difficult to have other impls of the same interface.

On this last point, under the current rules the following example would be rejected:

class C(T:! type) { ... }

interface I {}
impl forall [T:! I] C(T) as As(T) { ... }

The issue is that this impl overlaps with the final impl of interface As(T) for any type C(T) that implements ImplicitAs(T). This impl is rejected preemptively because it conflicts on the overlap, whether or not anything inhabits that overlap in the developer’s program. This avoids conflicts only being discovered by some consuming library.

Background

• Proposal #553 introduced interface extension
• Proposal #983 introduced final impl
• Proposal #2760 introduced require Self impls I in an interface or constraint scope, replacing the previous spelling of impl as I from proposal #553.
• Proposal #2868 allowed an impl to overlap a final impl as long as agreed on the overlap.

Proposal

First, to make require Self impls I usage more consistent with impl Self as I (and since we will be using this more after this proposal), we allow the Self to be omitted. So:

• require Self impls I ✅ allowed, same meaning as before
• require impls I ✅ allowed, same as require Self impls I
• require T impls I ✅ allowed, same meaning as before

Next, since we are creating another way that an interface can extend another interface, we change the existing usage of extend from being an introducer of its own declaration, to a modifier on a require declaration. In this case, the only type that can be constrained is Self, since that is the type being extended. To match the restriction that an extend impl must be followed by as in class scope, extend require can only be followed by impls in interface scope:

• extend require Self impls I ❌ forbidden, Self must be omitted since no other value allowed
• extend require impls I ✅ allowed
• extend require T impls I ❌ forbidden

extend require impls I after this proposal has the same meaning as extend I did before this proposal, so:

interface A {
  fn F();
}

interface B {
  extend require impls A;
  fn G();
}

is equivalent to:

interface A {
  fn F();
}

interface B {
  require impls A;
  alias F = A.F;
  fn G();
}

We then add another way to use extend as a modifier in an interface scope. We define the meaning of extend impl as I; in an interface J scope to do two things:

• Copy the members of I to form new members of J.
• Define a blanket impl that anything that impls J also impls I, by forwarding to the corresponding members of J.

These semantics are intended to be similar to extend impl in a class, except that the definition of the blanket impl is generated automatically (and impl without extend is not allowed in an interface).

In this example:

interface I {
  let T:! type;
  fn F();
  fn G();
}

interface J {
  extend impl as I;
  fn H();
}

The definition of interface J is equivalent to:

interface J {
  let T:! type;
  fn F();
  fn G();
  fn H();
}
impl forall [U:! J] U as I {
  let T:! type = U.(J.T);
  fn F() = U.(J.F);
  fn G() = U.(J.G);
}

The keyword final can be added between extend and impl to make the generated impl definition final. For example, the final impl forall [T:! type, U:! ImplicitAs(T)] U as As(T) from the “Problem” section would be generated from this:

interface ImplicitAs(T:! type) {
  extend final impl as As(T);
}

To allow a non-final impl to overlap a final impl, we say the final impl is prioritized over a non-final impl anytime they overlap. This addresses a problem caused by the fact that we don’t support the negative constraints that would allow a developer to avoid the overlap – and the only sound choice is to prefer the final impl. However, if a non-final impl can never be used because it is completely subsumed by a final impl, that is an error.

To allow multiple interfaces extending the same interface, we also want to support a way to declare overlapping final impls. We do this by listing the names of the overlapping impls in a final match_first block instead of putting final on the impl declarations. Note this requires all of the final impls to be in the same file.

The impl generated by an extend impl as Foo in an interface Bar can be named as impl Bar.(as Foo). This name can be used to put such an impl into a match_first block (or a final match_first block).

This example inspired by C++ iterator categories shows using these pieces together:

interface Iterator {
  fn Increment[addr self: Self*]();
}

interface InputIterator {
  let Element:! type;
  extend impl as Iterator;
  fn Get[addr self: Self*]() -> Element;
}

interface OutputIterator {
  let Element:! type;
  extend impl as Iterator;
  fn Set[addr self: Self*](x: Element);
}

// Makes both impls final and prioritizes them.
final match_first {
  impl InputIterator.(as Iterator);
  impl OutputIterator.(as Iterator);
}

interface ForwardIterator {
  extend final impl as InputIterator;
  fn Copy[self: Self]() -> Self;
  fn Equal[self: Self](compare: Self) -> bool;
}

interface OutputForwardIterator {
  // Need to be careful with `Element`, see the
  // "Name conflicts" section.
  let Element:! type;
  extend final impl as ForwardIterator
      where .Element = Element;
  extend final impl as OutputIterator
      where .Element = Element;
}

class MyIntIterator { ... }
// An impl of OutputForwardIterator also implements:
// Iterator, InputIterator, OutputIterator, and
// ForwardIterator.
impl MyIntIterator as OutputForwardIterator {
  where Element = i32;
  fn Increment[addr self: Self*]() { ... }
  fn Get[addr self: Self*]() -> i32 { ... }
  fn Set[addr self: Self*](x: i32) { ... }
  fn Copy[self: Self]() -> Self { ... }
  fn Equal[self: Self](compare: Self) -> bool { ... }
}

Details

Note that extend being first, before final or impl, follows our other uses of extend.

extend require

Some notes and clarifications on extend require:

• To be consistent with other uses of extend, we use the same name lookup rule: name lookup into a scope that extends other scopes first looks in that scope, and then if it finds nothing, it looks into all of the extended scopes, and the lookup is an error if there’s more than one different result. Example:

  interface A {
    fn F();
    fn G();
    fn H();
  }
  
  interface B {
    fn G();
    fn J();
    fn K();
  }
  
  interface C {
    extend require impls A;
    extend require impls B;
    fn F();
    fn J();
  }
  

  This definition of interface C means A and B are required and name lookup into C for:

  • F finds C.F, hiding A.F;
  • G is ambiguous, due to the conflict between A.G and B.G;
  • H finds A.H;
  • J finds C.J, hiding B.J;
  • K finds B.K.

  Note that if we had two more interfaces:

  interface D {
    fn G();
  }
  interface E {
    extend require impls C;
    extend require impls D;
  }
  

  then lookup into E for G is also ambiguous, since the ambiguous lookup into C for G still counts as a conflict with D.G.

• If interface B has extend require impls A, then any impl C as B will require an impl C as A. We no longer support implementing the members of A in an impl of B, see leads issue #4566 and proposal #5168.

• If we accept the extend api/extend alias proposal #3802, then extend require impls A; becomes equivalent to require impls A; plus extend api A; (or extend alias A;, depending on the syntax we choose).

extend impl as with parameterized interfaces

When using extend impl as in a parameterized interface, those parameters end up in the forall clause in the generated impl. For example:

interface PointerContainer(T:! type) {
  extend impl as Container(T*);
}

generates this impl:

impl forall
    [T:! type, U:! PointerContainer(T)]
    U as Container(T*) { ... }

extend impl as restrictions

extend impl as can only be used if the generated impl would be legal. This includes the the orphan rule, so the interface or type argument must be in the same file. For example:

class BigInt { ... }

interface IntLike {
  // Only valid in the same library as `ImplicitAs`
  // or `BigInt`.
  extend impl as ImplicitAs(BigInt);
}

The additional restrictions on final impls mean that extend final impl as can only be used in the same library as the interface being extended, not the type arguments.

Similarly, the expression to the right of the as must correspond to a single interface, due to leads issue #4566 and proposal #5168.

Name conflicts

If two associated constants or functions have the same name in the two interfaces, this is an error since there is no way to assign values to both in an impl of the extending interface.

Example with an associated function:

interface A {
  fn F();
}

interface B {
  fn F();
  // Name conflict with `F`.
  extend impl as A;
}

class C {
  impl as B {
    // Probably refers to the `F` explicitly declared in `B` --
    // no way to implement the `F` that comes from `A`.
    fn F() { ... }
  }
}

Example with an associated constant:

interface A {
  let T:! type;
}

interface B {
  let T:! type;
  // Name conflict with `T`.
  extend impl as A;
}

class C {
  impl as B {
    // Two different associated constants named `T` and no way
    // to distinguish them.
    where T = i32;
  }
}

Notice that the rewrite to put the members of A into B would result in a conflict. Further, if there is only one member with that name after the rewrite in B, then there is no way to write the generated impl to set the member of A from the values of the associated constants in B.

However, if the extending interface gives a value to the associated constant, there is no need to specify that value in an impl, so that is not an error.

interface A {
  let T:! type;
  fn F() -> T;
}

interface B {
  let T:! type;
  // Okay
  extend impl as A where .T = T*;
}

class C {
  impl as B {
    // `T` here is `B.T`
    where T = i32;
    // `F` here is `B.F` and `A.F`.
    fn F() -> i32*;
  }
}

This is equivalent to:

interface A {
  let T:! type;
  fn F() -> T;
}

interface B {
  let T:! type;
  // Skip A.T due to conflict.
  fn F() -> T*;
}

impl forall [U:! B] U as A where .T = .(B.T)* {
  fn F() -> T = U.(B.F);
}

class C {
  impl as B {
    where T = i32;
    fn F() -> i32*;
  }
}

This was used in the OutputForwardIterator example in the “Proposal” section.

Name conflicts are not expected to generally be a problem in practice since this form of extension often requires the two interfaces to be defined in the same file.

Final impl priority

With the design prior to this proposal, a final impl can only overlap another (final or non-final) impl if they have the same definition on their overlap. This means that if there is a final blanket impl of an interface, as is generated by extend final impl as in the interface’s scope, then other impls of that interface may be overly restricted. This example:

package Core;

interface As(T:! type) {
  fn Convert[self: Self]() -> T;
}

interface ImplicitAs(T:! type) {
  extend final impl as As(T);
}

is equivalent to:

package Core;

interface As(T:! type) {
  fn Convert[self: Self]() -> T;
}

interface ImplicitAs(T:! type) {
  fn Convert[self: Self]() -> T;
}

final impl forall [T:! type, U:! ImplicitAs(T)] U as As(T) {
  fn Convert[self: Self]() -> T = U.(ImplicitAs(T).Convert);
}

Any other impl of As(T) is going to overlap unless we could establish that the type does not implement ImplicitAs(T). However, in a generic context, we don’t support (and don’t intend to support) that sort of negative constraint. So there would be no way to prove the following impl of As(T) doesn’t overlap the final impl of As(T):

import Core;

class X(T:! type) {
  impl as As(T);
}

In particular, an unrelated library defining MyType could define impl X(MyType) as ImplicitAs(MyType), which would create a conflict between the impl in X(T) and the final impl associated with ImplicitAs(T).

This motivates a change to the rules: we want to allow a non-final impl to overlap with a final impl. The question is what to do for queries in the overlap.

Now consider this second example:

import Core;

class Array(Element:! type) { ... }

// Impl 1
impl forall [T:! type, U:! As(T)]
    Array(U) as As(Array(T)) { ... }

// Impl 2
impl forall [T:! type, U:! ImplicitAs(T)]
    Array(U) as ImplicitAs(Array(T)) { ... }

This creates a conflict:

1. Impl 1 provides impl Array(U) as As(Array(T)).
2. Impl 2 provides impl Array(U) as ImplicitAs(Array(T)).
3. The Core package defined at the beginning of this section has final impl forall [T:! type, U:! ImplicitAs(T)] U as As(T).
4. Combining 2 and 3 provides another definition of impl Array(U) as As(Array(T)) which is final. Impl 1 has a more specific type structure, though.

Furthermore, this example is realistic:

• The final blanket impl defined in the Core package is the definition we expect to use.
• We need impl 1 to support types T that only impl As(U) and not ImplicitAs(U).
• We need impl 2 to support types T that impl ImplicitAs(U).
• Carbon will define an implicit conversion from i32 to i64, and it would be reasonable to ask if Array(i32) implicitly converts to Array(i64), which would be a query in the overlap.

Any generic code that sees the final impl can assume it applies whenever it is used. If we don’t want to forbid this overlap situation (either when defining a non-final impl with a more-specific type structure or when doing an impl query in the overlap that selects the non-final one), the only sound choice is to use the final impl. And we don’t want to give an error here since:

• It would reduce expressiveness, since there isn’t a good workaround to prevent the overlap.
• It would reduce the ability to compose libraries.
• We want to support examples like this interaction between Array, As, and ImplicitAs.

Note that prioritizing the final impl over the non-final impl (even when the non-final impl has a preferred type structure) produces the desired result in the example above. By writing final we ensure that Convert in ImplicitAs always matches Convert in As, when they are both defined.

Also note that this gives the desired behavior that this final impl of the CommonTypeWith interface:

final impl forall [T:! type] T as CommonTypeWith(T) where .Result = T {}

is prioritized as if it is more specialized than user-written impls of CommonTypeWith, as desired.

Overlapping final impls

The next question is what to do if there are overlapping final impls. We considered options that allowed them to be in different files, but this led to prioritization that was inconsistent with the type structure rules for non-final impls.

In particular, the restrictions on which libraries can define a final impl mean there are at most two files that can contain two final impl definitions that both match a particular (type, interface) query: the one defining the root type and the one defining the root interface. The only way to have the final impls in different files is if there is a blanket impl of the interface in the file defining the interface and the other in the file defining the type. Generic code may only see the file with the interface, and since it is marked “final” will assume it is safe to use. As a result, the only sound solution is to prioritize the final blanket impl over the final impl that specifies the type, the opposite of how non-final impls prioritize using type structure. Furthermore, there would be queries that would match the final impl that specifies the type but would not select that impl, a property we would like to have. So we require that overlapping final impls be declared in the same file, a restriction that the compiler can enforce due to the file limitations.

Future work: If we determine that we do want to support overlapping final impls across the two files, we thought the second file could use extend final match_first to say “these entries are notionally added to the earlier final match_first.

Within a file, we have two tools here we could use to select between the candidates: type structure and impl_priority/match_first blocks. (We will use the placeholder term of “match_first blocks” to refer to these without asserting how they will be spelled.)

The decision here is to only use match_first blocks, not type structure to choose between overlapping final impl definitions, for a few reasons:

• Type structure is needed to pick betewen impl defined in different files, which we are not allowing for final impls.
• A match_first block is very explicit way of prioritizing, and with final impls in particular it is helpful to be clear about the conditions where they won’t be selected even when they match.

With this decision not to use type structure to prioritize final impls, it doesn’t make sense to mix final and non-final impls in the same match_first block. Furthermore, until the compiler sees the match_first block, we can’t treat an impl as final since we don’t know if another final impl will be appear earlier in the match_first block and used instead. Which leads to the decision to put the final modifier on the match_first block instead of the impl declaration, when it appears in a match_first block. Example:

// Compiler does not treat this as final, so it
// won't use `A = i32`.
impl forall [T:! Z] T as J {
  where A = i32;
  // ...
}

fn F(T:! Z) {
  // Can assume `T impls J`.
  // Can't assume `T.(J.A)` is `i32`.

  // If we were to mark the above `impl` as `final`,
  // this code would assume it is selected, and we
  // would have to poison the impl lookup to prevent
  // the following conflicting `impl` and
  // `match_first` declarations.
}

// Also not treated as final yet, so the compiler
// won't use `A = bool`.
impl forall [U:! Y] U as J {
  where A = bool;
  // ...
}

// Matching `bool` assignment to `J.A` as the
// previous impl.
impl forall [V:! W] V as J {
  where A = bool;
  // ...
}

final match_first {
  impl forall [U:! Y] U as J;
  impl forall [V:! W] V as J;
  impl forall [T:! Z] T as J;
}

// Now all are considered final, with the
// understanding that `impl forall [T:! Z] T as J`
// may not be used even when it matches. The
// compiler can now tell if it can use `A = bool`
// from `impl forall [U:! Y] U as J`.

fn G(U:! Y) {
  // Can assume `U impls J` and `U.(J.A)` is `bool`.
}

fn H(V:! W) {
  // Don't know if `V impls Y`, so we don't know
  // which `impl` is selected. We use a symbolic
  // witness for `V` and `V.(J.A)` is unknown
  // (despite that it would be `bool` in either
  // case).
}

Note: final match_first was considered in open discussion on 2023-09-13 as a part of function overloading, and other times since.

This leads us to these rules:

• An impl is considered “final” if is declared with the final keyword modifier or if it is named in a final match_first block.
  • In the first case (a final impl declaration), that impl may not appear in any match_first block.
• An impl may appear in at most one match_first block.
  • This is true whether or not the block is marked final.
• Two final impls in the same file must appear in the same final match_first block if they overlap, as determined by their type structure.

Using associated constants from impls in a final match_first

As established by proposal #5168, concrete impl queries resolve to a concrete impl witness, with the associated constants from a single impl definition. A symbolic impl query can in some cases use the associated constants from a final impl. If an impl query matches an impl marked final (as opposed to one in a final match_first), then that impl will definitely be used. In that case, the associated constants from the impl can be used.

If a symbolic query selects an impl from a final match_first block, though, that impl’s associated constants may only be used if it is the first that could match in its final match block, as determined by the type structures of the impls that appear earlier. Phrased another way, a query will use the associated constants of a final impl if it both matches and has no overlap with the type structure of any of the impls that appear before it in its final match first block. For example:

interface L(T:! type) {
  let B:! type;
}
class C(T:! type) {}

final match_first {
  // Can use the associated constants from this impl,
  // since it is the first, so nothing could match ahead
  // of it.
  impl forall [U:! Y] C(U) as L(bool) where .B = i32;

  // Queries that match this impl and can't match the
  // previous impl's type structure can use the
  // associated constants from this impl. In this case,
  // that happens if the self type (left of the `as`) of
  // the query can't match `C(?)`.
  impl forall [V:! W] V as L(bool) where .B = bool;

  // Can use the associated constants from this impl,
  // since any query that matches `T as L(i32)` won't
  // match the type structure of the earlier impls in
  // the `final match_first`, since they all have
  // `L(bool)` to the right of `as`.
  impl forall [T:! Z] T as L(i32) where .B = f32;
}

class D(X:! type) {}
impl forall [X:! type] D(X) as W {}
// D(X) as L(bool) uses the middle `impl forall` from
// the `final match_first` so the return type is `bool`.
// Note that we can conclude `D(X)` does not match the
// type structure of the first `impl forall` of
// `C(?) as`... even though the query is not concrete.
fn F(X:! type) -> (D(X) as L(bool)).B {
  return true;
}

class E(T:! type) {}
impl forall [T:! type] C(E(T)) as W {}
// `C(E(T))` does impl `W`, so it impls `L(bool)`. But
// since we don't know whether `E(T)` impls `Y`, we
// don't know which impl it will ultimately use, and so
// `(C(E(T)) as L(bool)).B` is unknown.

impl selection algorithm

In conclusion, we prioritize final impls over non-final impls. In the case that there are multiple matching final impls defined in the same file, they overlap so they must be in a single final match_first block. In that case, pick the first matching one listed in the final match_first block.

If no final impl declarations match the query, we fall back to the original rules:

• The non-final impl declarations matching the query with the most preferred type structure must be in the same non-final match_first block, or a single non-final impl declaration not in a match_first can match.
  • In the latter case, that impl is selected. Alternatively, impl declarations not in any match_first block could be considered to be the only member of their own match_first block.
• If a non-final match_first block is chosen, the first matching impl in that block is selected.

Since it may be observable which impl declarations are considered during impl lookup, due to the acyclic rule and termination rule, we specify this more precisely:

• Only (final or non-final) impls with a type structure compatible with the query are considered.
• Final impls are considered in the order they appear in the final match_first block, if any.
  • The first matching final impl considered is returned, skipping the remaining steps.
• Non-final impls are considered most specific type structure first.
• Non-final impls with the same type structure are considered in the order they appear in their common match_first block.
• Once the first matching non-final impl is found:
  • If it is not in a match_first block, it can be returned, skipping the remaining steps.
  • The non-final impls earlier in the same match_first block with compatible type structure are considered in the order they appear in the match_first block
    • We skip those with an equal or preferred type structure compared to the matching impl, since those have already been considered and determined to not be matching.
  • The first matching impl is selected. If no impl matches before the one used to select the match_first block, that impl is selected and no later impls will be considered.

An impl that can never match is an error

Instead of the current rule that prevents a (final or non-final) impl from overlapping an existing final impl, we have a replacement rule that says a (final or non-final) impl that will never be selected due to being subsumed by a final impl is an error.

The compiler can detect whether an impl declaration is subsumed by performing an impl lookup (restricting to final impls) for the query represented by its declaration (ignoring any trailing where clause setting associated constants). For the declaration impl forall [T:! I] X(T) as J where .A = bool, as an example, the query would be “X(T) impls J with T impls I”.

Note that the rules for which libraries can define a final impl mean that a subsuming final impl is either visible or is later in the same file (and such will be diagnosed due to poisoning when we look for a subsuming final impl). In order to detect the subsumption, the query for the final impl should either be delayed to the end of the file, or poisoned.

Concern: Consider a situation where a library defines a broad final impl, but has determined it is a bad idea and wants to remove it in the future. One strategy would be to ask clients of the library to define their own non-final impls first. This non-final impl would be ignored before the transition since the final impl has higher priority, but would be used once the final impl is removed. In this case, we would like to suppress the error for the subsumed non-final impl defined in the client. This is future work, but our current idea is to associate the final impl with some build configuration constant to mark it as conditionally available. A final impl marked in that way would not be considered to subsume any impl not marked the same way. This could also be used to allow temporary changes made while debugging.

Impl names for prioritization

The generated impl from an extend impl in an interface is given a name similar to an impl defined in a class scope, as discussed on 2024-03-11, mentioned in proposal #3763, and proposed in pending proposal #5366.

For example, these names can be used to allow multiple interfaces to extend a single interface:

interface A(T:! type) {
  fn F() -> T;
}

interface B {
  extend impl as A(i32);
  // Produces impl with name `B.(as A(i32))`.
}

interface C1 {
  let U:! type;
  extend impl as A(U);
  // Produces impl with name `C1.(as A(U))`.
}

interface C2 {
  let U:! type;
  // Only difference from C1 is using `Self.U` instead of `U`.
  extend impl as A(Self.U);
  // Produces impl with name `C2.(as A(Self.U))`.
}

interface D(V:! type) {
  extend impl as A(V);
  // Produces impl with name `D(V:! type).(as A(V))`.
}

interface E {}
impl forall [W:! E] W as A(W) { ... }

class F {}
impl F as A(F) { ... }

// Placeholder impl priority syntax
match_first {
  impl B.(as A(i32));

  impl C1.(as A(U));
  impl C2.(as A(Self.U));
  // Can't write `impl C1.(as A(Self.U))` or `impl C2.(as A(U))`.

  impl D(V:! type).(as A(V));

  impl forall [W:! E] W as A(W);

  impl F as A(F);
}

Note how the expression after the as has to match syntactically between the two declarations.

Without the impl prioritization, these would be conflicting impls of the interface A. Note that by the overlapping final impl rules, at most one interface can final extend impl as a given interface. final match_first must be used instead of multiple final impls, so that there is an explicit prioritization between them, as in this example:

interface I {
  fn IFn();
}

interface J {
  // Can't mark as `final` here.
  extend impl as I;
  fn JFn();
}

interface K {
  // Can't mark as `final` here.
  extend impl as I;
  fn KFn();
}

// Makes both impls final and prioritizes them.
final match_first {
  impl J.(as I);
  impl K.(as I);
}

When the extending interface is parameterized, following the approach of proposal #3763: Matching redeclarations, the same sequence of tokens (between the interface and {) is used to name the interface, allowing a syntactic match. For example:

interface Z(T:! type) { ... }

interface Y(T:! type) {
  extend impl as Z(T*);
}
// ...

final match_first {
  impl Y(T:! type).(as Z(T*));
  // ...
}

Rationale

This proposal’s end goal is to support a form of interface extension that matches user’s expectations, to aid the “Code that is easy to read, understand, and write” goal. This goal also informed the choice to be explicit about prioritizing overlapping final impls.

The choice to not treat an impl as final when it overlaps another final impl until we see how to choose between them on the overlap is in accord with the information accumulation principle.

Alternatives considered

Allow overlap between a non-final and final impl but only if no queries pick the non-final on the overlap

This question was considered in the “final impl priority” section.

Forbid overlap between final impls

The downside of allowing them to overlap is we no longer have the property that a final impl is selected anytime it matches. This puts limits on when the compiler can use the values of associated constants from a final impl. However, the use cases, such as having multiple interfaces extend a single interface, were compelling.

Prioritize between final impls using type structure

This question was considered in the “Overlapping final impls” section.

Allow mixing final and non-final impls in the same match_first block

There were some ways we could imagine supporting a mix of final and non-final impls in the same match_first block. With the decision to not use type structure to prioritize between final impls, though, reconciling the differences seemed like it would lead to a lot of complexity and surprising behavior, like priority inversions. We thought the approach of putting final on the match_first block resulted in simpler rules.

No default Self in require Self impls I

Shortening of require Self impls I to just require I was considered in proposal #2760. It was not chosen to be consistent with where clauses, but the door was left open if it was found to be too verbose. The require impls I approach adopted by this proposal, though, could be extended to work with where as well. The consideration of that change has been left to future proposals, and is out of scope for this one.

Different rules for prioritizing between final impls

We considered five options in discussions in a GitHub comment on this proposal, #generics-and-templates on Discord on 2025-05-02, and open discussion on 2025-05-05.

1. Final impls in the file with the interface are prioritized over the final impls in the file with root self type of the impl (when they are different).
2. Blanket final impls with a ? for the whole self type in the type structure are prioritized over final impls with a concrete root self type.
3. Final impls are prioritized using the reverse of type structure prioritization.
4. The syntax of final impls associates them with either the interface (final match_first) or the root self type (extend final match_first). Those associated with the interface are prioritized first, and then those associated with the type are prioritized after. Ties are resolved by type structure and then match_first.
5. Final impl overlap is only allowed within a final match_first block.

Note: Each final impl must be declared either in the file with the interface or the root type.

The concern with option 1 was that concatenating files that contain overlapping final impls, such as when creating a reproduction of a bug, would necessitate match_first changes.

The concern with option 2 was that it was a new rule to learn, unrelated to the rule for non-final impls. It has the advantage of using explicit match_first to prioritize almost as much as option 1, while allowing files to be concatenated with fewer changes.

The concern with option 3 was that it might not do what developers expect, due to being the opposite of non-final impl prioritization.

In general, options 1-4 were more complex than option 5. Option 5 maximized the use of explicit match_first to resolve priority on final impl overlap, rather than an implicit prioritization. We were also interested these two properties:

• If we have two impls A and B where A is preferred over B, and then we make them both final, we should not make them valid but with B preferred over A.
• A final impl is selected for any query that it matches.

which options 1-3 did not satisfy. The main concern with option 5 was that it might not be able to express desired use cases. We noted, though, that you could create additional interfaces to support different prioritization policies. For example:

interface ImplicitAs(T:! type) { ... }
interface HighPriorityImplicitAs(T:! type) { ... }
interface LowerPriorityFrom(U:! type) { ... }

final match_first {
  impl forall [T:! type] T as ImplicitAs(T);
  impl forall [T:! type, U:! HighPriorityImplicitAs(T)]
      U as ImplicitAs(T);
  impl forall [U:! type, T:! LowerPriorityFrom(U)]
      U as ImplicitAs(T);
}

Notes:

• This gives control over which type is given special treatment as the self type when implementing one of the auxiliary added interfaces.
• This final match_first is with the interfaces, but that does not preclude a final impl of HighPriorityImplicitAs or LowerPriorityFrom in the files with the self root types.

Different final match_first associated constant rules

We considered in discussion on 2025-05-06 a couple of alternative rules for determining when associated constants were considered to be known, and what value to use, when matching an impl from a final match_first.

One approach was to say that the final match_first would be allowed to have a where clause specifying the value of a subset of the associated constants of the interface. Every impl named in the body would have to have a consistent assignment to those associated constants in their definitions. This had two downsides:

• It did not support the anticipated overloading use cases well, where the return type would vary across overloads.
• Supporting associated constants whose value varied with the value of a type or interface parameter would have added a lot of complexity.

Another approach we considered was to say an associated constant would have a value if every impl that could match gave the same value. For example, in the first example from the “Overlapping final impls” section, the first two impls in the final match_first both set A.J to bool, so anything matching either of them could use bool for the value of A.J. This seemed hard to reason about. Also, there were concerns that this would be very sensitive to changes, introduce additional fragility in the case of evolution.

We also considered only using associated constants that were included in the impl’s name (using a where clause in the facet type instead of a where declaration in the impl definition body). This had the advantage that the logic for determining the values of those associated constants could be done without the impl definitions. This would introduce implementation complexity, and would cause impl names to be longer increasing verbosity. It would also introduce a difference between a final impl and a single impl by itself inside a final match_first.