Problem with mutable views and COW


(Adrian Zubarev) #1

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
     
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
     
    var _storageReference: Storage
     
    public init() {
         
        self._storageReference = Storage()
    }
     
    public init(_ values: DocumentValues) {
         
        self._storageReference = values._storageReference
    }
     
    public var values: DocumentValues {
         
        get { return DocumentValues(self) }
         
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
     
    unowned var _storageReference: Storage
     
    init(_ document: Document) {
         
        self._storageReference = document._storageReference
    }
     
    public var startIndex: Int {
         
        return self._storageReference.keys.startIndex
    }
     
    public var endIndex: Int {
         
        return self._storageReference.keys.endIndex
    }
     
    public func index(after i: Int) -> Int {
         
        return self._storageReference.keys.index(after: i)
    }
     
    public subscript(position: Int) -> Int {
         
        get { return _storageReference.values[position] }
         
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
             
    if !isKnownUniquelyReferenced(&self._storageReference) {
                 
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

···

--
Adrian Zubarev
Sent with Airmail


(Karl) #2

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
     
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
     
    var _storageReference: Storage
     
    public init() {
         
        self._storageReference = Storage()
    }
     
    public init(_ values: DocumentValues) {
         
        self._storageReference = values._storageReference
    }
     
    public var values: DocumentValues {
         
        get { return DocumentValues(self) }
         
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
     
    unowned var _storageReference: Storage
     
    init(_ document: Document) {
         
        self._storageReference = document._storageReference
    }
     
    public var startIndex: Int {
         
        return self._storageReference.keys.startIndex
    }
     
    public var endIndex: Int {
         
        return self._storageReference.keys.endIndex
    }
     
    public func index(after i: Int) -> Int {
         
        return self._storageReference.keys.index(after: i)
    }
     
    public subscript(position: Int) -> Int {
         
        get { return _storageReference.values[position] }
         
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
             
    if !isKnownUniquelyReferenced(&self._storageReference) {
                 
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

This is kind of an invalid/unsafe design IMO; DocumentValues may escape the scope of the Document and the underlying storage may be deallocated.

Instead, I’d recommend a function:

func withDocumentValues<T>(_ invoke: (inout DocumentValues)->T) -> T {
  var view = DocumentValues(self)
        defer { _fixLifetime(view) }
        return invoke(&view)
}

(unfortunately, this isn’t completely safe because somebody could still copy the DocumentValues from their closure, the same way you can copy the pointer from String’s withCString, but that’s a limitation of Swift right now)

- Karl

···

On 18 Nov 2016, at 13:05, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:

CC: John McCall, because I read his suggestion in the thread about contiguous memory/borrowing that we could have a generalised @noescape. In this example, you would want the DocumentValues parameter in the closure to be @noescape.


(Zhao Xin) #3

Why is the second check false, even if the property is marked as unowned for

the view?

Please search the mailing list, this is not the first time it comes as a
new question. Shortly speaking, it is `false` only because you used
`unowned`. If you you can grantee it always exists. Just use it directly,
this is what `unowned` for. If you can't grantee that. You should use
`weak` and check it with `if let` or `if foo == nil`

Zhaoxin

···

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users < swift-users@swift.org> wrote:

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {

    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {

    var _storageReference: Storage

    public init() {

        self._storageReference = Storage()
    }

    public init(_ values: DocumentValues) {

        self._storageReference = values._storageReference
    }

    public var values: DocumentValues {

        get { return DocumentValues(self) }

        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {

    unowned var _storageReference: Storage

    init(_ document: Document) {

        self._storageReference = document._storageReference
    }

    public var startIndex: Int {

        return self._storageReference.keys.startIndex
    }

    public var endIndex: Int {

        return self._storageReference.keys.endIndex
    }

    public func index(after i: Int) -> Int {

        return self._storageReference.keys.index(after: i)
    }

    public subscript(position: Int) -> Int {

        get { return _storageReference.values[position] }

        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}

First of all the _storageReference property is unowned because I wanted
to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false

Why is the second check false, even if the property is marked as unowned
for the view?

Next up, I don’t have an idea how to correctly COW optimize this view.
Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10

VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`

We could change the subscript setter on the mutable view like this:

set {

    if !isKnownUniquelyReferenced(&self._storageReference) {

        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}

There is only one problem here. We’d end up cloning the storage every
time, because as shown in the very first example, even with unowned the
function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view
should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(John McCall) #4

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
     
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
     
    var _storageReference: Storage
     
    public init() {
         
        self._storageReference = Storage()
    }
     
    public init(_ values: DocumentValues) {
         
        self._storageReference = values._storageReference
    }
     
    public var values: DocumentValues {
         
        get { return DocumentValues(self) }
         
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
     
    unowned var _storageReference: Storage
     
    init(_ document: Document) {
         
        self._storageReference = document._storageReference
    }
     
    public var startIndex: Int {
         
        return self._storageReference.keys.startIndex
    }
     
    public var endIndex: Int {
         
        return self._storageReference.keys.endIndex
    }
     
    public func index(after i: Int) -> Int {
         
        return self._storageReference.keys.index(after: i)
    }
     
    public subscript(position: Int) -> Int {
         
        get { return _storageReference.values[position] }
         
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
             
    if !isKnownUniquelyReferenced(&self._storageReference) {
                 
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

This is kind of an invalid/unsafe design IMO; DocumentValues may escape the scope of the Document and the underlying storage may be deallocated.

Instead, I’d recommend a function:

func withDocumentValues<T>(_ invoke: (inout DocumentValues)->T) -> T {
  var view = DocumentValues(self)
        defer { _fixLifetime(view) }
        return invoke(&view)
}

(unfortunately, this isn’t completely safe because somebody could still copy the DocumentValues from their closure, the same way you can copy the pointer from String’s withCString, but that’s a limitation of Swift right now)

CC: John McCall, because I read his suggestion in the thread about contiguous memory/borrowing that we could have a generalised @noescape. In this example, you would want the DocumentValues parameter in the closure to be @noescape.

I think you guys understand this stuff, but let me talk through it, and I hope it will be illuminating about where we're thinking of taking the language.

In value semantics, you expect something like:
  let values = document.values
to produce an independent value, and mutations of it shouldn't affect the original document value.

But there is a situation where values aren't independent, which is when one value is just a projected component of another. In Swift, this is (currently, at least) always expressed with properties and subscripts. So when you write:
  document.values.mutateInSomeWay()
this is expected to actually change the document. So it makes language sense for views like "values" to be expressed in this way; the only question is whether that can be done efficiently while still providing a satisfactory level of safety etc.

When a property is actually stored directly in a value, Swift allows direct access to it (although for subscripts this mechanism is not currently documented + exposed, intentionally). This sort of direct access is optimal, but it's not general enough for use cases like views and slices because the slice value doesn't actually exist anywhere; it needs to be created. We do allow properties to be defined with get / set, but there are problems with that, which are exactly what you're seeing: slice values need to assert ownership of the underlying data if they're going to be used as independent values, but they also need to not assert ownership so that they don't interfere with copy-on-write. get / set isn't good enough for this because get is used to both derive an independent value (which should assert ownership) and initiate a mutation (which should not). The obvious solution is to allow a third accessor to be provided which is used when a value is mutated, as opposed to just copied (get) or overwritten whole-sale (set). We're still working out various ideas for how this will look at the language level.

So that would be sufficient to allow DocumentValues to store either a stong or an unowned reference to the storage, depending on how the property is being used. However, that creates the problem that, like with Karl's solution, the value can be copied during the mutation, and the user would expect that to create an independent value, i.e. to promote an unowned reference to strong. The most general solution for this is to provide some sort of "copy constructor" feature which would be used to create an independent value. But that's a pretty large hammer to pull out for this nail.

A third problem is that the original document can be copied and/or mutated during the projection of the DocumentValues, leaving the copy / the view in a potentially inconsistent state. But this is a problem that we expect to thoroughly solve with the ownership system, which will statically (or dynamically when necessary) prevent simultaneous conflicting accesses to a value.

In the meantime, I think the best alternative is to
  - allow the view to hold either an unowned or owned reference and
  - create a callback-based accessor like Karl's and document that copies from the value are not permitted

On a purely technical level:

print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

A function taking an "inout T" expects to be passed an l-value for an ordinary (strong) reference. Swift makes this work when passing an unowned or weak reference by passing a temporary variable holding a temporarily-promoted strong reference. That's usually good, but it's wrong for isKnownUniquelyReferenced, and even more unfortunately, I don't think there's any supported way to make this work in the current compiler; you need language support.

John.

···

On Nov 18, 2016, at 7:40 AM, Karl <razielim@gmail.com> wrote:

On 18 Nov 2016, at 13:05, Adrian Zubarev via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:


(Adrian Zubarev) #5

This doesn’t make any sense.

Somewhere from the Swift book:

Weak and unowned references enable one instance in a reference cycle to refer to the other instance without keeping a strong hold on it. The instances can then refer to each other without creating a strong reference cycle.
From the sdlib of the function isKnownUniquelyReferenced:

Returns a Boolean value indicating whether the given object is a class instance known to have a single strong reference.
unowned doesn’t increase the reference count, so the view in the examples I showed should have no strong reference to that class instance. The only strong reference that exists is from Document. So why exactly is the result of the second isKnownUniquelyReferenced call false again?

···

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 14:50:57, Zhao Xin (owenzx@gmail.com) schrieb:

Why is the second check false, even if the property is marked as unowned for the view?

Please search the mailing list, this is not the first time it comes as a new question. Shortly speaking, it is `false` only because you used `unowned`. If you you can grantee it always exists. Just use it directly, this is what `unowned` for. If you can't grantee that. You should use `weak` and check it with `if let` or `if foo == nil`

Zhaoxin

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:
Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
      
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
      
    var _storageReference: Storage
      
    public init() {
          
        self._storageReference = Storage()
    }
      
    public init(_ values: DocumentValues) {
          
        self._storageReference = values._storageReference
    }
      
    public var values: DocumentValues {
          
        get { return DocumentValues(self) }
          
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
      
    unowned var _storageReference: Storage
      
    init(_ document: Document) {
          
        self._storageReference = document._storageReference
    }
      
    public var startIndex: Int {
          
        return self._storageReference.keys.startIndex
    }
      
    public var endIndex: Int {
          
        return self._storageReference.keys.endIndex
    }
      
    public func index(after i: Int) -> Int {
          
        return self._storageReference.keys.index(after: i)
    }
      
    public subscript(position: Int) -> Int {
          
        get { return _storageReference.values[position] }
          
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
              
    if !isKnownUniquelyReferenced(&self._storageReference) {
                  
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Adrian Zubarev) #6

I apologize about the weak/unowned issue I mentioned. I kinda missed that portion from the docs Weak references do not affect the result of this function..

Okay it’s clear to me now why the result is evaluated as false.

But how do I solve the COW problem for mutable views?

···

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:04:55, Adrian Zubarev (adrian.zubarev@devandartist.com) schrieb:

This doesn’t make any sense.

Somewhere from the Swift book:

Weak and unowned references enable one instance in a reference cycle to refer to the other instance without keeping a strong hold on it. The instances can then refer to each other without creating a strong reference cycle.
From the sdlib of the function isKnownUniquelyReferenced:

Returns a Boolean value indicating whether the given object is a class instance known to have a single strong reference.
unowned doesn’t increase the reference count, so the view in the examples I showed should have no strong reference to that class instance. The only strong reference that exists is from Document. So why exactly is the result of the second isKnownUniquelyReferenced call false again?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 14:50:57, Zhao Xin (owenzx@gmail.com) schrieb:

Why is the second check false, even if the property is marked as unowned for the view?

Please search the mailing list, this is not the first time it comes as a new question. Shortly speaking, it is `false` only because you used `unowned`. If you you can grantee it always exists. Just use it directly, this is what `unowned` for. If you can't grantee that. You should use `weak` and check it with `if let` or `if foo == nil`

Zhaoxin

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:
Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
       
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
       
    var _storageReference: Storage
       
    public init() {
           
        self._storageReference = Storage()
    }
       
    public init(_ values: DocumentValues) {
           
        self._storageReference = values._storageReference
    }
       
    public var values: DocumentValues {
           
        get { return DocumentValues(self) }
           
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
       
    unowned var _storageReference: Storage
       
    init(_ document: Document) {
           
        self._storageReference = document._storageReference
    }
       
    public var startIndex: Int {
           
        return self._storageReference.keys.startIndex
    }
       
    public var endIndex: Int {
           
        return self._storageReference.keys.endIndex
    }
       
    public func index(after i: Int) -> Int {
           
        return self._storageReference.keys.index(after: i)
    }
       
    public subscript(position: Int) -> Int {
           
        get { return _storageReference.values[position] }
           
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
               
    if !isKnownUniquelyReferenced(&self._storageReference) {
                   
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Adrian Zubarev) #7

Ups sorry for CCing the post to the evolution list. That happens from time to time. :confused:

···

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:07:43, Adrian Zubarev (adrian.zubarev@devandartist.com) schrieb:

I apologize about the weak/unowned issue I mentioned. I kinda missed that portion from the docs Weak references do not affect the result of this function..

Okay it’s clear to me now why the result is evaluated as false.

But how do I solve the COW problem for mutable views?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:04:55, Adrian Zubarev (adrian.zubarev@devandartist.com) schrieb:

This doesn’t make any sense.

Somewhere from the Swift book:

Weak and unowned references enable one instance in a reference cycle to refer to the other instance without keeping a strong hold on it. The instances can then refer to each other without creating a strong reference cycle.
From the sdlib of the function isKnownUniquelyReferenced:

Returns a Boolean value indicating whether the given object is a class instance known to have a single strong reference.
unowned doesn’t increase the reference count, so the view in the examples I showed should have no strong reference to that class instance. The only strong reference that exists is from Document. So why exactly is the result of the second isKnownUniquelyReferenced call false again?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 14:50:57, Zhao Xin (owenzx@gmail.com) schrieb:

Why is the second check false, even if the property is marked as unowned for the view?

Please search the mailing list, this is not the first time it comes as a new question. Shortly speaking, it is `false` only because you used `unowned`. If you you can grantee it always exists. Just use it directly, this is what `unowned` for. If you can't grantee that. You should use `weak` and check it with `if let` or `if foo == nil`

Zhaoxin

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:
Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
        
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
        
    var _storageReference: Storage
        
    public init() {
            
        self._storageReference = Storage()
    }
        
    public init(_ values: DocumentValues) {
            
        self._storageReference = values._storageReference
    }
        
    public var values: DocumentValues {
            
        get { return DocumentValues(self) }
            
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
        
    unowned var _storageReference: Storage
        
    init(_ document: Document) {
            
        self._storageReference = document._storageReference
    }
        
    public var startIndex: Int {
            
        return self._storageReference.keys.startIndex
    }
        
    public var endIndex: Int {
            
        return self._storageReference.keys.endIndex
    }
        
    public func index(after i: Int) -> Int {
            
        return self._storageReference.keys.index(after: i)
    }
        
    public subscript(position: Int) -> Int {
            
        get { return _storageReference.values[position] }
            
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
                
    if !isKnownUniquelyReferenced(&self._storageReference) {
                    
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Karl) #8

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
     
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
     
    var _storageReference: Storage
     
    public init() {
         
        self._storageReference = Storage()
    }
     
    public init(_ values: DocumentValues) {
         
        self._storageReference = values._storageReference
    }
     
    public var values: DocumentValues {
         
        get { return DocumentValues(self) }
         
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
     
    unowned var _storageReference: Storage
     
    init(_ document: Document) {
         
        self._storageReference = document._storageReference
    }
     
    public var startIndex: Int {
         
        return self._storageReference.keys.startIndex
    }
     
    public var endIndex: Int {
         
        return self._storageReference.keys.endIndex
    }
     
    public func index(after i: Int) -> Int {
         
        return self._storageReference.keys.index(after: i)
    }
     
    public subscript(position: Int) -> Int {
         
        get { return _storageReference.values[position] }
         
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
             
    if !isKnownUniquelyReferenced(&self._storageReference) {
                 
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

This is kind of an invalid/unsafe design IMO; DocumentValues may escape the scope of the Document and the underlying storage may be deallocated.

Instead, I’d recommend a function:

func withDocumentValues<T>(_ invoke: (inout DocumentValues)->T) -> T {
  var view = DocumentValues(self)
        defer { _fixLifetime(view) }

Oops.. actually, I think this should be:
        defer { _fixLifetime(self) }

···

On 18 Nov 2016, at 16:40, Karl <raziel.im+swift-users@gmail.com> wrote:

On 18 Nov 2016, at 13:05, Adrian Zubarev via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

        return invoke(&view)
}

(unfortunately, this isn’t completely safe because somebody could still copy the DocumentValues from their closure, the same way you can copy the pointer from String’s withCString, but that’s a limitation of Swift right now)

CC: John McCall, because I read his suggestion in the thread about contiguous memory/borrowing that we could have a generalised @noescape. In this example, you would want the DocumentValues parameter in the closure to be @noescape.

- Karl


(Adrian Zubarev) #9

Hi John,

Thank you for your huge and informative answer. Only after reading it I’ve realized that I made a couple mistakes in my code snippets. Thank you for correcting me. :slight_smile:

I also have done some further digging and found a thread [swift-dev] [idle] COW wrapper in 30 lines which explains a few things.

I believe that magical language support, which only exists internally is currently called mutableAddressWithNativeOwner?!

I really wished I could build this now, but dropped the idea.

I probably move both arrays keys/values directly into document and make them as public internal(set) var and conform Document itself to MutableCollection to mutate the values array correctly.

Thank you very much for summing everything up nicely.

···

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 20:18:44, John McCall (rjmccall@apple.com) schrieb:

On Nov 18, 2016, at 7:40 AM, Karl <razielim@gmail.com> wrote:

On 18 Nov 2016, at 13:05, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
      
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
      
    var _storageReference: Storage
      
    public init() {
          
        self._storageReference = Storage()
    }
      
    public init(_ values: DocumentValues) {
          
        self._storageReference = values._storageReference
    }
      
    public var values: DocumentValues {
          
        get { return DocumentValues(self) }
          
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
      
    unowned var _storageReference: Storage
      
    init(_ document: Document) {
          
        self._storageReference = document._storageReference
    }
      
    public var startIndex: Int {
          
        return self._storageReference.keys.startIndex
    }
      
    public var endIndex: Int {
          
        return self._storageReference.keys.endIndex
    }
      
    public func index(after i: Int) -> Int {
          
        return self._storageReference.keys.index(after: i)
    }
      
    public subscript(position: Int) -> Int {
          
        get { return _storageReference.values[position] }
          
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
              
    if !isKnownUniquelyReferenced(&self._storageReference) {
                  
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

This is kind of an invalid/unsafe design IMO; DocumentValues may escape the scope of the Document and the underlying storage may be deallocated.

Instead, I’d recommend a function:

func withDocumentValues<T>(_ invoke: (inout DocumentValues)->T) -> T {
var view = DocumentValues(self)
defer { _fixLifetime(view) }
return invoke(&view)
}

(unfortunately, this isn’t completely safe because somebody could still copy the DocumentValues from their closure, the same way you can copy the pointer from String’s withCString, but that’s a limitation of Swift right now)

CC: John McCall, because I read his suggestion in the thread about contiguous memory/borrowing that we could have a generalised @noescape. In this example, you would want the DocumentValues parameter in the closure to be @noescape.

I think you guys understand this stuff, but let me talk through it, and I hope it will be illuminating about where we're thinking of taking the language.

In value semantics, you expect something like:
let values = document.values
to produce an independent value, and mutations of it shouldn't affect the original document value.

But there is a situation where values aren't independent, which is when one value is just a projected component of another. In Swift, this is (currently, at least) always expressed with properties and subscripts. So when you write:
document.values.mutateInSomeWay()
this is expected to actually change the document. So it makes language sense for views like "values" to be expressed in this way; the only question is whether that can be done efficiently while still providing a satisfactory level of safety etc.

When a property is actually stored directly in a value, Swift allows direct access to it (although for subscripts this mechanism is not currently documented + exposed, intentionally). This sort of direct access is optimal, but it's not general enough for use cases like views and slices because the slice value doesn't actually exist anywhere; it needs to be created. We do allow properties to be defined with get / set, but there are problems with that, which are exactly what you're seeing: slice values need to assert ownership of the underlying data if they're going to be used as independent values, but they also need to not assert ownership so that they don't interfere with copy-on-write. get / set isn't good enough for this because get is used to both derive an independent value (which should assert ownership) and initiate a mutation (which should not). The obvious solution is to allow a third accessor to be provided which is used when a value is mutated, as opposed to just copied (get) or overwritten whole-sale (set). We're still working out various ideas for how this will look at the language level.

So that would be sufficient to allow DocumentValues to store either a stong or an unowned reference to the storage, depending on how the property is being used. However, that creates the problem that, like with Karl's solution, the value can be copied during the mutation, and the user would expect that to create an independent value, i.e. to promote an unowned reference to strong. The most general solution for this is to provide some sort of "copy constructor" feature which would be used to create an independent value. But that's a pretty large hammer to pull out for this nail.

A third problem is that the original document can be copied and/or mutated during the projection of the DocumentValues, leaving the copy / the view in a potentially inconsistent state. But this is a problem that we expect to thoroughly solve with the ownership system, which will statically (or dynamically when necessary) prevent simultaneous conflicting accesses to a value.

In the meantime, I think the best alternative is to
- allow the view to hold either an unowned or owned reference and
- create a callback-based accessor like Karl's and document that copies from the value are not permitted

On a purely technical level:
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

A function taking an "inout T" expects to be passed an l-value for an ordinary (strong) reference. Swift makes this work when passing an unowned or weak reference by passing a temporary variable holding a temporarily-promoted strong reference. That's usually good, but it's wrong for isKnownUniquelyReferenced, and even more unfortunately, I don't think there's any supported way to make this work in the current compiler; you need language support.

John.


(Zhao Xin) #10

protocol Copyable {

    func copy() -> Self

}

final class Storage:Copyable {

    var keys: [String] = []

    var values: [Int] = []

    func copy() -> Storage {

        let s = Storage()

        s.keys = keys

        s.values = values

        return s

    }

}

public struct Document:Copyable {

    var _storageReference: Storage

    public init() {

        self._storageReference = Storage()

    }

    public init(_ values: DocumentValues) {

        self._storageReference = values._storageReference

    }

    public var values: DocumentValues {

        get { return DocumentValues(self) }

        set { self = Document(newValue) }

    }

    public func copy() -> Document {

        var d = Document()

        d._storageReference = _storageReference.copy()

        return d

    }

}

var document = Document()

let copy = document.copy()

// just assume we already added some values and can mutate safely on a
given index

// mutation in place

document.values[0] = 10 // <--- this will only mutate `document` but not
`copy`

You use `class` property inside `struct`, so the `struct` is no longer
copyable. You have to do it yourself.

Zhaoxin

···

On Fri, Nov 18, 2016 at 10:09 PM, Adrian Zubarev < adrian.zubarev@devandartist.com> wrote:

Ups sorry for CCing the post to the evolution list. That happens from time
to time. :confused:

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:07:43, Adrian Zubarev (
adrian.zubarev@devandartist.com) schrieb:

I apologize about the weak/unowned issue I mentioned. I kinda missed that
portion from the docs Weak references do not affect the result of this
function..

Okay it’s clear to me now why the result is evaluated as false.

But how do I solve the COW problem for mutable views?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:04:55, Adrian Zubarev (
adrian.zubarev@devandartist.com) schrieb:

This doesn’t make any sense.

Somewhere from the Swift book:

Weak and unowned references enable one instance in a reference cycle to
refer to the other instance *without keeping a strong hold on it*. The
instances can then refer to each other without creating a strong reference
cycle.

From the sdlib of the function isKnownUniquelyReferenced:

Returns a Boolean value indicating whether the given object is a class
instance known to have *a single strong reference*.

unowned doesn’t increase the reference count, so the view in the examples
I showed should have no strong reference to that class instance. The only
strong reference that exists is from Document. So why exactly is the
result of the second isKnownUniquelyReferenced call false again?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 14:50:57, Zhao Xin (owenzx@gmail.com) schrieb:

>Why is the second check false, even if the property is marked as unowned for
the view?

Please search the mailing list, this is not the first time it comes as a
new question. Shortly speaking, it is `false` only because you used
`unowned`. If you you can grantee it always exists. Just use it directly,
this is what `unowned` for. If you can't grantee that. You should use
`weak` and check it with `if let` or `if foo == nil`

Zhaoxin

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users < > swift-users@swift.org> wrote:

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {

    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {

    var _storageReference: Storage

    public init() {

        self._storageReference = Storage()
    }

    public init(_ values: DocumentValues) {

        self._storageReference = values._storageReference
    }

    public var values: DocumentValues {

        get { return DocumentValues(self) }

        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {

    unowned var _storageReference: Storage

    init(_ document: Document) {

        self._storageReference = document._storageReference
    }

    public var startIndex: Int {

        return self._storageReference.keys.startIndex
    }

    public var endIndex: Int {

        return self._storageReference.keys.endIndex
    }

    public func index(after i: Int) -> Int {

        return self._storageReference.keys.index(after: i)
    }

    public subscript(position: Int) -> Int {

        get { return _storageReference.values[position] }

        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}

First of all the _storageReference property is unowned because I wanted
to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false

Why is the second check false, even if the property is marked as unowned
for the view?

Next up, I don’t have an idea how to correctly COW optimize this view.
Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10

VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`

We could change the subscript setter on the mutable view like this:

set {

    if !isKnownUniquelyReferenced(&self._storageReference) {

        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}

There is only one problem here. We’d end up cloning the storage every
time, because as shown in the very first example, even with unowned the
function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view
should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Karl) #11

That’s very illuminating.

For pure ‘views’, I would actually approach it in a different way (and I wrote a bit about this a while back on the lists): those additional views should not be separate, concrete types with pointers back to the data; they should be protocols on a single type which owns the data. This would simplify situations like String’s various lazily-encoding UTF(8/16/32) views and make it easier to write generic code.

In C, we had one big global namespace. With C++, types could contain function members and became their own namespaces. I believe protocols in Swift should be separate namespaces below their types, and you should have unlimited freedom to name protocol members how you like, as well as conform to multiple overlapping protocols. For example, in my dreams String would be implemented something like this (just UTF8/16, for brevity):

protocol UTF8Sequence : Sequence where Element = UTF8CodePoint {}
protocol UTF16Sequence : Sequence where Element = UTF16CodePoint {}

struct String { /* ... */ }

extension String : UTF8Sequence {
    struct Iterator { /* UTF8-encoding iterator */ }
    func makeIterator() -> Iterator { return Iterator(_core) }
}

extension String : UTF16Sequence {
    struct Iterator { /* UTF16-encoding iterator */ }
    func makeIterator() -> Iterator { return Iterator(_core) }
}

type(of: “hello”.UTF8Sequence.makeIterator()) // String.UTF8Sequence.Iterator
type(of: “hello”.UTF16Sequence.makeIterator()) // String.UTF16Sequence.Iterator

The members which are bound to protocols would have that protocol mangled in to its name; so we’d have: String.UTF8Sequence.makeIterator() -> String.UTF8Sequence.Iterator.
This is only possible because each conformance to UTF8Sequence lives in a parallel universe with its own version of Sequence and any other inherited protocols; String.UTF8Sequence actually is the protocol witness table itself, and we are explicitly building up all of its requirements in its own little bubble. This allows us to do some pretty neat things, like represent the fact that every UTF8Sequence is also viewable as a sequence of characters:

protocol CharacterSequence : Sequence where Element = Character {}

protocol UTF8Sequence : CharacterSequence, Sequence where Element = UTF8CodePoint {}
extension UTF8Sequence { /* default implementation of CharacterSequence, which turns UTF8 codepoints -> Characters */ }

String, however, would implement CharacterSequence natively. So String’s UTF8Sequence.CharacterSequence witness table could redirect to those more efficient implementations, which don't encode to UTF8 as a middle-man:

extension String : UTF8Sequence {

// We need to implement:
// - Sequence (where Iterator.Element is a UTF8CodePoint) - required
// - Sequence (where Iterator.Element is a Character) — optionally, since there is a default

struct Iterator { /* UTF8-encoding iterator */ }
func makeIterator() -> Iterator { return Iterator(_core) }

// The type-checker could probably figure out which Iterator we mean here, but in cases where it can’t,
// we disambiguate by explicitly saying which conformance it belongs to.

typealias CharacterSequence.Iterator = String.CharacterSequence.Iterator
func CharacterSequence.makeIterator() -> String.CharacterSequence.Iterator { return self.CharacterSequence.makeIterator() }
}

func chant(_ thingToChant: CharacterSequence) {
  for character in thingToChant {
    print(“Give me a \(character)!”)
  }
}

chant(“hello") // String is a CharacterSequence, so String.CharacterSequence exists
chant(myCustomUTF8Sequence) // A UTF8Sequence is a CharacterSequence, so MyCustomUTF8Sequence.CharacterSequence exists (maybe pointing to the default witnesses, maybe not)

The unfortunate thing about this is that it can be a bit verbose at the usage-site. For the common case (i.e. everything today) where protocols don’t overlap, the compiler could easily disambiguate:

protocol A { func doSomething() }
extension A { func doSomethingElse() }

struct MyStruct : A {
    func doSomething() { … }
}

let aThing = MyStruct()
aThing.doSomething() // Compiler expands this to ‘aThing.A.doSomething()’
aThing.doSomethingElse() // Compiler expands this to ‘aThing.A.doSomethingElse()’

Since String could conform to CharacterSequence in multiple ways (natively, or via any of the UTF8/16 sequences), any algorithms we write in protocol extensions would not be unambiguous. I’m not sure how to solve that one.

- Karl

···

On 18 Nov 2016, at 20:18, John McCall <rjmccall@apple.com> wrote:

On Nov 18, 2016, at 7:40 AM, Karl <razielim@gmail.com <mailto:razielim@gmail.com>> wrote:

On 18 Nov 2016, at 13:05, Adrian Zubarev via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
     
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
     
    var _storageReference: Storage
     
    public init() {
         
        self._storageReference = Storage()
    }
     
    public init(_ values: DocumentValues) {
         
        self._storageReference = values._storageReference
    }
     
    public var values: DocumentValues {
         
        get { return DocumentValues(self) }
         
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
     
    unowned var _storageReference: Storage
     
    init(_ document: Document) {
         
        self._storageReference = document._storageReference
    }
     
    public var startIndex: Int {
         
        return self._storageReference.keys.startIndex
    }
     
    public var endIndex: Int {
         
        return self._storageReference.keys.endIndex
    }
     
    public func index(after i: Int) -> Int {
         
        return self._storageReference.keys.index(after: i)
    }
     
    public subscript(position: Int) -> Int {
         
        get { return _storageReference.values[position] }
         
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
             
    if !isKnownUniquelyReferenced(&self._storageReference) {
                 
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

This is kind of an invalid/unsafe design IMO; DocumentValues may escape the scope of the Document and the underlying storage may be deallocated.

Instead, I’d recommend a function:

func withDocumentValues<T>(_ invoke: (inout DocumentValues)->T) -> T {
  var view = DocumentValues(self)
        defer { _fixLifetime(view) }
        return invoke(&view)
}

(unfortunately, this isn’t completely safe because somebody could still copy the DocumentValues from their closure, the same way you can copy the pointer from String’s withCString, but that’s a limitation of Swift right now)

CC: John McCall, because I read his suggestion in the thread about contiguous memory/borrowing that we could have a generalised @noescape. In this example, you would want the DocumentValues parameter in the closure to be @noescape.

I think you guys understand this stuff, but let me talk through it, and I hope it will be illuminating about where we're thinking of taking the language.

In value semantics, you expect something like:
  let values = document.values
to produce an independent value, and mutations of it shouldn't affect the original document value.

But there is a situation where values aren't independent, which is when one value is just a projected component of another. In Swift, this is (currently, at least) always expressed with properties and subscripts. So when you write:
  document.values.mutateInSomeWay()
this is expected to actually change the document. So it makes language sense for views like "values" to be expressed in this way; the only question is whether that can be done efficiently while still providing a satisfactory level of safety etc.

When a property is actually stored directly in a value, Swift allows direct access to it (although for subscripts this mechanism is not currently documented + exposed, intentionally). This sort of direct access is optimal, but it's not general enough for use cases like views and slices because the slice value doesn't actually exist anywhere; it needs to be created. We do allow properties to be defined with get / set, but there are problems with that, which are exactly what you're seeing: slice values need to assert ownership of the underlying data if they're going to be used as independent values, but they also need to not assert ownership so that they don't interfere with copy-on-write. get / set isn't good enough for this because get is used to both derive an independent value (which should assert ownership) and initiate a mutation (which should not). The obvious solution is to allow a third accessor to be provided which is used when a value is mutated, as opposed to just copied (get) or overwritten whole-sale (set). We're still working out various ideas for how this will look at the language level.

So that would be sufficient to allow DocumentValues to store either a stong or an unowned reference to the storage, depending on how the property is being used. However, that creates the problem that, like with Karl's solution, the value can be copied during the mutation, and the user would expect that to create an independent value, i.e. to promote an unowned reference to strong. The most general solution for this is to provide some sort of "copy constructor" feature which would be used to create an independent value. But that's a pretty large hammer to pull out for this nail.

A third problem is that the original document can be copied and/or mutated during the projection of the DocumentValues, leaving the copy / the view in a potentially inconsistent state. But this is a problem that we expect to thoroughly solve with the ownership system, which will statically (or dynamically when necessary) prevent simultaneous conflicting accesses to a value.

In the meantime, I think the best alternative is to
  - allow the view to hold either an unowned or owned reference and
  - create a callback-based accessor like Karl's and document that copies from the value are not permitted

On a purely technical level:

print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

A function taking an "inout T" expects to be passed an l-value for an ordinary (strong) reference. Swift makes this work when passing an unowned or weak reference by passing a temporary variable holding a temporarily-promoted strong reference. That's usually good, but it's wrong for isKnownUniquelyReferenced, and even more unfortunately, I don't think there's any supported way to make this work in the current compiler; you need language support.

John.


(John McCall) #12

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
     
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
     
    var _storageReference: Storage
     
    public init() {
         
        self._storageReference = Storage()
    }
     
    public init(_ values: DocumentValues) {
         
        self._storageReference = values._storageReference
    }
     
    public var values: DocumentValues {
         
        get { return DocumentValues(self) }
         
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
     
    unowned var _storageReference: Storage
     
    init(_ document: Document) {
         
        self._storageReference = document._storageReference
    }
     
    public var startIndex: Int {
         
        return self._storageReference.keys.startIndex
    }
     
    public var endIndex: Int {
         
        return self._storageReference.keys.endIndex
    }
     
    public func index(after i: Int) -> Int {
         
        return self._storageReference.keys.index(after: i)
    }
     
    public subscript(position: Int) -> Int {
         
        get { return _storageReference.values[position] }
         
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
             
    if !isKnownUniquelyReferenced(&self._storageReference) {
                 
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

This is kind of an invalid/unsafe design IMO; DocumentValues may escape the scope of the Document and the underlying storage may be deallocated.

Instead, I’d recommend a function:

func withDocumentValues<T>(_ invoke: (inout DocumentValues)->T) -> T {
  var view = DocumentValues(self)
        defer { _fixLifetime(view) }
        return invoke(&view)
}

(unfortunately, this isn’t completely safe because somebody could still copy the DocumentValues from their closure, the same way you can copy the pointer from String’s withCString, but that’s a limitation of Swift right now)

CC: John McCall, because I read his suggestion in the thread about contiguous memory/borrowing that we could have a generalised @noescape. In this example, you would want the DocumentValues parameter in the closure to be @noescape.

I think you guys understand this stuff, but let me talk through it, and I hope it will be illuminating about where we're thinking of taking the language.

In value semantics, you expect something like:
  let values = document.values
to produce an independent value, and mutations of it shouldn't affect the original document value.

But there is a situation where values aren't independent, which is when one value is just a projected component of another. In Swift, this is (currently, at least) always expressed with properties and subscripts. So when you write:
  document.values.mutateInSomeWay()
this is expected to actually change the document. So it makes language sense for views like "values" to be expressed in this way; the only question is whether that can be done efficiently while still providing a satisfactory level of safety etc.

When a property is actually stored directly in a value, Swift allows direct access to it (although for subscripts this mechanism is not currently documented + exposed, intentionally). This sort of direct access is optimal, but it's not general enough for use cases like views and slices because the slice value doesn't actually exist anywhere; it needs to be created. We do allow properties to be defined with get / set, but there are problems with that, which are exactly what you're seeing: slice values need to assert ownership of the underlying data if they're going to be used as independent values, but they also need to not assert ownership so that they don't interfere with copy-on-write. get / set isn't good enough for this because get is used to both derive an independent value (which should assert ownership) and initiate a mutation (which should not). The obvious solution is to allow a third accessor to be provided which is used when a value is mutated, as opposed to just copied (get) or overwritten whole-sale (set). We're still working out various ideas for how this will look at the language level.

So that would be sufficient to allow DocumentValues to store either a stong or an unowned reference to the storage, depending on how the property is being used. However, that creates the problem that, like with Karl's solution, the value can be copied during the mutation, and the user would expect that to create an independent value, i.e. to promote an unowned reference to strong. The most general solution for this is to provide some sort of "copy constructor" feature which would be used to create an independent value. But that's a pretty large hammer to pull out for this nail.

A third problem is that the original document can be copied and/or mutated during the projection of the DocumentValues, leaving the copy / the view in a potentially inconsistent state. But this is a problem that we expect to thoroughly solve with the ownership system, which will statically (or dynamically when necessary) prevent simultaneous conflicting accesses to a value.

In the meantime, I think the best alternative is to
  - allow the view to hold either an unowned or owned reference and
  - create a callback-based accessor like Karl's and document that copies from the value are not permitted

On a purely technical level:

print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

A function taking an "inout T" expects to be passed an l-value for an ordinary (strong) reference. Swift makes this work when passing an unowned or weak reference by passing a temporary variable holding a temporarily-promoted strong reference. That's usually good, but it's wrong for isKnownUniquelyReferenced, and even more unfortunately, I don't think there's any supported way to make this work in the current compiler; you need language support.

John.

That’s very illuminating.

For pure ‘views’, I would actually approach it in a different way (and I wrote a bit about this a while back on the lists): those additional views should not be separate, concrete types with pointers back to the data; they should be protocols on a single type which owns the data. This would simplify situations like String’s various lazily-encoding UTF(8/16/32) views and make it easier to write generic code.

Leaving all else aside, this would help only for unparameterized views. The core team needs to solve slices, which are dynamically parameterized by the extents of the slice, and so will need to solve this more generally. I suspect that that more general solution will also be a more satisfactory solution to the less general problem of unparameterized slices.

John.

···

On Nov 18, 2016, at 3:10 PM, Karl <razielim@gmail.com> wrote:

On 18 Nov 2016, at 20:18, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

On Nov 18, 2016, at 7:40 AM, Karl <razielim@gmail.com <mailto:razielim@gmail.com>> wrote:

On 18 Nov 2016, at 13:05, Adrian Zubarev via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

In C, we had one big global namespace. With C++, types could contain function members and became their own namespaces. I believe protocols in Swift should be separate namespaces below their types, and you should have unlimited freedom to name protocol members how you like, as well as conform to multiple overlapping protocols. For example, in my dreams String would be implemented something like this (just UTF8/16, for brevity):

protocol UTF8Sequence : Sequence where Element = UTF8CodePoint {}
protocol UTF16Sequence : Sequence where Element = UTF16CodePoint {}

struct String { /* ... */ }

extension String : UTF8Sequence {
    struct Iterator { /* UTF8-encoding iterator */ }
    func makeIterator() -> Iterator { return Iterator(_core) }
}

extension String : UTF16Sequence {
    struct Iterator { /* UTF16-encoding iterator */ }
    func makeIterator() -> Iterator { return Iterator(_core) }
}

type(of: “hello”.UTF8Sequence.makeIterator()) // String.UTF8Sequence.Iterator
type(of: “hello”.UTF16Sequence.makeIterator()) // String.UTF16Sequence.Iterator

The members which are bound to protocols would have that protocol mangled in to its name; so we’d have: String.UTF8Sequence.makeIterator() -> String.UTF8Sequence.Iterator.
This is only possible because each conformance to UTF8Sequence lives in a parallel universe with its own version of Sequence and any other inherited protocols; String.UTF8Sequence actually is the protocol witness table itself, and we are explicitly building up all of its requirements in its own little bubble. This allows us to do some pretty neat things, like represent the fact that every UTF8Sequence is also viewable as a sequence of characters:

protocol CharacterSequence : Sequence where Element = Character {}

protocol UTF8Sequence : CharacterSequence, Sequence where Element = UTF8CodePoint {}
extension UTF8Sequence { /* default implementation of CharacterSequence, which turns UTF8 codepoints -> Characters */ }

String, however, would implement CharacterSequence natively. So String’s UTF8Sequence.CharacterSequence witness table could redirect to those more efficient implementations, which don't encode to UTF8 as a middle-man:

extension String : UTF8Sequence {

// We need to implement:
// - Sequence (where Iterator.Element is a UTF8CodePoint) - required
// - Sequence (where Iterator.Element is a Character) — optionally, since there is a default

struct Iterator { /* UTF8-encoding iterator */ }
func makeIterator() -> Iterator { return Iterator(_core) }

// The type-checker could probably figure out which Iterator we mean here, but in cases where it can’t,
// we disambiguate by explicitly saying which conformance it belongs to.

typealias CharacterSequence.Iterator = String.CharacterSequence.Iterator
func CharacterSequence.makeIterator() -> String.CharacterSequence.Iterator { return self.CharacterSequence.makeIterator() }
}

func chant(_ thingToChant: CharacterSequence) {
  for character in thingToChant {
    print(“Give me a \(character)!”)
  }
}

chant(“hello") // String is a CharacterSequence, so String.CharacterSequence exists
chant(myCustomUTF8Sequence) // A UTF8Sequence is a CharacterSequence, so MyCustomUTF8Sequence.CharacterSequence exists (maybe pointing to the default witnesses, maybe not)

The unfortunate thing about this is that it can be a bit verbose at the usage-site. For the common case (i.e. everything today) where protocols don’t overlap, the compiler could easily disambiguate:

protocol A { func doSomething() }
extension A { func doSomethingElse() }

struct MyStruct : A {
    func doSomething() { … }
}

let aThing = MyStruct()
aThing.doSomething() // Compiler expands this to ‘aThing.A.doSomething()’
aThing.doSomethingElse() // Compiler expands this to ‘aThing.A.doSomethingElse()’

Since String could conform to CharacterSequence in multiple ways (natively, or via any of the UTF8/16 sequences), any algorithms we write in protocol extensions would not be unambiguous. I’m not sure how to solve that one.

- Karl


(Adrian Zubarev) #13

I’m sorry but you seem not to understand what I’m asking for!

If you don’t know what a mutable view is, please read this proposal to get the basic idea: https://github.com/natecook1000/swift-evolution/blob/nc-dictionary-collections/proposals/0000-dictionary-key-and-value-collections.md

Your answer doesn’t make any sense.

···

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 16:05:25, Zhao Xin (owenzx@gmail.com) schrieb:

protocol Copyable {
func copy() -> Self
}

final class Storage:Copyable {

var keys: \[String\] = \[\]
var values: \[Int\] = \[\]

func copy\(\) \-&gt; Storage \{
    let s = Storage\(\)
    s\.keys = keys
    s\.values = values
    
    return s
\}

}

public struct Document:Copyable {

var \_storageReference: Storage

public init\(\) \{
    
    self\.\_storageReference = Storage\(\)
\}

public init\(\_ values: DocumentValues\) \{
    
    self\.\_storageReference = values\.\_storageReference
\}

public var values: DocumentValues \{
    
    get \{ return DocumentValues\(self\) \}
    
    set \{ self = Document\(newValue\) \}
\}

public func copy\(\) \-&gt; Document \{
    var d = Document\(\)
    d\.\_storageReference = \_storageReference\.copy\(\)
    
    return d
\}

}

var document = Document()

let copy = document.copy()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this will only mutate `document` but not `copy`

You use `class` property inside `struct`, so the `struct` is no longer copyable. You have to do it yourself.

Zhaoxin

On Fri, Nov 18, 2016 at 10:09 PM, Adrian Zubarev <adrian.zubarev@devandartist.com> wrote:
Ups sorry for CCing the post to the evolution list. That happens from time to time. :confused:

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:07:43, Adrian Zubarev (adrian.zubarev@devandartist.com) schrieb:

I apologize about the weak/unowned issue I mentioned. I kinda missed that portion from the docs Weak references do not affect the result of this function..

Okay it’s clear to me now why the result is evaluated as false.

But how do I solve the COW problem for mutable views?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:04:55, Adrian Zubarev (adrian.zubarev@devandartist.com) schrieb:

This doesn’t make any sense.

Somewhere from the Swift book:

Weak and unowned references enable one instance in a reference cycle to refer to the other instance without keeping a strong hold on it. The instances can then refer to each other without creating a strong reference cycle.
From the sdlib of the function isKnownUniquelyReferenced:

Returns a Boolean value indicating whether the given object is a class instance known to have a single strong reference.
unowned doesn’t increase the reference count, so the view in the examples I showed should have no strong reference to that class instance. The only strong reference that exists is from Document. So why exactly is the result of the second isKnownUniquelyReferenced call false again?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 14:50:57, Zhao Xin (owenzx@gmail.com) schrieb:

Why is the second check false, even if the property is marked as unowned for the view?

Please search the mailing list, this is not the first time it comes as a new question. Shortly speaking, it is `false` only because you used `unowned`. If you you can grantee it always exists. Just use it directly, this is what `unowned` for. If you can't grantee that. You should use `weak` and check it with `if let` or `if foo == nil`

Zhaoxin

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:
Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
         
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
         
    var _storageReference: Storage
         
    public init() {
             
        self._storageReference = Storage()
    }
         
    public init(_ values: DocumentValues) {
             
        self._storageReference = values._storageReference
    }
         
    public var values: DocumentValues {
             
        get { return DocumentValues(self) }
             
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
         
    unowned var _storageReference: Storage
         
    init(_ document: Document) {
             
        self._storageReference = document._storageReference
    }
         
    public var startIndex: Int {
             
        return self._storageReference.keys.startIndex
    }
         
    public var endIndex: Int {
             
        return self._storageReference.keys.endIndex
    }
         
    public func index(after i: Int) -> Int {
             
        return self._storageReference.keys.index(after: i)
    }
         
    public subscript(position: Int) -> Int {
             
        get { return _storageReference.values[position] }
             
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
                 
    if !isKnownUniquelyReferenced(&self._storageReference) {
                     
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Adrian Zubarev) #14

What exactly to you mean by unsafe/invalide? If you refer to unowned than yes this is incorrect. That was only part of the first question about isKnownUniquelyReferenced, where I myself missed the part from the docs that says that weak references don’t affect the result.

In general DocumentValues has a strong reference to the storage and should be able to outlive Document.

I borrowed the main idea from:

proposal: https://github.com/natecook1000/swift-evolution/blob/nc-dictionary-collections/proposals/0000-dictionary-key-and-value-collections.md
implementation: https://github.com/apple/swift/compare/master…natecook1000:nc-dictionary
But it uses some buildin stuff that I don’t have. :confused:

···

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 16:43:40, Karl (razielim@gmail.com) schrieb:

On 18 Nov 2016, at 16:40, Karl <raziel.im+swift-users@gmail.com> wrote:

On 18 Nov 2016, at 13:05, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
      
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
      
    var _storageReference: Storage
      
    public init() {
          
        self._storageReference = Storage()
    }
      
    public init(_ values: DocumentValues) {
          
        self._storageReference = values._storageReference
    }
      
    public var values: DocumentValues {
          
        get { return DocumentValues(self) }
          
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
      
    unowned var _storageReference: Storage
      
    init(_ document: Document) {
          
        self._storageReference = document._storageReference
    }
      
    public var startIndex: Int {
          
        return self._storageReference.keys.startIndex
    }
      
    public var endIndex: Int {
          
        return self._storageReference.keys.endIndex
    }
      
    public func index(after i: Int) -> Int {
          
        return self._storageReference.keys.index(after: i)
    }
      
    public subscript(position: Int) -> Int {
          
        get { return _storageReference.values[position] }
          
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
              
    if !isKnownUniquelyReferenced(&self._storageReference) {
                  
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

This is kind of an invalid/unsafe design IMO; DocumentValues may escape the scope of the Document and the underlying storage may be deallocated.

Instead, I’d recommend a function:

func withDocumentValues<T>(_ invoke: (inout DocumentValues)->T) -> T {
var view = DocumentValues(self)
defer { _fixLifetime(view) }

Oops.. actually, I think this should be:
defer { _fixLifetime(self) }

    return invoke\(&amp;view\)

}

(unfortunately, this isn’t completely safe because somebody could still copy the DocumentValues from their closure, the same way you can copy the pointer from String’s withCString, but that’s a limitation of Swift right now)

CC: John McCall, because I read his suggestion in the thread about contiguous memory/borrowing that we could have a generalised @noescape. In this example, you would want the DocumentValues parameter in the closure to be @noescape.

- Karl


(Zhao Xin) #15

Sorry. If you are doing something on implementing proposals, you should use
[swift-dev] list instead. Yes. I do don't know what the COW means.

Zhaoxin

···

On Fri, Nov 18, 2016 at 11:09 PM, Adrian Zubarev < adrian.zubarev@devandartist.com> wrote:

I’m sorry but you seem not to understand what I’m asking for!

If you don’t know what a mutable view is, please read this proposal to
get the basic idea: https://github.com/natecook1000/swift-evolution/
blob/nc-dictionary-collections/proposals/0000-dictionary-key-and-value-
collections.md

Your answer doesn’t make any sense.

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 16:05:25, Zhao Xin (owenzx@gmail.com) schrieb:

protocol Copyable {

    func copy() -> Self

}

final class Storage:Copyable {

    var keys: [String] = []

    var values: [Int] = []

    func copy() -> Storage {

        let s = Storage()

        s.keys = keys

        s.values = values

        return s

    }

}

public struct Document:Copyable {

    var _storageReference: Storage

    public init() {

        self._storageReference = Storage()

    }

    public init(_ values: DocumentValues) {

        self._storageReference = values._storageReference

    }

    public var values: DocumentValues {

        get { return DocumentValues(self) }

        set { self = Document(newValue) }

    }

    public func copy() -> Document {

        var d = Document()

        d._storageReference = _storageReference.copy()

        return d

    }

}

var document = Document()

let copy = document.copy()

// just assume we already added some values and can mutate safely on a
given index

// mutation in place

document.values[0] = 10 // <--- this will only mutate `document` but not
`copy`

You use `class` property inside `struct`, so the `struct` is no longer
copyable. You have to do it yourself.

Zhaoxin

On Fri, Nov 18, 2016 at 10:09 PM, Adrian Zubarev < > adrian.zubarev@devandartist.com> wrote:

Ups sorry for CCing the post to the evolution list. That happens from
time to time. :confused:

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:07:43, Adrian Zubarev (
adrian.zubarev@devandartist.com) schrieb:

I apologize about the weak/unowned issue I mentioned. I kinda missed
that portion from the docs Weak references do not affect the result of
this function..

Okay it’s clear to me now why the result is evaluated as false.

But how do I solve the COW problem for mutable views?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:04:55, Adrian Zubarev (
adrian.zubarev@devandartist.com) schrieb:

This doesn’t make any sense.

Somewhere from the Swift book:

Weak and unowned references enable one instance in a reference cycle to
refer to the other instance *without keeping a strong hold on it*. The
instances can then refer to each other without creating a strong reference
cycle.

From the sdlib of the function isKnownUniquelyReferenced:

Returns a Boolean value indicating whether the given object is a class
instance known to have *a single strong reference*.

unowned doesn’t increase the reference count, so the view in the
examples I showed should have no strong reference to that class instance.
The only strong reference that exists is from Document. So why exactly
is the result of the second isKnownUniquelyReferenced call false again?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 14:50:57, Zhao Xin (owenzx@gmail.com) schrieb:

>Why is the second check false, even if the property is marked as unowned for
the view?

Please search the mailing list, this is not the first time it comes as a
new question. Shortly speaking, it is `false` only because you used
`unowned`. If you you can grantee it always exists. Just use it directly,
this is what `unowned` for. If you can't grantee that. You should use
`weak` and check it with `if let` or `if foo == nil`

Zhaoxin

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users < >> swift-users@swift.org> wrote:

Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {

    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {

    var _storageReference: Storage

    public init() {

        self._storageReference = Storage()
    }

    public init(_ values: DocumentValues) {

        self._storageReference = values._storageReference
    }

    public var values: DocumentValues {

        get { return DocumentValues(self) }

        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {

    unowned var _storageReference: Storage

    init(_ document: Document) {

        self._storageReference = document._storageReference
    }

    public var startIndex: Int {

        return self._storageReference.keys.startIndex
    }

    public var endIndex: Int {

        return self._storageReference.keys.endIndex
    }

    public func index(after i: Int) -> Int {

        return self._storageReference.keys.index(after: i)
    }

    public subscript(position: Int) -> Int {

        get { return _storageReference.values[position] }

        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}

First of all the _storageReference property is unowned because I wanted
to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false

Why is the second check false, even if the property is marked as unowned
for the view?

Next up, I don’t have an idea how to correctly COW optimize this view.
Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10

VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`

We could change the subscript setter on the mutable view like this:

set {

    if !isKnownUniquelyReferenced(&self._storageReference) {

        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}

There is only one problem here. We’d end up cloning the storage every
time, because as shown in the very first example, even with unowned the
function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view
should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Adrian Zubarev) #16

Nah it’s okay mate. :wink: This is the right list, because I ask for help.

COW stands for copy-on-write. If you’re interesting on learning something new, read this paragraph https://github.com/apple/swift/blob/7e68e02b4eaa1cf44037a383129cbef60ea55d67/docs/OptimizationTips.rst#advice-use-copy-on-write-semantics-for-large-values

···

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 16:22:06, Zhao Xin (owenzx@gmail.com) schrieb:

Sorry. If you are doing something on implementing proposals, you should use [swift-dev] list instead. Yes. I do don't know what the COW means.

Zhaoxin

On Fri, Nov 18, 2016 at 11:09 PM, Adrian Zubarev <adrian.zubarev@devandartist.com> wrote:
I’m sorry but you seem not to understand what I’m asking for!

If you don’t know what a mutable view is, please read this proposal to get the basic idea: https://github.com/natecook1000/swift-evolution/blob/nc-dictionary-collections/proposals/0000-dictionary-key-and-value-collections.md

Your answer doesn’t make any sense.

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 16:05:25, Zhao Xin (owenzx@gmail.com) schrieb:

protocol Copyable {
func copy() -> Self
}

final class Storage:Copyable {

var keys: \[String\] = \[\]
var values: \[Int\] = \[\]

func copy\(\) \-&gt; Storage \{
    let s = Storage\(\)
    s\.keys = keys
    s\.values = values
    
    return s
\}

}

public struct Document:Copyable {

var \_storageReference: Storage

public init\(\) \{
    
    self\.\_storageReference = Storage\(\)
\}

public init\(\_ values: DocumentValues\) \{
    
    self\.\_storageReference = values\.\_storageReference
\}

public var values: DocumentValues \{
    
    get \{ return DocumentValues\(self\) \}
    
    set \{ self = Document\(newValue\) \}
\}

public func copy\(\) \-&gt; Document \{
    var d = Document\(\)
    d\.\_storageReference = \_storageReference\.copy\(\)
    
    return d
\}

}

var document = Document()

let copy = document.copy()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this will only mutate `document` but not `copy`

You use `class` property inside `struct`, so the `struct` is no longer copyable. You have to do it yourself.

Zhaoxin

On Fri, Nov 18, 2016 at 10:09 PM, Adrian Zubarev <adrian.zubarev@devandartist.com> wrote:
Ups sorry for CCing the post to the evolution list. That happens from time to time. :confused:

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:07:43, Adrian Zubarev (adrian.zubarev@devandartist.com) schrieb:

I apologize about the weak/unowned issue I mentioned. I kinda missed that portion from the docs Weak references do not affect the result of this function..

Okay it’s clear to me now why the result is evaluated as false.

But how do I solve the COW problem for mutable views?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 15:04:55, Adrian Zubarev (adrian.zubarev@devandartist.com) schrieb:

This doesn’t make any sense.

Somewhere from the Swift book:

Weak and unowned references enable one instance in a reference cycle to refer to the other instance without keeping a strong hold on it. The instances can then refer to each other without creating a strong reference cycle.
From the sdlib of the function isKnownUniquelyReferenced:

Returns a Boolean value indicating whether the given object is a class instance known to have a single strong reference.
unowned doesn’t increase the reference count, so the view in the examples I showed should have no strong reference to that class instance. The only strong reference that exists is from Document. So why exactly is the result of the second isKnownUniquelyReferenced call false again?

--
Adrian Zubarev
Sent with Airmail

Am 18. November 2016 um 14:50:57, Zhao Xin (owenzx@gmail.com) schrieb:

Why is the second check false, even if the property is marked as unowned for the view?

Please search the mailing list, this is not the first time it comes as a new question. Shortly speaking, it is `false` only because you used `unowned`. If you you can grantee it always exists. Just use it directly, this is what `unowned` for. If you can't grantee that. You should use `weak` and check it with `if let` or `if foo == nil`

Zhaoxin

On Fri, Nov 18, 2016 at 8:05 PM, Adrian Zubarev via swift-users <swift-users@swift.org> wrote:
Hi there,

I just can’t get my head around mutable views and COW.

Here is a small example:

final class Storage {
          
    var keys: [String] = []
    var values: [Int] = []
}

public struct Document {
          
    var _storageReference: Storage
          
    public init() {
              
        self._storageReference = Storage()
    }
          
    public init(_ values: DocumentValues) {
              
        self._storageReference = values._storageReference
    }
          
    public var values: DocumentValues {
              
        get { return DocumentValues(self) }
              
        set { self = Document(newValue) }
    }
}

public struct DocumentValues : MutableCollection {
          
    unowned var _storageReference: Storage
          
    init(_ document: Document) {
              
        self._storageReference = document._storageReference
    }
          
    public var startIndex: Int {
              
        return self._storageReference.keys.startIndex
    }
          
    public var endIndex: Int {
              
        return self._storageReference.keys.endIndex
    }
          
    public func index(after i: Int) -> Int {
              
        return self._storageReference.keys.index(after: i)
    }
          
    public subscript(position: Int) -> Int {
              
        get { return _storageReference.values[position] }
              
        set { self._storageReference.values[position] = newValue } // That will break COW
    }
}
First of all the _storageReference property is unowned because I wanted to check the following:

var document = Document()

print(CFGetRetainCount(document._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&document._storageReference)) // true

var values = document.values

print(CFGetRetainCount(values._storageReference)) //=> 2
print(isKnownUniquelyReferenced(&values._storageReference)) // false
Why is the second check false, even if the property is marked as unowned for the view?

Next up, I don’t have an idea how to correctly COW optimize this view. Assume the following scenario:

Scenario A:

var document = Document()

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10
VS:

Scenario B:

var document = Document()

let copy = document

// just assume we already added some values and can mutate safely on a given index
// mutation in place
document.values[0] = 10 // <--- this should only mutate `document` but not `copy`
We could change the subscript setter on the mutable view like this:

set {
                  
    if !isKnownUniquelyReferenced(&self._storageReference) {
                      
        self._storageReference = ... // clone
    }
    self._storageReference.values[position] = newValue
}
There is only one problem here. We’d end up cloning the storage every time, because as shown in the very first example, even with unowned the function isKnownUniquelyReferenced will return false for scenario A.

Any suggestions?

PS: In general I also wouldn’t want to use unowned because the view should be able to outlive it’s parent.

--
Adrian Zubarev
Sent with Airmail

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users