Allow overlap with a final impl if identical

Pull request

Table of contents

Abstract

Allow an impl to overlap with a final impl if they agree on the overlap. Agreement is defined as all values comparing equal, and functions never comparing equal. Implements the decision in question-for-leads issue #1077: find a way to permit impls of CommonTypeWith where the LHS and RHS type overlap.

Problem

The current design includes a final impl declaration for the CommonTypeWith(T) interface:

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

Marking an impl declaration final, prevents any overlapping implementation that would be considered more specific by the overlap rule. This includes cases where the overlap is harmless, such as:

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

This is an implementation we would like to define, along with a number of similar cases. And this impl declaration doesn’t actually conflict with the previous final impl because the value of Result, the only member of the CommonTypeWith interface, agrees where the two implementations overlap.

Background

The CommonTypeWith(T) interface and final impl above were introduced in proposal #911: Conditional expressions.

Proposal #983: Generics details 7: final impls introduced and defined the rules for final impl declarations.

The overlap rule was introduced in proposal #920.

There were a number of different resolutions for this problem considered in question-for-leads issue #1077: find a way to permit impls of CommonTypeWith where the LHS and RHS type overlap. This proposal codifies the resolution of that issue.

Proposal

We allow an impl declaration to overlap with a final impl declaration if it agrees on the overlap. Since we do not require the compiler to compare the definitions of functions, agreement is only possible for interfaces without any function members. The details about how the intersection is computed and how templated impl declarations are handled have been added to the section on final impl declarations in the generics design doc.

Rationale

This proposal is intentionally keeping the language small by making a simple rule that addresses the only identified use case and nothing more. This benefits

by relying on Carbon’s commitment to software and language evolution to update our approach as needed, rather then trying to proactively address concerns ahead of time.

Alternatives considered

Allow interfaces with member functions to compare equal

There are some specific cases where the compiler can verify that two functions are the same without having to compare their definitions. For example, two implementations that don’t implement a function and instead inherit the default from the interface could be considered equal. This creates an evolution hazard, though, that copying the definition from the interface into the implementation means that the interface could now compare not equal without any change in behavior. For now, the simple rule that we don’t compare functions at all is sufficient for our identified use case. This is something we would reconsider given new use cases.

Mark associated constants as final instead of an impl declaration

The biggest benefit from knowing that an impl declaration won’t be specialized is being able to use the values of the associated constants, particularly associated types. Thus, it is natural to focus on associated constants, which don’t have the same concerns as functions with comparing for equality.

However, for the motivating use case, we would still need this proposal, just restricted to the associated constants that are declared final. So we may still add this feature, if it is warranted by demand, but we did not yet have that justification. This is essentially the same position as when this feature was considered in proposal #983.

Allow type inequality constraints

Another approach would be to provide type inequality constraints so the more specialized implementation could exclude the overlapping cases. This has some downsides:

  • The more specialized implementation has to be aware of the final impl to specifically exclude it. This would add extra steps to the development process since this discovery is likely to occur as the result of a failed compile.
  • The more specialized implementation becomes more verbose, with extra conditions that don’t add any value.
  • The current approach for establishing whether two types are equal doesn’t in general provide a way to show two types are not equal in generic code.

Prioritize a final impl over a more specific impl on the overlap

This was a possible fix, but was seen as a bigger change that we didn’t yet have justification for.