233463 - Have faster methods for getting at last frames

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Boris Zbarsky [:bzbarsky]]

See bug 40988 comment 62 and slightly preceding. The idea is to add
GetLastChild() on nsIFrame and a pointer on nsFrameList to speed it up.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: Work in progress

I've not tested this carefully yet (nor run it in a debug build, for that
matter).  I did check on the testcase in bug 40988, though.  With this patch
that testcase gets about 30% faster or so (it still has two O(N^2) functions in
it, even with this patch).

Some things that I'm not sure about with this change:

1)  How to get the last normal child of nsBlockFrame.  I guessed, but it may be

    wrong... David, what do you think?
2)  Whether to have mLastChild be lazily computed the first time or maintained
    always.  Always maintaining it seems simpler than sometimes maintaining and

    sometimes not, and shouldn't be much slower.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Fixes some issues in nsFrameList.h

This is even somewhat tested.... ;)

Comment 3

[Boris Zbarsky [:bzbarsky]]

Hmm.. I'm seeing assertions trigger in nsTableFrame::CreateAnonymousColFrames on
nytimes.com.

The problem seems to be that the code there manually hooks the frames it creates
up to lastColFrame.  Then it calls AppendFrames on them on a list which seems to
have the lastColFrame as its head!  Without my patch, that should produce the
following data structure, if I understand what's going on correctly:

lastColFrame -> firstCreatedFrame -> ... -> lastCreatedFrame -> firstCreatedFrame

which is really bad, as linked lists go (and I'm surprised it's not bitten us
before).  bernd, what's this method trying to achieve and why?  And why's it
casting frames of type nsLayoutAtoms::tableColFrame to nsTableColGroupFrame*???

Comment 4

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 141360 [details] [diff] [review]
Fixes some issues in nsFrameList.h

>Index: layout/base/src/nsFrameList.cpp
> nsFrameList::RemoveFrame(nsIFrame* aFrame)
>+      if (!nextFrame) {
>+        mFirstChild = nsnull;
>+      }

That should set mLastChild, of course.	Fixed locally, but waiting to hear what
the table story is before posting an updated patch....

Comment 5

[Boris Zbarsky [:bzbarsky]]

Shaver's patch is in bug 74656 

Comment 6

[rbs]

The hick is in the extra member... As a space-efficient possibility, if you
don't mind weird ideas...
- change the child list into a circular list
- only keep mLastChild
- thus FirstChild becomes available implicitly as mLastChild->next
- deal with the tons of places that assume that it goes from first to nsnull...

Comment 7

[Boris Zbarsky [:bzbarsky]]

> - deal with the tons of places that assume that it goes from first to
> nsnull...

This is the kicker.  That's all of layout right there....  I'm having enough
trouble with code that assumes that we have an nsFrameList class for fun only
and that manually munging the linked list inside it is a fun and profitable
thing to do.  :(  And that's by far the least part of the layout code....

Comment 8

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

Here's another version of rbs's suggestion. Suppose we have a free frame state
bit (haha). Use a frame state bit to indicate "last child" [shouldn't be too
hard to maintain: just find all setters of mNextSibling/SetNextSibling and set
the state bit if they are currently setting to nsnull]. Change any direct
readers of mNextSibling to use GetNextSibling() [easy]. Change GetNextSibling to

nsIFrame* GetNextSibling() { return (mState & NS_FRAME_IS_LAST) ? nsnull :
mNextSibling; }

I suspect we'd eat some pageload time and code size though.

Comment 9

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

Hmm, I guess with that, the code you get for the normal for loop isn't the best.
for (nsIFrame* f = blah; f; f = f->GetNextSibling()) {
 ...
}

expands to

nsIFrame* f = blah;
if (!f) goto end;
start:
...
nsIFrame* tmp;
if (!(f->mState & NS_FRAME_IS_LAST)) goto label1;
tmp = nsnull;
goto label2;
label1:
tmp = f->mNextSibling;
label2:
f = tmp;
goto start;
end:

so we'd have to do two conditional branches per iteration (in case mNextSibling
is itself null).

Comment 10

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

It's too bad gcc doesn't have a way to tell the optimizer that a certain value
will never be null.

Comment 11

[Boris Zbarsky [:bzbarsky]]

roc, what's the benefit of your proposal?  The goal of this bug is to make
appending a bunch of frames to a frame list one at a time O(N) instead of O(N^2).

Comment 12

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

Oh, I meant "follow rbs and make the child frames a circular list and keep
mLastChild, so GetFirstChild() can just return mLastChild->mNextSibling"

Comment 13

[Boris Zbarsky [:bzbarsky]]

Oh, hmm.... That may work.... We do have free framestate bits (at least two that
I can think of).

I may try to do this.  It should be much safer than my approach (since there
will be less state to keep consistent).

Comment 14

[Boris Zbarsky [:bzbarsky]]

Note to self:  when someone calls SetNextSibling(nsnull) on a frame what we
actually need to do is:

1)  Mark ourselves as the last frame.
2)  Walk to the end of the framelist and set the mNextSibling of the frame with
    the "last frame" bit set as our mNextSibling.

Comment 15

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

I'm not sure that my proposal is a good idea :-). It would add a conditional
branch to everyone who calls GetNextSibling(). Although you can do tricks to
turn the conditional into some arithmetic ops.

For what kind of containers do we really need fast access to the last child?
Blocks already have fast access to their last line, and I'm not aware of any
code paths that need access to the last inline on a line. For inlines, maybe in
pathological cases you might have very long spans with lots of children (*very*
pathological since most lines would wrap first), but then block reflow is going
to bog down even if you have a last-child pointer. Not sure about tables, but I
know tables already have cell maps and other funky structures that can probably
take care of things. So, the original motivating example is the only case I can
think of: nsAbsoluteContainingBlock. One way to deal with this particular case
is to change nsAbsoluteContainingBlock so it lazily allocates a (firstChild,
lastChild) pair when something is first added to it, and contains just a pointer
to that pair or null.

Comment 16

[Boris Zbarsky [:bzbarsky]]

> For what kind of containers do we really need fast access to the last child?

See comment 0 and the link therein.

> and I'm not aware of any code paths that need access to the last inline on a
> line.

Appending to a block.

> *very* pathological since most lines would wrap first

Not if all of those children are placeholders for positioned stuff....

> So, the original motivating example 

The original motivating example was actually random code in the
nsCSSFrameConstructor that walks the frame list by hand or calls LastChild() on
an nsFrameList to get the last frame, as well as the line box code (which the
patches I have posted thus far do not fix).  This happens for all sorts of
lists, not just nsAbsoluteContainingBlock.

Comment 17

[rbs]

Adding bug 145425 as a dependency. Might be another bug that motivates (non
premature) optimizations.

Re: Comment #14 & Comment #15

SetNextSibling(nsnull): You could also forbid that operation (as a second
patch?), and provide a SetLastChild() that people can use. Also, maybe it is
worth privatizing |mNextSibling| to enforce your desired invariants, and
safeguarding from regressions in the future.

As for the conditional branch, I wouldn't be scared too much (at least without
any profile data). I often take courage by saying to myself that "every _single_
character that Gecko displays is tested against a bunch of fontS, yet it
amazingly goes so fast. And if that goes so fast, ..."

Comment 18

[Boris Zbarsky [:bzbarsky]]

> SetNextSibling(nsnull): You could also forbid that operation (as a second
> patch?)

It'd have to be... That would involve some pretty significant surgery on tables
code and splitting of frames while printing (yay!).  A lot of that code has no
idea who the parent of the list of frames it's munging is (which is why it
causes problems with my initial approach).

> Also, maybe it is worth privatizing |mNextSibling|

Definitely.

The conditional branch thing looks like premature optimization to me... the
problem right now is that appending a bunch of things is O(N^2) and some pages
do it on hundreds or thousands of items.  That's an algorithmic problem that
needs solving somehow....

All this said, I still don't understand the code I talked about in comment 3. 
That code creates a loop in the frame tree as far as I can tell.  Am I missing
something?

Comment 19

[Bernd]

re comment 3, damned is that still broken? see
http://bugzilla.mozilla.org/show_bug.cgi?id=139524#c42. Boris if you can replace
Chris' list assembler with a C++ solution it would be great. It might solve some
of these print crashes or as a side effect people will not be so scared when
they see the code. (I am least so scared that I don't touch printing, and it
seems that I am not the only one). The assertion at nytimes could you send me
the page content.

Comment 20

[Boris Zbarsky [:bzbarsky]]

bernd, should we spin off the cols issue into a separate bug?  It sounds like
something we need to resolve before we go any further with the rest of this...

I don't have these changes in a debug build right now, so I can't guarantee that
what I send you actually triggers the assert, but I'll send you the page.

Comment 21

[Boris Zbarsky [:bzbarsky]]

So, what I suggest in comment 14 will NOT work, in fact.  The nsFrameList will
be pointing to the wrong frame as a result of this operation.  So doing rbs'
suggestion would still involve eliminating all current callers of
SetNextSibling(nsnull) (as would any implementation of this bug, I suspect).

To really fix this, I suspect we would have to:

1)  Use nsFrameList& instead of nsIFrame* any time we have frame lists.
2)  Fix most  of our code to stop assuming anything about how frame lists work
    (that is, whether it's a linked list, an array, or whatever).

Comment 22

[Boris Zbarsky [:bzbarsky]]

That patch also has some issues related to the fact that nsInlineFrame::Reflow
appends overflow frames to mFrames.  We either end up in an infinite loop
(looking for the end of the overflow list when appending) or just take a very
long time (O(N^2) or higher algorithm).  Hard to tell which, but the net result
is 100% cpu usage and no rendering.

Comment 23

[Boris Zbarsky [:bzbarsky]]

I'm not going to have time to work on this any time in the foreseeable future
(we're talking many months here), so to default owner.  As far as I can tell,
doing this would involve a systematic audit of most of layout and rewrites of
far too much code.  The wonders of assuming things are a linked list all over
instead of having a class encapsulating the storage method.

Bernd, I guess bug 139524 is the bug on that colframe loop?

Comment 24

[Boris Zbarsky [:bzbarsky]]

Er, no.  That bug is resolved.  I've filed bug 240245 on the issue.

Comment 25

[Boris Zbarsky [:bzbarsky]]

More thoughts on how this should work (building on comment 21):

1)  Use nsFrameList& instead of nsIFrame* any time we have frame lists.
2)  Make SetNextSibling/GetNextSibling protected methods of nsIFrame*
3)  Make nsFrameList a friend class of nsIFrame*
4)  Eliminate all other callers of SetNextSibling/GetNextSibling (have to, to
    make things compile), and use nsFrameList methods to manipulate frame lists.
5)  Have nsFrameList do whatever it wants to internally, since at that point
    most of layout won't know anything about its inner workings.
6)  (Optional, but I think we want it) Make nsFrameList::First()/Last() return
    not frames but frame iterator thingies that we can call next() on to advance
    (sorta like what the line list does for blocks).  These can be efficiently
    implemented for either linked lists or arrays or circular lists or whatever.

Does this program seem reasonable to people?  If so, we could start working on
it (removing consumers of SetNextSibling/GetNextSibling and replacing them with
nsFrameList access).

Comment 26

[Nicholas Allen]

Somewhere in there, maybe around 4), the API for nsFrameList needs an overhaul.
 Right now it's just a couple of nsIFrame utility methods stuck on a linked list
class.  Ideally it would be easier to figure out how to use nsFrameList than to
do something directly with nsIFrame*s.

Comment 27

[rbs]

You can also borrow from the DOM APIs which had the benefit of extensive
debates/thoughts.
- have nsFrameList& -- the catch all - an iter is fine.
- retain GetNextSibling() -- this is useful. Otherwise one has to get the
parent's frameList, etc. It is readonly, so not a big deal.

- parent->AppendChild(...)
- parent->InsertChildBefore(another, ...)

the intringuing ones... equivalent to delegating to some method of the parent's
nsFrameList - something that is bound to happen anyhow.

[You mentioned in comment 18 that the parent isn't known -- but it is in any
frame's GetParent() for those who care. Note: what I am getting at is that the
way the DOM defines its walking methods might provide another food for thought.]

Comment 28

[Boris Zbarsky [:bzbarsky]]

> Somewhere in there, maybe around 4), the API for nsFrameList needs an overhaul.

Yes, that would be absolutely necessary to implement step 4.

> - parent->AppendChild(...)
> - parent->InsertChildBefore(another, ...)

We have those already -- SetInitialChildList, AppendFrames, InsertFrames,
RemoveFrame, ReplaceFrame all on nsIFrame.  Some of those need to take
nsFrameLists instead of nsIFrames, though (all but RemoveFrame and ReplaceFrame,
in fact).

> You mentioned in comment 18 that the parent isn't known

I should have been more precise.  The parent is known, but to use the parent you
need to know the parent and which of the parent's child lists a frame is in. 
the latter is what is not known.

Comment 29

[rbs]

> We have those already

Yes I know that (and know that you know that...). I was on the DOM route and
mentioned them from completeness -- to remain in the new nsFrameList, whatever
it becomes.

> which of the parent's child lists a frame is in

that's much clear...

Your plan sounds good, save for retaining GetNextSibling() as directly as possible.

Comment 30

[Boris Zbarsky [:bzbarsky]]

Yeah, GetNextSibling can probably stay, since as you point out it returns
something that can't be used to mutate the frame list.

Comment 31

[Mike Schroepfer]

Nominating as a result of the discussion on dev.performance:

http://groups.google.com/group/mozilla.dev.performance/browse_thread/thread/84fa381688f2fd2b/cab86fb32ccda8ee#cab86fb32ccda8ee

Comment 32

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

I don't think this can block 1.9. It's large amount of work, risky too.

Comment 33

[Boris Zbarsky [:bzbarsky]]

I was about to say exactly that.  This would be great to have, but it's a huge architectural change with lots of regression risk.  Definitely early alpha material.

Comment 34

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

One potential solution is to do something similar as I did for the nsINode::IndexOf cache. Basically keep a cache mapping nsFrameList to last-child-in-list. This cache can be done very fast by using inexact caching, see AddIndexToCache and GetIndexFromCache in nsAttrAndChildArray.cpp.

The only thing we'd need to do different is to make sure that when a frame dies it is removed from the cache, but that should be as fast as AddIndexToCache if we still have the nsFrameList pointer still around. And we'd also need to remove things from the cache when they are moved from one nsFrameList to another if that ever happens?

Comment 35

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

My suggestion probably doesn't change the risk though.

Comment 36

[Boris Zbarsky [:bzbarsky]]

> make sure that when a frame dies

Or when the GetNextSibling() of any frame earlier in the list changes.

The real issue is that people manually mess with the innards of nsFrameLists (not using the frame list API).  If they didn't, we'd have no problem implementing one of the earlier suggestions in this bug....

> when they are moved from one nsFrameList to another if that ever happens?

Right.  This happens.  A lot, actually.

Comment 37

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

If you could get from the frame to its frame-list you could deal with both those situations doing something like:

nsIFrame* GetLastFrame(nsFrameList* aList)
{
   PRUint32 ix = CACHE_GET_INDEX(aList);
   if (lastFrameCache[ix].list != aList ||
       lastFrameCache[ix].frame->List() != aList) {
     return nsnull;
   }
   nsIFrame* frame, lastFrame = lastFrameCache[ix].frame;
   while ((frame = lastFrame->GetNextSibling())) {
      lastFrame = frame;
   }

   return lastFrame;
}

This does require that frame->List() can be implemented though, which I'm not sure if it can?

(the code above can be optimized somewhat, I know)

Comment 38

[Boris Zbarsky [:bzbarsky]]

> This does require that frame->List() can be implemented though

Not without adding members, in general...

Comment 39

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

Another crazy idea:

We could have a global cache like the one we have for nsAttrAndChildArray::IndexOf. The full solution would be something like this:

Whenever we go look for the last first check the cache. If a result is in the cache start searching there, otherwise search from the first child. When a result is found store in the cache.

Whenever a frame is removed from its parent check if its the cached frame and if so remove it from the cache.


Note that if we write the cache like its done in nsAttrAndChildArray then lookups and writes to the cache are extremely fast.

Comment 40

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

> Whenever a frame is removed from its parent check if its the cached frame and
> if so remove it from the cache.

That's not trivial actually. You could, however, store (parent, child) pairs indexed separately on parent and child. Then you can do a fast lookup on the parent and verify that the child's parent is still the stored parent. When the child is destroyed, nsFrameManager::NotifyDestroyingFrame can efficiently remove the pair.

Comment 41

[Boris Zbarsky [:bzbarsky]]

Yeah, that sounds like it would work.  It might be worth implementing this and seeing how much it helps...  It should at least help DOM-mutation situations, maybe.

Comment 42

[Mats Palmgren (inactive)]

Attachment: Like so?

* add a mLastChild member to nsFrameList for fast access
* eliminate SetNextSibling calls everywhere that could potentially
  invalidate that member
* change SetInitialChildList/AppendFrames/InsertFrames to take a
  const nsFrameList&
* replace nsFrameItems (in nsCSSFrameConstructor) with nsFrameList
* add nsIFrame::GetLastChild(nsIAtom*)  (from Boris' earlier patch)
* cleanup nsFrameList API
* use nsFrameList in a lot more places....

Comment 43

[Boris Zbarsky [:bzbarsky]]

So... that looks like it'll seriously conflict with the work in bug 281387 and its dependencies (as in, duplicate some of it).

Comment 44

[Boris Zbarsky [:bzbarsky]]

And it worries me that it doesn't remove all SetNextSibling calls outside nsFrameList, which makes it a lot harder to be sure that it's correct.

Comment 45

[Boris Zbarsky [:bzbarsky]]

Or does it remove all of them?

Comment 46

[Mats Palmgren (inactive)]

(In reply to comment #43)
> So... that looks like it'll seriously conflict with the work in bug 281387 and
> its dependencies (as in, duplicate some of it).

Ah, I wasn't aware of your work there... or in bug 504221...

(In reply to comment #45)
> Or does it remove all of them?

It removes all that matters.  The remaining ones are in nsBlockFrame
which doesn't affect any nsFrameList.  I don't think we have to worry
about those unless we make nsLineBox::mFirstChild into a nsFrameList.

There are a couple more remaining in nsCSSFrameConstructor.cpp
nsBoxFrame.cpp (MergeSort) but they should be safe (their frame list
are under control in those cases).  I was planning to eliminate those
eventually though and possibly make SetNextSibling private to
nsBlockFrame/nsFrameList somehow...

So, I guess I should wait until your patches land and see if there's
anything in my patch that could still be useful after that?

Comment 47

[Boris Zbarsky [:bzbarsky]]

If you're willing to do that, I'm certainly not going to complain!

For what it's worth, I would think that at the very least most of the SetNextSibling() changes you made would be usable more or less as-is (possibly with some tweaks to framelist api).  And they're very much welcome!  I hadn't been looking forward to trying to deal with that part of things, esp. in some of the tables code.

I do think we want to change block to nsFrameList (for now in addition to the line list); there can be lots of kids in a single line and dealing with walking to the end of the last line is a pain.  But nsBlockFrame has an unused mFrames that we'd just need to keep in sync; shouldn't be that big a deal, right?

Comment 48

[Boris Zbarsky [:bzbarsky]]

Mats, those patches have all landed now.

Comment 49

[Mats Palmgren (inactive)]

I'm working on this, patches for review soon...

Comment 50

[Mats Palmgren (inactive)]

Attachment: Patch 0, "Eliminate some SetNextSibling calls"

Eliminate some SetNextSibling calls, the ones left should be safe
for now as discussed in an earlier comment.  I made CreateNextInFlow()
assert it's a frame on the principal child list and changed
nsBlockFrame not to use it.  Many callers did in fact not want it
to be inserted there so I changed those to just call
CreateContinuingFrame directly.

Comment 51

[Mats Palmgren (inactive)]

Attachment: Patch 1, "nsTableRowGroupFrame cleanup"

Some related nsTableRowGroupFrame code cleanup.

Comment 52

[Mats Palmgren (inactive)]

Attachment: Patch 2, "Introduce nsFrameList::mLastChild"

Introduce nsFrameList::mLastChild, and make nsIFrame::GetLastChild
a simple non-virtual method like GetFirstChild. The change in nsBlockFrame:

-    return (mLines.empty()) ? nsnull : mLines.front()->mFirstChild;
+    return mLines.empty() ? nsFrameList::EmptyList()
+                          : nsFrameList(mLines.front()->mFirstChild,
+                                        mLines.back()->LastChild());

should work, right?

Comment 53

[Mats Palmgren (inactive)]

Attachment: Patch 3, "fix false positive RemoveFrame asserts"

Make nsFrameList::DestroyFrame/RemoveFrame assert if the frame isn't found
and introduce methods that does not do that.  This is to fix
false positive asserts from StealFrame.  (This patch is slightly unrelated
but I wanted to make sure the patch set as a whole doesn't assert from
within nsFrameList).

Comment 54

[Mats Palmgren (inactive)]

Attachment: Patch 4, "make mNextSibling private"

Also not really necessary for this bug, but I wanted to catch any
mischief and I have it my queue.  I think this is a good idea going
forward, we should not allow sub-classes to tamper with it directly.

Comment 55

[Mats Palmgren (inactive)]

Attachment: Patch 5, "Declare nsFrameList(nsIFrame*) explicit"

Declare nsFrameList(nsIFrame*) explicit and some code cleanup.

Comment 56

[Mats Palmgren (inactive)]

Attachment: Summary, the above patches as one.

Here's what the code looks like after the Patch 0 - 5 is applied.

Comment 57

[Mats Palmgren (inactive)]

There's more to do but I think this patch set is a good first chunk for
reviewing and baking on trunk (remaining work items can be filed as
new bugs). The patch set passes regression tests on TryServer and it
doesn't add any new assertions in my local debug build on Linux.

Comment 58

[Mats Palmgren (inactive)]

> it doesn't add any new assertions in my local debug build on Linux.

To clarify; I didn't see any assertion that wasn't also triggered before
the changes, if there were additional occurrences of an existing assertion
I do not know.

Comment 59

[Mats Palmgren (inactive)]

BTW, I should also point out a problem I found in StealFrame:
https://bugzilla.mozilla.org/attachment.cgi?id=395382&action=diff#a/layout/generic/nsContainerFrame.cpp_sec7
In the current code, in case we don't find aChild on the principal list
and the result of GetOverflowFrames() is null, 'removed' will still
be PR_TRUE and we return NS_OK even though we never found the frame.
This seems like a bug to me and I've included a fix for it.

Comment 60

[fantasai]

-  PRBool result = mAbsoluteFrames.DestroyFrame(aOldFrame);
-  NS_ASSERTION(result, "didn't find frame to delete");
-
-  return result ? NS_OK : NS_ERROR_FAILURE;
+  mAbsoluteFrames.DestroyFrame(aOldFrame);
+  return NS_OK;

Asserts like these were very helpful to me when I was debugging things like the float continuation rewrite and the removal of DeletingFrameSubtree. Why are you removing them?

Comment 61

[Mats Palmgren (inactive)]

It is not my intention to remove any existing assertions, rather add more
of them.  In this case, DestroyFrame calls RemoveFrame where I added
NS_PRECONDITION(ContainsFrame(aFrame), "wrong list");
Previously, it didn't do that, and we had (a few) of the RemoveFrame
call sites do it instead.  (I added Destroy/RemoveFrameIfPresent,
for the few places where the caller does not now.)

Comment 62

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 395372 [details] [diff] [review]
Patch 0, "Eliminate some SetNextSibling calls"

>+++ b/layout/base/nsBidiPresUtils.cpp
>@@ -112,54 +113,51 @@ IsBidiSplittable(nsIFrame* aFrame) {
>+    // Split the child list after |frame|.
>+    nsContainerFrame* container = do_QueryFrame(parent);
>+    nsFrameList tail = container->StealFramesAfter(frame);

Are we guaranteed this QI will succeed?

>+    nsFrameList temp(newParent);

newParent is guaranteed to not have any following siblings here, right?  If so, I'd prefer that we introduce a two-argument nsFrameList constructor in this diff (with first and last frames, as you do later on anyway) and use it here.  For now the impl can just assert that the first child's last sibling is the given last child and call the single-frame constructor.  Once we have the better two-argument implementation, we can work on getting rid of the O(N) single-argument constructor perf nightmare.

>+++ b/layout/base/nsCSSFrameConstructor.cpp
>@@ -2174,44 +2174,44 @@ nsCSSFrameConstructor::ConstructTableCol
>+    aFrameItems.AddChild(newCol);
>     lastCol->SetNextContinuation(newCol);
>     newCol->SetPrevContinuation(lastCol);

If you do the continuation stuff before the AddChild call and use the aFrameItems.lastChild for it, you don't need the lastCol local.  Either way, though.

While you're here, there's this code in nsCSSFrameConstructor::WipeContainingBlock:

  prevSibling =
    nsFrameList(parentPrevCont->GetFirstChild(nsnull)).LastChild();

This should probably become either:

  prevSibling = parentPrevCont->GetChildList(nsnull).LastChild();

or

  prevSibling = parentPrevCont->GetLastChild(nsnull);

>+++ b/layout/generic/nsColumnSetFrame.cpp
>@@ -743,20 +743,19 @@ nsColumnSetFrame::ReflowChildren(nsHTMLR
>+        nsFrameList continuationColumns = mFrames.RemoveFramesAfter(child);

Would it make sense to reuse existing code for this by adding a constructor for FrameLinkEnumerator that takes a const nsFrameList& and the frame before the link and then use ExtractTail here?

>+          SetOverflowFrames(PresContext(), continuationColumns.FirstChild());

The second argument of SetOverflowFrames is a const nsFrameList*&, so just pass in continuationColumns here.  And continuationColumns could be a const reference, not an object.

>+++ b/layout/generic/nsContainerFrame.cpp
>+nsFrameList
>+nsContainerFrame::StealFramesAfter(nsIFrame* aChild)

This could use the same FrameLinkEnumerator constructor I suggest above...

That said, would it be better to have an nsIFrame API that basically takes a child list name and does ExtractHead on it?  Then we wouldn't need the QIs to nsContainerFrame and such either.  On the other hand we'd need to implement it on all the various frame classes... and this is only used in the bidi code, right?

Should this method be asserting if called on a block, at least for now?

>+  // We didn't find the child in the principal child list.
>+  // Maybe it's on the overflow list?

Do we want to do this?  Would it be hit in the bidi splitting case where this is actually used?  I'd really like either roc or fantasai to look over this part of the code.

>+++ b/layout/generic/nsFirstLetterFrame.cpp
>+      mFrames.RemoveFramesAfter(kid);
>       SetOverflowFrames(aPresContext, nextInFlow);

  SetOverflowFrames(aPresContext, mFrames.RemoveFramesAfter(kid));

would be better, right?

>+        mFrames.RemoveFramesAfter(kid);
>         SetOverflowFrames(aPresContext, nextSib);

And here.

You could even skip the nextSib temporary if you put the nsFrameList in a temporary and check whether it's empty.  A |const nsFrameList&| on the stack seems like the thing to do here.

>+++ b/layout/generic/nsFrameSetFrame.cpp
>+      mFrames.AppendFrame(nsnull, frame);

In the short term this is not great, but since we're about to add an mLastChild to nsFrameList, should be fine.

>+++ b/layout/generic/nsHTMLContainerFrame.h
>+   * @param aNextInFlowResult must be non-null.

I'm not sure what that means.  It's an out parameter, right?  Did you mean to change it to nsIFrame** (which I would support, by the way)?  It doesn't make sense to require the reference to point to non-null at function call time, since this is a pure out param...

>+++ b/layout/generic/nsInlineFrame.cpp
> nsInlineFrame::PushFrames(nsPresContext* aPresContext,
>+  mFrames.RemoveFramesAfter(aPrevSibling);
...
>   SetOverflowFrames(aPresContext, aFromChild);

Similar comments here as in nsFirstLetterFrame.cpp.

>+++ b/layout/generic/nsSimplePageSequence.cpp
>@@ -293,29 +282,29 @@ nsSimplePageSequenceFrame::Reflow(nsPres
>+    } else if (!kidNextInFlow) {

This seems to basically duplicate nsHTMLContainerFrame::CreateNextInFlow.  Should nsSimplePageSequenceFrame just inherit from nsHTMLContainerFrame?  As a followup?

For that matter, I'm not quite sure why we have separate nsHTMLContainerFrame and nsContainerFrame, but that's also fodder for a separate bug.

>+++ b/layout/xul/base/src/nsBoxFrame.cpp

The changes to this file make this whole thing totally worth it.  ;)

Comment 63

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 395373 [details] [diff] [review]
Patch 1, "nsTableRowGroupFrame cleanup"

>+++ b/layout/tables/nsTableRowGroupFrame.cpp
> nsTableRowGroupFrame::GetRowCount()

I would be pretty happy with this becoming |return mFrames.GetLength()| possibly with some asserts about all the frames having the right display type, but that can be a followup bug.  Keeping the behavior the same as part of this change is probably best...

>+  nsIFrame* childFrame = mFrames.FirstChild();
>+  for (; childFrame; childFrame = childFrame->GetNextSibling()) {

Could just move the declaration into the for loop too.  MSVC handles that correctly nowadays.

> PRInt32 nsTableRowGroupFrame::GetStartRowIndex()

Again, this could just nix the loop in favor of:

 if (mFrames.NotEmpty()) {
  // Assert display of mFrames.FirstChild()
  result =
   static_cast<nsTableRowFrame*>(mFrames.FirstChild())->GetRowIndex();
 }

or some such, but again a followup is fine for this.

r=bzbarsky

Comment 64

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 395374 [details] [diff] [review]
Patch 2, "Introduce nsFrameList::mLastChild"

>+++ b/layout/generic/nsBlockFrame.cpp
>+    return mLines.empty() ? nsFrameList::EmptyList()
>+                          : nsFrameList(mLines.front()->mFirstChild,
>+                                        mLines.back()->LastChild());

This is slightly worrying because it makes GetFirstChild() on a block O(N) in the number of kids on the last line.  In general this shouldn't be too bad, I guess...  and once we fix the line list storage to keep track of last kids of lines better it'll be just fine.  Still, keep an eye out for performance issues when landing this part?

>+++ b/layout/generic/nsFrameList.cpp
> nsFrameList::RemoveFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint)
>+    return PR_TRUE;
>+  }
>+  else {

No need for the else after return.  Just outdent the case when aFrame != mFirstChild?

>-  // aFrame was not in the list. 

Probably better to keep that comment.

> nsFrameList::RemoveFramesAfter(nsIFrame* aAfterFrame)
>+  // if (!tail) return EmptyList();  -- worth optimizing this case?

Imo, no.

>+++ b/layout/generic/nsFrameList.h
>- * A class for managing a list of frames.
>+ * A class for managing a singly linked list of frames. Frames are
>+ * linked together through their next-sibling pointer.

The old comment was vague for a reason.  I'd rather not have consumers assuming this is a singly linked list or how the linkage works, especially since we plan on changing it.

>+  void AppendFrames(nsIFrame* aParent, nsIFrame* aFrameList)

Followup bug on eliminating this function signature?

>+  inline Slice AppendFrames(nsIFrame* aParent, nsFrameList& aFrameList);

Is there a reason to not just implement this as:

  InsertFrames(aParent, LastChild(), aFrameList);

?  Less code to maintain....

>+  inline PRBool RemoveFirstChild();

Why inline this?

>   void InsertFrames(nsIFrame* aParent,
>                     nsIFrame* aPrevSibling,
>-                    nsIFrame* aFrameList);
>+                    nsIFrame* aFrameList)

Again, file a bug on eliminating this function signature?

>+  void VerifyList() const;

Why does that need to be public?

>+++ b/layout/generic/nsIFrame.h
>-  nsIFrame* GetFirstChild(nsIAtom* aListName) const {
>+  nsIFrame* GetFirstChild(nsIAtom* aListName) const
>+  {

Please leave the curlies as they were (and similar for GetLastChild and the nsFrameList methods that were implemented directly inside the class decl).

>+  // XXXmats this method should also go away then
>+  nsIFrame* GetLastChild(nsIAtom* aListName) const

Yeah, it was a quick hack.  Since there are only 1 or 2 consumers, want to just nix it in this patch?

>+nsFrameList::AppendFrames(nsIFrame* aParent, nsFrameList& aFrameList)

As I said above, I think this should just call InsertFrames.  I didn't review the logic here.

> nsFrameList::AppendFrame(nsIFrame* aParent, nsIFrame* aFrame)
> {
>   NS_PRECONDITION(aFrame && !aFrame->GetNextSibling(),
>                   "Shouldn't be appending more than one frame");
>-  AppendFrames(aParent, aFrame);

Why this change?  I'd prefer to leave this as it was so we don't have complicated logic duplicated...

>+inline nsFrameList::Slice
>+nsFrameList::InsertFrames(nsIFrame* aParent, nsIFrame* aPrevSibling,

I don't think this should be inlined.  Is there a good reason to inline it?

> nsFrameList::InsertFrame(nsIFrame* aParent,
>                          nsIFrame* aPrevSibling,
>-                         nsIFrame* aNewFrame) {
...
>-  InsertFrames(aParent, aPrevSibling, aNewFrame);

Why not keep the old impl?

>+++ b/layout/xul/base/src/nsBoxFrame.cpp
>-  mFrames.SetFrames(MergeSort(aState, mFrames.FirstChild()));
>+  mFrames = nsFrameList(MergeSort(aState, mFrames.FirstChild()));

Can we make MergeSort take and return frame lists?  Or even just take a frame list and sort it instead of returning a separate sorted list?  Either sliding that under this patch or as a followup bug...

Comment 65

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 395376 [details] [diff] [review]
Patch 3, "fix false positive RemoveFrame asserts"

>+++ b/layout/generic/nsAbsoluteContainingBlock.cpp
>@@ -116,20 +116,18 @@ nsAbsoluteContainingBlock::RemoveFrame(n

Looks like you can make this a void method, right?

>+++ b/layout/generic/nsFrameList.cpp
>+nsFrameList::DestroyFrameIfPresent(nsIFrame* aFrame)

I'd prefer it if this called RemoveFrameIfPresent and then Destroy to reimplementing the traversal and then calling DestroyFrame....

With those two nits, r=bzbarsky

Comment 66

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 395379 [details] [diff] [review]
Patch 5, "Declare nsFrameList(nsIFrame*) explicit"

This looks fine, but how many consumers are left?  Ideally we'd nix this signature completely now that we have the two-frame one.

Comment 67

[Mats Palmgren (inactive)]

Attachment: Patch 0, v2, "Eliminate some SetNextSibling calls"

(In reply to comment #62)
> >+    nsContainerFrame* container = do_QueryFrame(parent);
> >+    nsFrameList tail = container->StealFramesAfter(frame);
> 
> Are we guaranteed this QI will succeed?

Yes. The above line is under "if (IsBidiSplittable(parent))" which tests
for IsFrameOfType(nsIFrame::eBidiInlineContainer) which is only implemented
by nsInlineFrame and nsFirstLetterFrame, both inherit nsContainerFrame.

> >+    nsFrameList temp(newParent);
> 
> newParent is guaranteed to not have any following siblings here, right?

Yes, I don't think we should allow CreateContinuingFrame to return siblings.
I've added a POSTCONDITION for that.

>  If so, I'd prefer that we introduce a two-argument nsFrameList constructor

Fixed

> >+++ b/layout/base/nsCSSFrameConstructor.cpp
> If you do the continuation stuff before the AddChild call and use the
> aFrameItems.lastChild for it, you don't need the lastCol local.

Fixed

> nsCSSFrameConstructor::WipeContainingBlock:
> This should probably become either: ...
> prevSibling = parentPrevCont->GetLastChild(nsnull);

Fixed


> >+++ b/layout/generic/nsColumnSetFrame.cpp
> Would it make sense to reuse existing code for this by adding a constructor for
> FrameLinkEnumerator that takes a const nsFrameList& and the frame before the
> link and then use ExtractTail here?

That would be less readable IMO:
        nsFrameList::FrameLinkEnumerator iter(mFrames, child);
        const nsFrameList& continuationColumns = mFrames.ExtractTail(iter);


> >+          SetOverflowFrames(PresContext(), continuationColumns.FirstChild());
> 
> The second argument of SetOverflowFrames is a const nsFrameList*&, so just pass
> in continuationColumns here.  And continuationColumns could be a const
> reference, not an object.

Fixed


> >+++ b/layout/generic/nsContainerFrame.cpp
> >+nsFrameList
> >+nsContainerFrame::StealFramesAfter(nsIFrame* aChild)
> 
> This could use the same FrameLinkEnumerator constructor I suggest above...

If we introduce said ctor, I strongly feel that it should assert that the
given prev-frame is either null or a frame on the list.
So we could only partly use it here.

> That said, would it be better to have an nsIFrame API that basically takes a
> child list name and does ExtractHead on it?

I considered this, but as you said, the only use right now would be
the one place in the bidi code.  Let's wait and see.

> Should this method be asserting if called on a block, at least for now?

Ok, fixed.

> >+  // We didn't find the child in the principal child list.
> >+  // Maybe it's on the overflow list?
> 
> Do we want to do this?  Would it be hit in the bidi splitting case where this
> is actually used?  I'd really like either roc or fantasai to look over this
> part of the code.

I don't think we should change it as part of this bug.


> >+++ b/layout/generic/nsFirstLetterFrame.cpp
> You could even skip the nextSib temporary if you put the nsFrameList in a
> temporary and check whether it's empty.  A |const nsFrameList&| on the stack
> seems like the thing to do here.

Fixed, in patch 5.


> >+++ b/layout/generic/nsHTMLContainerFrame.h
> >+   * @param aNextInFlowResult must be non-null.
> 
> I'm not sure what that means.

Removed "must be non-null".  I probably had the idea to change it to
nsIFrame** at one point, but later changed my mind, thinking that
CreateNextInFlow should just go away.

> >+++ b/layout/generic/nsInlineFrame.cpp
> Similar comments here as in nsFirstLetterFrame.cpp.

Fixed

Comment 68

[Mats Palmgren (inactive)]

Attachment: Patch 1, v2, "nsTableRowGroupFrame cleanup"

(In reply to comment #63)
> >+  nsIFrame* childFrame = mFrames.FirstChild();
> >+  for (; childFrame; childFrame = childFrame->GetNextSibling()) {
> 
> Could just move the declaration into the for loop too.

Fixed

Comment 69

[Mats Palmgren (inactive)]

Attachment: Patch 2, v2, "Introduce nsFrameList::mLastChild"

(In reply to comment #64)
> >+++ b/layout/generic/nsFrameList.cpp
> > nsFrameList::RemoveFrame(nsIFrame* aFrame, nsIFrame* aPrevSiblingHint)
> >+    return PR_TRUE;
> >+  }
> >+  else {
> 
> No need for the else after return.  Just outdent the case when aFrame !=
> mFirstChild?
> 
> >-  // aFrame was not in the list. 
> 
> Probably better to keep that comment.

Ok, but the final version of this method is fine IMO.

> >+++ b/layout/generic/nsFrameList.h
> >- * A class for managing a list of frames.
> >+ * A class for managing a singly linked list of frames. Frames are
> >+ * linked together through their next-sibling pointer.
> 
> The old comment was vague for a reason.

Fixed, I left the comment unchanged.

> >+  inline Slice AppendFrames(nsIFrame* aParent, nsFrameList& aFrameList);
> 
> Is there a reason to not just implement this as:
> 
>   InsertFrames(aParent, LastChild(), aFrameList);

Ok, I changed it to your suggestion.

> 
> >+  inline PRBool RemoveFirstChild();
> 
> Why inline this?

Not sure. I changed it back to the old version.

> >+  void VerifyList() const;
> 
> Why does that need to be public?

No need. Made it protected.


> >+++ b/layout/generic/nsIFrame.h
> Please leave the curlies as they were (and similar for GetLastChild and the
> nsFrameList methods that were implemented directly inside the class decl).

Fixed.  (Could we have a coding standard for this please?)

> > nsFrameList::AppendFrame(nsIFrame* aParent, nsIFrame* aFrame)
> Why this change?  I'd prefer to leave this as it was so we don't have
> complicated logic duplicated...

Ok, left it as is.

> >+inline nsFrameList::Slice
> >+nsFrameList::InsertFrames(nsIFrame* aParent, nsIFrame* aPrevSibling,
> 
> I don't think this should be inlined.  Is there a good reason to inline it?

I mistakenly thought it had to be in nsIFrame.h for build reasons.
I moved all the nsFrameList methods there to nsFrameList.h/cpp.

> > nsFrameList::InsertFrame(nsIFrame* aParent,
> Why not keep the old impl?

Ok, kept the old impl.  IIRC, for the single frame Insert/Append
I wanted to avoid creating a throw-away Slice and Clear() of the
temp list.

> Can we make MergeSort take and return frame lists?

Will file a separate bug for that.

Comment 70

[Mats Palmgren (inactive)]

Attachment: Patch 3, v2, "fix false positive RemoveFrame asserts"

(In reply to comment #65)
> (From update of attachment 395376 [details] [diff] [review])
> >+++ b/layout/generic/nsAbsoluteContainingBlock.cpp
> >@@ -116,20 +116,18 @@ nsAbsoluteContainingBlock::RemoveFrame(n
> 
> Looks like you can make this a void method, right?

Yes, fixed.

> >+++ b/layout/generic/nsFrameList.cpp
> >+nsFrameList::DestroyFrameIfPresent(nsIFrame* aFrame)
> 
> I'd prefer it if this called RemoveFrameIfPresent and then Destroy to
> reimplementing the traversal and then calling DestroyFrame....

Fixed

Comment 71

[Mats Palmgren (inactive)]

Attachment: Patch 5, v2, "Remove nsFrameList(nsIFrame*)"

(In reply to comment #66)
> (From update of attachment 395379 [details] [diff] [review])
> This looks fine, but how many consumers are left?  Ideally we'd nix this
> signature completely now that we have the two-frame one.

Quite a few, but the changes were simple and led to nice improvements.

Comment 72

[Mats Palmgren (inactive)]

Attachment: Summary, v2, the above patches as one.

Comment 73

[Boris Zbarsky [:bzbarsky]]

> That would be less readable IMO:

I'm not sure, but it would also have smaller API mindprint...

> So we could only partly use it here.

Are there cases where aChild isn't in fact in the list?

> I don't think we should change it as part of this bug.

I'm not sure what you mean by change.  The only consumer is the bidi code.  Is that ever working with things on the overflow list?  If not, there's no point adding overflow list stuff here.  roc or fantasai should still look over this change (and ideally over the nsFrameList API changes).

> Ok, but the final version of this method is fine IMO.

You mean with the else after return?  It's harder to read than outdenting, especially since the other branch doesn't always return.

Looking at the rest now.

Comment 74

[Mats Palmgren (inactive)]

(In reply to comment #73)
> Are there cases where aChild isn't in fact in the list?

Don't know for sure.

> > I don't think we should change it as part of this bug.
> 
> I'm not sure what you mean by change.  The only consumer is the bidi code.  Is
> that ever working with things on the overflow list?  If not, there's no point
> adding overflow list stuff here.

I modeled it after StealFrame, which checks both the principal and
overflow lists.  The old (SetNextSibling) code is list-agnostic so
I wanted to be on the safe side.

> > Ok, but the final version of this method is fine IMO.
> 
> You mean with the else after return?

I change nsFrameList::RemoveFrame in a later patch as well,
making it void, so there is no return.  And it has
NS_PRECONDITION(ContainsFrame(aFrame), "wrong list")
so the removed comment doesn't make sense.
https://bugzilla.mozilla.org/attachment.cgi?id=398806&action=diff#a/layout/generic/nsFrameList.cpp_sec2

Comment 75

[Boris Zbarsky [:bzbarsky]]

> I modeled it after StealFrame

Right; StealFrame is explicitly called in cases when the next-in-flow might have frames on its overflow list.  Again, it's not clear to me that this can be the case with bidi code...

> I change nsFrameList::RemoveFrame in a later patch as well,
> making it void

Oh, I see what you meant by final.  OK.

Bugzilla interdiff is lying to me (silently) by leaving stuff out of your patches.  I really need to get to sleep now, but I'll look at this first thing on Tuesday (Monday being a holiday).  If it's not too hard to make interdiffs from the patches I reviewed to the new ones, that would help a lot; if it would be too much trouble I can deal; it'll just take more time.

Comment 76

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 0

Comment 77

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 1

Comment 78

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 2

Comment 79

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 3

Comment 80

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 4

Comment 81

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 5

Comment 82

[Boris Zbarsky [:bzbarsky]]

Interdiffs in unified format, even? :(

Comment 83

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 398801 [details] [diff] [review]
Patch 0, v2, "Eliminate some SetNextSibling calls"

r=bzbarsky.  Please do file a followup bug on that nsSimplePageSequenceFrame thing I mention in comment 62.

Comment 84

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 398802 [details] [diff] [review]
Patch 1, v2, "nsTableRowGroupFrame cleanup"

Again, please don't forget the followups from comment 63.

Comment 85

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 0 (unidiff)

Comment 86

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 1 (unidiff)

Comment 87

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 2 (unidiff)

Comment 88

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 3 (unidiff)

Comment 89

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 4 (unidiff)

Comment 90

[Mats Palmgren (inactive)]

Attachment: Interdiff, Patch 5 (unidiff)

Comment 91

[Mats Palmgren (inactive)]

Filed bug 515530 and bug 515531 to followup comment 62
and bug 515534 to followup comment 63.

Comment 92

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 398803 [details] [diff] [review]
Patch 2, v2, "Introduce nsFrameList::mLastChild"

Let's get a bug filed on the MergeSort thing.

r=bzbarsky.

Comment 93

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 398805 [details] [diff] [review]
Patch 5, v2, "Remove nsFrameList(nsIFrame*)"

> IsFrameInCurrentLine(nsBlockInFlowLineIterator* aLineIter,
>+  return nsFrameList(startFrame, nsLayoutUtils::GetLastSibling(startFrame))
>+           .ContainsFrameBefore(aFrame, endFrame);

This is suboptimal, since it'll end up walking all the kids of the block after startFrame while constructing the framelist...  This could easily make what used to be a O(N) operation (if we do this for all the lines) into an O(N^2) operation.

We should perhaps move ContainsFrameBefore onto Slice and create a Slice() here, since that's what we really want; the implementation could be shared with the nsFrameList one by having the latter simply do Slice(*this).ContainsFrameBefore().  The other option is to reimplement it here, I guess...

>+++ b/layout/generic/nsBlockFrame.cpp
>@@ -522,26 +522,30 @@ nsBlockFrame::GetChildList(nsIAtom* aLis
>+             ? nsFrameList(mBullet, nsLayoutUtils::GetLastSibling(mBullet))

Pretty sure this could just be nsFrameList(mBullet, mBullet); mBullet should never have any next siblings for outside bullets...

> nsBlockFrame::GetOverflowOutOfFlows() const
>+  return nsFrameList(result, nsLayoutUtils::GetLastSibling(result));

Maybe file a followup bug to store the overflow out of flows as an nsFrameList, unless we're guaranteed that there aren't many of them....  And maybe even then.

>+++ b/layout/generic/nsFrameList.cpp
>+nsFrameList::AppendFrames(nsIFrame* aParent, nsIFrame* aFrameList)

File a bug on eliminating this signature?  There can't be that many consumers left!

>+nsFrameList::InsertFrames(nsIFrame* aParent,
>+                          nsIFrame* aPrevSibling,
>+                          nsIFrame* aFrameList)

And this one too.

Some of the "nsAbsoluteContainingBlock::RemoveFrames is now void" changes look like they should be part of patch 3.  Does patch 3 not build without this applied on top? Might be good to either fix that before pushing or qfold them all together so we don't have non-building changesets in m-c.

r=bzbarsky with the above nits (esp. the bidi one) fixed.  Thanks a ton for getting this done!

Comment 94

[Boris Zbarsky [:bzbarsky]]

> Let's get a bug filed on the MergeSort thing.

Filed bug 516783.

Comment 95

[Mats Palmgren (inactive)]

Filed bug 516974, bug 516976 and bug 516977 for the enhancements in comment 93.

Comment 96

[Mats Palmgren (inactive)]

Attachment: Patch 0, v3, "Eliminate some SetNextSibling calls"

Macro name change
s/NS_DECLARE_FRAME_ACCESSOR/NS_DECL_QUERYFRAME_TARGET/g
due to frame poisoning landing.

Comment 97

[Mats Palmgren (inactive)]

Attachment: Patch 3, v3, "fix false positive RemoveFrame asserts"

Moved the "nsAbsoluteContainingBlock::RemoveFrames is now void"
changes from Patch 5 here. No other changes.

Comment 98

[Mats Palmgren (inactive)]

Attachment: Patch 5, v3, "Remove nsFrameList(nsIFrame*)"

> This is suboptimal, since it'll end up walking all the kids

Good catch.  I fixed it by iterating the siblings locally rather
than using nsFrameList.  The problem with creating a Slice is that
it requires a nsFrameList, and nsFrameList(aFrame, endFrame) will
assert unless endFrame is the last sibling.  (I think we can change
it to use a Slice when block frames have a child list we can use.)

> Pretty sure this could just be nsFrameList(mBullet, mBullet)

Ok, fixed.

I moved the "nsAbsoluteContainingBlock::RemoveFrames is now void" changes
to Patch 3 as you suggested.  All patches now builds, and should also pass
regression tests separately although I haven't verified this on TryServer.

Comment 99

[Mats Palmgren (inactive)]

Attachment: Summary, v3, the above patches as one.

Comment 100

[Mats Palmgren (inactive)]

Attachment: Interdiff v2 to v3, Patch 0 (unidiff)

Comment 101

[Mats Palmgren (inactive)]

Attachment: Interdiff v2 to v3, Patch 3 (unidiff)

Comment 102

[Mats Palmgren (inactive)]

Attachment: Interdiff v2 to v3, Patch 5 (unidiff)

Comment 103

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 401028 [details] [diff] [review]
Patch 5, v3, "Remove nsFrameList(nsIFrame*)"

Looks good.

Comment 104

[Mats Palmgren (inactive)]

http://hg.mozilla.org/mozilla-central/rev/b90618f4d706
http://hg.mozilla.org/mozilla-central/rev/ffb5ea9c48c7
http://hg.mozilla.org/mozilla-central/rev/70ec90925933
http://hg.mozilla.org/mozilla-central/rev/6a77f2399246
http://hg.mozilla.org/mozilla-central/rev/17874c9d2249
http://hg.mozilla.org/mozilla-central/rev/4b8efcb179b8

Comment 105

[Timothy Nikkel (:tnikkel)]

The comment above RemoveFrame in nsFrameList.h got trampled on by http://hg.mozilla.org/mozilla-central/rev/6a77f2399246 (part 3).

Comment 106

[Mats Palmgren (inactive)]

Oops.  Fortunately Boris discovered it too and is fixing it in bug 512336.