HashedCollections.swift.gyb

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2015 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
//
//===----------------------------------------------------------------------===//

import SwiftShims

// General Mutable, Value-Type Collections
// =================================================
//
// Basic copy-on-write (COW) requires a container's data to be copied
// into new storage before it is modified, to avoid changing the data
// of other containers that may share the data.  There is one
// exception: when we know the container has the only reference to the
// data, we can elide the copy.  This COW optimization is crucial for
// the performance of mutating algorithms.
//
// Some container elements (Characters in a String, key/value pairs in
// an open-addressing hash table) are not traversable with a fixed
// size offset, so incrementing/decrementing indices requires looking
// at the contents of the container.  The current interface for
// incrementing/decrementing indices of an CollectionType is the usual ++i,
// --i. Therefore, for memory safety, the indices need to keep a
// reference to the container's underlying data so that it can be
// inspected.  But having multiple outstanding references to the
// underlying data defeats the COW optimization.
//
// The way out is to count containers referencing the data separately
// from indices that reference the data.  When deciding to elide the
// copy and modify the data directly---as long as we don't violate
// memory safety of any outstanding indices---we only need to be
// sure that no other containers are referencing the data.
//
// Implementation notes
// ====================
//
// `Dictionary` uses two storage schemes: native storage and Cocoa storage.
//
// Native storage is a hash table with open addressing and linear probing.  The
// bucket array forms a logical ring (e.g., a chain can wrap around the end of
// buckets array to the beginning of it).
//
// The logical bucket array is implemented as three arrays: Key, Value, and a
// bitmap that marks valid entries. An invalid entry marks the end of a chain.
// There is always at least one invalid entry among the buckets. `Dictionary`
// does not use tombstones.
//
// In addition to the native storage `Dictionary` can also wrap an
// `NSDictionary` in order to allow brdidging `NSDictionary` to `Dictionary` in
// `O(1)`.
//
// Currently native storage uses a data structure like this::
//
//   Dictionary<K,V> (a struct)
//   +----------------------------------------------+
//   | [ _VariantDictionaryStorage<K,V> (an enum) ] |
//   +---|------------------------------------------+
//      /
//     |
//     V  _NativeDictionaryStorageOwner<K,V> (a class)
//   +-----------------------------------------------------------+
//   | [refcount#1] [ _NativeDictionaryStorage<K,V> (a struct) ] |
//   +----------------|------------------------------------------+
//                    |
//     +--------------+
//     |
//     V  _NativeDictionaryStorageImpl<K,V> (a class)
//   +-----------------------------------------+
//   | [refcount#2]    [...element storage...] |
//   +-----------------------------------------+
//     ^
//     +---+
//         |              Dictionary<K,V>.Index (an enum)
//   +-----|--------------------------------------------+
//   |     |     _NativeDictionaryIndex<K,V> (a struct) |
//   | +---|------------------------------------------+ |
//   | | [ _NativeDictionaryStorage<K,V> (a struct) ] | |
//   | +----------------------------------------------+ |
//   +--------------------------------------------------+
//
// We would like to optimize by allocating the `_NativeDictionaryStorageOwner`
// /inside/ the `_NativeDictionaryStorageImpl`, and override the `dealloc`
// method of `_NativeDictionaryStorageOwner` to do nothing but release its
// reference.
//
//     Dictionary<K,V> (a struct)
//     +----------------------------------------------+
//     | [ _VariantDictionaryStorage<K,V> (an enum) ] |
//     +---|------------------------------------------+
//        /
//       |          +---+
//       |          V   |  _NativeDictionaryStorageImpl<K,V> (a class)
//   +---|--------------|----------------------------------------------+
//   |   |              |                                              |
//   |   | [refcount#2] |                                              |
//   |   |              |                                              |
//   |   V              | _NativeDictionaryStorageOwner<K,V> (a class) |
//   | +----------------|------------------------------------------+   |
//   | | [refcount#1] [ _NativeDictionaryStorage<K,V> (a struct) ] |   |
//   | +-----------------------------------------------------------+   |
//   |                                                                 |
//   | [...element storage...]                                         |
//   +-----------------------------------------------------------------+
//
//
// Cocoa storage uses a data structure like this::
//
//   Dictionary<K,V> (a struct)
//   +----------------------------------------------+
//   | _VariantDictionaryStorage<K,V> (an enum)     |
//   | +----------------------------------------+   |
//   | | [ _CocoaDictionaryStorage (a struct) ] |   |
//   | +---|------------------------------------+   |
//   +-----|----------------------------------------+
//         |
//     +---+
//     |
//     V  NSDictionary (a class)
//   +--------------+
//   | [refcount#1] |
//   +--------------+
//     ^
//     +-+
//       |     Dictionary<K,V>.Index (an enum)
//   +---|-----------------------------------+
//   |   |  _CocoaDictionaryIndex (a struct) |
//   | +-|-----------------------------+     |
//   | | * [ all keys ] [ next index ] |     |
//   | +-------------------------------+     |
//   +---------------------------------------+
//
// `_NativeDictionaryStorageOwner` is an `NSDictionary` subclass.  It can
// be returned to Objective-C during bridging if both `Key` and `Value`
// bridge verbatim.
//
// Index Invalidation
// ------------------
//
// Indexing a container, `c[i]`, uses the integral offset stored in the index
// to access the elements referenced by the container.  The buffer referenced
// by the index is only used to increment and decrement the index.  Most of the
// time, these two buffers will be identical, but they need not always be.  For
// example, if one ensures that a `Dictionary` has sufficient capacity to avoid
// reallocation on the next element insertion, the following works ::
//
//   var (i, found) = d.find(k) // i is associated with d's buffer
//   if found {
//      var e = d            // now d is sharing its data with e
//      e[newKey] = newValue // e now has a unique copy of the data
//      return e[i]          // use i to access e
//   }
//
// The result should be a set of iterator invalidation rules familiar to anyone
// familiar with the C++ standard library.  Note that because all accesses to a
// dictionary buffer are bounds-checked, this scheme never compromises memory
// safety.
//
// Bridging
// ========
//
// Bridging `NSDictionary` to `Dictionary`
// ---------------------------------------
//
// `NSDictionary` bridges to `Dictionary<NSObject, AnyObject>` in `O(1)`,
// without memory allocation.
//
// Bridging `Dictionary` to `NSDictionary`
// ---------------------------------------
//
// `Dictionary<K, V>` bridges to `NSDictionary` iff both `K` and `V` are
// bridged.  Otherwise, a runtime error is raised.
//
// * if both `K` and `V` are bridged verbatim, then `Dictionary<K, V>` bridges
//   to `NSDictionary` in `O(1)`, without memory allocation.  Access to
//   elements does not cause memory allocation.
//
// * otherwise, `K` and/or `V` are unconditionally or conditionally bridged.
//   In this case, `Dictionary<K, V>` is bridged to `NSDictionary` in `O(1)`,
//   without memory allocation.  Complete bridging is performed when the first
//   access to elements happens.  The bridged `NSDictionary` has a cache of
//   pointers it returned, so that:
//   - Every time keys or values are accessed on the bridged `NSDictionary`,
//     new objects are not created.
//   - Accessing the same element (key or value) multiple times will return
//     the same pointer.
//
// Bridging `NSSet` to `Set` and vice versa
// ----------------------------------------
//
// Bridging guarantees for `Set<Element>` are the same as for
// `Dictionary<Element, ()>`.
//

/// This protocol is only used for compile-time checks that
/// every storage type implements all required operations.
internal protocol _HashStorageType {
  typealias Key
  typealias Value
  typealias Index
  typealias SequenceElement
  var startIndex: Index { get }
  var endIndex: Index { get }

  @warn_unused_result
  func indexForKey(key: Key) -> Index?

  @warn_unused_result
  func assertingGet(i: Index) -> SequenceElement

  @warn_unused_result
  func assertingGet(key: Key) -> Value

  @warn_unused_result
  func maybeGet(key: Key) -> Value?

  mutating func updateValue(value: Value, forKey: Key) -> Value?
  mutating func removeAtIndex(index: Index) -> SequenceElement
  mutating func removeValueForKey(key: Key) -> Value?
  mutating func removeAll(keepCapacity keepCapacity: Bool)
  var count: Int { get }

  @warn_unused_result
  static func fromArray(elements: [SequenceElement]) -> Self
}

/// The inverse of the default hash table load factor.  Factored out so that it
/// can be used in multiple places in the implementation and stay consistent.
/// Should not be used outside `Dictionary` implementation.
@_transparent
internal var _hashContainerDefaultMaxLoadFactorInverse: Double {
  return 1.0 / 0.75
}

#if _runtime(_ObjC)
/// Call `[lhs isEqual: rhs]`.
///
/// This function is part of the runtime because `Bool` type is bridged to
/// `ObjCBool`, which is in Foundation overlay.
@_silgen_name("swift_stdlib_NSObject_isEqual")
internal func _stdlib_NSObject_isEqual(lhs: AnyObject, _ rhs: AnyObject) -> Bool
#endif

//===--- Hacks and workarounds --------------------------------------------===//

/// Like `UnsafeMutablePointer<Unmanaged<AnyObject>>`, or `id
/// __unsafe_unretained *` in Objective-C ARC.
internal struct _UnmanagedAnyObjectArray {
  // `UnsafeMutablePointer<Unmanaged<AnyObject>>` fails because of:
  // <rdar://problem/16836348> IRGen: Couldn't find conformance

  /// Underlying pointer, typed as an integer to escape from reference
  /// counting.
  internal var value: UnsafeMutablePointer<Int>

  internal init(_ up: UnsafeMutablePointer<AnyObject>) {
    self.value = UnsafeMutablePointer(up)
  }

  internal subscript(i: Int) -> AnyObject {
    get {
      return _reinterpretCastToAnyObject(value[i])
    }
    nonmutating set(newValue) {
      value[i] = unsafeBitCast(newValue, Int.self)
    }
  }
}

//===--- APIs unique to Set<Element> --------------------------------------===//

/// A collection of unique `Element` instances with no defined ordering.
public struct Set<Element : Hashable> :
  Hashable, CollectionType, ArrayLiteralConvertible {

  @available(*, unavailable, renamed="Element")
  public typealias T = Element

  internal typealias _Self = Set<Element>
  internal typealias _VariantStorage = _VariantSetStorage<Element>
  internal typealias _NativeStorage = _NativeSetStorage<Element>
  public typealias Index = SetIndex<Element>

  internal var _variantStorage: _VariantStorage

  /// Create an empty set with at least the given number of
  /// elements worth of storage.  The actual capacity will be the
  /// smallest power of 2 that's >= `minimumCapacity`.
  public init(minimumCapacity: Int) {
    _variantStorage =
      _VariantStorage.Native(
        _NativeStorage.Owner(minimumCapacity: minimumCapacity))
  }

  /// Private initializer.
  internal init(_nativeStorage: _NativeSetStorage<Element>) {
    _variantStorage = _VariantStorage.Native(
      _NativeStorage.Owner(nativeStorage: _nativeStorage))
  }

  /// Private initializer.
  internal init(_nativeStorageOwner: _NativeSetStorageOwner<Element>) {
    _variantStorage = .Native(_nativeStorageOwner)
  }

  //
  // All APIs below should dispatch to `_variantStorage`, without doing any
  // additional processing.
  //

#if _runtime(_ObjC)
  /// Private initializer used for bridging.
  ///
  /// Only use this initializer when both conditions are true:
  ///
  /// * it is statically known that the given `NSSet` is immutable;
  /// * `Element` is bridged verbatim to Objective-C (i.e.,
  ///   is a reference type).
  public init(_immutableCocoaSet: _NSSetType) {
    _sanityCheck(_isBridgedVerbatimToObjectiveC(Element.self),
      "Set can be backed by NSSet _variantStorage only when the member type can be bridged verbatim to Objective-C")
    _variantStorage = _VariantSetStorage.Cocoa(
      _CocoaSetStorage(cocoaSet: _immutableCocoaSet))
  }
#endif

  /// The position of the first element in a non-empty set.
  ///
  /// This is identical to `endIndex` in an empty set.
  ///
  /// - Complexity: Amortized O(1) if `self` does not wrap a bridged
  ///   `NSSet`, O(N) otherwise.
  public var startIndex: Index {
    return _variantStorage.startIndex
  }

  /// The collection's "past the end" position.
  ///
  /// `endIndex` is not a valid argument to `subscript`, and is always
  /// reachable from `startIndex` by zero or more applications of
  /// `successor()`.
  ///
  /// - Complexity: Amortized O(1) if `self` does not wrap a bridged
  ///   `NSSet`, O(N) otherwise.
  public var endIndex: Index {
    return _variantStorage.endIndex
  }

  /// Returns `true` if the set contains a member.
  @warn_unused_result
  public func contains(member: Element) -> Bool {
    return _variantStorage.maybeGet(member) != nil
  }

  /// Returns the `Index` of a given member, or `nil` if the member is not
  /// present in the set.
  @warn_unused_result
  public func indexOf(member: Element) -> Index? {
    return _variantStorage.indexForKey(member)
  }

  /// Insert a member into the set.
  public mutating func insert(member: Element) {
    _variantStorage.updateValue(member, forKey: member)
  }

  /// Remove the member from the set and return it if it was present.
  public mutating func remove(member: Element) -> Element? {
    return _variantStorage.removeValueForKey(member)
  }

  /// Remove the member referenced by the given index.
  public mutating func removeAtIndex(index: Index) -> Element {
    return _variantStorage.removeAtIndex(index)
  }

  /// Erase all the elements.  If `keepCapacity` is `true`, `capacity`
  /// will not decrease.
  public mutating func removeAll(keepCapacity keepCapacity: Bool = false) {
    _variantStorage.removeAll(keepCapacity: keepCapacity)
  }

  /// Remove a member from the set and return it.
  ///
  /// - Requires: `count > 0`.
  public mutating func removeFirst() -> Element {
    _precondition(count > 0, "can't removeFirst from an empty Set")
    let member = first!
    remove(member)
    return member
  }

  /// The number of members in the set.
  ///
  /// - Complexity: O(1).
  public var count: Int {
    return _variantStorage.count
  }

  //
  // `SequenceType` conformance
  //

  /// Access the member at `position`.
  ///
  /// - Complexity: O(1).
  public subscript(position: Index) -> Element {
    return _variantStorage.assertingGet(position)
  }

  /// Return a *generator* over the members.
  ///
  /// - Complexity: O(1).
  public func generate() -> SetGenerator<Element> {
    return _variantStorage.generate()
  }

  //
  // `ArrayLiteralConvertible` conformance
  //
  public init(arrayLiteral elements: Element...) {
    self.init(_nativeStorage: _NativeSetStorage.fromArray(elements))
  }

  //
  // APIs below this comment should be implemented strictly in terms of
  // *public* APIs above.  `_variantStorage` should not be accessed directly.
  //
  // This separates concerns for testing.  Tests for the following APIs need
  // not to concern themselves with testing correctness of behavior of
  // underlying storage (and different variants of it), only correctness of the
  // API itself.
  //

  /// Create an empty `Set`.
  public init() {
    self = Set<Element>(minimumCapacity: 0)
  }

  /// Create a `Set` from a finite sequence of items.
  public init<S : SequenceType where S.Generator.Element == Element>(_ sequence: S) {
    self.init()
    if let s = sequence as? Set<Element> {
      // If this sequence is actually a native `Set`, then we can quickly
      // adopt its native storage and let COW handle uniquing only
      // if necessary.
      switch (s._variantStorage) {
        case .Native(let owner):
          _variantStorage = .Native(owner)
        case .Cocoa(let owner):
          _variantStorage = .Cocoa(owner)
      }
    } else {
      for item in sequence {
        insert(item)
      }
    }
  }

  /// Returns true if the set is a subset of a finite sequence as a `Set`.
  @warn_unused_result
  public func isSubsetOf<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Bool {
    let other = sequence as? Set<Element> ?? Set(sequence)
    let (isSubset, isEqual) = _compareSets(self, other)
    return isSubset || isEqual
  }

  /// Returns true if the set is a subset of a finite sequence as a `Set`
  /// but not equal.
  @warn_unused_result
  public func isStrictSubsetOf<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Bool {
    let other = sequence as? Set<Element> ?? Set(sequence)
    let (isSubset, isEqual) = _compareSets(self, other)
    return isSubset && !isEqual
  }

  /// Returns true if the set is a superset of a finite sequence as a `Set`.
  @warn_unused_result
  public func isSupersetOf<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Bool {
    let other = sequence as? Set<Element> ?? Set(sequence)
    return other.isSubsetOf(self)
  }

  /// Returns true if the set is a superset of a finite sequence as a `Set`
  /// but not equal.
  @warn_unused_result
  public func isStrictSupersetOf<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Bool {
    let other = sequence as? Set<Element> ?? Set(sequence)
    return other.isStrictSubsetOf(self)
  }

  /// Returns true if no members in the set are in a finite sequence as a `Set`.
  @warn_unused_result
  public func isDisjointWith<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Bool {
    let other = sequence as? Set<Element> ?? Set(sequence)
    for member in self {
      if other.contains(member) {
        return false
      }
    }
    return true
  }

  /// Return a new `Set` with items in both this set and a finite sequence.
  @warn_unused_result
  public func union<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Set<Element> {
    var newSet = self
    newSet.unionInPlace(sequence)
    return newSet
  }

  /// Insert elements of a finite sequence into this `Set`.
  public mutating func unionInPlace<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) {
    for item in sequence {
      insert(item)
    }
  }

  /// Return a new set with elements in this set that do not occur
  /// in a finite sequence.
  @warn_unused_result
  public func subtract<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Set<Element> {
    var newSet = self
    newSet.subtractInPlace(sequence)
    return newSet
  }

  /// Remove all members in the set that occur in a finite sequence.
  public mutating func subtractInPlace<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) {
    for item in sequence {
      remove(item)
    }
  }

  /// Return a new set with elements common to this set and a finite sequence.
  @warn_unused_result
  public func intersect<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Set<Element> {
    let other = sequence as? Set<Element> ?? Set(sequence)
    var newSet = Set<Element>()
    for member in self {
      if other.contains(member) {
        newSet.insert(member)
      }
    }
    return newSet
  }

  /// Remove any members of this set that aren't also in a finite sequence.
  public mutating func intersectInPlace<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) {
    // Because `intersect` needs to both modify and iterate over
    // the left-hand side, the index may become invalidated during
    // traversal so an intermediate set must be created.
    //
    // FIXME(performance): perform this operation at a lower level
    // to avoid invalidating the index and avoiding a copy.
    let result = self.intersect(sequence)

    // The result can only have fewer or the same number of elements.
    // If no elements were removed, don't perform a reassignment
    // as this may cause an unnecessary uniquing COW.
    if result.count != count {
      self = result
    }
  }

  /// Return a new set with elements that are either in the set or a finite
  /// sequence but do not occur in both.
  @warn_unused_result
  public func exclusiveOr<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) -> Set<Element> {
    var newSet = self
    newSet.exclusiveOrInPlace(sequence)
    return newSet
  }

  /// For each element of a finite sequence, remove it from the set if it is a
  /// common element, otherwise add it to the set. Repeated elements of the
  /// sequence will be ignored.
  public mutating func exclusiveOrInPlace<
    S : SequenceType where S.Generator.Element == Element
  >(sequence: S) {
    let other = sequence as? Set<Element> ?? Set(sequence)
    for member in other {
      if contains(member) {
        remove(member)
      } else {
        insert(member)
      }
    }
  }

  public var hashValue: Int {
    // FIXME: <rdar://problem/18915294> Cache Set<T> hashValue
    var result: Int = _mixInt(0)
    for member in self {
       result ^= _mixInt(member.hashValue)
    }
    return result
  }

  //
  // `SequenceType` conformance
  //

  @warn_unused_result
  public func _customContainsEquatableElement(member: Element) -> Bool? {
    return contains(member)
  }

  @warn_unused_result
  public func _customIndexOfEquatableElement(member: Element) -> Index?? {
    return Optional(indexOf(member))
  }

  //
  // CollectionType conformance
  //

  /// `true` if the set is empty.
  public var isEmpty: Bool {
    return count == 0
  }

  /// The first element obtained when iterating, or `nil` if `self` is
  /// empty.  Equivalent to `self.generate().next()`.
  public var first: Element? {
    return count > 0 ? self[startIndex] : .None
  }
}

/// Check for both subset and equality relationship between
/// a set and some sequence (which may itself be a `Set`).
///
/// (isSubset: lhs ⊂ rhs, isEqual: lhs ⊂ rhs and |lhs| = |rhs|)
@warn_unused_result
internal func _compareSets<Element>(lhs: Set<Element>, _ rhs: Set<Element>)
  -> (isSubset: Bool, isEqual: Bool) {
  for member in lhs {
    if !rhs.contains(member) {
      return (false, false)
    }
  }
  return (true, lhs.count == rhs.count)
}

@warn_unused_result
public func == <Element : Hashable>(lhs: Set<Element>, rhs: Set<Element>) -> Bool {
  switch (lhs._variantStorage, rhs._variantStorage) {
  case (.Native(let lhsNativeOwner), .Native(let rhsNativeOwner)):
    let lhsNative = lhsNativeOwner.nativeStorage
    let rhsNative = rhsNativeOwner.nativeStorage
    // FIXME(performance): early exit if lhs and rhs reference the same
    // storage?

    if lhsNative.count != rhsNative.count {
      return false
    }

    for member in lhs {
      let (_, found) = rhsNative._find(member, rhsNative._bucket(member))
      if !found {
        return false
      }
    }
    return true

  case (_VariantSetStorage.Cocoa(let lhsCocoa),
      _VariantSetStorage.Cocoa(let rhsCocoa)):
#if _runtime(_ObjC)
    return _stdlib_NSObject_isEqual(lhsCocoa.cocoaSet, rhsCocoa.cocoaSet)
#else
      _sanityCheckFailure("internal error: unexpected cocoa set")
#endif

  case (_VariantSetStorage.Native(let lhsNativeOwner),
    _VariantSetStorage.Cocoa(let rhsCocoa)):
#if _runtime(_ObjC)
    let lhsNative = lhsNativeOwner.nativeStorage

    if lhsNative.count != rhsCocoa.count {
      return false
    }

    let endIndex = lhsNative.endIndex
    for var i = lhsNative.startIndex; i != endIndex; ++i {
      let key = lhsNative.assertingGet(i)
      let bridgedKey: AnyObject = _bridgeToObjectiveCUnconditional(key)
      let optRhsValue: AnyObject? = rhsCocoa.maybeGet(bridgedKey)
      if let rhsValue = optRhsValue {
        if key == _forceBridgeFromObjectiveC(rhsValue, Element.self) {
          continue
        }
      }
      return false
    }
    return true
#else
      _sanityCheckFailure("internal error: unexpected cocoa set")
#endif

  case (_VariantSetStorage.Cocoa, _VariantSetStorage.Native):
#if _runtime(_ObjC)
    return rhs == lhs
#else
      _sanityCheckFailure("internal error: unexpected cocoa set")
#endif
  }
}

extension Set : CustomStringConvertible, CustomDebugStringConvertible {
  @warn_unused_result
  private func makeDescription(isDebug isDebug: Bool) -> String {
    var result = isDebug ? "Set([" : "["
    var first = true
    for member in self {
      if first {
        first = false
      } else {
        result += ", "
      }
      debugPrint(member, terminator: "", toStream: &result)
    }
    result += isDebug ? "])" : "]"
    return result
  }

  /// A textual representation of `self`.
  public var description: String {
    return makeDescription(isDebug: false)
  }

  /// A textual representation of `self`, suitable for debugging.
  public var debugDescription: String {
    return makeDescription(isDebug: true)
  }
}

#if _runtime(_ObjC)
@_silgen_name("swift_stdlib_CFSetGetValues")
func _stdlib_CFSetGetValues(nss: _NSSetType, _: UnsafeMutablePointer<AnyObject>)

/// Equivalent to `NSSet.allObjects`, but does not leave objects on the
/// autorelease pool.
internal func _stdlib_NSSet_allObjects(nss: _NSSetType) ->
  _HeapBuffer<Int, AnyObject> {
  let count = nss.count
  let buffer = _HeapBuffer<Int, AnyObject>(
    _HeapBufferStorage<Int, AnyObject>.self, count, count)
  _stdlib_CFSetGetValues(nss, buffer.baseAddress)
  return buffer
}
#endif

//===--- Compiler conversion/casting entry points for Set<Element> --------===//

#if _runtime(_ObjC)
/// Perform a non-bridged upcast that always succeeds.
///
/// - Requires: `BaseValue` is a base class or base `@objc`
///   protocol (such as `AnyObject`) of `DerivedValue`.
@warn_unused_result
public func _setUpCast<DerivedValue, BaseValue>(source: Set<DerivedValue>)
  -> Set<BaseValue> {
  _sanityCheck(_isClassOrObjCExistential(BaseValue.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedValue.self))

  var builder = _SetBuilder<BaseValue>(count: source.count)
  for member in source {
    builder.add(member: unsafeBitCast(member, BaseValue.self))
  }
  return builder.take()
}

/// Implements an unconditional upcast that involves bridging.
///
/// The cast can fail if bridging fails.
///
/// - Precondition: `SwiftValue` is bridged to Objective-C
///   and requires non-trivial bridging.
@warn_unused_result
public func _setBridgeToObjectiveC<SwiftValue, ObjCValue>(
  source: Set<SwiftValue>
) -> Set<ObjCValue> {
  _sanityCheck(_isClassOrObjCExistential(ObjCValue.self))
  _sanityCheck(!_isBridgedVerbatimToObjectiveC(SwiftValue.self))

  var result = Set<ObjCValue>(minimumCapacity: source.count)
  let valueBridgesDirectly =
    _isBridgedVerbatimToObjectiveC(SwiftValue.self) ==
    _isBridgedVerbatimToObjectiveC(ObjCValue.self)
  for member in source {
    var bridgedMember: ObjCValue
    if valueBridgesDirectly {
      bridgedMember = unsafeBitCast(member, ObjCValue.self)
    } else {
      let bridged: AnyObject? = _bridgeToObjectiveC(member)
      _precondition(bridged != nil,
      "set member cannot be bridged to Objective-C")
      bridgedMember = unsafeBitCast(bridged!, ObjCValue.self)
    }
    result.insert(bridgedMember)
  }
  return result
}

/// Implements a forced downcast.  This operation should have O(1) complexity.
///
/// The cast can fail if bridging fails.  The actual checks and bridging can be
/// deferred.
///
/// - Precondition: `DerivedValue` is a subtype of `BaseValue` and both
///   are reference types.
@warn_unused_result
public func _setDownCast<BaseValue, DerivedValue>(source: Set<BaseValue>)
  -> Set<DerivedValue> {

  _sanityCheck(_isClassOrObjCExistential(BaseValue.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedValue.self))

  switch source._variantStorage {
  case _VariantSetStorage.Native(let nativeOwner):
    return Set(
    _immutableCocoaSet:
    unsafeBitCast(nativeOwner, _NSSetType.self))

  case _VariantSetStorage.Cocoa(let cocoaStorage):
    return Set(
    _immutableCocoaSet:
    unsafeBitCast(cocoaStorage, _NSSetType.self))
  }
}

/// Implements a conditional downcast.
///
/// If the cast fails, the function returns `.None`.  All checks should be
/// performed eagerly.
///
/// - Precondition: `DerivedValue` is a subtype of `BaseValue` and both
///   are reference types.
@warn_unused_result
public func _setDownCastConditional<BaseValue, DerivedValue>(
  source: Set<BaseValue>
) -> Set<DerivedValue>? {
  _sanityCheck(_isClassOrObjCExistential(BaseValue.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedValue.self))

  var result = Set<DerivedValue>(minimumCapacity: source.count)
  for member in source {
    if let derivedMember = member as? DerivedValue {
      result.insert(derivedMember)
      continue
    }
    return .None
  }
  return result
}

/// Implements an unconditional downcast that involves bridging.
///
/// - Precondition: At least one of `SwiftValue` is a bridged value
///   type, and the corresponding `ObjCValue` is a reference type.
@warn_unused_result
public func _setBridgeFromObjectiveC<ObjCValue, SwiftValue>(
  source: Set<ObjCValue>
) -> Set<SwiftValue> {
  let result: Set<SwiftValue>? = _setBridgeFromObjectiveCConditional(source)
  _precondition(result != nil, "This set cannot be bridged from Objective-C")
  return result!
}

/// Implements a conditional downcast that involves bridging.
///
/// If the cast fails, the function returns `.None`.  All checks should be
/// performed eagerly.
///
/// - Precondition: At least one of `SwiftValue` is a bridged value
///   type, and the corresponding `ObjCValue` is a reference type.
@warn_unused_result
public func _setBridgeFromObjectiveCConditional<
  ObjCValue, SwiftValue
>(
  source: Set<ObjCValue>
) -> Set<SwiftValue>? {
  _sanityCheck(_isClassOrObjCExistential(ObjCValue.self))
  _sanityCheck(!_isBridgedVerbatimToObjectiveC(SwiftValue.self))

  let valueBridgesDirectly =
    _isBridgedVerbatimToObjectiveC(SwiftValue.self) ==
      _isBridgedVerbatimToObjectiveC(ObjCValue.self)

  var result = Set<SwiftValue>(minimumCapacity: source.count)
  for value in source {
    // Downcast the value.
    var resultValue: SwiftValue
    if valueBridgesDirectly {
      if let bridgedValue = value as? SwiftValue {
        resultValue = bridgedValue
      } else {
        return nil
      }
    } else {
      if let bridgedValue = _conditionallyBridgeFromObjectiveC(
          _reinterpretCastToAnyObject(value), SwiftValue.self) {
        resultValue = bridgedValue
      } else {
        return nil
      }
    }
    result.insert(resultValue)
  }
  return result
}
#endif

//===--- APIs unique to Dictionary<Key, Value> ----------------------------===//

/// A hash-based mapping from `Key` to `Value` instances.  Also a
/// collection of key-value pairs with no defined ordering.
public struct Dictionary<Key : Hashable, Value> :
  CollectionType, DictionaryLiteralConvertible {

  internal typealias _Self = Dictionary<Key, Value>
  internal typealias _VariantStorage = _VariantDictionaryStorage<Key, Value>
  internal typealias _NativeStorage = _NativeDictionaryStorage<Key, Value>
  public typealias Element = (Key, Value)
  public typealias Index = DictionaryIndex<Key, Value>

  internal var _variantStorage: _VariantStorage

  /// Create an empty dictionary.
  public init() {
    self = Dictionary<Key, Value>(minimumCapacity: 0)
  }

  /// Create a dictionary with at least the given number of
  /// elements worth of storage.  The actual capacity will be the
  /// smallest power of 2 that's >= `minimumCapacity`.
  public init(minimumCapacity: Int) {
    _variantStorage =
      .Native(_NativeStorage.Owner(minimumCapacity: minimumCapacity))
  }

  /// Private initializer.
  internal init(_nativeStorage: _NativeDictionaryStorage<Key, Value>) {
    _variantStorage =
      .Native(_NativeStorage.Owner(nativeStorage: _nativeStorage))
  }

  /// Private initializer.
  internal init(_nativeStorageOwner:
    _NativeDictionaryStorageOwner<Key, Value>) {
    _variantStorage = .Native(_nativeStorageOwner)
  }

#if _runtime(_ObjC)
  /// Private initializer used for bridging.
  ///
  /// Only use this initializer when both conditions are true:
  ///
  /// * it is statically known that the given `NSDictionary` is immutable;
  /// * `Key` and `Value` are bridged verbatim to Objective-C (i.e.,
  ///   are reference types).
  public init(_immutableCocoaDictionary: _NSDictionaryType) {
    _sanityCheck(
      _isBridgedVerbatimToObjectiveC(Key.self) &&
      _isBridgedVerbatimToObjectiveC(Value.self),
      "Dictionary can be backed by NSDictionary storage only when both key and value are bridged verbatim to Objective-C")
    _variantStorage = .Cocoa(
      _CocoaDictionaryStorage(cocoaDictionary: _immutableCocoaDictionary))
  }
#endif

  //
  // All APIs below should dispatch to `_variantStorage`, without doing any
  // additional processing.
  //

  /// The position of the first element in a non-empty dictionary.
  ///
  /// Identical to `endIndex` in an empty dictionary.
  ///
  /// - Complexity: Amortized O(1) if `self` does not wrap a bridged
  ///   `NSDictionary`, O(N) otherwise.
  public var startIndex: Index {
    return _variantStorage.startIndex
  }

  /// The collection's "past the end" position.
  ///
  /// `endIndex` is not a valid argument to `subscript`, and is always
  /// reachable from `startIndex` by zero or more applications of
  /// `successor()`.
  ///
  /// - Complexity: Amortized O(1) if `self` does not wrap a bridged
  ///   `NSDictionary`, O(N) otherwise.
  public var endIndex: Index {
    return _variantStorage.endIndex
  }

  /// Returns the `Index` for the given key, or `nil` if the key is not
  /// present in the dictionary.
  @warn_unused_result
  public func indexForKey(key: Key) -> Index? {
    // Complexity: amortized O(1) for native storage, O(N) when wrapping an
    // NSDictionary.
    return _variantStorage.indexForKey(key)
  }

  /// Access the key-value pair at `position`.
  ///
  /// - Complexity: O(1).
  public subscript(position: Index) -> Element {
    return _variantStorage.assertingGet(position)
  }

  /// Access the value associated with the given key.
  ///
  /// Reading a key that is not present in `self` yields `nil`.
  /// Writing `nil` as the value for a given key erases that key from
  /// `self`.
  public subscript(key: Key) -> Value? {
    get {
      return _variantStorage.maybeGet(key)
    }
    set(newValue) {
      if let x = newValue {
        // FIXME(performance): this loads and discards the old value.
        _variantStorage.updateValue(x, forKey: key)
      }
      else {
        // FIXME(performance): this loads and discards the old value.
        removeValueForKey(key)
      }
    }
  }

  /// Update the value stored in the dictionary for the given key, or, if they
  /// key does not exist, add a new key-value pair to the dictionary.
  ///
  /// Returns the value that was replaced, or `nil` if a new key-value pair
  /// was added.
  public mutating func updateValue(
    value: Value, forKey key: Key
  ) -> Value? {
    return _variantStorage.updateValue(value, forKey: key)
  }

  /// Remove the key-value pair at `index`.
  ///
  /// Invalidates all indices with respect to `self`.
  ///
  /// - Complexity: O(`self.count`).
  public mutating func removeAtIndex(index: Index) -> Element {
    return _variantStorage.removeAtIndex(index)
  }

  /// Remove a given key and the associated value from the dictionary.
  /// Returns the value that was removed, or `nil` if the key was not present
  /// in the dictionary.
  public mutating func removeValueForKey(key: Key) -> Value? {
    return _variantStorage.removeValueForKey(key)
  }

  /// Remove all elements.
  ///
  /// - Postcondition: `capacity == 0` if `keepCapacity` is `false`, otherwise
  ///   the capacity will not be decreased.
  ///
  /// Invalidates all indices with respect to `self`.
  ///
  /// - parameter keepCapacity: If `true`, the operation preserves the
  ///   storage capacity that the collection has, otherwise the underlying
  ///   storage is released.  The default is `false`.
  ///
  /// Complexity: O(`self.count`).
  public mutating func removeAll(keepCapacity keepCapacity: Bool = false) {
    // The 'will not decrease' part in the documentation comment is worded very
    // carefully.  The capacity can increase if we replace Cocoa storage with
    // native storage.
    _variantStorage.removeAll(keepCapacity: keepCapacity)
  }

  /// The number of entries in the dictionary.
  ///
  /// - Complexity: O(1).
  public var count: Int {
    return _variantStorage.count
  }

  //
  // `SequenceType` conformance
  //

  /// Return a *generator* over the (key, value) pairs.
  ///
  /// - Complexity: O(1).
  public func generate() -> DictionaryGenerator<Key, Value> {
    return _variantStorage.generate()
  }

  //
  // DictionaryLiteralConvertible conformance
  //

  /// Create an instance initialized with `elements`.
  @effects(readonly)
  public init(dictionaryLiteral elements: (Key, Value)...) {
    self.init(_nativeStorage: _NativeDictionaryStorage.fromArray(elements))
  }

  //
  // APIs below this comment should be implemented strictly in terms of
  // *public* APIs above.  `_variantStorage` should not be accessed directly.
  //
  // This separates concerns for testing.  Tests for the following APIs need
  // not to concern themselves with testing correctness of behavior of
  // underlying storage (and different variants of it), only correctness of the
  // API itself.
  //

  /// A collection containing just the keys of `self`.
  ///
  /// Keys appear in the same order as they occur as the `.0` member
  /// of key-value pairs in `self`.  Each key in the result has a
  /// unique value.
  public var keys: LazyMapCollection<Dictionary, Key> {
    return self.lazy.map { $0.0 }
  }

  /// A collection containing just the values of `self`.
  ///
  /// Values appear in the same order as they occur as the `.1` member
  /// of key-value pairs in `self`.
  public var values: LazyMapCollection<Dictionary, Value> {
    return self.lazy.map { $0.1 }
  }

  //
  // CollectionType conformance
  //

  /// `true` iff `count == 0`.
  public var isEmpty: Bool {
    return count == 0
  }

}

@warn_unused_result
public func == <Key : Equatable, Value : Equatable>(
  lhs: [Key : Value],
  rhs: [Key : Value]
) -> Bool {
  switch (lhs._variantStorage, rhs._variantStorage) {
  case (.Native(let lhsNativeOwner), .Native(let rhsNativeOwner)):
    let lhsNative = lhsNativeOwner.nativeStorage
    let rhsNative = rhsNativeOwner.nativeStorage
    // FIXME(performance): early exit if lhs and rhs reference the same
    // storage?

    if lhsNative.count != rhsNative.count {
      return false
    }

    for (k, v) in lhs {
      let (pos, found) = rhsNative._find(k, rhsNative._bucket(k))
      // FIXME: Can't write the simple code pending
      // <rdar://problem/15484639> Refcounting bug
      /*
      if !found || rhs[pos].value != lhsElement.value {
        return false
      }
      */
      if !found {
        return false
      }
      if rhsNative.valueAt(pos.offset) != v {
        return false
      }
    }
    return true

  case (.Cocoa(let lhsCocoa), .Cocoa(let rhsCocoa)):
#if _runtime(_ObjC)
    return _stdlib_NSObject_isEqual(
      lhsCocoa.cocoaDictionary, rhsCocoa.cocoaDictionary)
#else
      _sanityCheckFailure("internal error: unexpected cocoa dictionary")
#endif

  case (.Native(let lhsNativeOwner), .Cocoa(let rhsCocoa)):
#if _runtime(_ObjC)
    let lhsNative = lhsNativeOwner.nativeStorage

    if lhsNative.count != rhsCocoa.count {
      return false
    }

    let endIndex = lhsNative.endIndex
    for var index = lhsNative.startIndex; index != endIndex; ++index {
      let (key, value) = lhsNative.assertingGet(index)
      let optRhsValue: AnyObject? =
        rhsCocoa.maybeGet(_bridgeToObjectiveCUnconditional(key))
      if let rhsValue = optRhsValue {
        if value == _forceBridgeFromObjectiveC(rhsValue, Value.self) {
          continue
        }
      }
      return false
    }
    return true
#else
      _sanityCheckFailure("internal error: unexpected cocoa dictionary")
#endif

  case (.Cocoa, .Native):
#if _runtime(_ObjC)
    return rhs == lhs
#else
      _sanityCheckFailure("internal error: unexpected cocoa dictionary")
#endif
  }
}

@warn_unused_result
public func != <Key : Equatable, Value : Equatable>(
  lhs: [Key : Value],
  rhs: [Key : Value]
) -> Bool {
  return !(lhs == rhs)
}

extension Dictionary : CustomStringConvertible, CustomDebugStringConvertible {
  @warn_unused_result
  internal func _makeDescription() -> String {
    if count == 0 {
      return "[:]"
    }

    var result = "["
    var first = true
    for (k, v) in self {
      if first {
        first = false
      } else {
        result += ", "
      }
      debugPrint(k, terminator: "", toStream: &result)
      result += ": "
      debugPrint(v, terminator: "", toStream: &result)
    }
    result += "]"
    return result
  }

  /// A textual representation of `self`.
  public var description: String {
    return _makeDescription()
  }

  /// A textual representation of `self`, suitable for debugging.
  public var debugDescription: String {
    return _makeDescription()
  }
}

#if _runtime(_ObjC)
/// Equivalent to `NSDictionary.allKeys`, but does not leave objects on the
/// autorelease pool.
@warn_unused_result
internal func _stdlib_NSDictionary_allKeys(nsd: _NSDictionaryType)
    -> _HeapBuffer<Int, AnyObject> {
  let count = nsd.count
  let buffer = _HeapBuffer<Int, AnyObject>(
    _HeapBufferStorage<Int, AnyObject>.self, count, count)

  nsd.getObjects(nil, andKeys: buffer.baseAddress)
  return buffer
}
#endif

//===--- Compiler conversion/casting entry points for Dictionary<Key, Value> =//

#if _runtime(_ObjC)
/// Perform a non-bridged upcast that always succeeds.
///
/// - Requires: `BaseKey` and `BaseValue` are base classes or base `@objc`
///   protocols (such as `AnyObject`) of `DerivedKey` and `DerivedValue`,
///   respectively.
@warn_unused_result
public func _dictionaryUpCast<DerivedKey, DerivedValue, BaseKey, BaseValue>(
    source: Dictionary<DerivedKey, DerivedValue>
) -> Dictionary<BaseKey, BaseValue> {
  // FIXME: This crappy implementation is O(n) because it copies the
  // data; a proper implementation would be O(1).

  _sanityCheck(_isClassOrObjCExistential(BaseKey.self))
  _sanityCheck(_isClassOrObjCExistential(BaseValue.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedKey.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedValue.self))

  var result = Dictionary<BaseKey, BaseValue>(minimumCapacity: source.count)
  for (k, v) in source {
    result[unsafeBitCast(k, BaseKey.self)] = unsafeBitCast(v, BaseValue.self)
  }
  return result
}

/// Implements an unconditional upcast that involves bridging.
///
/// The cast can fail if bridging fails.
///
/// - Precondition: `SwiftKey` and `SwiftValue` are bridged to Objective-C,
///   and at least one of them requires non-trivial bridging.
@warn_unused_result
@inline(never)
@_semantics("stdlib_binary_only")
public func _dictionaryBridgeToObjectiveC<
  SwiftKey, SwiftValue, ObjCKey, ObjCValue
>(
  source: Dictionary<SwiftKey, SwiftValue>
) -> Dictionary<ObjCKey, ObjCValue> {

  // Note: We force this function to stay in the swift dylib because
  // it is not performance sensitive and keeping it in the dylib saves
  // a new kilobytes for each specialization for all users of dictionary.

  _sanityCheck(
    !_isBridgedVerbatimToObjectiveC(SwiftKey.self) ||
    !_isBridgedVerbatimToObjectiveC(SwiftValue.self))
  _sanityCheck(
    _isClassOrObjCExistential(ObjCKey.self) ||
    _isClassOrObjCExistential(ObjCValue.self))

  var result = Dictionary<ObjCKey, ObjCValue>(minimumCapacity: source.count)
  let keyBridgesDirectly =
    _isBridgedVerbatimToObjectiveC(SwiftKey.self) ==
      _isBridgedVerbatimToObjectiveC(ObjCKey.self)
  let valueBridgesDirectly =
    _isBridgedVerbatimToObjectiveC(SwiftValue.self) ==
      _isBridgedVerbatimToObjectiveC(ObjCValue.self)
  for (key, value) in source {
    // Bridge the key
    var bridgedKey: ObjCKey
    if keyBridgesDirectly {
      bridgedKey = unsafeBitCast(key, ObjCKey.self)
    } else {
      let bridged: AnyObject? = _bridgeToObjectiveC(key)
      _precondition(bridged != nil, "dictionary key cannot be bridged to Objective-C")
      bridgedKey = unsafeBitCast(bridged!, ObjCKey.self)
    }

    // Bridge the value
    var bridgedValue: ObjCValue
    if valueBridgesDirectly {
      bridgedValue = unsafeBitCast(value, ObjCValue.self)
    } else {
      let bridged: AnyObject? = _bridgeToObjectiveC(value)
      _precondition(bridged != nil,
          "dictionary value cannot be bridged to Objective-C")
      bridgedValue = unsafeBitCast(bridged!, ObjCValue.self)
    }

    result[bridgedKey] = bridgedValue
  }

  return result
}

/// Implements a forced downcast.  This operation should have O(1) complexity.
///
/// The cast can fail if bridging fails.  The actual checks and bridging can be
/// deferred.
///
/// - Precondition: `DerivedKey` is a subtype of `BaseKey`, `DerivedValue` is
///   a subtype of `BaseValue`, and all of these types are reference types.
@warn_unused_result
public func _dictionaryDownCast<BaseKey, BaseValue, DerivedKey, DerivedValue>(
  source: Dictionary<BaseKey, BaseValue>
) -> Dictionary<DerivedKey, DerivedValue> {
  _sanityCheck(_isClassOrObjCExistential(BaseKey.self))
  _sanityCheck(_isClassOrObjCExistential(BaseValue.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedKey.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedValue.self))

  switch source._variantStorage {
  case .Native(let nativeOwner):
    // FIXME(performance): this introduces an indirection through Objective-C
    // runtime, even though we access native storage.  But we can not
    // unsafeBitCast the owner object, because that would change the generic
    // arguments.
    //
    // One way to solve this is to add a third, read-only, representation to
    // variant storage: like _NativeDictionaryStorageOwner, but it would
    // perform casts when accessing elements.
    //
    // Note: it is safe to treat the storage as immutable here because
    // Dictionary will not mutate storage with reference count greater than 1.
    return Dictionary(
      _immutableCocoaDictionary:
        unsafeBitCast(nativeOwner, _NSDictionaryType.self))

  case .Cocoa(let cocoaStorage):
    return Dictionary(
      _immutableCocoaDictionary:
        unsafeBitCast(cocoaStorage, _NSDictionaryType.self))
  }
}

/// Implements a conditional downcast.
///
/// If the cast fails, the function returns `.None`.  All checks should be
/// performed eagerly.
///
/// - Precondition: `DerivedKey` is a subtype of `BaseKey`, `DerivedValue` is
///   a subtype of `BaseValue`, and all of these types are reference types.
@warn_unused_result
public func _dictionaryDownCastConditional<
  BaseKey, BaseValue, DerivedKey, DerivedValue
>(
  source: Dictionary<BaseKey, BaseValue>
) -> Dictionary<DerivedKey, DerivedValue>? {
  _sanityCheck(_isClassOrObjCExistential(BaseKey.self))
  _sanityCheck(_isClassOrObjCExistential(BaseValue.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedKey.self))
  _sanityCheck(_isClassOrObjCExistential(DerivedValue.self))

  var result = Dictionary<DerivedKey, DerivedValue>()
  for (key, value) in source {
    if let derivedKey = key as? DerivedKey {
      if let derivedValue = value as? DerivedValue {
        result[derivedKey] = derivedValue
        continue
      }
    }

    // Either the key or the value wasn't of the appropriate derived
    // type. Fail.
    return nil
  }
  return result
}

/// Implements an unconditional downcast that involves bridging.
///
/// - Precondition: At least one of `SwiftKey` or `SwiftValue` is a bridged value
///   type, and the corresponding `ObjCKey` or `ObjCValue` is a reference type.
@warn_unused_result
public func _dictionaryBridgeFromObjectiveC<
  ObjCKey, ObjCValue, SwiftKey, SwiftValue
>(
  source: Dictionary<ObjCKey, ObjCValue>
) -> Dictionary<SwiftKey, SwiftValue> {
  let result: Dictionary<SwiftKey, SwiftValue>? =
    _dictionaryBridgeFromObjectiveCConditional(source)
  _precondition(result != nil, "dictionary cannot be bridged from Objective-C")
  return result!
}

/// Implements a conditional downcast that involves bridging.
///
/// If the cast fails, the function returns `.None`.  All checks should be
/// performed eagerly.
///
/// - Precondition: At least one of `SwiftKey` or `SwiftValue` is a bridged value
///   type, and the corresponding `ObjCKey` or `ObjCValue` is a reference type.
@warn_unused_result
public func _dictionaryBridgeFromObjectiveCConditional<
  ObjCKey, ObjCValue, SwiftKey, SwiftValue
>(
  source: Dictionary<ObjCKey, ObjCValue>
) -> Dictionary<SwiftKey, SwiftValue>? {
  _sanityCheck(
    _isClassOrObjCExistential(ObjCKey.self) ||
    _isClassOrObjCExistential(ObjCValue.self))
  _sanityCheck(
    !_isBridgedVerbatimToObjectiveC(SwiftKey.self) ||
    !_isBridgedVerbatimToObjectiveC(SwiftValue.self))

  let keyBridgesDirectly =
    _isBridgedVerbatimToObjectiveC(SwiftKey.self) ==
      _isBridgedVerbatimToObjectiveC(ObjCKey.self)
  let valueBridgesDirectly =
    _isBridgedVerbatimToObjectiveC(SwiftValue.self) ==
      _isBridgedVerbatimToObjectiveC(ObjCValue.self)

  var result = Dictionary<SwiftKey, SwiftValue>(minimumCapacity: source.count)
  for (key, value) in source {
    // Downcast the key.
    var resultKey: SwiftKey
    if keyBridgesDirectly {
      if let bridgedKey = key as? SwiftKey {
        resultKey = bridgedKey
      } else {
        return nil
      }
    } else {
      if let bridgedKey = _conditionallyBridgeFromObjectiveC(
        _reinterpretCastToAnyObject(key), SwiftKey.self) {
          resultKey = bridgedKey
      } else {
        return nil
      }
    }

    // Downcast the value.
    var resultValue: SwiftValue
    if valueBridgesDirectly {
      if let bridgedValue = value as? SwiftValue {
        resultValue = bridgedValue
      } else {
        return nil
      }
    } else {
      if let bridgedValue = _conditionallyBridgeFromObjectiveC(
        _reinterpretCastToAnyObject(value), SwiftValue.self) {
          resultValue = bridgedValue
      } else {
        return nil
      }
    }

    result[resultKey] = resultValue
  }
  return result
}
#endif

//===--- APIs templated for Dictionary and Set ----------------------------===//

%{
# Tuple items:
# Self: Class name
#
# a_Self: Class name when using an indefinite article
#
# TypeParametersDecl: Generic parameters appearing in top-level declarations
#
# TypeParameters: Generic parameters appearing in typealiases, etc.
#
# AnyTypeParameters: Generic parameters where all variables are AnyObject
#
# SequenceType: The type of things appearing in the collection as a sequence
#                 e.g. dictionaries are a sequence of (Key, Value) pairs.
# AnySequenceType: The same as SequenceType but everything is an AnyObject.
collections = [
  ('Set',
   'a Set',
   'Element : Hashable',
   'Element',
   'AnyObject',
   'Element',
   'AnyObject'),

  ('Dictionary',
   'a Dictionary',
   'Key : Hashable, Value',
   'Key, Value',
   'AnyObject, AnyObject',
   '(Key, Value)',
   '(AnyObject, AnyObject)'),
]
}%

/// A wrapper around a bitmap storage with room for at least bitCount bits.
internal struct _BitMap {
  internal let values: UnsafeMutablePointer<UInt>
  internal let bitCount: Int

  // Note: We use UInt here to get unsigned math (shifts).
  @warn_unused_result
  internal static func wordIndex(i: UInt) -> UInt {
    return i / UInt._sizeInBits
  }

  @warn_unused_result
  internal static func bitIndex(i: UInt) -> UInt {
    return i % UInt._sizeInBits
  }

  @warn_unused_result
  internal static func wordsFor(bitCount: Int) -> Int {
    return bitCount + Int._sizeInBytes - 1 / Int._sizeInBytes
  }

  internal init(storage: UnsafeMutablePointer<UInt>, bitCount: Int) {
    self.bitCount = bitCount
    self.values = storage
  }

  internal var numberOfWords: Int {
    @warn_unused_result
    get {
      return _BitMap.wordsFor(bitCount)
    }
  }

  internal func initializeToZero() {
    for i in 0 ..< numberOfWords {
      (values + i).initialize(0)
    }
  }

  internal subscript(i: Int) -> Bool {
    @warn_unused_result
    get {
      _sanityCheck(i < Int(bitCount) && i >= 0, "index out of bounds")
      let idx = UInt(i)
      let word = values[Int(_BitMap.wordIndex(idx))]
      let bit = word & (1 << _BitMap.bitIndex(idx))
      return bit != 0
    }
    nonmutating set {
      _sanityCheck(i < Int(bitCount) && i >= 0, "index out of bounds")
      let idx = UInt(i)
      let wordIdx = _BitMap.wordIndex(idx)
      if newValue {
        values[Int(wordIdx)] =
            values[Int(wordIdx)] | (1 << _BitMap.bitIndex(idx))
      } else {
        values[Int(wordIdx)] =
            values[Int(wordIdx)] & ~(1 << _BitMap.bitIndex(idx))
      }
    }
  }
}

/// Header part of the native storage.
internal struct _HashedContainerStorageHeader {
  internal init(capacity: Int) {
    self.capacity = capacity
  }

  internal var capacity: Int
  internal var count: Int = 0
  internal var maxLoadFactorInverse: Double =
    _hashContainerDefaultMaxLoadFactorInverse
}

% for (Self, a_Self, TypeParametersDecl, TypeParameters, AnyTypeParameters, SequenceType, AnySequenceType) in collections:

/// An instance of this class has all `${Self}` data tail-allocated.
/// Enough bytes are allocated to hold the bitmap for marking valid entries,
/// keys, and values. The data layout starts with the bitmap, followed by the
/// keys, followed by the values.
final internal class _Native${Self}StorageImpl<${TypeParameters}> :
  ManagedBuffer<_HashedContainerStorageHeader, UInt8> {
  // Note: It is intended that ${TypeParameters}
  // (without : Hashable) is used here - this storage must work
  // with non-Hashable types.

  internal typealias BufferPointer =
    ManagedBufferPointer<_HashedContainerStorageHeader, UInt8>
  internal typealias StorageImpl = _Native${Self}StorageImpl

%if Self == 'Set': # Set needs these to keep signatures simple.
  internal typealias Key = ${TypeParameters}
%end

  /// Returns the bytes necessary to store a bit map of 'capacity' bytes and
  /// padding to align the start to word alignment.
  @warn_unused_result
  internal static func bytesForBitMap(capacity: Int) -> Int {
    let numWords = _BitMap.wordsFor(capacity)
    return numWords * sizeof(UInt) + alignof(UInt)
  }

  /// Returns the bytes necessary to store 'capacity' keys and padding to align
  /// the start to the alignment of the 'Key' type assuming a word aligned base
  /// address.
  @warn_unused_result
  internal static func bytesForKeys(capacity: Int) -> Int {
    let padding = max(0, alignof(Key.self) - alignof(UInt))
    return strideof(Key.self) * capacity + padding
  }

  /// Returns the bytes necessary to store 'capacity' values and padding to
  /// align the start to the alignment of the 'Value' type assuming a base
  /// address aligned to the maximum of the alignment of the 'Key' type and the
  /// alignment of a word.

%if Self == 'Dictionary':
  @warn_unused_result
  internal static func bytesForValues(capacity: Int) -> Int {
    let maxPrevAlignment = max(alignof(Key.self), alignof(UInt))
    let padding = max(0, alignof(Value.self) - maxPrevAlignment)
    return strideof(Value.self) * capacity + padding
  }
%end

  internal var buffer: BufferPointer {
    @warn_unused_result
    get {
      return BufferPointer(self)
    }
  }

  // All underscored functions are unsafe and need a _fixLifetime in the caller.
  internal var _body: _HashedContainerStorageHeader {
    unsafeAddress {
      return UnsafePointer(buffer._valuePointer)
    }
    unsafeMutableAddress {
      return buffer._valuePointer
    }
  }

  internal var _capacity: Int {
    @warn_unused_result
    get {
      return _body.capacity
    }
  }

  internal var _count: Int {
    set {
      _body.count = newValue
    }
    @warn_unused_result
    get {
      return _body.count
    }
  }

  internal var _maxLoadFactorInverse : Double {
    @warn_unused_result
    get {
      return _body.maxLoadFactorInverse
    }
  }

  internal
  var _initializedHashtableEntriesBitMapStorage: UnsafeMutablePointer<UInt> {
    @warn_unused_result
    get {
      let start = UInt(Builtin.ptrtoint_Word(buffer._elementPointer._rawValue))
      let alignment = UInt(alignof(UInt))
      let alignMask = alignment &- UInt(1)
      return UnsafeMutablePointer<UInt>(
          bitPattern:(start &+ alignMask) & ~alignMask)
    }
  }

  internal var _keys: UnsafeMutablePointer<Key> {
    @warn_unused_result
    get {
      let start =
          UInt(Builtin.ptrtoint_Word(
              _initializedHashtableEntriesBitMapStorage._rawValue)) &+
          UInt(_BitMap.wordsFor(_capacity)) &* UInt(strideof(UInt))
      let alignment = UInt(alignof(Key))
      let alignMask = alignment &- UInt(1)
      return UnsafeMutablePointer<Key>(
          bitPattern:(start &+ alignMask) & ~alignMask)
    }
  }

%if Self == 'Dictionary':
  internal var _values: UnsafeMutablePointer<Value> {
    @warn_unused_result
    get {
      let start = UInt(Builtin.ptrtoint_Word(_keys._rawValue)) &+
        UInt(_capacity) &* UInt(strideof(Key.self))
      let alignment = UInt(alignof(Value))
      let alignMask = alignment &- UInt(1)
      return UnsafeMutablePointer<Value>(
          bitPattern:(start &+ alignMask) & ~alignMask)
    }
  }
%end

  /// Create a storage instance with room for 'capacity' entries and all entries
  /// marked invalid.
  internal class func create(capacity: Int) -> StorageImpl {
    let requiredCapacity = bytesForBitMap(capacity) + bytesForKeys(capacity)
%if Self == 'Dictionary':
        + bytesForValues(capacity)
%end

    let r = super.create(requiredCapacity) { _ in
      return _HashedContainerStorageHeader(capacity: capacity)
    }
    let storage = r as! StorageImpl
    let initializedEntries = _BitMap(
        storage: storage._initializedHashtableEntriesBitMapStorage,
        bitCount: capacity)
    initializedEntries.initializeToZero()
    return storage
  }

  deinit {
    let capacity = _capacity
    let initializedEntries = _BitMap(
        storage: _initializedHashtableEntriesBitMapStorage, bitCount: capacity)
    let keys = _keys
%if Self == 'Dictionary':
    let values = _values
%end

    if !_isPOD(Key.self) {
      for i in 0 ..< capacity {
        if initializedEntries[i] {
          (keys+i).destroy()
        }
      }
    }

%if Self == 'Dictionary':
    if !_isPOD(Value.self) {
      for i in 0 ..< capacity {
        if initializedEntries[i] {
          (values+i).destroy()
        }
      }
    }
%end
    buffer._valuePointer.destroy()
    _fixLifetime(self)
  }
}

public // @testable
struct _Native${Self}Storage<${TypeParametersDecl}> :
  _HashStorageType, CustomStringConvertible {
  internal typealias Owner = _Native${Self}StorageOwner<${TypeParameters}>
  internal typealias StorageImpl = _Native${Self}StorageImpl<${TypeParameters}>
  internal typealias SequenceElement = ${SequenceType}
  internal typealias Storage = _Native${Self}Storage<${TypeParameters}>

%if Self == 'Set': # Set needs these to keep signatures simple.
  internal typealias Key = ${TypeParameters}
  internal typealias Value = ${TypeParameters}
%end

  internal let buffer: StorageImpl

  internal let initializedEntries: _BitMap
  internal let keys: UnsafeMutablePointer<Key>
%if Self == 'Dictionary':
  internal let values: UnsafeMutablePointer<Value>
%end

  internal init(capacity: Int) {
    buffer = StorageImpl.create(capacity)
    initializedEntries = _BitMap(
        storage: buffer._initializedHashtableEntriesBitMapStorage,
        bitCount: capacity)
    keys = buffer._keys
%if Self == 'Dictionary':
    values = buffer._values
%end
    _fixLifetime(buffer)
  }

  internal init(minimumCapacity: Int = 2) {
    // Make sure there's a representable power of 2 >= minimumCapacity
    _sanityCheck(minimumCapacity <= (Int.max >> 1) + 1)

    var capacity = 2
    while capacity < minimumCapacity {
      capacity <<= 1
    }

    self = _Native${Self}Storage(capacity: capacity)
  }

  @_transparent
  public // @testable
  var capacity: Int {
    @warn_unused_result
    get {
      let c = buffer._capacity
      _fixLifetime(buffer)
      return c
    }
  }

  @_transparent
  internal var count: Int {
    @warn_unused_result
    get {
      let c  = buffer._count
      _fixLifetime(buffer)
      return c
    }
    nonmutating set(newValue) {
      buffer._count = newValue
      _fixLifetime(buffer)
    }
  }

  @_transparent
  internal var maxLoadFactorInverse: Double {
    @warn_unused_result
    get {
      let c = buffer._maxLoadFactorInverse
      _fixLifetime(buffer)
      return c
    }
  }

  @warn_unused_result
  internal func keyAt(i: Int) -> Key {
    _precondition(i >= 0 && i < capacity)
    _sanityCheck(isInitializedEntry(i))

    let res = (keys + i).memory
    _fixLifetime(self)
    return res
  }

  @warn_unused_result
  internal func isInitializedEntry(i: Int) -> Bool {
    _precondition(i >= 0 && i < capacity)
    return initializedEntries[i]
  }

  @_transparent
  internal func destroyEntryAt(i: Int) {
    _sanityCheck(isInitializedEntry(i))
    (keys + i).destroy()
%if Self == 'Dictionary':
    (values + i).destroy()
%end
    initializedEntries[i] = false
    _fixLifetime(self)
  }

%if Self == 'Set':
  @_transparent
  internal func initializeKey(k: Key, at i: Int) {
    _sanityCheck(!isInitializedEntry(i))

    (keys + i).initialize(k)
    initializedEntries[i] = true
    _fixLifetime(self)
  }

  @_transparent
  internal func moveInitializeFrom(from: Storage, at: Int, toEntryAt: Int) {
    _sanityCheck(!isInitializedEntry(toEntryAt))
    (keys + toEntryAt).initialize((from.keys + at).move())
    from.initializedEntries[at] = false
    initializedEntries[toEntryAt] = true
  }

  internal func setKey(key: Key, at i: Int) {
    _precondition(i >= 0 && i < capacity)
    _sanityCheck(isInitializedEntry(i))

    (keys + i).memory = key
    _fixLifetime(self)
  }

%elif Self == 'Dictionary':
  @_transparent
  internal func initializeKey(k: Key, value v: Value, at i: Int) {
    _sanityCheck(!isInitializedEntry(i))

    (keys + i).initialize(k)
    (values + i).initialize(v)
    initializedEntries[i] = true
    _fixLifetime(self)
  }

  @_transparent
  internal func moveInitializeFrom(from: Storage, at: Int, toEntryAt: Int) {
    _sanityCheck(!isInitializedEntry(toEntryAt))
    (keys + toEntryAt).initialize((from.keys + at).move())
    (values + toEntryAt).initialize((from.values + at).move())
    from.initializedEntries[at] = false
    initializedEntries[toEntryAt] = true
  }

  @_transparent
  @warn_unused_result
  internal func valueAt(i: Int) -> Value {
    _sanityCheck(isInitializedEntry(i))

    let res = (values + i).memory
    _fixLifetime(self)
    return res
  }

  @_transparent
  internal func setKey(key: Key, value: Value, at i: Int) {
    _sanityCheck(isInitializedEntry(i))
    (keys + i).memory = key
    (values + i).memory = value
    _fixLifetime(self)
  }

%end

  //
  // Implementation details
  //

  internal var _bucketMask: Int {
    // The capacity is not negative, therefore subtracting 1 will not overflow.
    return capacity &- 1
  }

  @warn_unused_result
  internal func _bucket(k: Key) -> Int {
    return _squeezeHashValue(k.hashValue, 0..<capacity)
  }

  @warn_unused_result
  internal func _next(bucket: Int) -> Int {
    // Bucket is within 0 and capacity. Therefore adding 1 does not overflow.
    return (bucket &+ 1) & _bucketMask
  }

  @warn_unused_result
  internal func _prev(bucket: Int) -> Int {
    // Bucket is not negative. Therefore subtracting 1 does not overflow.
    return (bucket &- 1) & _bucketMask
  }

  /// Search for a given key starting from the specified bucket.
  ///
  /// If the key is not present, returns the position where it could be
  /// inserted.
  @warn_unused_result
  internal
  func _find(key: Key, _ startBucket: Int) -> (pos: Index, found: Bool) {
    var bucket = startBucket

    // The invariant guarantees there's always a hole, so we just loop
    // until we find one
    while true {
      let isHole = !isInitializedEntry(bucket)
      if isHole {
        return (Index(nativeStorage: self, offset: bucket), false)
      }
      if keyAt(bucket) == key {
        return (Index(nativeStorage: self, offset: bucket), true)
      }
      bucket = _next(bucket)
    }
  }

  @_transparent
  @warn_unused_result
  internal static func getMinCapacity(
      requestedCount: Int, _ maxLoadFactorInverse: Double) -> Int {
    // `requestedCount + 1` below ensures that we don't fill in the last hole
    return max(Int(Double(requestedCount) * maxLoadFactorInverse),
               requestedCount + 1)
  }

  /// Storage should be uniquely referenced.
  /// The `key` should not be present in the ${Self}.
  /// This function does *not* update `count`.

%if Self == 'Set':

  internal mutating func unsafeAddNew(key newKey: Element) {
    let (i, found) = _find(newKey, _bucket(newKey))
    _sanityCheck(
      !found, "unsafeAddNew was called, but the key is already present")
    initializeKey(newKey, at: i.offset)
  }

%elif Self == 'Dictionary':

  internal mutating func unsafeAddNew(key newKey: Key, value: Value) {
    let (i, found) = _find(newKey, _bucket(newKey))
    _sanityCheck(
      !found, "unsafeAddNew was called, but the key is already present")
    initializeKey(newKey, value: value, at: i.offset)
  }

%end

  /// A textual representation of `self`.
  public // @testable
  var description: String {
    var result = ""
#if INTERNAL_CHECKS_ENABLED
    for var i = 0; i != capacity; ++i {
      if isInitializedEntry(i) {
        let key = keyAt(i)
        result += "bucket \(i), ideal bucket = \(_bucket(key)), key = \(key)\n"
      } else {
        result += "bucket \(i), empty\n"
      }
    }
#endif
    return result
  }

  //
  // _HashStorageType conformance
  //

  internal typealias Index = _Native${Self}Index<${TypeParameters}>

  internal var startIndex: Index {
    return Index(nativeStorage: self, offset: -1).successor()
  }

  internal var endIndex: Index {
    return Index(nativeStorage: self, offset: capacity)
  }

  @warn_unused_result
  internal func indexForKey(key: Key) -> Index? {
    if count == 0 {
      // Fast path that avoids computing the hash of the key.
      return .None
    }
    let (i, found) = _find(key, _bucket(key))
    return found ? i : .None
  }

  @warn_unused_result
  internal func assertingGet(i: Index) -> SequenceElement {
    _precondition(
      isInitializedEntry(i.offset),
      "attempting to access ${Self} elements using an invalid Index")
    let key = keyAt(i.offset)
%if Self == 'Set':
    return key
%elif Self == 'Dictionary':
    return (key, valueAt(i.offset))
%end

  }

  @warn_unused_result
  internal func assertingGet(key: Key) -> Value {
    let (i, found) = _find(key, _bucket(key))
    _precondition(found, "key not found")
%if Self == 'Set':
    return keyAt(i.offset)
%elif Self == 'Dictionary':
    return valueAt(i.offset)
%end
  }

  @warn_unused_result
  internal func maybeGet(key: Key) -> Value? {
    if count == 0 {
      // Fast path that avoids computing the hash of the key.
      return .None
    }

    let (i, found) = _find(key, _bucket(key))
    if found {
%if Self == 'Set':
      return keyAt(i.offset)
%elif Self == 'Dictionary':
      return valueAt(i.offset)
%end
    }
    return .None
  }

  internal mutating func updateValue(value: Value, forKey: Key) -> Value? {
    _sanityCheckFailure(
      "don't call mutating methods on _Native${Self}Storage")
  }

  internal mutating func removeAtIndex(index: Index) -> SequenceElement {
    _sanityCheckFailure(
      "don't call mutating methods on _Native${Self}Storage")
  }

  internal mutating func removeValueForKey(key: Key) -> Value? {
    _sanityCheckFailure(
      "don't call mutating methods on _Native${Self}Storage")
  }

  internal mutating func removeAll(keepCapacity keepCapacity: Bool) {
    _sanityCheckFailure(
      "don't call mutating methods on _Native${Self}Storage")
  }

  @warn_unused_result
  internal static func fromArray(elements: [SequenceElement])
    -> _Native${Self}Storage<${TypeParameters}> {

    let requiredCapacity =
      _Native${Self}Storage<${TypeParameters}>.getMinCapacity(
        elements.count, _hashContainerDefaultMaxLoadFactorInverse)
    let nativeStorage = _Native${Self}Storage<${TypeParameters}>(
      minimumCapacity: requiredCapacity)

%if Self == 'Set':

    var count = 0
    for key in elements {
      let (i, found) = nativeStorage._find(key, nativeStorage._bucket(key))
      if found {
        continue
      }
      nativeStorage.initializeKey(key, at: i.offset)
      ++count
    }
    nativeStorage.count = count

%elif Self == 'Dictionary':

    for (key, value) in elements {
      let (i, found) = nativeStorage._find(key, nativeStorage._bucket(key))
      _precondition(!found, "${Self} literal contains duplicate keys")
      nativeStorage.initializeKey(key, value: value, at: i.offset)
    }
    nativeStorage.count = elements.count

%end

    return nativeStorage
  }
}

#if _runtime(_ObjC)
/// Storage for bridged `${Self}` elements.  We could have used
/// `${Self}<${AnyTypeParameters}>`, but `AnyObject` can not be a Key because
/// it is not `Hashable`.
internal struct _BridgedNative${Self}Storage {
  internal typealias StorageImpl =
    _Native${Self}StorageImpl<${AnyTypeParameters}>
  internal typealias SequenceElement = ${AnySequenceType}

  internal let buffer: StorageImpl
  internal let initializedEntries: _BitMap
  internal let keys: UnsafeMutablePointer<AnyObject>
%if Self == 'Dictionary':
  internal let values: UnsafeMutablePointer<AnyObject>
%end


  internal init(buffer: StorageImpl) {
    self.buffer = buffer
    initializedEntries = _BitMap(
        storage: buffer._initializedHashtableEntriesBitMapStorage,
        bitCount: buffer._capacity)
    keys = buffer._keys
%if Self == 'Dictionary':
    values = buffer._values
%end
    _fixLifetime(buffer)
  }

  @_transparent
  internal var capacity: Int {
    get {
      let c = buffer._capacity
      _fixLifetime(buffer)
      return c
    }
  }

  internal func isInitializedEntry(i: Int) -> Bool {
    return initializedEntries[i]
  }

  internal func keyAt(i: Int) -> AnyObject {
    _precondition(i >= 0 && i < capacity)
    _sanityCheck(isInitializedEntry(i))

    let res = (keys + i).memory
    _fixLifetime(self)
    return res
  }

  internal func setKey(key: AnyObject, at i: Int) {
    _precondition(i >= 0 && i < capacity)
    _sanityCheck(isInitializedEntry(i))

    (keys + i).memory = key
    _fixLifetime(self)
  }

%if Self == 'Set':
  @_transparent
  internal func initializeKey(k: AnyObject, at i: Int) {
    _sanityCheck(!isInitializedEntry(i))

    (keys + i).initialize(k)
    initializedEntries[i] = true
    _fixLifetime(self)
  }
%elif Self == 'Dictionary':
  @_transparent
  internal func initializeKey(k: AnyObject, value v: AnyObject, at i: Int
  ) {
    _sanityCheck(!isInitializedEntry(i))

    (keys + i).initialize(k)
    (values + i).initialize(v)
    initializedEntries[i] = true
    _fixLifetime(self)
  }

  @_transparent
  @warn_unused_result
  internal func valueAt(i: Int) -> AnyObject {
    _sanityCheck(isInitializedEntry(i))
    let res = (values + i).memory
    _fixLifetime(self)
    return res
  }
%end

  @warn_unused_result
  internal func assertingGet(i: Int) -> SequenceElement {
    _precondition(
      isInitializedEntry(i),
      "attempting to access ${Self} elements using an invalid Index")
    let key = keyAt(i)
%if Self == 'Set':
    return key
%elif Self == 'Dictionary':
    return (key, valueAt(i))
%end
  }
}

final internal class _Native${Self}StorageKeyNSEnumerator<
  ${TypeParametersDecl}
>
  : _SwiftNativeNSEnumerator, _NSEnumeratorType {

  internal typealias NativeStorageOwner =
    _Native${Self}StorageOwner<${TypeParameters}>
  internal typealias Index = _Native${Self}Index<${TypeParameters}>

  internal override required init() {
    _sanityCheckFailure("don't call this designated initializer")
  }

  internal init(_ nativeStorageOwner: NativeStorageOwner) {
    self.nativeStorageOwner = nativeStorageOwner
    nextIndex = nativeStorageOwner.nativeStorage.startIndex
    endIndex = nativeStorageOwner.nativeStorage.endIndex
  }

  internal var nativeStorageOwner: NativeStorageOwner
  internal var nextIndex: Index
  internal var endIndex: Index

  //
  // NSEnumerator implementation.
  //
  // Do not call any of these methods from the standard library!
  //

  @objc
  @warn_unused_result
  internal func nextObject() -> AnyObject? {
    if nextIndex == endIndex {
      return nil
    }
    let bridgedKey: AnyObject = nativeStorageOwner._getBridgedKey(nextIndex)
    nextIndex = nextIndex.successor()
    return bridgedKey
  }

  @objc
  internal func countByEnumeratingWithState(
    state: UnsafeMutablePointer<_SwiftNSFastEnumerationState>,
    objects: UnsafeMutablePointer<AnyObject>,
    count: Int
  ) -> Int {
    var theState = state.memory
    if theState.state == 0 {
      theState.state = 1 // Arbitrary non-zero value.
      theState.itemsPtr = AutoreleasingUnsafeMutablePointer(objects)
      theState.mutationsPtr = _fastEnumerationStorageMutationsPtr
    }

    if nextIndex == endIndex {
      state.memory = theState
      return 0
    }

    // Return only a single element so that code can start iterating via fast
    // enumeration, terminate it, and continue via NSEnumerator.
    let bridgedKey: AnyObject = nativeStorageOwner._getBridgedKey(nextIndex)
    nextIndex = nextIndex.successor()

    let unmanagedObjects = _UnmanagedAnyObjectArray(objects)
    unmanagedObjects[0] = bridgedKey
    state.memory = theState
    return 1
  }
}
#endif

/// This class is an artifact of the COW implementation.  This class only
/// exists to keep separate retain counts separate for:
/// - `${Self}` and `NS${Self}`,
/// - `${Self}Index`.
///
/// This is important because the uniqueness check for COW only cares about
/// retain counts of the first kind.
///
/// Specifically, `${Self}` points to instances of this class.  This class
/// is also a proper `NS${Self}` subclass, which is returned to Objective-C
/// during bridging.  `${Self}Index` points directly to
/// `_Native${Self}Storage`.
final internal class _Native${Self}StorageOwner<${TypeParametersDecl}>
  : _SwiftNativeNS${Self}, _NS${Self}CoreType {

  internal typealias NativeStorage = _Native${Self}Storage<${TypeParameters}>
#if _runtime(_ObjC)
  internal typealias BridgedNativeStorage = _BridgedNative${Self}Storage
#endif

%if Self == 'Set':
  internal typealias Key = Element
  internal typealias Value = Element
%end

  internal init(minimumCapacity: Int = 2) {
    nativeStorage = NativeStorage(minimumCapacity: minimumCapacity)
    super.init()
  }

  internal init(nativeStorage: NativeStorage) {
    self.nativeStorage = nativeStorage
    super.init()
  }

  // This stored property should be stored at offset zero.  We perform atomic
  // operations on it.
  //
  // Do not access this property directly.
  internal var _heapBufferBridged_DoNotUse: AnyObject? = nil

  internal var nativeStorage: NativeStorage

#if _runtime(_ObjC)

%if Self == 'Set':

  //
  // NSSet implementation.
  //
  // Do not call any of these methods from the standard library!  Use only
  // `nativeStorage`.
  //

  @objc
  internal required init(objects: UnsafePointer<AnyObject?>, count: Int) {
    _sanityCheckFailure("don't call this designated initializer")
  }

  @objc
  @warn_unused_result
  internal func member(object: AnyObject) -> AnyObject? {
    return bridgingObjectForKey(object)
  }

  @objc
  @warn_unused_result
  internal func objectEnumerator() -> _NSEnumeratorType {
    return bridgingKeyEnumerator(())
  }

  @objc
  @warn_unused_result
  internal func copyWithZone(zone: _SwiftNSZone) -> AnyObject {
    // Instances of this class should be visible outside of standard library as
    // having `NSSet` type, which is immutable.
    return self
  }

%elif Self == 'Dictionary':
  //
  // NSDictionary implementation.
  //
  // Do not call any of these methods from the standard library!  Use only
  // `nativeStorage`.
  //

  @objc
  internal required init(
    objects: UnsafePointer<AnyObject?>,
    forKeys: UnsafePointer<Void>,
    count: Int
  ) {
    _sanityCheckFailure("don't call this designated initializer")
  }

  @objc
  internal func objectForKey(aKey: AnyObject) -> AnyObject? {
    return bridgingObjectForKey(aKey)
  }

  @objc
  internal func keyEnumerator() -> _NSEnumeratorType {
    return bridgingKeyEnumerator(())
  }

  @objc
  internal func copyWithZone(zone: _SwiftNSZone) -> AnyObject {
    // Instances of this class should be visible outside of standard library as
    // having `NSDictionary` type, which is immutable.
    return self
  }

  @objc
  internal func getObjects(
    objects: UnsafeMutablePointer<AnyObject>,
    andKeys keys: UnsafeMutablePointer<AnyObject>
  ) {
    bridgedAllKeysAndValues(objects, keys)
  }
%end

  /// Returns the pointer to the stored property, which contains bridged
  /// ${Self} elements.
  internal var _heapBufferBridgedPtr: UnsafeMutablePointer<AnyObject?> {
    return UnsafeMutablePointer(_getUnsafePointerToStoredProperties(self))
  }

  /// The storage for bridged ${Self} elements, if present.
  internal var _bridgedBuffer:
    BridgedNativeStorage.StorageImpl? {
    @warn_unused_result
    get {
      if let ref = _stdlib_atomicLoadARCRef(object: _heapBufferBridgedPtr) {
        return unsafeDowncast(ref) as BridgedNativeStorage.StorageImpl
      }
      return nil
    }
  }

  /// Attach a storage for bridged ${Self} elements.
  internal func _initializeHeapBufferBridged(newBuffer: AnyObject) {
    _stdlib_atomicInitializeARCRef(
      object: _heapBufferBridgedPtr, desired: newBuffer)
  }

  /// Detach the storage of bridged ${Self} elements.
  ///
  /// Call this before mutating the ${Self} storage owned by this owner.
  internal func deinitializeHeapBufferBridged() {
    // Perform a non-atomic store because storage should be
    // uniquely-referenced.
    _heapBufferBridgedPtr.memory = nil
  }

  /// Returns the bridged ${Self} values.
  internal var bridgedNativeStorage: BridgedNativeStorage {
    return BridgedNativeStorage(buffer: _bridgedBuffer!)
  }

  @warn_unused_result
  internal func _createBridgedNativeStorage(capacity: Int) ->
    BridgedNativeStorage {
    let buffer = BridgedNativeStorage.StorageImpl.create(capacity)
    return BridgedNativeStorage(buffer: buffer)
  }

  internal func bridgeEverything() {
    if _fastPath(_bridgedBuffer != nil) {
      return
    }

    // Create storage for bridged data.
    let bridged = _createBridgedNativeStorage(nativeStorage.capacity)

    // Bridge everything.
    for var i = 0; i < nativeStorage.capacity; ++i {
      if nativeStorage.isInitializedEntry(i) {
        let key = _bridgeToObjectiveCUnconditional(nativeStorage.keyAt(i))
%if Self == 'Set':
        bridged.initializeKey(key, at: i)
%elif Self == 'Dictionary':
        let val = _bridgeToObjectiveCUnconditional(nativeStorage.valueAt(i))
        bridged.initializeKey(key, value: val, at: i)
%end
      }
    }

    // Atomically put the bridged elements in place.
    _initializeHeapBufferBridged(bridged.buffer)
  }

  //
  // Entry points for bridging ${Self} elements.  In implementations of
  // Foundation subclasses (NS${Self}, NSEnumerator), don't access any
  // storage directly, use these functions.
  //
  @warn_unused_result
  internal func _getBridgedKey(i: _Native${Self}Index<${TypeParameters}>) ->
    AnyObject {
    if _fastPath(_isClassOrObjCExistential(Key.self)) {
%if Self == 'Set':
      return _bridgeToObjectiveCUnconditional(nativeStorage.assertingGet(i))
%elif Self == 'Dictionary':
      return _bridgeToObjectiveCUnconditional(nativeStorage.assertingGet(i).0)
%end
    }
    bridgeEverything()
%if Self == 'Set':
    return bridgedNativeStorage.assertingGet(i.offset)
%elif Self == 'Dictionary':
    return bridgedNativeStorage.assertingGet(i.offset).0
%end
  }

%if Self == 'Set':

  @warn_unused_result
  internal func _getBridgedValue(i: _Native${Self}Index<${TypeParameters}>) ->
    AnyObject {
    if _fastPath(_isClassOrObjCExistential(Value.self)) {
      return _bridgeToObjectiveCUnconditional(nativeStorage.assertingGet(i))
    }
    bridgeEverything()
    return bridgedNativeStorage.assertingGet(i.offset)
  }

%elif Self == 'Dictionary':

  @warn_unused_result
  internal func _getBridgedValue(i: _Native${Self}Index<${TypeParameters}>)
    -> AnyObject {
    if _fastPath(_isClassOrObjCExistential(Value.self)) {
      return _bridgeToObjectiveCUnconditional(nativeStorage.assertingGet(i).1)
    }
    bridgeEverything()
    return bridgedNativeStorage.assertingGet(i.offset).1
  }

  internal func bridgedAllKeysAndValues(
    objects: UnsafeMutablePointer<AnyObject>,
    _ keys: UnsafeMutablePointer<AnyObject>
  ) {
    bridgeEverything()
    // the user is expected to provide a buffer of the correct size
    var i = 0 // position in the input buffer
    var position = 0 // position in the dictionary storage
    let count = bridgedNativeStorage.capacity
    let unmanagedKeys = _UnmanagedAnyObjectArray(keys)
    let unmanagedObjects = _UnmanagedAnyObjectArray(objects)

    if keys == nil {
      if objects == nil {
        // do nothing, both are null
      } else {
        // keys null, objects nonnull
        while position < count {
          if bridgedNativeStorage.isInitializedEntry(position) {
            unmanagedObjects[i] = bridgedNativeStorage.valueAt(position)
            i++
          }
          position++
        }
      }
    } else {
      if objects == nil {
        // keys nonnull, objects null
        while position < count {
          if bridgedNativeStorage.isInitializedEntry(position) {
            unmanagedKeys[i] = bridgedNativeStorage.keyAt(position)
            i++
          }
          position++
        }
      } else {
        // keys nonnull, objects nonnull
        while position < count {
          if bridgedNativeStorage.isInitializedEntry(position) {
            unmanagedObjects[i] = bridgedNativeStorage.valueAt(position)
            unmanagedKeys[i] = bridgedNativeStorage.keyAt(position)
            i++
          }
          position++
        }
      }
    }
  }

%end

  //
  // ${Self} -> NS${Self} bridging
  //

  @objc
  internal var count: Int {
    return nativeStorage.count
  }

  @warn_unused_result
  internal func bridgingObjectForKey(aKey: AnyObject)
    -> AnyObject? {
    let nativeKey = _forceBridgeFromObjectiveC(aKey, Key.self)
    let (i, found) = nativeStorage._find(
      nativeKey, nativeStorage._bucket(nativeKey))
    if found {
      return _getBridgedValue(i)
    }
    return nil
  }

  @warn_unused_result
  internal func bridgingKeyEnumerator() -> _NSEnumeratorType {
    return _Native${Self}StorageKeyNSEnumerator<${TypeParameters}>(self)
  }

  @objc
  internal func countByEnumeratingWithState(
    state: UnsafeMutablePointer<_SwiftNSFastEnumerationState>,
    objects: UnsafeMutablePointer<AnyObject>,
    count: Int
  ) -> Int {
    var theState = state.memory
    if theState.state == 0 {
      theState.state = 1 // Arbitrary non-zero value.
      theState.itemsPtr = AutoreleasingUnsafeMutablePointer(objects)
      theState.mutationsPtr = _fastEnumerationStorageMutationsPtr
      theState.extra.0 = CUnsignedLong(nativeStorage.startIndex.offset)
    }
    let unmanagedObjects = _UnmanagedAnyObjectArray(objects)
    var currIndex = _Native${Self}Index<${TypeParameters}>(
        nativeStorage: nativeStorage, offset: Int(theState.extra.0))
    let endIndex = nativeStorage.endIndex
    var stored = 0
    for i in 0..<count {
      if (currIndex == endIndex) {
        break
      }

      let bridgedKey: AnyObject = _getBridgedKey(currIndex)
      unmanagedObjects[i] = bridgedKey
      ++stored
      currIndex = currIndex.successor()
    }
    theState.extra.0 = CUnsignedLong(currIndex.offset)
    state.memory = theState
    return stored
  }
#endif
}

#if _runtime(_ObjC)
internal struct _Cocoa${Self}Storage : _HashStorageType {
  internal var cocoa${Self}: _NS${Self}Type

  internal typealias Index = _Cocoa${Self}Index
  internal typealias SequenceElement = ${AnySequenceType}

  internal typealias Key = AnyObject
  internal typealias Value = AnyObject

  internal var startIndex: Index {
    return Index(cocoa${Self}, startIndex: ())
  }

  internal var endIndex: Index {
    return Index(cocoa${Self}, endIndex: ())
  }

  @warn_unused_result
  internal func indexForKey(key: Key) -> Index? {
    // Fast path that does not involve creating an array of all keys.  In case
    // the key is present, this lookup is a penalty for the slow path, but the
    // potential savings are significant: we could skip a memory allocation and
    // a linear search.
    if maybeGet(key) == nil {
      return .None
    }

%if Self == 'Set':
    let allKeys = _stdlib_NSSet_allObjects(cocoaSet)
%elif Self == 'Dictionary':
    let allKeys = _stdlib_NSDictionary_allKeys(cocoaDictionary)
%end
    var keyIndex = -1
    for i in 0..<allKeys.value {
      if _stdlib_NSObject_isEqual(key, allKeys[i]) {
        keyIndex = i
        break
      }
    }
    _sanityCheck(keyIndex >= 0,
        "key was found in fast path, but not found later?")
    return Index(cocoa${Self}, allKeys, keyIndex)
  }

  @warn_unused_result
  internal func assertingGet(i: Index) -> SequenceElement {
%if Self == 'Set':
    let value: Value? = i.allKeys[i.currentKeyIndex]
    _sanityCheck(value != nil, "item not found in underlying NS${Self}")
    return value!
%elif Self == 'Dictionary':
    let key: Key = i.allKeys[i.currentKeyIndex]
    let value: Value = i.cocoaDictionary.objectForKey(key)!
    return (key, value)
%end

  }

  @warn_unused_result
  internal func assertingGet(key: Key) -> Value {
%if Self == 'Set':
    let value: Value? = cocoa${Self}.member(key)
    _precondition(value != nil, "member not found in underlying NS${Self}")
    return value!
%elif Self == 'Dictionary':
    let value: Value? = cocoa${Self}.objectForKey(key)
    _precondition(value != nil, "key not found in underlying NS${Self}")
    return value!
%end
  }

  @warn_unused_result
  internal func maybeGet(key: Key) -> Value? {

%if Self == 'Set':
  return cocoaSet.member(key)
%elif Self == 'Dictionary':
  return cocoaDictionary.objectForKey(key)
%end

  }

  internal mutating func updateValue(value: Value, forKey: Key) -> Value? {
    _sanityCheckFailure("can not mutate NS${Self}")
  }

  internal mutating func removeAtIndex(index: Index) -> SequenceElement {
    _sanityCheckFailure("can not mutate NS${Self}")
  }

  internal mutating func removeValueForKey(key: Key) -> Value? {
    _sanityCheckFailure("can not mutate NS${Self}")
  }

  internal mutating func removeAll(keepCapacity keepCapacity: Bool) {
    _sanityCheckFailure("can not mutate NS${Self}")
  }

  internal var count: Int {
    return cocoa${Self}.count
  }

  @warn_unused_result
  internal static func fromArray(elements: [SequenceElement])
    -> _Cocoa${Self}Storage {

    _sanityCheckFailure("this function should never be called")
  }
}
#else
internal struct _Cocoa${Self}Storage {}
#endif

internal enum _Variant${Self}Storage<${TypeParametersDecl}> : _HashStorageType {

  internal typealias NativeStorage = _Native${Self}Storage<${TypeParameters}>
  internal typealias NativeStorageOwner =
    _Native${Self}StorageOwner<${TypeParameters}>
  internal typealias NativeIndex = _Native${Self}Index<${TypeParameters}>
  internal typealias CocoaStorage = _Cocoa${Self}Storage
  internal typealias SequenceElement = ${SequenceType}
  internal typealias SelfType = _Variant${Self}Storage

%if Self == 'Set':
  internal typealias Key = ${TypeParameters}
  internal typealias Value = ${TypeParameters}
%end

  case Native(NativeStorageOwner)
  case Cocoa(CocoaStorage)

  @_transparent
  internal var guaranteedNative: Bool {
    return _canBeClass(Key.self) == 0 && _canBeClass(Value.self) == 0
  }

  @warn_unused_result
  internal mutating func isUniquelyReferenced() -> Bool {
    if _fastPath(guaranteedNative) {
      return _isUnique_native(&self)
    }

    switch self {
    case .Native:
      return _isUnique_native(&self)
    case .Cocoa:
      // Don't consider Cocoa storage mutable, even if it is mutable and is
      // uniquely referenced.
      return false
    }
  }

  internal var native: NativeStorage {
    switch self {
    case .Native(let owner):
      return owner.nativeStorage
    case .Cocoa:
      _sanityCheckFailure("internal error: not backed by native storage")
    }
  }

#if _runtime(_ObjC)
  internal var cocoa: CocoaStorage {
    switch self {
    case .Native:
      _sanityCheckFailure("internal error: not backed by NS${Self}")
    case .Cocoa(let cocoaStorage):
      return cocoaStorage
    }
  }
#endif

  /// Ensure this we hold a unique reference to a native storage
  /// having at least `minimumCapacity` elements.
  internal mutating func ensureUniqueNativeStorage(minimumCapacity: Int)
    -> (reallocated: Bool, capacityChanged: Bool) {
    switch self {
    case .Native:
      let oldCapacity = native.capacity
      if isUniquelyReferenced() && oldCapacity >= minimumCapacity {
#if _runtime(_ObjC)
        // Clear the cache of bridged elements.
        switch self {
        case .Native(let owner):
          owner.deinitializeHeapBufferBridged()
        case .Cocoa:
          _sanityCheckFailure("internal error: not backed by native storage")
        }
#endif
        return (reallocated: false, capacityChanged: false)
      }

      let oldNativeStorage = native
      let newNativeOwner = NativeStorageOwner(minimumCapacity: minimumCapacity)
      var newNativeStorage = newNativeOwner.nativeStorage
      let newCapacity = newNativeStorage.capacity
      for i in 0..<oldCapacity {
        if oldNativeStorage.isInitializedEntry(i) {
          if oldCapacity == newCapacity {
            let key = oldNativeStorage.keyAt(i)
%if Self == 'Set':
            newNativeStorage.initializeKey(key, at: i)
%elif Self == 'Dictionary':
            let value = oldNativeStorage.valueAt(i)
            newNativeStorage.initializeKey(key, value: value , at: i)
%end
          } else {
            let key = oldNativeStorage.keyAt(i)
%if Self == 'Set':
            newNativeStorage.unsafeAddNew(key: key)
%elif Self == 'Dictionary':
            newNativeStorage.unsafeAddNew(
              key: key,
              value: oldNativeStorage.valueAt(i))
%end
          }
        }
      }
      newNativeStorage.count = oldNativeStorage.count

      self = .Native(newNativeOwner)
      return (reallocated: true,
              capacityChanged: oldCapacity != newNativeStorage.capacity)

    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      let cocoa${Self} = cocoaStorage.cocoa${Self}
      let newNativeOwner = NativeStorageOwner(minimumCapacity: minimumCapacity)
      var newNativeStorage = newNativeOwner.nativeStorage
      let oldCocoaGenerator = _Cocoa${Self}Generator(cocoa${Self})
%if Self == 'Set':
      while let key = oldCocoaGenerator.next() {
        newNativeStorage.unsafeAddNew(
            key: _forceBridgeFromObjectiveC(key, Value.self))
      }

%elif Self == 'Dictionary':

      while let (key, value) = oldCocoaGenerator.next() {
        newNativeStorage.unsafeAddNew(
          key: _forceBridgeFromObjectiveC(key, Key.self),
          value: _forceBridgeFromObjectiveC(value, Value.self))
      }

%end
      newNativeStorage.count = cocoa${Self}.count

      self = .Native(newNativeOwner)
      return (reallocated: true, capacityChanged: true)
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

#if _runtime(_ObjC)
  @inline(never)
  internal mutating func migrateDataToNativeStorage(
    cocoaStorage: _Cocoa${Self}Storage
  ) {
    let minCapacity = NativeStorage.getMinCapacity(
      cocoaStorage.count, _hashContainerDefaultMaxLoadFactorInverse)
    let allocated = ensureUniqueNativeStorage(minCapacity).reallocated
    _sanityCheck(allocated, "failed to allocate native ${Self} storage")
  }
#endif

  //
  // _HashStorageType conformance
  //

  internal typealias Index = ${Self}Index<${TypeParameters}>

  internal var startIndex: Index {
    switch self {
    case .Native:
      return ._Native(native.startIndex)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      return ._Cocoa(cocoaStorage.startIndex)
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  internal var endIndex: Index {
    switch self {
    case .Native:
      return ._Native(native.endIndex)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      return ._Cocoa(cocoaStorage.endIndex)
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  @warn_unused_result
  internal func indexForKey(key: Key) -> Index? {
    switch self {
    case .Native:
      if let nativeIndex = native.indexForKey(key) {
        return .Some(._Native(nativeIndex))
      }
      return .None
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      let anyObjectKey: AnyObject = _bridgeToObjectiveCUnconditional(key)
      if let cocoaIndex = cocoaStorage.indexForKey(anyObjectKey) {
        return .Some(._Cocoa(cocoaIndex))
      }
      return .None
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  @warn_unused_result
  internal func assertingGet(i: Index) -> SequenceElement {
    switch self {
    case .Native:
      return native.assertingGet(i._nativeIndex)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
%if Self == 'Set':
      let anyObjectValue: AnyObject = cocoaStorage.assertingGet(i._cocoaIndex)
      let nativeValue = _forceBridgeFromObjectiveC(anyObjectValue, Value.self)
      return nativeValue
%elif Self == 'Dictionary':
      let (anyObjectKey, anyObjectValue) =
          cocoaStorage.assertingGet(i._cocoaIndex)
      let nativeKey = _forceBridgeFromObjectiveC(anyObjectKey, Key.self)
      let nativeValue = _forceBridgeFromObjectiveC(anyObjectValue, Value.self)
      return (nativeKey, nativeValue)
%end
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  @warn_unused_result
  internal func assertingGet(key: Key) -> Value {
    switch self {
    case .Native:
      return native.assertingGet(key)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      // FIXME: This assumes that Key and Value are bridged verbatim.
      let anyObjectKey: AnyObject = _bridgeToObjectiveCUnconditional(key)
      let anyObjectValue: AnyObject = cocoaStorage.assertingGet(anyObjectKey)
      return _forceBridgeFromObjectiveC(anyObjectValue, Value.self)
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

#if _runtime(_ObjC)
  @inline(never)
  internal static func maybeGetFromCocoaStorage(
    cocoaStorage : CocoaStorage, forKey key: Key
  ) -> Value? {
    let anyObjectKey: AnyObject = _bridgeToObjectiveCUnconditional(key)
    if let anyObjectValue = cocoaStorage.maybeGet(anyObjectKey) {
      return _forceBridgeFromObjectiveC(anyObjectValue, Value.self)
    }
    return .None
  }
#endif

  @warn_unused_result
  internal func maybeGet(key: Key) -> Value? {
    switch self {
    case .Native:
      return native.maybeGet(key)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      return SelfType.maybeGetFromCocoaStorage(cocoaStorage, forKey: key)
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  internal mutating func nativeUpdateValue(
    value: Value, forKey key: Key
  ) -> Value? {
    var (i, found) = native._find(key, native._bucket(key))
    
    let minCapacity = found
      ? native.capacity
      : NativeStorage.getMinCapacity(
          native.count + 1,
          native.maxLoadFactorInverse)

    let (_, capacityChanged) = ensureUniqueNativeStorage(minCapacity)
    if capacityChanged {
      i = native._find(key, native._bucket(key)).pos
    }

%if Self == 'Set':
    let oldValue: Value? = found ? native.keyAt(i.offset) : .None
    if found {
      native.setKey(key, at: i.offset)
    } else {
      native.initializeKey(key, at: i.offset)
      ++native.count
    }
%elif Self == 'Dictionary':
    let oldValue: Value? = found ? native.valueAt(i.offset) : .None
    if found {
      native.setKey(key, value: value, at: i.offset)
    } else {
      native.initializeKey(key, value: value, at: i.offset)
      ++native.count
    }
%end

    return oldValue
  }

  internal mutating func updateValue(
    value: Value, forKey key: Key
  ) -> Value? {

    if _fastPath(guaranteedNative) {
      return nativeUpdateValue(value, forKey: key)
    }

    switch self {
    case .Native:
      return nativeUpdateValue(value, forKey: key)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      migrateDataToNativeStorage(cocoaStorage)
      return nativeUpdateValue(value, forKey: key)
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  /// - parameter idealBucket: The ideal bucket for the element being deleted.
  /// - parameter offset: The offset of the element that will be deleted.
  /// Requires an initialized entry at offset.
  internal mutating func nativeDeleteImpl(
    nativeStorage: NativeStorage, idealBucket: Int, offset: Int
  ) {
    _sanityCheck(
        nativeStorage.isInitializedEntry(offset), "expected initialized entry")

    // remove the element
    nativeStorage.destroyEntryAt(offset)
    --nativeStorage.count

    // If we've put a hole in a chain of contiguous elements, some
    // element after the hole may belong where the new hole is.
    var hole = offset

    // Find the first bucket in the contigous chain
    var start = idealBucket
    while nativeStorage.isInitializedEntry(nativeStorage._prev(start)) {
      start = nativeStorage._prev(start)
    }

    // Find the last bucket in the contiguous chain
    var lastInChain = hole
    for var b = nativeStorage._next(lastInChain);
      nativeStorage.isInitializedEntry(b);
      b = nativeStorage._next(b) {
      lastInChain = b
    }

    // Relocate out-of-place elements in the chain, repeating until
    // none are found.
    while hole != lastInChain {
      // Walk backwards from the end of the chain looking for
      // something out-of-place.
      var b: Int
      for b = lastInChain; b != hole; b = nativeStorage._prev(b) {
        let idealBucket = nativeStorage._bucket(nativeStorage.keyAt(b))

        // Does this element belong between start and hole?  We need
        // two separate tests depending on whether [start,hole] wraps
        // around the end of the buffer
        let c0 = idealBucket >= start
        let c1 = idealBucket <= hole
        if start <= hole ? (c0 && c1) : (c0 || c1) {
          break // found it
        }
      }

      if b == hole { // No out-of-place elements found; we're done adjusting
        break
      }

      // Move the found element into the hole
      nativeStorage.moveInitializeFrom(nativeStorage, at: b, toEntryAt: hole)
      hole = b
    }
  }

  internal mutating func nativeRemoveObjectForKey(key: Key) -> Value? {
    var nativeStorage = native
    var idealBucket = nativeStorage._bucket(key)
    var (index, found) = nativeStorage._find(key, idealBucket)

    // Fast path: if the key is not present, we will not mutate the set,
    // so don't force unique storage.
    if !found {
      return .None
    }

    let (reallocated, capacityChanged) =
      ensureUniqueNativeStorage(nativeStorage.capacity)
    if reallocated {
      nativeStorage = native
    }
    if capacityChanged {
      idealBucket = nativeStorage._bucket(key)
      (index, found) = nativeStorage._find(key, idealBucket)
      _sanityCheck(found, "key was lost during storage migration")
    }
%if Self == 'Set':
    let oldValue = nativeStorage.keyAt(index.offset)
%elif Self == 'Dictionary':
    let oldValue = nativeStorage.valueAt(index.offset)
%end
    nativeDeleteImpl(nativeStorage, idealBucket: idealBucket,
      offset: index.offset)
    return oldValue
  }

  internal mutating func nativeRemoveAtIndex(
    nativeIndex: NativeIndex
  ) -> SequenceElement {
    var nativeStorage = native

    // The provided index should be valid, so we will always mutating the
    // set storage.  Request unique storage.
    let (reallocated, _) = ensureUniqueNativeStorage(nativeStorage.capacity)
    if reallocated {
      nativeStorage = native
    }

    let result = nativeStorage.assertingGet(nativeIndex)
%if Self == 'Set':
    let key = result
%elif Self == 'Dictionary':
    let key = result.0
%end

    nativeDeleteImpl(nativeStorage, idealBucket: nativeStorage._bucket(key),
        offset: nativeIndex.offset)
    return result
  }

  internal mutating func removeAtIndex(index: Index) -> SequenceElement {
    if _fastPath(guaranteedNative) {
      return nativeRemoveAtIndex(index._nativeIndex)
    }

    switch self {
    case .Native:
      return nativeRemoveAtIndex(index._nativeIndex)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      // We have to migrate the data first.  But after we do so, the Cocoa
      // index becomes useless, so get the key first.
      //
      // FIXME(performance): fuse data migration and element deletion into one
      // operation.
      let cocoaIndex = index._cocoaIndex
      let anyObjectKey: AnyObject =
        cocoaIndex.allKeys[cocoaIndex.currentKeyIndex]
      migrateDataToNativeStorage(cocoaStorage)
      let key = _forceBridgeFromObjectiveC(anyObjectKey, Key.self)
      let value = nativeRemoveObjectForKey(key)

%if Self == 'Set':
      _sanityCheck(key == value, "bridging did not preserve equality")
      return key
%elif Self == 'Dictionary':
      return (key, _unsafeUnwrap(value))
%end
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  internal mutating func removeValueForKey(key: Key) -> Value? {
    if _fastPath(guaranteedNative) {
      return nativeRemoveObjectForKey(key)
    }

    switch self {
    case .Native:
      return nativeRemoveObjectForKey(key)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      let anyObjectKey: AnyObject = _bridgeToObjectiveCUnconditional(key)
      if cocoaStorage.maybeGet(anyObjectKey) == nil {
        return .None
      }
      migrateDataToNativeStorage(cocoaStorage)
      return nativeRemoveObjectForKey(key)
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  internal mutating func nativeRemoveAll() {
    var nativeStorage = native

    // FIXME(performance): if the storage is non-uniquely referenced, we
    // shouldn’t be copying the elements into new storage and then immediately
    // deleting the elements. We should detect that the storage is not uniquely
    // referenced and allocate new empty storage of appropriate capacity.

    // We have already checked for the empty dictionary case, so we will always
    // mutating the dictionary storage.  Request unique storage.
    let (reallocated, _) = ensureUniqueNativeStorage(nativeStorage.capacity)
    if reallocated {
      nativeStorage = native
    }

    for var b = 0; b != nativeStorage.capacity; ++b {
      if nativeStorage.isInitializedEntry(b) {
        nativeStorage.destroyEntryAt(b)
      }
    }
    nativeStorage.count = 0
  }

  internal mutating func removeAll(keepCapacity keepCapacity: Bool) {
    if count == 0 {
      return
    }

    if !keepCapacity {
      self = .Native(NativeStorage.Owner(minimumCapacity: 2))
      return
    }

    if _fastPath(guaranteedNative) {
      nativeRemoveAll()
      return
    }

    switch self {
    case .Native:
      nativeRemoveAll()
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      self = .Native(NativeStorage.Owner(minimumCapacity: cocoaStorage.count))
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  internal var count: Int {
    switch self {
    case .Native:
      return native.count
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      return cocoaStorage.count
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  /// Return a *generator* over the (Key, Value) pairs.
  ///
  /// - Complexity: O(1).
  internal func generate() -> ${Self}Generator<${TypeParameters}> {
    switch self {
    case .Native(let owner):
      return
        ._Native(start: native.startIndex, end: native.endIndex, owner: owner)
    case .Cocoa(let cocoaStorage):
#if _runtime(_ObjC)
      return ._Cocoa(_Cocoa${Self}Generator(cocoaStorage.cocoa${Self}))
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }

  @warn_unused_result
  internal static func fromArray(elements: [SequenceElement])
    -> _Variant${Self}Storage<${TypeParameters}> {

    _sanityCheckFailure("this function should never be called")
  }
}

internal struct _Native${Self}Index<${TypeParametersDecl}> :
  ForwardIndexType, Comparable {

  internal typealias NativeStorage = _Native${Self}Storage<${TypeParameters}>
  internal typealias NativeIndex = _Native${Self}Index<${TypeParameters}>

  internal var nativeStorage: NativeStorage
  internal var offset: Int

  internal init(nativeStorage: NativeStorage, offset: Int) {
    self.nativeStorage = nativeStorage
    self.offset = offset
  }

  /// Returns the next consecutive value after `self`.
  ///
  /// - Requires: The next value is representable.
  @warn_unused_result
  internal func successor() -> NativeIndex {
    var i = offset + 1
    // FIXME: Can't write the simple code pending
    // <rdar://problem/15484639> Refcounting bug
    while i < nativeStorage.capacity /*&& !nativeStorage[i]*/ {
      // FIXME: workaround for <rdar://problem/15484639>
      if nativeStorage.isInitializedEntry(i) {
        break
      }
      // end workaround
      ++i
    }
    return NativeIndex(nativeStorage: nativeStorage, offset: i)
  }
}

internal func == <${TypeParametersDecl}> (
  lhs: _Native${Self}Index<${TypeParameters}>,
  rhs: _Native${Self}Index<${TypeParameters}>
) -> Bool {
  // FIXME: assert that lhs and rhs are from the same dictionary.
  return lhs.offset == rhs.offset
}

internal func < <${TypeParametersDecl}> (
  lhs: _Native${Self}Index<${TypeParameters}>,
  rhs: _Native${Self}Index<${TypeParameters}>
) -> Bool {
  // FIXME: assert that lhs and rhs are from the same dictionary.
  return lhs.offset < rhs.offset
}

#if _runtime(_ObjC)
internal struct _Cocoa${Self}Index : ForwardIndexType, Comparable {
  // Assumption: we rely on NSDictionary.getObjects when being
  // repeatedly called on the same NSDictionary, returning items in the same
  // order every time.
  // Similarly, the same assumption holds for NSSet.allObjects.

  /// A reference to the NS${Self}, which owns members in `allObjects`,
  /// or `allKeys`, for NSSet and NSDictionary respectively.
  internal let cocoa${Self}: _NS${Self}Type

  /// An unowned array of keys.
  internal var allKeys: _HeapBuffer<Int, AnyObject>

  /// Index into `allKeys`
  internal var currentKeyIndex: Int

  internal init(_ cocoa${Self}: _NS${Self}Type, startIndex: ()) {
    self.cocoa${Self} = cocoa${Self}
%if Self == 'Set':
    self.allKeys = _stdlib_NSSet_allObjects(cocoaSet)
%elif Self == 'Dictionary':
    self.allKeys = _stdlib_NSDictionary_allKeys(cocoaDictionary)
%end
    self.currentKeyIndex = 0
  }

  internal init(_ cocoa${Self}: _NS${Self}Type, endIndex: ()) {
    self.cocoa${Self} = cocoa${Self}
%if Self == 'Set':
    self.allKeys = _stdlib_NS${Self}_allObjects(cocoa${Self})
%elif Self == 'Dictionary':
    self.allKeys = _stdlib_NS${Self}_allKeys(cocoa${Self})
%end
    self.currentKeyIndex = allKeys.value
  }

  internal init(_ cocoa${Self}: _NS${Self}Type,
    _ allKeys: _HeapBuffer<Int, AnyObject>,
    _ currentKeyIndex: Int
  ) {
    self.cocoa${Self} = cocoa${Self}
    self.allKeys = allKeys
    self.currentKeyIndex = currentKeyIndex
  }

  /// Returns the next consecutive value after `self`.
  ///
  /// - Requires: The next value is representable.
  @warn_unused_result
  internal func successor() -> _Cocoa${Self}Index {
    _precondition(
      currentKeyIndex < allKeys.value, "can not increment endIndex")
    return _Cocoa${Self}Index(cocoa${Self}, allKeys, currentKeyIndex + 1)
  }
}

@warn_unused_result
internal func ==(lhs: _Cocoa${Self}Index, rhs: _Cocoa${Self}Index) -> Bool {
  _precondition(lhs.cocoa${Self} === rhs.cocoa${Self},
    "can not compare indexes pointing to different ${Self}s")
  _precondition(lhs.allKeys.value == rhs.allKeys.value,
    "one or both of the indexes have been invalidated")

  return lhs.currentKeyIndex == rhs.currentKeyIndex
}

@warn_unused_result
internal func <(lhs: _Cocoa${Self}Index, rhs: _Cocoa${Self}Index) -> Bool {
  _precondition(lhs.cocoa${Self} === rhs.cocoa${Self},
    "can not compare indexes pointing to different ${Self}s")
  _precondition(lhs.allKeys.value == rhs.allKeys.value,
    "one or both of the indexes have been invalidated")

  return lhs.currentKeyIndex < rhs.currentKeyIndex
}
#else
internal struct _Cocoa${Self}Index {}
#endif

internal enum ${Self}IndexRepresentation<${TypeParametersDecl}> {
  typealias _Index = ${Self}Index<${TypeParameters}>
  typealias _NativeIndex = _Index._NativeIndex
  typealias _CocoaIndex = _Index._CocoaIndex

  case _Native(_NativeIndex)
  case _Cocoa(_CocoaIndex)
}

%{
if Self == 'Set':
  SubscriptingWithIndexDoc = """\
/// Used to access the members in an instance of `Set<Element>`."""
elif Self == 'Dictionary':
  SubscriptingWithIndexDoc = """\
/// Used to access the key-value pairs in an instance of
/// `Dictionary<Key, Value>`.
///
/// Dictionary has two subscripting interfaces:
///
/// 1. Subscripting with a key, yielding an optional value:
///
///        v = d[k]!
///
/// 2. Subscripting with an index, yielding a key-value pair:
///
///        (k,v) = d[i]"""
}%

${SubscriptingWithIndexDoc}
public struct ${Self}Index<${TypeParametersDecl}> :
  ForwardIndexType, Comparable {
  // Index for native storage is efficient.  Index for bridged NS${Self} is
  // not, because neither NSEnumerator nor fast enumeration support moving
  // backwards.  Even if they did, there is another issue: NSEnumerator does
  // not support NSCopying, and fast enumeration does not document that it is
  // safe to copy the state.  So, we can not implement Index that is a value
  // type for bridged NS${Self} in terms of Cocoa enumeration facilities.

  internal typealias _NativeIndex = _Native${Self}Index<${TypeParameters}>
  internal typealias _CocoaIndex = _Cocoa${Self}Index

%if Self == 'Set':
  internal typealias Key = ${TypeParameters}
  internal typealias Value = ${TypeParameters}

  @available(*, unavailable, renamed="Element")
  public typealias T = Element
%end

  internal var _value: ${Self}IndexRepresentation<${TypeParameters}>

  internal static func _Native(index: _NativeIndex) -> ${Self}Index {
    return ${Self}Index(_value: ._Native(index))
  }
#if _runtime(_ObjC)
  internal static func _Cocoa(index: _CocoaIndex) -> ${Self}Index {
    return ${Self}Index(_value: ._Cocoa(index))
  }
#endif

  @_transparent
  internal var _guaranteedNative: Bool {
    return _canBeClass(Key.self) == 0 && _canBeClass(Value.self) == 0
  }

  @_transparent
  internal var _nativeIndex: _NativeIndex {
    switch _value {
    case ._Native(let nativeIndex):
      return nativeIndex
    case ._Cocoa:
      _sanityCheckFailure("internal error: does not contain a native index")
    }
  }

#if _runtime(_ObjC)
  @_transparent
  internal var _cocoaIndex: _CocoaIndex {
    switch _value {
    case ._Native:
      _sanityCheckFailure("internal error: does not contain a Cocoa index")
    case ._Cocoa(let cocoaIndex):
      return cocoaIndex
    }
  }
#endif

  /// Returns the next consecutive value after `self`.
  ///
  /// - Requires: The next value is representable.
  public func successor() -> ${Self}Index<${TypeParameters}> {
    if _fastPath(_guaranteedNative) {
      return ._Native(_nativeIndex.successor())
    }

    switch _value {
    case ._Native(let nativeIndex):
      return ._Native(nativeIndex.successor())
    case ._Cocoa(let cocoaIndex):
#if _runtime(_ObjC)
      return ._Cocoa(cocoaIndex.successor())
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }
}

@warn_unused_result
public func == <${TypeParametersDecl}> (
  lhs: ${Self}Index<${TypeParameters}>,
  rhs: ${Self}Index<${TypeParameters}>
) -> Bool {
  if _fastPath(lhs._guaranteedNative) {
    return lhs._nativeIndex == rhs._nativeIndex
  }

  switch (lhs._value, rhs._value) {
  case (._Native(let lhsNative), ._Native(let rhsNative)):
    return lhsNative == rhsNative
  case (._Cocoa(let lhsCocoa), ._Cocoa(let rhsCocoa)):
#if _runtime(_ObjC)
    return lhsCocoa == rhsCocoa
#else
    _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
  default:
    _preconditionFailure("comparing indexes from different sets")
  }
}

@warn_unused_result
public func < <${TypeParametersDecl}> (
  lhs: ${Self}Index<${TypeParameters}>,
  rhs: ${Self}Index<${TypeParameters}>
) -> Bool {
  if _fastPath(lhs._guaranteedNative) {
    return lhs._nativeIndex < rhs._nativeIndex
  }

  switch (lhs._value, rhs._value) {
  case (._Native(let lhsNative), ._Native(let rhsNative)):
    return lhsNative < rhsNative
  case (._Cocoa(let lhsCocoa), ._Cocoa(let rhsCocoa)):
#if _runtime(_ObjC)
    return lhsCocoa < rhsCocoa
#else
    _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
  default:
    _preconditionFailure("comparing indexes from different sets")
  }
}

#if _runtime(_ObjC)
final internal class _Cocoa${Self}Generator : GeneratorType {
  internal typealias Element = ${AnySequenceType}

  // Cocoa ${Self} generator has to be a class, otherwise we can not
  // guarantee that the fast enumeration struct is pinned to a certain memory
  // location.

  // This stored property should be stored at offset zero.  There's code below
  // relying on this.
  internal var _fastEnumerationState: _SwiftNSFastEnumerationState =
    _makeSwiftNSFastEnumerationState()

  // This stored property should be stored right after `_fastEnumerationState`.
  // There's code below relying on this.
  internal var _fastEnumerationStackBuf = _CocoaFastEnumerationStackBuf()

  internal let cocoa${Self}: _NS${Self}Type

  internal var _fastEnumerationStatePtr:
    UnsafeMutablePointer<_SwiftNSFastEnumerationState> {
    return UnsafeMutablePointer(_getUnsafePointerToStoredProperties(self))
  }

  internal var _fastEnumerationStackBufPtr:
    UnsafeMutablePointer<_CocoaFastEnumerationStackBuf> {
    return UnsafeMutablePointer(_fastEnumerationStatePtr + 1)
  }

  // These members have to be word-sized integers, they can not be limited to
  // Int8 just because our buffer holds 16 elements: fast enumeration is
  // allowed to return inner pointers to the container, which can be much
  // larger.
  internal var itemIndex: Int = 0
  internal var itemCount: Int = 0

  internal init(_ cocoa${Self}: _NS${Self}Type) {
    self.cocoa${Self} = cocoa${Self}
  }

  internal func next() -> Element? {
    if itemIndex < 0 {
      return .None
    }
    let cocoa${Self} = self.cocoa${Self}
    if itemIndex == itemCount {
      let stackBufLength = _fastEnumerationStackBuf.length
      // We can't use `withUnsafeMutablePointers` here to get pointers to
      // properties, because doing so might introduce a writeback buffer, but
      // fast enumeration relies on the pointer identity of the enumeration
      // state struct.
      itemCount = cocoa${Self}.countByEnumeratingWithState(
        _fastEnumerationStatePtr,
        objects: UnsafeMutablePointer(_fastEnumerationStackBufPtr),
        count: stackBufLength)
      if itemCount == 0 {
        itemIndex = -1
        return .None
      }
      itemIndex = 0
    }
    let itemsPtrUP: UnsafeMutablePointer<AnyObject> =
      UnsafeMutablePointer(_fastEnumerationState.itemsPtr)
    let itemsPtr = _UnmanagedAnyObjectArray(itemsPtrUP)
    let key: AnyObject = itemsPtr[itemIndex]
    ++itemIndex
%if Self == 'Set':
    return key
%elif Self == 'Dictionary':
    let value: AnyObject = cocoa${Self}.objectForKey(key)!
    return (key, value)
%end
  }
}
#else
final internal class _Cocoa${Self}Generator {}
#endif

internal enum ${Self}GeneratorRepresentation<${TypeParametersDecl}> {
  internal typealias _Generator = ${Self}Generator<${TypeParameters}>
  internal typealias _NativeStorageOwner =
    _Native${Self}StorageOwner<${TypeParameters}>
  internal typealias _NativeIndex = _Generator._NativeIndex

  // For native storage, we keep two indices to keep track of the iteration
  // progress and the storage owner to make the storage non-uniquely
  // referenced.
  //
  // While indices keep the storage alive, they don't affect reference count of
  // the storage.  Generator is iterating over a frozen view of the collection
  // state, so it should keep its own reference to the storage owner.
  case _Native(
    start: _NativeIndex, end: _NativeIndex, owner: _NativeStorageOwner)
  case _Cocoa(_Cocoa${Self}Generator)
}

/// A generator over the members of a `${Self}<${TypeParameters}>`.
public struct ${Self}Generator<${TypeParametersDecl}> : GeneratorType {
  // ${Self} has a separate GeneratorType and Index because of efficiency
  // and implementability reasons.
  //
  // Index for native storage is efficient.  Index for bridged NS${Self} is
  // not.
  //
  // Even though fast enumeration is not suitable for implementing
  // Index, which is multi-pass, it is suitable for implementing a
  // GeneratorType, which is being consumed as iteration proceeds.

  internal typealias _NativeStorageOwner =
    _Native${Self}StorageOwner<${TypeParameters}>
  internal typealias _NativeIndex = _Native${Self}Index<${TypeParameters}>

%if Self == 'Set':
  @available(*, unavailable, renamed="Element")
  public typealias T = Element
%end

  internal var _state: ${Self}GeneratorRepresentation<${TypeParameters}>

  internal static func _Native(
    start start: _NativeIndex, end: _NativeIndex, owner: _NativeStorageOwner
  ) -> ${Self}Generator {
    return ${Self}Generator(
      _state: ._Native(start: start, end: end, owner: owner))
  }
#if _runtime(_ObjC)
  internal static func _Cocoa(
    generator: _Cocoa${Self}Generator
  ) -> ${Self}Generator{
    return ${Self}Generator(_state: ._Cocoa(generator))
  }
#endif

  @_transparent
  internal var _guaranteedNative: Bool {
%if Self == 'Set':
    return _canBeClass(Element.self) == 0
%elif Self == 'Dictionary':
    return _canBeClass(Key.self) == 0 && _canBeClass(Value.self) == 0
%end
  }

  internal mutating func _nativeNext() -> ${SequenceType}? {
    switch _state {
    case ._Native(let startIndex, let endIndex, let owner):
      if startIndex == endIndex {
        return .None
      }
      let result = startIndex.nativeStorage.assertingGet(startIndex)
      _state =
        ._Native(start: startIndex.successor(), end: endIndex, owner: owner)
      return result
    case ._Cocoa:
      _sanityCheckFailure("internal error: not backed by NS${Self}")
    }
  }

  /// Advance to the next element and return it, or `nil` if no next
  /// element exists.
  ///
  /// - Requires: No preceding call to `self.next()` has returned `nil`.
  public mutating func next() -> ${SequenceType}? {
    if _fastPath(_guaranteedNative) {
      return _nativeNext()
    }

    switch _state {
    case ._Native:
      return _nativeNext()
    case ._Cocoa(let cocoaGenerator):
#if _runtime(_ObjC)
%if Self == 'Set':
      if let anyObjectElement = cocoaGenerator.next() {
        return _forceBridgeFromObjectiveC(anyObjectElement, Element.self)
      }
%elif Self == 'Dictionary':
      if let (anyObjectKey, anyObjectValue) = cocoaGenerator.next() {
        let nativeKey = _forceBridgeFromObjectiveC(anyObjectKey, Key.self)
        let nativeValue = _forceBridgeFromObjectiveC(anyObjectValue, Value.self)
        return (nativeKey, nativeValue)
      }
%end
      return .None
#else
      _sanityCheckFailure("internal error: unexpected cocoa ${Self}")
#endif
    }
  }
}

internal struct ${Self}MirrorPosition<${TypeParametersDecl}> {
  internal typealias MirroredType = ${Self}<${TypeParameters}>

  internal var _intPos: Int
  internal var ${Self}Pos: MirroredType.Index

  internal init(_ m: MirroredType) {
    _intPos = 0
    ${Self}Pos = m.startIndex
  }

  internal mutating func successor() {
    _intPos = _intPos + 1
    ${Self}Pos = ${Self}Pos.successor()
  }

}

@warn_unused_result
internal func == <${TypeParametersDecl}> (
  lhs: ${Self}MirrorPosition<${TypeParameters}>, rhs : Int
) -> Bool {
  return lhs._intPos == rhs
}

@warn_unused_result
internal func > <${TypeParametersDecl}> (
  lhs: ${Self}MirrorPosition<${TypeParameters}>, rhs : Int
) -> Bool {
  return lhs._intPos > rhs
}

@warn_unused_result
internal func < <${TypeParametersDecl}> (
  lhs: ${Self}MirrorPosition<${TypeParameters}>, rhs : Int
) -> Bool {
  return lhs._intPos < rhs
}

internal class ${Self}Mirror<${TypeParametersDecl}> : _MirrorType {
  typealias MirroredType = ${Self}<${TypeParameters}>
  internal let _mirror : MirroredType
  internal var _pos : ${Self}MirrorPosition<${TypeParameters}>

  internal init(_ m : MirroredType) {
    _mirror = m
    _pos = ${Self}MirrorPosition(m)
  }

  internal var value: Any { return (_mirror as Any) }

  internal var valueType: Any.Type { return (_mirror as Any).dynamicType }

  internal var objectIdentifier: ObjectIdentifier? { return nil }

  internal var count: Int { return _mirror.count }

  internal subscript(i: Int) -> (String, _MirrorType) {
    _precondition(i >= 0 && i < count, "_MirrorType access out of bounds")

    if _pos > i {
      _pos._intPos = 0
    }

    while _pos < i && !(_pos == i) {
      _pos.successor()
    }
%if Self == 'Set':
    return ("[\(_pos._intPos)]", _reflect(_mirror[_pos.${Self}Pos]))
%elif Self == 'Dictionary':
    return ("[\(_pos._intPos)]", _reflect(_mirror[_pos.${Self}Pos]))
%end
  }

  internal var summary: String {
%if Self == 'Set':
    if count == 1 {
      return "1 member"
    }
    return "\(count) members"
%elif Self == 'Dictionary':
    if count == 1 {
      return "1 key/value pair"
    }
    return "\(count) key/value pairs"
%end
  }

  internal var quickLookObject: PlaygroundQuickLook? { return nil }

%if Self == 'Set':
  internal var disposition: _MirrorDisposition { return .MembershipContainer }
%elif Self == 'Dictionary':
  internal var disposition: _MirrorDisposition { return .KeyContainer }
%end
}

extension ${Self} : _Reflectable {
  /// Returns a mirror that reflects `self`.
  @warn_unused_result
  public func _getMirror() -> _MirrorType {
    return ${Self}Mirror(self)
  }
}

/// Initializes `${a_Self}` from unique members.
///
/// Using a builder can be faster than inserting members into an empty
/// `${Self}`.
public struct _${Self}Builder<${TypeParametersDecl}> {
%if Self == 'Set':
  public typealias Key = ${TypeParameters}
  public typealias Value = ${TypeParameters}
%end

  internal var _result: ${Self}<${TypeParameters}>
  internal var _nativeStorage: _Native${Self}Storage<${TypeParameters}>
  internal let _requestedCount: Int
  internal var _actualCount: Int

  public init(count: Int) {
    let requiredCapacity =
      _Native${Self}Storage<${TypeParameters}>.getMinCapacity(
        count, _hashContainerDefaultMaxLoadFactorInverse)
    _result = ${Self}<${TypeParameters}>(minimumCapacity: requiredCapacity)
    _nativeStorage = _result._variantStorage.native
    _requestedCount = count
    _actualCount = 0
  }

%if Self == 'Set':
  public mutating func add(member newKey: Key) {
    _nativeStorage.unsafeAddNew(key: newKey)
%elif Self == 'Dictionary':
  public mutating func add(key newKey: Key, value: Value) {
    _nativeStorage.unsafeAddNew(key: newKey, value: value)
%end
    _actualCount++
  }

  @warn_unused_result
  public mutating func take() -> ${Self}<${TypeParameters}> {
    _precondition(_actualCount >= 0,
      "can not take the result twice")
    _precondition(_actualCount == _requestedCount,
      "the number of members added does not match the promised count")

    // Finish building the `${Self}`.
    _nativeStorage.count = _requestedCount

    // Prevent taking the result twice.
    _actualCount = -1
    return _result
  }
}

extension ${Self} {
  /// If `!self.isEmpty`, return the first key-value pair in the sequence of
  /// elements, otherwise return `nil`.
  ///
  /// - Complexity: Amortized O(1)
  public mutating func popFirst() -> Element? {
    guard !isEmpty else { return nil }
    return removeAtIndex(startIndex)
  }
}

//===--- Bridging ---------------------------------------------------------===//

#if _runtime(_ObjC)
extension ${Self} {
  @warn_unused_result
  public func _bridgeToObjectiveCImpl() -> _NS${Self}CoreType {
    switch _variantStorage {
    case _Variant${Self}Storage.Native(let nativeOwner):
%if Self == 'Set':
      _precondition(_isBridgedToObjectiveC(Element.self),
        "Key is not bridged to Objective-C")
%elif Self == 'Dictionary':
      _precondition(_isBridgedToObjectiveC(Value.self),
        "Value is not bridged to Objective-C")
%end
      return nativeOwner as _Native${Self}StorageOwner<${TypeParameters}>

    case _Variant${Self}Storage.Cocoa(let cocoaStorage):
      return cocoaStorage.cocoa${Self}
    }
  }

  @warn_unused_result
  public static func _bridgeFromObjectiveCAdoptingNativeStorage(
    s: AnyObject
  ) -> ${Self}<${TypeParameters}>? {
    if let nativeOwner =
        s as AnyObject as? _Native${Self}StorageOwner<${TypeParameters}> {
      // If `NS${Self}` is actually native storage of `${Self}` with key
      // and value types that the requested ones match exactly, then just
      // re-wrap the native storage.
      return ${Self}<${TypeParameters}>(_nativeStorageOwner: nativeOwner)
    }
    // FIXME: what if `s` is native storage, but for different key/value type?
    return .None
  }
}
#endif