<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>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>
<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_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"><span><div><div></div><div><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></div></div></span></blockquote></div><div class="bloop_markdown"><p></p></div></body></html>