401291 - optimize handling of dynamic changes for advanced CSS selectors

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

This is taken from bug 73586 comment 22:

We should set bits on nsINode (which means we need to mark some more nsINode
flags an not reserved for implementations) that mean:
 1. element has an :empty or :-moz-only-whitespace selector
 2. arbitrary operations on children of the element (including append) require
a reresolve on the element
 3. append requires a reresolve on the element's last child; other operations
on children of the element require a reresolve of the element
 4. append requires no changes, but other operations on children of the element
require a reresolve of the element

I'm not sure if we really need the distinction between (3) and (4).  We need
(1) separate because of the pile of :-moz-only-whitespace rules in quirk.css --
this would be much easier if we moved that margin collapsing quirk into C++.

SelectorMatches and SelectorMatchesTree would then set these bits *any* time
they tried to match one of the problematic selectors (match or no).  This will
guarantee that we'll always have them set if the change might matter.  We
should move the problematic selectors to the end of SelectorMatches so they get
set less often (from least to most problematic).


This will fix a number of existing bugs in dynamic change handling and allow us to implement some additional selectors easily.

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: work in progress

I just typed this out.  I think it's roughly what's necessary to fix this.  I haven't had a chance to compile this, and I have to head out now, so I'll do that tomorrow (or much later tonight).

(Fixing this seems like the easiest way to fix bug 404418, which is blocking1.9+; it's also a good thing to do, and not all that risky - the main risk is to performance, but I think this approach should be fine.)

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

This compiles and works on cursory testing.  Need to do a bit more testing (including of performance characteristics) and write regression tests.

I realized after looking at attachment 127688 [details] in bug 98997 that I also need to handle CharacterDataChanged; that shouldn't be hard to add, but I won't get to it tonight.

I took out the PR_STATIC_ASSERTs I wanted to add because I didn't want to deal with including prlog.h in header files (the lack of which was one of the things that caused the previous patch not to compile), fixing up all the FORCE_PR_LOGs in the tree to be before *any* includes, potentially dealing with un-forcing any PR_LOGs that occur in header files, etc.  I need to file one bug for those changes and another for dealing with the PR_LOG mess.

Comment 3

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

OK, this adds the CharacterDataChanged handling too.

I'm not sure if we use CharacterDataChanged during document loading, but we could in the future even if we don't now, so I did optimize the append case (which wasn't hard to do).  I restructured the insert/remove handling to use a child pointer instead of index so that I wouldn't need to call IndexOf for the CharacterDataChanged case.

Comment 4

[Jeff Walden [:Waldo]]

acid3 includes tests for (at least) the following not-fun selectors:

  :first-child
  :last-child
  :only-child
  :empty (including awesomeness like contains-empty-textnode or contains-comment)
  :nth-child(odd/even)
  :nth-child(-n+3)
  :first-of-type
  :last-of-type
  :only-of-type
  :nth-of-type(3n+1)
  :nth-of-type(3n-1)
  :nth-last-of-type(2n)
  :nth-last-of-type(-5n+3)

These are tests 35-40, and 42 covers dynamic changes with ~/+/>/descendant.  It's probably worth double-checking behaviors against it to make sure they're correct (load and wait for finish, then shift-click on the "A" of "Acid3"); at a skim nothing looked wrong, but I only skimmed.  Probably also a good idea to anticipate the necessary changes for the :nth-* selectors, which I seem to remember Gecko doesn't (yet, given acid3) support at all.

Comment 5

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

This is designed to handle dynamic changes for the :nth-* and :*-of-type selectors (although it doesn't have a particularly great optimization path for the latter -- it just treats them like everything needs to be restyled, except for optimizing the append case for :first-of-type).

Comment 6

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch

Now with tests (for the three main dependency bugs).

The tests caught a pretty bad mistake I made.  I'd thought ContentRemoved notifications happened before the removal (but they really happen after).  Though now that I'm reminded, I'm glad we don't try to do frame reconstruction on the tree we're "going to have" shortly.

Comment 7

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 302496 [details] [diff] [review]
patch

>+++ b/content/base/public/nsINode.h

>-  NODE_TYPE_SPECIFIC_BITS_OFFSET =
>-    NODE_SCRIPT_TYPE_OFFSET + NODE_SCRIPT_TYPE_SIZE
>+  NODE_TYPE_SPECIFIC_BITS_OFFSET = 20

I'd rather we just put the new flags before the script type stuff, incremented NODE_SCRIPT_TYPE_OFFSET, and left this line as is.

>+++ b/layout/base/nsCSSFrameConstructor.cpp
>@@ -8906,6 +8908,8 @@ nsCSSFrameConstructor::ContentInserted(n
>@@ -9476,6 +9480,8 @@ nsCSSFrameConstructor::ContentRemoved(ns

I guess it's not really worth optimizing for the case when the ContentInserted/ContentRemoved doesn't correspond to an actual DOM operation but to a reframing operation?  We'd just finished getting rid of those booleans...

Maybe we should push this code into the presshell instead, to make sure that we only hit it on real content changes?  That can be a separate patch if you just want to get this in as-is.

>@@ -9900,6 +9906,19 @@ nsCSSFrameConstructor::CharacterDataChan
>+  PRUint32 selectorFlags =
>+    container ? (container->GetFlags() & NODE_ALL_SELECTOR_FLAGS) : 0;

I can't think of a sane way for |container| to be null here.  I guess we can leave the null-check just in case, but add an assert?

>+nsCSSFrameConstructor::RestyleForAppend(nsIContent* aContainer,
>+  PRUint32 selectorFlags = aContainer ?
>+    (aContainer->GetFlags() & (NODE_ALL_SELECTOR_FLAGS &

Again, I don't thin aContainer can be null here.

>+  if (selectorFlags != 0) {

Flip this around and make it an early return?

>+      PostRestyleEvent(aContainer, eReStyle_Self, NS_STYLE_HINT_NONE);

I'd be kind of tempted to return after this call and outdent the else too, but either way.

>+        // see if we need to restyle the container

s/if/whether/

>+        for (PRInt32 index = 0; index < aNewIndexInContainer; ++index) {
>+          if (nsStyleUtil::IsSignificantChild(aContainer->GetChildAt(index),
>+                                              PR_TRUE, PR_FALSE)) {

This could use a comment about why PR_FALSE is the right thing to pass as that first arg.  As far as I can tell, if some child _is_ actually significant but we decide it's not that's just a performance issue, whereas the other way around would be a correctness issue.  So we go with the value that will detect the fewest things as significant so that we're sure to have correct behavior.  We can't tell the "right" value because we don't know which of the two selectors was involved.

If any of the above is wrong, _definitely_ document what the right reasoning is!  ;)

>+        for (PRInt32 index = aNewIndexInContainer - 1; index >= 0; --index) {

This could blow up badly if there are lots of text nodes and no elements, but I don't see a good way to address that.  :(

>+nsCSSFrameConstructor::RestyleForInsertOrChange(nsIContent* aContainer,
>+  PRUint32 selectorFlags =
>+    aContainer ? (aContainer->GetFlags() & NODE_ALL_SELECTOR_FLAGS) : 0;

The only way aContainer can be null here is if this is an insertion of a node into the DOM with the Document node as the parent.  That case can't lead to any style changes, I don't think.  So I'd rather put this null-check in the ContentInserted and not bother calling this method if aContainer is null.

>+  if (selectorFlags != 0) {

Again, I'd reverse that test and early-return.

>+        // see if we need to restyle the container

s/if/whether/

>+          if (nsStyleUtil::IsSignificantChild(child, PR_TRUE, PR_FALSE)) {

Perhaps point here to the other comment I asked you to write?

The two for loops here violate the portability guideline about scoping; I guess MSVC has fixed that by now?

>+nsCSSFrameConstructor::RestyleForRemove(nsIContent* aContainer,
>+  PRUint32 selectorFlags =
>+    aContainer ? (aContainer->GetFlags() & NODE_ALL_SELECTOR_FLAGS) : 0;

Again, the aContainer check could just as easily be in the caller.

>+  if (selectorFlags != 0) {

Early return.

>+        // see if we need to restyle the container

s/if/whether/

It sort of feels like we could still combine these if we tried hard enough, but I suspect it would complicate the code too much (need random -1 on the index in some cases but no others, etc)...  :(

>+++ b/layout/style/test/test_bug229915.html

Can you toss some tests for ~ in here as well?

>+++ b/layout/style/test/test_bug73586.html

And some -moz-first-node/last-node here?

>+++ b/layout/style/test/test_bug98997.html

And some :-moz-only-whitespace tests here?

With those nits, looks great.

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

(In reply to comment #7)
> I'd rather we just put the new flags before the script type stuff, incremented
> NODE_SCRIPT_TYPE_OFFSET, and left this line as is.

Done.

> I guess it's not really worth optimizing for the case when the
> ContentInserted/ContentRemoved doesn't correspond to an actual DOM operation
> but to a reframing operation?  We'd just finished getting rid of those
> booleans...
> 
> Maybe we should push this code into the presshell instead, to make sure that we
> only hit it on real content changes?  That can be a separate patch if you just
> want to get this in as-is.

Oh, good point.  I'll do that now.

> >@@ -9900,6 +9906,19 @@ nsCSSFrameConstructor::CharacterDataChan
> I can't think of a sane way for |container| to be null here.  I guess we can
> leave the null-check just in case, but add an assert?

Text nodes can be children of the document.

> >+nsCSSFrameConstructor::RestyleForAppend(nsIContent* aContainer,
> Again, I don't thin aContainer can be null here.

Right.  Changed to assertion.

> >+  if (selectorFlags != 0) {
> Flip this around and make it an early return?
[multiple times]

Yeah -- originally I had some of this code not as a separate function, and then it made sense that way.

> >+      PostRestyleEvent(aContainer, eReStyle_Self, NS_STYLE_HINT_NONE);
> 
> I'd be kind of tempted to return after this call and outdent the else too, but
> either way.

Done (all 6 times we restyle the container).

> >+        // see if we need to restyle the container
> 
> s/if/whether/

Done, multiple times (although I think it's ok as it was).

> >+        for (PRInt32 index = 0; index < aNewIndexInContainer; ++index) {
> >+          if (nsStyleUtil::IsSignificantChild(aContainer->GetChildAt(index),
> >+                                              PR_TRUE, PR_FALSE)) {
> 
> This could use a comment about why PR_FALSE is the right thing to pass as that
> first arg.  As far as I can tell, if some child _is_ actually significant but
> we decide it's not that's just a performance issue, whereas the other way
> around would be a correctness issue.  So we go with the value that will detect
> the fewest things as significant so that we're sure to have correct behavior. 
> We can't tell the "right" value because we don't know which of the two
> selectors was involved.

Right.  But actually you made me realize that the extra check I'd stuck in in RestyleForRemove had the last parameter wrong.  To avoid confusing myself further (I already confused myself a bunch of times over exactly this), I just removed it, since it's a probably-mostly-irrelevant optimization.

> The two for loops here violate the portability guideline about scoping; I guess
> MSVC has fixed that by now?

Yes, that's been ok since we raised the requirement to MSVC 7.1.

> Again, the aContainer check could just as easily be in the caller.

Done (in all cases).

> It sort of feels like we could still combine these if we tried hard enough, but
> I suspect it would complicate the code too much (need random -1 on the index in
> some cases but no others, etc)...  :(

They'd combine perfectly if we got ContentRemoved before the removal, but that would create other problems.

Still need to add the tests; then I'll post a new patch.

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch for landing

Comment 10

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Also hit some unexpected passes for the following in layout/reftests/bugs/:

315920-4.html
315920-14.html
352980-1f.html
352980-1h.html

315920-5.html was also expected to pass, but it's not, nor does it look to me like it ought to.

Comment 11

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Fix checked in to trunk, 2008-02-18 22:17 -0800.

Comment 12

[Jonas Sicking (:sicking) No longer reading bugmail consistently]

> > >@@ -9900,6 +9906,19 @@ nsCSSFrameConstructor::CharacterDataChan
> > I can't think of a sane way for |container| to be null here.  I guess we can
> > leave the null-check just in case, but add an assert?
> 
> Text nodes can be children of the document.

Nope, they can not. We even enforce this through DOM mutations:
http://lxr.mozilla.org/mozilla/source/content/base/src/nsGenericElement.cpp#2961