ContiguousArray.swift

public struct ContiguousArray<Element>: _DestructorSafeContainer {
  internal typealias _Buffer = _ContiguousArrayBuffer<Element>
  internal var _buffer: _Buffer

  internal init(_buffer: _Buffer) {
    self._buffer = _buffer
  }
}

extension ContiguousArray: RandomAccessCollection, MutableCollection {
  public typealias Index = Int
  public typealias Indices = Range<Int>
  public typealias Iterator = IndexingIterator<ContiguousArray>

  public var startIndex: Int { return 0 }
  public var endIndex: Int { get { return _getCount() } }

  public func index(after i: Int) -> Int { return i + 1 }
  public func formIndex(after i: inout Int) { i += 1 }
  public func index(before i: Int) -> Int { return i - 1 }
  public func formIndex(before i: inout Int) { i -= 1 }
  public func index(_ i: Int, offsetBy n: Int) -> Int { return i + n }
  public func index( _ i: Int, offsetBy n: Int, limitedBy limit: Int ) -> Int? {
    let l = limit - i
    if n > 0 ? l >= 0 && l < n : l <= 0 && n < l {
      return nil
    }
    return i + n
  }

  public func distance(from start: Int, to end: Int) -> Int {
    return end - start
  }

  public subscript(index: Int) -> Element {
    get {
      let wasNativeTypeChecked = _hoistableIsNativeTypeChecked()
      let token = _checkSubscript(index, wasNativeTypeChecked: wasNativeTypeChecked)
      return _getElement(
        index, wasNativeTypeChecked: wasNativeTypeChecked,
        matchingSubscriptCheck: token)
    }
  }

  public subscript(bounds: Range<Int>) -> ArraySlice<Element> {
    get {
      return ArraySlice(_buffer: _buffer[bounds])
    }
    set(rhs) {
      if self[bounds]._buffer.identity != rhs._buffer.identity
      || bounds != rhs.startIndex..<rhs.endIndex {
        self.replaceSubrange(bounds, with: rhs)
      }
    }
  }
}

extension ContiguousArray {
  public func _hoistableIsNativeTypeChecked() -> Bool {
   return _buffer.arrayPropertyIsNativeTypeChecked
  }

  internal func _getCount() -> Int {
    return _buffer.count
  }

  internal func _getCapacity() -> Int {
    return _buffer.capacity
  }

  internal func _getOwnerWithSemanticLabel_native() -> Builtin.NativeObject {
    return Builtin.unsafeCastToNativeObject(_buffer.nativeOwner)
  }

  internal func _getOwner_native() -> Builtin.NativeObject {
#if _runtime(_ObjC)
    if _isClassOrObjCExistential(Element.self) {
      return _getOwnerWithSemanticLabel_native()
    }
#endif
    return Builtin.unsafeCastToNativeObject(_buffer.owner)
  }

  internal mutating func _makeMutableAndUnique() {
    if _slowPath(!_buffer.isMutableAndUniquelyReferenced()) {
      _buffer = _Buffer(copying: _buffer)
    }
  }

  internal mutating func _makeMutableAndUniqueOrPinned() {
    if _slowPath(!_buffer.isMutableAndUniquelyReferencedOrPinned()) {
      _buffer = _Buffer(copying: _buffer)
    }
  }

  internal func _checkSubscript_native(_ index: Int) {
    _buffer._checkValidSubscript(index)
  }

  public func _checkSubscript(_ index: Int, wasNativeTypeChecked: Bool) -> _DependenceToken {
#if _runtime(_ObjC)
    _buffer._checkValidSubscript(index)
#else
    _buffer._checkValidSubscript(index)
#endif
    return _DependenceToken()
  }

  internal func _checkIndex(_ index: Int) {
    _precondition(index <= endIndex, "ContiguousArray index is out of range")
    _precondition(index >= startIndex, "Negative ContiguousArray index is out of range")
  }

  public func _getElement(_ index: Int, wasNativeTypeChecked : Bool, matchingSubscriptCheck: _DependenceToken) -> Element {
    return _buffer.getElement(index)
  }

  internal func _getElementAddress(_ index: Int) -> UnsafeMutablePointer<Element> {
    return _buffer.subscriptBaseAddress + index
  }
}

extension ContiguousArray : ExpressibleByArrayLiteral {
  public init(arrayLiteral elements: Element...) {
    self.init(_buffer: ContiguousArray(elements)._buffer)
  }
}

extension ContiguousArray : RangeReplaceableCollection, ArrayProtocol {
  public init() {
    _buffer = _Buffer()
  }

  public init<S : Sequence>(_ s: S) where S.Element == Element {
    self = ContiguousArray(
      _buffer: _Buffer(_buffer: s._copyToContiguousArray()._buffer, shiftedToStartIndex: 0)
    )
  }
  
  public init(repeating repeatedValue: Element, count: Int) {
    var p: UnsafeMutablePointer<Element>
    (self, p) = ContiguousArray._allocateUninitialized(count)
    for _ in 0..<count {
      p.initialize(to: repeatedValue)
      p += 1
    }
  }

  internal static func _allocateBufferUninitialized(minimumCapacity: Int) -> _Buffer {
    let newBuffer = _ContiguousArrayBuffer<Element>(_uninitializedCount: 0, minimumCapacity: minimumCapacity)
    return _Buffer(_buffer: newBuffer, shiftedToStartIndex: 0)
  }

  internal init(_uninitializedCount count: Int) {
    _buffer = _Buffer()
    if count > 0 {
      _buffer = ContiguousArray._allocateBufferUninitialized(minimumCapacity: count)
      _buffer.count = count
    }
  }

  internal static func _allocateUninitialized(_ count: Int) -> (ContiguousArray, UnsafeMutablePointer<Element>) {
    let result = ContiguousArray(_uninitializedCount: count)
    return (result, result._buffer.firstElementAddress)
  }

  public var count: Int { return _getCount() }
  public var capacity: Int { return _getCapacity() }
  
  var _owner: AnyObject? { return _buffer.owner }

  public var _baseAddressIfContiguous: UnsafeMutablePointer<Element>? {
    get { return _buffer.firstElementAddressIfContiguous }
  }

  internal var _baseAddress: UnsafeMutablePointer<Element> {
    return _buffer.firstElementAddress
  }

  public mutating func reserveCapacity(_ minimumCapacity: Int) {
    if _buffer.requestUniqueMutableBackingBuffer(minimumCapacity: minimumCapacity) == nil {
      let newBuffer = _ContiguousArrayBuffer<Element>(_uninitializedCount: count, minimumCapacity: minimumCapacity)

      _buffer._copyContents(
        subRange: _buffer.indices,
        initializing: newBuffer.firstElementAddress)
      _buffer = _Buffer(_buffer: newBuffer, shiftedToStartIndex: _buffer.startIndex)
    }
  }

  internal mutating func _copyToNewBuffer(oldCount: Int) {
    let newCount = oldCount + 1
    var newBuffer = _buffer._forceCreateUniqueMutableBuffer(countForNewBuffer: oldCount, minNewCapacity: newCount)
    _buffer._arrayOutOfPlaceUpdate(&newBuffer, oldCount, 0, _IgnorePointer())
  }

  internal mutating func _makeUniqueAndReserveCapacityIfNotUnique() {
    if !_buffer.isMutableAndUniquelyReferenced() {
      _copyToNewBuffer(oldCount: _buffer.count)
    }
  }

  internal mutating func _reserveCapacityAssumingUniqueBuffer(oldCount: Int) {
    let capacity = _buffer.capacity == 0
    if oldCount + 1 > _buffer.capacity {
      _copyToNewBuffer(oldCount: oldCount)
    }
  }

  internal mutating func _appendElementAssumeUniqueAndCapacity(_ oldCount: Int, newElement: Element) {
    _buffer.count = oldCount + 1
    (_buffer.firstElementAddress + oldCount).initialize(to: newElement)
  }

  public mutating func append(_ newElement: Element) {
    _makeUniqueAndReserveCapacityIfNotUnique()
    let oldCount = _getCount()
    _reserveCapacityAssumingUniqueBuffer(oldCount: oldCount)
    _appendElementAssumeUniqueAndCapacity(oldCount, newElement: newElement)
  }

  public mutating func append<S : Sequence>(contentsOf newElements: S) where S.Element == Element {

    let newElementsCount = newElements.underestimatedCount
    reserveCapacityForAppend(newElementsCount: newElementsCount)

    let oldCount = self.count
    let startNewElements = _buffer.firstElementAddress + oldCount
    let buf = UnsafeMutableBufferPointer(
                start: startNewElements, 
                count: self.capacity - oldCount)

    let (remainder,writtenUpTo) = buf.initialize(from: newElements)
    let writtenCount = buf.distance(from: buf.startIndex, to: writtenUpTo)
    _buffer.count += writtenCount
    if writtenUpTo == buf.endIndex {
      _buffer._arrayAppendSequence(IteratorSequence(remainder))
    }
  }

  internal mutating func reserveCapacityForAppend(newElementsCount: Int) {
    let oldCount = self.count
    let oldCapacity = self.capacity
    let newCount = oldCount + newElementsCount

    self.reserveCapacity(newCount > oldCapacity ? Swift.max(newCount, _growArrayCapacity(oldCapacity)) : newCount)
  }

  public mutating func _customRemoveLast() -> Element? {
    let newCount = _getCount() - 1
    _makeUniqueAndReserveCapacityIfNotUnique()
    let pointer = (_buffer.firstElementAddress + newCount)
    let element = pointer.move()
    _buffer.count = newCount
    return element
  }

  public mutating func remove(at index: Int) -> Element {
    _makeUniqueAndReserveCapacityIfNotUnique()
    let newCount = _getCount() - 1
    let pointer = (_buffer.firstElementAddress + index)
    let result = pointer.move()
    pointer.moveInitialize(from: pointer + 1, count: newCount - index)
    _buffer.count = newCount
    return result
  }

  public mutating func insert(_ newElement: Element, at i: Int) {
    self.replaceSubrange(i..<i, with: CollectionOfOne(newElement))
  }

  public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
    if !keepCapacity {
      _buffer = _Buffer()
    } else {
      self.replaceSubrange(indices, with: EmptyCollection())
    }
  }

  public mutating func _withUnsafeMutableBufferPointerIfSupported<R>(_ body: (inout UnsafeMutableBufferPointer<Element>) throws -> R) rethrows -> R? {
    return try withUnsafeMutableBufferPointer {
      (bufferPointer) -> R in
      let r = try body(&bufferPointer)
      return r
    }
  }

  public func _copyToContiguousArray() -> ContiguousArray<Element> {
    if let n = _buffer.requestNativeBuffer() {
      return ContiguousArray(_buffer: n)
    }
    return _copyCollectionToContiguousArray(_buffer)
  }
}

extension ContiguousArray {
  public func withUnsafeBufferPointer<R>(_ body: (UnsafeBufferPointer<Element>) throws -> R) rethrows -> R {
    return try _buffer.withUnsafeBufferPointer(body)
  }

  public mutating func withUnsafeMutableBufferPointer<R>(_ body: (inout UnsafeMutableBufferPointer<Element>) throws -> R) rethrows -> R {
    let count = self.count
    _buffer._outlinedMakeUniqueBuffer(bufferCount: count)
    var work = ContiguousArray()
    (work, self) = (self, work)

    let pointer = work._buffer.firstElementAddress
    var inoutBufferPointer = UnsafeMutableBufferPointer(
      start: pointer, count: count)

    defer {
      (work, self) = (self, work)
    }
    return try body(&inoutBufferPointer)
  }

  public func _copyContents(initializing buffer: UnsafeMutableBufferPointer<Element>) -> (Iterator,UnsafeMutableBufferPointer<Element>.Index) {
    guard !self.isEmpty else { return (makeIterator(),buffer.startIndex) }
    guard var p = buffer.baseAddress else { 
        _preconditionFailure("Attempt to copy contents into nil buffer pointer") 
    }
    
    if let s = _baseAddressIfContiguous {
      p.initialize(from: s, count: self.count)
    } else {
      for x in self {
        p.initialize(to: x)
        p += 1
      }
    }

    var it = IndexingIterator(_elements: self)
    it._position = endIndex
    return (it,buffer.index(buffer.startIndex, offsetBy: self.count))
  }
}