RFC: Deque: should it be self-slicing

Related Projects Collections
10

Ah! This explains my confusion over in RFC: Deque: should it have an opaque index?.

Even though I was a fan of it for a while, I don't think self-slicing is desirable in general -- see my post in the other topic for my reasoning. (I think I actually first heard it from you, based on your experience with ByteBuffer. :see_no_evil:)

Luckily, it is possible to implement the original CircularBuffer semantics on top of Deque. Given the documented semantics below, we don't even need to keep the index values stable across count-changing mutations, so there isn't any reason to have indices contain the exact same values before/after a push/pop. We can simply have them store Deque indices.

/// - note: Every index is invalidated as soon as you perform a length-changing operating on the `CircularBuffer`
///         but remains valid when you replace one item by another using the subscript.

(Although if there was one, we could probably emulate that by maintaining a bias value that gets subtracted from CircularBuffer indices to convert them to a Deque index. It gets tricky because the bias can grow arbitrarily large, but that can be handled by careful use of wrapping arithmetic. The Comparable conformance of Index would get a lot more tricky, unless the Index would contain the bias too -- but then it wouldn't be constant anymore, and in fact it would be just a rather pointless & weird decomposition of the underlying Deque offset.)

Here is one draft on how it can be done:

(You can keep Index 8 bytes wide by narrowing the offset value and the version number.)

struct CircularBuffer<Element> {
  var _base: Deque<Element> = []
  var _start: Int
  var _end: Int
  var _version: Int = { 
    var rng = SystemRandomNumberGenerator()
    return rng.next() 
  }()

  struct Index: Comparable {
    var _offset: Int
    var _version: Int

    static func == (left: Self, right: Self) -> Bool {
      precondition(left._version == right._version, 
        "Indices from different collections aren't comparable")
      return left._offset == right._offset
    }

    static func < (left: Self, right: Self) -> Bool {
      precondition(left._version == right._version, 
        "Indices from different collections aren't comparable")
      return left._offset < right._offset
    }
  }

  var startIndex: Index { Index(_offset: _start, _version: _version) }
  var endIndex: Index { Index(_offset: _end, _version: _version) }
  var count: Int { _end - _start }
  
  func index(_ i: Index, offsetBy delta: Int) -> Index {
    Index(_position: i._offset &+ delta)
  }

  subscript(_ i: Index) -> Element {
    get { 
      precondition(i._version == _version && _start <= i._offset && i._offset < _end, "Invalid index")
      _base[i._offset] 
    }
    _modify { 
      precondition(i._version == _version && _start <= i._offset && i._offset < _end, "Invalid index")
      yield &_base[i._offset] 
    }
  }
   
  func append(_ item: Element) { 
    _version &+= 1 // Note: this leads to stricter index validation than in the original
    _base.insert(item, at: _end) 
    _end += 1
  }

  func removeLast() -> Element { 
    precondition(count > 0)
    _version &+= 1 // Note: this leads to stricter index validation than in the original
    _end -= 1
    return _base.remove(at: _end) 
  }

  func prepend(_ item: Element) {
    _version &+= 1 // Note: this leads to stricter index validation than in the original
    _base.insert(item, at: _start)
    _end += 1
  }

  func removeFirst() -> Element {
    precondition(count > 0)
    _version &+= 1 // Note: this leads to stricter index validation than in the original
    _end -= 1
    return  _base.remove(at: _start)
  }
}

(Being forced to implement range-replacing mutations on slices is another great reason to dislike self-slicing. :wink:)

3 Likes