Back to index

lightning-sunbird  0.9+nobinonly
nsColumnSetFrame.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Robert O'Callahan <roc@ocallahan.org>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either of the GNU General Public License Version 2 or later (the "GPL"),
00027  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include "nsHTMLContainerFrame.h"
00040 #include "nsIContent.h"
00041 #include "nsIFrame.h"
00042 #include "nsISupports.h"
00043 #include "nsIAtom.h"
00044 #include "nsPresContext.h"
00045 #include "nsHTMLParts.h"
00046 #include "nsLayoutAtoms.h"
00047 #include "nsStyleConsts.h"
00048 #include "nsCOMPtr.h"
00049 #include "nsReflowPath.h"
00050 
00051 class nsColumnSetFrame : public nsHTMLContainerFrame {
00052 public:
00053   nsColumnSetFrame();
00054 
00055   NS_IMETHOD SetInitialChildList(nsPresContext* aPresContext,
00056                                  nsIAtom*        aListName,
00057                                  nsIFrame*       aChildList);
00058 
00059   NS_IMETHOD Reflow(nsPresContext* aPresContext,
00060                     nsHTMLReflowMetrics& aDesiredSize,
00061                     const nsHTMLReflowState& aReflowState,
00062                     nsReflowStatus& aStatus);
00063                                
00064   NS_IMETHOD  AppendFrames(nsIAtom*        aListName,
00065                            nsIFrame*       aFrameList);
00066   NS_IMETHOD  InsertFrames(nsIAtom*        aListName,
00067                            nsIFrame*       aPrevFrame,
00068                            nsIFrame*       aFrameList);
00069   NS_IMETHOD  RemoveFrame(nsIAtom*        aListName,
00070                           nsIFrame*       aOldFrame);
00071 
00072   NS_IMETHOD  GetFrameForPoint(const nsPoint& aPoint, 
00073                                nsFramePaintLayer aWhichLayer,
00074                                nsIFrame**     aFrame);
00075 
00076   virtual nsIFrame* GetContentInsertionFrame() {
00077     nsIFrame* kid = GetFirstChild(nsnull);
00078     return kid ? kid->GetContentInsertionFrame() : nsnull;
00079   }
00080 
00081   virtual nsIAtom* GetType() const;
00082 
00083 #ifdef DEBUG
00084   NS_IMETHOD GetFrameName(nsAString& aResult) const {
00085     return MakeFrameName(NS_LITERAL_STRING("ColumnSet"), aResult);
00086   }
00087 #endif
00088 
00089 protected:
00090   nscoord        mLastBalanceHeight;
00091   nsReflowStatus mLastFrameStatus;
00092 
00093   virtual PRIntn GetSkipSides() const;
00094 
00098   struct ReflowConfig {
00099     PRInt32 mBalanceColCount;
00100     nscoord mColWidth;
00101     nscoord mExpectedWidthLeftOver;
00102     nscoord mColGap;
00103     nscoord mColMaxHeight;
00104   };
00105   
00111   void DrainOverflowColumns();
00112 
00120   ReflowConfig ChooseColumnStrategy(const nsHTMLReflowState& aReflowState);
00121 
00126   PRBool ReflowChildren(nsHTMLReflowMetrics& aDesiredSize,
00127                         const nsHTMLReflowState& aReflowState,
00128                         nsReflowReason aReason,
00129                         nsReflowStatus& aStatus,
00130                         const ReflowConfig& aConfig,
00131                         PRBool aLastColumnUnbounded,
00132                         nsCollapsingMargin* aCarriedOutBottomMargin);
00133 };
00134 
00143 nsresult
00144 NS_NewColumnSetFrame(nsIPresShell* aPresShell, nsIFrame** aNewFrame, PRUint32 aStateFlags)
00145 {
00146   NS_PRECONDITION(aNewFrame, "null OUT ptr");
00147 
00148   nsColumnSetFrame* it = new (aPresShell) nsColumnSetFrame;
00149   if (!it) {
00150     return NS_ERROR_OUT_OF_MEMORY;
00151   }
00152 
00153   // set the state flags (if any are provided)
00154   it->AddStateBits(aStateFlags);
00155   
00156   *aNewFrame = it;
00157   return NS_OK;
00158 }
00159 
00160 nsColumnSetFrame::nsColumnSetFrame()
00161   : nsHTMLContainerFrame(), mLastBalanceHeight(NS_INTRINSICSIZE),
00162     mLastFrameStatus(NS_FRAME_COMPLETE)
00163 {
00164 }
00165 
00166 nsIAtom*
00167 nsColumnSetFrame::GetType() const
00168 {
00169   return nsLayoutAtoms::columnSetFrame;
00170 }
00171 
00172 NS_IMETHODIMP
00173 nsColumnSetFrame::GetFrameForPoint(const nsPoint& aPoint, 
00174                                    nsFramePaintLayer aWhichLayer,
00175                                    nsIFrame**     aFrame)
00176 {
00177   // This frame counts as part of the background.
00178   return GetFrameForPointUsing(aPoint, nsnull, aWhichLayer,
00179                                (aWhichLayer == NS_FRAME_PAINT_LAYER_BACKGROUND), aFrame);
00180 }
00181 
00182 NS_IMETHODIMP
00183 nsColumnSetFrame::SetInitialChildList(nsPresContext* aPresContext,
00184                                    nsIAtom*        aListName,
00185                                    nsIFrame*       aChildList)
00186 {
00187   NS_ASSERTION(!aListName, "Only default child list supported");
00188   NS_ASSERTION(aChildList && !aChildList->GetNextSibling(),
00189                "initial child list must have exactly one child");
00190   // Queue up the frames for the content frame
00191   return nsHTMLContainerFrame::SetInitialChildList(aPresContext, nsnull, aChildList);
00192 }
00193 
00194 static nscoord GetAvailableContentWidth(const nsHTMLReflowState& aReflowState) {
00195   if (aReflowState.availableWidth == NS_INTRINSICSIZE) {
00196     return NS_INTRINSICSIZE;
00197   }
00198   nscoord borderPaddingWidth =
00199     aReflowState.mComputedBorderPadding.left +
00200     aReflowState.mComputedBorderPadding.right;
00201   return PR_MAX(0, aReflowState.availableWidth - borderPaddingWidth);
00202 }
00203 
00204 static nscoord GetAvailableContentHeight(const nsHTMLReflowState& aReflowState) {
00205   if (aReflowState.availableHeight == NS_INTRINSICSIZE) {
00206     return NS_INTRINSICSIZE;
00207   }
00208   nscoord borderPaddingHeight =
00209     aReflowState.mComputedBorderPadding.top +
00210     aReflowState.mComputedBorderPadding.bottom;
00211   return PR_MAX(0, aReflowState.availableHeight - borderPaddingHeight);
00212 }
00213 
00214 nsColumnSetFrame::ReflowConfig
00215 nsColumnSetFrame::ChooseColumnStrategy(const nsHTMLReflowState& aReflowState)
00216 {
00217   const nsStyleColumn* colStyle = GetStyleColumn();
00218   nscoord availContentWidth = GetAvailableContentWidth(aReflowState);
00219   if (aReflowState.mComputedWidth != NS_INTRINSICSIZE) {
00220     availContentWidth = aReflowState.mComputedWidth;
00221   }
00222   nscoord colHeight = GetAvailableContentHeight(aReflowState);
00223   if (aReflowState.mComputedHeight != NS_INTRINSICSIZE) {
00224     colHeight = aReflowState.mComputedHeight;
00225   }
00226 
00227   nscoord colGap = 0;
00228   switch (colStyle->mColumnGap.GetUnit()) {
00229     case eStyleUnit_Coord:
00230       colGap = colStyle->mColumnGap.GetCoordValue();
00231       break;
00232     case eStyleUnit_Percent:
00233       if (availContentWidth != NS_INTRINSICSIZE) {
00234         colGap = NSToCoordRound(colStyle->mColumnGap.GetPercentValue()*availContentWidth);
00235       }
00236       break;
00237     default:
00238       NS_NOTREACHED("Unknown gap type");
00239       break;
00240   }
00241 
00242   PRInt32 numColumns = colStyle->mColumnCount;
00243 
00244   nscoord colWidth = NS_INTRINSICSIZE;
00245   if (colStyle->mColumnWidth.GetUnit() == eStyleUnit_Coord) {
00246     colWidth = colStyle->mColumnWidth.GetCoordValue();
00247 
00248     // Reduce column count if necesary to make columns fit in the
00249     // available width. Compute max number of columns that fit in
00250     // availContentWidth, satisfying colGap*(maxColumns - 1) +
00251     // colWidth*maxColumns <= availContentWidth
00252     if (availContentWidth != NS_INTRINSICSIZE && colWidth + colGap > 0
00253         && numColumns > 0) {
00254       // This expression uses truncated rounding, which is what we
00255       // want
00256       PRInt32 maxColumns = (availContentWidth + colGap)/(colGap + colWidth);
00257       numColumns = PR_MAX(1, PR_MIN(numColumns, maxColumns));
00258     }
00259   } else if (numColumns > 0 && availContentWidth != NS_INTRINSICSIZE) {
00260     nscoord widthMinusGaps = availContentWidth - colGap*(numColumns - 1);
00261     colWidth = widthMinusGaps/numColumns;
00262   }
00263   // Take care of the situation where there's only one column but it's
00264   // still too wide
00265   colWidth = PR_MAX(1, PR_MIN(colWidth, availContentWidth));
00266 
00267   nscoord expectedWidthLeftOver = 0;
00268 
00269   if (colWidth != NS_INTRINSICSIZE && availContentWidth != NS_INTRINSICSIZE) {
00270     // distribute leftover space
00271 
00272     // First, determine how many columns will be showing if the column
00273     // count is auto
00274     if (numColumns <= 0) {
00275       // choose so that colGap*(nominalColumnCount - 1) +
00276       // colWidth*nominalColumnCount is nearly availContentWidth
00277       // make sure to round down
00278       numColumns = (availContentWidth + colGap)/(colGap + colWidth);
00279       if (numColumns <= 0) {
00280         numColumns = 1;
00281       }
00282     }
00283 
00284     // Compute extra space and divide it among the columns
00285     nscoord extraSpace = availContentWidth - (colWidth*numColumns + colGap*(numColumns - 1));
00286     nscoord extraToColumns = extraSpace/numColumns;
00287     colWidth += extraToColumns;
00288     expectedWidthLeftOver = extraSpace - (extraToColumns*numColumns);
00289   }
00290 
00291   // NOTE that the non-balancing behavior for non-auto computed height
00292   // is not in the CSS3 columns draft as of 18 January 2001
00293   if (aReflowState.mComputedHeight == NS_INTRINSICSIZE) {
00294     // Balancing!
00295     if (numColumns <= 0) {
00296       // Hmm, auto column count, column width or available width is unknown,
00297       // and balancing is required. Let's just use one column then.
00298       numColumns = 1;
00299     }
00300     colHeight = PR_MIN(mLastBalanceHeight, GetAvailableContentHeight(aReflowState));
00301   } else {
00302     // No balancing, so don't limit the column count
00303     numColumns = PR_INT32_MAX;
00304   }
00305 
00306 #ifdef DEBUG_roc
00307   printf("*** nsColumnSetFrame::ChooseColumnStrategy: numColumns=%d, colWidth=%d, expectedWidthLeftOver=%d, colHeight=%d, colGap=%d\n",
00308          numColumns, colWidth, expectedWidthLeftOver, colHeight, colGap);
00309 #endif
00310   ReflowConfig config = { numColumns, colWidth, expectedWidthLeftOver, colGap, colHeight };
00311   return config;
00312 }
00313 
00314 // XXX copied from nsBlockFrame, should this be moved to nsContainerFrame?
00315 static void
00316 PlaceFrameView(nsIFrame* aFrame)
00317 {
00318   if (aFrame->HasView())
00319     nsContainerFrame::PositionFrameView(aFrame);
00320   else
00321     nsContainerFrame::PositionChildViews(aFrame);
00322 }
00323 
00324 static void MoveChildTo(nsIFrame* aParent, nsIFrame* aChild, nsPoint aOrigin) {
00325   if (aChild->GetPosition() == aOrigin) {
00326     return;
00327   }
00328   
00329   nsRect* overflowArea = aChild->GetOverflowAreaProperty(PR_FALSE);
00330   nsRect r = overflowArea ? *overflowArea : nsRect(nsPoint(0, 0), aChild->GetSize());
00331   r += aChild->GetPosition();
00332   aParent->Invalidate(r);
00333   r -= aChild->GetPosition();
00334   aChild->SetPosition(aOrigin);
00335   r += aOrigin;
00336   aParent->Invalidate(r);
00337   PlaceFrameView(aChild);
00338 }
00339 
00340 PRBool
00341 nsColumnSetFrame::ReflowChildren(nsHTMLReflowMetrics&     aDesiredSize,
00342                                  const nsHTMLReflowState& aReflowState,
00343                                  nsReflowReason           aKidReason,
00344                                  nsReflowStatus&          aStatus,
00345                                  const ReflowConfig&      aConfig,
00346                                  PRBool                   aUnboundedLastColumn,
00347                                  nsCollapsingMargin*      aBottomMarginCarriedOut) {
00348   PRBool allFit = PR_TRUE;
00349   PRBool RTL = GetStyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL;
00350   PRBool shrinkingHeightOnly = aKidReason == eReflowReason_Resize &&
00351     mLastBalanceHeight > aConfig.mColMaxHeight;
00352   
00353 #ifdef DEBUG_roc
00354   printf("*** Doing column reflow pass: mLastBalanceHeight=%d, mColMaxHeight=%d, RTL=%d\n, mBalanceColCount=%d, mColWidth=%d, mColGap=%d\n",
00355          mLastBalanceHeight, aConfig.mColMaxHeight, RTL, aConfig.mBalanceColCount,
00356          aConfig.mColWidth, aConfig.mColGap);
00357 #endif
00358 
00359   DrainOverflowColumns();
00360   
00361   if (mLastBalanceHeight != aConfig.mColMaxHeight) {
00362     mLastBalanceHeight = aConfig.mColMaxHeight;
00363     // XXX Seems like this could fire if incremental reflow pushed the column set
00364     // down so we reflow incrementally with a different available height.
00365     // We need a way to do an incremental reflow and be sure availableHeight
00366     // changes are taken account of! Right now I think block frames with absolute
00367     // children might exit early.
00368     NS_ASSERTION(aKidReason != eReflowReason_Incremental,
00369                  "incremental reflow should not have changed the balance height");
00370   }
00371 
00372   // get our border and padding
00373   const nsMargin &borderPadding = aReflowState.mComputedBorderPadding;
00374   
00375   nsRect contentRect(0, 0, 0, 0);
00376   aDesiredSize.mMaxElementWidth = 0;
00377   nsRect overflowRect(0, 0, 0, 0);
00378   
00379   nsIFrame* child = mFrames.FirstChild();
00380   nsPoint childOrigin = nsPoint(borderPadding.left, borderPadding.top);
00381   // For RTL, figure out where the last column's left edge should be. Since the
00382   // columns might not fill the frame exactly, we need to account for the
00383   // slop. Otherwise we'll waste time moving the columns by some tiny
00384   // amount unnecessarily.
00385   nscoord targetX = borderPadding.left;
00386   if (RTL) {
00387     nscoord availWidth = aReflowState.availableWidth;
00388     if (aReflowState.mComputedWidth != NS_INTRINSICSIZE) {
00389       availWidth = aReflowState.mComputedWidth;
00390     }
00391     if (availWidth != NS_INTRINSICSIZE) {
00392       childOrigin.x += availWidth - aConfig.mColWidth;
00393       targetX += aConfig.mExpectedWidthLeftOver;
00394 #ifdef DEBUG_roc
00395       printf("*** childOrigin.x = %d\n", childOrigin.x);
00396 #endif
00397     }
00398   }
00399   int columnCount = 0;
00400   PRBool reflowNext = PR_FALSE;
00401 
00402   while (child) {
00403     // Try to skip reflowing the child. We can't skip if the child is dirty. We also can't
00404     // skip if the next column is dirty, because the next column's first line(s)
00405     // might be pullable back to this column. We can't skip if it's the last child
00406     // because we need to obtain the bottom margin.
00407     PRBool skipIncremental = aKidReason == eReflowReason_Incremental
00408       && !(child->GetStateBits() & NS_FRAME_IS_DIRTY)
00409       && child->GetNextSibling()
00410       && !(child->GetNextSibling()->GetStateBits() & NS_FRAME_IS_DIRTY)
00411       && !aDesiredSize.mComputeMEW;
00412     // If we need to pull up content from the prev-in-flow then this is not just
00413     // a height shrink. The prev in flow will have set the dirty bit.
00414     PRBool skipResizeHeightShrink = shrinkingHeightOnly
00415       && child->GetSize().height <= aConfig.mColMaxHeight
00416       && !(child->GetStateBits() & NS_FRAME_IS_DIRTY);
00417     if (!reflowNext && (skipIncremental || skipResizeHeightShrink)) {
00418       // This child does not need to be reflowed, but we may need to move it
00419       MoveChildTo(this, child, childOrigin);
00420       
00421       // If this is the last frame then make sure we get the right status
00422       if (child->GetNextSibling()) {
00423         aStatus = NS_FRAME_NOT_COMPLETE;
00424       } else {
00425         aStatus = mLastFrameStatus;
00426       }
00427 #ifdef DEBUG_roc
00428       printf("*** Skipping child #%d %p (incremental %d, resize height shrink %d): status = %d\n",
00429              columnCount, (void*)child, skipIncremental, skipResizeHeightShrink, aStatus);
00430 #endif
00431     } else {
00432       nsSize availSize(aConfig.mColWidth, aConfig.mColMaxHeight);
00433       
00434       if (aUnboundedLastColumn && columnCount == aConfig.mBalanceColCount - 1) {
00435         availSize.height = GetAvailableContentHeight(aReflowState);
00436       }
00437   
00438       nsReflowReason tmpReason = aKidReason;
00439       if (reflowNext && aKidReason == eReflowReason_Incremental
00440           && !(child->GetStateBits() & NS_FRAME_IS_DIRTY)) {
00441         // If this frame was not being incrementally reflowed but was
00442         // just reflowed because the previous frame wants us to
00443         // reflow, then force this child to reflow its dirty lines!
00444         // XXX what we should really do here is add the child block to
00445         // the incremental reflow path! Currently I think if there's an
00446         // incremental reflow targeted only at the absolute frames of a
00447         // column, then the column will be dirty BUT reflowing it will
00448         // not reflow any lines affected by the prev-in-flow!
00449         tmpReason = eReflowReason_Dirty;
00450       }
00451 
00452       nsHTMLReflowState kidReflowState(GetPresContext(), aReflowState, child,
00453                                        availSize, availSize.width,
00454                                        aReflowState.mComputedHeight, tmpReason);
00455       kidReflowState.mFlags.mIsTopOfPage = PR_TRUE;
00456           
00457 #ifdef DEBUG_roc
00458       printf("*** Reflowing child #%d %p: reason = %d, availHeight=%d\n",
00459              columnCount, (void*)child, tmpReason, availSize.height);
00460 #endif
00461 
00462       // Note if the column's next in flow is not being changed by this incremental reflow.
00463       // This may allow the current column to avoid trying to pull lines from the next column.
00464       if (child->GetNextSibling() && aKidReason == eReflowReason_Incremental &&
00465         !(child->GetNextSibling()->GetStateBits() & NS_FRAME_IS_DIRTY)) {
00466         kidReflowState.mFlags.mNextInFlowUntouched = PR_TRUE;
00467       }
00468     
00469       nsHTMLReflowMetrics kidDesiredSize(aDesiredSize.mComputeMEW, aDesiredSize.mFlags);
00470 
00471       // XXX it would be cool to consult the space manager for the
00472       // previous block to figure out the region of floats from the
00473       // previous column that extend into this column, and subtract
00474       // that region from the new space manager.  So you could stick a
00475       // really big float in the first column and text in following
00476       // columns would flow around it.
00477 
00478       // Reflow the frame
00479       ReflowChild(child, GetPresContext(), kidDesiredSize, kidReflowState,
00480                   childOrigin.x + kidReflowState.mComputedMargin.left,
00481                   childOrigin.y + kidReflowState.mComputedMargin.top,
00482                   0, aStatus);
00483 
00484       if (kidDesiredSize.height > aConfig.mColMaxHeight) {
00485         allFit = PR_FALSE;
00486       }
00487       
00488       reflowNext = (aStatus & NS_FRAME_REFLOW_NEXTINFLOW) != 0;
00489     
00490 #ifdef DEBUG_roc
00491       printf("*** Reflowed child #%d %p: status = %d, desiredSize=%d,%d\n",
00492              columnCount, (void*)child, aStatus, kidDesiredSize.width, kidDesiredSize.height);
00493 #endif
00494 
00495       NS_FRAME_TRACE_REFLOW_OUT("Column::Reflow", aStatus);
00496 
00497       *aBottomMarginCarriedOut = kidDesiredSize.mCarriedOutBottomMargin;
00498       
00499       FinishReflowChild(child, GetPresContext(), &kidReflowState, 
00500                         kidDesiredSize, childOrigin.x, childOrigin.y, 0);
00501 
00502       if (aDesiredSize.mComputeMEW) {
00503         aDesiredSize.mMaxElementWidth = PR_MAX(aDesiredSize.mMaxElementWidth,
00504                                                kidDesiredSize.mMaxElementWidth);
00505       }
00506     }
00507 
00508     contentRect.UnionRect(contentRect, child->GetRect());
00509 
00510     ConsiderChildOverflow(overflowRect, child);
00511 
00512     // Build a continuation column if necessary
00513     nsIFrame* kidNextInFlow = child->GetNextInFlow();
00514 
00515     if (NS_FRAME_IS_COMPLETE(aStatus) && !NS_FRAME_IS_TRUNCATED(aStatus)) {
00516       NS_ASSERTION(!kidNextInFlow, "next in flow should have been deleted");
00517       break;
00518     } else {
00519       ++columnCount;
00520       // Make sure that the column has a next-in-flow. If not, we must
00521       // create one to hold the overflowing stuff, even if we're just
00522       // going to put it on our overflow list and let *our*
00523       // next in flow handle it.
00524       if (!kidNextInFlow) {
00525         NS_ASSERTION(aStatus & NS_FRAME_REFLOW_NEXTINFLOW,
00526                      "We have to create a continuation, but the block doesn't want us to reflow it?");
00527 
00528         // We need to create a continuing column
00529         nsresult rv = CreateNextInFlow(GetPresContext(), this, child, kidNextInFlow);
00530         
00531         if (NS_FAILED(rv)) {
00532           NS_NOTREACHED("Couldn't create continuation");
00533           break;
00534         }
00535         
00536         kidNextInFlow->AddStateBits(NS_BLOCK_SPACE_MGR);
00537 
00538         // Do an initial reflow if we're going to reflow this thing.
00539         aKidReason = eReflowReason_Initial;
00540       }
00541         
00542       if (columnCount >= aConfig.mBalanceColCount) {
00543         // No more columns allowed here. Stop.
00544         aStatus |= NS_FRAME_REFLOW_NEXTINFLOW;
00545         kidNextInFlow->AddStateBits(NS_FRAME_IS_DIRTY);
00546         
00547         // Move any of our leftover columns to our overflow list. Our
00548         // next-in-flow will eventually pick them up.
00549         nsIFrame* continuationColumns = child->GetNextSibling();
00550         if (continuationColumns) {
00551           SetOverflowFrames(GetPresContext(), continuationColumns);
00552           child->SetNextSibling(nsnull);
00553         }
00554         break;
00555       }
00556     }
00557 
00558     // Advance to the next column
00559     child = child->GetNextSibling();
00560 
00561     if (child) {
00562       if (!RTL) {
00563         childOrigin.x += aConfig.mColWidth + aConfig.mColGap;
00564       } else {
00565         childOrigin.x -= aConfig.mColWidth + aConfig.mColGap;
00566       }
00567       
00568 #ifdef DEBUG_roc
00569       printf("*** NEXT CHILD ORIGIN.x = %d\n", childOrigin.x);
00570 #endif
00571     }
00572   }
00573   
00574   // If we're doing RTL, we need to make sure our last column is at the left-hand side of the frame.
00575   if (RTL && childOrigin.x != targetX) {
00576     overflowRect = nsRect(0, 0, 0, 0);
00577     contentRect = nsRect(0, 0, 0, 0);
00578     PRInt32 deltaX = targetX - childOrigin.x;
00579 #ifdef DEBUG_roc
00580     printf("*** CHILDORIGIN.x = %d, targetX = %d, DELTAX = %d\n", childOrigin.x, targetX, deltaX);
00581 #endif
00582     for (child = mFrames.FirstChild(); child; child = child->GetNextSibling()) {
00583       MoveChildTo(this, child, child->GetPosition() + nsPoint(deltaX, 0));
00584       ConsiderChildOverflow(overflowRect, child);
00585       contentRect.UnionRect(contentRect, child->GetRect());
00586     }
00587   }
00588 
00589   mLastFrameStatus = aStatus;
00590   
00591   // contentRect included the borderPadding.left,borderPadding.top of the child rects
00592   contentRect -= nsPoint(borderPadding.left, borderPadding.top);
00593   
00594   nsSize contentSize = nsSize(contentRect.XMost(), contentRect.YMost());
00595 
00596   // Apply computed and min/max values
00597   if (aReflowState.mComputedHeight != NS_INTRINSICSIZE) {
00598     contentSize.height = aReflowState.mComputedHeight;
00599   } else {
00600     if (NS_UNCONSTRAINEDSIZE != aReflowState.mComputedMaxHeight) {
00601       contentSize.height = PR_MIN(aReflowState.mComputedMaxHeight, contentSize.height);
00602     }
00603     if (NS_UNCONSTRAINEDSIZE != aReflowState.mComputedMinHeight) {
00604       contentSize.height = PR_MAX(aReflowState.mComputedMinHeight, contentSize.height);
00605     }
00606   }
00607   if (aReflowState.mComputedWidth != NS_INTRINSICSIZE) {
00608     contentSize.width = aReflowState.mComputedWidth;
00609   } else {
00610     if (NS_UNCONSTRAINEDSIZE != aReflowState.mComputedMaxWidth) {
00611       contentSize.width = PR_MIN(aReflowState.mComputedMaxWidth, contentSize.width);
00612     }
00613     if (NS_UNCONSTRAINEDSIZE != aReflowState.mComputedMinWidth) {
00614       contentSize.width = PR_MAX(aReflowState.mComputedMinWidth, contentSize.width);
00615     }
00616   }
00617     
00618   aDesiredSize.height = borderPadding.top + contentSize.height +
00619     borderPadding.bottom;
00620   aDesiredSize.width = contentSize.width + borderPadding.left + borderPadding.right;
00621   aDesiredSize.ascent  = aDesiredSize.height;
00622   aDesiredSize.descent = 0;
00623   aDesiredSize.mMaximumWidth = aDesiredSize.width;
00624   if (aDesiredSize.mComputeMEW) {
00625     // add in padding.
00626     aDesiredSize.mMaxElementWidth += borderPadding.left + borderPadding.right;
00627   }
00628   overflowRect.UnionRect(overflowRect, nsRect(0, 0, aDesiredSize.width, aDesiredSize.height));
00629   aDesiredSize.mOverflowArea = overflowRect;
00630   
00631 #ifdef DEBUG_roc
00632   printf("*** DONE PASS feasible=%d\n", allFit && NS_FRAME_IS_COMPLETE(aStatus)
00633          && !NS_FRAME_IS_TRUNCATED(aStatus));
00634 #endif
00635   return allFit && NS_FRAME_IS_COMPLETE(aStatus)
00636     && !NS_FRAME_IS_TRUNCATED(aStatus);
00637 }
00638 
00639 static nscoord ComputeSumOfChildHeights(nsIFrame* aFrame) {
00640   nscoord totalHeight = 0;
00641   for (nsIFrame* f = aFrame->GetFirstChild(nsnull); f; f = f->GetNextSibling()) {
00642     // individual columns don't have borders or padding so this is a
00643     // reasonable way to get their content height
00644     totalHeight += f->GetSize().height;
00645   }
00646   return totalHeight;
00647 }
00648 
00649 void
00650 nsColumnSetFrame::DrainOverflowColumns()
00651 {
00652   // First grab the prev-in-flows overflows and reparent them to this
00653   // frame.
00654   nsColumnSetFrame* prev = NS_STATIC_CAST(nsColumnSetFrame*, mPrevInFlow);
00655   if (prev) {
00656     nsIFrame* overflows = prev->GetOverflowFrames(GetPresContext(), PR_TRUE);
00657     if (overflows) {
00658       // Make all the frames on the overflow list mine
00659       nsIFrame* lastFrame = nsnull;
00660       for (nsIFrame* f = overflows; f; f = f->GetNextSibling()) {
00661         f->SetParent(this);
00662 
00663         // When pushing and pulling frames we need to check for whether any
00664         // views need to be reparented
00665         nsHTMLContainerFrame::ReparentFrameView(GetPresContext(), f, prev, this);
00666 
00667         // Get the next frame
00668         lastFrame = f;
00669       }
00670 
00671       NS_ASSERTION(lastFrame, "overflow list was created with no frames");
00672       lastFrame->SetNextSibling(mFrames.FirstChild());
00673       
00674       mFrames.SetFrames(overflows);
00675     }
00676   }
00677   
00678   // Now pull back our own overflows and append them to our children.
00679   // We don't need to reparent them since we're already their parent.
00680   nsIFrame* overflows = GetOverflowFrames(GetPresContext(), PR_TRUE);
00681   if (overflows) {
00682     mFrames.AppendFrames(this, overflows);
00683   }
00684 }
00685 
00686 NS_IMETHODIMP 
00687 nsColumnSetFrame::Reflow(nsPresContext*          aPresContext,
00688                       nsHTMLReflowMetrics&     aDesiredSize,
00689                       const nsHTMLReflowState& aReflowState,
00690                       nsReflowStatus&          aStatus)
00691 {
00692   DO_GLOBAL_REFLOW_COUNT("nsColumnSetFrame", aReflowState.reason);
00693   DISPLAY_REFLOW(aPresContext, this, aReflowState, aDesiredSize, aStatus);
00694 
00695   // Initialize OUT parameter
00696   aStatus = NS_FRAME_COMPLETE;
00697 
00698   //------------ Handle Incremental Reflow -----------------
00699   nsReflowReason kidReason = aReflowState.reason;
00700 
00701   if ( aReflowState.reason == eReflowReason_Incremental ) {
00702     nsHTMLReflowCommand *command = aReflowState.path->mReflowCommand;
00703     
00704     // Dirty any frames on the incremental reflow path
00705     nsReflowPath *path = aReflowState.path;
00706     nsReflowPath::iterator iter = path->FirstChild();
00707     nsReflowPath::iterator end = path->EndChildren();
00708     for ( ; iter != end; ++iter) {
00709       (*iter)->AddStateBits(NS_FRAME_IS_DIRTY);
00710     }
00711 
00712     // See if it's targeted at us
00713     if (command) {
00714       switch (command->Type()) {
00715         
00716       case eReflowType_StyleChanged:
00717         kidReason = eReflowReason_StyleChange;
00718         break;
00719         
00720         // if its a dirty type then reflow us with a dirty reflow
00721       case eReflowType_ReflowDirty:
00722         kidReason = eReflowReason_Dirty;
00723         break;
00724 
00725       default:
00726         NS_ERROR("Unexpected Reflow Type");
00727       }
00728     }
00729   }
00730 
00731   ReflowConfig config = ChooseColumnStrategy(aReflowState);
00732   PRBool isBalancing = config.mBalanceColCount < PR_INT32_MAX;
00733   
00734   // If balancing, then we allow the last column to grow to unbounded
00735   // height during the first reflow. This gives us a way to estimate
00736   // what the average column height should be, because we can measure
00737   // the heights of all the columns and sum them up. But don't do this
00738   // if we have a next in flow because we don't want to suck all its
00739   // content back here and then have to push it out again!
00740   nsIFrame* nextInFlow = GetNextInFlow();
00741   PRBool unboundedLastColumn = isBalancing && nextInFlow;
00742   nsCollapsingMargin carriedOutBottomMargin;
00743   PRBool feasible = ReflowChildren(aDesiredSize, aReflowState, kidReason,
00744     aStatus, config, unboundedLastColumn, &carriedOutBottomMargin);
00745 
00746   if (isBalancing) {
00747     if (feasible ||
00748       // All children were reflowed as necessary, so we can go ahead
00749       // and do resize reflows from now on
00750         kidReason != eReflowReason_StyleChange) {
00751       // Any non-stylechange reflow can be followed by resize
00752       // reflows. But a stylechange reflow demands that all children
00753       // be reflowed, which may not have happened yet; some of them
00754       // might just have been pushed to an overflow list. So we have to
00755       // keep doing stylechange reflows.
00756       kidReason = eReflowReason_Resize;
00757     }
00758 
00759     nscoord availableContentHeight = GetAvailableContentHeight(aReflowState);
00760   
00761     // Termination of the algorithm below is guaranteed because
00762     // knownFeasibleHeight - knownInfeasibleHeight decreases in every
00763     // iteration.
00764     nscoord knownFeasibleHeight = NS_INTRINSICSIZE;
00765     nscoord knownInfeasibleHeight = 0;
00766     // We set this flag when we detect that we may contain a frame
00767     // that can break anywhere (thus foiling the linear decrease-by-one
00768     // search)
00769     PRBool maybeContinuousBreakingDetected = PR_FALSE;
00770 
00771     while (1) {
00772       nscoord lastKnownFeasibleHeight = knownFeasibleHeight;
00773 
00774       nscoord maxHeight = 0;
00775       for (nsIFrame* f = mFrames.FirstChild(); f; f = f->GetNextSibling()) {
00776         maxHeight = PR_MAX(maxHeight, f->GetSize().height);
00777       }
00778 
00779       // Record what we learned from the last reflow
00780       if (feasible) {
00781         // maxHeight is feasible (and always maxHeight <=
00782         // mLastBalanceHeight)
00783         knownFeasibleHeight = PR_MIN(knownFeasibleHeight, maxHeight);
00784 
00785         // Furthermore, no height less than the height of the last
00786         // column can ever be feasible.
00787         if (mFrames.GetLength() == config.mBalanceColCount) {
00788           knownInfeasibleHeight = PR_MAX(knownInfeasibleHeight,
00789                                          mFrames.LastChild()->GetSize().height - 1);
00790         }
00791       } else {
00792         knownInfeasibleHeight = PR_MAX(knownInfeasibleHeight, mLastBalanceHeight);
00793 
00794         if (unboundedLastColumn) {
00795           // The last column is unbounded, so all content got reflowed, so the
00796           // maxHeight is feasible.
00797           knownFeasibleHeight = PR_MIN(knownFeasibleHeight, maxHeight);
00798         }
00799       }
00800 
00801 #ifdef DEBUG_roc
00802       printf("*** nsColumnSetFrame::Reflow balancing knownInfeasible=%d knownFeasible=%d\n",
00803              knownInfeasibleHeight, knownFeasibleHeight);
00804 #endif
00805 
00806       if (knownInfeasibleHeight >= knownFeasibleHeight - 1) {
00807         // knownFeasibleHeight is where we want to be
00808         break;
00809       }
00810 
00811       if (knownInfeasibleHeight >= availableContentHeight) {
00812         break;
00813       }
00814 
00815       if (lastKnownFeasibleHeight - knownFeasibleHeight == 1) {
00816         // We decreased the feasible height by one twip only. This could
00817         // indicate that there is a continuously breakable child frame
00818         // that we are crawling through.
00819         maybeContinuousBreakingDetected = PR_TRUE;
00820       }
00821 
00822       nscoord nextGuess = (knownFeasibleHeight + knownInfeasibleHeight)/2;
00823       // The constant of 600 twips is arbitrary. It's about two line-heights.
00824       if (knownFeasibleHeight - nextGuess < 600 &&
00825           !maybeContinuousBreakingDetected) {
00826         // We're close to our target, so just try shrinking just the
00827         // minimum amount that will cause one of our columns to break
00828         // differently.
00829         nextGuess = knownFeasibleHeight - 1;
00830       } else if (unboundedLastColumn) {
00831         // Make a guess by dividing that into N columns. Add some slop
00832         // to try to make it on the feasible side.  The constant of
00833         // 600 twips is arbitrary. It's about two line-heights.
00834         nextGuess = ComputeSumOfChildHeights(this)/config.mBalanceColCount + 600;
00835         // Sanitize it
00836         nextGuess = PR_MIN(PR_MAX(nextGuess, knownInfeasibleHeight + 1),
00837                            knownFeasibleHeight - 1);
00838       } else if (knownFeasibleHeight == NS_INTRINSICSIZE) {
00839         // This can happen when we had a next-in-flow so we didn't
00840         // want to do an unbounded height measuring step. Let's just increase
00841         // from the infeasible height by some reasonable amount.
00842         nextGuess = knownInfeasibleHeight*2 + 600;
00843       }
00844       // Don't bother guessing more than our height constraint.
00845       nextGuess = PR_MIN(availableContentHeight, nextGuess);
00846 
00847 #ifdef DEBUG_roc
00848       printf("*** nsColumnSetFrame::Reflow balancing choosing next guess=%d\n", nextGuess);
00849 #endif
00850 
00851       config.mColMaxHeight = nextGuess;
00852       
00853       unboundedLastColumn = PR_FALSE;
00854       feasible = ReflowChildren(aDesiredSize, aReflowState,
00855                                 kidReason, aStatus, config, PR_FALSE, 
00856                                 &carriedOutBottomMargin);
00857     }
00858 
00859     if (!feasible) {
00860       // We may need to reflow one more time at the feasible height to
00861       // get a valid layout.
00862       PRBool skip = PR_FALSE;
00863       if (knownInfeasibleHeight >= availableContentHeight) {
00864         config.mColMaxHeight = availableContentHeight;
00865         if (mLastBalanceHeight == availableContentHeight) {
00866           skip = PR_TRUE;
00867         }
00868       } else {
00869         config.mColMaxHeight = knownFeasibleHeight;
00870       }
00871       if (!skip) {
00872         ReflowChildren(aDesiredSize, aReflowState, eReflowReason_Resize,
00873                        aStatus, config, PR_FALSE, &carriedOutBottomMargin);
00874       }
00875     }
00876   }
00877   
00878   CheckInvalidateSizeChange(GetPresContext(), aDesiredSize, aReflowState);
00879 
00880   FinishAndStoreOverflow(&aDesiredSize);
00881   aDesiredSize.mCarriedOutBottomMargin = carriedOutBottomMargin;
00882 
00883   NS_FRAME_SET_TRUNCATION(aStatus, aReflowState, aDesiredSize);
00884 
00885   return NS_OK;
00886 }
00887 
00888 PRIntn
00889 nsColumnSetFrame::GetSkipSides() const
00890 {
00891   return 0;
00892 }
00893 
00894 NS_IMETHODIMP
00895 nsColumnSetFrame::AppendFrames(nsIAtom*        aListName,
00896                                nsIFrame*       aFrameList)
00897 {
00898   NS_NOTREACHED("AppendFrames not supported");
00899   return NS_ERROR_NOT_IMPLEMENTED;
00900 }
00901 
00902 NS_IMETHODIMP
00903 nsColumnSetFrame::InsertFrames(nsIAtom*        aListName,
00904                                nsIFrame*       aPrevFrame,
00905                                nsIFrame*       aFrameList)
00906 {
00907   NS_NOTREACHED("InsertFrames not supported");
00908   return NS_ERROR_NOT_IMPLEMENTED;
00909 }
00910 
00911 NS_IMETHODIMP
00912 nsColumnSetFrame::RemoveFrame(nsIAtom*        aListName,
00913                               nsIFrame*       aOldFrame)
00914 {
00915   NS_NOTREACHED("RemoveFrame not supported");
00916   return NS_ERROR_NOT_IMPLEMENTED;
00917 }