How should unqualified lookup work for impls?

[jonmeow]

Summary of issue:

Asked by @zygoloid at https://github.com/carbon-language/carbon-lang/pull/2287/files/47e08ca918ded47684369e64addf2c42f7e07095#r1015980990, filing on his behalf:

impls seem like a much more complicated case, because they don't seem to have "one true home" unlike the other kinds of entities you mentioned above.

It's not obvious to me when lookup within an impl or impl member would look into a class. Does this depend on whether the impl is internal / external, or on where the definition of the impl appears?

Details:

0. Internal impl defined in class (current example).

1. Internal impl declared in class and defined out of class.

class S1 {
  impl as TotalOrder;
  fn LessHelper(...);
}
impl S1 as TotalOrder {
  fn TotalLess[me: Self](right: Self) -> bool;
}
fn (S1 as TotalOrder).TotalLess[me: Self](right: Self) -> bool {
  // can use LessHelper unqualified?
}

2. External impl declared in class and defined out of class.

class S2 {
  external impl as TotalOrder;
  fn LessHelper(...);
}
external impl S2 as TotalOrder {
  fn TotalLess[me: Self](right: Self) -> bool;
}
fn (S2 as TotalOrder).TotalLess[me: Self](right: Self) -> bool {
  // can use LessHelper unqualified?
}

3. External impl defined before class and redeclared in class.

external impl S3 as TotalOrder {
  fn TotalLess[me: Self](right: Self) -> bool;
}
class S3 {
  external impl as TotalOrder;
  fn LessHelper(...);
}
fn (S3 as TotalOrder).TotalLess[me: Self](right: Self) -> bool {
  // can use LessHelper unqualified?
}

4. External impl defined outside class and not redeclared in class.

external impl S4 as TotalOrder {
  fn TotalLess[me: Self](right: Self) -> bool;
}
class S4 {
  external impl as TotalOrder;
  fn LessHelper(...);
}
fn (S4 as TotalOrder).TotalLess[me: Self](right: Self) -> bool {
  // can use LessHelper unqualified?
}

If we want (0) to find LessHelper and (4) to not find it, where do we draw the line between them? (Another example that didn't fit on the above scale: an external impl that's nonetheless defined in the class.)

A related example:

class X {
  fn F();
  external impl i32 as FriendsWith(X) {
    // Presumably OK.
    fn G() { F(); }
    fn H();
  }
}
fn (i32 as FriendsWith(X)).H() {
  // Also OK?
  F();
}

One possible general rule would be that a definition can see all the names that were in scope in any declaration (excluding those following the definition). Though that could be odd if there is more than one declaration of an entity:

class A;
class B {
  external impl A as ImplicitAs(B);
  fn F();
}
class A {
  // Not clear whether it's valid to forward-declare an impl twice like this.
  external impl A as ImplicitAs(B);
  fn G();
}
external impl A as ImplicitAs(B) {
  // Not clear what `Self` would mean here. Ambiguous?
  fn Convert[me: A]() -> B {
    // Are both of these valid, naming `A.F` and `B.G`?
    F();
    G();
  }
}

Any other information that you want to share?

No response

[jonmeow]

Actually, I should note, https://github.com/carbon-language/carbon-lang/blob/trunk/docs/design/generics/details.md doesn't seem to define rules for out-of-line definitions of impl or its parts. As a consequence, it may be necessary to also decide that forward declarations are allowed for zygoloid's examples (which I'm just mentioned so that it's explicit).

[josh11b]

Note the example for case 0, copied out of #2287 is (updating String.TotalOrder to (String as TotalOrder)):

class String {
  impl as TotalOrder {
    fn TotalLess[me: Self](right: Self) -> bool { ... }
  }
  fn LessHelper(v: i32, v: i32) -> bool
  var v: i32;
}
fn (String as TotalOrder).TotalLess[me: Self](right: Self) -> bool {
  // Does unqualified lookup into TotalOrder then String, finding
  // String.LessHelper?
  return LessHelper(me.v, right.v);
}

[josh11b]

I believe the current rule (in both the design and implemented in Explorer) is that in the scope of [external] impl A as B { ... }, Self means A. This is independent of the scope that impl is declared in except when A is omitted, in which case Self means whatever it means in the enclosing scope.

We currently limit to one forward declaration of an impl, if you ignore match_first blocks, which I think can safely be ignored for these purposes since they should always be at file scope and never should introduce new names.

There are rules for forward declaring and then later defining impls in https://github.com/carbon-language/carbon-lang/blob/trunk/docs/design/generics/details.md#declaring-implementations , but no way to define members of an impl out of line. Is there a definite need for defining individual functions of an impl out-of-line, or is that something we can postpone?

Should we use the same rule for accessing private members as allowing unqualified lookup to find members of the class? It would expect that an external impl that is not mentioned in a class definition to not have access to any private members of the class, beyond friendship. I would expect that an impl (external or not) fully defined in the class' scope to have access to private members. I don't know how I feel about an impl declared in class scope but defined outside, but I would lean toward giving those access to private members.

[zygoloid]

I think the rule that seems most appealing to me is that lookup for a name appearing in an out-of-line definition of a member of X (where X is a class, interface, impl, adapter, ...) always looks in the same places as for a name appearing in the definition of X. So:

interface Iface { fn G(); }
class A {
  fn F();
  impl as Iface {
    fn G();
    // #1
  }
}
// Out-of-line definition of impl member `G`.
fn (A as Iface).G() {
  // OK, looks for `F` in the same way that we'd look for `F`
  // if it appeared at #1. Finds `A.F`.
  F();
}

but

interface Iface { fn G(); }
class B {
  fn F();
  impl as Iface;
}
// This is not an out-of-line definition of a member.
impl as Iface {
  fn G();
  // #2
}
// Out-of-line definition of impl member `G`.
fn (B as Iface).G() {
  // Error, looks for `F` in the same way that we'd look for `F`
  // if it appeared at #2. Finds nothing.
  F();
}

Conversely:

class C {
  fn F();
  class D;
  // #3
}
// Out-of-line definition of class member `D`.
class C.D {
  fn G();
  // #4
}
// Out-of-line definition of class member `G`.
fn C.D.G() {
  // OK, looks for `F` in the same way that we'd look for `F`
  // if it appeared at #4. That looks for `F` in the same way we'd
  // look for `F` if it appeared at #3. That finds `C.F`.
  F();
}

[josh11b]

@zygoloid I'm fine with your resolution, but I think I would prefer the 2nd example to work more like the 3rd. I'm worried that the distinction between those examples is too subtle and acknowledging impl as Iface; in the definition of class B should be sufficient to give the implementation of Iface for B access to B.