We currently recover vertical margin state in an incremental reflow in a very inefficient way -- we walk the whole list of frames and keep clobbering the margin everytime one of the frames has nonempty contents. Not only does the current stuff often give the wrong answer (see all the [MARGIN-C] bugs) but it's slow. I think the solution to this should be roughly the following: * make the line list doubly linked (perhaps with XOR?) * rewrite collapsing margin code to fix at least some of the [MARGIN-C] bugs and recover the vertical margins by walking backwards

The above patch is work in progress to fix this bug, bug 61962, and bug 50142.

Since I posted that patch, I fixed a few typos in it and then discovered that the vertical margin code in nsLineLayout and nsLineBox is vestigial -- nothing uses it. So it shouldn't have surprised me that it didn't work when I tried to use it, since the numbers it had are often wrong and no existing code noticed. The unused code has been ripped out of my tree...

This won't make 0.9.3.

Sun's forte gives this error with patch: "layout/html/base/src/nsBlockFrame.cpp", line 1927: Error: Non-const function nsFusedLinkedList<nsLineBox>::iterator::operator nsLineBox*() called for const object. Line 1927 is: if (aLine == aLineEnd) {

[17:16:49] <imoT> dbaron: your patch chops over half of from pages like in bug #72885 [17:17:51] <imoT> dbaron: but it doesnt help much for long <pre> pages

Things that still need to be done: * finish the code for pulling out the appropriate top vertical margin that's needed when beginning an incremental reflow targeted at C in, where A, B, and C are all blocks whose margins can collapse together: <A/> <B><C/></B> * rewrite the code in ReflowDirtyLines that handled incremental reflow when printing (and also add DrainOverflowLines to a style changed reflow) -- This code is used now due to the way our form controls are messed up and might be useful in the future for columns

I did the above (not yet tested, though), and I also changed some of my ugly hacks to give lines a second dirty bit (could be cleaned up a little more still). I still need to figure out why multi-page printing is broken (perhaps something I messed up with overflow lines handling), figure out why I'm having some {inc} float problems on http://www.nytimes.com/ articles (probably something funky with nsIntervalMap use -- perhaps the old code was using the offsets totally wrong and I'm seeing the problems now, like waterson mentioned once), and do a lot more testing.

I need to work on fixing the testcase attachment 13792 [details] on bug 48138.

It actually didn't fix the problem with http://www.nytimes.com/ articles. And I've seen view-movement problems again -- we probably need another bug to get the issue of who repositions views sorted out.

I was able to remove the code that repositions views even if it was sliding the line by 0 distance (i.e, add a 0-check before calling SlideLine) after pulling the fix for bug 55086 and making an almost-identical change to nsContainerFrame::ReflowChild.

The printing bug I've been searching for was an = vs. == typo causing me to clobber aState.mCurrentLine.

I uploaded this jprof for two reasons - one because it shows quite directly the cost of the current singly-linked nsLineBox implementation (Check the flat hits following #1), and two because it also gives a pretty detailed look at loading large (fairly flat) HTML docs with lots of links. Note also that 29% of the direct hits were in IndexOf() from GetPrimaryFrameFor(), which is another bug: bug 77114 I may go point some other bugs at this attachment as well for data.

attachment 49635 [details] demonstrates a bug that shows up on articles at http://www.nytimes.com/ (the first line doesn't wrap around the floater on the incremental reflow triggered by the loading of the "W" image). I understand exactly what's causing this bug, but it will require a significant amount of refactoring (or copying of code) to fix it. In particular, it requires the "emptiness" logic to perfectly predict whether nsLineLayout::VerticalAlignFrames will set the mZeroEffectiveSpanBox flag and from that figure out whether a line will be empty. I think the correct way to fix this is by adding the following method to nsIFrame: /** * Determine whether the frame is logically empty, i.e., whether the layout * would be the same whether or not the frame is present. */ IsEmpty(nsCompatability aQuirkMode); /* maybe needs nsIPresContext* aPresContext too?? */ This would require some significant refactoring of the nsLineLayout code so that the rules for emptiness would be maintained in one place. The bug happens because the new block code needs to skip *through* empty lines when doing its backwards-recovery of vertical margins. The new emptiness code incorrectly determines that the NYT_LINKS_ONSITE inline element is not empty because of the two bits of whitespace within it. This whitespace does make it, and thus the line containing it, non-empty in strict mode but empty in quirks mode. Therefore the margin recovery doesn't skip all the way up to the bigger bottom-margin of the div (an H5 in the original), and the text is placed too high and therefore partially intersects the float. (The text intersects the float since the code that wraps text around floats can make the assumption that no float already placed will be below the top of the current line -- an assumption that is generally valid but really isn't completely valid and is the cause of bug 41412.) So what I'm saying here is that I think this regression isn't bad enough to block landing of the changes, although I'd want to fix it before the next milestone. However, there could be other issues -- I'm going to try running the block regression tests soon. (I may even figure out how to set up a harness for downloading and running suites from the net, even though I still have a copy of buster's old net tests that can't be checked in.)

To clarify, there are two bugs described in my comment above: * first, the regression caused by the difference in emptiness tests that causes an incremental reflow bug (the incremental reflow triggered by the loading of the "W" image) that causes the paragraph to shift up a small amount because it isn't including the collapsed bottom margin from the DIV/H5 * second, the floater bug (bug 41412 / bug 25888) that shows up in this additional case where it did not before because of the vertical margin bug

The only problem that showed up on the block regression tests that I haven't fixed yet relates to incremental loading of the first floating image in http://www.editions-eyrolles.com/livres/glazman/tests/vfm/vfm11.htm . I think I need to make the nsIntervalMap owned by the space manager, or something like that, so that damage from floats inside a block can be propagated outside of the block. (Maybe there's a simpler solution, but the space manager already maintains a transformation, so one part is already done for me.)

Actually, the refactoring that I thought was possible between nsLineLayout an nsIFrame::IsEmpty is not possible, since nsLineLayout cares whether a frame is empty, excluding its children. However, putting IsEmpty on nsIFrame was an easier way to do what I was doing originally and I think there are a number of other places that should be using it.

However, I'm seeing some view positioning problems again on the bugzilla query page (with the listboxes) since waterson undid / redid some of his view positioning changes. I also probably still need to untemplatize my list class for the line list. I also need to run the block regression tests on the bits I wrote in the past hour. :-)

Attachment 53168 [details] (in bug 48138) isn't fixed yet.

Er, actually, it is fixed. So I'm not sure why I'm still seeing regression test errors on Daniel's vfm11.htm

(Although nsCList.h in that patch isn't ready yet -- Mac has problems, as does gcc 2.7.2.3, which I think we don't support anymore.)

dbaron walked me through these changes for about an hour and a half; there were a few nits he's going to pick, but r= or sr=waterson.

Comment on attachment 53846 [details] [diff] [review] complete patch with nsCList untemplatized and iterators un-nested (zj) sr=waterson

Any perf figures? Did all the effort pay off?

I've been trying to get reproducable perf figures. For normal-sized large pages (like LXR pages), it's hard to find anything reproducable, since the improvement is within the (large) standard deviation, although I think there is a noticeable improvement if I did enough tests. However, I just did a test with 100,000 lines of: <p>This is a paragraph.</p> and the time was 5:54 without my changes and 4:08 with my changes (one run -- I'll try to see if it's reproducable).

Some hackery that I did in bug 56854 indicates that this ought to lead to significant speedup, especially on slower machines (see my comments in that bug dated 2001-04-24 22:06).

excellent! can't wait to see the next page-load results. :-) thanks guys!!

Hey, not so fast Cathleen, it has to actually be checked in... =)

Also, it's not going to help the page load tests since it affects mainly large pages, and the page load tests only have two large pages in them (and not all *that* large). Anyway, I'm about to attach a new patch fixing the issues we found during the review.

I had a read through the patch and I wasn't struck by something particularly suspicious -- seems that the migration of APIs was careful and things and have been refined quite well over the time. I am thinking of applying the diff to my tree and letting it bake a couple of days or so to see how it goes. Below are some pointless nits in the meantime. (PS: are these zc, zj, etc, annotations of interest?) ============== + * aIsPre should be ignored by frames to which the 'white-space' + * property applies. + */ + NS_IMETHOD IsEmpty(PRBool aIsQuirkMode, + PRBool aIsPre, + PRBool* aResult) = 0; >>> do you mean "doesn't apply"? + class Node { >>> mind calling this 'Interval' (or 'Segment')? ========== case eReflowReason_StyleChange: + DrainOverflowLines(aPresContext); rv = PrepareStyleChangedReflow(state); break; >>> why is this necessary now, was there a latent bug waiting to strike? + if (! mLines.empty()) { >>> mind renaming to mLines.isempty()? Found this much easier to read -- as it avoid stopping and thinking whether it is being reset... (and while you are at it, mind renaming 'erase' to 'remove', and 'size' to 'count'?) ============== -nsLineBox* +void nsBlockFrame::FindLineFor(nsIFrame* aFrame, - nsLineBox** aPrevLineResult, - PRBool* aIsFloaterResult) + PRBool* aIsFloaterResult, + line_iterator* aFoundLine) { - // This assertion actually fires on lots of pages - // (e.g., bugzilla, bugzilla query page), so limit it - // to a few people until we fix the problem causing it. -#if defined(DEBUG_dbaron) || defined(DEBUG_waterson) NS_PRECONDITION(aFrame, "why pass a null frame?"); -#endif >>> did you find the explanation to the null frame?

> (PS: are these zc, zj, etc, annotations of interest?) My numbering system for patches (0,1,...,9,a,b,...,z,z0,z1,...) > ============== > + * aIsPre should be ignored by frames to which the 'white-space' > + * property applies. > + */ > + NS_IMETHOD IsEmpty(PRBool aIsQuirkMode, > + PRBool aIsPre, > + PRBool* aResult) = 0; > >>> do you mean "doesn't apply"? No, I mean apply, since when the 'white-space' property does apply, the value is recomputed. It's a way of passing the value of the white-space property from block frames (to which it applies) down through inline frames to text frames, to which it doesn't apply. > + class Node { > >>> mind calling this 'Interval' (or 'Segment')? OK, I'll change it to Interval. > ========== > case eReflowReason_StyleChange: > + DrainOverflowLines(aPresContext); > rv = PrepareStyleChangedReflow(state); > break; > >>> why is this necessary now, was there a latent bug waiting to strike? Yes, although I forget the bug number. At one point we were doing a style-change reflow during printing, but it caused lines to disappear. (The same thing could be a more serious problem if we used the same mechanism for multicol support.) > + if (! mLines.empty()) { > >>> mind renaming to mLines.isempty()? Found this much easier to > read -- as it avoid stopping and thinking whether it is being reset... > (and while you are at it, mind renaming 'erase' to 'remove', and 'size' > to 'count'?) I'd prefer to stay close to the C++ list API, which is theoretically well known. (My only change was 'after_insert' and 'before_insert' rather than 'insert'.) > ============== > -nsLineBox* > +void > nsBlockFrame::FindLineFor(nsIFrame* aFrame, > - nsLineBox** aPrevLineResult, > - PRBool* aIsFloaterResult) > + PRBool* aIsFloaterResult, > + line_iterator* aFoundLine) > { > - // This assertion actually fires on lots of pages > - // (e.g., bugzilla, bugzilla query page), so limit it > - // to a few people until we fix the problem causing it. > -#if defined(DEBUG_dbaron) || defined(DEBUG_waterson) > NS_PRECONDITION(aFrame, "why pass a null frame?"); > -#endif > >>> did you find the explanation to the null frame? No, but it's related to the other assertion where I changed the comment (about incremental unconstrained first-pass reflows), and I'll add back the #ifdef and refer to the comment on the other assertion.

Applied the patch on Win2K, and things have been going well. I am sending this bugzilla comment with a build that has the patch. I just had to work my way through two build errors listed below. ============ mozilla\layout\html\base\src\nsLineBox.h(1279) : error C26 79: binary '!=' : no operator defined which takes a right-hand operand of type ' class nsLineLink' (or there is no acceptable conversion) NMAKE : fatal error U1077: 'cl' : return code '0x2' Stop. NMAKE : fatal error U1077: '"C:\Program Files\Microsoft Visual Studio\VC98\bin\N MAKE.EXE"' : return code '0x2' Stop. >>> Work-around: it turned out that the problem arises in an assertion, so I just commented it to get going... - NS_ASSERTION(position != i && position != *i->_mNext, - "We don't check for this case."); +// NS_ASSERTION(position != i && position != *i->_mNext, +// "We don't check for this case."); ============ mozilla\layout\base\tests\TestSpaceManager.cpp(47) : error C2664: '__thiscall nsSpaceManager::nsSpaceManager(const class nsSpaceManager &) ' : cannot convert parameter 1 from 'class nsIFrame *' to 'const class nsSpaceMa nager &' Reason: cannot convert from 'class nsIFrame *' to 'const class nsSpaceMa nager' No constructor could take the source type, or constructor overload resol ution was ambiguous >>>Work-around: Since I am not going to run TestSpaceManager, I did: - MySpaceManager(nsIFrame* aFrame) : nsSpaceManager(aFrame) {} + MySpaceManager(nsIFrame* aFrame) : nsSpaceManager(nsnull, aFrame) {}

Wow. I did a bunch of the early development of the patch on Windows, although I haven't built it there for a bit. That's surprising -- it builds fine on Mac and Linux with gcc 3.0.1 and gcc 2.7.2.3. It's nice that TestSpaceManager is part of the build only on Windows. I'm really not sure how that assertion compiled -- I'm assuming the bustage was fixed by removing the "*".

Yes.

For reviewers and for the permanent record, here's a summary of the changes (which I'll probably compact into a checkin comment): The major changes are: 1) Make the line list doubly-linked, and access it through a list class similar to the C++ list API, but using fused allocation of links with line boxes. This is needed to do (2) since (2) requires walking backward through the line list an arbitrary distance. It also allowed of other performance optimizations such as the one in nsBlockFrame::AddFrames. This change is most of the changes in terms of lines of code, since it involved many changes to all users of the line list. However, most of those changes are self-explanatory, and those that aren't are probably the result of debugging the strange code. 2) Rather than recomputing vertical margins on all children of any block in the reflow chain, add an additional dirty bit to the line box (top margin dirty, or, dirty in a way that might require sliding but not reflowing), and recompute vertical margins only when that bit is set or for a child that is dirty and is going to be reflowed. (I made room for the bit by removing a write-only bit isTrimmed.) This requires some logic to walk backwards to retrieve the vertical margins, which requires (1). This change involved changing nsBlockFrame::ReflowDirtyLines a bit, removing much of the code from nsBlockReflowState::RecoverStateFrom and moving some the logic into nsBlockReflowState::RecoverVerticalMarginAbove. This also required the addition and implementations of nsIFrame::IsEmpty to emulate the code in nsLineLayout that determines when lines are empty (which cannot easily be shared). The changes to nsBlockFrame::ReflowDirtyLines: * maintain |deltaY| more accurately, and depend on it for sliding lines * maintain |needToRecoverMargins| to ensure that margins are recovered only on the transition from a line that did not require reflow or recomputation of top margin to one that did require one of those operations. * reposition views once for the entire block rather than for each SlideLine, since I'm avoiding calling SlideLine when the offset is 0. (We need to revisit this with changes to the way we do view positioning.) 3) Fix the O(N^2) propagation of float damage (bug 61962) by maintaining a set of intervals that have been damaged by changes to floats, so that, rather than marking all the relevant lines dirty when a float changes size, just add a region of damage and as we get to the relevant line check to see if the line is listed in the regions that have been damaged. The old propagation actually didn't even work right, so these changes also fix bug 48138. Change #3 involved changes to nsBlockFrame::ReflowDirtyLines, and splitting nsBlockFrame::PropagateReflowDamage into nsBlockFrame::RememberReflowDamage and nsBlockFrame::PropagateReflowDamage, the creation of the nsIntervalSet class, and the addition of methods to the space manager to deal with the interval set (since the space manager maintains appropriate coordinate transforms). 4) Fix bug 50142 by using nsCollapsingMargin to do correct collapsing of mixed positive and negative margins instead of the incorrect nsBlockReflowContext::MaxMargin. This change involves changes to nsHTMLReflowMetrics.h (introducing nsCollapsingMargin) and changes to the other places where margins are handled. 5) Various build warning fixes (in particular, casts to |void*| for printf), changes from NS_DEFINE_IID to NS_DEFINE_CID when used with CIDs, and fixes to 80th column violations are also included.

I occasionnally hit this assertion in nsBlockFrame::ComputeFinalSize() : // Return bottom margin information NS_ASSERTION(aMetrics.mCarriedOutBottomMargin.IsZero(), "someone else set the margin"); Here is a stack trace from from visiting CNN and clicking to one of the news arctiles: NTDLL! 77f9eea9() nsDebug::Assertion(const char * 0x01c70304, const char * 0x01c702d8, const char * 0x01c70294, int 1358) line 290 + 13 bytes nsBlockFrame::ComputeFinalSize(const nsHTMLReflowState & {...}, nsBlockReflowState & {...}, nsHTMLReflowMetrics & {...}) line 1358 + 41 bytes nsBlockFrame::Reflow(nsBlockFrame * const 0x04b3c6c8, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 853 nsBlockReflowContext::DoReflowBlock(nsHTMLReflowState & {...}, nsReflowReason eReflowReason_Resize, nsIFrame * 0x04b3c6c8, const nsRect & {...}, int 1, nsCollapsingMargin & {...}, int 0, nsMargin & {...}, unsigned int & 0) line 580 + 36 bytes nsBlockReflowContext::ReflowBlock(nsIFrame * 0x04b3c6c8, const nsRect & {...}, int 1, nsCollapsingMargin & {...}, int 0, nsMargin & {...}, unsigned int & 0) line 356 + 50 bytes nsBlockFrame::ReflowBlockFrame(nsBlockReflowState & {...}, nsLineList_iterator {...}, int * 0x0012b2b8) line 3096 + 59 bytes nsBlockFrame::ReflowLine(nsBlockReflowState & {...}, nsLineList_iterator {...}, int * 0x0012b2b8, int 0) line 2306 + 27 bytes nsBlockFrame::ReflowDirtyLines(nsBlockReflowState & {...}) line 2076 + 31 bytes nsBlockFrame::Reflow(nsBlockFrame * const 0x00f2972c, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 826 + 15 bytes nsContainerFrame::ReflowChild(nsIFrame * 0x00f2972c, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 0, int 0, unsigned int 0, unsigned int & 0) line 715 + 31 bytes nsTableCellFrame::Reflow(nsTableCellFrame * const 0x00f296d0, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 796 nsContainerFrame::ReflowChild(nsIFrame * 0x00f296d0, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 1950, int 0, unsigned int 0, unsigned int & 0) line 715 + 31 bytes nsTableRowFrame::ReflowChildren(nsTableRowFrame * const 0x049760ac, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, nsTableFrame & {...}, unsigned int & 0, int 0) line 900 + 45 bytes nsTableRowFrame::Reflow(nsTableRowFrame * const 0x049760ac, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 1244 + 37 bytes nsContainerFrame::ReflowChild(nsIFrame * 0x049760ac, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 0, int 37665, unsigned int 0, unsigned int & 0) line 715 + 31 bytes nsTableRowGroupFrame::ReflowChildren(nsTableRowGroupFrame * const 0x048a83f8, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, nsRowGroupReflowState & {...}, unsigned int & 0, nsTableRowFrame * 0x00000000, int 1, nsTableRowFrame * * 0x0012bfd4) line 407 + 45 bytes nsTableRowGroupFrame::IR_TargetIsMe(nsTableRowGroupFrame * const 0x048a83f8, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, nsRowGroupReflowState & {...}, unsigned int & 0) line 1268 + 33 bytes nsTableRowGroupFrame::IncrementalReflow(nsTableRowGroupFrame * const 0x048a83f8, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, nsRowGroupReflowState & {...}, unsigned int & 0) line 1126 + 31 bytes nsTableRowGroupFrame::Reflow(nsTableRowGroupFrame * const 0x048a83f8, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 1060 + 31 bytes nsContainerFrame::ReflowChild(nsIFrame * 0x048a83f8, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 0, int 0, unsigned int 0, unsigned int & 0) line 715 + 31 bytes nsTableFrame::IR_TargetIsChild(nsTableFrame * const 0x048a8328, nsIPresContext * 0x04b6b0e0, nsTableReflowState & {...}, unsigned int & 0, nsIFrame * 0x048a83f8) line 2775 + 50 bytes nsTableFrame::IncrementalReflow(nsTableFrame * const 0x048a8328, nsIPresContext * 0x04b6b0e0, const nsHTMLReflowState & {...}, unsigned int & 0) line 2617 + 31 bytes nsTableFrame::Reflow(nsTableFrame * const 0x048a8328, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 1884 + 27 bytes nsContainerFrame::ReflowChild(nsIFrame * 0x048a8328, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 0, int 0, unsigned int 3, unsigned int & 0) line 715 + 31 bytes nsTableOuterFrame::OuterReflowChild(nsTableOuterFrame * const 0x049721c4, nsIPresContext * 0x04b6b0e0, nsIFrame * 0x048a8328, const nsHTMLReflowState & {...}, nsHTMLReflowMetrics & {...}, int * 0x00000000, nsSize & {...}, nsMargin & {...}, nsMargin & {...}, nsMargin & {...}, nsReflowReason eReflowReason_Incremental, unsigned int & 0) line 990 + 47 bytes nsTableOuterFrame::IR_InnerTableReflow(nsTableOuterFrame * const 0x049721c4, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 1293 + 67 bytes nsTableOuterFrame::IR_TargetIsInnerTableFrame(nsTableOuterFrame * const 0x049721c4, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 1095 + 31 bytes nsTableOuterFrame::IR_TargetIsChild(nsTableOuterFrame * const 0x049721c4, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0, nsIFrame * 0x048a8328) line 1067 + 31 bytes nsTableOuterFrame::IncrementalReflow(nsTableOuterFrame * const 0x049721c4, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 1046 + 35 bytes nsTableOuterFrame::Reflow(nsTableOuterFrame * const 0x049721c4, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 1523 + 31 bytes nsBlockReflowContext::DoReflowBlock(nsHTMLReflowState & {...}, nsReflowReason eReflowReason_Incremental, nsIFrame * 0x049721c4, const nsRect & {...}, int 1, nsCollapsingMargin & {...}, int 0, nsMargin & {...}, unsigned int & 0) line 580 + 36 bytes nsBlockReflowContext::ReflowBlock(nsIFrame * 0x049721c4, const nsRect & {...}, int 1, nsCollapsingMargin & {...}, int 0, nsMargin & {...}, unsigned int & 0) line 356 + 50 bytes nsBlockFrame::ReflowBlockFrame(nsBlockReflowState & {...}, nsLineList_iterator {...}, int * 0x0012d04c) line 3096 + 59 bytes nsBlockFrame::ReflowLine(nsBlockReflowState & {...}, nsLineList_iterator {...}, int * 0x0012d04c, int 1) line 2306 + 27 bytes nsBlockFrame::ReflowDirtyLines(nsBlockReflowState & {...}) line 2076 + 31 bytes nsBlockFrame::Reflow(nsBlockFrame * const 0x00e2d590, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 826 + 15 bytes nsBlockReflowContext::DoReflowBlock(nsHTMLReflowState & {...}, nsReflowReason eReflowReason_Incremental, nsIFrame * 0x00e2d590, const nsRect & {...}, int 1, nsCollapsingMargin & {...}, int 1, nsMargin & {...}, unsigned int & 0) line 580 + 36 bytes nsBlockReflowContext::ReflowBlock(nsIFrame * 0x00e2d590, const nsRect & {...}, int 1, nsCollapsingMargin & {...}, int 1, nsMargin & {...}, unsigned int & 0) line 356 + 50 bytes nsBlockFrame::ReflowBlockFrame(nsBlockReflowState & {...}, nsLineList_iterator {...}, int * 0x0012dd10) line 3096 + 59 bytes nsBlockFrame::ReflowLine(nsBlockReflowState & {...}, nsLineList_iterator {...}, int * 0x0012dd10, int 1) line 2306 + 27 bytes nsBlockFrame::ReflowDirtyLines(nsBlockReflowState & {...}) line 2076 + 31 bytes nsBlockFrame::Reflow(nsBlockFrame * const 0x00e2d158, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 826 + 15 bytes nsContainerFrame::ReflowChild(nsIFrame * 0x00e2d158, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 0, int 0, unsigned int 0, unsigned int & 0) line 715 + 31 bytes CanvasFrame::Reflow(CanvasFrame * const 0x048167e4, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 581 nsBoxToBlockAdaptor::Reflow(nsBoxLayoutState & {...}, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0, int 0, int 0, int 11460, int 8055, int 1) line 884 nsBoxToBlockAdaptor::DoLayout(nsBoxToBlockAdaptor * const 0x00e2d0b8, nsBoxLayoutState & {...}) line 539 + 52 bytes nsBox::Layout(nsBox * const 0x00e2d0b8, nsBoxLayoutState & {...}) line 1002 nsScrollBoxFrame::DoLayout(nsScrollBoxFrame * const 0x04816b9c, nsBoxLayoutState & {...}) line 393 nsBox::Layout(nsBox * const 0x04816b9c, nsBoxLayoutState & {...}) line 1002 nsContainerBox::LayoutChildAt(nsBoxLayoutState & {...}, nsIBox * 0x04816b9c, const nsRect & {...}) line 649 + 16 bytes nsGfxScrollFrameInner::LayoutBox(nsBoxLayoutState & {...}, nsIBox * 0x04816b9c, const nsRect & {...}) line 1026 + 17 bytes nsGfxScrollFrameInner::Layout(nsBoxLayoutState & {...}) line 1133 nsGfxScrollFrame::DoLayout(nsGfxScrollFrame * const 0x04816934, nsBoxLayoutState & {...}) line 1034 + 15 bytes nsBox::Layout(nsBox * const 0x04816934, nsBoxLayoutState & {...}) line 1002 nsBoxFrame::Reflow(nsBoxFrame * const 0x048168fc, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 944 nsGfxScrollFrame::Reflow(nsGfxScrollFrame * const 0x048168fc, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 750 + 25 bytes nsContainerFrame::ReflowChild(nsIFrame * 0x048168fc, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 0, int 0, unsigned int 0, unsigned int & 0) line 715 + 31 bytes ViewportFrame::Reflow(ViewportFrame * const 0x048167a8, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) line 575 nsHTMLReflowCommand::Dispatch(nsHTMLReflowCommand * const 0x05142430, nsIPresContext * 0x04b6b0e0, nsHTMLReflowMetrics & {...}, const nsSize & {...}, nsIRenderingContext & {...}) line 217 PresShell::ProcessReflowCommand(nsVoidArray & {...}, int 0, nsHTMLReflowMetrics & {...}, nsSize & {...}, nsIRenderingContext & {...}) line 5950 PresShell::ProcessReflowCommands(int 0) line 6005 PresShell::FlushPendingNotifications(PresShell * const 0x04b91cd0, int 0) line 4963 nsEventStateManager::FlushPendingEvents(nsIPresContext * 0x04b6b0e0) line 3975 nsEventStateManager::GenerateDragGesture(nsIPresContext * 0x04b6b0e0, nsGUIEvent * 0x0012f780) line 1149 nsEventStateManager::PreHandleEvent(nsEventStateManager * const 0x04ba9398, nsIPresContext * 0x04b6b0e0, nsEvent * 0x0012f780, nsIFrame * 0x04990884, nsEventStatus * 0x0012f674, nsIView * 0x04fc6d30) line 367 PresShell::HandleEventInternal(nsEvent * 0x0012f780, nsIView * 0x04fc6d30, unsigned int 1, nsEventStatus * 0x0012f674) line 5742 + 43 bytes PresShell::HandleEvent(PresShell * const 0x04b91cd4, nsIView * 0x04fc6d30, nsGUIEvent * 0x0012f780, nsEventStatus * 0x0012f674, int 0, int & 1) line 5673 + 25 bytes nsView::HandleEvent(nsView * const 0x04fc6d30, nsGUIEvent * 0x0012f780, unsigned int 8, nsEventStatus * 0x0012f674, int 0, int & 1) line 392 nsView::HandleEvent(nsView * const 0x04fc2d50, nsGUIEvent * 0x0012f780, unsigned int 8, nsEventStatus * 0x0012f674, int 0, int & 1) line 365 nsView::HandleEvent(nsView * const 0x04b93f90, nsGUIEvent * 0x0012f780, unsigned int 28, nsEventStatus * 0x0012f674, int 1, int & 1) line 365 nsViewManager::DispatchEvent(nsViewManager * const 0x04b915f0, nsGUIEvent * 0x0012f780, nsEventStatus * 0x0012f674) line 2196 HandleEvent(nsGUIEvent * 0x0012f780) line 83 nsWindow::DispatchEvent(nsWindow * const 0x04fc6ee4, nsGUIEvent * 0x0012f780, nsEventStatus & nsEventStatus_eIgnore) line 744 + 10 bytes nsWindow::DispatchWindowEvent(nsGUIEvent * 0x0012f780) line 765 nsWindow::DispatchMouseEvent(unsigned int 300, nsPoint * 0x00000000) line 4314 + 21 bytes ChildWindow::DispatchMouseEvent(unsigned int 300, nsPoint * 0x00000000) line 4566 nsWindow::ProcessMessage(unsigned int 512, unsigned int 0, long 22872583, long * 0x0012fb9c) line 3226 + 24 bytes nsWindow::WindowProc(HWND__ * 0x001503b0, unsigned int 512, unsigned int 0, long 22872583) line 1012 + 27 bytes USER32! 77e148dc() USER32! 77e14aa7() USER32! 77e266fd() nsAppShellService::Run(nsAppShellService * const 0x037e7ee0) line 305 main1(int 1, char * * 0x00484300, nsISupports * 0x00000000) line 1285 + 32 bytes main(int 1, char * * 0x00484300) line 1607 + 37 bytes mainCRTStartup() line 338 + 17 bytes

> > >>> why is this necessary now, was there a latent bug waiting to strike? > > Yes, although I forget the bug number. At one point we were doing a > style-change reflow during printing, but it caused lines to disappear. > (The same thing could be a more serious problem if we used the same > mechanism for multicol support.) It was bug 91678.

The patch seems to be going fine since I applied it. In particular, the da mow mow portal hasn't regressed. I stepped in the debugger for a particular code-path that I had in mind, and have now tried to reverse-match the changes to the explanatory comments you gave above. I had some further nits in the process (see below). However, rather than removing all the matches that I found, I have left them in and simply labeled them as 'FYI' for others who might be interested. No action needed on these. Any thoughts on the assertion I reported above? I will give my r= upon hearing back from you on these points. === /** - * Propagate reflow "damage" from the just reflowed line (aLine) to - * any subsequent lines that were affected. The only thing that causes - * damage is a change to the impact that floaters make. - * - * XXX_perf: This is O(N^2) because we loop over all following lines - * for each line that is damaged. See bug 61962. + * Propagate reflow "damage" from from earlier lines to the current + * line. */ void nsBlockFrame::PropagateReflowDamage(nsBlockReflowState& aState, >>>Many comments were removed in that function, without giving replacements. The key information that I see when I flip pass that function is "The only thing that causes damage is a change to the impact that floaters make." This quickly turns the "floater radars" on when reading the code. Surely, equivalent helpful comments are needed if these are to be deleted. === - // The line's combined-area changed. Therefore we need to damage - // the lines below that were previously (or are now) impacted by - // the change. It's possible that a floater shrunk or grew so - // use the larger of the impacted area. >>>Taking all the minuses out, we end up with a collapsed code as: nsBlockFrame::PropagateReflowDamage(nsBlockReflowState& aState, nsLineBox* aLine, + nscoord aDeltaY, + PRBool* aRepositionViews) { + if (aDeltaY != 0) + SlideLine(aState, aLine, aDeltaY); + else + *aRepositionViews = PR_TRUE; + + if (aLine->IsDirty()) + return; + + // Check the damage region recorded in the float damage. + nsISpaceManager *spaceManager = aState.mReflowState.mSpaceManager; + if (spaceManager->HasFloatDamage()) { + nscoord lineYA = aLine->mBounds.y + aDeltaY; + nscoord lineYB = lineYA + aLine->mBounds.height; + if (spaceManager->IntersectsDamage(lineYA, lineYB)) { + aLine->MarkDirty(); return; } } >>>No comments... (Not this meaning of this idiom! I mean what the code is doing seems to be lost. It isn't a simple code where comments can be deleted so easily without replacing them with other helpful comments. Let's collapse the margins, not the comments). >2) [...] > This change involved changing nsBlockFrame::ReflowDirtyLines a bit, > removing much of the code from nsBlockReflowState::RecoverStateFrom > and moving some the logic into > nsBlockReflowState::RecoverVerticalMarginAbove. This also required > the addition and implementations of nsIFrame::IsEmpty to emulate the > code in nsLineLayout that determines when lines are empty (which > cannot easily be shared). The changes to > nsBlockFrame::ReflowDirtyLines: >>>typo: -RecoverVerticalMarginAbove +ReconstructMarginAbove And here also, comments are taken out and not replaced. === > * maintain |deltaY| more accurately, and depend on it for sliding > lines >>>an example of the dependent use of |deltaY|: + if (oldY == 0 && oldY + deltaY != line->mBounds.y) { + // This means the current line was just reflowed for the first + // time. Thus we must mark the top margin of the next line dirty. >>>nit (maybe ignore this nit since it doesn't help readability): + if (oldY == 0 && deltaY != line->mBounds.y) { and what makes this test fulfil what the comment says, BTW? Since [a]DeltaY appears as a critical parameter upon which you depend for other things, its particular (expected?) state surely needs more comments wherever it is used. === > * maintain |needToRecoverMargins| to ensure that margins are > recovered only on the transition from a line that did not require > reflow or recomputation of top margin to one that did require one > of those operations. >>> FYI: in action at: @@ -2009,23 +2027,23 @@ + PRBool needToRecoverMargin = PR_FALSE; [...] + // Reflow the lines that are already ours + line_iterator line = begin_lines(), line_end = end_lines(); + for ( ; line != line_end; ++line, aState.AdvanceToNextLine()) { - if (line->IsDirty() || (aState.GetFlag(BRS_COMPUTEMAXWIDTH) && ::WrappedLinesAreDirty(line))) { + if (line->IsDirty() || + (aState.GetFlag(BRS_COMPUTEMAXWIDTH) && + ::WrappedLinesAreDirty(line, line_end))) { + + if (needToRecoverMargin) + aState.ReconstructMarginAbove(line); + needToRecoverMargin = PR_FALSE; >>>nit: + if (needToRecoverMargin) { + aState.ReconstructMarginAbove(line); + needToRecoverMargin = PR_FALSE; } === > * reposition views once for the entire block rather than for each > SlideLine, since I'm avoiding calling SlideLine when the offset is > 0. (We need to revisit this with changes to the way we do view > positioning.) >>> more of |deltaY| is here. >3) [...] > Change #3 involved changes to nsBlockFrame::ReflowDirtyLines, and > splitting nsBlockFrame::PropagateReflowDamage into > nsBlockFrame::RememberReflowDamage >>>FYI: in action at: @@ -2053,35 +2079,56 @@ > and nsBlockFrame::PropagateReflowDamage, >>>FYI: in action at: @@ -1980,6 +1997,7 @@ and ff. > the creation of the > nsIntervalSet class, and the addition of methods to the space manager > to deal with the interval set (since the space manager maintains > appropriate coordinate transforms). >>>FYI: class nsSpaceManager : public nsISpaceManager { [...] + NS_IMETHOD_(void) IncludeInDamage(nscoord aIntervalBegin, + nscoord aIntervalEnd); + NS_IMETHOD_(PRBool) IntersectsDamage(nscoord aIntervalBegin, + nscoord aIntervalEnd); [...] + nsIntervalSet mFloatDamage; >>>FYI: in action in: nsBlockFrame::RememberReflowDamage() nsBlockFrame::PropagateReflowDamage() >4) Fix bug 50142 by using nsCollapsingMargin to do correct collapsing > of mixed positive and negative margins instead of the incorrect > nsBlockReflowContext::MaxMargin. >>>FYI: in action at: @@ -2931,14 +3050,13 @@ and ff.

The patch looks great! Overall I think it is a nice improvement, although I am worried about some of the apparent loose-ends (not like there weren;t any before though). Here are my comments, all minor really: General: - there are some +// vim:cindent:ts=2:et:sw=2: lines with ts=8 (do we really want vim entries in these files?) mozilla/layout/base/src/makefile.win mozilla/layout/html/base/src/makefile.win - why are the CPPSRCS removed? nsIntervalSet::nsIntervalSet - presumably, he arguments must all be non-null. Should assert that they are. nsIntervalSet::FreeNode - direct call of dtor is really ugly - why? Can't you use a Destroy method? Actually, Node needs no dtor call at all... - ASSERT that aNode is non-null? nsIntervalSet::IncludeInterval - allocation should check for null - 'useless' is an _interesting_ name for the cursor in the list ;) nsBlockFrame - a helper to mark all lines dirty might be nice (it happens a few times in the current code) - nsBlockFrame::FindLineFor has a differnt iterator construct - wondering why, so line can be referenced outside of the loop? + line_iterator line = begin_lines(), + line_end = end_lines(); + for ( ; line != line_end; ++line) { - what are we to do with this? Is it a major flaw we must (or can) live with? + // This is a major flaw in this code. - and this? + // XXX EVIL O(N^2) EVIL - nsBlockFrame::SlideLine might want to check for non-empty bounds before invalidating (twice) - do the inline line_iterator methods need to be public? Could BlockReflowState be a friend instead? + line_iterator begin_lines() { return mLines.begin(); } + line_iterator end_lines() { return mLines.end(); } etc. nsLineList_* - Should these cause me any worry? If they do not work, maybe they can be #if 0'd out? +// Many of these implementations of operator= don't work yet. I don't +// know why.

Comment on attachment 53964 [details] [diff] [review] patch incorporating comments from waterson review (zk) r=attinasi

Comment on attachment 53964 [details] [diff] [review] patch incorporating comments from waterson review (zk) > ------- Additional Comments From rbs@maths.uq.edu.au 2001-10-19 15:38 ------- > > I occasionnally hit this assertion in nsBlockFrame::ComputeFinalSize() : > > // Return bottom margin information > NS_ASSERTION(aMetrics.mCarriedOutBottomMargin.IsZero(), > "someone else set the margin"); OK, I commented out the assertion and changed it back to zeroing the margin. > ------- Additional Comments From rbs@maths.uq.edu.au 2001-10-22 04:27 ------- > > void > nsBlockFrame::PropagateReflowDamage(nsBlockReflowState& aState, > > >>>Many comments were removed in that function, without giving replacements. > The key information that I see when I flip pass that function is "The only > thing that causes damage is a change to the impact that floaters make." > This quickly turns the "floater radars" on when reading the code. Surely, > equivalent helpful comments are needed if these are to be deleted. Renamed RememberReflowDamage to RememberFloaterDamage and added some comments to PropagateReflowDamage. I also removed an extraneous |IsDirty| check in PropagateReflowDamage since it is now never called on lines that are already dirty. However, this led me to a bug (in the ordering of code in ReflowDirtyLines), which is that I didn't then reflow the dirty line that was marked dirty by PropagateReflowDamage, which I fixed, although the fix was somewhat involved (described below). > >>>typo: > -RecoverVerticalMarginAbove > +ReconstructMarginAbove > And here also, comments are taken out and not replaced. Comments added here (although it's an entirely new function). > Since [a]DeltaY appears as a critical parameter upon which you depend for other > things, its particular (expected?) state surely needs more comments wherever it > is used. I added a number of comments in the cleanup of ReflowDirtyLines that I did to fix the bug mentioned above. I also fixed the two "nit"s you pointed out. > ------- Additional Comments From Marc Attinasi 2001-10-22 22:15 ------- > > General: > - there are some +// vim:cindent:ts=2:et:sw=2: lines with ts=8 > (do we really want vim entries in these files?) Yes. I certainly want them in files that I edit often. After all, we have emacs modelines in practically every file in the tree... > mozilla/layout/base/src/makefile.win > mozilla/layout/html/base/src/makefile.win > - why are the CPPSRCS removed? Because they don't do anything. I've asked for this removal to be done tree-wide (it's not really tree-wide, it's only the old Gecko makefiles which may have used them at one point in the long-gone past), but it hasn't happened yet. See bug 102459. > nsIntervalSet::nsIntervalSet > - presumably, he arguments must all be non-null. Should assert that they are. Done. > nsIntervalSet::FreeNode > - direct call of dtor is really ugly - why? Can't you use a Destroy method? > Actually, Node needs no dtor call at all... Why is it ugly? I want to do any destruction before using the free callback. That's what destructors are for. > - ASSERT that aNode is non-null? Done. > nsIntervalSet::IncludeInterval > - allocation should check for null Done. > - 'useless' is an _interesting_ name for the cursor in the list ;) Changed to subsumed (Brendan's suggestion). > nsBlockFrame > - a helper to mark all lines dirty might be nice (it happens a few times in the > current code) Hmmm. I'd rather not make it easy since I'd rather not mark all lines dirty. :-) > - nsBlockFrame::FindLineFor has a differnt iterator construct - wondering why, > so line can be referenced outside of the loop? > + line_iterator line = begin_lines(), > + line_end = end_lines(); > + for ( ; line != line_end; ++line) { Yep -- line is used after the loop. > - what are we to do with this? Is it a major flaw we must (or can) live with? > + // This is a major flaw in this code. It existed before my checkin. I'm just pointing it out a little more strongly. I'm also hoping to fix it sometime, although it's a good bit of work. > - and this? > + // XXX EVIL O(N^2) EVIL Ditto. > - nsBlockFrame::SlideLine might want to check for non-empty bounds before > invalidating (twice) Done. > - do the inline line_iterator methods need to be public? Could BlockReflowState > be a friend instead? > + line_iterator begin_lines() { return mLines.begin(); } > + line_iterator end_lines() { return mLines.end(); } > etc. Made them protected, which is what mLines is. > nsLineList_* > - Should these cause me any worry? If they do not work, maybe they can be > #if 0'd out? > +// Many of these implementations of operator= don't work yet. I don't > +// know why. That comment may or may not be valid anymore since I untemplatized the code. If it's not, then "not work" == "not compile", so it's not really a problem. The more major problem that I mentioned above was that when PropagateReflowDamage marked something dirty, we were already past the dirtiness check. So I reordered some of the stuff in ReflowDirtyLines (I think it's a little cleaner now, although maybe some of the things I had to add made it about even). I had to pull the SlideLine call out of PropagateReflowDamage, and I clarified the meaning of deltaY at different points. I also renamed PropagateReflowDamage to PropagateFloaterDamage since that's all it does now. I also renamed MarkTopMarginDirty to MarkPreviousMarginDirty since it's really about the carried out margin of the previous line, not the top margin of the new one. I'll attach the revised patch.

Comment on attachment 54827 [details] [diff] [review] patch incorporating feedback from rbs and attinasi (zm) r=rbs >I also renamed PropagateReflowDamage to >PropagateFloaterDamage since that's all it does now. Apparently, the s///g is still pending

Results from jrgm's performance tests: baseline: 1082/1093/473/3497 baseline: 1084/1097/476/3208 block changes: 1075/1085/468/3088 block changes: 1077/1088/479/3138 Not very significant, but this patch helps mostly long pages, and jrgm's tests only contain a few long pages (and not all that long).

Checked in 2001-10-24 18:08 PDT.

MathML doesn't build anymore on Mac. Any ideas? Error : type mismatch 'nsLineList_iterator' and 'nsLineLink *' nsLineBox.h line 1257 "We don't check for this case.");

Changing http://lxr.mozilla.org/seamonkey/source/layout/html/base/src/nsLineBox.h#1256 from NS_ASSERTION(position != i && position != i->_mNext, to NS_ASSERTION(position != i && position.get() != i->_mNext, fixes it, but I don't know whether that's right.

Fresh update this morning (10/25). Since this patch went in, I'm seeing a number of frame-related assertions (I was loading a jprof file): "unexpected child frame type" (due to nsnull as aListName - arg 4 to InsertFrames in nsCSSFrameConstructor::ContentInserted line 8702). "not a container" from nsFrame::AppendFrames() line 392 "invalid previous frame"

peterv: |.mCurrent| would be better than |.get()| -- I'll check it in when the tree opens, or maybe earlier. I wonder why only you and jfrancis see the problem (and he doesn't build MathML). rjesup: Do you know whether the assertions are related to my changes? bryner said he's seen those often before. Could they be related to hyatt's changes?

The assertions I mentioned (not a container, invalid previous frame, unexpected type) are all new to me since I updated this morning. All involve nsFrame and nsFrameManager. The "this doesn't do anything: 'NS_UNCONSTRAINEDSIZE != aReflowState.availableWidth'" assertion I've seen on and off for a month or two.

I have a readily available build that only has dbaron's changes (the final ones that he checked in). Do you have links to reproduce that I could try?

Load cnn.com. Read stories on it. Select part of two paragraphs/li's below the main story image and paste into an editor/notepad/etc and see what gets pasted. Load a jprof.html file.

WFM. (The two assertions that I see: the "this doesn't do anything" and "aCombineArea" assertions are still there as in the past -- though I am wonder why these two have been there for a surprisingly long time.)

The mac debug bustage has been fixed. The assertions are most likely related to bug 106809. For any other regressions related to this change (such as bug 106658), please file other bugs. Marking this bug FIXED again.

Er, The assertions are most likely related to bug 106802. (wrong bug number -- I was looking at my own bug list, and it looked similar enough)