dabrahams/CoW.swift

## CoW.swift
/// Example of a recursive sum type representing a tree.
///
/// The compiler uses copy-on-write under the covers to give instances value
/// semantics.
indirect enum Tree<Body> {
  case o(_ body: Body, _ left: Tree?, _ right: Tree?)
}

extension Tree : Equatable where Body: Equatable {}

// Interface improvements (single-case enums are slightly awkward).
extension Tree {
  /// Creates a tree with `body` stored at the root node, `left` as its left
  /// subtree, and `right` as its right subtree.
  init(_ body: Body, _ left: Tree? = nil, _ right: Tree? = nil) {
    self = .o(body, left, right)
  }

  /// Accesses the value stored at the root node of `self`.
  public var body: Body {
    get {
      switch self { case let .o(v, _, _): return v }
    }
    set {
      switch self { case let .o(_, l, r): self = .o(newValue, l, r) }
    }
  }

  /// Accesses the left subtree of `self`.
  public var left: Tree? {
    get {
      switch self { case let .o(_, l, _): return l }
    }
    set {
      switch self { case let .o(v, _, r): self = .o(v, newValue, r) }
    }
  }

  /// Accesses the right subtree of `self`.
 public var right: Tree? {
    get {
      switch self { case let .o(_, _, r): return r }
    }
    set {
      switch self { case let .o(v, l, _): self = .o(v, l, newValue) }
    }
  }
}

//
// InstrumentedTree implementation
//


/// Global operation counters
var stats = (
    boxCreations: 0,
    boxDestructions: 0,
    bodyReads: 0,
    bodyWrites: 0,
    bodyModifys: 0,
    childReads: 0,
    childWrites: 0,
    childModifys: 0
  )

/// Resets all operation counts to zero.
///
/// When you want to measure the cost of one operation, call this first, then
/// `print(stats)`.
func resetStats() {
  stats = (0, 0, 0, 0, 0, 0, 0, 0)
}

/// A version of Tree that does all the copy-on-write by hand and counts the
/// operations, so you can measure efficiency of the paradigm.
///
/// Semantics are identical to Tree<Body>.
struct InstrumentedTree<Body> {
  private var box: Box

  /// Accesses the value stored at the root node of `self`.
  public var body: Body {
    get {
      stats.bodyReads += 1
      return box.body
    }
    set {
      stats.bodyWrites += 1
      if isKnownUniquelyReferenced(&box) { box.body = newValue }
      else { box = Box(newValue, box.left, box.right)}
    }
    _modify {
      if !isKnownUniquelyReferenced(&box) { box = box.clone() }
      stats.bodyModifys += 1
      yield &box.body
    }
  }

  /// Accesses the left subtree of `self`.
  public var left: Self? {
    get {
      stats.childReads += 1
      return box.left
    }
    set {
      stats.childWrites += 1
      if isKnownUniquelyReferenced(&box) { box.left = newValue }
      else { box = Box(box.body, newValue, box.right)}
    }
    _modify {
      if !isKnownUniquelyReferenced(&box) { box = box.clone() }
      stats.childModifys += 1
      yield &box.left
    }
  }

  /// Accesses the right subtree of `self`.
  public var right: Self? {
    get {
      stats.childReads += 1
      return box.right
    }
    set {
      stats.childWrites += 1
      if isKnownUniquelyReferenced(&box) { box.right = newValue }
      else { box = Box(box.body, box.left, newValue)}
    }
    _modify {
      if !isKnownUniquelyReferenced(&box) { box = box.clone() }
      stats.childModifys += 1
      yield &box.right
    }
  }

  /// Creates a tree with `body` stored at the root node, `left` as its left
  /// subtree, and `right` as its right subtree.
  public init(_ body: Body, _ leftChild: Self? = nil, _ rightChild: Self? = nil) {
    box = Box(body, leftChild, rightChild)
  }

  /// Indirect storage to support type recursion and instrumentation.
  private class Box {
    fileprivate var
      body: Body, left: InstrumentedTree?, right: InstrumentedTree?

    init(_ body: Body, _ left: InstrumentedTree?, _ right: InstrumentedTree?) {
      stats.boxCreations += 1
      self.body = body
      self.left = left
      self.right = right
    }

    func clone() -> Box {
      return Box(body, left, right)
    }

    deinit {
      stats.boxDestructions += 1
    }
  }
}

extension InstrumentedTree : Equatable where Body: Equatable {
  /// Returns true iff `l` is identical to `r`.
  static func ==(l: Self, r: Self) -> Bool {
    // Uncomment to optimize. I'm not sure whether the compiler does this
    // optimization, but in principle, it could:
    // l.box === r.box ||

    l.body == r.body && l.left == r.left && l.right == r.right
  }
}

extension InstrumentedTree: CustomStringConvertible {
  // Note: for diagnostic purposes only; does not contribute to operation count.
  var description: String {
    "(\(box.body), \(box.left.map(String.init) ?? "ε")"
    + ", \(box.right.map(String.init) ?? "ε"))"
  }
}

extension Tree: CustomStringConvertible {
  var description: String {
    "(\(body), \(left.map(String.init) ?? "ε")"
    + ", \(right.map(String.init) ?? "ε"))"
  }
}

extension Tree {
  func duplicated() -> Self {
    return Self(body, Self(body, left?.duplicated(), right?.duplicated()), nil)
  }

  mutating func duplicate() {
    left?.duplicate()
    right?.duplicate()
    self = Self(body, self)
  }
}

extension InstrumentedTree {
  func duplicated() -> Self {
    return Self(body, Self(body, left?.duplicated(), right?.duplicated()), nil)
  }

  mutating func duplicate() {
    left?.duplicate()
    right?.duplicate()
    self = Self(body, self)
  }
}

func demo() {
  print("------------- demo -----------")
  typealias T = InstrumentedTree<Int>
  let ε: T? = nil

  var x = T(1, T(2, ε, T(3, T(4), T(5))), T(6, T(7, T(8))))
  print(x)
  print(stats)
  resetStats()
  print()

  // Start mutating
  x.left!.body += 7
  print(stats)
  let y = x
  x.right!.body += 7
  // If y isn't used, its lifetime ends right away and we won't observe any box
  // allocations, so print it here.  Also show that we have value semantics by
  // demonstrating that it hasn't changed.
  print(y)
  print(x)
  print(stats)

  resetStats()
  print()

  assert(x != y)
  print(stats)

  var x1 = T(1, T(2, ε, T(3, T(4), T(5))), T(6, T(7, T(8))))

  print("nonmutating:")
  resetStats()
  let y1 = x1.duplicated()
  print(y1)
  print(stats)

  resetStats()
  print("mutating:")
  x1.duplicate()
  print(x1)
  print(stats)
}
demo()

// This merely shows we have the same API on both types.  Feel free to
// ignore/comment out the call.
func demo1() {
  print("------------- demo1 -----------")
  typealias T = Tree<Int>
  let ε: T? = nil

  var x = T(1, T(2, ε, T(3, T(4), T(5))), T(6, T(7, T(8))))
  print(x)
  x.left!.body += 7
  let y = x
  x.right!.body += 7
  print(y)
  print(x)

  assert(x != y)
}
demo1()
	/// Example of a recursive sum type representing a tree.
	///
	/// The compiler uses copy-on-write under the covers to give instances value
	/// semantics.
	indirect enum Tree<Body> {
	case o(_ body: Body, _ left: Tree?, _ right: Tree?)
	}

	extension Tree : Equatable where Body: Equatable {}

	// Interface improvements (single-case enums are slightly awkward).
	extension Tree {
	/// Creates a tree with `body` stored at the root node, `left` as its left
	/// subtree, and `right` as its right subtree.
	init(_ body: Body, _ left: Tree? = nil, _ right: Tree? = nil) {
	self = .o(body, left, right)
	}

	/// Accesses the value stored at the root node of `self`.
	public var body: Body {
	get {
	switch self { case let .o(v, _, _): return v }
	}
	set {
	switch self { case let .o(_, l, r): self = .o(newValue, l, r) }
	}
	}

	/// Accesses the left subtree of `self`.
	public var left: Tree? {
	get {
	switch self { case let .o(_, l, _): return l }
	}
	set {
	switch self { case let .o(v, _, r): self = .o(v, newValue, r) }
	}
	}

	/// Accesses the right subtree of `self`.
	public var right: Tree? {
	get {
	switch self { case let .o(_, _, r): return r }
	}
	set {
	switch self { case let .o(v, l, _): self = .o(v, l, newValue) }
	}
	}
	}

	//
	// InstrumentedTree implementation
	//


	/// Global operation counters
	var stats = (
	boxCreations: 0,
	boxDestructions: 0,
	bodyReads: 0,
	bodyWrites: 0,
	bodyModifys: 0,
	childReads: 0,
	childWrites: 0,
	childModifys: 0
	)

	/// Resets all operation counts to zero.
	///
	/// When you want to measure the cost of one operation, call this first, then
	/// `print(stats)`.
	func resetStats() {
	stats = (0, 0, 0, 0, 0, 0, 0, 0)
	}

	/// A version of Tree that does all the copy-on-write by hand and counts the
	/// operations, so you can measure efficiency of the paradigm.
	///
	/// Semantics are identical to Tree<Body>.
	struct InstrumentedTree<Body> {
	private var box: Box

	/// Accesses the value stored at the root node of `self`.
	public var body: Body {
	get {
	stats.bodyReads += 1
	return box.body
	}
	set {
	stats.bodyWrites += 1
	if isKnownUniquelyReferenced(&box) { box.body = newValue }
	else { box = Box(newValue, box.left, box.right)}
	}
	_modify {
	if !isKnownUniquelyReferenced(&box) { box = box.clone() }
	stats.bodyModifys += 1
	yield &box.body
	}
	}

	/// Accesses the left subtree of `self`.
	public var left: Self? {
	get {
	stats.childReads += 1
	return box.left
	}
	set {
	stats.childWrites += 1
	if isKnownUniquelyReferenced(&box) { box.left = newValue }
	else { box = Box(box.body, newValue, box.right)}
	}
	_modify {
	if !isKnownUniquelyReferenced(&box) { box = box.clone() }
	stats.childModifys += 1
	yield &box.left
	}
	}

	/// Accesses the right subtree of `self`.
	public var right: Self? {
	get {
	stats.childReads += 1
	return box.right
	}
	set {
	stats.childWrites += 1
	if isKnownUniquelyReferenced(&box) { box.right = newValue }
	else { box = Box(box.body, box.left, newValue)}
	}
	_modify {
	if !isKnownUniquelyReferenced(&box) { box = box.clone() }
	stats.childModifys += 1
	yield &box.right
	}
	}

	/// Creates a tree with `body` stored at the root node, `left` as its left
	/// subtree, and `right` as its right subtree.
	public init(_ body: Body, _ leftChild: Self? = nil, _ rightChild: Self? = nil) {
	box = Box(body, leftChild, rightChild)
	}

	/// Indirect storage to support type recursion and instrumentation.
	private class Box {
	fileprivate var
	body: Body, left: InstrumentedTree?, right: InstrumentedTree?

	init(_ body: Body, _ left: InstrumentedTree?, _ right: InstrumentedTree?) {
	stats.boxCreations += 1
	self.body = body
	self.left = left
	self.right = right
	}

	func clone() -> Box {
	return Box(body, left, right)
	}

	deinit {
	stats.boxDestructions += 1
	}
	}
	}

	extension InstrumentedTree : Equatable where Body: Equatable {
	/// Returns true iff `l` is identical to `r`.
	static func ==(l: Self, r: Self) -> Bool {
	// Uncomment to optimize. I'm not sure whether the compiler does this
	// optimization, but in principle, it could:
	// l.box === r.box \|\|

	l.body == r.body && l.left == r.left && l.right == r.right
	}
	}

	extension InstrumentedTree: CustomStringConvertible {
	// Note: for diagnostic purposes only; does not contribute to operation count.
	var description: String {
	"(\(box.body), \(box.left.map(String.init) ?? "ε")"
	+ ", \(box.right.map(String.init) ?? "ε"))"
	}
	}

	extension Tree: CustomStringConvertible {
	var description: String {
	"(\(body), \(left.map(String.init) ?? "ε")"
	+ ", \(right.map(String.init) ?? "ε"))"
	}
	}

	extension Tree {
	func duplicated() -> Self {
	return Self(body, Self(body, left?.duplicated(), right?.duplicated()), nil)
	}

	mutating func duplicate() {
	left?.duplicate()
	right?.duplicate()
	self = Self(body, self)
	}
	}

	extension InstrumentedTree {
	func duplicated() -> Self {
	return Self(body, Self(body, left?.duplicated(), right?.duplicated()), nil)
	}

	mutating func duplicate() {
	left?.duplicate()
	right?.duplicate()
	self = Self(body, self)
	}
	}

	func demo() {
	print("------------- demo -----------")
	typealias T = InstrumentedTree<Int>
	let ε: T? = nil

	var x = T(1, T(2, ε, T(3, T(4), T(5))), T(6, T(7, T(8))))
	print(x)
	print(stats)
	resetStats()
	print()

	// Start mutating
	x.left!.body += 7
	print(stats)
	let y = x
	x.right!.body += 7
	// If y isn't used, its lifetime ends right away and we won't observe any box
	// allocations, so print it here. Also show that we have value semantics by
	// demonstrating that it hasn't changed.
	print(y)
	print(x)
	print(stats)

	resetStats()
	print()

	assert(x != y)
	print(stats)

	var x1 = T(1, T(2, ε, T(3, T(4), T(5))), T(6, T(7, T(8))))

	print("nonmutating:")
	resetStats()
	let y1 = x1.duplicated()
	print(y1)
	print(stats)

	resetStats()
	print("mutating:")
	x1.duplicate()
	print(x1)
	print(stats)
	}
	demo()

	// This merely shows we have the same API on both types. Feel free to
	// ignore/comment out the call.
	func demo1() {
	print("------------- demo1 -----------")
	typealias T = Tree<Int>
	let ε: T? = nil

	var x = T(1, T(2, ε, T(3, T(4), T(5))), T(6, T(7, T(8))))
	print(x)
	x.left!.body += 7
	let y = x
	x.right!.body += 7
	print(y)
	print(x)

	assert(x != y)
	}
	demo1()