How ArraySlice in Swift work internally?

Question

I have already read multiple posts and articles about how ArraySlice works with Array in `Swift.

But, what I couldn't find is how it works internally? What does ArraySlice are Views onto Arrays exactly mean?

var arr = [1, 2, 3, 4, 5]
let slice = arr[2...4]

arr.remove(at: 2)
print(slice.startIndex) //2
print(slice.endIndex)   //5
slice[slice.startIndex] //3

In the code above, I've removed element at index-2 (i.e 3) from arr. Index-2 is the startIndex of slice as well. When I print slice[slice.startIndex] it still prints 3.

Since no extra storage is created for ArraySlice, then how come any changes in Array doesn't reflect in ArraySlice?

The articles/ posts can be found here:

https://dzone.com/articles/arrayslice-in-swift

https://marcosantadev.com/arrayslice-in-swift/

Answer 1

Both Array and ArraySlice are value types, which means that after

var array = [0, 1, 2, 3, 4, 5]
var slice = array[0..<2]

array and slice are independent values, and mutating one does not affect the other:

print(slice) // [0, 1]
array.remove(at: 0)
print(slice) // [0, 1]

How that is achieved is an implementation detail of the Swift standard library, but one can inspect the source code to get some ideas: At Array.swift#L1241 we find the implementation of Array.remove(at:):

  public mutating func remove(at index: Int) -> Element {
    _precondition(index < endIndex, "Index out of range")
    _precondition(index >= startIndex, "Index out of range")
    _makeUniqueAndReserveCapacityIfNotUnique()

   // ...
  }

which uses

  @inlinable
  @_semantics("array.make_mutable")
  internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
    if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {
      _copyToNewBuffer(oldCount: _buffer.count)
    }
  }

Following that trail, we find at ArrayBuffer.swift#L107

  /// Returns `true` iff this buffer's storage is uniquely-referenced.
  @inlinable
  internal mutating func isUniquelyReferenced() -> Bool {

    // ...
  }

This isn't the full implementation yet, but (hopefully) already demonstrates that the (mutating) remove(at:) method copies the element storage to a new buffer if is was shared (with another array or an array slice).

We can also verify that by printing the element storage base address:

var array = [0, 1, 2, 3, 4, 5]
var slice = array[0..<2]

array.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101927190
slice.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101927190

array.remove(at: 0)

array.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101b05350
slice.withUnsafeBytes { print($0.baseAddress!) }  // 0x0000000101927190

The same “copy-on-write” technique is used if arrays, dictionaries, or strings are copied, or if String and Substring share storage.

So an array slice shares the element storage with its originating array as long as neither of them is mutated.

That is still a useful feature. Here is a simple example:

let array = [1, 4, 2]
let diffs = zip(array, array[1...]).map(-)
print(diffs) // [-3, 2]

array[1...] is a view/slice of the given array, without actually copying the elements.

A recursive binary search function where slices (of the left or right half) are passed down would be another application.