<commit_before># Accessing an Array's Uninitialized Buffer

* Proposal: [SE-0223](0223-array-uninitialized-initializer.md)
* Author: [<NAME>](https://github.com/natecook1000)
* Review Manager: [<NAME>](https://github.com/jckarter)
* Status: **Active review (August 13...August 19, 2018)**
* Implementation: [apple/swift#17389](https://github.com/apple/swift/pull/17389)
* Bug: [SR-3087](https://bugs.swift.org/browse/SR-3087)

## Introduction

This proposal suggests a new initializer and method for `Array` and `ContiguousArray`
that provide access to an array's uninitialized storage buffer.

Swift-evolution thread: [https://forums.swift.org/t/array-initializer-with-access-to-uninitialized-buffer/13689](https://forums.swift.org/t/array-initializer-with-access-to-uninitialized-buffer/13689)

## Motivation

Some collection operations require working on a fixed-size buffer of uninitialized memory.
For example, one O(*n*) algorithm for performing a stable partition of an array is as follows:

1. Create a new array the same size as the original array.
2. Iterate over the original array,
   copying matching elements to the beginning of the new array
   and non-matching elements to the end.
3. When finished iterating, reverse the slice of non-matching elements.

Unfortunately, the standard library provides no way to create an array
of a particular size without allocating every element,
or to copy elements to the end of an array's buffer
without initializing every preceding element.
Even if we avoid initialization by manually allocating the memory using an `UnsafeMutableBufferPointer`,
there's no way to convert that buffer into an array without copying the contents.
There simply isn't a way to implement this particular algorithm with maximum efficiency in Swift.

We also see this limitation when working with C APIs
that fill a buffer with an unknown number of elements and return the count.
The workarounds are the same as above:
either initialize an array before passing it
or copy the elements from an unsafe mutable buffer into an array after calling.

## Proposed solution

Adding a new `Array` initializer
that lets a program work with an uninitialized buffer,
and a method for accessing an existing array's buffer
of both initialized and uninitialized memory,
would fill in this missing functionality.

The new initializer takes a closure that operates on an `UnsafeMutableBufferPointer`
and an `inout` count of initialized elements.
This closure has access to the uninitialized contents
of the newly created array's storage,
and must set the intialized count of the array before exiting.

```swift
var myArray = Array<Int>(unsafeUninitializedCapacity: 10) { buffer, initializedCount in
    for x in 1..<5 {
        buffer[x] = x
    }
    buffer[0] = 10
    initializedCount = 5
}
// myArray == [10, 1, 2, 3, 4]
```

With this new initializer, it's possible to implement the stable partition
as an extension to the `Collection` protocol, without any unnecessary copies:

```swift
func stablyPartitioned(by belongsInFirstPartition: (Element) throws -> Bool) rethrows -> [Element] {
    return try Array<Element>(unsafeUninitializedCapacity: count) { 
        buffer, initializedCount in
        var low = buffer.baseAddress!
        var high = low + buffer.count
        for element in self {
            if try belongsInFirstPartition(element) {
                low.initialize(to: element)
                low += 1
            } else {
                high -= 1
                high.initialize(to: element)
            }
        }
        
        let highIndex = high - buffer.baseAddress!
        buffer[highIndex...].reverse()
        initializedCount = buffer.count
    }
}
```

## Detailed design

The new initializer and method are added to both `Array` and `ContiguousArray`.

```swift
/// Creates an array with the specified capacity, then calls the given closure
/// with a buffer covering the array's uninitialized memory.
///
/// The closure must set its second parameter to a number `c`, the number 
/// of elements that are initialized. The memory in the range `buffer[0..<c]`  
/// must be initialized at the end of the closure's execution, and the memory 
/// in the range `buffer[c...]` must be uninitialized.
///
/// - Note: While the resulting array may have a capacity larger than the
///   requested amount, the buffer passed to the closure will cover exactly
///   the requested number of elements.
///
/// - Parameters:
///   - unsafeUninitializedCapacity: The number of elements to allocate space
///     for in the new array.
///   - initializer: A closure that initializes elements and sets the count of
///     the new array.
///     - Parameters:
///       - buffer: A buffer covering uninitialized memory with room
///         for the specified number of of elements.
///       - initializedCount: The count of the array's initialized elements.
///         After initializing any elements inside `initializer`, update <commit_msg>Add correct throw-handling to stablePartition example (#899)<commit_after># Accessing an Array's Uninitialized Buffer

* Proposal: [SE-0223](0223-array-uninitialized-initializer.md)
* Author: [<NAME>](https://github.com/natecook1000)
* Review Manager: [<NAME>](https://github.com/jckarter)
* Status: **Active review (August 13...August 19, 2018)**
* Implementation: [apple/swift#17389](https://github.com/apple/swift/pull/17389)
* Bug: [SR-3087](https://bugs.swift.org/browse/SR-3087)

## Introduction

This proposal suggests a new initializer and method for `Array` and `ContiguousArray`
that provide access to an array's uninitialized storage buffer.

Swift-evolution thread: [https://forums.swift.org/t/array-initializer-with-access-to-uninitialized-buffer/13689](https://forums.swift.org/t/array-initializer-with-access-to-uninitialized-buffer/13689)

## Motivation

Some collection operations require working on a fixed-size buffer of uninitialized memory.
For example, one O(*n*) algorithm for performing a stable partition of an array is as follows:

1. Create a new array the same size as the original array.
2. Iterate over the original array,
   copying matching elements to the beginning of the new array
   and non-matching elements to the end.
3. When finished iterating, reverse the slice of non-matching elements.

Unfortunately, the standard library provides no way to create an array
of a particular size without allocating every element,
or to copy elements to the end of an array's buffer
without initializing every preceding element.
Even if we avoid initialization by manually allocating the memory using an `UnsafeMutableBufferPointer`,
there's no way to convert that buffer into an array without copying the contents.
There simply isn't a way to implement this particular algorithm with maximum efficiency in Swift.

We also see this limitation when working with C APIs
that fill a buffer with an unknown number of elements and return the count.
The workarounds are the same as above:
either initialize an array before passing it
or copy the elements from an unsafe mutable buffer into an array after calling.

## Proposed solution

Adding a new `Array` initializer
that lets a program work with an uninitialized buffer,
and a method for accessing an existing array's buffer
of both initialized and uninitialized memory,
would fill in this missing functionality.

The new initializer takes a closure that operates on an `UnsafeMutableBufferPointer`
and an `inout` count of initialized elements.
This closure has access to the uninitialized contents
of the newly created array's storage,
and must set the intialized count of the array before exiting.

```swift
var myArray = Array<Int>(unsafeUninitializedCapacity: 10) { buffer, initializedCount in
    for x in 1..<5 {
        buffer[x] = x
    }
    buffer[0] = 10
    initializedCount = 5
}
// myArray == [10, 1, 2, 3, 4]
```

With this new initializer, it's possible to implement the stable partition
as an extension to the `Collection` protocol, without any unnecessary copies:

```swift
func stablyPartitioned(by belongsInFirstPartition: (Element) throws -> Bool) rethrows -> [Element] {
    return try Array<Element>(unsafeUninitializedCapacity: count) { 
        buffer, initializedCount in
        var low = buffer.baseAddress!
        var high = low + buffer.count
        do {
            for element in self {
                if try belongsInFirstPartition(element) {
                    low.initialize(to: element)
                    low += 1
                } else {
                    high -= 1
                    high.initialize(to: element)
                }
            }
            
            let highIndex = high - buffer.baseAddress!
            buffer[highIndex...].reverse()
            initializedCount = buffer.count
        } catch {
            let lowCount = low - buffer.baseAddress!
            let highCount = (buffer.baseAddress! + buffer.count) - high
            buffer.baseAddress!.deinitialize(count: lowCount)
            high.deinitialize(count: highCount)
            throw error
        }
    }
}
```

## Detailed design

The new initializer and method are added to both `Array` and `ContiguousArray`.

```swift
/// Creates an array with the specified capacity, then calls the given closure
/// with a buffer covering the array's uninitialized memory.
///
/// The closure must set its second parameter to a number `c`, the number 
/// of elements that are initialized. The memory in the range `buffer[0..<c]`  
/// must be initialized at the end of the closure's execution, and the memory 
/// in the range `buffer[c...]` must be uninitialized.
///
/// - Note: While the resulting array may have a capacity larger than the
///   requested amount, the buffer passed to the closure will cover exactly
///   the requested number of elements.
///
/// - Parameters:
///   - unsafeUninitializedCapacity: The number of elements to allocate space
///     for in the new array.
///   - initializer: A closure that initializes elements and sets the count of
///     the new array.
///     - Parameters:
///       - buffer: A buffer covering uninitialized memory with room
///         for the specified number of of elements.
///       - initializedCount: The count of the array's initialized elements.
///         After initializing any elements inside `initializer`, update 
{'fraction_non_alphanumeric': 0.08218385260924085, 'fraction_numerical': 0.013407929005498215, 'mean_word_length': 3.2701812191103787, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 15, 'https://': 12, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1454450', 'n_tokens_mistral': 2774, 'n_tokens_neox': 2599, 'n_words': 1201}