[SR-3631] Introduce ContiguouslyStored protocol and kill ArraySlice type

[dabrahams]

Previous ID	SR-3631
Radar	rdar://problem/30541077
Original Reporter	@dabrahams
Type	Improvement

Attachment: Download

Additional Detail from JIRA

Votes	0
Component/s	Standard Library
Labels	Improvement, AffectsABI, StarterProposal
Assignee	None
Priority	Medium

md5: 0b822da3966dafcaf6527038fc805b6a

relates to:

• SR-3633 Support for segmented data structures
• SR-3087 No way to arbitrarily initialise an Array's storage

Issue Description:

Sketch:

protocol ContiguouslyStored : RandomAccessCollection {
  func withUnsafeBufferPointer<R>(...) -> R
  mutating func withUnsafeMutableBufferPointer<R>(...) -> R
}

extension Slice : ContiguouslyStored where Base : ContiguouslyStored {
  func withUnsafeBufferPointer<R>(...) -> R { ... }
  mutating func withUnsafeMutableBufferPointer<R>(...) -> R { ... }
}

typealias ArraySlice<T> = Slice<Array<T>>

(This is related to https://bugs.swift.org/browse/SR-3633)

[swift-ci]

Comment by Daryle Walker (JIRA)

Whether or not a type uses contiguous storage has nothing to do with how its elements are accessed by normal developers. For instance, a multi-dimensional array would have packed storage, but can't qualify for Sequence or its derivatives (since it's a non-linear container). So ContiguouslyStored should be a base protocol, and not inherit from any of the collection protocols.

As of this writing, I recently posted the same idea. But I had a ContiguousBlock protocol for .withUnsafeBufferPointer (with an Element associated type) for immutable visitation, and a derived MutableContiguousBlock adding .withUnsafeMutableBufferPointer for mutable visitation.

[swift-ci]

Comment by Daryle Walker (JIRA)

I just attached my version of this idea.

[dabrahams]

CTMacUser (JIRA User) I disagree. If there is storage for a contiguous array of elements, there is inherently a random-access collection. A dense multi-dimensional array should not be-a RandomAccessCollection of all its elements, but it could have such a collection, and probably does. At the same level of abstraction where that collection would be exposed, so too could unsafe access to its contiguous storage be exposed.

[swift-ci]

Comment by Daryle Walker (JIRA)

And the implication from contiguous arrays of elements to random-access collections is already present; Unsafe[Mutable]BufferPointer IS-A RandomAccessCollection already. Copying that connection up to the Contiguous* protocol is an over-specification, the two methods look self-contained and don't need anything from the Collection interface.

[dabrahams]

It's not overspecification; it's good old-fashioned concept clustering. We don't make every concept minimal for good reasons.

[dabrahams]

I should add that there are no interesting generic algorithms that can operate on a "has contiguous memory" protocol without further semantic constraints. An Int has contiguous memory; what are you going to do with it? Now if you know the type has the semantics of a collection and the contiguous memory is expressed as its elements, a generic algorithm can meaningfully take advantage of that.

[swift-ci]

Comment by Daryle Walker (JIRA)

Unsafe[Mutable]BufferPointer already provides both contiguous memory and collection semantics. The generic algorithm can be called within withUnsafe[Mutable]BufferPointer; that's the reason for their existence, after all. Adding Collection to Contiguous* just adds a second path for the same concept.

Side Note: I was just pondering why we don't replace these methods with two properties. But that wouldn't be compatible with the array changing size between calls. The current function-based interface avoids us making the user invalidate any cached copies of the buffers. I know some interfaces have "lazy" variants; I don't know enough about how lazy evaluation works to know if that technique could help making this interface property-based instead.

[dabrahams]

1. The point is that algorithms that are sure of themselves should be able to (generically) get an unsafe buffer to any contiguously stored collection. That collection should not necessarily be forced to expose an unsafe primary interface to all users.

2. That's not why they aren't properties' it has to do with being able to guarantee the lifetime of the underlying storage

[airspeedswift]

This kind of more in depth conversation is better had on he evolution list rather than on this Jira via comments. This jira will become a proposal pitch soon at which point we can have this debate there.

[airspeedswift]

@swift-ci create

[dabrahams]

Some parts of this story have been coded up and at least compile:

https://github.com/apple/swift/blob/unicode-rethink/stdlib/public/core/ContiguouslyStored.swift
https://github.com/apple/swift/blob/unicode-rethink/stdlib/public/core/Collection.swift#L657
https://github.com/apple/swift/blob/unicode-rethink/stdlib/public/core/MutableCollection.swift#L333

But they should probably be extended to work on Sequence and not just Collection

[karwa]

Do you imagine UnsafeRawBufferPointer would also conform to that protocol, vending a typed buffer of UInt8s?

At the memory-binding level it may be false, but at the Collection level, for generic algorithms, it's sometimes useful to think of a raw-buffer simply as some contiguously-stored bytes (and since there is no Byte type, that means UInt8s).

For example, let's say I have a simple slicing structure which buffers some streaming data and queries a predicate when to break. It's nice if I can handle generic data-frames which are contiguous collections of T, handling raw-byte streaming and buffering as well as typed buffers with the same implementation (the reason it has to be contiguous is so that we can pass-through slices that are entirely contained within the frame without copying - could also be solved in other ways, I suppose...).

Additionally, it would be nice if we could implement Sequence's hidden "_copyContents" optimisations using this, so any 3rd-party Sequence which declares that it is contiguously-stored automatically gets those optimisations when copying its contents in to an Array or buffer.

[glessard]

`ContiguouslyStored` was merged in #21092
`ArraySlice` seems likely to stick around. Should this be closed?