167351 - Identical z-indexed elements not sorted in document order.

Status: RESOLVED FIXED

(Core :: Layout, defect, P2)

Description

[David Hyatt]

If you have two positioned blocks with identical z-indices, but one of them is
nested inside another block with no specified z-index (i.e., auto), then you end
up with the blocks being incorrectly sorted.

Testcase coming momentarily.

Comment 1

[David Hyatt]

The URL field now shows the bug.

Unfortunately when you fix this bug, a real-world Web site's DHTML menus are
actually going to break (they're actually exploiting this bug in Gecko right now). 

Comment 2

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

This is unlikely to be a bug anymore in the next release of CSS2.1.

Any idea what the real-world site is?  The URL would be useful evidence...

Comment 3

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Strange. When I first saw the bug I thought it was going to be one of the
deficiencies that I already know about, but actually we should be doing this
test case correctly.

dbaron: so CSS2.1 will let the user agent break z-index ties arbitrarily, as I
suggested?

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

OK, this problem is a regression caused by kmcclusk's topmost hack. Although
it's probably my fault because I talked him into using simpler code which
doesn't work for this case :-).

Comment 5

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

Actually, I'm probably wrong about CSS2.1.

Comment 6

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: fix

this patch fixes the bug by moving the topmost logic into the display list
sorting algorithm. It also fixes the view tree ordering so that it matches
document order rather than z-index order, which is required so that document
order is preserved for later use by the display list sorter.

Comment 7

[Brendan Eich [:brendan]]

Comment on attachment 98346 [details] [diff] [review]
fix

>Index: view/src/nsViewManager.cpp
>===================================================================
>RCS file: /cvsroot/mozilla/view/src/nsViewManager.cpp,v
>retrieving revision 3.257
>diff -u -r3.257 nsViewManager.cpp
>--- view/src/nsViewManager.cpp	3 Sep 2002 21:51:12 -0000	3.257
>+++ view/src/nsViewManager.cpp	8 Sep 2002 20:29:17 -0000
>@@ -108,7 +108,7 @@
>   nsRect        mBounds;      // coordinates relative to the view manager root
>   nscoord       mAbsX, mAbsY; // coordinates relative to the view that we're Refreshing 
>   PRUint32      mFlags;       // see above
>-  PRInt32       mZIndex;      // temporary used during z=index processing (see below)
>+  PRInt64       mZIndex;      // temporary used during z=index processing (see below)

Humongous!  Necessary?

> };
> 
> /*
>@@ -881,6 +881,10 @@
>   }
> }
> 
>+static PRInt64 BuildExtendedZIndex(nsView* aView) {
>+  return ((PRInt64)aView->GetZIndex() << 1) | (aView->IsTopMost() ? 1 : 0);
>+}

D'oh!  Need to use prlong.h macros, or better, nsLong.h inline operators here,
to be XP (I believe we still have platforms without long long support).

/be

Comment 8

[Boris Zbarsky [:bzbarsky]]

Could we do something like

struct {
  PRInt32 mZIndex;
  PRBool mOnTop;
} mZIndex;

?  We'd probably need to define operator < and such on it, but...  (granted,
that seems like a gratuitous reimplementation of the PRInt64 stuff...)

Oh, and doing << 1 on the z-index seems like a bad idea for negative z-indices
(which are perfectly legal).

Comment 9

[Brendan Eich [:brendan]]

bz: what's wrong with << on a negative number to set the low order bit (or not)
as a special tag?

/be

Comment 10

[Boris Zbarsky [:bzbarsky]]

Well.. This patch, as far as I can see, relies on the identity:

((PRInt64)foo << 1 | 1)  > ((PRInt64)foo << 1 | 0)

This identity is not true for negative numbers in the typical 2's complement
notation.  In particular, for foo == -1, we have:

(PRInt64)foo << 1 | 1 == (PRInt64)-1
(PRInt64)foo << 1 | 0 == (PRInt64)-2

Comment 11

[Brendan Eich [:brendan]]

I shoulda read the patch.  Yes, if relational operators are used, you have to
clear the tag bit, or something.  Yuck.

/be

Comment 12

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Um, guys, -1 IS greater than -2.

Comment 13

[Robert O'Callahan (:roc) (email my personal email if necessary)]

> Humongous!  Necessary?

It simplifies the logic and is intuitively compelling. The best way to think
about IsTopMost is that it is an extra low-order bit of precision on the z-index.

I'll switch to macros and attach the new patch.

Comment 14

[Robert O'Callahan (:roc) (email my personal email if necessary)]

BTW those DisplayListElement2 structures are very short-lived so their size
doesn't matter much.

Comment 15

[Boris Zbarsky [:bzbarsky]]

OK, tendering two apologies.  Mine for being an idiot (my other concern was
about the sign bit being shifted off into oblivion, but the upcast to PRInt64
makes that work out ok), and Brendan's (at his request) for not standing up for
himself and the patch.

Comment 16

[Robert O'Callahan (:roc) (email my personal email if necessary)]

:-) Apology accepted. We all have days like that.

I am sort of curious why this humble bug merits the attention of hyatt and
brendan...

Comment 17

[Brendan Eich [:brendan]]

roc, I just wanna keep systems without long long working.  Also, I bit-tag quite
a bit, so I was curious about bz's claim.  Too bad I folded without reading his
reply carefully (lack of lunch, what can I say?).

/be

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: better patch

as promised

Comment 19

[Brendan Eich [:brendan]]

Comment on attachment 98372 [details] [diff] [review]
better patch

I meant nsInt64 (xpcom/ds/nsInt64.h), not nsLong -- alas, that old C++ sugar
class doesn't implement shift-ops.  But it sure would make for prettier code
here, if it were fixed to include the shift ops, and used here instead of naked
PRInt64/LL_*.  My 2 cents.

/be

Comment 20

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: sugary patch

Mmmm, sugar.

Actually, wrapping a scalar in a class like this introduces overhead in many
compilers. But I don't care.

If we're going to play the C++ overloading game, why don't we just overload the
operators on PRInt64 on those platforms that don't have a native 64bit type?
But I still don't care :-).

Comment 21

[David Hyatt]

Hey, all I did was discover it. :)

Comment 22

[Kevin McCluskey (gone)]

attachment (id=98377) causes the two bugs the topmost hack was created for to
regress.
http://bugzilla.mozilla.org/show_bug.cgi?id=137853
http://bugzilla.mozilla.org/show_bug.cgi?id=77607

The problem is the patch does not take into account the topmost flag when
ordering the child list in nsViewManager::InsertChild. 

Comment 23

[Kevin McCluskey (gone)]

When views are zindex:auto the stable Z sort will leave them alone. It assumes
they are in the correct document order. So the topmost flag has no effect. The
topmost flag is really only needed to order views when the views are
z-index:auto. It is not needed when an explicit z-index is set.  So we need to
change the position of the view within it's parents list based on the topmost
flag when the view is inserted.  

Comment 24

[Kevin McCluskey (gone)]

Using the comparision logic from attachment
http://bugzilla.mozilla.org/attachment.cgi?id=88674&action=view in bug 137853
fixes this bug.

Comment 25

[Kevin McCluskey (gone)]

Attachment: Patch which fixes this bug by changing the logic in CompareZIndex

Comment 26

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: testcase which cannot be solved by reordering child views

Check out this testcase. I don't think any method for handling topmost which
relies on reordering the children of a view can handle this testcase.

All 3 divs get views. You must put the view for div "a" either before or after
the view for div "b" in the sibling list. If you put it before the view for div
"b", then it will appear under "b", which is wrong. If you put it after the
view for div "b", then it will appear on top of "c", which is wrong. (The
latter is what we currently do.)

Comment 27

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: fixed patch

Here's my next attempt. This patch fixes the problems in my earlier patch by
making topmost apply to z-index:auto views in the z-index sorter. It works on
the testcases in the old topmost bug (I did check it earlier, but I guess I
missed some testcases --- sorry). It works with the testcase above.

Apart from working on all the testcases, I do prefer to have the z-index logic
confined to the z-index sorter as much as possible. It seems simpler and more
robust in the face of dynamic changes to z-index.

Comment 28

[Brendan Eich [:brendan]]

Comment on attachment 98377 [details] [diff] [review]
sugary patch

r/sr=[e-mail] on the xpcom/ds/nsInt64.h part of this patch only.

/be

Comment 29

[Kevin McCluskey (gone)]

Comment on attachment 98542 [details] [diff] [review]
fixed patch

r=[e-mail]

Looks good. I agree, this patch is cleaner then my previous solution.

Comment 30

[kinmoz]

Comment on attachment 98542 [details] [diff] [review]
fixed patch

sr=[e-mail]

Comment 31

[Brendan Eich [:brendan]]

Comment on attachment 98542 [details] [diff] [review]
fixed patch

>+  for (PRInt32 i = childStartIndex; i < childEndIndex; i++) {
>+    DisplayListElement2* element = NS_STATIC_CAST(DisplayListElement2*, aBuffer.ElementAt(i));
>+    if (!autoZIndex) {
>       element->mZIndex = explicitZIndex;
>+    } else if (aNode->mView->IsTopMost()) {
>+      // promote children to topmost if this view is topmost
>+      element->mZIndex |= nsInt64(1);
>     }
>   }

Finally reading the patch.  autoZIndex and aNode->mView-IsTopMost() are
loop-invariant, so perhaps this control flow should be inverted, to wrap the
if-else around two for loops, one for the autoZIndex case and the other for the
else-if's condition.  Save some cycles, spend a little more instruction space.

>+      // if aAfter is set, we will insert the child after 'prev' (i.e. after 'kid' in document
>+      // order, otherwise after 'kid' (i.e. before 'kid' in document order).
> 
>+#if 1

Why keep the #if 0 code around?  CVS will remember.  Sorry if this is all part
of a plan whereby the #if-0'd code will reemerge triumphant, soon.

>+      if (nsnull == aSibling) {

(Bletch to the (nsnull == ...) style, which isn't followed consistently in
other newly-added code, below.	Nit, I'm whiny today.)

>+        if (aAfter) {
>+          // insert at end of document order, i.e., before first view
>+          // this is the common case, by far
>+          parent->InsertChild(child, nsnull);
>+        } else {
>+          // insert at beginning of document order, i.e., after last view
>+          nsView *kid = parent->GetFirstChild();
>+          nsView *prev = nsnull;
>+          while (kid != nsnull) {
>+            prev = kid;
>+            kid = kid->GetNextSibling();
>+          }
>+          // prev is last view or null if there are no children
>+          parent->InsertChild(child, prev);
>+        }
>+      } else {
>+        nsView *kid = parent->GetFirstChild();
>+        nsView *prev = nsnull;
>+        while (nsnull != kid && sibling != kid) {
>           //get the next sibling view

Sorry for the lo-cal nit-picking -- maybe the loop/if inversion is worth it.

/be

Comment 32

[Robert O'Callahan (:roc) (email my personal email if necessary)]

I'm opting for saving code space (source code space, really). We have no reason
to believe that these cycles are significant.

The #if 0 code will be eradicated soon. There is a lot of dead code in the view
system and I'm going to take it all out at once.

Comment 33

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Fix checked in.