Constrained template name lookup

[josh11b]

Given a template function constrained to taking types implementing the interface Hashable:

interface Hashable {
  fn Hash...;
  fn CombineHash...;
}

and we call it with a value with type Potato that implements Hashable externally and has a method name conflict with Hash:

class Potato {
  fn Hash...;
  fn FrenchFry...;
}

Question: How should name lookup in the template function work?

Goals: These are desirable properties, but are in conflict. We won't be able to achieve all of these:

• Substitutability: Like C++, a template call behaves as if the caller's type is substituted in place of the template parameter.
• Continuity: The change from going from an unconstrained template to a constrained template is similar to the change from adding that constraint to an existing constraint.
• Incrementality: Can add constraints to a template one at a time, incrementally.
• Evolvability: Switching from an unconstrained template to a constrained template and from a constrained template to a generic never causes a member name to be silently reinterpreted differently. Either names refer to the same thing semantically, or you get an error.
• Convenience: The code can be brief since names don't have to be qualified all the time.
• Disambiguation: Adding a constraint clarifies that calls that are ambiguous should be resolved to mean the name in the constraint.
• Simplicity: The explanation of the model to users is brief, without edge cases that need to be explained.

Options: Given this template function, which calls are legal and what do they resolve to?

fn F[template T:! Hashable](x: T) {
  x.FrenchFry();
  x.Hash();
  x.CombineHash();
}
var p: Potato = ...;
F(p);

• Type: Lookup follows the C++ rule of looking up names in the caller's type, just like unconstrained templates. Good for substitutability, continuity, incrementality, simplicity. Medium for: convenience (type names are unqualified). Bad for evolvability (reinterpretation happens in constrained template -> generic transitions), disambiguation.
• Constraint: Lookup is only in the constraint unless there is no constraint, most similar to how generics work. Good for disambiguation, simplicity. Medium for: convenience. Bad for: substitutability, continuity, incrementality, evolvability (reinterpretation happens when adding constraints to an unconstrained template).
• Constraint over type: Lookup is in the constraint first, and if not found look in the type. Good for incrementality, convenience, disambiguation, continuity. Medium for simplicity. Bad for substitutability, evolvability (reinterpretation happens when adding constraints)
• Union minus conflicts: Lookup is done in both the type and the constraint and succeeds if they do not conflict, following & for combining constraints. Conflict is both defining the name, with different definitions. Good for: continuity, incrementality, evolvability, convenience. Medium for substitutability. Bad for: disambiguation, simplicity. In addition to being a more complicated rule to explain, it has edge cases regarding when it triggers with respect to associated types.

Option	x.FrenchFry() Type only	x.Hash() Conflict	x.CombineHash() Constraint only
Type	-> Type	-> Type	rejected
Constraint	rejected	-> Constraint	-> Constraint
Constraint over type	-> Type	-> Constraint	-> Constraint
Union minus conflicts	-> Type	rejected	-> Constraint

I've omitted the "both" column with the case where the name is present in both the type and the constraint with the same definition. All options allow that name to be referenced unqualified to pick up the consistent definition.

[josh11b]

Note that I excluded an option that no longer had any supporters:

• Type minus conflicts: look up in the type unless the name has a conflict in the constraint, which is also good for evolvability, but almost as complex as the more convenient "union minus conflicts"

Option	x.FrenchFry() Type only	x.Hash() Conflict	x.CombineHash() Constraint only
Type minus conflicts	-> Type	rejected	rejected

[josh11b]

My current preferences are for "type", for simplicity and consistency with C++, or "union minus conflicts", for evolvability and convenience. After that I'd consider "constraint over type", and in last place for me is "constraint". My concerns with "constraint" is that it has a lot of overlap with generics and for those use cases I think we should be pushing people to generics. It also gives up too much in the way of continuity and incrementality without gaining evolvability. I thinks its main benefit is disambiguation, which isn't as important to me in a template context.

[chandlerc]

I'm still somewhat struggling with "type" because the constraint in a type-of-type position in that model actively confuses my thinking about it...

But I'm being won over by both constraint over type and union minus conflicts. I think I'd be quite happy with either of those at this point. Beyond the advantages over "constraint" that @josh11b mentions, they also both have the nice property that the unconstrained point is actually useful and exactly matches unconstrained C++ templates. As the overwhelming majority of C++ templates are unconstrained (constraint syntax is very new, and just hasn't had time for widespread adoption), this seems like the most important bit of consistency with C++ for me.

[chandlerc]

The "union minus conflicts" model, particularly if we look in the impl of the constraint (which we can because it's a template) to ensure aliases don't form conflicts, seems really convenient and user friendly to me. I think that's the one I'm somewhat leaning toward at this point, but still mulling over.

[zygoloid]

Constraint

I think this rule largely removes the difference between constrained templates and generics. Some differences would probably remain (eg, impl lookup being potentially deferred for templates but needing to match eagerly for generics), but I'm not sure whether it's worth supporting both constrained templates using the "constraint" rule and generics.

Union minus conflicts vs constraint over type

The difference between these two is whether you look in the constraint or reject in the case of ambiguity. Given that choice, I think I prefer rejecting, because I expect there to be situations where it's unclear whether a constraint is known or not when type-checking a template, and in such circumstances the "constraint over type" model would give quite different interpretations for programs that differ in ways that we might not want a developer to need to understand. For example:

interface Foo {
  type T:! Hashable;
  overloaded fn G[me: Self](n: i32) -> T;
  overloaded fn G[me: Self](p: Self*);
}
fn H[template F:! Foo](f: F) {
  f.G(0).Hash();
}

What happens here, under "constraint over type"? I think:

• If we can determine while type-checking the template H that f.G(0) will always call the first overload, then we know that its return type is Hashable, so we know that the .Hash is .(Hashable.Hash), and we call that.
• If we can't determine which function will be called, then the return type is a fully-unknown template-dependent type, so we defer name lookup to instantiation, and call the Hash found in the type instead.

... and I think it's not reasonable to expect a Carbon developer to know whether type-checking the template will be able to figure out which overload is picked here.

In contrast, under "union minus conflicts", we will never pick Hashable.Hash if the type has a member Hash, regardless of whether we can resolve the overload during type-checking. If we can resolve the overload, then H will support types that only implement Hash externally and have no member Hash, so the validity of the example can depend on this subtle determination, but the interpretation of a valid example cannot.

So, of these two, I think I prefer "union minus conflict" for that reason, and I'd be happy removing "constraint over type" from consideration.

Type versus other rules

The "type" rule is simple and matches C++ behavior, but sacrifices consistency with the behavior of generics, and means that constraints don't affect name lookup, which may be surprising. However, in a constrained template that correctly deals with conflicts, all uses of members from the constraint must always be written with explicit qualification anyway, so the "type" rule doesn't add any additional burden for such templates. Moreover, if we consider explicit qualification by the constraint to be good style (because it avoids ambiguity problems in the case where there is a type versus constraint conflict), the "type" rule encourages that good style.

My conclusions

Both the "union minus conflict" and "type" rules have appeal. "Type" seems simpler but requires more work to use methods from interfaces in a constrained generic, and provides a less good story for migrating from templates to generics; "union minus conflict" provides better ergonomics for pragmatic cases where conflicts aren't expected.

Of these, I'm leaning towards preferring "union minus conflict".

[chandlerc]

I agree both with the analysis and conclusion FWIW. Maybe we have a decision?

[chandlerc]

Seems Richard and I are both aligned here, and this doesn't seem like a contentious issue across the leads so let's call this decided with union-minus-conflicts as described above and with Richard's rationale.

[zygoloid]

Implemented in #989.