From 931c0c20882086d2e0074c3a23acff0aa68fbbfb Mon Sep 17 00:00:00 2001
From: Arnold Schwaighofer <aschwaighofer@apple.com>
Date: Mon, 9 Nov 2015 13:11:00 -0800
Subject: [PATCH] A copy-on-write data type

---
 .../SwiftExperimental/SwiftExperimental.swift      | 138 +++++++++++++++++++++
 1 file changed, 138 insertions(+)

diff --git a/stdlib/internal/SwiftExperimental/SwiftExperimental.swift b/stdlib/internal/SwiftExperimental/SwiftExperimental.swift
index 7e85e70..c8515d4 100644
--- a/stdlib/internal/SwiftExperimental/SwiftExperimental.swift
+++ b/stdlib/internal/SwiftExperimental/SwiftExperimental.swift
@@ -184,3 +184,141 @@ public func ⊉ <
   return !lhs.isSupersetOf(rhs)
 }
 
+/// The storage for the `Box` type.
+///
+/// Stores one 'T'.
+internal class _BoxStorage<T>
+  : CustomStringConvertible, CustomDebugStringConvertible {
+  internal final var value: T
+
+  init(_ elt: T) {
+    value = elt
+  }
+
+  @warn_unused_result
+  internal func _makeDescription(isDebug isDebug: Bool) -> String {
+    var result = ""
+    if isDebug {
+      result += "_BoxStorage("
+    }
+    debugPrint(value, terminator: "", toStream: &result)
+    if isDebug {
+      result += ")"
+    }
+    return result
+  }
+
+  internal var description : String {
+    @warn_unused_result
+    get {
+      return _makeDescription(isDebug: false)
+    }
+  }
+
+  internal var debugDescription : String {
+    @warn_unused_result
+    get {
+      return _makeDescription(isDebug: true)
+    }
+  }
+}
+
+/// 'Box' is a wrapper that stores the boxed value in a copy-on-write reference.
+///
+/// This type can be used to implement nested structures with value semantics
+/// without the cost of recurively copying values in the nested structure. The
+/// copy will occur only on modification of the structure due to the
+/// copy-on-write semantics.
+///
+/// Example:
+///
+/// We can implement a copy-on-write tree using `Box`. The cost of copying the
+/// entire tree on every assignment is avoided by wrapping the tree's nodes in a
+/// `Box`. When the tree is copied only the references to its sub-tree are
+/// copied breaking a potentially expensive recursive copy. Value semantics of
+/// the tree is preserved by the copy-on-write semantics of the `Box`.
+///
+/// struct Tree {
+///   var value: Int
+///   var left: Box<Tree?>
+///   var right: Box<Tree?>
+//
+///   init(_ v: Int) {
+///     value = v
+///     left = Box(nil)
+///     right = Box(nil)
+///   }
+///
+///   mutating func addSubTree(t: Tree) {
+///     if t.value < value {
+///       if left.value == nil {
+///         left.value = t
+///       } else {
+///         left.value!.addSubTree(t)
+///       }
+///     } else {
+///       if right.value == nil {
+///         right.value = t
+///       } else {
+///         right.value!.addSubTree(t)
+///       }
+///     }
+///   }
+/// }
+public struct Box<T>
+  : CustomStringConvertible, CustomDebugStringConvertible {
+
+  internal var _storage: _BoxStorage<T>
+
+  public init(_ elt: T) {
+    _storage = _BoxStorage(elt)
+  }
+
+  public var value : T {
+    @warn_unused_result
+    get {
+      return _storage.value
+    }
+
+    mutableAddressWithNativeOwner {
+      if !isUniquelyReferencedNonObjC(&_storage) {
+        _storage = _BoxStorage(_storage.value)
+      }
+      return (
+        UnsafeMutablePointer(Builtin.addressof(&_storage.value)),
+        Builtin.castToNativeObject(_storage))
+    }
+  }
+
+  @warn_unused_result
+  internal func _makeDescription(isDebug isDebug: Bool) -> String {
+    var result = ""
+    if isDebug {
+      debugPrint(_storage, terminator: "", toStream: &result)
+    } else {
+      print(_storage, terminator: "", toStream: &result)
+    }
+    return result
+  }
+
+  public var description : String {
+    @warn_unused_result
+    get {
+      return _makeDescription(isDebug: false)
+    }
+  }
+
+  public var debugDescription : String {
+    @warn_unused_result
+    get {
+      return _makeDescription(isDebug: true)
+    }
+  }
+
+  //@testable
+  public var _internalStorage : AnyObject {
+    get {
+      return _storage
+    }
+  }
+}
-- 
2.5.4 (Apple Git-61)