See testcase which crashes in current trunk build on reload. It doesn't crash in a 2008-01-09 build, but does crash in a 2008-01-10 build: http://bonsai.mozilla.org/cvsquery.cgi?treeid=default&module=all&branch=HEAD&branchtype=match&dir=&file=&filetype=match&who=&whotype=match&sortby=Date&hours=2&date=explicit&mindate=2008-01-09+15&maxdate=2008-01-10+07&cvsroot=%2Fcvsroot http://crash-stats.mozilla.com/report/index/17f5d623-179f-11dd-9990-001cc45a2ce4?p=1 0 @0x308e349 Stack from debug build: dddddddd() > gklayout.dll!nsCOMPtr<nsPresContext>::nsCOMPtr<nsPresContext>(nsPresContext * aRawPtr=0x0551d060) Line 628 C++ gklayout.dll!nsStyleContext::Destroy() Line 926 C++ gklayout.dll!nsStyleContext::Release() Line 93 C++ gklayout.dll!nsStyleContext::~nsStyleContext() Line 108 C++ gklayout.dll!nsStyleContext::`scalar deleting destructor'() + 0xf bytes C++ gklayout.dll!nsStyleContext::Destroy() Line 930 C++ gklayout.dll!nsStyleContext::Release() Line 93 C++ gklayout.dll!nsFrame::~nsFrame() Line 351 C++ gklayout.dll!nsSplittableFrame::~nsSplittableFrame() + 0xf bytes C++ gklayout.dll!nsContainerFrame::~nsContainerFrame() Line 82 + 0x13 bytes C++ gklayout.dll!nsHTMLContainerFrame::~nsHTMLContainerFrame() + 0xf bytes C++ gklayout.dll!nsBlockFrame::~nsBlockFrame() Line 282 + 0x1e bytes C++ gklayout.dll!nsBlockFrame::`scalar deleting destructor'() + 0xf bytes C++ gklayout.dll!nsFrame::Destroy() Line 510 + 0x24 bytes C++ gklayout.dll!nsSplittableFrame::Destroy() Line 74 C++ gklayout.dll!nsContainerFrame::Destroy() Line 300 C++ gklayout.dll!nsBlockFrame::Destroy() Line 314 C++ gklayout.dll!nsFrameList::DestroyFrames() Line 68 C++ gklayout.dll!nsContainerFrame::Destroy() Line 260 C++ gklayout.dll!nsBoxFrame::Destroy() Line 963 C++ gklayout.dll!nsDocElementBoxFrame::Destroy() Line 110 C++ gklayout.dll!nsFrameList::DestroyFrames() Line 68 C++ gklayout.dll!nsContainerFrame::Destroy() Line 260 C++ gklayout.dll!nsBoxFrame::Destroy() Line 963 C++ gklayout.dll!nsFrameList::DestroyFrames() Line 68 C++ gklayout.dll!nsContainerFrame::Destroy() Line 260 C++ gklayout.dll!ViewportFrame::Destroy() Line 69 C++ gklayout.dll!nsFrameManager::Destroy() Line 284 C++ gklayout.dll!PresShell::Destroy() Line 1708 C++ gklayout.dll!DocumentViewerImpl::Destroy() Line 1526 C++ gklayout.dll!DocumentViewerImpl::Show() Line 1848 C++ gklayout.dll!nsPresContext::EnsureVisible(int aUnsuppressFocus=0) Line 1461 C++ gklayout.dll!PresShell::UnsuppressAndInvalidate() Line 4316 + 0xd bytes C++ gklayout.dll!PresShell::UnsuppressPainting() Line 4365 C++ gklayout.dll!DocumentViewerImpl::LoadComplete(unsigned int aStatus=0) Line 1015 C++ docshell.dll!nsDocShell::EndPageLoad(nsIWebProgress * aProgress=0x053b165c, nsIChannel * aChannel=0x0510d830, unsigned int aStatus=0) Line 5069 C++ docshell.dll!nsWebShell::EndPageLoad(nsIWebProgress * aProgress=0x053b165c, nsIChannel * channel=0x0510d830, unsigned int aStatus=0) Line 1016 C++ docshell.dll!nsDocShell::OnStateChange(nsIWebProgress * aProgress=0x053b165c, nsIRequest * aRequest=0x0510d830, unsigned int aStateFlags=131088, unsigned int aStatus=0) Line 4974 C++ docshell.dll!nsDocLoader::FireOnStateChange(nsIWebProgress * aProgress=0x053b165c, nsIRequest * aRequest=0x0510d830, int aStateFlags=131088, unsigned int aStatus=0) Line 1236 C++ docshell.dll!nsDocLoader::doStopDocumentLoad(nsIRequest * request=0x0510d830, unsigned int aStatus=0) Line 869 C++ docshell.dll!nsDocLoader::DocLoaderIsEmpty() Line 765 C++ docshell.dll!nsDocLoader::OnStopRequest(nsIRequest * aRequest=0x05553698, nsISupports * aCtxt=0x00000000, unsigned int aStatus=0) Line 682 C++ necko.dll!nsLoadGroup::RemoveRequest(nsIRequest * request=0x05553698, nsISupports * ctxt=0x00000000, unsigned int aStatus=0) Line 688 + 0x2e bytes C++ gklayout.dll!nsDocument::DoUnblockOnload() Line 5731 C++ gklayout.dll!nsDocument::UnblockOnload(int aFireSync=1) Line 5679 C++ gklayout.dll!nsBindingManager::DoProcessAttachedQueue() Line 963 C++ gklayout.dll!nsRunnableMethod<nsBindingManager>::Run() Line 262 C++ xpcom_core.dll!nsThread::ProcessNextEvent(int mayWait=1, int * result=0x0012f848) Line 511 C++ xpcom_core.dll!NS_ProcessNextEvent_P(nsIThread * thread=0x012b4098, int mayWait=1) Line 227 + 0x16 bytes C++ gkwidget.dll!nsBaseAppShell::Run() Line 170 + 0xc bytes C++ tkitcmps.dll!nsAppStartup::Run() Line 181 + 0x1c bytes C++ xul.dll!XRE_main(int argc=1, char * * argv=0x003ff7f0, const nsXREAppData * aAppData=0x003ffe98) Line 3170 + 0x25 bytes C++ firefox.exe!NS_internal_main(int argc=1, char * * argv=0x003ff7f0) Line 158 + 0x12 bytes C++ firefox.exe!wmain(int argc=1, unsigned short * * argv=0x003fa080) Line 87 + 0xd bytes C++ firefox.exe!__tmainCRTStartup() Line 583 + 0x19 bytes C firefox.exe!wmainCRTStartup() Line 403 C kernel32.dll!_BaseProcessStart@4() + 0x23 bytes

I got a slightly different regression range: 2008-01-08-04 -- 2008-01-09-04 http://bonsai.mozilla.org/cvsquery.cgi?treeid=default&module=all&branch=HEAD&branchtype=match&dir=&file=&filetype=match&who=&whotype=match&sortby=Date&hours=2&date=explicit&mindate=2008-01-08+03%3A00&maxdate=2008-01-09+05%3A00&cvsroot=%2Fcvsroot It looks like bug 355548 uncovered an existing bug in reresolving stylecontexts for special frames that was reordered by a -moz-box-ordinal-group. I have a fix in my tree... more soon...

The block-in-inline situation makes us create three special frames but the -moz-box-ordinal-group isn't propagated to all three. Then nsBoxFrame::CheckBoxOrder() tries to sort the child list which reorders the special frames (see the first two frame dumps). Then nsCSSFrameConstructor::RebuildAllStyleData() is called: http://bonsai.mozilla.org/cvsblame.cgi?file=/mozilla/layout/base/nsCSSFrameConstructor.cpp&rev=1.1473&mark=13408,13421,13430#13394 Since the style structs are deleted by EndConstruct it's essential that ComputeStyleChangeFor() does not leave a reference to an old struct behind, but since the special frames were reordered we do them in the wrong order so we leave a style struct parent intact which is later deleted.

Ok, so then I added -moz-box-ordinal-group:inherit in ua.css to make the special frames have the same ordinal, but it turns out the current sorting algorithm (Selection sort) isn't stable, i.e. it doesn't maintain the relative order of frames with the same ordinal.

Patch overview: 1. add -moz-box-ordinal-group:inherit so that special frames have the same ordinal 2. make CheckBoxOrder() use a stable sorting alg. (I chose Strand sort) 3. to implement that it was convenient to use "struct nsFrameItems" from nsCSSFrameConstructor.cpp, so I moved it to nsFrameList.h. Note two minor changes I did: 1) the ctor assumes the frame arg has a null next-sibling: http://bonsai.mozilla.org/cvsblame.cgi?file=/mozilla/layout/base/nsCSSFrameConstructor.cpp&rev=1.1473&root=/cvsroot&mark=752-755,785#733 I removed that limitation and made it initialize 'lastChild' to the last frame in the list as is the invariant for this struct. 2) I changed "!childList || (aAfter && !aAfter->GetNextSibling())" to "!childList || aAfter == lastChild" which is the same thing if aAfter is on the list (implicit precondition for this method). No other changes, except the methods I added: RemoveFirstChild(), LastChild(),FirstChild(),IsEmpty(). Note: there is also a -moz-mathml-anonymous-block in mathml.css but that can't end up in nsBoxFrame::CheckBoxOrder(), right?

I'd actually prefer a recursive mergesort here. It's still stable, but it's O(n log n) whereas strand sort is O(n^2) in the worst case. Also, recursive mergesort on singly-linked lists is really simple, probably simpler than what you have here.

Mats, any chance of a new patch?

Recursive mergesort does not fit linked lists very well since you need to repeatedly iterate the list to split it in half, so I wrote a bottom-up version instead.

Comment on attachment 329953 [details] [diff] [review] Patch rev. 2 Make the helper functions static. + result = result ? SortedMerge(aState, *left, result) : *left; Shouldn't the parameters be in the order result, *left to ensure stability? I think it would probably be a lot simpler to just use the recursive sort --- look at Sort() in nsDisplayList.cpp --- and I don't think we care about constant-factor performance here. If we did, I think the version in nsDisplayList would still win since it has a nice already-sorted check which is going to make the common case (no box-ordinals set) O(N).

What's the status here: we've got r/sr on a patch but it hasn't landed. Do we need a new patch? just need to land this one?

(In reply to comment #9) > Make the helper functions static. Will do. > + result = result ? SortedMerge(aState, *left, result) : *left; > > Shouldn't the parameters be in the order result, *left to ensure stability? No, sorted[0] is the last result, ie. items from later in the list. FYI, I wrote this code outside of Gecko in a test jig where I could measure performance and verify correctness (including stability) with input lists of various length, ordinal spread etc. > nsDisplayList would still win since it has a nice already-sorted check You might think so, but... I gathered some statistics on the nsDisplayList input lists (loading all Alexa Global Top 100 urls): ~90% of all calls take the "aCount < 2" early return. The remaining lists that we actually sort: the average length is ~7.3 ~70% are already fully ordered Even with this high degree of sorted input the performance of a recursive sort (with already-sorted check) is slightly slower than the attached bottom-up iterative sort. Statistics on the nsBoxFrame::CheckBoxOrder input lists (just clicking around in the UI): ~70% of all calls take the "aCount < 2" early return. For the remaining lists: the average length is ~3.3 >99.9% are already fully ordered (and nearly all of those due to ordinal == DEFAULT_ORDINAL_GROUP) Clearly, pruning already sorted lists will pay off in this case and the patch does that.

(In reply to comment #10) I'll land this one when the tree opens post beta2, with roc's nit about static.

(In reply to comment #12) > (In reply to comment #10) > I'll land this one when the tree opens post beta2, with roc's nit about static. If you add it to https://wiki.mozilla.org/MeteredCheckins according to the rules described there, the sheriff will even land it for you (although I think there's only about 12 hours of that left).

Made the helper functions static as suggested: http://hg.mozilla.org/mozilla-central/rev/f7c410f03d0e I'm holding the crashtest until Firefox 3.0.x is fixed. -> FIXED

Now also includes the 2nd testcase from bug 467080.

(In reply to comment #14) > I'm holding the crashtest until Firefox 3.0.x is fixed. > > -> FIXED This does not appear to have landed for 3.1, just 3.2. ugh, it's going to be murder trying to keep track of which "blocking1.9.1+" things need to have "fixed1.9.1" and which are OK without.

> This does not appear to have landed for 3.1, just 3.2. Correct. I assume the standard two day minimum baking period applies (and explicit approval for 1.9.1 is required anyway).

Verified fixed, using: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2a1pre) Gecko/20081208 Minefield/3.2a1pre

This bug is blocking1.9.1+, so it doesn't need explicit approval to land on the 1.9.1 branch.

Thanks Boris, I see now that I misread the 2nd bullet of 1.9.1 rules at https://wiki.mozilla.org/TreeStatus

I pushed http://hg.mozilla.org/releases/mozilla-1.9.1/rev/f3f47273e026 to fix this on 1.9.1.

Comment on attachment 329953 [details] [diff] [review] Patch rev. 2 Low risk. No performance impact.

Comment on attachment 329953 [details] [diff] [review] Patch rev. 2 Approved for 1.9.0.6, a=dveditz for release-drivers

I see now that the last declaration became redundant between rev. 1 and 2 of the patch above, so it can be removed: http://mxr.mozilla.org/mozilla-central/source/layout/style/ua.css?mark=126,133,196,206#125

This is the 1.9.0 version of the patch. It's identical except for layout/style/ua.css where the *|*::-moz-anonymous-block, *|*::-moz-anonymous-positioned-block { rule isn't present so I'm adding it here to make it as close to trunk/1.9.1 as possible.

Comment on attachment 353401 [details] [diff] [review] Additional patch, rev. 1 http://hg.mozilla.org/mozilla-central/rev/1a08d472ccf5 http://hg.mozilla.org/releases/mozilla-1.9.1/rev/f9aa72fb3a6d

Comment on attachment 353403 [details] [diff] [review] 1.9.0 patch Checked in on CVS trunk for 1.9.0.6: mozilla/layout/style/ua.css 3.235 mozilla/layout/xul/base/src/nsBoxFrame.cpp 1.351

1.9 regression. probably not for 1.8 branches

Verified for 1.9.0.6 with Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.0.6pre) Gecko/2009010504 GranParadiso/3.0.6pre.

Verified fix on Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10.5; en-US; rv:1.9.1b3pre) Gecko/20090130 Shiretoko/3.1b3pre Ubiquity/0.1.5