Closed Bug 512336 Opened 15 years ago Closed 15 years ago

Make frame lists doubly-linked

Categories

(Core :: Layout, defect)

x86
macOS
defect
Not set
normal

Tracking

()

RESOLVED FIXED

People

(Reporter: bzbarsky, Assigned: bzbarsky)

References

(Blocks 2 open bugs)

Details

Attachments

(1 file, 1 obsolete file)

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.
Blocks: 512338
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...
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 ?
> 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?
I filed bug 512470 on nsLineBox stuff.
Blocks: 512470
Filed bug 512471 on nsBlockFrame using its mFrames.
Depends on: 512471
Yes, overflow placeholders will be removed in bug 492627.

Or you could use mFirstChild's mParent to get the blockframe. :)
Hmm.  That would work just fine, yes.  Good idea!
Blocks: 424715
Blocks: 516742
Attached patch Fix (obsolete) — Splinter Review
This applies on top of the patch for bug 512471.
Assignee: nobody → bzbarsky
Status: NEW → ASSIGNED
Attachment #400824 - Flags: review?(roc)
Attachment #400824 - Flags: review?(fantasai.bugs)
Blocks: 40988
         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!
> 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.
Attachment #400824 - Attachment is obsolete: true
Attachment #401592 - Flags: review?(roc)
Attachment #401592 - Flags: review?(fantasai.bugs)
Attachment #400824 - Flags: review?(roc)
Attachment #400824 - Flags: review?(fantasai.bugs)
Comment on attachment 401592 [details] [diff] [review]
Updated to comments

r=fantasai
Attachment #401592 - Flags: review?(fantasai.bugs) → review+
BTW, do we still need the FrameLinkEnumerator now that we have prevSibling access?
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.
Blocks: 518656
Blocks: 518665
Pushed http://hg.mozilla.org/mozilla-central/rev/c52390466bd1
Status: ASSIGNED → RESOLVED
Closed: 15 years ago
Resolution: --- → FIXED
Blocks: 529950
No longer blocks: 529950
Depends on: 529950
Depends on: 554376
Depends on: 696640
You need to log in before you can comment on or make changes to this bug.