docs/IndexInvalidation.rst - third_party/swift - Git at Google

 ======================================================
 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.
	======================================================
	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.