Closed Bug 132824 Opened 22 years ago Closed 16 years ago

Implement NodeIterator object of Traversal API

Categories

(Core :: DOM: Core & HTML, enhancement, P2)

Product:
Core
Component:
DOM: Core & HTML
Type:
enhancement

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: bugmail, Assigned: craig.topper)

References

(
URL
)

Details

(Keywords: dom2)

Attachments

(4 files, 8 obsolete files)

Test case demonstrating weird behavior of TreeWalker when filter removes a node
1.02 KB, text/html
Details
add two webkit extensions needed for their tests
1.94 KB, patch
Details | Diff | Splinter Review
WIP test cases: all of hixie's, some of webkit's
15.66 KB, patch
sicking
: review+
Details | Diff | Splinter Review
Patch that addresses comment #64
38.83 KB, patch
craig.topper
: review+
sicking
: superreview+
Details | Diff | Splinter Review 
From Bugzilla Helper:
User-Agent: Mozilla/5.0 (Macintosh; U; PPC Mac OS X; en-US; rv:0.9.9) Gecko/20020310
BuildID:    2002031005

The Traversal API consists of two key objects; NodeIterator and TreeWalker.
TreeWalker has been implemented, but NodeIterator has not.

NodeIterator should be implemented in Mozilla to complete the API implementation.

Reproducible: Always
Steps to Reproduce:
1. Execute the attached testcase

Actual Results:  "NS_ERROR_NOT_IMPLEMENTED" is generated.

Expected Results:  A NodeIterator object should have been created.

    
  
Keywords: dom2
Status: UNCONFIRMED → NEW
Ever confirmed: true

    
    

    
  
reassiging to kin, dont hate me.
Assignee: anthonyd → kin

    
    

    
  
--> jst
Assignee: kin → jst

    
    

    
  
I'll take this for now, although i won't fix it right this minute.

Note to everybody that is waiting for this though. You could most probably use a
TreeWalker instead. It has all the functionality (and then some) of the
NodeIterator.

The only difference between them is how they behave if the DOM is changed while
you walk/iterate the DOM.

This doesn't mean it's not important though, it's just a workaround while you wait.
Assignee: jst → bugmail

    
    

    
  
Opera 7.60 preview 1 seems to implement the NodeIterator interface

    
    

    
  
I'm starting to transform a clone of nsTreeWalker into nsNodeIterator.

In response to comment 4, I'm personally thinking we should add DOMNodeInserted
and DOMNodeRemoved capturing event listeners to the owner document, and use DOM
3 compareDocumentPosition to determine when we need to change mCurrentNode.  The
detach() call would then remove these event listeners, in addition to any other
cleanup.

sicking: What do you think?

    
    

    
  
On second thought, I'm not sure we'd need a listener for DOMNodeInserted.  We
would need DOMNodeRemoved to check if the removed node is an ancestor of the
reference node.
Assignee: bugmail → traversal-range
QA Contact: lchiang → ian
QA Contact: ian → lchiang
Assignee: traversal-range → bugmail

    
    

    
  
I'd rather not use DOM mutation events since we have better internal
alternatives. nsIDocumentObserver is a better alternative.

Originally I was hoping to be able to use the same mechanism for updating range
endpoints as for updating iterators. I sort of gave up on that idea though since
they behave differently enough that it seemed akward.

Though it might be possible to use one and the same code for detecting that a
node contains a rangeend or iterator. IIRC we keep a flag in a hash for all such
nodes so that we can quickly see if any updates needs to be done.

    
    

    
  
Why do you need any document observers at all, for NodeIterator? The model is
designed so that it is completely stable even in the face of nodes changing
document and everything. I don't understand what you want to be watching for.
QA Contact: lchiang → ian

    
    

    
  
(In reply to comment #9)
> Why do you need any document observers at all, for NodeIterator? The model is
> designed so that it is completely stable even in the face of nodes changing
> document and everything. I don't understand what you want to be watching for.

One of the requirements of the specification is that if the reference node
disappears, we have to set a new reference node.  So if an ancestor of our
reference node is removed from the document, we have to reposition ourselves.

I believe this is the only situation we have to worry about.

sicking: I'm afraid I don't know how to do what you have in mind.  I'll look up
nsIDocumentObserver and our nsIDOMRange code.

    
    

    
  
Oh, right. Forgot about that. So you need to listen to the reference node being
removed from its parent, or any of the ancestors of the reference node, up to
but not including the root node (if the root node is an ancestor of the
reference node, otherwise up to the root of the subtree) being removed from
_their_ parent.

    
    

    
  
(I can't see any way for the reference node to stop being under the root node,
actually, now that I look at it more closely.)

    
    

    
  
Based on IRC conversations, I would suggest that you just need to listen to
element removal mutation events bubbling past the root node. (If you do this
using DOM events instead of some internal thing, then you'd have to make sure
that you don't miss events that are .stopPropagation()ed by author code, and
you'd have to make sure you don't get confused by fake events dispatched by
author code. This basically means, as I understand it, using a special event
group, and making sure the event is a trusted event.)

    
    

    
  


  
Hixie raised the point of trees not being in the document (say, if the root
node or an ancestor was removed from the document), and our iterator having to
deal with that and still be tied to the root node.  If we go the event listener
route, we should attach to the root node of the iterator, not the document
node.

sicking: Do document listeners apply to removed nodes?	Do they apply to nodes
which were created from scratch, but not yet added to the document?

    
    

    
  
I forgot about checking iterator position within nextNode / previousNode, and
about FILTER_SKIP and FILTER_REJECT having the same meaning for NodeIterators.

No new patch right away -- I'd like to hear about how to implement the mutation
handling first.

    
    

    
  
My patch for comment 15 causes crashes through garbage collection & destructors.
 I saw three distinct stacks for crashes:

Stack 1:
gklayout!nsCOMPtr<nsIDOMNode>::~nsCOMPtr<nsIDOMNode>+0x1c
[m:\builds\mozdebug\dist\include\xpcom\nscomptr.h @ 583]
gklayout!nsNodeIterator::~nsNodeIterator+0x27
[m:\mozilla\content\base\src\nsnodeiterator.cpp @ 103]
gklayout!nsNodeIterator::`scalar deleting destructor'+0xf
gklayout!nsNodeIterator::Release+0xcd
[m:\mozilla\content\base\src\nsnodeiterator.cpp @ 117]
xpc3250!XPCJSRuntime::GCCallback+0x6fe
[m:\mozilla\js\src\xpconnect\src\xpcjsruntime.cpp @ 557]
gklayout!DOMGCCallback+0x35 [m:\mozilla\dom\src\base\nsjsenvironment.cpp @ 2032]
js3250!js_GC+0xef4 [m:\mozilla\js\src\jsgc.c @ 1937]
js3250!js_ForceGC+0x53 [m:\mozilla\js\src\jsgc.c @ 1502]
js3250!JS_GC+0x48 [m:\mozilla\js\src\jsapi.c @ 1755]
gklayout!nsJSContext::Notify+0x3a [m:\mozilla\dom\src\base\nsjsenvironment.cpp @
1987]
xpcom_core!nsTimerImpl::Fire+0x243 [m:\mozilla\xpcom\threads\nstimerimpl.cpp @ 398]
xpcom_core!nsTimerManager::FireNextIdleTimer+0x8c
[m:\mozilla\xpcom\threads\nstimerimpl.cpp @ 628]
gkwidget!nsAppShell::Run+0x145 [m:\mozilla\widget\src\windows\nsappshell.cpp @ 142]
appcomps!nsAppStartup::Run+0x1e
[m:\mozilla\xpfe\components\startup\src\nsappstartup.cpp @ 208]
mozilla!main1+0xae8 [m:\mozilla\xpfe\bootstrap\nsapprunner.cpp @ 1272]
mozilla!main+0x174 [m:\mozilla\xpfe\bootstrap\nsapprunner.cpp @ 1763]
mozilla!mainCRTStartup+0x12c [f:\vs70builds\3077\vc\crtbld\crt\src\crtexe.c @ 398]
kernel32!BaseProcessStart+0x23

Stack 2:
gklayout!nsAttrAndChildArray::Clear+0xd9
[m:\mozilla\content\base\src\nsattrandchildarray.cpp @ 622]
gklayout!nsAttrAndChildArray::~nsAttrAndChildArray+0x19
[m:\mozilla\content\base\src\nsattrandchildarray.cpp @ 126]
gklayout!nsGenericElement::~nsGenericElement+0x13d
[m:\mozilla\content\base\src\nsgenericelement.cpp @ 882]
gklayout!nsGenericHTMLElement::~nsGenericHTMLElement+0xf
gklayout!nsHTMLHtmlElement::~nsHTMLHtmlElement+0x22
[m:\mozilla\content\html\content\src\nshtmlhtmlelement.cpp @ 80]
gklayout!nsHTMLHtmlElement::`scalar deleting destructor'+0xf
gklayout!nsGenericElement::Release+0xd6
[m:\mozilla\content\base\src\nsgenericelement.cpp @ 3280]
gklayout!nsHTMLHtmlElement::Release+0xc
[m:\mozilla\content\html\content\src\nshtmlhtmlelement.cpp @ 84]
xpcom_core!ReleaseObjects+0x1c [m:\mozilla\xpcom\ds\nscomarray.cpp @ 149]
xpcom_core!nsVoidArray::EnumerateForwards+0x52
[m:\mozilla\xpcom\ds\nsvoidarray.cpp @ 648]
xpcom_core!nsCOMArray_base::Clear+0x16 [m:\mozilla\xpcom\ds\nscomarray.cpp @ 157]
gklayout!nsCOMArray<nsIContent>::Clear+0x10
[m:\builds\mozdebug\dist\include\xpcom\nscomarray.h @ 211]
gklayout!nsDocument::~nsDocument+0x228
[m:\mozilla\content\base\src\nsdocument.cpp @ 632]
gklayout!nsXMLDocument::~nsXMLDocument+0x136
[m:\mozilla\content\xml\document\src\nsxmldocument.cpp @ 190]
gklayout!nsXMLDocument::`scalar deleting destructor'+0xf
gklayout!nsDocument::Release+0xe8 [m:\mozilla\content\base\src\nsdocument.cpp @ 736]
gklayout!nsXMLDocument::Release+0xc
[m:\mozilla\content\xml\document\src\nsxmldocument.cpp @ 203]
xpc3250!XPCJSRuntime::GCCallback+0x6fe
[m:\mozilla\js\src\xpconnect\src\xpcjsruntime.cpp @ 557]
gklayout!DOMGCCallback+0x35 [m:\mozilla\dom\src\base\nsjsenvironment.cpp @ 2032]
js3250!js_GC+0xef4 [m:\mozilla\js\src\jsgc.c @ 1937]

Stack 3:
gklayout!nsCOMPtr<nsIDocument>::~nsCOMPtr<nsIDocument>+0x1c
[m:\builds\mozdebug\dist\include\xpcom\nscomptr.h @ 583]
gklayout!nsEventStateManager::~nsEventStateManager+0x151
[m:\mozilla\content\events\src\nseventstatemanager.cpp @ 292]
gklayout!nsEventStateManager::`scalar deleting destructor'+0xf
gklayout!nsEventStateManager::Release+0xd3
[m:\mozilla\content\events\src\nseventstatemanager.cpp @ 381]
gklayout!nsPresContext::~nsPresContext+0x88
[m:\mozilla\layout\base\nsprescontext.cpp @ 219]
gklayout!nsPresContext::`scalar deleting destructor'+0xf
gklayout!nsPresContext::Release+0xd0 [m:\mozilla\layout\base\nsprescontext.cpp @
255]
gklayout!nsCOMPtr<nsPresContext>::~nsCOMPtr<nsPresContext>+0x1f
[m:\builds\mozdebug\dist\include\xpcom\nscomptr.h @ 584]
gklayout!nsDOMEvent::~nsDOMEvent+0xf1
[m:\mozilla\content\events\src\nsdomevent.cpp @ 137]
gklayout!nsDOMEvent::`scalar deleting destructor'+0xf
gklayout!nsDOMEvent::Release+0xd3 [m:\mozilla\content\events\src\nsdomevent.cpp
@ 140]
xpc3250!XPCJSRuntime::GCCallback+0x6fe
[m:\mozilla\js\src\xpconnect\src\xpcjsruntime.cpp @ 557]
gklayout!DOMGCCallback+0x35 [m:\mozilla\dom\src\base\nsjsenvironment.cpp @ 2032]
js3250!js_GC+0xef4 [m:\mozilla\js\src\jsgc.c @ 1937]
js3250!js_ForceGC+0x53 [m:\mozilla\js\src\jsgc.c @ 1502]
js3250!JS_GC+0x48 [m:\mozilla\js\src\jsapi.c @ 1755]
gklayout!nsJSContext::Notify+0x3a [m:\mozilla\dom\src\base\nsjsenvironment.cpp @
1987]
xpcom_core!nsTimerImpl::Fire+0x243 [m:\mozilla\xpcom\threads\nstimerimpl.cpp @ 398]
xpcom_core!nsTimerManager::FireNextIdleTimer+0x8c
[m:\mozilla\xpcom\threads\nstimerimpl.cpp @ 628]
gkwidget!nsAppShell::Run+0x145 [m:\mozilla\widget\src\windows\nsappshell.cpp @ 142]


Help wanted in figuring out the cause of these crashes, please.  I consistently
crash, but the stack I get is at random one of these three.

    
    

    
  
I don't think we have any notifications that happen for nodes that are in a
subtree disconnected from the document, so neither mutation-events or
nsIDocumentObserver will help you there. Basically I don't think there is any
way to handle that case currently, I think ranges fail on that too.

I'll try to grab you on irc and lets see if we can find a good solution that'd
work for both ranges and iterators.

I think that rather then duplicating a fair amout of code form the treewalker
it'd probably be better to implement NodeIterator using a treewalker who's
currentNode you update in the face of mutations?

    
    

    
  
Doesn't that mean mutation events are buggy? Is there a bug #?

Also, note that tree walker and node iterator have quite different semantics.
While it may be possible to share code, I wouldn't try too hard to share all of
it, as it were, since you'll probably just get a headache trying to get the
right semantics for both.

    
    

    
  
AFAICT there are only three differences between iterators and treewalkers:

1. They behave differently in the face of tree mutations
2. Iterators ignore the FILTER_REJECT return value and treat it as FILTER_SKIP
3. Iterators only has navigational methods for forward and back in doc order

So if you react to tree changes, the only difference between the two is that
iterators lack a few features.

No, i don't think there's a bug on mutation events not working for out-of-doc nodes.

    
    

    
  
Like I said, quite different. What are the similarities?

    
    

    
  
As long as document.createNodeIterator is not functional could you please 'hide'
it? IMHO a function that just throws an error should not be made available to
scripts, it just prevents the use of the usual JS object detection, e.g.

if (document.createNodeIterator) ni = document.createNodeIterator( ... );


    
    

    
  
That would be better filed as a seperate bug, Seno.Aiko@gmail.com.

    
    

    
  
*** Bug 309866 has been marked as a duplicate of this bug. ***

    
    

    
  
In terms of sharing code, would it be a good idea to create a nsTraversalUtils class which both NodeIterator and TreeWalker inherit from?  The utility functions FirstChildOf, etc. could be consolidated there.

    
    

    
  
The big issue in this bug is not the traversal issue. There are a number of ways that can be solved. It's hard to say which is better but it really doesn't make that big a difference since I suspect any solution will be ok. Personally I suspect that making the iterator wrap a treewalker would be the way to go, but i'll leave that to whoever comes up with a patch.

The big issue in this bug is dealing with mutations. That is the hard part here and the one that requires some thought.

I can see two solutions. Either do something similar to how ranges are implemented by letting elements manually call into the rangecode whenever they are mutated. Or we could use an nsIDocumentObserver.

The latter seems cleaner, but wouldn't be able to deal with subtrees that are not in the document. I recall the WG saying that this might be required for both ranges and iterators, but they never seem to have gotten around to putting that into the errata. See comment 11 and on.

    
    

    
  
To anyone wanting to give this one a try, here is how I would implement it:

First, read up on iterators here:
http://www.w3.org/TR/DOM-Level-2-Traversal-Range/traversal.html
especially the part about how to deal with mutations to the DOM.

Create a new class that contains an nsTreeWalker as a member. Let the treewalker point to the "reference node" of the iterator (see link above). Calls to iterate the nodeiterator forwards and back mostly forwards calls to the treewalker.

To deal with mutations attach an nsIMutationObserver to the given "root" (see link above). This will tell you whenever a node is removed and you can check if that is an ancestor of the current reference node (there's a function in nsContentUtils that's useful for this). If so, adjust the position of the treewalker.

That should mostly be all that's needed. There are some trickyness with regards to keeping track of if the current position is before or after the reference node, and additionally the fact that nodeiterators should treat FILTER_REJECT as FILTER_SKIP.

    
  
Blocks: acid3

    
    

    
  


  
I have created a patch that handles mutations and passes or improves results on Acid3. It passes acid3 test 2, 3, and 4. Test 1 still fails to do an acceptNode exception forwarding problem present in TreeWalker as well.

I moved the common member variables and the TestNode routine from nsTreeWalker into a new nsTraversal class so that NodeIterator could share them. I tried to use the helper routines from nsTreeWalker, but mutations during acceptNode caused problems with that approach.

Key problems that had to be handled:
-If acceptNode accepts a node and removes it from the document it must still be returned by the call to nextNode or previousNode that called acceptNode. The reference node should still be moved according to spec and future traversals should move from there.
-If acceptNode modifies the document and doesn't accept the node the search needs to continue based on the modification made. This requires the mutation observer to be able to modify the working pointer while inside acceptNode.

This code was perhaps overly influenced by the WebKit code for this feature which I had looked at prior to working on this. It didn't start off so similar, but after encountering the problems above it kinda migrated that direction.

    
    

    
  
would be nice to include Mochitests for this at the same time. Converting the tests from http://hixie.ch/tests/adhoc/dom/traversal/node-iterator/ or http://trac.webkit.org/projects/webkit/browser/trunk/LayoutTests/traversal would be a good start. (if you don't know about Mochitest, you can find more information on http://developer.mozilla.org/en/docs/Mochitest)

    
    

    
  
Is there any way you could simply use an nsTreeWalker internally to do all the walking? And just modify it's position as needed when the DOM mutates? That should reduce the size of the implementation significantly I would hope?

    
    

    
  


  
Fixed a small bug in the mutation observer when walking forward the starting index to look for the sibling of the removed node was off by 1.

        Attachment #315053 -
        Attachment is obsolete: true

    
    

    
  
TreeWalker keeps too many pointers live across calls to acceptNode. acceptNode can modify where you go next if it modifies the document and rejects the node so all those pointers can become invalid.

You would need at the very least a new member variable in TreeWalker to keep track of where you are if the mutation observer is triggered while inside of TestNode so that you can modify it when you return. Then if TestNode rejects the node you need to pick up iteration from the modified point. You would still need to keep the existing member variable that is only updated when a node is accepted.

This may indicate bugs in TreeWalker because it remembers other nodes during calls to TestNode.

    
    

    
  


  

        Attachment #315234 -
        Attachment is obsolete: true

    
    

    
  
Do you have a testcase where you think using a treewalker would do the wrong thing? It's entirely possible that treewalker does the wrong thing, but I'm also wondering if there is a defined behavior here for either node iterator or treewalker.

    
    

    
  


  
Here is a test case that demonstrates weird behavior of TreeWalker when the filter removes a node. The spec isn't very clear on what should happen here. 

Current WebKit nightlies do not throw an error on this same test case.

    
    

    
  
So if we really do care about this case (which I'm not convinced that we do that much given the fact that it's undefined by spec, and the spec recommends against NodeFilters doing this) I think we should take care of it by fixing the treewalker code rather than by writing NodeIterators separately.

So I suggest to reuse a treewalker in this bug, and file a separate bug on fixing the treewalker to deal with this situation.

    
    

    
  
What about the FILTER_REJECT differences? I guess we'll have to add a flag to TreeWalker to tell it its being used for a NodeIterator so it can behave correctly? Also the calling sequence of TestNode on the way to previous node are also different. When there are no previous siblings, TreeWalker moves to the parent's sibling and starts descending. It calls TestNode on every node on it way down since any node on the way can reject its children. Iterator filters can't reject children so you don't need to call TestNode before considering children for this case.

    
    

    
  
You could use the same flag and not test as you walk down the chain if it's set.

This difference between NodeIterator and treewalker is really idiotic. It makes it harder for us to reuse code, and removes features for developers :(

Alternatively I guess we could go with your initial patch. If reusing the treewalker adds as much code as not doing it, the whole point sort of goes away...

    
    

    
  


  
The previous patch had a problem with the cycle collector and the mutation observer. The mutation observer was still registered after node iterator was unlinked. Added code to Unlink to unregister it before clearing the root node. I'm not sure if that's the right way to do it, but it seemed to fix the crash I was getting.

Reduced the code a little more. Clear out the working pointer after moving the iterator so that we don't have to mutate it when we are not traversing. Also cleared out the current pointer in Detach to remove the unnecessary reference.

        Attachment #315294 -
        Attachment is obsolete: true

    
  

        Attachment #316943 -
        Flags: review?(jonas)

    
    

    
  


  
I'm working on a test suite for NodeIterator as suggested in comment 29.  In order to bring over the tests that are included in WebKit, I had to add two attributes to nsIDOMNodeIterator - I am assuming these are WebKit extensions, they're not in the DOM 2 Traversal spec.

 readonly attribute nsIDOMNode referenceNode;
 readonly attribute boolean pointerBeforeReferenceNode;

They do what their names imply.  The WebKit tests use them to validate the iterator state.  I think these are useful and reasonable to support, but could be convinced otherwise.

The attached patch implements the additional attributes; it applies *on top* of Craig's most recent patch.

Tangentially, why is mWorkingPointer necessary?  It seems to me that it could be a local variable in the various functions that use it; as far as I can tell, it is never left pointing to anything in between calls to those functions.

    
    

    
  


  
Here's what I've got so far for test cases.  I'm using the Mochitest framework for this.  The patch is independent of both Craig's patch and my additional patch for webkit extensions, but obviously the tests will fail without those patches.

The files test_NodeIterator_basics_filters.xhtml and test_NodeIterator_mutations_1.xhtml are based on Ian Hickson's tests - between them they cover all of that set.  You only need Craig's patch to make those tests work.  However, _basics_filters has six TODOs.  The problem there is: there are four close tags in a row at the end of the file, with carriage returns in between.  As I understand it, the NodeIterator should see three text nodes in a row when it gets to that point, just like it sees text nodes for carriage returns in between start tags.  But they're not there.  I don't know if that's a bug in NodeIterator, a bug in the XHTML parser, or expected behavior.

The third file, test_NodeIterator_mutations_2.html, is based on two of the WebKit tests.  It will fail if you don't have both Craig's patch and my patch for attribute extensions.  I am not going to work on porting over additional WebKit tests until we decide whether or not we want those extensions.

        Attachment #75594 -
        Attachment is obsolete: true

    
    

    
  
mWorkingPointer is there because its used if the document is mutated while inside of TestNode which gives control to user code. This way the mutation handler can change where nextNode or previousNode are working. I don't exactly like it, but I couldn't come up with anything better.

    
    

    
  
Cluttering public interfaces with extensions just to support testing use cases, without public discussion of the extensions, doesn't seem like a good idea.  If the values of the properties affect behavior given further decisions, it seems like you could test those behaviors directly instead.

    
    

    
  
Jeff, please have a look at test_NodeIterator_mutations_2.html (in attachment 319080 [details] [diff] [review]).  I have not been able to think of a way to do what checkseq() does without the webkit extensions, but if you have an idea I'm all ears.

Craig, thanks for the clarification.  I think your way is probably fine given the constraints.

    
    

    
  
Comment on attachment 319080 [details] [diff] [review]
WIP test cases: all of hixie's, some of webkit's

requesting review of these test cases.  shaver (on IRC) is dubious about the value of the webkit extensions, so I'm specifically wanting to know whether you think the hixie tests are adequate, and if not, what more is needed.

        Attachment #319080 -
        Flags: review?(jonas)
Flags: wanted1.9.1?
Priority: -- → P2
Flags: wanted1.9.1? → wanted1.9.1+

    
    

    
  
So why this mWorkingPointer business? Are there really tests that test that? It seems very undefined behavior so I think we should just do the simplest thing. Especially since the code gets a decent amount more complicated.

    
    

    
  
I agree the working pointer mess makes the code complex, but without it Acid3 doesn't pass. It seems that the Acid3 guys made up their own definition of the behavior for a vague area of the spec.

    
    

    
  
Sigh, sucks when ACID tries to specify unspecified behavior. Though it does make some sense to have it behave this way.

So I have realized one big problem with the patch though. During the ContentRemoved callback you are not allowed to call out into javascript. This is because we are not in a consistent state, and so if that javascript is sufficiently evil we can crash.

The best way to fix this is to do the following:

When ContentRemoved is called, move the NodePointers up the parent chain as far as needed to keep them in the context tree. Then register an nsIRunnable with nsContentUtils::AddScriptRunner (this can be the iterator itself). Once the runnable is run you can do the call to moveforward/movebackward.

    
    

    
  
Where does ContentRemoved call out to javascript? I'm not following. moveBackward and moveForward are just routines that walk the tree forwards or backwards. They don't test a node at all.

    
    

    
  
Comment on attachment 316943 [details] [diff] [review]
Updated patch that fixes some bugs

Oooh, I assumed that the spec called for filtered nodes never to become the reference node. Looks safe then :)

        Attachment #316943 -
        Flags: review- → review?(jonas)

        Attachment #184194 -
        Attachment is obsolete: true

    
    

    
  
Comment on attachment 316943 [details] [diff] [review]
Updated patch that fixes some bugs

> nsDocument::CreateNodeIterator(nsIDOMNode *aRoot,
>                                PRUint32 aWhatToShow,
>                                nsIDOMNodeFilter *aFilter,
>                                PRBool aEntityReferenceExpansion,
>                                nsIDOMNodeIterator **_retval)
> {
>-  return NS_ERROR_NOT_IMPLEMENTED;
>+  *_retval = nsnull;
>+
>+  if (!aRoot) {
>+    return NS_ERROR_DOM_NOT_SUPPORTED_ERR;
>+  }
>+
>+  nsresult rv = nsContentUtils::CheckSameOrigin(this, aRoot);
>+  if (NS_FAILED(rv)) {
>+    return rv;
>+  }

Use NS_ENSURE_SUCCESS(rv, rv);

>+  return NS_NewNodeIterator(aRoot, aWhatToShow, aFilter,
>+                            aEntityReferenceExpansion, _retval);

Nit: I would sort of prefer if this simply did |new nsNodeIterator| instead. I know you just copied code (my code even :) ), but we've been trying to move away from unnecessary indirection like this.

>Index: content/base/src/nsNodeIterator.cpp

>+PRBool nsNodeIterator::NodePointer::moveToPrevious(nsINode *aRoot) {
>+
>+    if (!mBeforeNode) {
>+        mBeforeNode = PR_TRUE;
>+        return PR_TRUE;
>+    }
>+
>+    if (mNode == aRoot)
>+        return PR_FALSE;
>+
>+    nsINode *parent = mNode->GetNodeParent();
>+
>+    moveBackward(parent, parent->IndexOf(mNode));

You need to return the result of moveBackward here, no?

>+void nsNodeIterator::NodePointer::adjustAfterRemoval(nsINode* aRoot, nsINode *aContainer, nsIContent *aChild, PRInt32 aIndexInContainer) {
>+
>+    if (!mNode)
>+        return;
>+
>+    if (!nsContentUtils::ContentIsDescendantOf(mNode, aChild))
>+        return;

Combine these two tests. Though, do you really need an mNode nulltest?


>+void nsNodeIterator::NodePointer::moveBackward(nsINode *aParent, PRInt32 aChildNum) {
>+    nsINode *sibling = aParent->GetChildAt(aChildNum-1);
>+    if (sibling) {
>+        nsINode* child;
>+        do {
>+            child = sibling->GetChildAt(sibling->GetChildCount()-1);
>+            if (child)
>+                sibling = child;
>+        } while (child);
>+
>+        mNode = sibling;
>+    } else {
>+        mNode = aParent;
>+    }
>+}

Don't you need to make this guy stop at aRoot too?

    
    

    
  
Ignore the two comments about moveBackward, it always succeeds of course.

    
    

    
  
(In reply to comment #51)
> (From update of attachment 316943 [details] [diff] [review])
> > nsDocument::CreateNodeIterator(nsIDOMNode *aRoot,
> >                                PRUint32 aWhatToShow,
> >                                nsIDOMNodeFilter *aFilter,
> >                                PRBool aEntityReferenceExpansion,
> >                                nsIDOMNodeIterator **_retval)
> > {
> >-  return NS_ERROR_NOT_IMPLEMENTED;
> >+  *_retval = nsnull;
> >+
> >+  if (!aRoot) {
> >+    return NS_ERROR_DOM_NOT_SUPPORTED_ERR;
> >+  }
> >+
> >+  nsresult rv = nsContentUtils::CheckSameOrigin(this, aRoot);
> >+  if (NS_FAILED(rv)) {
> >+    return rv;
> >+  }
> 
> Use NS_ENSURE_SUCCESS(rv, rv);

Ok I can do that.

> 
> >+  return NS_NewNodeIterator(aRoot, aWhatToShow, aFilter,
> >+                            aEntityReferenceExpansion, _retval);
> 
> Nit: I would sort of prefer if this simply did |new nsNodeIterator| instead. I
> know you just copied code (my code even :) ), but we've been trying to move
> away from unnecessary indirection like this.

Should I just move the body of NS_NewNodeIterator here then cause its more than just calling "new nsNodeIterator"

> 
> >Index: content/base/src/nsNodeIterator.cpp
> 
> >+PRBool nsNodeIterator::NodePointer::moveToPrevious(nsINode *aRoot) {
> >+
> >+    if (!mBeforeNode) {
> >+        mBeforeNode = PR_TRUE;
> >+        return PR_TRUE;
> >+    }
> >+
> >+    if (mNode == aRoot)
> >+        return PR_FALSE;
> >+
> >+    nsINode *parent = mNode->GetNodeParent();
> >+
> >+    moveBackward(parent, parent->IndexOf(mNode));
> 
> You need to return the result of moveBackward here, no?
> 
> >+void nsNodeIterator::NodePointer::adjustAfterRemoval(nsINode* aRoot, nsINode *aContainer, nsIContent *aChild, PRInt32 aIndexInContainer) {
> >+
> >+    if (!mNode)
> >+        return;
> >+
> >+    if (!nsContentUtils::ContentIsDescendantOf(mNode, aChild))
> >+        return;
> 
> Combine these two tests. Though, do you really need an mNode nulltest?

mNode is set to null on mWorkingPointer to invalidate it after we finishing iterating. So we only have to mutate it when the mutation happens in TestNode.

> 
> 
> >+void nsNodeIterator::NodePointer::moveBackward(nsINode *aParent, PRInt32 aChildNum) {
> >+    nsINode *sibling = aParent->GetChildAt(aChildNum-1);
> >+    if (sibling) {
> >+        nsINode* child;
> >+        do {
> >+            child = sibling->GetChildAt(sibling->GetChildCount()-1);
> >+            if (child)
> >+                sibling = child;
> >+        } while (child);
> >+
> >+        mNode = sibling;
> >+    } else {
> >+        mNode = aParent;
> >+    }
> >+}
> 
> Don't you need to make this guy stop at aRoot too?
> 

The way the callers are set up, aParent is either mRoot or a descendant of mRoot. The routine can only return aParent or a child of aParent. Thus it can never reach an ancestor of mRoot.

    
    

    
  
Style nits:

> +PRBool nsNodeIterator::NodePointer::moveToNext(nsINode *aRoot) {
> +

Please put the '{' on the next line to follow the style of the rest of the file, and the files around here. Also use UpperCamelCase as that is the prevalent style.

Looks good otherwise. However, I think we should add a couple of perf optimizations. I think there is a definite risk that people will use this API rather than the treewalker when iterating nodes (despite the fact that the treewalker works fine for that), so I think we should try to keep them comparatively fast. So I have two changes in mind:

* Make the NodePointer::mNode weak. There should be no way that ends up as a dangling pointer since mRoot keeps it alive, and we adjust mNode as soon as it's removed from mRoot.

* We should try to avoid calling nsINode::IndexOf a bit more as it can be expensive. To do this you can do the following.

  1. Give NodePointer an PRInt32 mIndexInParent member and an nsINode* mParent
     member. Whenever you set mNode, also set these members.
  2. In NodePointer::adjustAfterRemoval adjust mIndexInParent if aContainer ==
     mParent && aIndexInContainer < mIndexInParent.

This way you can avoid both the GetParent and IndexOf calls.

    
    

    
  
> Should I just move the body of NS_NewNodeIterator here then cause its more than
> just calling "new nsNodeIterator"

Yes, please do.

> > Combine these two tests. Though, do you really need an mNode nulltest?
> 
> mNode is set to null on mWorkingPointer to invalidate it after we finishing
> iterating. So we only have to mutate it when the mutation happens in TestNode.

Ah, though you could move the nulltest to ContentRemoved. That's somewhat ugly too though, so feel free to go either way.


One final thing:
+    class NodePointer {
+    public:
+        NodePointer() {};
+        NodePointer(nsINode *aNode, PRBool aBeforeNode);
+        PRBool moveToNext(nsINode *aRoot);
+        PRBool moveToPrevious(nsINode *aRoot);
+        void adjustAfterRemoval(nsINode *aRoot, nsINode *aContainer, nsIContent *aChild, PRInt32 aIndexInContainer);
+        void clear() { mNode = nsnull; }
+        nsCOMPtr<nsINode> mNode;
+    private:
+        PRBool moveForward(nsINode *aRoot, nsINode *aParent, PRInt32 aChildNum);
+        void moveBackward(nsINode *aParent, PRInt32 aChildNum);
+        PRBool mBeforeNode;
+    };

This declaration is somewhat hard to read. At the very least have an empty line between the members and the functions. I would additionally just make the whole thing public and instead group by functionality. The whole class is private to nsNodeIterator anyway.


Btw, the code looks great!

    
    

    
  


  
This patch addresses most of sicking's comments. It does not cache the parent node of mNode in the NodePointer class. I need to put more thought into how to properly handle mutation for two node pointers in the class. I did cache the index value, this required the addition of a ContentInserted mutation observer in order to handle siblings being inserted before mNode that would cause mNode's index to change.

        Attachment #316943 -
        Attachment is obsolete: true

        Attachment #326242 -
        Flags: review?

        Attachment #316943 -
        Flags: review?(jonas)

    
    

    
  
Catch me on irc to discuss the parent thing. I should be there briefly tomorrow, but most of wednesday.
Assignee: jonas → craig.topper

    
    

    
  
Comment on attachment 326242 [details] [diff] [review]
Patch that addresses most of sickings comments

For some reason some files were missing from the diff

        Attachment #326242 -
        Attachment is obsolete: true

        Attachment #326242 -
        Flags: review?(jonas)

    
    

    
  
Comment on attachment 319080 [details] [diff] [review]
WIP test cases: all of hixie's, some of webkit's

FWIW I do think it would make sense to expose the safari properties. Every implementation should have the data readily available and pages might find it useful.

So IMHO lets expose them and add these tests.

        Attachment #319080 -
        Flags: review?(jonas) → review+

    
    

    
  
Ok.  Probably it makes most sense for Craig to take my patches from here.  I would be willing to translate more of the Webkit test suite into the mochitest framework, but I'd like to understand first why a sequence of end tags separated by carriage returns doesn't produce a sequence of text nodes as seen by NodeIterator (see comment 59, and the TODO items in the "_basics_filters" test)

    
    

    
  
I meant comment 41.  Sorry.

    
    

    
  


  
This patch adds the WebKit extensions Zack's patch. It also stores a pointer to the parent node as Jonas suggested. It seems to work. Acid3 still passes as well as hixie's tests.

I guess in my head I made it out to be harder than it was. Are there any ways to mutate the document that would separate the parent from the node without going through the ContentRemoved observer?

        Attachment #329029 -
        Flags: review?(jonas)

    
    

    
  
Actually, there is. When a node dies it nulls out the parent pointer on all children. But I'm not sure if that's a problem here. Will look for it when I review.

    
    

    
  
Comment on attachment 329029 [details] [diff] [review]
Patch that adds the WebKit extensions and stores the parent node of the reference node as Jonas suggested

>Index: content/base/src/nsContentIterator.cpp

Are the changes to this file related to this bug? If yes, why are they needed?


>Index: content/base/src/nsNodeIterator.h

>+ * The Original Code is this file as it was released on May 1 2001.
>+ *
>+ * The Initial Developer of the Original Code is
>+ * Jonas Sicking.

This isn't true, you are the initial developer, and you wrote this way later than that date :)

>+    struct NodePointer {
>+        NodePointer() {};

You need to initialize mNode to nsnull here to properly deal with a DOM mutation happening before mWorkingPointer is ever used.

>+        nsINode *mNode;
>+        nsINode *mNodeParent;
>+        PRBool mBeforeNode;
>+        PRInt32 mIndexInParent;

Please document that mNodeParent can be a dangling pointer in the case when mNode is null or points to mRoot.

r=me with those things fixed and assuming the ContentIterator changes aren't really supposed to go in.

        Attachment #329029 -
        Flags: superreview+

        Attachment #329029 -
        Flags: review?(jonas)

        Attachment #329029 -
        Flags: review+

    
    

    
  
Also, it'd be great if you could add a testcase that would have caught the problem of not initializing mNode to nsnull up front. I.e. do some mutations after initializing the node iterator, but before it has been used.

    
    

    
  


  

        Attachment #329029 -
        Attachment is obsolete: true

        Attachment #330434 -
        Flags: superreview?(jonas)

        Attachment #330434 -
        Flags: review+

    
    

    
  
(In reply to comment #64)
> (From update of attachment 329029 [details] [diff] [review])
> >Index: content/base/src/nsContentIterator.cpp
> 
> Are the changes to this file related to this bug? If yes, why are they needed?
> 

Those changes were included by accident.

> 
> >Index: content/base/src/nsNodeIterator.h
> 
> >+ * The Original Code is this file as it was released on May 1 2001.
> >+ *
> >+ * The Initial Developer of the Original Code is
> >+ * Jonas Sicking.
> 
> This isn't true, you are the initial developer, and you wrote this way later
> than that date :)
> 

Fixed

> >+    struct NodePointer {
> >+        NodePointer() {};
> 
> You need to initialize mNode to nsnull here to properly deal with a DOM
> mutation happening before mWorkingPointer is ever used.
> 

The missing initialization is left over from when mNode was an nsCOMPtr.

> >+        nsINode *mNode;
> >+        nsINode *mNodeParent;
> >+        PRBool mBeforeNode;
> >+        PRInt32 mIndexInParent;
> 
> Please document that mNodeParent can be a dangling pointer in the case when
> mNode is null or points to mRoot.

Done.

> 
> r=me with those things fixed and assuming the ContentIterator changes aren't
> really supposed to go in.
> 

ContentIterator changes have been been removed from the patch.

        Attachment #330434 -
        Flags: superreview?(jonas) → superreview+

    
    

    
  
Is test 1 of Acid3 supposed to be failing still with these patches checked in?

    
    

    
  
The bug isn't resolved yet.

Test 01 failed: method [object NodeIterator].nextNode() didn't forward exception

    
    

    
  
This bug is fixed, the NodeIterator API has been implemented. Please file separate bugs for bugs in the implementation.

(the reason it's still left open is that we usually leave the honor of closing the bug up to the spec writer)

    
    

    
  
The bug referenced in comment #70 exists in the treewalker interface too.

    
    

    
  
Could someone please file a bug and attach a testcase and cc me. Should be easy enough to fix. Possibly it's as simple as the return value getting lost somewhere along the way.

    
    

    
  
what are we going to do now? A single bug 4 nodeiterator and treewalker bug?

    
  
Depends on: 446584

    
    

    
  
Fixed now?

    
    

    
  
Yes, this was fixed long time ago
Status: NEW → RESOLVED
Closed: 16 years ago
Resolution: --- → FIXED

    
    

    
  
It's not obvious to me (since I'm not intimate with DOM like you guys are) what referenceNode and pointerBeforeReferenceNode do.

I'm guessing that referenceNode lets you look at the current node without advancing the iterator, but I don't even have a guess what pointerBeforeReferenceNode does.  I looked at the code, but that doesn't make it any more obvious to me. :)

I'd appreciate some info so I can wrap up the docs for this.  Thanks!

    
    

    
  
It's somewhat obvious if you look at the spec. An iterator is always anchored to a node. This is the node it stays next to when nodes around it are inserted.

That node is what referenceNode is. pointerBeforeReferenceNode indicates if the iterator is placed before or after that node.

    
    

    
  
Comment on attachment 330434 [details] [diff] [review]
Patch that addresses comment #64

> NS_IMETHODIMP
> nsDocument::CreateTreeWalker(nsIDOMNode *aRoot,
>                              PRUint32 aWhatToShow,
>                              nsIDOMNodeFilter *aFilter,
>                              PRBool aEntityReferenceExpansion,
>                              nsIDOMTreeWalker **_retval)
> {
>   *_retval = nsnull;

>+  NS_ENSURE_ARG_POINTER(_retval);

Heh.
Component: DOM: Traversal-Range → DOM: Core & HTML

          You need to log in
          before you can comment on or make changes to this bug.
        






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: