[webkit-dev] DOM tree traversal on detached nodes

[Geoffrey Garen]

>> IMHO, (a) would be the best semantics.
> 
> I agree, and I think that the specification actually does require this.
> 
> The real issue here is how to fix this bug efficiently. I believe that Geoff Garen has been contemplating this and also has a proposal for how to do it.

I believe you could achieve (a) (i.e., preserve all reachable nodes without help from the JavaScript garbage collector) with these semantics in the C++ DOM:

===== Design =====

ref():

	++this->refCount
	++root()->refCount

deref():

	--this->refCount
	--root()->refCount

	if !root()->refCount:
		assert(!this->refCount)
		for each descendent of root():
			delete descendent
		delete root()

Remove 'this' from tree:

	assert(this->refCount) // clients must put a node into a RefPtr to remove it from a tree

	root()->refCount -= this->refCount

	for each descendent of this:
		this->refCount += descendent->refCount

Insert 'this' into tree:

	root()->refCount += this->refCount

	for each descendent of this:
		this->refCount -= descendent->refCount

What is "root()"?:

	If this is in a document:
		root() == document()

	else:
		root() == the highest link in the parentNode chain


===== FAQ =====

Cycles?

	No cycles are possible because the DOM API does not allow cycles in a DOM tree.

Is O(n) subtree insertion and removal OK?

	I believe these operations are already O(n).

Is average case O(log n) access to disconnected root() OK?

	If n is small and/or ref/deref of disconnected subnodes are rare, then yes.

	Otherwise, we can optimize this case by putting a direct pointer to root() in rare data.

Geoff

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20120611/e9c8b7b0/attachment.html>