<html><head><style>
body {
font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
padding:1em;
margin:auto;
background:#fefefe;
}
h1, h2, h3, h4, h5, h6 {
font-weight: bold;
}
h1 {
color: #000000;
font-size: 28pt;
}
h2 {
border-bottom: 1px solid #CCCCCC;
color: #000000;
font-size: 24px;
}
h3 {
font-size: 18px;
}
h4 {
font-size: 16px;
}
h5 {
font-size: 14px;
}
h6 {
color: #777777;
background-color: inherit;
font-size: 14px;
}
hr {
height: 0.2em;
border: 0;
color: #CCCCCC;
background-color: #CCCCCC;
display: inherit;
}
p, blockquote, ul, ol, dl, li, table, pre {
margin: 15px 0;
}
a, a:visited {
color: #4183C4;
background-color: inherit;
text-decoration: none;
}
#message {
border-radius: 6px;
border: 1px solid #ccc;
display:block;
width:100%;
height:60px;
margin:6px 0px;
}
button, #ws {
font-size: 12 pt;
padding: 4px 6px;
border-radius: 5px;
border: 1px solid #bbb;
background-color: #eee;
}
code, pre, #ws, #message {
font-family: Monaco;
font-size: 10pt;
border-radius: 3px;
background-color: #F8F8F8;
color: inherit;
}
code {
border: 1px solid #EAEAEA;
margin: 0 2px;
padding: 0 5px;
}
pre {
border: 1px solid #CCCCCC;
overflow: auto;
padding: 4px 8px;
}
pre > code {
border: 0;
margin: 0;
padding: 0;
}
#ws { background-color: #f8f8f8; }
.bloop_markdown table {
border-collapse: collapse;
font-family: Helvetica, arial, freesans, clean, sans-serif;
color: rgb(51, 51, 51);
font-size: 15px; line-height: 25px;
padding: 0; }
.bloop_markdown table tr {
border-top: 1px solid #cccccc;
background-color: white;
margin: 0;
padding: 0; }
.bloop_markdown table tr:nth-child(2n) {
background-color: #f8f8f8; }
.bloop_markdown table tr th {
font-weight: bold;
border: 1px solid #cccccc;
margin: 0;
padding: 6px 13px; }
.bloop_markdown table tr td {
border: 1px solid #cccccc;
margin: 0;
padding: 6px 13px; }
.bloop_markdown table tr th :first-child, table tr td :first-child {
margin-top: 0; }
.bloop_markdown table tr th :last-child, table tr td :last-child {
margin-bottom: 0; }
.bloop_markdown blockquote{
border-left: 4px solid #dddddd;
padding: 0 15px;
color: #777777; }
blockquote > :first-child {
margin-top: 0; }
blockquote > :last-child {
margin-bottom: 0; }
code, pre, #ws, #message {
word-break: normal;
word-wrap: normal;
}
hr {
display: inherit;
}
.bloop_markdown :first-child {
-webkit-margin-before: 0;
}
code, pre, #ws, #message {
font-family: Menlo, Consolas, Liberation Mono, Courier, monospace;
}
.send { color:#77bb77; }
.server { color:#7799bb; }
.error { color:#AA0000; }</style></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class="bloop_markdown"><p>I think I just found a solution to my problem:</p>
<pre><code class="swift">/// - 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)
}
</code></pre>
<p>I’m using <code>CFGetRetainCount(self.reference)</code> to catch that implementation artifact.</p>
<p></p></div><div class="bloop_original_html"><style>body{font-family:Helvetica,Arial;font-size:13px}</style><div id="bloop_customfont" style="font-family:Helvetica,Arial;font-size:13px; color: rgba(0,0,0,1.0); margin: 0px; line-height: auto;"><br></div> <br> <div id="bloop_sign_1474279558626446848" class="bloop_sign"><div style="font-family:helvetica,arial;font-size:13px">-- <br>Adrian Zubarev<br>Sent with Airmail</div></div> <br><p class="airmail_on">Am 19. September 2016 um 09:59:24, Adrian Zubarev (<a href="mailto:adrian.zubarev@devandartist.com">adrian.zubarev@devandartist.com</a>) schrieb:</p> <blockquote type="cite" class="clean_bq"><span><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div></div><div>
<title></title>
<div class="bloop_markdown">
<p>Hello Dave,</p>
<p>thank you for trying to help me. I’ll try to explain the issue
with some more details.</p>
<p>First here is some code:</p>
<pre><code class="swift">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) }
...
}
}
</code></pre>
<p>Now lets focus on the problem.</p>
<p>Every <code>Element</code> is baked with it’s own
<code>Reference</code> to be able to traverse the tree from any of
it’s node all way up to the root for example.</p>
<p>Lets look again at the scenario I already described:</p>
<pre><code class="swift">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
</code></pre>
<p>The way I’m adding children to the tree is that every passed
element of type <code>XML.Element</code> stores a
<code>Reference</code>, which will be cloned and added as a new
standalone object to the children array.</p>
<p>The same happens when we try adding <code>root</code> as it’s
own child. We copy <code>root</code> struct which contains the same
reference, then we clone it inside <code>add</code> method, then we
pass the new object to the <code>mutableInsert</code> function. At
that point we don’t need the old reference anymore, I’m speaking of
<code>root.add(root)</code>. The problem here is that at that time
<code>root.reference</code> has 2 strong references which I cannot
escape.</p>
<p>I could workaround the problem if I knew the reference counter
value, because I could check if the passed <code>Element</code>
contains the same reference first. And if it does and we have
exactly 2 strong references, I don’t need to recreate
<code>root.reference</code> here.</p>
<p>But I couldn’t find any API for that. :/</p>
</div>
<div class="bloop_original_html">
<div id="bloop_customfont" style="font-family:Helvetica,Arial;font-size:13px; color: rgba(0,0,0,1.0); margin: 0px; line-height: auto;">
<br></div>
<br>
<div id="bloop_sign_1474267770105763840" class="bloop_sign">
<div style="font-family:helvetica,arial;font-size:13px">
-- <br>
Adrian Zubarev<br>
Sent with Airmail</div>
</div>
<br>
<p class="airmail_on">Am 19. September 2016 um 05:50:57, Dave
Abrahams via swift-users (<a href="mailto:swift-users@swift.org">swift-users@swift.org</a>)
schrieb:</p>
<blockquote type="cite" class="clean_bq">
<div>
<div><span><br>
on Sun Sep 18 2016, Adrian Zubarev <swift-users-AT-swift.org>
wrote:<br>
<br>
> Dear Swift community,<br>
><br>
> currently I’m building a value type XML library which is baked
behind<br>
> the scene with a reference type to manage graph traversing
between<br>
> nodes. I also like to COW optimize the xml graph, but I run
into one<br>
> single problem atm.<br>
><br>
> Image this xml tree:<br>
><br>
> <root><br>
> <item/><br>
> </root><br>
> It’s just a root element with one single child. As for value
types it<br>
> should be totally fine to do something like this:<br>
><br>
> // The given xml tree<br>
> var root = XML.Element(name: "root")<br>
> let item = XML.Element(name: "item")<br>
> root.add(item)<br>
><br>
> // The problematic behavior<br>
> root.add(root)<br>
> If this would be a simple value type without any references
behind the<br>
> scenes you could imagine that the result of the last code line
will<br>
> look like this:<br>
><br>
> <root><br>
> <item/><br>
> <root><br>
> <item/><br>
> </root><br>
> </root><br>
<br>
Yep, that's exactly the right answer for a tree with value
semantics.<br>
The simplest way to implement this tree is to use an Array for the
child<br>
nodes.<br>
<br>
> Basically we copied the whole tree and added it as the second
child<br>
> into the original root element.<br>
><br>
> As for COW optimization this is a problem, just because the
passed<br>
> root is a copy of a struct that contains the exact same
reference as<br>
> the original root element.<br>
<br>
I don't understand why that's a problem.<br>
<br>
> isKnownUniquelyReferenced(&self.reference) will result in
false inside<br>
> the add method.<br>
<br>
...as it should.<br>
<br>
> Is there any chance I could force my program to decrease the
reference<br>
> counter of that last item after I’m sure I don’t need
it?!<br>
<br>
Which last item? When are you sure you don't need it? What result
do<br>
you hope for?<br>
<br>
> A few more details: inside the add method I’m always cloning
the<br>
> passed reference just because graphs aren’t that trivial and
otherwise<br>
> I could possibly end up with a cycle graph, which would be
really<br>
> bad. After that job I’m sure that I don’t need the passed
reference<br>
> anymore and I need a way to escape from it.<br>
><br>
> I’d appreciate any suggestions and help. :)<br>
<br>
It's not clear what you want to acheive nor can I picture the
code<br>
you're using to acheive it, so it's hard to give useful
feedback.<br>
<br>
Sorry,<br>
<br>
--<br>
-Dave<br>
<br>
_______________________________________________<br>
swift-users mailing list<br>
swift-users@swift.org<br>
https://lists.swift.org/mailman/listinfo/swift-users<br></span></div>
</div>
</blockquote>
</div>
<div class="bloop_markdown"></div>
</div></div></span></blockquote></div><div class="bloop_markdown"><p></p></div></body></html>