Refactor nsContentIterator: remove index cache and slightly better integration with nsRange

RESOLVED FIXED in Firefox 60

Status

()

enhancement
P2
normal
RESOLVED FIXED
2 years ago
3 months ago

People

(Reporter: catalinb, Assigned: catalinb)

Tracking

unspecified
mozilla60
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(firefox60 fixed)

Details

Attachments

(1 attachment, 5 obsolete attachments)

Assignee

Description

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

Updated

2 years ago
Attachment #8903619 - Attachment is obsolete: true
Assignee

Comment 4

2 years ago
Attachment #8905148 - Flags: review?(masayuki)
Assignee

Updated

2 years ago
Attachment #8905137 - Attachment is obsolete: true
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.
Attachment #8905148 - Flags: review?(masayuki) → review+
Assignee

Comment 7

2 years ago
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.
Assignee

Updated

2 years ago
Attachment #8905148 - Attachment is obsolete: true
Assignee

Comment 9

2 years ago
(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.

Comment 10

2 years ago
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
Flags: needinfo?(catalin.badea392)
Assignee

Comment 12

2 years ago
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?
Flags: needinfo?(catalin.badea392) → needinfo?(masayuki)
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?
Flags: needinfo?(masayuki) → needinfo?(bugs)
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?
Flags: needinfo?(bugs)
Assignee

Updated

2 years ago
See Also: → 1404916
Assignee

Comment 15

2 years ago
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.
Assignee

Updated

2 years ago
Attachment #8903618 - Attachment is obsolete: true
Attachment #8905861 - Attachment is obsolete: true

Comment 16

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

Comment 17

2 years ago
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
Flags: needinfo?(catalin.badea392)
Assignee

Comment 19

2 years ago
Hmm, this doesn't fail on my machine.
Flags: needinfo?(catalin.badea392)
Priority: -- → P2

Comment 21

Last year
Pushed by catalin.badea392@gmail.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/1d057e2c36fe
Remove index cache from nsContentIterator. r=masayuki
https://hg.mozilla.org/mozilla-central/rev/1d057e2c36fe
Status: NEW → RESOLVED
Closed: Last year
Resolution: --- → FIXED
Target Milestone: --- → mozilla60
Component: DOM → DOM: Core & HTML
You need to log in before you can comment on or make changes to this bug.