Skip to content

Latest commit

 

History

History
158 lines (124 loc) · 5.69 KB

indexing.md

File metadata and controls

158 lines (124 loc) · 5.69 KB
Raw

Indexing

Table of contents

Overview

Carbon supports indexing using the conventional a[i] subscript syntax. When a is a durable reference expression, the result of subscripting is also a durable reference expression, but when a is a value expression, the result can be a durable reference expression or a value expression, depending on which interface the type implements:

  • If subscripting a value expression produces a value expression, as with an array, the type should implement IndexWith.
  • If subscripting a value expression produces a durable reference expression, as with C++'s std::span, the type should implement IndirectIndexWith.

IndirectIndexWith is a subtype of IndexWith, and subscript expressions are rewritten to method calls on IndirectIndexWith if the type is known to implement that interface, or to method calls on IndexWith otherwise.

IndirectIndexWith provides a final blanket impl of IndexWith, so a type can implement at most one of those two interfaces.

The Addr methods of these interfaces, which are used to form durable reference expressions on indexing, must return a pointer and work similarly to the pointer dereference customization interface. The returned pointer is then dereferenced by the language to form the reference expression referring to the pointed-to object. These methods must return a raw pointer, and do not automatically chain with customized dereference interfaces.

Open question: It's not clear that the lack of chaining is necessary, and it might be more expressive for the pointer type returned by the Addr methods to be an associated type with a default to allow types to produce custom pointer-like types on their indexing boundary and have them still be automatically dereferenced.

Details

A subscript expression has the form "lhs [ index ]". As in C++, this syntax has the same precedence as ., ->, and function calls, and associates left-to-right with all of them.

Its semantics are defined in terms of the following interfaces:

interface IndexWith(SubscriptType:! type) {
  let ElementType:! type;
  fn At[self: Self](subscript: SubscriptType) -> ElementType;
  fn Addr[addr self: Self*](subscript: SubscriptType) -> ElementType*;
}

interface IndirectIndexWith(SubscriptType:! type) {
  require Self impls IndexWith(SubscriptType);
  fn Addr[self: Self](subscript: SubscriptType) -> ElementType*;
}

A subscript expression where lhs has type T and index has type I is rewritten based on the expression category of lhs and whether T is known to implement IndirectIndexWith(I):

  • If T implements IndirectIndexWith(I), the expression is rewritten to "*(( lhs ).(IndirectIndexWith(I).Addr)( index ))".
  • Otherwise, if lhs is a durable reference expression, the expression is rewritten to "*(( lhs ).(IndexWith(I).Addr)( index ))".
  • Otherwise, the expression is rewritten to "( lhs ).(IndexWith(I).At)( index )".

IndirectIndexWith provides a blanket final impl for IndexWith:

final impl forall
    [SubscriptType:! type, T:! IndirectIndexWith(SubscriptType)]
    T as IndexWith(SubscriptType) {
  let ElementType:! type = T.(IndirectIndexWith(SubscriptType)).ElementType;
  fn At[self: Self](subscript: SubscriptType) -> ElementType {
    return *(self.(IndirectIndexWith(SubscriptType).Addr)(index));
  }
  fn Addr[addr self: Self*](subscript: SubscriptType) -> ElementType* {
    return self->(IndirectIndexWith(SubscriptType).Addr)(index);
  }
}

Thus, a type that implements IndirectIndexWith need not, and cannot, provide its own definitions of IndexWith.At and IndexWith.Addr.

Examples

An array type could implement subscripting like so:

class Array(template T:! type) {
  impl as IndexWith(like i64) {
    let ElementType:! type = T;
    fn At[self: Self](subscript: i64) -> T;
    fn Addr[addr self: Self*](subscript: i64) -> T*;
  }
}

And a type such as std::span could look like this:

class Span(T:! type) {
  impl as IndirectIndexWith(like i64) {
    let ElementType:! type = T;
    fn Addr[self: Self](subscript: i64) -> T*;
  }
}

Open questions

Tuple indexing

It is not clear how tuple indexing will be modeled. When indexing a tuple, the index value must be a constant, and the type of the expression can depend on that value, but we don't yet have the tools to express those properties in a Carbon API.

Alternatives considered

References