michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /* rendering object for css3 multi-column layout */
michael@0: 
michael@0: #include "nsColumnSetFrame.h"
michael@0: #include "nsCSSRendering.h"
michael@0: #include "nsDisplayList.h"
michael@0: 
michael@0: using namespace mozilla;
michael@0: using namespace mozilla::layout;
michael@0: 
michael@0: /**
michael@0:  * Tracking issues:
michael@0:  *
michael@0:  * XXX cursor movement around the top and bottom of colums seems to make the editor
michael@0:  * lose the caret.
michael@0:  *
michael@0:  * XXX should we support CSS columns applied to table elements?
michael@0:  */
michael@0: nsIFrame*
michael@0: NS_NewColumnSetFrame(nsIPresShell* aPresShell, nsStyleContext* aContext, nsFrameState aStateFlags)
michael@0: {
michael@0:   nsColumnSetFrame* it = new (aPresShell) nsColumnSetFrame(aContext);
michael@0:   it->AddStateBits(aStateFlags | NS_BLOCK_MARGIN_ROOT);
michael@0:   return it;
michael@0: }
michael@0: 
michael@0: NS_IMPL_FRAMEARENA_HELPERS(nsColumnSetFrame)
michael@0: 
michael@0: nsColumnSetFrame::nsColumnSetFrame(nsStyleContext* aContext)
michael@0:   : nsContainerFrame(aContext), mLastBalanceHeight(NS_INTRINSICSIZE),
michael@0:     mLastFrameStatus(NS_FRAME_COMPLETE)
michael@0: {
michael@0: }
michael@0: 
michael@0: nsIAtom*
michael@0: nsColumnSetFrame::GetType() const
michael@0: {
michael@0:   return nsGkAtoms::columnSetFrame;
michael@0: }
michael@0: 
michael@0: static void
michael@0: PaintColumnRule(nsIFrame* aFrame, nsRenderingContext* aCtx,
michael@0:                 const nsRect& aDirtyRect, nsPoint aPt)
michael@0: {
michael@0:   static_cast<nsColumnSetFrame*>(aFrame)->PaintColumnRule(aCtx, aDirtyRect, aPt);
michael@0: }
michael@0: 
michael@0: void
michael@0: nsColumnSetFrame::PaintColumnRule(nsRenderingContext* aCtx,
michael@0:                                   const nsRect& aDirtyRect,
michael@0:                                   const nsPoint& aPt)
michael@0: {
michael@0:   nsIFrame* child = mFrames.FirstChild();
michael@0:   if (!child)
michael@0:     return;  // no columns
michael@0: 
michael@0:   nsIFrame* nextSibling = child->GetNextSibling();
michael@0:   if (!nextSibling)
michael@0:     return;  // 1 column only - this means no gap to draw on
michael@0: 
michael@0:   bool isRTL = StyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL;
michael@0:   const nsStyleColumn* colStyle = StyleColumn();
michael@0: 
michael@0:   uint8_t ruleStyle;
michael@0:   // Per spec, inset => ridge and outset => groove
michael@0:   if (colStyle->mColumnRuleStyle == NS_STYLE_BORDER_STYLE_INSET)
michael@0:     ruleStyle = NS_STYLE_BORDER_STYLE_RIDGE;
michael@0:   else if (colStyle->mColumnRuleStyle == NS_STYLE_BORDER_STYLE_OUTSET)
michael@0:     ruleStyle = NS_STYLE_BORDER_STYLE_GROOVE;
michael@0:   else
michael@0:     ruleStyle = colStyle->mColumnRuleStyle;
michael@0: 
michael@0:   nsPresContext* presContext = PresContext();
michael@0:   nscoord ruleWidth = colStyle->GetComputedColumnRuleWidth();
michael@0:   if (!ruleWidth)
michael@0:     return;
michael@0: 
michael@0:   nscolor ruleColor =
michael@0:     GetVisitedDependentColor(eCSSProperty__moz_column_rule_color);
michael@0: 
michael@0:   // In order to re-use a large amount of code, we treat the column rule as a border.
michael@0:   // We create a new border style object and fill in all the details of the column rule as
michael@0:   // the left border. PaintBorder() does all the rendering for us, so we not
michael@0:   // only save an enormous amount of code but we'll support all the line styles that
michael@0:   // we support on borders!
michael@0:   nsStyleBorder border(presContext);
michael@0:   border.SetBorderWidth(NS_SIDE_LEFT, ruleWidth);
michael@0:   border.SetBorderStyle(NS_SIDE_LEFT, ruleStyle);
michael@0:   border.SetBorderColor(NS_SIDE_LEFT, ruleColor);
michael@0: 
michael@0:   // Get our content rect as an absolute coordinate, not relative to
michael@0:   // our parent (which is what the X and Y normally is)
michael@0:   nsRect contentRect = GetContentRect() - GetRect().TopLeft() + aPt;
michael@0:   nsSize ruleSize(ruleWidth, contentRect.height);
michael@0: 
michael@0:   while (nextSibling) {
michael@0:     // The frame tree goes RTL in RTL
michael@0:     nsIFrame* leftSibling = isRTL ? nextSibling : child;
michael@0:     nsIFrame* rightSibling = isRTL ? child : nextSibling;
michael@0: 
michael@0:     // Each child frame's position coordinates is actually relative to this nsColumnSetFrame.
michael@0:     // linePt will be at the top-left edge to paint the line.
michael@0:     nsPoint edgeOfLeftSibling = leftSibling->GetRect().TopRight() + aPt;
michael@0:     nsPoint edgeOfRightSibling = rightSibling->GetRect().TopLeft() + aPt;
michael@0:     nsPoint linePt((edgeOfLeftSibling.x + edgeOfRightSibling.x - ruleWidth) / 2,
michael@0:                    contentRect.y);
michael@0: 
michael@0:     nsRect lineRect(linePt, ruleSize);
michael@0:     nsCSSRendering::PaintBorderWithStyleBorder(presContext, *aCtx, this,
michael@0:         aDirtyRect, lineRect, border, StyleContext(),
michael@0:         // Remember, we only have the "left" "border". Skip everything else
michael@0:         (1 << NS_SIDE_TOP | 1 << NS_SIDE_RIGHT | 1 << NS_SIDE_BOTTOM));
michael@0: 
michael@0:     child = nextSibling;
michael@0:     nextSibling = nextSibling->GetNextSibling();
michael@0:   }
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsColumnSetFrame::SetInitialChildList(ChildListID     aListID,
michael@0:                                       nsFrameList&    aChildList)
michael@0: {
michael@0:   if (aListID == kAbsoluteList) {
michael@0:     return nsContainerFrame::SetInitialChildList(aListID, aChildList);
michael@0:   }
michael@0: 
michael@0:   NS_ASSERTION(aListID == kPrincipalList,
michael@0:                "Only default child list supported");
michael@0:   NS_ASSERTION(aChildList.OnlyChild(),
michael@0:                "initial child list must have exaisRevertingctly one child");
michael@0:   // Queue up the frames for the content frame
michael@0:   return nsContainerFrame::SetInitialChildList(kPrincipalList, aChildList);
michael@0: }
michael@0: 
michael@0: static nscoord
michael@0: GetAvailableContentWidth(const nsHTMLReflowState& aReflowState)
michael@0: {
michael@0:   if (aReflowState.AvailableWidth() == NS_INTRINSICSIZE) {
michael@0:     return NS_INTRINSICSIZE;
michael@0:   }
michael@0:   nscoord borderPaddingWidth =
michael@0:     aReflowState.ComputedPhysicalBorderPadding().left +
michael@0:     aReflowState.ComputedPhysicalBorderPadding().right;
michael@0:   return std::max(0, aReflowState.AvailableWidth() - borderPaddingWidth);
michael@0: }
michael@0: 
michael@0: nscoord
michael@0: nsColumnSetFrame::GetAvailableContentHeight(const nsHTMLReflowState& aReflowState)
michael@0: {
michael@0:   if (aReflowState.AvailableHeight() == NS_INTRINSICSIZE) {
michael@0:     return NS_INTRINSICSIZE;
michael@0:   }
michael@0: 
michael@0:   nsMargin bp = aReflowState.ComputedPhysicalBorderPadding();
michael@0:   ApplySkipSides(bp, &aReflowState);
michael@0:   bp.bottom = aReflowState.ComputedPhysicalBorderPadding().bottom;
michael@0:   return std::max(0, aReflowState.AvailableHeight() - bp.TopBottom());
michael@0: }
michael@0: 
michael@0: static nscoord
michael@0: GetColumnGap(nsColumnSetFrame*    aFrame,
michael@0:              const nsStyleColumn* aColStyle)
michael@0: {
michael@0:   if (eStyleUnit_Normal == aColStyle->mColumnGap.GetUnit())
michael@0:     return aFrame->StyleFont()->mFont.size;
michael@0:   if (eStyleUnit_Coord == aColStyle->mColumnGap.GetUnit()) {
michael@0:     nscoord colGap = aColStyle->mColumnGap.GetCoordValue();
michael@0:     NS_ASSERTION(colGap >= 0, "negative column gap");
michael@0:     return colGap;
michael@0:   }
michael@0: 
michael@0:   NS_NOTREACHED("Unknown gap type");
michael@0:   return 0;
michael@0: }
michael@0: 
michael@0: nsColumnSetFrame::ReflowConfig
michael@0: nsColumnSetFrame::ChooseColumnStrategy(const nsHTMLReflowState& aReflowState,
michael@0:                                        bool aForceAuto = false,
michael@0:                                        nscoord aFeasibleHeight = NS_INTRINSICSIZE,
michael@0:                                        nscoord aInfeasibleHeight = 0)
michael@0: 
michael@0: {
michael@0:   nscoord knownFeasibleHeight = aFeasibleHeight;
michael@0:   nscoord knownInfeasibleHeight = aInfeasibleHeight;
michael@0: 
michael@0:   const nsStyleColumn* colStyle = StyleColumn();
michael@0:   nscoord availContentWidth = GetAvailableContentWidth(aReflowState);
michael@0:   if (aReflowState.ComputedWidth() != NS_INTRINSICSIZE) {
michael@0:     availContentWidth = aReflowState.ComputedWidth();
michael@0:   }
michael@0: 
michael@0:   nscoord consumedHeight = GetConsumedHeight();
michael@0: 
michael@0:   // The effective computed height is the height of the current continuation
michael@0:   // of the column set frame. This should be the same as the computed height
michael@0:   // if we have an unconstrained available height.
michael@0:   nscoord computedHeight = GetEffectiveComputedHeight(aReflowState,
michael@0:                                                       consumedHeight);
michael@0:   nscoord colHeight = GetAvailableContentHeight(aReflowState);
michael@0: 
michael@0:   if (aReflowState.ComputedHeight() != NS_INTRINSICSIZE) {
michael@0:     colHeight = aReflowState.ComputedHeight();
michael@0:   } else if (aReflowState.ComputedMaxHeight() != NS_INTRINSICSIZE) {
michael@0:     colHeight = std::min(colHeight, aReflowState.ComputedMaxHeight());
michael@0:   }
michael@0: 
michael@0:   nscoord colGap = GetColumnGap(this, colStyle);
michael@0:   int32_t numColumns = colStyle->mColumnCount;
michael@0: 
michael@0:   // If column-fill is set to 'balance', then we want to balance the columns.
michael@0:   const bool isBalancing = colStyle->mColumnFill == NS_STYLE_COLUMN_FILL_BALANCE
michael@0:                            && !aForceAuto;
michael@0:   if (isBalancing) {
michael@0:     const uint32_t MAX_NESTED_COLUMN_BALANCING = 2;
michael@0:     uint32_t cnt = 0;
michael@0:     for (const nsHTMLReflowState* rs = aReflowState.parentReflowState;
michael@0:          rs && cnt < MAX_NESTED_COLUMN_BALANCING; rs = rs->parentReflowState) {
michael@0:       if (rs->mFlags.mIsColumnBalancing) {
michael@0:         ++cnt;
michael@0:       }
michael@0:     }
michael@0:     if (cnt == MAX_NESTED_COLUMN_BALANCING) {
michael@0:       numColumns = 1;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   nscoord colWidth;
michael@0:   if (colStyle->mColumnWidth.GetUnit() == eStyleUnit_Coord) {
michael@0:     colWidth = colStyle->mColumnWidth.GetCoordValue();
michael@0:     NS_ASSERTION(colWidth >= 0, "negative column width");
michael@0:     // Reduce column count if necessary to make columns fit in the
michael@0:     // available width. Compute max number of columns that fit in
michael@0:     // availContentWidth, satisfying colGap*(maxColumns - 1) +
michael@0:     // colWidth*maxColumns <= availContentWidth
michael@0:     if (availContentWidth != NS_INTRINSICSIZE && colGap + colWidth > 0
michael@0:         && numColumns > 0) {
michael@0:       // This expression uses truncated rounding, which is what we
michael@0:       // want
michael@0:       int32_t maxColumns =
michael@0:         std::min(nscoord(nsStyleColumn::kMaxColumnCount),
michael@0:                  (availContentWidth + colGap)/(colGap + colWidth));
michael@0:       numColumns = std::max(1, std::min(numColumns, maxColumns));
michael@0:     }
michael@0:   } else if (numColumns > 0 && availContentWidth != NS_INTRINSICSIZE) {
michael@0:     nscoord widthMinusGaps = availContentWidth - colGap*(numColumns - 1);
michael@0:     colWidth = widthMinusGaps/numColumns;
michael@0:   } else {
michael@0:     colWidth = NS_INTRINSICSIZE;
michael@0:   }
michael@0:   // Take care of the situation where there's only one column but it's
michael@0:   // still too wide
michael@0:   colWidth = std::max(1, std::min(colWidth, availContentWidth));
michael@0: 
michael@0:   nscoord expectedWidthLeftOver = 0;
michael@0: 
michael@0:   if (colWidth != NS_INTRINSICSIZE && availContentWidth != NS_INTRINSICSIZE) {
michael@0:     // distribute leftover space
michael@0: 
michael@0:     // First, determine how many columns will be showing if the column
michael@0:     // count is auto
michael@0:     if (numColumns <= 0) {
michael@0:       // choose so that colGap*(nominalColumnCount - 1) +
michael@0:       // colWidth*nominalColumnCount is nearly availContentWidth
michael@0:       // make sure to round down
michael@0:       if (colGap + colWidth > 0) {
michael@0:         numColumns = (availContentWidth + colGap)/(colGap + colWidth);
michael@0:         // The number of columns should never exceed kMaxColumnCount.
michael@0:         numColumns = std::min(nscoord(nsStyleColumn::kMaxColumnCount),
michael@0:                               numColumns);
michael@0:       }
michael@0:       if (numColumns <= 0) {
michael@0:         numColumns = 1;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     // Compute extra space and divide it among the columns
michael@0:     nscoord extraSpace =
michael@0:       std::max(0, availContentWidth - (colWidth*numColumns + colGap*(numColumns - 1)));
michael@0:     nscoord extraToColumns = extraSpace/numColumns;
michael@0:     colWidth += extraToColumns;
michael@0:     expectedWidthLeftOver = extraSpace - (extraToColumns*numColumns);
michael@0:   }
michael@0: 
michael@0:   if (isBalancing) {
michael@0:     if (numColumns <= 0) {
michael@0:       // Hmm, auto column count, column width or available width is unknown,
michael@0:       // and balancing is required. Let's just use one column then.
michael@0:       numColumns = 1;
michael@0:     }
michael@0:     colHeight = std::min(mLastBalanceHeight, colHeight);
michael@0:   } else {
michael@0:     // This is the case when the column-fill property is set to 'auto'.
michael@0:     // No balancing, so don't limit the column count
michael@0:     numColumns = INT32_MAX;
michael@0: 
michael@0:     // XXX_jwir3: If a page's height is set to 0, we could continually
michael@0:     //            create continuations, resulting in an infinite loop, since
michael@0:     //            no progress is ever made. This is an issue with the spec
michael@0:     //            (css3-multicol, css3-page, and css3-break) that is
michael@0:     //            unresolved as of 27 Feb 2013. For the time being, we set this
michael@0:     //            to have a minimum of 1 css px. Once a resolution is made
michael@0:     //            on what minimum to have for a page height, we may need to
michael@0:     //            change this value to match the appropriate spec(s).
michael@0:     colHeight = std::max(colHeight, nsPresContext::CSSPixelsToAppUnits(1));
michael@0:   }
michael@0: 
michael@0: #ifdef DEBUG_roc
michael@0:   printf("*** nsColumnSetFrame::ChooseColumnStrategy: numColumns=%d, colWidth=%d, expectedWidthLeftOver=%d, colHeight=%d, colGap=%d\n",
michael@0:          numColumns, colWidth, expectedWidthLeftOver, colHeight, colGap);
michael@0: #endif
michael@0:   ReflowConfig config = { numColumns, colWidth, expectedWidthLeftOver, colGap,
michael@0:                           colHeight, isBalancing, knownFeasibleHeight,
michael@0:                           knownInfeasibleHeight, computedHeight, consumedHeight };
michael@0:   return config;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsColumnSetFrame::ReflowColumns(nsHTMLReflowMetrics& aDesiredSize,
michael@0:                                 const nsHTMLReflowState& aReflowState,
michael@0:                                 nsReflowStatus& aReflowStatus,
michael@0:                                 ReflowConfig& aConfig,
michael@0:                                 bool aLastColumnUnbounded,
michael@0:                                 nsCollapsingMargin* aCarriedOutBottomMargin,
michael@0:                                 ColumnBalanceData& aColData)
michael@0: {
michael@0:   bool feasible = ReflowChildren(aDesiredSize, aReflowState,
michael@0:                                  aReflowStatus, aConfig, aLastColumnUnbounded,
michael@0:                                  aCarriedOutBottomMargin, aColData);
michael@0: 
michael@0:   if (aColData.mHasExcessHeight) {
michael@0:     aConfig = ChooseColumnStrategy(aReflowState, true);
michael@0: 
michael@0:     // We need to reflow our children again one last time, otherwise we might
michael@0:     // end up with a stale column height for some of our columns, since we
michael@0:     // bailed out of balancing.
michael@0:     feasible = ReflowChildren(aDesiredSize, aReflowState, aReflowStatus,
michael@0:                               aConfig, aLastColumnUnbounded,
michael@0:                               aCarriedOutBottomMargin, aColData);
michael@0:   }
michael@0: 
michael@0:   return feasible;
michael@0: }
michael@0: 
michael@0: static void MoveChildTo(nsIFrame* aParent, nsIFrame* aChild, nsPoint aOrigin) {
michael@0:   if (aChild->GetPosition() == aOrigin) {
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   aChild->SetPosition(aOrigin);
michael@0:   nsContainerFrame::PlaceFrameView(aChild);
michael@0: }
michael@0: 
michael@0: nscoord
michael@0: nsColumnSetFrame::GetMinWidth(nsRenderingContext *aRenderingContext) {
michael@0:   nscoord width = 0;
michael@0:   DISPLAY_MIN_WIDTH(this, width);
michael@0:   if (mFrames.FirstChild()) {
michael@0:     width = mFrames.FirstChild()->GetMinWidth(aRenderingContext);
michael@0:   }
michael@0:   const nsStyleColumn* colStyle = StyleColumn();
michael@0:   nscoord colWidth;
michael@0:   if (colStyle->mColumnWidth.GetUnit() == eStyleUnit_Coord) {
michael@0:     colWidth = colStyle->mColumnWidth.GetCoordValue();
michael@0:     // As available width reduces to zero, we reduce our number of columns
michael@0:     // to one, and don't enforce the column width, so just return the min
michael@0:     // of the child's min-width with any specified column width.
michael@0:     width = std::min(width, colWidth);
michael@0:   } else {
michael@0:     NS_ASSERTION(colStyle->mColumnCount > 0,
michael@0:                  "column-count and column-width can't both be auto");
michael@0:     // As available width reduces to zero, we still have mColumnCount columns,
michael@0:     // so multiply the child's min-width by the number of columns.
michael@0:     colWidth = width;
michael@0:     width *= colStyle->mColumnCount;
michael@0:     // The multiplication above can make 'width' negative (integer overflow),
michael@0:     // so use std::max to protect against that.
michael@0:     width = std::max(width, colWidth);
michael@0:   }
michael@0:   // XXX count forced column breaks here? Maybe we should return the child's
michael@0:   // min-width times the minimum number of columns.
michael@0:   return width;
michael@0: }
michael@0: 
michael@0: nscoord
michael@0: nsColumnSetFrame::GetPrefWidth(nsRenderingContext *aRenderingContext) {
michael@0:   // Our preferred width is our desired column width, if specified, otherwise
michael@0:   // the child's preferred width, times the number of columns, plus the width
michael@0:   // of any required column gaps
michael@0:   // XXX what about forced column breaks here?
michael@0:   nscoord result = 0;
michael@0:   DISPLAY_PREF_WIDTH(this, result);
michael@0:   const nsStyleColumn* colStyle = StyleColumn();
michael@0:   nscoord colGap = GetColumnGap(this, colStyle);
michael@0: 
michael@0:   nscoord colWidth;
michael@0:   if (colStyle->mColumnWidth.GetUnit() == eStyleUnit_Coord) {
michael@0:     colWidth = colStyle->mColumnWidth.GetCoordValue();
michael@0:   } else if (mFrames.FirstChild()) {
michael@0:     colWidth = mFrames.FirstChild()->GetPrefWidth(aRenderingContext);
michael@0:   } else {
michael@0:     colWidth = 0;
michael@0:   }
michael@0: 
michael@0:   int32_t numColumns = colStyle->mColumnCount;
michael@0:   if (numColumns <= 0) {
michael@0:     // if column-count is auto, assume one column
michael@0:     numColumns = 1;
michael@0:   }
michael@0:   
michael@0:   nscoord width = colWidth*numColumns + colGap*(numColumns - 1);
michael@0:   // The multiplication above can make 'width' negative (integer overflow),
michael@0:   // so use std::max to protect against that.
michael@0:   result = std::max(width, colWidth);
michael@0:   return result;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsColumnSetFrame::ReflowChildren(nsHTMLReflowMetrics&     aDesiredSize,
michael@0:                                  const nsHTMLReflowState& aReflowState,
michael@0:                                  nsReflowStatus&          aStatus,
michael@0:                                  const ReflowConfig&      aConfig,
michael@0:                                  bool                     aUnboundedLastColumn,
michael@0:                                  nsCollapsingMargin*      aBottomMarginCarriedOut,
michael@0:                                  ColumnBalanceData&       aColData)
michael@0: {
michael@0:   aColData.Reset();
michael@0:   bool allFit = true;
michael@0:   bool RTL = StyleVisibility()->mDirection == NS_STYLE_DIRECTION_RTL;
michael@0:   bool shrinkingHeightOnly = !NS_SUBTREE_DIRTY(this) &&
michael@0:     mLastBalanceHeight > aConfig.mColMaxHeight;
michael@0:   
michael@0: #ifdef DEBUG_roc
michael@0:   printf("*** Doing column reflow pass: mLastBalanceHeight=%d, mColMaxHeight=%d, RTL=%d\n, mBalanceColCount=%d, mColWidth=%d, mColGap=%d\n",
michael@0:          mLastBalanceHeight, aConfig.mColMaxHeight, RTL, aConfig.mBalanceColCount,
michael@0:          aConfig.mColWidth, aConfig.mColGap);
michael@0: #endif
michael@0: 
michael@0:   DrainOverflowColumns();
michael@0: 
michael@0:   const bool colHeightChanged = mLastBalanceHeight != aConfig.mColMaxHeight;
michael@0: 
michael@0:   if (colHeightChanged) {
michael@0:     mLastBalanceHeight = aConfig.mColMaxHeight;
michael@0:     // XXX Seems like this could fire if incremental reflow pushed the column set
michael@0:     // down so we reflow incrementally with a different available height.
michael@0:     // We need a way to do an incremental reflow and be sure availableHeight
michael@0:     // changes are taken account of! Right now I think block frames with absolute
michael@0:     // children might exit early.
michael@0:     //NS_ASSERTION(aKidReason != eReflowReason_Incremental,
michael@0:     //             "incremental reflow should not have changed the balance height");
michael@0:   }
michael@0: 
michael@0:   // get our border and padding
michael@0:   nsMargin borderPadding = aReflowState.ComputedPhysicalBorderPadding();
michael@0:   ApplySkipSides(borderPadding, &aReflowState);
michael@0:   
michael@0:   nsRect contentRect(0, 0, 0, 0);
michael@0:   nsOverflowAreas overflowRects;
michael@0: 
michael@0:   nsIFrame* child = mFrames.FirstChild();
michael@0:   nsPoint childOrigin = nsPoint(borderPadding.left, borderPadding.top);
michael@0:   // For RTL, figure out where the last column's left edge should be. Since the
michael@0:   // columns might not fill the frame exactly, we need to account for the
michael@0:   // slop. Otherwise we'll waste time moving the columns by some tiny
michael@0:   // amount unnecessarily.
michael@0:   if (RTL) {
michael@0:     nscoord availWidth = aReflowState.AvailableWidth();
michael@0:     if (aReflowState.ComputedWidth() != NS_INTRINSICSIZE) {
michael@0:       availWidth = aReflowState.ComputedWidth();
michael@0:     }
michael@0:     if (availWidth != NS_INTRINSICSIZE) {
michael@0:       childOrigin.x += availWidth - aConfig.mColWidth;
michael@0: #ifdef DEBUG_roc
michael@0:       printf("*** childOrigin.x = %d\n", childOrigin.x);
michael@0: #endif
michael@0:     }
michael@0:   }
michael@0:   int columnCount = 0;
michael@0:   int contentBottom = 0;
michael@0:   bool reflowNext = false;
michael@0: 
michael@0:   while (child) {
michael@0:     // Try to skip reflowing the child. We can't skip if the child is dirty. We also can't
michael@0:     // skip if the next column is dirty, because the next column's first line(s)
michael@0:     // might be pullable back to this column. We can't skip if it's the last child
michael@0:     // because we need to obtain the bottom margin. We can't skip
michael@0:     // if this is the last column and we're supposed to assign unbounded
michael@0:     // height to it, because that could change the available height from
michael@0:     // the last time we reflowed it and we should try to pull all the
michael@0:     // content from its next sibling. (Note that it might be the last
michael@0:     // column, but not be the last child because the desired number of columns
michael@0:     // has changed.)
michael@0:     bool skipIncremental = !aReflowState.ShouldReflowAllKids()
michael@0:       && !NS_SUBTREE_DIRTY(child)
michael@0:       && child->GetNextSibling()
michael@0:       && !(aUnboundedLastColumn && columnCount == aConfig.mBalanceColCount - 1)
michael@0:       && !NS_SUBTREE_DIRTY(child->GetNextSibling());
michael@0:     // If we need to pull up content from the prev-in-flow then this is not just
michael@0:     // a height shrink. The prev in flow will have set the dirty bit.
michael@0:     // Check the overflow rect YMost instead of just the child's content height. The child
michael@0:     // may have overflowing content that cares about the available height boundary.
michael@0:     // (It may also have overflowing content that doesn't care about the available height
michael@0:     // boundary, but if so, too bad, this optimization is defeated.)
michael@0:     // We want scrollable overflow here since this is a calculation that
michael@0:     // affects layout.
michael@0:     bool skipResizeHeightShrink = shrinkingHeightOnly
michael@0:       && child->GetScrollableOverflowRect().YMost() <= aConfig.mColMaxHeight;
michael@0: 
michael@0:     nscoord childContentBottom = 0;
michael@0:     if (!reflowNext && (skipIncremental || skipResizeHeightShrink)) {
michael@0:       // This child does not need to be reflowed, but we may need to move it
michael@0:       MoveChildTo(this, child, childOrigin);
michael@0:       
michael@0:       // If this is the last frame then make sure we get the right status
michael@0:       nsIFrame* kidNext = child->GetNextSibling();
michael@0:       if (kidNext) {
michael@0:         aStatus = (kidNext->GetStateBits() & NS_FRAME_IS_OVERFLOW_CONTAINER)
michael@0:                   ? NS_FRAME_OVERFLOW_INCOMPLETE
michael@0:                   : NS_FRAME_NOT_COMPLETE;
michael@0:       } else {
michael@0:         aStatus = mLastFrameStatus;
michael@0:       }
michael@0:       childContentBottom = nsLayoutUtils::CalculateContentBottom(child);
michael@0: #ifdef DEBUG_roc
michael@0:       printf("*** Skipping child #%d %p (incremental %d, resize height shrink %d): status = %d\n",
michael@0:              columnCount, (void*)child, skipIncremental, skipResizeHeightShrink, aStatus);
michael@0: #endif
michael@0:     } else {
michael@0:       nsSize availSize(aConfig.mColWidth, aConfig.mColMaxHeight);
michael@0:       
michael@0:       if (aUnboundedLastColumn && columnCount == aConfig.mBalanceColCount - 1) {
michael@0:         availSize.height = GetAvailableContentHeight(aReflowState);
michael@0:       }
michael@0: 
michael@0:       if (reflowNext)
michael@0:         child->AddStateBits(NS_FRAME_IS_DIRTY);
michael@0: 
michael@0:       nsHTMLReflowState kidReflowState(PresContext(), aReflowState, child,
michael@0:                                        availSize, availSize.width,
michael@0:                                        aReflowState.ComputedHeight());
michael@0:       kidReflowState.mFlags.mIsTopOfPage = true;
michael@0:       kidReflowState.mFlags.mTableIsSplittable = false;
michael@0:       kidReflowState.mFlags.mIsColumnBalancing = aConfig.mBalanceColCount < INT32_MAX;
michael@0: 
michael@0:       // We need to reflow any float placeholders, even if our column height
michael@0:       // hasn't changed.
michael@0:       kidReflowState.mFlags.mMustReflowPlaceholders = !colHeightChanged;
michael@0: 
michael@0: #ifdef DEBUG_roc
michael@0:       printf("*** Reflowing child #%d %p: availHeight=%d\n",
michael@0:              columnCount, (void*)child,availSize.height);
michael@0: #endif
michael@0: 
michael@0:       // Note if the column's next in flow is not being changed by this incremental reflow.
michael@0:       // This may allow the current column to avoid trying to pull lines from the next column.
michael@0:       if (child->GetNextSibling() &&
michael@0:           !(GetStateBits() & NS_FRAME_IS_DIRTY) &&
michael@0:         !(child->GetNextSibling()->GetStateBits() & NS_FRAME_IS_DIRTY)) {
michael@0:         kidReflowState.mFlags.mNextInFlowUntouched = true;
michael@0:       }
michael@0:     
michael@0:       nsHTMLReflowMetrics kidDesiredSize(aReflowState.GetWritingMode(),
michael@0:                                          aDesiredSize.mFlags);
michael@0: 
michael@0:       // XXX it would be cool to consult the float manager for the
michael@0:       // previous block to figure out the region of floats from the
michael@0:       // previous column that extend into this column, and subtract
michael@0:       // that region from the new float manager.  So you could stick a
michael@0:       // really big float in the first column and text in following
michael@0:       // columns would flow around it.
michael@0: 
michael@0:       // Reflow the frame
michael@0:       ReflowChild(child, PresContext(), kidDesiredSize, kidReflowState,
michael@0:                   childOrigin.x + kidReflowState.ComputedPhysicalMargin().left,
michael@0:                   childOrigin.y + kidReflowState.ComputedPhysicalMargin().top,
michael@0:                   0, aStatus);
michael@0: 
michael@0:       reflowNext = (aStatus & NS_FRAME_REFLOW_NEXTINFLOW) != 0;
michael@0:     
michael@0: #ifdef DEBUG_roc
michael@0:       printf("*** Reflowed child #%d %p: status = %d, desiredSize=%d,%d CarriedOutBottomMargin=%d\n",
michael@0:              columnCount, (void*)child, aStatus, kidDesiredSize.Width(), kidDesiredSize.Height(),
michael@0:              kidDesiredSize.mCarriedOutBottomMargin.get());
michael@0: #endif
michael@0: 
michael@0:       NS_FRAME_TRACE_REFLOW_OUT("Column::Reflow", aStatus);
michael@0: 
michael@0:       *aBottomMarginCarriedOut = kidDesiredSize.mCarriedOutBottomMargin;
michael@0:       
michael@0:       FinishReflowChild(child, PresContext(), kidDesiredSize,
michael@0:                         &kidReflowState, childOrigin.x, childOrigin.y, 0);
michael@0: 
michael@0:       childContentBottom = nsLayoutUtils::CalculateContentBottom(child);
michael@0:       if (childContentBottom > aConfig.mColMaxHeight) {
michael@0:         allFit = false;
michael@0:       }
michael@0:       if (childContentBottom > availSize.height) {
michael@0:         aColData.mMaxOverflowingHeight = std::max(childContentBottom,
michael@0:             aColData.mMaxOverflowingHeight);
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     contentRect.UnionRect(contentRect, child->GetRect());
michael@0: 
michael@0:     ConsiderChildOverflow(overflowRects, child);
michael@0:     contentBottom = std::max(contentBottom, childContentBottom);
michael@0:     aColData.mLastHeight = childContentBottom;
michael@0:     aColData.mSumHeight += childContentBottom;
michael@0: 
michael@0:     // Build a continuation column if necessary
michael@0:     nsIFrame* kidNextInFlow = child->GetNextInFlow();
michael@0: 
michael@0:     if (NS_FRAME_IS_FULLY_COMPLETE(aStatus) && !NS_FRAME_IS_TRUNCATED(aStatus)) {
michael@0:       NS_ASSERTION(!kidNextInFlow, "next in flow should have been deleted");
michael@0:       child = nullptr;
michael@0:       break;
michael@0:     } else {
michael@0:       ++columnCount;
michael@0:       // Make sure that the column has a next-in-flow. If not, we must
michael@0:       // create one to hold the overflowing stuff, even if we're just
michael@0:       // going to put it on our overflow list and let *our*
michael@0:       // next in flow handle it.
michael@0:       if (!kidNextInFlow) {
michael@0:         NS_ASSERTION(aStatus & NS_FRAME_REFLOW_NEXTINFLOW,
michael@0:                      "We have to create a continuation, but the block doesn't want us to reflow it?");
michael@0: 
michael@0:         // We need to create a continuing column
michael@0:         nsresult rv = CreateNextInFlow(child, kidNextInFlow);
michael@0:         
michael@0:         if (NS_FAILED(rv)) {
michael@0:           NS_NOTREACHED("Couldn't create continuation");
michael@0:           child = nullptr;
michael@0:           break;
michael@0:         }
michael@0:       }
michael@0: 
michael@0:       // Make sure we reflow a next-in-flow when it switches between being
michael@0:       // normal or overflow container
michael@0:       if (NS_FRAME_OVERFLOW_IS_INCOMPLETE(aStatus)) {
michael@0:         if (!(kidNextInFlow->GetStateBits() & NS_FRAME_IS_OVERFLOW_CONTAINER)) {
michael@0:           aStatus |= NS_FRAME_REFLOW_NEXTINFLOW;
michael@0:           reflowNext = true;
michael@0:           kidNextInFlow->AddStateBits(NS_FRAME_IS_OVERFLOW_CONTAINER);
michael@0:         }
michael@0:       }
michael@0:       else if (kidNextInFlow->GetStateBits() & NS_FRAME_IS_OVERFLOW_CONTAINER) {
michael@0:         aStatus |= NS_FRAME_REFLOW_NEXTINFLOW;
michael@0:         reflowNext = true;
michael@0:         kidNextInFlow->RemoveStateBits(NS_FRAME_IS_OVERFLOW_CONTAINER);
michael@0:       }
michael@0: 
michael@0:       if ((contentBottom > aReflowState.ComputedMaxHeight() ||
michael@0:            contentBottom > aReflowState.ComputedHeight()) &&
michael@0:            aConfig.mBalanceColCount < INT32_MAX) {
michael@0:         // We overflowed vertically, but have not exceeded the number of
michael@0:         // columns. We're going to go into overflow columns now, so balancing
michael@0:         // no longer applies.
michael@0:         aColData.mHasExcessHeight = true;
michael@0:       }
michael@0: 
michael@0:       if (columnCount >= aConfig.mBalanceColCount) {
michael@0:         // No more columns allowed here. Stop.
michael@0:         aStatus |= NS_FRAME_REFLOW_NEXTINFLOW;
michael@0:         kidNextInFlow->AddStateBits(NS_FRAME_IS_DIRTY);
michael@0:         // Move any of our leftover columns to our overflow list. Our
michael@0:         // next-in-flow will eventually pick them up.
michael@0:         const nsFrameList& continuationColumns = mFrames.RemoveFramesAfter(child);
michael@0:         if (continuationColumns.NotEmpty()) {
michael@0:           SetOverflowFrames(continuationColumns);
michael@0:         }
michael@0:         child = nullptr;
michael@0:         break;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     if (PresContext()->HasPendingInterrupt()) {
michael@0:       // Stop the loop now while |child| still points to the frame that bailed
michael@0:       // out.  We could keep going here and condition a bunch of the code in
michael@0:       // this loop on whether there's an interrupt, or even just keep going and
michael@0:       // trying to reflow the blocks (even though we know they'll interrupt
michael@0:       // right after their first line), but stopping now is conceptually the
michael@0:       // simplest (and probably fastest) thing.
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     // Advance to the next column
michael@0:     child = child->GetNextSibling();
michael@0: 
michael@0:     if (child) {
michael@0:       if (!RTL) {
michael@0:         childOrigin.x += aConfig.mColWidth + aConfig.mColGap;
michael@0:       } else {
michael@0:         childOrigin.x -= aConfig.mColWidth + aConfig.mColGap;
michael@0:       }
michael@0:       
michael@0: #ifdef DEBUG_roc
michael@0:       printf("*** NEXT CHILD ORIGIN.x = %d\n", childOrigin.x);
michael@0: #endif
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (PresContext()->CheckForInterrupt(this) &&
michael@0:       (GetStateBits() & NS_FRAME_IS_DIRTY)) {
michael@0:     // Mark all our kids starting with |child| dirty
michael@0: 
michael@0:     // Note that this is a CheckForInterrupt call, not a HasPendingInterrupt,
michael@0:     // because we might have interrupted while reflowing |child|, and since
michael@0:     // we're about to add a dirty bit to |child| we need to make sure that
michael@0:     // |this| is scheduled to have dirty bits marked on it and its ancestors.
michael@0:     // Otherwise, when we go to mark dirty bits on |child|'s ancestors we'll
michael@0:     // bail out immediately, since it'll already have a dirty bit.
michael@0:     for (; child; child = child->GetNextSibling()) {
michael@0:       child->AddStateBits(NS_FRAME_IS_DIRTY);
michael@0:     }
michael@0:   }
michael@0:   
michael@0:   aColData.mMaxHeight = contentBottom;
michael@0:   contentRect.height = std::max(contentRect.height, contentBottom);
michael@0:   mLastFrameStatus = aStatus;
michael@0:   
michael@0:   // contentRect included the borderPadding.left,borderPadding.top of the child rects
michael@0:   contentRect -= nsPoint(borderPadding.left, borderPadding.top);
michael@0:   
michael@0:   nsSize contentSize = nsSize(contentRect.XMost(), contentRect.YMost());
michael@0: 
michael@0:   // Apply computed and min/max values
michael@0:   if (aConfig.mComputedHeight != NS_INTRINSICSIZE) {
michael@0:     if (aReflowState.AvailableHeight() != NS_INTRINSICSIZE) {
michael@0:       contentSize.height = std::min(contentSize.height,
michael@0:                                     aConfig.mComputedHeight);
michael@0:     } else {
michael@0:       contentSize.height = aConfig.mComputedHeight;
michael@0:     }
michael@0:   } else {
michael@0:     // We add the "consumed" height back in so that we're applying
michael@0:     // constraints to the correct height value, then subtract it again
michael@0:     // after we've finished with the min/max calculation. This prevents us from
michael@0:     // having a last continuation that is smaller than the min height. but which
michael@0:     // has prev-in-flows, trigger a larger height than actually required.
michael@0:     contentSize.height = aReflowState.ApplyMinMaxHeight(contentSize.height,
michael@0:                                                         aConfig.mConsumedHeight);
michael@0:   }
michael@0:   if (aReflowState.ComputedWidth() != NS_INTRINSICSIZE) {
michael@0:     contentSize.width = aReflowState.ComputedWidth();
michael@0:   } else {
michael@0:     contentSize.width = aReflowState.ApplyMinMaxWidth(contentSize.width);
michael@0:   }
michael@0: 
michael@0:   aDesiredSize.Height() = contentSize.height +
michael@0:                         borderPadding.TopBottom();
michael@0:   aDesiredSize.Width() = contentSize.width +
michael@0:                        borderPadding.LeftRight();
michael@0:   aDesiredSize.mOverflowAreas = overflowRects;
michael@0:   aDesiredSize.UnionOverflowAreasWithDesiredBounds();
michael@0: 
michael@0: #ifdef DEBUG_roc
michael@0:   printf("*** DONE PASS feasible=%d\n", allFit && NS_FRAME_IS_FULLY_COMPLETE(aStatus)
michael@0:          && !NS_FRAME_IS_TRUNCATED(aStatus));
michael@0: #endif
michael@0:   return allFit && NS_FRAME_IS_FULLY_COMPLETE(aStatus)
michael@0:     && !NS_FRAME_IS_TRUNCATED(aStatus);
michael@0: }
michael@0: 
michael@0: void
michael@0: nsColumnSetFrame::DrainOverflowColumns()
michael@0: {
michael@0:   // First grab the prev-in-flows overflows and reparent them to this
michael@0:   // frame.
michael@0:   nsPresContext* presContext = PresContext();
michael@0:   nsColumnSetFrame* prev = static_cast<nsColumnSetFrame*>(GetPrevInFlow());
michael@0:   if (prev) {
michael@0:     AutoFrameListPtr overflows(presContext, prev->StealOverflowFrames());
michael@0:     if (overflows) {
michael@0:       nsContainerFrame::ReparentFrameViewList(*overflows, prev, this);
michael@0: 
michael@0:       mFrames.InsertFrames(this, nullptr, *overflows);
michael@0:     }
michael@0:   }
michael@0:   
michael@0:   // Now pull back our own overflows and append them to our children.
michael@0:   // We don't need to reparent them since we're already their parent.
michael@0:   AutoFrameListPtr overflows(presContext, StealOverflowFrames());
michael@0:   if (overflows) {
michael@0:     // We're already the parent for these frames, so no need to set
michael@0:     // their parent again.
michael@0:     mFrames.AppendFrames(nullptr, *overflows);
michael@0:   }
michael@0: }
michael@0: 
michael@0: void
michael@0: nsColumnSetFrame::FindBestBalanceHeight(const nsHTMLReflowState& aReflowState,
michael@0:                                         nsPresContext* aPresContext,
michael@0:                                         ReflowConfig& aConfig,
michael@0:                                         ColumnBalanceData& aColData,
michael@0:                                         nsHTMLReflowMetrics& aDesiredSize,
michael@0:                                         nsCollapsingMargin& aOutMargin,
michael@0:                                         bool& aUnboundedLastColumn,
michael@0:                                         bool& aRunWasFeasible,
michael@0:                                         nsReflowStatus& aStatus)
michael@0: {
michael@0:   bool feasible = aRunWasFeasible;
michael@0: 
michael@0:   nsMargin bp = aReflowState.ComputedPhysicalBorderPadding();
michael@0:   ApplySkipSides(bp);
michael@0:   bp.bottom = aReflowState.ComputedPhysicalBorderPadding().bottom;
michael@0: 
michael@0:   nscoord availableContentHeight =
michael@0:     GetAvailableContentHeight(aReflowState);
michael@0: 
michael@0:   // Termination of the algorithm below is guaranteed because
michael@0:   // aConfig.knownFeasibleHeight - aConfig.knownInfeasibleHeight decreases in every
michael@0:   // iteration.
michael@0: 
michael@0:   // We set this flag when we detect that we may contain a frame
michael@0:   // that can break anywhere (thus foiling the linear decrease-by-one
michael@0:   // search)
michael@0:   bool maybeContinuousBreakingDetected = false;
michael@0: 
michael@0:   while (!aPresContext->HasPendingInterrupt()) {
michael@0:     nscoord lastKnownFeasibleHeight = aConfig.mKnownFeasibleHeight;
michael@0: 
michael@0:     // Record what we learned from the last reflow
michael@0:     if (feasible) {
michael@0:       // maxHeight is feasible. Also, mLastBalanceHeight is feasible.
michael@0:       aConfig.mKnownFeasibleHeight = std::min(aConfig.mKnownFeasibleHeight,
michael@0:                                               aColData.mMaxHeight);
michael@0:       aConfig.mKnownFeasibleHeight = std::min(aConfig.mKnownFeasibleHeight,
michael@0:                                               mLastBalanceHeight);
michael@0: 
michael@0:       // Furthermore, no height less than the height of the last
michael@0:       // column can ever be feasible. (We might be able to reduce the
michael@0:       // height of a non-last column by moving content to a later column,
michael@0:       // but we can't do that with the last column.)
michael@0:       if (mFrames.GetLength() == aConfig.mBalanceColCount) {
michael@0:         aConfig.mKnownInfeasibleHeight = std::max(aConfig.mKnownInfeasibleHeight,
michael@0:                                        aColData.mLastHeight - 1);
michael@0:       }
michael@0:     } else {
michael@0:       aConfig.mKnownInfeasibleHeight = std::max(aConfig.mKnownInfeasibleHeight,
michael@0:                                                 mLastBalanceHeight);
michael@0:       // If a column didn't fit in its available height, then its current
michael@0:       // height must be the minimum height for unbreakable content in
michael@0:       // the column, and therefore no smaller height can be feasible.
michael@0:       aConfig.mKnownInfeasibleHeight = std::max(aConfig.mKnownInfeasibleHeight,
michael@0:                                          aColData.mMaxOverflowingHeight - 1);
michael@0: 
michael@0:       if (aUnboundedLastColumn) {
michael@0:         // The last column is unbounded, so all content got reflowed, so the
michael@0:         // mColMaxHeight is feasible.
michael@0:         aConfig.mKnownFeasibleHeight = std::min(aConfig.mKnownFeasibleHeight,
michael@0:                                                 aColData.mMaxHeight);
michael@0:       }
michael@0:     }
michael@0: 
michael@0: #ifdef DEBUG_roc
michael@0:     printf("*** nsColumnSetFrame::Reflow balancing knownInfeasible=%d knownFeasible=%d\n",
michael@0:            aConfig.mKnownInfeasibleHeight, aConfig.mKnownFeasibleHeight);
michael@0: #endif
michael@0: 
michael@0: 
michael@0:     if (aConfig.mKnownInfeasibleHeight >= aConfig.mKnownFeasibleHeight - 1) {
michael@0:       // aConfig.mKnownFeasibleHeight is where we want to be
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     if (aConfig.mKnownInfeasibleHeight >= availableContentHeight) {
michael@0:       break;
michael@0:     }
michael@0: 
michael@0:     if (lastKnownFeasibleHeight - aConfig.mKnownFeasibleHeight == 1) {
michael@0:       // We decreased the feasible height by one twip only. This could
michael@0:       // indicate that there is a continuously breakable child frame
michael@0:       // that we are crawling through.
michael@0:       maybeContinuousBreakingDetected = true;
michael@0:     }
michael@0: 
michael@0:     nscoord nextGuess = (aConfig.mKnownFeasibleHeight + aConfig.mKnownInfeasibleHeight)/2;
michael@0:     // The constant of 600 twips is arbitrary. It's about two line-heights.
michael@0:     if (aConfig.mKnownFeasibleHeight - nextGuess < 600 &&
michael@0:         !maybeContinuousBreakingDetected) {
michael@0:       // We're close to our target, so just try shrinking just the
michael@0:       // minimum amount that will cause one of our columns to break
michael@0:       // differently.
michael@0:       nextGuess = aConfig.mKnownFeasibleHeight - 1;
michael@0:     } else if (aUnboundedLastColumn) {
michael@0:       // Make a guess by dividing that into N columns. Add some slop
michael@0:       // to try to make it on the feasible side.  The constant of
michael@0:       // 600 twips is arbitrary. It's about two line-heights.
michael@0:       nextGuess = aColData.mSumHeight/aConfig.mBalanceColCount + 600;
michael@0:       // Sanitize it
michael@0:       nextGuess = clamped(nextGuess, aConfig.mKnownInfeasibleHeight + 1,
michael@0:                                      aConfig.mKnownFeasibleHeight - 1);
michael@0:     } else if (aConfig.mKnownFeasibleHeight == NS_INTRINSICSIZE) {
michael@0:       // This can happen when we had a next-in-flow so we didn't
michael@0:       // want to do an unbounded height measuring step. Let's just increase
michael@0:       // from the infeasible height by some reasonable amount.
michael@0:       nextGuess = aConfig.mKnownInfeasibleHeight*2 + 600;
michael@0:     }
michael@0:     // Don't bother guessing more than our height constraint.
michael@0:     nextGuess = std::min(availableContentHeight, nextGuess);
michael@0: 
michael@0: #ifdef DEBUG_roc
michael@0:     printf("*** nsColumnSetFrame::Reflow balancing choosing next guess=%d\n", nextGuess);
michael@0: #endif
michael@0: 
michael@0:     aConfig.mColMaxHeight = nextGuess;
michael@0: 
michael@0:     aUnboundedLastColumn = false;
michael@0:     AddStateBits(NS_FRAME_IS_DIRTY);
michael@0:     feasible = ReflowColumns(aDesiredSize, aReflowState, aStatus, aConfig, false,
michael@0:                              &aOutMargin, aColData);
michael@0: 
michael@0:     if (!aConfig.mIsBalancing) {
michael@0:       // Looks like we had excess height when balancing, so we gave up on
michael@0:       // trying to balance.
michael@0:       break;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (aConfig.mIsBalancing && !feasible &&
michael@0:       !aPresContext->HasPendingInterrupt()) {
michael@0:     // We may need to reflow one more time at the feasible height to
michael@0:     // get a valid layout.
michael@0:     bool skip = false;
michael@0:     if (aConfig.mKnownInfeasibleHeight >= availableContentHeight) {
michael@0:       aConfig.mColMaxHeight = availableContentHeight;
michael@0:       if (mLastBalanceHeight == availableContentHeight) {
michael@0:         skip = true;
michael@0:       }
michael@0:     } else {
michael@0:       aConfig.mColMaxHeight = aConfig.mKnownFeasibleHeight;
michael@0:     }
michael@0:     if (!skip) {
michael@0:       // If our height is unconstrained, make sure that the last column is
michael@0:       // allowed to have arbitrary height here, even though we were balancing.
michael@0:       // Otherwise we'd have to split, and it's not clear what we'd do with
michael@0:       // that.
michael@0:       AddStateBits(NS_FRAME_IS_DIRTY);
michael@0:       feasible = ReflowColumns(aDesiredSize, aReflowState, aStatus, aConfig,
michael@0:                                availableContentHeight == NS_UNCONSTRAINEDSIZE,
michael@0:                                &aOutMargin, aColData);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   aRunWasFeasible = feasible;
michael@0: }
michael@0: 
michael@0: nsresult 
michael@0: nsColumnSetFrame::Reflow(nsPresContext*           aPresContext,
michael@0:                          nsHTMLReflowMetrics&     aDesiredSize,
michael@0:                          const nsHTMLReflowState& aReflowState,
michael@0:                          nsReflowStatus&          aStatus)
michael@0: {
michael@0:   // Don't support interruption in columns
michael@0:   nsPresContext::InterruptPreventer noInterrupts(aPresContext);
michael@0: 
michael@0:   DO_GLOBAL_REFLOW_COUNT("nsColumnSetFrame");
michael@0:   DISPLAY_REFLOW(aPresContext, this, aReflowState, aDesiredSize, aStatus);
michael@0: 
michael@0:   // Initialize OUT parameter
michael@0:   aStatus = NS_FRAME_COMPLETE;
michael@0: 
michael@0:   // Our children depend on our height if we have a fixed height.
michael@0:   if (aReflowState.ComputedHeight() != NS_AUTOHEIGHT) {
michael@0:     NS_ASSERTION(aReflowState.ComputedHeight() != NS_INTRINSICSIZE,
michael@0:                  "Unexpected computed height");
michael@0:     AddStateBits(NS_FRAME_CONTAINS_RELATIVE_HEIGHT);
michael@0:   }
michael@0:   else {
michael@0:     RemoveStateBits(NS_FRAME_CONTAINS_RELATIVE_HEIGHT);
michael@0:   }
michael@0: 
michael@0:   //------------ Handle Incremental Reflow -----------------
michael@0: 
michael@0:   ReflowConfig config = ChooseColumnStrategy(aReflowState);
michael@0:   
michael@0:   // If balancing, then we allow the last column to grow to unbounded
michael@0:   // height during the first reflow. This gives us a way to estimate
michael@0:   // what the average column height should be, because we can measure
michael@0:   // the heights of all the columns and sum them up. But don't do this
michael@0:   // if we have a next in flow because we don't want to suck all its
michael@0:   // content back here and then have to push it out again!
michael@0:   nsIFrame* nextInFlow = GetNextInFlow();
michael@0:   bool unboundedLastColumn = config.mIsBalancing && !nextInFlow;
michael@0:   nsCollapsingMargin carriedOutBottomMargin;
michael@0:   ColumnBalanceData colData;
michael@0:   colData.mHasExcessHeight = false;
michael@0: 
michael@0:   bool feasible = ReflowColumns(aDesiredSize, aReflowState, aStatus, config,
michael@0:                                 unboundedLastColumn, &carriedOutBottomMargin,
michael@0:                                 colData);
michael@0: 
michael@0:   // If we're not balancing, then we're already done, since we should have
michael@0:   // reflown all of our children, and there is no need for a binary search to
michael@0:   // determine proper column height.
michael@0:   if (config.mIsBalancing && !aPresContext->HasPendingInterrupt()) {
michael@0:     FindBestBalanceHeight(aReflowState, aPresContext, config, colData,
michael@0:                           aDesiredSize, carriedOutBottomMargin,
michael@0:                           unboundedLastColumn, feasible, aStatus);
michael@0:   }
michael@0: 
michael@0:   if (aPresContext->HasPendingInterrupt() &&
michael@0:       aReflowState.AvailableHeight() == NS_UNCONSTRAINEDSIZE) {
michael@0:     // In this situation, we might be lying about our reflow status, because
michael@0:     // our last kid (the one that got interrupted) was incomplete.  Fix that.
michael@0:     aStatus = NS_FRAME_COMPLETE;
michael@0:   }
michael@0: 
michael@0:   FinishReflowWithAbsoluteFrames(aPresContext, aDesiredSize, aReflowState, aStatus, false);
michael@0: 
michael@0:   aDesiredSize.mCarriedOutBottomMargin = carriedOutBottomMargin;
michael@0: 
michael@0:   NS_FRAME_SET_TRUNCATION(aStatus, aReflowState, aDesiredSize);
michael@0: 
michael@0:   NS_ASSERTION(NS_FRAME_IS_FULLY_COMPLETE(aStatus) ||
michael@0:                aReflowState.AvailableHeight() != NS_UNCONSTRAINEDSIZE,
michael@0:                "Column set should be complete if the available height is unconstrained");
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: void
michael@0: nsColumnSetFrame::BuildDisplayList(nsDisplayListBuilder*   aBuilder,
michael@0:                                    const nsRect&           aDirtyRect,
michael@0:                                    const nsDisplayListSet& aLists) {
michael@0:   DisplayBorderBackgroundOutline(aBuilder, aLists);
michael@0: 
michael@0:   if (IsVisibleForPainting(aBuilder)) {
michael@0:     aLists.BorderBackground()->AppendNewToTop(new (aBuilder)
michael@0:       nsDisplayGenericOverflow(aBuilder, this, ::PaintColumnRule, "ColumnRule",
michael@0:                                nsDisplayItem::TYPE_COLUMN_RULE));
michael@0:   }
michael@0: 
michael@0:   // Our children won't have backgrounds so it doesn't matter where we put them.
michael@0:   for (nsFrameList::Enumerator e(mFrames); !e.AtEnd(); e.Next()) {
michael@0:     BuildDisplayListForChild(aBuilder, e.get(), aDirtyRect, aLists);
michael@0:   }
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsColumnSetFrame::AppendFrames(ChildListID     aListID,
michael@0:                                nsFrameList&    aFrameList)
michael@0: {
michael@0:   if (aListID == kAbsoluteList) {
michael@0:     return nsContainerFrame::AppendFrames(aListID, aFrameList);
michael@0:   }
michael@0: 
michael@0:   NS_ERROR("unexpected child list");
michael@0:   return NS_ERROR_INVALID_ARG;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsColumnSetFrame::InsertFrames(ChildListID     aListID,
michael@0:                                nsIFrame*       aPrevFrame,
michael@0:                                nsFrameList&    aFrameList)
michael@0: {
michael@0:   if (aListID == kAbsoluteList) {
michael@0:     return nsContainerFrame::InsertFrames(aListID, aPrevFrame, aFrameList);
michael@0:   }
michael@0: 
michael@0:   NS_ERROR("unexpected child list");
michael@0:   return NS_ERROR_INVALID_ARG;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: nsColumnSetFrame::RemoveFrame(ChildListID     aListID,
michael@0:                               nsIFrame*       aOldFrame)
michael@0: {
michael@0:   if (aListID == kAbsoluteList) {
michael@0:     return nsContainerFrame::RemoveFrame(aListID, aOldFrame);
michael@0:   }
michael@0: 
michael@0:   NS_ERROR("unexpected child list");
michael@0:   return NS_ERROR_INVALID_ARG;
michael@0: }