Notional bundles

[kyouko-taiga]

An interesting problem came up recently when I tried to identify the cause of a bug in name resolution. Consider the following program:

type A<T>: Deinitializable { public memberwise init }
extension A {
  public subscript (n: Int): Int { 1 }
}
extension A {
  public subscript (n: Int): Int { inout { var x = 1; yield &x } }
}
public fun main() {
  let aa = A<Int>()
  let xx = aa[n: 1] // error:  ambiguous use of 'aa'
}

This program will currently report an ambiguity error in the main function, complaining that there are two valid candidates for the subscript to apply.

There are good reasons to define the different variants of a subscript in different extensions. For example, one may want to write a conditional conformance to MutableCollection for a type that unconditionally conforms to Collection. The former trait requires an inout subscript while the latter only requires a let variant. So we may be tempted to write:

conformance A: Collection {
  public subscript (_ p: Position): Element { ... }
}
conformance A: MutableCollection where T: Movable {
  public subscript (_ p: Position): Element { inout { ... } }
}

Note that the same arguments can be applied to method bundles, not only subscripts.

Name resolution normally expects that all variants are gather in the same bundle declaration. That way, it can bind a name to that bundle and delay the selection of a particular variant until after we've gather enough flow-sensitive information (typically during IR lowering or analysis) to make an informed decision. The problem in the above examples is that name resolution is forced to make a choice before this information has been gathered. Relying on the presence of a mutation marker is not good enough because it wouldn't help us distinguish between let and sink or set and inout variants.

A better approach to solve this problem is to assume the existence of a "notional" bundle that gathers all the variant definitions, no matter where they are declared. This way, name resolution could bind names to this notional bundle and let a later phase of the compiler decide which variant must be used, as with regular bundles. One challenge with this approach is to determine how variants should be gathered.

I note that this issue is revealing a weakness in the design of bundles. One of the original goals was precisely to make this determination obvious, by gathering related definitions under the same syntactic element. One may therefore question the purpose of a bundle if we need another procedure to gather related definitions anyway.

As @dabrahams pointed out on Slack, there are likely two ways to identify related variants:

1. implicity, based on their signature
2. explicitly, using some annotation in the augmenting bundle (e.g., the in the declaration of A's conformance to MutableCollection in the above example).

One complication with either approach is about the constraints under which different variants are defined. If those constraints do not match, the selection of a variant later on may require another type checking pass to determine whether a particular choice is well-typed. For example:

type B {} // Note: B is not `Movable`
public fun main() {
  var a: A<B>()
  let p = a.start_position()
  print(a[p]) // OK
  &a[p] = 1 // should be ill-typed
}

A use of inout on A<B> variant is ill-typed because it does not satisfy the condition of the extension in which this variant is defined. The difficulty here is to decide what name resolution is supposed to do. If it conservatively requires all possible constraints of the notional bundle, then it will incorrectly make the use of the let variant illegal in the above example. But if those constraints are not upheld, the compiler will incorrectly accept the illegal use of the inout variant.

[dabrahams]

One of the original goals was precisely to make this determination obvious, by gathering related definitions under the same syntactic element. One may therefore question the purpose of a bundle if we need another procedure to gather related definitions anyway.

The point of the bundle is to create one entity in the language, not necessarily to have one syntactic mechanism to do so. Does the documentation for one access apply to the other one, for example?

[kyouko-taiga]

not necessarily to have one syntactic mechanism to do so.

We were against using overloading to form the bundle only notionally in the case all the bundled entities are declared in the same scope. The fact that there is only one syntactic construct is significant in my opinion. It makes it easier to read (for the human and the machine) and, it dramatically simplifies overload resolution.

Does the documentation for one access apply to the other one, for example?

That may be a question for @tothambrus11 but it could be. We'd need help from the type checker to determine the relationship between variants.

[dabrahams]

It makes it easier to read (for the human and the machine) and, it dramatically simplifies overload resolution.

I don't think this is right. It is precisely the second syntax, the one that lets us definitively identify members of a bundle that are not proximate in the source, that reduces overload resolution.

Yes, it is a significant burden to have a second syntax. My only point is: if we happen to need a second syntax, that doesn't entirely undermine the value of bundles, which is “one may question the purpose…” seems to imply.

Does the documentation for one access apply to the other one, for example?

That may be a question for @tothambrus11 but it could be. We'd need help from the type checker to determine the relationship between variants.

You might be missing my point. Clearly we want the same documentation to apply to all parts of a bundle, no matter where they are written (for presentation purposes the doc webpage might actually say "extends BaseTrait.subscript with set and inout accesses” rather than restating it… maybe). But the point is you can't do that unless the parts are associated as part of one entity, and not just overloads. A similar question: when you look at a list of the members of X do you see two subscripts or one? You want to see one. We may want variant selection in a bundle to work differently from overload resolution. If so, it's important to have an actual bundle, and we need a second syntax despite the burdens.