IndexInvalidation.md

Index Invalidation Rules in the Swift Standard Library

Points to consider

(1) Collections can be implemented as value types or a reference types.

(2) Copying an instance of a value type, or copying a reference has well-defined semantics built into the language and is not controllable by the user code.

Consequence: value-typed collections in Swift have to use copy-on-write for
data stored out-of-line in reference-typed buffers.

(3) We want to be able to pass/return a Collection along with its indices in a safe manner.

In Swift, unlike C++, indices are not sufficient to access collection data;
one needs an index and a collection.  Thus, merely passing a collection by
value to a function should not invalidate indices.

General principles

In C++, validity of an iterator is a property of the iterator itself, since iterators can be dereferenced to access collection elements.

In Swift, in order to access a collection element designated by an index, subscript operator is applied to the collection, C[I]. Thus, index is valid or not only in context of a certain collection instance at a certain point of program execution. A given index can be valid for zero, one or more than one collection instance at the same time.

An index that is valid for a certain collection designates an element of that collection or represents a one-past-end index.

Operations that access collection elements require valid indexes (this includes accessing using the subscript operator, slicing, swapping elements, removing elements etc.)

Using an invalid index to access elements of a collection leads to unspecified memory-safe behavior. (Possibilities include trapping, performing the operation on an arbitrary element of this or any other collection etc.) Concrete collection types can specify behavior; implementations are advised to perform a trap.

An arbitrary index instance is not valid for an arbitrary collection instance.

The following points apply to all collections, defined in the library or by the user:

(1) Indices obtained from a collection C via C.startIndex, C.endIndex and other collection-specific APIs returning indices, are valid for C.

(2) If an index I is valid for a collection C, a copy of I is valid for C.

(3) If an index I is valid for a collection C, indices obtained from I via I.successor(), I.predecessor(), and other index-specific APIs, are valid for C. FIXME: disallow startIndex.predecessor(), endIndex.successor()

(4) Indices of collections and slices freely interoperate.

If an index `I` is valid for a collection `C`, it is also valid for
slices of `C`, provided that `I` was in the bounds that were passed to
the slicing subscript.

If an index `I` is valid for a slice obtained from a collection `C`, it
is also valid for `C` itself.

(5) If an index I is valid for a collection C, it is also valid for a copy of C.

(6) If an index I is valid for a collection C, it continues to be valid after a call to a non-mutating method on C.

(7) Calling a non-mutating method on a collection instance does not invalidate any indexes.

(8) Indices behave as if they are composites of offsets in the underlying data structure. For example:

- an index into a set backed by a hash table with open addressing is the
  number of the bucket where the element is stored;

- an index into a collection backed by a tree is a sequence of integers
  that describe the path from the root of the tree to the leaf node;

- an index into a lazy flatMap collection consists of a pair of indices, an
  index into the base collection that is being mapped, and the index into
  the result of mapping the element designated by the first index.

This rule does not imply that indices should be cheap to convert to actual
integers.  The offsets for consecutive elements could be non-consecutive
(e.g., in a hash table with open addressing), or consist of multiple
offsets so that the conversion to an integer is non-trivial (e.g., in a
tree).

Note that this rule, like all other rules, is an "as if" rule.  As long as
the resulting semantics match what the rules dictate, the actual
implementation can be anything.

Rationale and discussion:

- This rule is mostly motivated by its consequences, in particular, being
  able to mutate an element of a collection without changing the
  collection's structure, and, thus, without invalidating indices.

- Replacing a collection element has runtime complexity O(1) and is not
  considered a structural mutation.  Therefore, there seems to be no reason
  for a collection model would need to invalidate indices from the
  implementation point of view.

- Iterating over a collection and performing mutations in place is a common
  pattern that Swift's collection library needs to support.  If replacing
  individual collection elements would invalidate indices, many common
  algorithms (like sorting) wouldn't be implementable directly with
  indices; the code would need to maintain its own shadow indices, for
  example, plain integers, that are not invalidated by mutations.

Consequences:

• The setter of MutableCollection.subscript(_: Index) does not invalidate any indices. Indices are composites of offsets, so replacing the value does not change the shape of the data structure and preserves offsets.

• A value type mutable linked list cannot conform to MutableCollectionType. An index for a linked list has to be implemented as a pointer to the list node to provide O(1) element access. Mutating an element of a non-uniquely referenced linked list will create a copy of the nodes that comprise the list. Indices obtained before the copy was made would point to the old nodes and wouldn't be valid for the copy of the list.

  It is still valid to have a value type linked list conform to CollectionType, or to have a reference type mutable linked list conform to MutableCollection.

The following points apply to all collections by default, but specific collection implementations can be less strict:

(1) A call to a mutating method on a collection instance, except the setter of MutableCollection.subscript(_: Index), invalidates all indices for that collection instance.

Consequences:

• Passing a collection as an inout argument invalidates all indexes for that collection instance, unless the function explicitly documents stronger guarantees. (The function can call mutating methods on an inout argument or completely replace it.)

  • Swift.swap() does not invalidate any indexes.

Additional guarantees for Swift.Array, Swift.ContiguousArray, Swift.ArraySlice

Valid array indexes can be created without using Array APIs. Array indexes are plain integers. Integers that are dynamically in the range 0..<A.count are valid indexes for the array or slice A. It does not matter if an index was obtained from the collection instance, or derived from input or unrelated data.

Traps are guaranteed. Using an invalid index to designate elements of an array or an array slice is guaranteed to perform a trap.

Additional guarantees for Swift.Dictionary

Insertion into a Dictionary invalidates indexes only on a rehash. If a Dictionary has enough free buckets (guaranteed by calling an initializer or reserving space), then inserting elements does not invalidate indexes.

Note: unlike C++'s std::unordered_map, removing elements from a Dictionary invalidates indexes.