512471 - Make nsBlockFrame's mFrames track its principal child list

Status: RESOLVED FIXED

(Core :: Layout: Block and Inline, defect)

Description

[Boris Zbarsky [:bzbarsky]]

This would make fixing bug 512336 much simpler.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Proposed fix

This applies on top of Mats' patches in bug 233463.  Please review very carefully; some of this stuff was a bit.... fragile-looking.  I've gone through it pretty carefully, but I don't really know this code that well.

Particular things to pay attention to:

1)  The code ordering change in nsBlockFrame::PullFrameFrom.  Is that ok?  I
    _think_ it should be, but if it's not please tell me!
2)  nsBlockFrame::StealFrame had this weird behavior where it didn't update
    line->mFirstChild if prevSibling was non-null.  Since we keep track of 
    prevSibling across lines there, I have no idea how that could have been
    correct, so I changed it.  But maybe there was a reason for the way it was
    written?
3)  I left AddFrames virtual, but that seems kinda bogus to me.  Any objections
    to changing that?

Comment 2

[Timothy Nikkel (:tnikkel)]

Comment on attachment 400823 [details] [diff] [review]
Proposed fix

>       NS_ASSERTION(aState.mPrevChild || mLines.empty(), "should have a prevchild here");
> 
>+      NS_ASSERTION(aState.mPrevChild == mFrames.LastChild(),
>+                   "Incorrect aState.mPrevChild before inserting line at end");
>+

You can just replace the old assertion with your new one (I added the old one in bug 513394). I do the same thing in bug 515811, but yours is better.

Comment 3

[Timothy Nikkel (:tnikkel)]

Oops, I meant that I added the old one in bug 514634, the followup to bug 513394.

Comment 4

[Boris Zbarsky [:bzbarsky]]

I'd like to keep both assertions, since that implicitly asserts that mFrames.LastChild() has been updated correctly.

Comment 5

[fantasai]

+  // Now clear mFrames, since we've destroyed all the frames in it.
+  mFrames.Clear();

Put this up near the relevant destroy call.

+    // XXXbz once we start using nsFrameList for our overflow list, we
+    // could switch GetChildList to returning a |const nsFrameList&|.

Why not do that in this patch? It seems like the code would be more understandable if both line lists had the same storage model. I'd also like to see the linebox/linelist classes handle more of the frame splicing if that's possible.

If you can make this patch apply on top of the double-linking instead of before them, I think that might be a good idea. It would give you a better opportunity to clean up some of this code.

Comment 6

[Boris Zbarsky [:bzbarsky]]

Hmm.  I did this before double-linking because I had hoped it would reduce the number of SetNextSibling callsites and so that I wouldn't have to worry about the block's framelist getting confused.  I suppose I can see about changing the order.

It wasn't clear to me whether the extra nsFrameList allocations involved in making the overflow list into an nsFrameList were worthwhile.  If you think they are, I could try to do that...

I assume by "more of the splicing" you mean splicing the framelist?  That involves having access the relevant nsFrameList, right?  I suppose that could be an argument for some of that stuff.

I'll be honest: I'd been hoping for a minimally-invasive change here so I could fix the bugs it blocks.  If you want, I can try to go for something more extensive, or I could do it as a followup.  Either way, I guess.

Comment 7

[fantasai]

(Yes, that involves having access to the relevant nsFrameList.)

If it's possible to double-link underneath this patch, then I don't see what benefit we're gaining here by doing a half-way fix. The other two bugs blocked by this bug are perf; how does this patch fix them?

Comment 8

[Boris Zbarsky [:bzbarsky]]

> If it's possible to double-link underneath this patch

It's possible, I think.  I think it's certainly more work on my end than doing a followup.  Not sure about review work...  I guess I'll do it, in the interests of getting at least one of these patches in.  Part of the issue, I guess is that trying to clean up this code scares me, so I'd rather do it in bite-sized pieces so at least I get sane regression ranges on the bugs Jesse will file... ;)

If you feel strongly that you'd prefer a more comprehensive patch, I can do that, I guess.  If not, I'd prefer to land these patches as-is, and work on a followup to clean up even more.

> how does this patch fix them?

It makes it possible to append to a block in O(1) time instead of O(# of frames on last line) time.  The blocked testcase has all the block's kids on a single line (all 60000 of them), because they're all placeholders.

Comment 9

[fantasai]

Ok, well. I don't *like* that the overflow lines code is getting harder to understand rather than easier. But if you feel the priority is getting the perf fix in asap, here's comments:

+      if (collectOverflowFloats) {
+        // Pulling from an overflow list

If collectOverflowFloats means we're pulling from an overflow list, change the name of the variable so that's clear. Right now it seems to be more specific than that, for unknown reasons.

+        nsFrameList::FrameLinkEnumerator linkToBreak(nextInFlow->mFrames, lastFrame);
+        nextInFlow->mFrames.ExtractHead(linkToBreak);

For the record, I think this would make more sense like
  nextInFlow->mFrames.RemoveFramesBefore(lastFrame->GetNextSibling())
rather than creating a FrameLinkEnumerator just to break the list at that point.
But we can't do that atm. (Just sayin', for future reference; I like the RemoveFramesAfter method name, it's very clear what it does.)

+      nsFrameList newFrames(toMove->mFirstChild, lastFrame);
+      mFrames.InsertFrames(nsnull, aState.mPrevChild, newFrames);

Keep all the frame list splicing together. This needs to move up next to nextInFlow->mFrames.ExtractHead. Also, why is that InsertFrames instead of AppendFrames, isn't that what we're doing here?

-      if (! mLines.empty()) 
-        {
+      if (! mLines.empty()) {

Also get rid of the space.

+  for (nsFrameList::Enumerator e(newFrames); !e.AtEnd(); e.Next()) {
+    nsIFrame* newFrame = e.get();
+    NS_ASSERTION(!aPrevSibling || aPrevSibling->GetNextSibling() == newFrame,
+                 "Unexpected aPrevSibling");

How does this assert not fire when we're adding more than one frame at a time?

Otherwise looks ok.

Comment 10

[Boris Zbarsky [:bzbarsky]]

> if you feel the priority is getting the perf fix in asap,

The priority is getting double-linking in ASAP because it blocks other work...  The fastest path there is to land this, I think, instead of rewriting parts of the double-linking patch.  But again, if you feel strongly about it I'll do that rewriting.

>  nextInFlow->mFrames.RemoveFramesBefore(lastFrame->GetNextSibling())

We would need to define that this removes all frames if null is passed in, right?  Past that, I'd be fine with adding this as a followup.

> Keep all the frame list splicing together.

Will ReparentFloats work right if we put in the new frames before calling it?  I guess it should....

> Also, why is that InsertFrames instead of AppendFrames

No particularly good reason past mechanically changing code.  Will change.

> How does this assert not fire when we're adding more than one frame at a time?

Because the tail of the for loop changes aPrevSibling.

Comment 11

[Boris Zbarsky [:bzbarsky]]

Attachment: Updated to comment 5 and comment 9

Comment 12

[Boris Zbarsky [:bzbarsky]]

Attachment: interdiff between the two patches

Comment 13

[Boris Zbarsky [:bzbarsky]]

Filed bug 518665 on cleaning up the overflow lines situation.

Comment 14

[fantasai]

-      lastFrame->SetNextSibling(nsnull);
+      if (toMoveIsOverflowLine) {
+        // Pulling from an overflow list
+        // XXXbz If we switch overflow lines to nsFrameList, we should
+        // change this SetNextSibling call.
+        lastFrame->SetNextSibling(nsnull);
+      } else {
+        // Pulling from nextInFlow->mFrames
+        nsFrameList::FrameLinkEnumerator linkToBreak(nextInFlow->mFrames, lastFrame);
+        nextInFlow->mFrames.ExtractHead(linkToBreak);
+      }
+      NS_ASSERTION(lastFrame == toMove->LastChild(), "Unexpected lastFrame");
+
+      NS_ASSERTION(aState.mPrevChild || mLines.empty(), "should have a prevchild here");
+
+      NS_ASSERTION(aState.mPrevChild == mFrames.LastChild(),
+                   "Incorrect aState.mPrevChild before inserting line at end");
+
+      // Add line to our line list, and set its last child as our new prev-child
+      nsFrameList newFrames(toMove->mFirstChild, lastFrame);
+      mFrames.AppendFrames(nsnull, newFrames);
+      aState.mPrevChild = lastFrame;
+
+      NS_ASSERTION(aState.mPrevChild == mFrames.LastChild(),
+                   "Incorrect aState.mPrevChild after inserting line at end");
+
+      line = mLines.before_insert(end_lines(), toMove);


By "Keep all the frame list splicing together" I mean like this:

+      NS_ASSERTION(lastFrame == toMove->LastChild(), "Unexpected lastFrame");
+      NS_ASSERTION(aState.mPrevChild || mLines.empty(),
+                   "should have a prevchild here");
+      NS_ASSERTION(aState.mPrevChild == mFrames.LastChild(),
+                   "Incorrect aState.mPrevChild before inserting line at end");
+
+      // Append toMove frames to our frame list
+      if (toMoveIsOverflowLine) {
+        // Pulling from an overflow list
+        // XXXbz If we switch overflow lines to nsFrameList, we should
+        // change this SetNextSibling call.
+        lastFrame->SetNextSibling(nsnull);
+      } else {
+        // Pulling from nextInFlow->mFrames
+        nsFrameList::FrameLinkEnumerator linkToBreak(nextInFlow->mFrames, lastFrame);
+        nextInFlow->mFrames.ExtractHead(linkToBreak);
+      }
+      nsFrameList newFrames(toMove->mFirstChild, lastFrame);
+      mFrames.AppendFrames(nsnull, newFrames);
+
+      // Add line to our line list, and set its last child as our new prev-child
+      line = mLines.before_insert(end_lines(), toMove);
+      aState.mPrevChild = lastFrame;
+      NS_ASSERTION(aState.mPrevChild == mFrames.LastChild(),
+                   "Incorrect aState.mPrevChild after inserting line at end");

This keeps:
  - preconditions for what we're doing before we get deep into it
  - postconditions for what we're doing after we're done
  - all framelist splicing code together, not mixed with other stuff like
    unrelated assertions
  - comments about what we're doing next to the code that implements them

r=fantasai with that change

Comment 15

[Boris Zbarsky [:bzbarsky]]

Attachment: With that change

Comment 16

[fantasai]

Comment on attachment 402664 [details] [diff] [review]
With that change

+      // Disconnect toMove's frames from our overflow list

If you want a comment like that, put it inside the if-statement because that's all it applies to. If you want a comment to summarize the whole block code underneath it (more useful), then something like
// Shift toMove's frames into our mFrames list
would be more useful.

Comment 17

[Boris Zbarsky [:bzbarsky]]

Pushed http://hg.mozilla.org/mozilla-central/rev/dab2d59ebd97 with that comment change.