We currently maintain a stack of indices in nsContentIterator that's not really needed. This is expensive and should be removed.

Sorry, I didn't have a chance to review this not small patch. I'll try to do it tomorrow.

Comment on attachment 8905148 [details] [diff] [review] Remove index cache from nsContentIterator. ># HG changeset patch ># User Catalin Badea <catalin.badea392@gmail.com> > >Bug 1395973 - Remove index cache from nsContentIterator. r=masayuki Please explain why we don't need to cache the index anymore in this commit message before landing. >@@ -263,17 +230,17 @@ nsContentIterator::LastRelease() > > /****************************************************** > * constructor/destructor > ******************************************************/ > > nsContentIterator::nsContentIterator(bool aPre) : > // don't need to explicitly initialize |nsCOMPtr|s, they will automatically > // be nullptr >- mCachedIndex(0), mIsDone(false), mPre(aPre) >+ mIsDone(false), mPre(aPre) > { Could you rewrite this as: nsContentIterator::nsContentIterator(bool aPre) : mIsDone(false) , mPre(aPre) { >@@ -371,25 +336,23 @@ nsContentIterator::InitInternal(nsINode* aStartContainer, uint32_t aStartOffset, > } > > if (startIsData) { > // It's a character data node. > mFirst = aStartContainer->AsContent(); > mLast = mFirst; > mCurNode = mFirst; > >- DebugOnly<nsresult> rv = RebuildIndexStack(); >- NS_WARNING_ASSERTION(NS_SUCCEEDED(rv), "RebuildIndexStack failed"); > return NS_OK; > } > } > > // Find first node in range. > >- nsIContent* cChild = nullptr; >+ nsINode* cChild = nullptr; I don't understand this change especially you changed it to base class of nsIContent. I'd like you to keep this as nsIContent* if this change isn't necessary. > nsINode* >+nsContentIterator::GetDeepFirstChild(nsINode* aRoot) > { > if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) { > return aRoot; > } >+ >+ return GetDeepFirstChild(aRoot->GetFirstChild()); > } Although, not scope of this bug, why we need to call the other GetDeepFirstChild() instead of just using a loop... > nsINode* >+nsContentIterator::GetDeepLastChild(nsINode* aRoot) > { > if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) { > return aRoot; > } >+ >+ return GetDeepLastChild(aRoot->GetLastChild()); > } same... >+nsContentIterator::GetNextSibling(nsINode* aNode) > { > if (NS_WARN_IF(!aNode)) { > return nullptr; > } > >+ if (aNode->GetNextSibling()) { >+ return aNode->GetNextSibling(); >+ } >+ > nsINode* parent = aNode->GetParentNode(); > if (NS_WARN_IF(!parent)) { > return nullptr; > } > >+ return GetNextSibling(parent); > } Similar to above, why do we use this method recursively?? > nsIContent* >+nsContentIterator::GetPrevSibling(nsINode* aNode) > { > if (NS_WARN_IF(!aNode)) { > return nullptr; > } > >+ if (aNode->GetPreviousSibling()) { >+ return aNode->GetPreviousSibling(); >+ } >+ > nsINode* parent = aNode->GetParentNode(); > if (NS_WARN_IF(!parent)) { > return nullptr; > } >+ return GetPrevSibling(parent); > } Same... And you removed empty line immediately before |return| statement, but you didn't do it in nsContentIterator::GetNextSibling(). I'd like you to use same style in those similar methods.

comments addressed. nsContentIterator used to maintain a stack of indices so that when it finished iterating through a subtree it would know the position of the next node. Maintaining this stack is expensive and unnecessary since we have fast getters for next and previous siblings.

(In reply to Masayuki Nakano [:masayuki] (JST, +0900)(offline: 9/13 ~ 9/18) from comment #6) > Comment on attachment 8905148 [details] [diff] [review] > Remove index cache from nsContentIterator. > > > nsINode* > >+nsContentIterator::GetDeepFirstChild(nsINode* aRoot) > > { > > if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) { > > return aRoot; > > } > >+ > >+ return GetDeepFirstChild(aRoot->GetFirstChild()); > > } > > Although, not scope of this bug, why we need to call the other > GetDeepFirstChild() instead of just using a loop... This can rewritten as a loop. > > > nsINode* > >+nsContentIterator::GetDeepLastChild(nsINode* aRoot) > > { > > if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) { > > return aRoot; > > } > >+ > >+ return GetDeepLastChild(aRoot->GetLastChild()); > > } > > same... > > >+nsContentIterator::GetNextSibling(nsINode* aNode) > > { > > if (NS_WARN_IF(!aNode)) { > > return nullptr; > > } > > > >+ if (aNode->GetNextSibling()) { > >+ return aNode->GetNextSibling(); > >+ } > >+ > > nsINode* parent = aNode->GetParentNode(); > > if (NS_WARN_IF(!parent)) { > > return nullptr; > > } > > > >+ return GetNextSibling(parent); > > } > > Similar to above, why do we use this method recursively?? > > > nsIContent* > >+nsContentIterator::GetPrevSibling(nsINode* aNode) > > { > > if (NS_WARN_IF(!aNode)) { > > return nullptr; > > } > > > >+ if (aNode->GetPreviousSibling()) { > >+ return aNode->GetPreviousSibling(); > >+ } > >+ > > nsINode* parent = aNode->GetParentNode(); > > if (NS_WARN_IF(!parent)) { > > return nullptr; > > } > >+ return GetPrevSibling(parent); > > } > > Same... Yes, these methods can definitely be rewritten to use loops instead of recursion, but that should be done in a separate patch. My goal was only to remove the stack of indices and leave everything else the same.

Pushed by catalin.badea392@gmail.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/bc3d643c4973 Remove index cache from nsContentIterator. r=masayuki

Backed out for failing browser-chrome's toolkit/content/tests/browser/browser_bug982298.js and toolkit/modules/tests/browser/browser_Finder_hidden_textarea.js: https://hg.mozilla.org/integration/mozilla-inbound/rev/6c7111ab968fc55accf3a2c6faf498cfd7c997a4 Push with ran failing tests: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=67672b4fecc49740a30cdd2f61412044f134b585&filter-resultStatus=testfailed&filter-resultStatus=busted&filter-resultStatus=exception&filter-resultStatus=retry&filter-resultStatus=usercancel&filter-resultStatus=runnable Failure log browser_bug982298.js: https://treeherder.mozilla.org/logviewer.html#?job_id=131011573&repo=mozilla-inbound [task 2017-09-14T12:15:59.552483Z] 12:15:59 INFO - 1001 INFO TEST-START | toolkit/content/tests/browser/browser_bug982298.js [task 2017-09-14T12:16:00.044353Z] 12:16:00 INFO - TEST-INFO | started process screentopng [task 2017-09-14T12:16:01.987804Z] 12:16:01 INFO - TEST-INFO | screentopng: exit 0 [task 2017-09-14T12:16:01.988383Z] 12:16:01 INFO - Buffered messages logged at 12:15:59 [task 2017-09-14T12:16:01.991320Z] 12:16:01 INFO - 1002 INFO Entering test bound [task 2017-09-14T12:16:01.995892Z] 12:16:01 INFO - 1003 INFO Console message: [JavaScript Error: "The character encoding of the HTML document was not declared. The document will render with garbled text in some browser configurations if the document contains characters from outside the US-ASCII range. The character encoding of the page must be declared in the document or in the transfer protocol." {file: "data:text/html;base64,PHRleHRhcmVhIGlkPSJ0ZXh0YXJlYTEiIHJvdz0yPkZpcmVmb3gKCkZpcmVmb3gKCgoKCgoKCgoKPC90ZXh0YXJlYT48YSBocmVmPSJhYm91dDpibGFuayI+Ymxhbms8L2E+" line: 0}] [task 2017-09-14T12:16:02.001082Z] 12:16:02 INFO - 1004 INFO about to add results listener, open find bar, and send 'F' string [task 2017-09-14T12:16:02.004752Z] 12:16:02 INFO - 1005 INFO added result listener and sent string 'F' [task 2017-09-14T12:16:02.006722Z] 12:16:02 INFO - Buffered messages logged at 12:16:00 [task 2017-09-14T12:16:02.008511Z] 12:16:02 INFO - 1006 INFO got find result [task 2017-09-14T12:16:02.010297Z] 12:16:02 INFO - Buffered messages finished [task 2017-09-14T12:16:02.014646Z] 12:16:02 ERROR - 1007 INFO TEST-UNEXPECTED-FAIL | toolkit/content/tests/browser/browser_bug982298.js | should find string - [task 2017-09-14T12:16:02.023108Z] 12:16:02 INFO - Stack trace: [task 2017-09-14T12:16:02.025535Z] 12:16:02 INFO - chrome://mochitests/content/browser/toolkit/content/tests/browser/browser_bug982298.js:onFindResult:14 [task 2017-09-14T12:16:02.027304Z] 12:16:02 INFO - resource://gre/modules/RemoteFinder.jsm:receiveMessage:92 Failure log browser_Finder_hidden_textarea.js: https://treeherder.mozilla.org/logviewer.html#?job_id=131011571&repo=mozilla-inbound [task 2017-09-14T12:16:05.614334Z] 12:16:05 INFO - 886 INFO TEST-START | toolkit/modules/tests/browser/browser_Finder_hidden_textarea.js [task 2017-09-14T12:16:06.203237Z] 12:16:06 INFO - TEST-INFO | started process screentopng [task 2017-09-14T12:16:07.882628Z] 12:16:07 INFO - TEST-INFO | screentopng: exit 0 [task 2017-09-14T12:16:07.883054Z] 12:16:07 INFO - Buffered messages logged at 12:16:05 [task 2017-09-14T12:16:07.885522Z] 12:16:07 INFO - 887 INFO Entering test bound test_bug1174036 [task 2017-09-14T12:16:07.886734Z] 12:16:07 INFO - Buffered messages logged at 12:16:06 [task 2017-09-14T12:16:07.888093Z] 12:16:07 INFO - 888 INFO Console message: [JavaScript Warning: "Use of nsIFile in content process is deprecated." {file: "resource://gre/modules/FileUtils.jsm" line: 174}] [task 2017-09-14T12:16:07.888664Z] 12:16:07 INFO - 889 INFO TEST-PASS | toolkit/modules/tests/browser/browser_Finder_hidden_textarea.js | find first string - [task 2017-09-14T12:16:07.896517Z] 12:16:07 INFO - Buffered messages finished [task 2017-09-14T12:16:07.898676Z] 12:16:07 ERROR - 890 INFO TEST-UNEXPECTED-FAIL | toolkit/modules/tests/browser/browser_Finder_hidden_textarea.js | find second string - Got 2, expected 0 [task 2017-09-14T12:16:07.901147Z] 12:16:07 INFO - Stack trace: [task 2017-09-14T12:16:07.906199Z] 12:16:07 INFO - chrome://mochikit/content/browser-test.js:test_is:1007 [task 2017-09-14T12:16:07.909057Z] 12:16:07 INFO - c

This test fails because our "find" code will initialize the iterator with an anonymous content node and then nsContentIterator::NextNode(<anonymous node>) will skip nodes by going up the parent chain since <anonymous node>->GetNextSibling() will be null. Existing code gets it right by luck, because it thinks the current cached index is wrong and by trying to recompute it will end up on the first non anonymous child. Is nsContentIterator supposed to be able to go over anonymous nodes? If so, how do you know the order between anonymous nodes and normal nodes?

Hmm, I'm not so familiar with the internal code of nsContentIterator. Smaug, do you have some comments here or do you know who is one of the most familiar people around walking DOM tree?

The code is really old and hasn't changed too much over the years. Can we inject the same behavior what the current code has but without using indexes?

nsContentIterator used to maintain a stack of indices so that when it finished iterating through a subtree it would know the position of the next node. Maintaining this stack is expensive and unnecessary since we have fast getters for next and previous siblings.

Pushed by catalin.badea392@gmail.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/cc51fec33925 Remove index cache from nsContentIterator. r=masayuki

Backout by michael@thelayzells.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/ddbf0b0a03d8 Backed out changeset cc51fec33925 for failing browser-chrome's toolkit/content/tests/browser/browser_bug982298.js with Linux x64 debug and OSX debug. r=backout

Backed out for failing browser-chrome's toolkit/content/tests/browser/browser_bug982298.js with Linux x64 debug and OSX debug: https://hg.mozilla.org/integration/mozilla-inbound/rev/ddbf0b0a03d8a8ff27170c59654f1445bce4437d Push with failures: https://treeherder.mozilla.org/#/jobs?repo=mozilla-inbound&revision=cc51fec33925ca29c0e60a42db9636d76a21dc52&filter-resultStatus=testfailed&filter-resultStatus=busted&filter-resultStatus=exception&filter-resultStatus=retry&filter-resultStatus=usercancel&filter-resultStatus=runnable Failure log: https://treeherder.mozilla.org/logviewer.html#?job_id=134412466&repo=mozilla-inbound [task 2017-10-02T15:36:21.140Z] 15:36:21 INFO - Entering test bound [task 2017-10-02T15:36:21.141Z] 15:36:21 INFO - Buffered messages logged at 15:34:49 [task 2017-10-02T15:36:21.146Z] 15:36:21 INFO - about to add results listener, open find bar, and send 'F' string [task 2017-10-02T15:36:21.147Z] 15:36:21 INFO - Buffered messages logged at 15:34:50 [task 2017-10-02T15:36:21.160Z] 15:36:21 INFO - added result listener and sent string 'F' [task 2017-10-02T15:36:21.164Z] 15:36:21 INFO - Console message: [JavaScript Error: "The character encoding of the HTML document was not declared. The document will render with garbled text in some browser configurations if the document contains characters from outside the US-ASCII range. The character encoding of the page must be declared in the document or in the transfer protocol." {file: "data:text/html;base64,PHRleHRhcmVhIGlkPSJ0ZXh0YXJlYTEiIHJvdz0yPkZpcmVmb3gKCkZpcmVmb3gKCgoKCgoKCgoKPC90ZXh0YXJlYT48YSBocmVmPSJhYm91dDpibGFuayI+Ymxhbms8L2E+" line: 0}] [task 2017-10-02T15:36:21.167Z] 15:36:21 INFO - Buffered messages finished [task 2017-10-02T15:36:21.176Z] 15:36:21 INFO - TEST-UNEXPECTED-FAIL | toolkit/content/tests/browser/browser_bug982298.js | Test timed out - [task 2017-10-02T15:36:21.179Z] 15:36:21 INFO - GECKO(4113) | MEMORY STAT | vsize 2401MB | residentFast 243MB | heapAllocated 97MB [task 2017-10-02T15:36:21.186Z] 15:36:21 INFO - TEST-OK | toolkit/content/tests/browser/browser_bug982298.js | took 90358ms

Hmm, this doesn't fail on my machine.

Pushed by catalin.badea392@gmail.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/1d057e2c36fe Remove index cache from nsContentIterator. r=masayuki