//===--- ArrayShared.swift ------------------------------------*- swift -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//

/// This type is used as a result of the _checkSubscript call to associate the
/// call with the array access call it guards.
@_fixed_layout
public struct _DependenceToken {
  @inlinable
  public init() {
  }
}

/// Returns an Array of `_count` uninitialized elements using the
/// given `storage`, and a pointer to uninitialized memory for the
/// first element.
///
/// This function is referenced by the compiler to allocate array literals.
///
/// - Precondition: `storage` is `_ContiguousArrayStorage`.
@inline(__always)
public // COMPILER_INTRINSIC
func _allocateUninitializedArray<Element>(_  builtinCount: Builtin.Word)
    -> (Array<Element>, Builtin.RawPointer) {
  let count = Int(builtinCount)
  if count > 0 {
    // Doing the actual buffer allocation outside of the array.uninitialized
    // semantics function enables stack propagation of the buffer.
    let bufferObject = Builtin.allocWithTailElems_1(
      _ContiguousArrayStorage<Element>.self, builtinCount, Element.self)

    let (array, ptr) = Array<Element>._adoptStorage(bufferObject, count: count)
    return (array, ptr._rawValue)
  }
  // For an empty array no buffer allocation is needed.
  let (array, ptr) = Array<Element>._allocateUninitialized(count)
  return (array, ptr._rawValue)
}

// Referenced by the compiler to deallocate array literals on the
// error path.
@inlinable
@_semantics("array.dealloc_uninitialized")
public // COMPILER_INTRINSIC
func _deallocateUninitializedArray<Element>(
  _ array: __owned Array<Element>
) {
  var array = array
  array._deallocateUninitialized()
}


// Utility method for collections that wish to implement CustomStringConvertible
// and CustomDebugStringConvertible using a bracketed list of elements,
// like an array.
@inlinable // FIXME(sil-serialize-all)
internal func _makeCollectionDescription<C: Collection>
  (for items: C, withTypeName type: String?) -> String {
  var result = ""
  if let type = type {
    result += "\(type)(["
  } else {
    result += "["
  }
  var first = true
  for item in items {
    if first {
      first = false
    } else {
      result += ", "
    }
    debugPrint(item, terminator: "", to: &result)
  }
  result += type != nil ? "])" : "]"
  return result
}

extension _ArrayBufferProtocol {
  @inlinable // FIXME @useableFromInline https://bugs.swift.org/browse/SR-7588
  @inline(never)
  internal mutating func _arrayOutOfPlaceReplace<C: Collection>(
    _ bounds: Range<Int>,
    with newValues: C,
    count insertCount: Int
  ) where C.Element == Element {

    let growth = insertCount - bounds.count
    let newCount = self.count + growth
    var newBuffer = _forceCreateUniqueMutableBuffer(
      newCount: newCount, requiredCapacity: newCount)

    _arrayOutOfPlaceUpdate(
      &newBuffer, bounds.lowerBound - startIndex, insertCount,
      { rawMemory, count in
        var p = rawMemory
        var q = newValues.startIndex
        for _ in 0..<count {
          p.initialize(to: newValues[q])
          newValues.formIndex(after: &q)
          p += 1
        }
        _expectEnd(of: newValues, is: q)
      }
    )
  }
}

/// A _debugPrecondition check that `i` has exactly reached the end of
/// `s`.  This test is never used to ensure memory safety; that is
/// always guaranteed by measuring `s` once and re-using that value.
@inlinable
internal func _expectEnd<C: Collection>(of s: C, is i: C.Index) {
  _debugPrecondition(
    i == s.endIndex,
    "invalid Collection: count differed in successive traversals")
}

@inlinable
internal func _growArrayCapacity(_ capacity: Int) -> Int {
  return capacity * 2
}

//===--- generic helpers --------------------------------------------------===//

extension _ArrayBufferProtocol {
  /// Create a unique mutable buffer that has enough capacity to hold 'newCount'
  /// elements and at least 'requiredCapacity' elements. Set the count of the new
  /// buffer to 'newCount'. The content of the buffer is uninitialized.
  /// The formula used to compute the new buffers capacity is:
  ///   max(requiredCapacity, source.capacity)  if newCount <= source.capacity
  ///   max(requiredCapacity, _growArrayCapacity(source.capacity)) otherwise
  @inline(never)
  @inlinable // @specializable
  internal func _forceCreateUniqueMutableBuffer(
    newCount: Int, requiredCapacity: Int
  ) -> _ContiguousArrayBuffer<Element> {
    return _forceCreateUniqueMutableBufferImpl(
      countForBuffer: newCount, minNewCapacity: newCount,
      requiredCapacity: requiredCapacity)
  }

  /// Create a unique mutable buffer that has enough capacity to hold
  /// 'minNewCapacity' elements and set the count of the new buffer to
  /// 'countForNewBuffer'. The content of the buffer uninitialized.
  /// The formula used to compute the new buffers capacity is:
  ///   max(minNewCapacity, source.capacity) if minNewCapacity <= source.capacity
  ///   max(minNewCapacity, _growArrayCapacity(source.capacity)) otherwise
  @inline(never)
  @inlinable // @specializable
  internal func _forceCreateUniqueMutableBuffer(
    countForNewBuffer: Int, minNewCapacity: Int
  ) -> _ContiguousArrayBuffer<Element> {
    return _forceCreateUniqueMutableBufferImpl(
      countForBuffer: countForNewBuffer, minNewCapacity: minNewCapacity,
      requiredCapacity: minNewCapacity)
  }

  /// Create a unique mutable buffer that has enough capacity to hold
  /// 'minNewCapacity' elements and at least 'requiredCapacity' elements and set
  /// the count of the new buffer to 'countForBuffer'. The content of the buffer
  /// uninitialized.
  /// The formula used to compute the new capacity is:
  ///  max(requiredCapacity, source.capacity) if minNewCapacity <= source.capacity
  ///  max(requiredCapacity, _growArrayCapacity(source.capacity))  otherwise
  @inlinable
  internal func _forceCreateUniqueMutableBufferImpl(
    countForBuffer: Int, minNewCapacity: Int,
    requiredCapacity: Int
  ) -> _ContiguousArrayBuffer<Element> {
    _sanityCheck(countForBuffer >= 0)
    _sanityCheck(requiredCapacity >= countForBuffer)
    _sanityCheck(minNewCapacity >= countForBuffer)

    let minimumCapacity = Swift.max(requiredCapacity,
      minNewCapacity > capacity
         ? _growArrayCapacity(capacity) : capacity)

    return _ContiguousArrayBuffer(
      _uninitializedCount: countForBuffer, minimumCapacity: minimumCapacity)
  }
}

extension _ArrayBufferProtocol {
  /// Initialize the elements of dest by copying the first headCount
  /// items from source, calling initializeNewElements on the next
  /// uninitialized element, and finally by copying the last N items
  /// from source into the N remaining uninitialized elements of dest.
  ///
  /// As an optimization, may move elements out of source rather than
  /// copying when it isUniquelyReferenced.
  @inline(never)
  @inlinable // @specializable
  internal mutating func _arrayOutOfPlaceUpdate(
    _ dest: inout _ContiguousArrayBuffer<Element>,
    _ headCount: Int, // Count of initial source elements to copy/move
    _ newCount: Int,  // Number of new elements to insert
    _ initializeNewElements: 
        ((UnsafeMutablePointer<Element>, _ count: Int) -> ()) = { ptr, count in
      _sanityCheck(count == 0)
    }
  ) {

    _sanityCheck(headCount >= 0)
    _sanityCheck(newCount >= 0)

    // Count of trailing source elements to copy/move
    let sourceCount = self.count
    let tailCount = dest.count - headCount - newCount
    _sanityCheck(headCount + tailCount <= sourceCount)

    let oldCount = sourceCount - headCount - tailCount
    let destStart = dest.firstElementAddress
    let newStart = destStart + headCount
    let newEnd = newStart + newCount

    // Check to see if we have storage we can move from
    if let backing = requestUniqueMutableBackingBuffer(
      minimumCapacity: sourceCount) {

      let sourceStart = firstElementAddress
      let oldStart = sourceStart + headCount

      // Destroy any items that may be lurking in a _SliceBuffer before
      // its real first element
      let backingStart = backing.firstElementAddress
      let sourceOffset = sourceStart - backingStart
      backingStart.deinitialize(count: sourceOffset)

      // Move the head items
      destStart.moveInitialize(from: sourceStart, count: headCount)

      // Destroy unused source items
      oldStart.deinitialize(count: oldCount)

      initializeNewElements(newStart, newCount)

      // Move the tail items
      newEnd.moveInitialize(from: oldStart + oldCount, count: tailCount)

      // Destroy any items that may be lurking in a _SliceBuffer after
      // its real last element
      let backingEnd = backingStart + backing.count
      let sourceEnd = sourceStart + sourceCount
      sourceEnd.deinitialize(count: backingEnd - sourceEnd)
      backing.count = 0
    }
    else {
      let headStart = startIndex
      let headEnd = headStart + headCount
      let newStart = _copyContents(
        subRange: headStart..<headEnd,
        initializing: destStart)
      initializeNewElements(newStart, newCount)
      let tailStart = headEnd + oldCount
      let tailEnd = endIndex
      _copyContents(subRange: tailStart..<tailEnd, initializing: newEnd)
    }
    self = Self(_buffer: dest, shiftedToStartIndex: startIndex)
  }
}

extension _ArrayBufferProtocol {
  @inline(never)
  @usableFromInline
  internal mutating func _outlinedMakeUniqueBuffer(bufferCount: Int) {

    if _fastPath(
        requestUniqueMutableBackingBuffer(minimumCapacity: bufferCount) != nil) {
      return
    }

    var newBuffer = _forceCreateUniqueMutableBuffer(
      newCount: bufferCount, requiredCapacity: bufferCount)
    _arrayOutOfPlaceUpdate(&newBuffer, bufferCount, 0)
  }

  /// Append items from `newItems` to a buffer.
  @inlinable
  internal mutating func _arrayAppendSequence<S: Sequence>(
    _ newItems: S
  ) where S.Element == Element {
    
    // this function is only ever called from append(contentsOf:)
    // which should always have exhausted its capacity before calling
    _sanityCheck(count == capacity)
    var newCount = self.count

    // there might not be any elements to append remaining,
    // so check for nil element first, then increase capacity,
    // then inner-loop to fill that capacity with elements
    var stream = newItems.makeIterator()
    var nextItem = stream.next()
    while nextItem != nil {

      // grow capacity, first time around and when filled
      var newBuffer = _forceCreateUniqueMutableBuffer(
        countForNewBuffer: newCount, 
        // minNewCapacity handles the exponential growth, just
        // need to request 1 more than current count/capacity
        minNewCapacity: newCount + 1)

      _arrayOutOfPlaceUpdate(&newBuffer, newCount, 0)

      let currentCapacity = self.capacity
      let base = self.firstElementAddress

      // fill while there is another item and spare capacity
      while let next = nextItem, newCount < currentCapacity {
        (base + newCount).initialize(to: next)
        newCount += 1
        nextItem = stream.next()
      }
      self.count = newCount
    }
  }
}