Dependent name lookup in base class templates

[josh11b]

trafficstars

Summary of issue:

Consider this code:

// #1
fn F();
class C(template T:! type) {
  extend base: T;
  fn G[self: Self]() {
    // #2
    F();
  }
}

class B {
  // #3
  fn F();
}

var x: C(B) = {};
x.G();

What happens at #2 in x.G()? Does it call #1? #3? is it an error since both names are in scope?

In discussion on 2023-09-05, we decided we were most interested in three options:

• C++ rules -- unqualified name lookup happens and finishes before template instantiation, and if you want to find it a name in the template, use a dependent qualification of the name. In the example, #2 always calls #1.
• No unqualified name lookup through extend -> always have to use Self or self to get to base class names. In the example, #2 always calls #1.
• Dependent unqualified name lookup. This has the downside that unqualified names in a method of a class with a template base would in some instantiations find globals and others base members. In the example, #2 sees both #1 and #3 and either calls #3 or it is considered ambiguous. With other instantiations, like C({}), #2 might only see #1 and call that.
• Require disambiguation anytime it could look inside a template. That would make #2 ambiguous at its definition and require qualification, independent of how it is instantiated. With this rule, changing a base class to be a template would break code in all transitively-derived classes.

Details:

Note that switching T to a checked-generic T:! type means name lookup no longer depends on the instantiation, and so there is a better option for avoiding this problem than C++.

The difference between the first two options is what happens with non-templated base classes:

class D {
  extend base: B;
  fn H[self: Self]() {
    // #4
    F();
  }
}

With C++ rules, #4 would see #1 and #3.

With "no unqualified name lookup through extend", #4 would not consider #3 and instead always resolve to #1. To call #3, you would have to write something like B.F(), Self.F(), or self.F(). We might also consider adding base.F() or even Base.F(). With this rule, unqualified name lookup would only find names directly declared in class scope, and not in any referenced or nested scope.

[josh11b]

C++ Rules

[josh11b]

No unqualified name lookup through extend

[josh11b]

Dependent unqualified name lookup

[josh11b]

Require disambiguation anytime it could look inside a template

[josh11b]

FYI, one use case for base class templates is implementing types that have different APIs for different specializations, such as std::vector<bool>. This might be modeled in Carbon as:

interface VectorSpecialization {
  let BaseType:! type;
  // anything else that might change with specializatoin
}

impl [forall T:! Type] T as VectorSpecialization {
  class BaseType {
    // default API if not specialized
  }
}

impl bool as VectorSpecialization {
  class BaseType {
    // Vector(bool)-specific API;
    fn Flip[addr self: Self*]();
    // ...
  }
}

class Vector(T:! type) {
  extend base: (T as VectorSpecialization).BaseType;
  // ...
}

I agree that in this case we generally aren't going to need to find members of BaseType when doing unqualified lookup in the implementation of Vector(T) methods, and callers of functions like Flip are going to be in a qualified context, which argues against the "Dependent unqualified name lookup" option (and would make the "Require disambiguation anytime it could look inside a template" option more painful for Vector(T)).

The alternative to this specialization approach would require accessing the Flip method through a member of Vector(T), which is a bigger difference from C++.

[josh11b]

@zygoloid @chandlerc I thought of an argument for a particular approach. Right now name lookup with templates follows the information accumulation principle. By this I mean:

• Name lookup happens at definition time. If a name is found, it is assumed to be correct and is used.
• Name lookup is repeated when the argument value of the template parameter is known. If this results in a different name being found than was assumed in the first step, it is an error. (If no name was found in the first step, it counts as "no information" not "contradictory information", and the results from the second step are used.)

Applying this same approach to this problem gives:

• Name lookup happens at definition time. At #2 it finds #1.
• Name lookup #2 is repeated at instantiation time, and finds #3. This contradicts the previous assumption, and so results in an instantiation failure.

So the cases are:

• Use of unqualified names that don't resolve at definition time are equivalent to having a T. qualification, and are looked up in the templated base at instantiation time. Those names are template dependent.
• If the unqualified name is found in the bound on the template parameter at definition time (as in example below), it has the normal template behavior of checking that name lookup has the same result when looked up in the instantiating type. The validity of that name is template dependent.
• If the unqualified name is found elsewhere at definition time, that name is assumed to be used as described above, so again the validity of that name is template dependent. Name lookup is repeated at instantiation time and if the result is different, it is a monomorphization error.

I think that means that in all cases unqualified names are looked up at definition time, and based on the result they get a qualification. I think the remaining possible instantiation/monomorphization errors are all errors that could otherwise occur from template instantiation/monomorphizaton.

Example of the middle case:

interface I {
  // #4
  fn F();
}

class C2(template T:! I) {
  extend base: T;
  fn G[self: Self]() {
    // #5
    // At definition time, `F` resolves to #4 `I.F`
    // based on the `I` bound on `T`.
    F();
  }
}

class B2 {
  // #6
  fn F();
  impl as I {
    // #7
    fn F();
  }
}

// Okay: `B2` implements `I`
var x2: C2(B2) = {};
// Monomorphization error: #5 resolved to `I.F` at
// definition time, which is #7 for `B2`, but #5
// resolves to #6 at instantiation time.
x2.G();

class B3 {
  extend impl as I {
    // #8
    fn F();
  }
}
// Okay: `B3` implements `I`
var x3: C2(B3) = {};
// Okay: #5 resolved to #8 at definition and
// instantiation time.
x3.G();