Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SR-4140] Add capacity property requirement to RangeReplaceableCollection #46723

Open
dabrahams opened this issue Mar 2, 2017 · 1 comment
Open
Labels
affects ABI Flag: Affects ABI bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. standard library Area: Standard library umbrella

Comments

@dabrahams
Copy link
Collaborator

Previous ID SR-4140
Radar rdar://problem/31419825
Original Reporter @dabrahams
Type Bug
Additional Detail from JIRA
Votes 0
Component/s Standard Library
Labels Bug, AffectsABI
Assignee None
Priority Medium

md5: 5ca4f0196ccedc3e562f99bf46841892

Issue Description:

Here's an example where I needed it in a protocol:

protocol _RangeReplaceableCollection : RangeReplaceableCollection {
  var capacity : Int { get }
}

enum _UnboundCapacity<
  Base: RandomAccessCollection & _RangeReplaceableCollection
> {
  case small(Base)
  case large([Base.Iterator.Element])
}

extension _UnboundCapacity : Collection {
  public typealias Index = Int
  public var startIndex : Int { return 0 }
  
  public var endIndex : Int {
    switch self {
    case .small(let base):
      return numericCast(base.count)
    case .large(let base):
      return base.count
    }
  }

  public subscript(i: Index) -> Base.Iterator.Element {
    switch self {
    case .small(let base):
      return base[base.index(atOffset: i)]
    case .large(let base):
      return base[base.index(atOffset: i)]
    }
  }
  
  public func index(after i: Index) -> Index {
    return i + 1
  }
}

extension _UnboundCapacity : BidirectionalCollection {
  public func index(before i: Index) -> Index {
    return i - 1
  }
}

extension _UnboundCapacity : RandomAccessCollection {
  public func index(_ i: Index, offsetBy n: IndexDistance) -> Index {
    return i + n
  }
  public func distance(from i: Index, to j: Index) -> Int {
    return j - i
  }
}

extension _UnboundCapacity {
  
  internal mutating func withMutableArray<R>(
    minCapacity: Int = 0,
    body: (inout [Base.Iterator.Element]) throws->R
  ) rethrows -> R {
    var result: [Base.Iterator.Element]
    switch self {
      
    case .small(let base):
      if minCapacity <= numericCast(base.count) {
        result = Array(base)
      }
      else {
        result = []
        result.reserveCapacity(Swift.min(minCapacity, numericCast(base.count)))
        result.append(contentsOf: base)
      }
      
    case .large(let base):
      result = base
      self = .large([]) // Swap out result so we don't incur multiple refs
    }
    defer { self = .large(result) }
    return try body(&result)
  }
  
  internal func _small(minCapacity: Int) -> Base? {
    if case .small(let base) = self, minCapacity <= base.capacity {
      return base
    }
    return nil
  }
}

extension _UnboundCapacity : RangeReplaceableCollection {
  public init() {
    self.init(Base())
  }

  public init(_ b: Base) { self = .small(b) }
  public init(_ b: [Base.Iterator.Element]) { self = .large(b) }
  
  public mutating func replaceSubrange<C>(
    _ target: Range<Index>,
    with newElements: C
  ) where C : Collection, C.Iterator.Element == Iterator.Element {
    let newCount = count + numericCast(newElements.count) - target.count

    let r = _small(minCapacity: newCount)
    if _fastPath(r != nil), var s = r {
      s.replaceSubrange(
        s.index(atOffset: target.lowerBound)
        ..< s.index(atOffset: target.upperBound),
        with: newElements)
      self = .small(s)
      return
    }
    
    withMutableArray(minCapacity: newCount) {
      $0.replaceSubrange(target, with: newElements)
    }
  }

  public mutating func reserveCapacity(_ n: IndexDistance) {
    if _fastPath(_small(minCapacity: n) != nil) { return }
    withMutableArray(minCapacity: n) { _ in }
  }
}

struct UpTo4Inline<T> : RandomAccessCollection, _RangeReplaceableCollection {
  var storage: (T, (T, (T, T?)?)?)?

  public typealias Index = Int
  public var startIndex : Index { return 0 }
  public var endIndex : Index {
    switch storage {
    case nil: return 0
    case .some(_, nil): return 1
    case .some(_, .some(_, nil)): return 2
    case .some(_, .some(_, .some(_, nil))): return 3
    default: return 4
    }
  }
  public subscript(i: Index) -> T {
    switch i {
    case 0:
      return storage!.0
    case 1:
      return storage!.1!.0
    case 2:
      return storage!.1!.1!.0
    default:
      return storage!.1!.1!.1!
    }
  }
  
  public mutating func append(_ x: T) {
    switch storage {
    case nil: storage = (x, nil)
    case .some(let a, nil): storage = (a, (x, nil))
    case .some(let a, .some(let b, nil)): storage = (a, (b, (x, nil)))
    case .some(let a, .some(let b, .some(let c, nil))): storage = (a, (b, (c, x)))
    default: fatalError("overfilled")
    }
  }

  public init() { storage = nil }
  
  public init<S: Sequence>(_ s: S) where S.Iterator.Element == T {
    self.init()
    append(contentsOf: s)
  }

  public mutating func append<S: Sequence>(contentsOf s: S)
  where S.Iterator.Element == T {
    for x in s {
      append(x)
    }
  }

  public mutating func replaceSubrange<C>(
    _ target: Range<Index>, with newElements: C
  ) where C : Collection, C.Iterator.Element == T {
    if target.lowerBound == count {
      append(contentsOf: newElements)
    }
    else {
      var newSelf = UpTo4Inline(self[..<target.lowerBound])
      newSelf.append(contentsOf: newElements)
      newSelf.append(contentsOf: self[target.upperBound...])
      self = newSelf
    }
  }

  public var capacity: Int { return 4 }

  public func index(after i: Index) -> Index {
    return i + 1
  }
  public func index(before i: Index) -> Index {
    return i - 1
  }
  public func index(_ i: Index, offsetBy n: Int) -> Index {
    return i + n
  }
}

do {
  var u = UpTo4Inline<Int>()
  u.append(contentsOf: 1...2)
  print(Array(u))
  u.replaceSubrange(1..<1, with: 7...7)
  u.replaceSubrange(1..<1, with: 5...5)
  print(Array(u))
}

do {
  var u = _UnboundCapacity<UpTo4Inline<Int>>()
  u.append(contentsOf: 1...2)
  print(Array(u))
  u.insert(contentsOf: 7...7, at: 1)
  u.insert(contentsOf: 5...20, at: 1)
  print(Array(u))
}
@bob-wilson
Copy link

@swift-ci create

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
affects ABI Flag: Affects ABI bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. standard library Area: Standard library umbrella
Projects
None yet
Development

No branches or pull requests

2 participants