512336 - Make frame lists doubly-linked

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Boris Zbarsky [:bzbarsky]]

Once the patches for bug 233463 land, we should make frame lists doubly-linked.  Note that doing that will involve auditing the various remaining SetNextSibling callers.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Note that it might be simplest to fix bug 512338 as part of this patch instead of trying to make sure its SetNextSibling usage is still sane with this bug fixed...

Comment 2

[Mats Palmgren (inactive)]

FWIW, I have a wip patch on top the patch set in bug 233463.
The nsFrameList changes were easy, but fixing the places in nsBlockFrame
that still uses SetNextSibling were tricky.  The patch did survive
a TryServer run, but I'm not very confident with it yet...

Maybe we should first make nsBlockFrame use its 'mFrames' for its principal
list, and replace the SetNextSibling calls with nsFrameList methods?

BTW, are there any plans on changing nsLineBox to use something different
than mFirstChild + count, maybe a nsFrameList::Slice ?

Comment 3

[Boris Zbarsky [:bzbarsky]]

> Maybe we should first make nsBlockFrame use its 'mFrames' for its principal
> list, and replace the SetNextSibling calls with nsFrameList methods?

That certainly seems like the path of least resistance to me.  I believe that's blocked on fantasai's elimination of overflow placeholders, right?  fantasai, is there a bug on that?  If so, we should file a bug on switching bugs to mFrames and make it depend on eliminating the placeholders and block this bug.

> BTW, are there any plans on changing nsLineBox to use something different
> than mFirstChild + count, maybe a nsFrameList::Slice ?

There are plans to make it use something different (at least in my head!).  nsFrameList::Slice is one possibility, but another simple option is to just have an mFirstChild.  Then the frames the line contains are all the frames between mFirstChild and the next line's mFirstChild.  The line has a pointer to the next line so this works and even allows fast access to the line's last child one we doubly-link the frames.  The only issue is the last line; to make the last child thing work right there we'd need to pass the blockframe or its mFrames into the last-child-getting function or something...

The main issue in my mind with nsFrameList::Slice use here (and it's an issue the current design already has) is that it's not that hard to end up with frames that no line claims to own, right?

Comment 4

[Boris Zbarsky [:bzbarsky]]

I filed bug 512470 on nsLineBox stuff.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Filed bug 512471 on nsBlockFrame using its mFrames.

Comment 6

[fantasai]

Yes, overflow placeholders will be removed in bug 492627.

Or you could use mFirstChild's mParent to get the blockframe. :)

Comment 7

[Boris Zbarsky [:bzbarsky]]

Hmm.  That would work just fine, yes.  Good idea!

Comment 8

[Boris Zbarsky [:bzbarsky]]

Attachment: Fix

This applies on top of the patch for bug 512471.

Comment 9

[fantasai]

         PRBool wasSearchingOverflowList = searchingOverflowList;
         TryAllLines(&line, &line_start, &line_end, &searchingOverflowList);
-        if (NS_UNLIKELY(searchingOverflowList && !wasSearchingOverflowList &&
-                        prevSibling)) {

Also remove PRBool wasSearchingOverflowList = searchingOverflowList;

    * The second frame is a hint for the prev-sibling of aFrame; if the
    * hint is correct, then this is O(1) time.
    */
-  void RemoveFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint = nsnull);
+  void RemoveFrame(nsIFrame* aFrame);

Also remove the comment that talks about aPrevSiblingHint :)

   void SetNextSibling(nsIFrame* aNextSibling) {
+    if (mNextSibling && mNextSibling->GetPrevSibling() == this) {
+      mNextSibling->SetPrevSibling(nsnull);
+    }

Maybe I'm not wrapping my head around this correctly, but shouldn't "mNextSibling->GetPrevSibling() == this" be an assertion, and not needed as part of this if-clause?

+private:
+  void SetPrevSibling(nsIFrame* aPrevSibling) {
+    mPrevSibling = aPrevSibling;
+  }

I would prefer not to create this method. mPrevSibling should be directly modified by SetNextSibling() and there should be no suggestion that it should be modifiable by anyone else at all.

   nsIFrame *child = mFrames.FirstChild();
-  nsIFrame *curPrevSib = nsnull, *newPrevSib = nsnull;
-  PRBool foundPrevSib = PR_FALSE, foundNewPrevSib = PR_FALSE;
+  nsIFrame *newPrevSib = nsnull;

Since you're touching these lines anyway, please switch them to put the star before the space so they're consistent with the rest of layout/.

+    PRUint32 ordCmp = child->GetOrdinal(aState);
+    if (ord < ordCmp) {
+      break;
+    }

I'd fold this to get rid of ordCmp; there's no need to cache it here, not even for line-wrapping.

Otherwise it looks good!

Comment 10

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to comments

> Maybe I'm not wrapping my head around this correctly, but shouldn't
> "mNextSibling->GetPrevSibling() == this" be an assertion,

I used to not have that check (nor the assertion, which made the debugging fun) and ran into crashes during reftests/crashtests with frames having a null mPrevSibling when they were the mNextSibling of something.

The thing is, if the nextsibling linkage looks like A -> B -> C and someone wants to take frame B out of the list, they typically do A->SetNextSibling(C) followed by B->SetNextSibling(nsnull).  That's certainly what nsFrameList::RemoveFrame does.  Without that extra condition, after the first SetNextSibling call the next-sibling pointers are A->C, B->C, C->null and the previous-sibling pointers are A->null, B->null, C->A.  Then after the second SetNextSibling call the previous sibling pointers are null in all three frames, and we lose.

If we had fewer SetNextSibling callsites, it might have been worth making sure they all do the ordering "right", but as it is I decided this is safer and easier.

I addressed the other comments.  Good catches all.

Comment 11

[fantasai]

Comment on attachment 401592 [details] [diff] [review]
Updated to comments

r=fantasai

Comment 12

[fantasai]

BTW, do we still need the FrameLinkEnumerator now that we have prevSibling access?

Comment 13

[Boris Zbarsky [:bzbarsky]]

Sort of, because prevSibling doesn't help with expressing "link from last frame in the list to null" as things stand.  Or "link from null to first frame in the list", depending on which frame you keep track of.

Comment 14

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

Comment on attachment 401592 [details] [diff] [review]
Updated to comments

great!

Comment 15

[Boris Zbarsky [:bzbarsky]]

Pushed http://hg.mozilla.org/mozilla-central/rev/c52390466bd1