NewArray.swift.gyb

%# -*- mode: swift -*-
//===--- NewArray.swift.gyb -----------------------------------*- swift -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// RUN-DISABLED: %target-run-simple-swift | FileCheck %s
// RUN: rm -rf %t && mkdir -p %t && %S/../../utils/gyb %s -o %t/NewArray.swift
// RUN: %S/../../utils/line-directive %t/NewArray.swift -- %target-build-swift %t/NewArray.swift -o %t/a.out -Xfrontend -disable-access-control
// RUN: %target-run %t/a.out 2>&1 | %S/../../utils/line-directive %t/NewArray.swift -- FileCheck %t/NewArray.swift
// REQUIRES: executable_test

// XFAIL: linux

var xCount = 0
var xSerial = 0

import StdlibUnittest

// Instead of testing with Int elements, we use this wrapper class
// that can help us track allocations and find issues with object
// lifetime inside Array implementations.
final class X
  : Comparable, CustomStringConvertible, 
    IntegerLiteralConvertible, Strideable
{
  required init(_ value: Int) {
    xCount += 1
    xSerial += 1
    serial = xSerial
    self.value = value
  }
  
  deinit {
    assert(serial > 0, "double destruction!")
    xCount -= 1
    serial = -serial
  }

  var description: String {
    assert(serial > 0, "dead X!")
    return value.description
  }

  func successor() -> Self {
    return self.dynamicType.init(self.value + 1)
  }
  
  convenience init(integerLiteral value: Int) {
    self.init(value)
  }

  @warn_unused_result
  func distance(to other: X) -> Int {
    return value.distance(to: other.value)
  }

  @warn_unused_result
  func advanced(by n: Int) -> X {
    return X(value.advanced(by: n))
  }
  
  var value: Int
  var serial: Int
}

func == (x: X, y: X) -> Bool {
  return x.value == y.value
}

func < (x: X, y: X) -> Bool {
  return x.value < y.value
}

//===----------------------------------------------------------------------===//

func printSequence<T : Sequence>(x: T) {
  print("[", terminator: "")
  var prefix = ""
  for a in x {
    print(prefix, terminator: "")
    print(a, terminator: "")
    prefix = ", "
  }
  print("]")
}

typealias BufferID = UnsafePointer<Void>

func bufferID<T : _ArrayProtocol>(x: T) -> BufferID {
  return x._buffer.identity
}

func checkReallocation<T : _ArrayProtocol>(
  x: T, _ lastBuffer: BufferID, _ reallocationExpected: Bool
) -> BufferID {
  let currentBuffer = bufferID(x)
  if (currentBuffer != lastBuffer) != reallocationExpected {
    let message = reallocationExpected ? "lack of" : ""
    print("unexpected \(message) reallocation")
  }
  return currentBuffer
}

func checkEqual<
  S1 : Sequence, S2 : Sequence
  where
  S1.Iterator.Element == S2.Iterator.Element,
  S1.Iterator.Element : Equatable
>(a1: S1, _ a2: S2, _ expected: Bool) {
  if a1.elementsEqual(a2) != expected {
    let un = expected ? "un" : ""
    print("unexpectedly \(un)equal sequences!")
  }
}

func test<
  T : _ArrayProtocol
  where
  T.Iterator.Element == T._Buffer.Element,
  T._Buffer.Element == T.Element,
  T.Element == X,
  T.Index == Int,
  T : RandomAccessCollection
>(_: T.Type, _ label: String) {
  print("test: \(label)...", terminator: "")

  var x: T = [1, 2, 3, 4, 5]
  
  checkEqual(x, 1...5, true)

  x.reserveCapacity(x.count + 2)
  checkEqual(x, 1...5, true)
  
  let bufferId0 = bufferID(x)

  // Append a range of integers
  x += 0..<2
  let bufferId1 = checkReallocation(x, bufferId0, false)
  
  for i in x.count..<(x.capacity + 1) {
    let bufferId1a = checkReallocation(x, bufferId1, false)
    x.append(13)
  }
  let bufferId2 = checkReallocation(x, bufferId1, true)

  let y = x
  x[x.predecessor(of: x.endIndex)] = 17
  let bufferId3 = checkReallocation(x, bufferId2, true)
  checkEqual(x, y, false)

  func checkReallocations(
    a: T, _ growthDescription: String, _ growBy1: (_: inout T)->()
  ) {
    var a = a
    var reallocations = 0

    // Note: right now this test is dependent on a growth factor of 2.
    // It's possible that factor will change, but (cursory) testing
    // has shown that using 1.5, the other popular growth factor,
    // slows things down.
    for _ in a.count..<(a.capacity * 4) {
      let oldId = bufferID(a)
      growBy1(&a)
      if oldId != bufferID(a) {
        reallocations += 1
      }
    }
    
    if reallocations > 3 {
      print(
        "Unexpectedly found \(reallocations) reallocations "
        + "of \(label) when growing via \(growthDescription)")
    }
  }

  checkReallocations(x, "append") { (x: inout T) -> () in x.append(42) }
  checkReallocations(x, "+=") { (x: inout T) -> () in x.append(42) }
  print("done.")
}

print("testing...")
// CHECK: testing...

test(ContiguousArray<X>.self, "ContiguousArray")
// CHECK-NEXT: test: ContiguousArray...done


test(Array<X>.self, "Array")
// CHECK-NEXT: test: Array...done

test(ArraySlice<X>.self, "ArraySlice")
// CHECK-NEXT: test: ArraySlice...done

func testAsArray() {
  print("== AsArray ==")
  var w: ContiguousArray<X> = [4, 2, 1]
  // CHECK: == AsArray == 
  
  let x = ContiguousArray(w)
  print(bufferID(w) == bufferID(x))
  // CHECK-NEXT: true
  
  let y = Array(x)
  print(bufferID(x) == bufferID(y))
  // CHECK-NEXT: true

  // Because of their indirection, arrays of classes can share
  // buffers.  
  let y1 = Array(y)
  print(bufferID(y1) == bufferID(y))
  // CHECK-NEXT: true
  
  let z = ArraySlice(y)
  print(bufferID(y) == bufferID(z))
  // CHECK-NEXT: true

  w = ContiguousArray(z)
  print(bufferID(w) == bufferID(z))
  // CHECK-NEXT: true

  let zz = y[0..<2]
  print(bufferID(zz))
  // CHECK-NEXT: 0x
}
testAsArray()

import Foundation

func nsArrayOfStrings() -> Array<NSString> {
  let src: ContiguousArray<NSString> = ["foo", "bar", "baz"]

  return src.withUnsafeBufferPointer {
    let ns =  NSArray(objects: UnsafePointer($0.baseAddress), count: $0.count)
    return ns as! [NSString]
  }
}

func testCocoa() {
  print("== Cocoa ==")
  // CHECK: == Cocoa ==

  var a = nsArrayOfStrings()
  printSequence(a)
  // CHECK-NEXT: [foo, bar, baz]
  
  a.append("qux")
  printSequence(a)
  // CHECK-NEXT: [foo, bar, baz, qux]

  a = nsArrayOfStrings()
  printSequence(a)
  // CHECK-NEXT: [foo, bar, baz]
  
  let b = a
  
  a[1] = "garply"
  printSequence(a)
  // CHECK-NEXT: [foo, garply, baz]

  // Mutating an element in a has no effect on b
  printSequence(b)
  // CHECK-NEXT: [foo, bar, baz]
  
  a = nsArrayOfStrings()
  a.insert("bag", at: 2)
  printSequence(a)
  // CHECK-NEXT: [foo, bar, bag, baz]

  a = nsArrayOfStrings()
  a.reserveCapacity(30)
  printSequence(a)
  // CHECK-NEXT: [foo, bar, baz]
  
  print(a.capacity >= 30)
  // CHECK-NEXT: true

  // Prove that we create contiguous storage for an opaque NSArray
  a.withUnsafeBufferPointer {
    (p) -> () in
    print(p[0])
    // CHECK-NEXT: foo
  }
}
testCocoa()

extension ArraySlice {
  mutating func qsort(compare: (Element, Element) -> Bool) {
    _introSort(&self, subRange: Range(self.indices), isOrderedBefore: compare)
  }
}

func testSlice() {
  print("== ArraySlice ==")
  // CHECK: == ArraySlice ==

  // do some tests on the shared semantics
  var b = ContiguousArray(X(0)..<X(10))

  // ArraySlice it
  var bSlice = b[3..<8]
  print("<\(bSlice.count)>")
  // CHECK-NEXT: <5>
  print("bSlice0: \(bSlice)")      // CHECK-NEXT: bSlice0: [3, 4, 5, 6, 7]

  // bSlice += X(11)..<X(13)

  // Writing into b does not change bSlice
  b[4] = 41        
  print("bSlice1: \(bSlice)")      // CHECK-NEXT: bSlice1: [3, 4, 5, 6, 7]

  // Writing into bSlice does not change b
  bSlice[3] = 32

  print("bSlice2: \(bSlice)")     // CHECK-NEXT: bSlice2: [32, 4, 5, 6, 7]
  printSequence(b)                // CHECK-NEXT: [0, 1, 2, 3, 41, 5, 6, 7, 8, 9]

  let c = b
  b[b.startIndex..<b.endIndex].qsort(<)
  printSequence(b)                // CHECK-NEXT: [0, 1, 2, 3, 5, 6, 7, 8, 9, 41]
  printSequence(c)                // CHECK-NEXT: [0, 1, 2, 3, 41, 5, 6, 7, 8, 9]

  // Now a bridged slice
  var a = Array<NSString>(
    _ArrayBuffer(nsArray: nsArrayOfStrings()._buffer._asCocoaArray()))

  printSequence(a)                // CHECK-NEXT: [foo, bar, baz]

  var aSlice = a[1..<3]           // CHECK-NEXT: [bar, baz]
  printSequence(aSlice)

  // Writing into aSlice works
  aSlice[1] = "buzz"              // CHECK-NEXT: [buzz, baz]
  printSequence(aSlice)

  // ...and doesn't affect a
  printSequence(a)                // CHECK-NEXT: [foo, bar, baz]

  // Appending to aSlice works...
  aSlice.append("fodder")
  print("<\(aSlice.count)>")      // CHECK-NEXT: <3>
  printSequence(aSlice)           // CHECK-NEXT: [buzz, baz, fodder]

  // And doesn't change a
  printSequence(a)                // CHECK-NEXT: [foo, bar, baz]
}
testSlice()

//===--- sub-range replacement --------------------------------------------===//

// Size of the array on which we're going to test "replace."
// testing time grows roughly as the cube of this constant
let testWidth = 11

%arrayTypes = ['ContiguousArray', 'Array', 'ArraySlice']
%for A in arrayTypes:

func testReplace(make: () -> ${A}<X>) {

  checkRangeReplaceable(make, { X(100)..<X(100 + $0) })
}

func testReplace${A}(
  makeOne: () -> ${A}<X> = {
    var x = ${A}<X>()
    // make sure some - but not all - replacements will have to grow the buffer
    x.reserveCapacity(testWidth * 3 / 2)
    x += X(0)..<X(testWidth)
    return x
  }
) {
  testReplace(makeOne)

  // Create one that will not be uniquely-referenced so we can test
  // the out-of-place code paths.
  let r = makeOne()
  testReplace({ r })
  
  // This test should ensure r's retain isn't dropped before we start testing.
  if (r.count != testWidth) {
    print("something bad happened!")
  }
}

print("testing subrange replacement in ${A}")
testReplace${A}()
%end

// Also test with a sub-slice of some larger buffer.  The "trailing"
// case is interesting because when the buffer is uniquely referenced
// we can expect to expand the slice in-place
for (maxValue, label) in [(testWidth, "trailing"), (testWidth*2, "interior")] {
  print("testing subrange replacement in \(label) Sub-ArraySlice")
  testReplaceArraySlice {
    var a = ContiguousArray(X(-testWidth)..<X(maxValue))
    a.reserveCapacity(a.count * 3 / 2)
    return a[testWidth..<(2 * testWidth)]
  }
}

// CHECK-NEXT: testing subrange replacement in ContiguousArray
// CHECK-NEXT: testing subrange replacement in Array
// CHECK-NEXT: testing subrange replacement in ArraySlice
// CHECK-NEXT: testing subrange replacement in trailing Sub-ArraySlice
// CHECK-NEXT: testing subrange replacement in interior Sub-ArraySlice

//===--- inout violations -------------------------------------------------===//

// The user has to obey certain rules when things are passed via
// inout, but in those cases we only guarantee memory-safety, not
// coherent semantics.  Let's try to force a memory-safety problem
// here.  This crashes when withUnsafeMutableBufferPointer is not
// sufficiently careful.
func testInoutViolation() {
  var a: [X] = [
    X(10), X(8), X(6), X(4), X(2), X(0), X(9), X(7), X(5), X(3), X(1)
  ]

%for A in arrayTypes:
  do {
    var b = ${A}(a)
    _ = b.sorted { x, y in
      b.removeAll()
      return x < y
    }
  }
%end
  
  // An overload of sorted for Arrays uses withUnsafeMutableBufferPointer,
  // which disables bounds checks.
  _ = a.sorted { x, y in
    a = []         // Invalidate the whole array during sorting
    return x < y
  }
}
testInoutViolation()

//===--- single-element modifiers -----------------------------------------===//

%for A in arrayTypes:

func testSingleElementModifiers${A}() {
  print("testing ${A} single-argument modifiers")
  // CHECK-NEXT: testing ${A} single-argument modifiers
  
  var a = ${A}(X(0)..<10)
  print(a.removeLast().value)     // CHECK-NEXT: 9
  printSequence(a)               // CHECK-NEXT: [0, 1, 2, 3, 4, 5, 6, 7, 8]
  
  a.insert(42, at: 4)
  printSequence(a)               // CHECK-NEXT: [0, 1, 2, 3, 42, 4, 5, 6, 7, 8]
  
  print(a.remove(at: 2).value) // CHECK-NEXT: 2
  printSequence(a)                  // CHECK-NEXT: [0, 1, 3, 42, 4, 5, 6, 7, 8]
}
testSingleElementModifiers${A}()
%end

//===--- isEmpty, first, last ---------------------------------------------===//

%for A in arrayTypes:

func testIsEmptyFirstLast${A}() {
  print("testing ${A} isEmpty, first, and last")
  // CHECK-NEXT: testing ${A} isEmpty, first, and last

  print(${A}<Int>().isEmpty)          // CHECK-NEXT: true
  print(${A}(42...42).isEmpty)   // CHECK-NEXT: false

  print("<\(${A}(3...42).first!)>")  // CHECK-NEXT: <3>
  print("<\(${A}(3...42).last!)>")   // CHECK-NEXT: <42>

  print("<\(${A}<Int>().first)>")    // CHECK-NEXT: nil
  print("<\(${A}<Int>().last)>")     // CHECK-NEXT: nil
  
  var a = ${A}(X(0)..<10)
  print(a.removeLast().value)     // CHECK-NEXT: 9
  printSequence(a)               // CHECK-NEXT: [0, 1, 2, 3, 4, 5, 6, 7, 8]
  
  a.insert(42, at: 4)
  printSequence(a)               // CHECK-NEXT: [0, 1, 2, 3, 42, 4, 5, 6, 7, 8]
  
  print(a.remove(at: 2).value) // CHECK-NEXT: 2
  printSequence(a)                  // CHECK-NEXT: [0, 1, 3, 42, 4, 5, 6, 7, 8]
}
testIsEmptyFirstLast${A}()
%end

//===--- Regression Tests -------------------------------------------------===//
func rdar16958865() {
  var a: [Int] = []
  a += AnySequence([ 42, 4242 ])
  // CHECK-NEXT: [42, 4242]
  print(a)
}
rdar16958865()

#if os(OSX)
import AppKit
typealias OSColor = NSColor
#else
import UIKit
typealias OSColor = UIColor
#endif

class Rdar16914909 : NSObject {
  var basicColorSet = [OSColor]()
  
  func doColorStuff() {
    basicColorSet.append(OSColor.lightGray())
    print("appended")
  }
}

Rdar16914909().doColorStuff()
// CHECK-NEXT: appended

print("leaks = \(xCount)")
// CHECK-NEXT: leaks = 0

// CHECK-NEXT: all done.
print("all done.")

// ${'Local Variables'}:
// eval: (read-only-mode 1)
// End: