> On Sep 19, 2016, at 3:18 AM, Adrian Zubarev via swift-evolution
> <swift-evolution@swift.org> wrote:
>
> I think I just found a solution to my problem:
>
> /// - Parameter child: The new `child` to add to the `children` array.
> public mutating func add(_ child: Element) {
>
> let clonedChildReference = Reference(cloning: child.reference)
> let index = self.reference.children.endIndex
>
> self.mutableInsert(clonedChildReference, at: index, isNotOwnReference:
> child.reference !== self.reference)
> }
>
> /// Warning: Pass only clonded nodes of type Element to this function!
> private mutating func mutableInsert(_ node: XML.Node, at index: Int,
> isNotOwnReference: Bool) {
>
> // * If `self.reference` is NOT uniquely referenced and `node` is a String,
> // we should rebuilt own reference.
> // * If `self.reference` is NOT uniquely referenced and `node` is a
> Reference
> // `isNotOwnReference` is true, we should rebuilt own reference.
> // * If `self.reference` is NOT uniquely referenced and `node` is a clone
> // reference to `self.reference` where is `isNotOwnReference` is false,
> we
> // should check if there are more than **two** strong references to
> rebuild
> // own reference, otherwise it's an implementation artifact and we can
> keep
> // old reference (any `node` of type Reference is cloned before it's
> added
> // to the child array).
> let isNotKnownUniquelyReferenced =
> !isKnownUniquelyReferenced(&self.reference)
>
> var shouldRebuildReference = false
>
> switch node.kind {
>
> case .element(_):
> let hasMoreThanTwoStrongReferences = (CFGetRetainCount(self.reference)
> - 1) > 2
> shouldRebuildReference = (isNotKnownUniquelyReferenced &&
> isNotOwnReference) || hasMoreThanTwoStrongReferences
>
> case .text(_):
> shouldRebuildReference = isNotKnownUniquelyReferenced
> }
>
> if shouldRebuildReference {
>
> self.reference = Reference(cloning: self.reference, wholeTree: true)
> }
>
> self.reference.insert(node, at: index)
> }
> I’m using CFGetRetainCount(self.reference) to catch that implementation
> artifact.
>
If people are resorting to CFGetRetainCount, then we have a problem. The
optimizer is not under any obligation to bump the refcount to 2.
There must be a better way to handle this. Rather than passing an
'isNotOwnReference' flag, I think you should determine whether a clone
is needed before passing the node into mutableInsert.
You effectively want an API like root.addSelf().
-Andy
>
>
>
> --
> Adrian Zubarev
> Sent with Airmail
>
> Am 19. September 2016 um 09:59:24, Adrian Zubarev
> (adrian.zuba...@devandartist.com <mailto:adrian.zuba...@devandartist.com>)
> schrieb:
>
>> Hello Dave,
>>
>> thank you for trying to help me. I’ll try to explain the issue with some
>> more details.
>>
>> First here is some code:
>>
>> extension XML {
>>
>> public struct Element {
>>
>> // public for testing
>> public var reference: Reference
>>
>> public var name: String { return self.reference.name }
>>
>> public var children: [Element] {
>>
>> return self.reference.children.flatMap {
>>
>> guard case .element(let element) = $0.kind else { return nil
>> }
>> return Element(wrapping: element)
>> }
>> }
>>
>> public init(name: String) {
>>
>> self.reference = Reference(name: name)
>> }
>>
>> public mutating func add(_ child: Element) {
>>
>> self.mutableInsert(Reference(cloning: child.reference), at:
>> self.reference.children.endIndex)
>> }
>>
>> // Ignore XML.Node, it's a String or Reference
>> // Parameter `Node` is assumed to be a clone of a reference passed
>> to `add` or `insert` method.
>> private mutating func mutableInsert(_ node: XML.Node, at index: Int)
>> {
>>
>> // Clone own reference all way up to the root
>> if !isKnownUniquelyReferenced(&self.reference) {
>>
>> self.reference = Reference(cloning: self.reference,
>> wholeTree: true)
>> }
>>
>> // Extract a reference or just insert a string as a child
>> guard case .element(let nodeReference) = node.kind else {
>>
>> self.reference.insert(node, at: index)
>> return
>> }
>>
>> // Check for possible debelopment bug
>> if nodeReference === self.reference {
>>
>> fatalError("wrong usage of `mutableInsert` function")
>> }
>>
>> self.reference.insert(nodeReference, at: index)
>> }
>>
>> ...
>> }
>> }
>>
>> extension XML.Element {
>>
>> // public for testing
>> public class Reference : XML.Node {
>>
>> let name: String
>>
>> private(set) weak var parent: Reference?
>>
>> private(set) var children: [XML.Node]
>>
>> var kind: XML.Node.Kind { return .element(self) }
>>
>> ...
>> }
>> }
>> Now lets focus on the problem.
>>
>> Every Element is baked with it’s own Reference to be able to traverse the
>> tree from any of it’s node all way up to the root for example.
>>
>> Lets look again at the scenario I already described:
>>
>> var root = XML.Element(name: "root")
>> var elem = XML.Element(name: "elem")
>>
>> ObjectIdentifier(root.reference) // 0x000060000026ab40
>> ObjectIdentifier(elem.reference) // 0x000060800026bb00
>>
>> isKnownUniquelyReferenced(&root.reference) // true
>> isKnownUniquelyReferenced(&elem.reference) // true
>>
>> root.add(elem)
>>
>> isKnownUniquelyReferenced(&root.reference) // true
>>
>> root.add(root)
>>
>> // The reference of root has changed even if the second child
>> // was cloned and added as a new object to the reference.
>> // 0x000060000026ab40 <-- was thrown away
>> isKnownUniquelyReferenced(&root.reference) // true
>>
>> ObjectIdentifier(root.reference) // 0x000060000026c680 <— new one
>> The way I’m adding children to the tree is that every passed element of type
>> XML.Element stores a Reference, which will be cloned and added as a new
>> standalone object to the children array.
>>
>> The same happens when we try adding root as it’s own child. We copy root
>> struct which contains the same reference, then we clone it inside add
>> method, then we pass the new object to the mutableInsert function. At that
>> point we don’t need the old reference anymore, I’m speaking of
>> root.add(root). The problem here is that at that time root.reference has 2
>> strong references which I cannot escape.
>>
>> I could workaround the problem if I knew the reference counter value,
>> because I could check if the passed Element contains the same reference
>> first. And if it does and we have exactly 2 strong references, I don’t need
>> to recreate root.reference here.
>>
>> But I couldn’t find any API for that. :/
>>
>>
>>
>> --
>> Adrian Zubarev
>> Sent with Airmail
>>
>> Am 19. September 2016 um 05:50:57, Dave Abrahams via swift-users
>> (swift-us...@swift.org <mailto:swift-us...@swift.org>) schrieb:
>>
>>>
>>> on Sun Sep 18 2016, Adrian Zubarev <swift-users-AT-swift.org> wrote:
>>>
>>> > Dear Swift community,
>>> >
>>> > currently I’m building a value type XML library which is baked behind
>>> > the scene with a reference type to manage graph traversing between
>>> > nodes. I also like to COW optimize the xml graph, but I run into one
>>> > single problem atm.
>>> >
>>> > Image this xml tree:
>>> >
>>> > <root>
>>> > <item/>
>>> > </root>
>>> > It’s just a root element with one single child. As for value types it
>>> > should be totally fine to do something like this:
>>> >
>>> > // The given xml tree
>>> > var root = XML.Element(name: "root")
>>> > let item = XML.Element(name: "item")
>>> > root.add(item)
>>> >
>>> > // The problematic behavior
>>> > root.add(root)
>>> > If this would be a simple value type without any references behind the
>>> > scenes you could imagine that the result of the last code line will
>>> > look like this:
>>> >
>>> > <root>
>>> > <item/>
>>> > <root>
>>> > <item/>
>>> > </root>
>>> > </root>
>>>
>>> Yep, that's exactly the right answer for a tree with value semantics.
>>> The simplest way to implement this tree is to use an Array for the child
>>> nodes.
>>>
>>> > Basically we copied the whole tree and added it as the second child
>>> > into the original root element.
>>> >
>>> > As for COW optimization this is a problem, just because the passed
>>> > root is a copy of a struct that contains the exact same reference as
>>> > the original root element.
>>>
>>> I don't understand why that's a problem.
>>>
>>> > isKnownUniquelyReferenced(&self.reference) will result in false inside
>>> > the add method.
>>>
>>> ...as it should.
>>>
>>> > Is there any chance I could force my program to decrease the reference
>>> > counter of that last item after I’m sure I don’t need it?!
>>>
>>> Which last item? When are you sure you don't need it? What result do
>>> you hope for?
>>>
>>> > A few more details: inside the add method I’m always cloning the
>>> > passed reference just because graphs aren’t that trivial and otherwise
>>> > I could possibly end up with a cycle graph, which would be really
>>> > bad. After that job I’m sure that I don’t need the passed reference
>>> > anymore and I need a way to escape from it.
>>> >
>>> > I’d appreciate any suggestions and help. :)
>>>
>>> It's not clear what you want to acheive nor can I picture the code
>>> you're using to acheive it, so it's hard to give useful feedback.
>>>
>>> Sorry,
>>>
>>> --
>>> -Dave
>>>
>>> _______________________________________________
>>> swift-users mailing list
>>> swift-us...@swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-users
>>
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution@swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution
