<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>One note about the cloning:</p>
<pre><code class="xml"><root>
<first>
<second/>
</first>
</root>
</code></pre>
<pre><code class="swift">var root = XML.Element(name: "root")
var first = XML.Element(name: "first")
var second = XML.Element(name: "second")
first.add(second)
root[first][second].add(root) // Lets say we don't clone here anything
</code></pre>
<p>In that scenario we would add <code>root</code> as the first item to <code>second</code>. </p>
<pre><code class="xml"><root>
<first>
<second> <- - - - - - - -+
<root> | That would be the same item (baked with a class)
<first> | and that means that the inner `second` also has
<second/> <- - - -+ a child `root` => cycle graph.
</first> |
</root> |
</second> <- - - - - - - -+
</first>
</root>
</code></pre>
<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_1474357057623046912" 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 20. September 2016 um 09:37:22, 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>True, but how do you traverse back the tree from an inner
node?</p>
<p>Lets look at this simple tree:</p>
<pre><code class="xml"><root>
<first>
<second/>
</first>
</root>
</code></pre>
<pre><code class="swift">let second = /* get the second node */
second.parent // <— How would you implement this with pure value type?
</code></pre>
<p>If parent were only a struct without a reference type behind the
scenes the parent will also contain the current child, where every
child has the parent and so one. The reference type is there as a
layer to achieve this.</p>
<ul>
<li>What kind of a layer does <code>indirect</code> add on
enums?</li>
<li>Can <code>indirect</code> solve the problem here and can it be
added to structs as well?</li>
</ul>
<p>If I’m missing here something, and there might be a true value
type solution for this problem, I’d throw the whole project away
and rebuild it from the beginning. :)</p>
<p>Best regards,</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_1474356453107894784" 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 20. September 2016 um 08:56:20, Dave
Abrahams via swift-evolution (<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a>)
schrieb:</p>
<blockquote type="cite" class="clean_bq">
<div>
<div><span><br>
on Mon Sep 19 2016, Adrian Zubarev
<swift-evolution@swift.org> wrote:<br>
<br>
> I think I just found a solution to my problem:<br>
><br>
> /// - Parameter child: The new `child` to add to the
`children` array.<br>
> public mutating func add(_ child: Element) {<br>
><br>
> let clonedChildReference = Reference(cloning:
child.reference)<br>
> let index = self.reference.children.endIndex<br>
><br>
> self.mutableInsert(clonedChildReference, at: index,
isNotOwnReference: child.reference !== self.reference)<br>
> }<br>
><br>
> /// Warning: Pass only clonded nodes of type Element to this
function!<br>
<br>
I don't understand why any explicit cloning should be needed. An
XML<br>
tree can be modeled perfectly well using arrays of value types,
which<br>
will “clone” themselves as needed to maintain value
semantics.<br>
<br>
> private mutating func mutableInsert(_ node: XML.Node, at
index: Int,<br>
> isNotOwnReference: Bool) {<br>
><br>
> // * If `self.reference` is NOT uniquely referenced and `node`
is a String,<br>
> // we should rebuilt own reference.<br>
> // * If `self.reference` is NOT uniquely referenced and `node`
is a Reference<br>
> // `isNotOwnReference` is true, we should rebuilt own
reference.<br>
> // * If `self.reference` is NOT uniquely referenced and `node`
is a clone<br>
> // reference to `self.reference` where is `isNotOwnReference`
is false, we<br>
> // should check if there are more than **two** strong
references to rebuild<br>
> // own reference, otherwise it's an implementation artifact
and we can keep<br>
> // old reference (any `node` of type Reference is cloned
before it's added<br>
> // to the child array).<br>
> let isNotKnownUniquelyReferenced =
!isKnownUniquelyReferenced(&self.reference)<br>
><br>
> var shouldRebuildReference = false<br>
><br>
> switch node.kind {<br>
><br>
> case .element(_):<br>
> let hasMoreThanTwoStrongReferences =
(CFGetRetainCount(self.reference) - 1) > 2<br>
> shouldRebuildReference = (isNotKnownUniquelyReferenced
&& isNotOwnReference) ||
hasMoreThanTwoStrongReferences<br>
><br>
> case .text(_):<br>
> shouldRebuildReference = isNotKnownUniquelyReferenced<br>
> }<br>
><br>
> if shouldRebuildReference {<br>
><br>
> self.reference = Reference(cloning: self.reference, wholeTree:
true)<br>
> }<br>
><br>
> self.reference.insert(node, at: index)<br>
> }<br>
> I’m using CFGetRetainCount(self.reference) to catch that
implementation artifact.<br>
><br>
> -- <br>
> Adrian Zubarev<br>
> Sent with Airmail<br>
><br>
> Am 19. September 2016 um 09:59:24, Adrian Zubarev
(adrian.zubarev@devandartist.com) schrieb:<br>
><br>
> Hello Dave,<br>
><br>
> thank you for trying to help me. I’ll try to explain the issue
with some more details.<br>
><br>
> First here is some code:<br>
><br>
> extension XML {<br>
><br>
> public struct Element {<br>
><br>
> // public for testing<br>
> public var reference: Reference<br>
><br>
> public var name: String { return self.reference.name }<br>
><br>
> public var children: [Element] {<br>
><br>
> return self.reference.children.flatMap {<br>
><br>
> guard case .element(let element) = $0.kind else { return nil
}<br>
> return Element(wrapping: element)<br>
> }<br>
> }<br>
><br>
> public init(name: String) {<br>
><br>
> self.reference = Reference(name: name)<br>
> }<br>
><br>
> public mutating func add(_ child: Element) {<br>
><br>
> self.mutableInsert(Reference(cloning: child.reference), at:
self.reference.children.endIndex)<br>
> }<br>
><br>
> // Ignore XML.Node, it's a String or Reference<br>
> // Parameter `Node` is assumed to be a clone of a reference
passed to `add` or `insert` method.<br>
> private mutating func mutableInsert(_ node: XML.Node, at
index: Int) {<br>
><br>
> // Clone own reference all way up to the root<br>
> if !isKnownUniquelyReferenced(&self.reference) {<br>
><br>
> self.reference = Reference(cloning: self.reference, wholeTree:
true)<br>
> }<br>
><br>
> // Extract a reference or just insert a string as a
child<br>
> guard case .element(let nodeReference) = node.kind else
{<br>
><br>
> self.reference.insert(node, at: index)<br>
> return<br>
> }<br>
><br>
> // Check for possible debelopment bug<br>
> if nodeReference === self.reference {<br>
><br>
> fatalError("wrong usage of `mutableInsert` function")<br>
> }<br>
><br>
> self.reference.insert(nodeReference, at: index)<br>
> }<br>
><br>
> ...<br>
> }<br>
> }<br>
><br>
> extension XML.Element {<br>
><br>
> // public for testing<br>
> public class Reference : XML.Node {<br>
><br>
> let name: String<br>
><br>
> private(set) weak var parent: Reference?<br>
><br>
> private(set) var children: [XML.Node]<br>
><br>
> var kind: XML.Node.Kind { return .element(self) }<br>
><br>
> ...<br>
> }<br>
> }<br>
> Now lets focus on the problem.<br>
><br>
> 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.<br>
><br>
> Lets look again at the scenario I already described:<br>
><br>
> var root = XML.Element(name: "root")<br>
> var elem = XML.Element(name: "elem")<br>
><br>
> ObjectIdentifier(root.reference) // 0x000060000026ab40<br>
> ObjectIdentifier(elem.reference) // 0x000060800026bb00<br>
><br>
> isKnownUniquelyReferenced(&root.reference) // true<br>
> isKnownUniquelyReferenced(&elem.reference) // true<br>
><br>
> root.add(elem)<br>
><br>
> isKnownUniquelyReferenced(&root.reference) // true<br>
><br>
> root.add(root)<br>
><br>
> // The reference of root has changed even if the second
child<br>
> // was cloned and added as a new object to the
reference.<br>
> // 0x000060000026ab40 <-- was thrown away<br>
> isKnownUniquelyReferenced(&root.reference) // true<br>
><br>
> ObjectIdentifier(root.reference) // 0x000060000026c680 <—
new one<br>
> 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.<br>
><br>
> 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.<br>
><br>
> 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.<br>
><br>
> But I couldn’t find any API for that. :/<br>
><br>
> -- <br>
> Adrian Zubarev<br>
> Sent with Airmail<br>
><br>
> Am 19. September 2016 um 05:50:57, Dave Abrahams via
swift-users (swift-users@swift.org) schrieb:<br>
><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>
> _______________________________________________<br>
> swift-evolution mailing list<br>
> swift-evolution@swift.org<br>
> https://lists.swift.org/mailman/listinfo/swift-evolution<br>
><br>
<br>
--<br>
-Dave<br>
<br>
_______________________________________________<br>
swift-evolution mailing list<br>
swift-evolution@swift.org<br>
https://lists.swift.org/mailman/listinfo/swift-evolution<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>