[Pitch] OutputSpan

Evolution Pitches
1

We are proposing OutputSpan a new abstraction for initialization of memory, along the lines of Span and MutableSpan. OutputSpan will allow us to replace unsafe in-place initialization API such as Array.init(unsafeUninitializedCapacity:initializingWith:).

OutputSpan & OutputRawSpan

Introduction

Following the introduction of Span and MutableSpan, this proposal adds a general facility for initialization of exclusively-borrowed memory with the OutputSpan and OutputRawSpan types. The memory represented by OutputSpan consists of a number of initialized elements, followed by uninitialized memory. The operations of OutputSpan can change the number of initialized elements in memory, unlike MutableSpan which always represents memory that is initialized.

Motivation

Some standard library container types can delegate initialization of some or all of their storage to user code. Up to now, it has only been possible to do so with explicitly unsafe ways, which have also proven error-prone. The standard library provides this unsafe functionality with the closure-taking initializers Array.init(unsafeUninitializedCapacity:initializingWith:) and String.init(unsafeUninitializedCapacity:initializingUTF8With:).

These functions have a few different drawbacks, most prominently their reliance on unsafe types, which makes them unpalatable in security-conscious environments. We continue addressing these issues with OutputSpan and OutputRawSpan, new non-copyable and non-escapable types that manage initialization of typed and untyped memory.

In addition to the new types, we will propose adding new API for some standard library types to take advantage of OutputSpan and OutputRawSpan, and improve upon the Array and String initializers mentioned above.

Proposed solution

OutputSpan

OutputSpan allows delegating the initialization of a type's memory, by providing access to an exclusively-borrowed view of a range of contiguous memory. OutputSpan's contiguous memory consists of a prefix of initialized memory, followed by a suffix of uninitialized memory. Like MutableSpan, OutputSpan relies on two guarantees: (a) that it has exclusive access to the range of memory it represents, and (b) that the memory locations it represents will remain valid for the duration of the access. These guarantee data race safety and temporal safety. OutputSpan performs bounds-checking on every access to preserve spatial safety.

An OutputSpan provided by a container represents a mutation of that container, and is therefore an exclusive access.

OutputRawSpan

OutputRawSpan allows delegating the initialization of heterogeneously-typed memory, such as memory being prepared by an encoder. It makes the same safety guarantees as OutputSpan.

Extensions to standard library types

The standard library will provide new container initializers that delegate to an OutputSpan. Delegated initialization generally requires a container to perform some operations after the initialization has happened. In the case of Array this is simply noting the number of initialized elements; in the case of String this consists of validating the input. This post-processing implies the need for a scope, and we believe that scope is best represented by a closure. The Array initializer will be as follows:

extension Array {
  public init<E: Error>(
    capacity: Int,
    initializingWith: (_ span: inout OutputSpan<Element>) throws(E) -> Void
  ) throws(E)
}

We will also extend String, UnicodeScalarView and InlineArray with similar initializers, and add append-in-place operations where appropriate.

Please see the full proposal for the detailed design.

11 Likes
2

How does an OutputSpan differ from a MutableSpan? I was surprised not to see a comparison between the two in the pitch.

1 Like
3

Good question, I should add more about this in the introduction.

An OutputSpan is not fully initialized. It has count initialized elements at the beginning (where count is possibly zero,) followed by uninitialized memory. The operations of OutputSpan center around changing the number of initialized elements in the memory it represents.

4

If this is what differentiates an OutputSpan from a MutableSpan, does this make OutputSpan a superset of MutableSpan? Would data types like Array be expected to vend both OutputSpan and MutableSpan getters to support operations like truncation?

5

Because OutputSpan changes the number of elements in memory, mutations through it require a cleanup step. This is best represented by a closure-taking function. The alternative would be to write a specific OutputSpan-like type for each type that wants to vend it, because the cleanup is type-specific.

1 Like
6

How are you supposed to differentiate between these two overloads when using the trailing closure syntax?

extension String {
  public init<E: Error>(
    utf8Capacity: Int,
    initializingUTF8With initializer: (inout OutputSpan<UTF8.CodeUnit>) throws(E) -> Void
  )

  public init<E: Error>?(
    utf8Capacity: Int,
    initializingValidUTF8With initializer: (inout OutputSpan<UTF8.CodeUnit>) throws(E) -> Void
  ) throws(E)
}
7

This looks fantastic! I'm particularly excited to see the Array.append(addingCapacity:...) method, as that's something that we decided not to include when adding init(unsafeUninitializedCapacity:...). It's awesome that we can have fully safe versions of these APIs now. :clap: :clap:

5 Likes
8

I hand-rolled one of these for another project and I'd be happy to let it go.

Some questions:

  • Should append(fromContentsOf:) be append(contentsOf:) to mirror the Array method?
  • What happens if there are too many elements in the sequence/collection/iterator that you append from?
  • You say that the user of OutputSpan must call finalize. We don't have linear types, so we can't verify that. What happens if finalize isn't called?
  • As we discuss UTF8Span, should we also have a UTF8OutputSpan? Are there memory safety implications to the initializingValidUTF8With variant not receiving valid UTF-8?
  • Are there post-conditions on InlineArray's OutputSpan initializer? Seems like it should be an error to not fill it to capacity?
  • AFAIK, Swift does not commit to the order of fields in structs, even when they are BitwiseCopyable. As we have OutputRawSpan methods to (essentially) memcpy a BitwiseCopyable thing into the span, are we looking to change that stance? If not, are we leaving a can of worm in plain sight to be opened?
2 Likes
9

I used the nomenclature from UnsafeMutableBufferPointer for this one, as I had for the update() methods on MutableSpan. contentsOf does seem slightly better.

The functions trap. If there is not enough space, the user should explicitly trim the input in some way (e.g. by using prefix())

I don't think so. The initializers proposed here repair or validate the input depending on the variant used. I'll add doc-comments to the initializers.

Yes! The post-condition is that the OutputSpan's count must equal the InlineArray's count.

Indeed. It seems like the alternative to allowing outputting BitwiseCopyable fields is to restrict the vocabulary to a battery of functions storing specific types such as store(_: Int16). We haven't done that before -- is there a good reason to start now?

10 
  /// Initialize this span's suffix by moving every element from the source.
  @lifetime(self: copy self)
  public mutating func moveAppend(
    fromContentsOf source: inout OutputSpan<Element>
  )

I don't understand the contract of this family of functions, but this one in particular — what happens if the size of source exceeds the capacity of self? There's no way to remove a prefix of source and shuffle the remaining elements down, so it seems like it must crash? If that's the case, that should be clearly documented.

11

Yes, these functions trap when there is not enough space. I will try to make this clearer in the section's intro paragraph.

1 Like
12

This makes it feel like OutputSpan is append-only. Is there potentially a use case for memory that may be initialized in a different order (i.e. arbitrary or reverse)? One scenario off the top of my head is initializing a flattened-tree data structure, where child nodes may be indexed relative to their parent nodes but not immediately after (and perhaps initializing the remaining regions to "nil" later?). This begs a few questions:

  • Should the name of this type be more specialized (something like AppendOnlySpan?)
  • Is there a way we could extend this type to support random-access initialization while maintaining ABI compatibility?
  • Should we implement support for random-access initialization out-of-the gate?
4 Likes
13

Random-access initialization is mentioned in "future directions". It's clear that most applications are for front-to-back initialization, and that use case has a very low overhead. Random-access initialization, requiring extra runtime bookkeeping, is under consideration for a later proposal.

We believe this is the most important variant of OutputSpan; others should have less attractive names.

A safe abstraction for random-access initialization is not lightweight; it must be another type, and it must be less attractive to use because of its intrinsic overhead.

This proposal focuses on the simpler, higher-impact use case.

3 Likes
14

IIRC, existing collections have a trapping removeLast() and an optional-returning popLast(). Why deviate from that precedent here?

This looks like you’re supposed to be able to get an OutputSpan from an already-initialized container and consume it, emptying or destroying it in the process. Are you proposing any APIs which actually let you do that? Do you anticipate that such APIs will be added later?

(I could imagine, for instance, a consuming method on InlineArray which takes a closure that can empty elements from an OutputSpan of its elements and then destroys any that remain after the closure returns.)

How much thought have you put into modeling unused capacity at both ends of the span, and adding prepend(_:) and removeFirst() primitives? I ask because not being able to consume from the front would make it very difficult to process elements in-order; that doesn’t matter for the initialization case, but for anything else it seems like a real obstacle. It also seems like a much easier thing to design than the generalized bitmap-tracking direction.

3 Likes
15

Clearly I got this one wrong in a renaming. Thanks for the catch!

That is indeed the main application that has come to mind with the current set of types. In building up the primitives that will allow us to have containers of non-copyable elements, operations to empty them are important, and this is one such operation.

We have discussed a variant for deinitializing from the front, but none that has unused capacity at both ends. The main use cases have their unused capacity at the end (such as Array, String, Data), and if we allowed unused capacity at the front the owner would need to move elements around in order to maintain generality.

1 Like
16

I think that is fine. This is still a valuable feature as the layout is stable within a process.
Note that C structs are also BitwiseCopyable which is quite handy for writing them to Metal buffers. Any particular issue you are worried about that?

I have recently build something similar to OutputSpan but with one additional feature: reserving space that I'm promising to fill in later. This looks something like this:

extension RawOutputSpan {
    /// A promise to insert `Data` at a later point in time
    /// - precondition: needs to be consumed by calling `RawOutputSpan.insert(_:at:)` 
    ///   or otherwise crashes at runtime if deinitalized 
    struct InsertionPromise<Data: BitwiseCopyable>: ~Copyable {
        //... 
    }
    /// Reserve space to insert `Data`. It is required to use the returned `InsertionPromise` or
    /// otherwise the program will crash.
    mutating func reserve<Data: BitwiseCopyable>(
        for dataType: Data.Type
    ) -> ReservedToken<Data>
    /// inserts `data` at the previously reserved insert point.
    mutating func insert<Data: BitwiseCopyable>(
        _ data: Data, 
        at insertionIndex: consuming InsertionPromise<Data>
    )
}

InsertionPromise also should really be ~Escapable and have the same lifetime as the RawOutputSpan it is created for. Similar methods on OutputSpan and variants that reserve space for more than one element are useful as well.

My type doesn't support removing elements, just appending (and reserving + insert). I'm currently not sure if this can be implemented safely and efficiently if removes also need to be supported.

1 Like
17

I would imagine that this compacting operation could be built in to finalize(for:)* so that clients wouldn't need to worry about it. In fact, if you only supported pop/removeFirst() (not prepending), you might be able to implement this without significant time or space costs to other OutputSpan clients—removing from the front would bump along the base pointer (and decrease the count and capacity), and then finalizing would determine the element-shifting offset by subtracting the current base pointer from the buffer pointer passed to finalize(for:). (You could still assert that the base pointer is somewhere inside buffer.)

* You could, of course, offer a variant of the method which returns the offset instead of compacting it away for clients which can use it.

1 Like
18

I hand-rolled an OutputSpan in a project that stores pixel data as a repeating sequence of R, G, B, A bytes. Without a guarantee from the language that my struct RGBA would be laid out exactly like that, I opted against writing RGBA values as a unit even though it's BitwiseCopyable.

I think OutputRawSpan as proposed has a good chance of exacerbating reliance on the current field layout because it is very well-suited to reproduce the C pattern of memcpying things to serialize into a buffer. Most developers would probably think I'm being overbearing and would append the RGBA struct to the buffer through its BitwiseCopyable conformance, which corrodes Swift's ability to change layout algorithms. We'll eventually be forced to accept that the way Swift lays out types right now is basically how it's going to have to be forever, at least by default.

3 Likes
19

Or we add an equivalent to Rust's #[repr(C)] to get a stable layout.

1 Like
20

This is a great pitch @glessard, and I'm very excited to see it! With this addition we are getting much closer my grand dream of general purpose serialization mechanisms, which is very exciting.

Based on my read of the proposal, it looks like nothing would prevent us from adding a method like this to Array and friends:

extension Array {
    public mutating func appendUninitialized<ReturnValue, E: Error>(
        uninitializedCapacity: Int,
        initializingWith: (_ span: inout OutputSpan<Element>) throws(E) -> ReturnValue
    ) throws(E) -> ReturnValue
}

This method makes it possible for serializers that are not confident ahead-of-time of how many bytes they are going to need to use to be able to incrementally build their content by repeatedly appending to the existing payload.

Is there anything I'm not aware of that would prevent the implementation of this method? If not, should we add it to this pitch? I'm open to contributing the implementation if we think it's just a matter of resourcing it.

The reason I'd like to add this to Array is to define the de-facto shape for this kind of API. Once that's present, serializing libraries (e.g. swift-protobuf) can always define a protocol that meets their needs, and conform Array to it.

If there's a more complex reason I can't see, should we at least add this to the "Future directions"?

2 Likes