carbon-lang/docs/design/expressions/indexing.md

Indexing

Table of contents

• Overview
• Details
  • Examples
• Open questions
  • Tuple indexing
• Alternatives considered
• References

Overview

Carbon supports indexing using the conventional a[i] subscript syntax. When a is an l-value, the result of subscripting is always an l-value, but when a is an r-value, the result can be an l-value or an r-value, depending on which interface the type implements:

• If subscripting an r-value produces an r-value result, as with an array, the type should implement IndexWith.
• If subscripting an r-value produces an l-value result, 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.

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) {
  impl as 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 value 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 an l-value, 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 external 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) {
  external 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) {
  external 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

• Different subscripting syntaxes
• Multiple indices
• Read-only subscripting
• Rvalue-only subscripting
• Map-like subscripting

References

• Proposal #2274: Subscript syntax and semantics