mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
179 lines
7.7 KiB
Markdown
179 lines
7.7 KiB
Markdown
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.
|
|
|