[CSS Shapes] Use the floatingObject's logical coordinates to determine its size in...
[WebKit-https.git] / Source / WebCore / rendering / RenderBlockFlow.cpp
1 /*
2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
3  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
4  *           (C) 2007 David Smith (catfish.man@gmail.com)
5  * Copyright (C) 2003-2013 Apple Inc. All rights reserved.
6  * Copyright (C) Research In Motion Limited 2010. All rights reserved.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  */
23
24 #include "config.h"
25 #include "RenderBlockFlow.h"
26
27 #include "FloatingObjects.h"
28 #include "HitTestLocation.h"
29 #include "LayoutRepainter.h"
30 #include "RenderFlowThread.h"
31 #include "RenderLayer.h"
32 #include "RenderView.h"
33 #include "VerticalPositionCache.h"
34
35 using namespace std;
36
37 namespace WebCore {
38
39 bool RenderBlock::s_canPropagateFloatIntoSibling = false;
40
41 struct SameSizeAsMarginInfo {
42     uint32_t bitfields : 16;
43     LayoutUnit margins[2];
44 };
45
46 COMPILE_ASSERT(sizeof(RenderBlockFlow::MarginValues) == sizeof(LayoutUnit[4]), MarginValues_should_stay_small);
47
48 // Our MarginInfo state used when laying out block children.
49 RenderBlockFlow::MarginInfo::MarginInfo(RenderBlockFlow* block, LayoutUnit beforeBorderPadding, LayoutUnit afterBorderPadding)
50     : m_atBeforeSideOfBlock(true)
51     , m_atAfterSideOfBlock(false)
52     , m_hasMarginBeforeQuirk(false)
53     , m_hasMarginAfterQuirk(false)
54     , m_determinedMarginBeforeQuirk(false)
55     , m_discardMargin(false)
56 {
57     RenderStyle* blockStyle = block->style();
58     ASSERT(block->isRenderView() || block->parent());
59     m_canCollapseWithChildren = !block->isRenderView() && !block->isRoot() && !block->isOutOfFlowPositioned()
60         && !block->isFloating() && !block->isTableCell() && !block->hasOverflowClip() && !block->isInlineBlockOrInlineTable()
61         && !block->isRenderFlowThread() && !block->isWritingModeRoot() && !block->parent()->isFlexibleBox()
62         && blockStyle->hasAutoColumnCount() && blockStyle->hasAutoColumnWidth() && !blockStyle->columnSpan();
63
64     m_canCollapseMarginBeforeWithChildren = m_canCollapseWithChildren && !beforeBorderPadding && blockStyle->marginBeforeCollapse() != MSEPARATE;
65
66     // If any height other than auto is specified in CSS, then we don't collapse our bottom
67     // margins with our children's margins. To do otherwise would be to risk odd visual
68     // effects when the children overflow out of the parent block and yet still collapse
69     // with it. We also don't collapse if we have any bottom border/padding.
70     m_canCollapseMarginAfterWithChildren = m_canCollapseWithChildren && !afterBorderPadding
71         && (blockStyle->logicalHeight().isAuto() && !blockStyle->logicalHeight().value()) && blockStyle->marginAfterCollapse() != MSEPARATE;
72     
73     m_quirkContainer = block->isTableCell() || block->isBody();
74
75     m_discardMargin = m_canCollapseMarginBeforeWithChildren && block->mustDiscardMarginBefore();
76
77     m_positiveMargin = (m_canCollapseMarginBeforeWithChildren && !block->mustDiscardMarginBefore()) ? block->maxPositiveMarginBefore() : LayoutUnit();
78     m_negativeMargin = (m_canCollapseMarginBeforeWithChildren && !block->mustDiscardMarginBefore()) ? block->maxNegativeMarginBefore() : LayoutUnit();
79 }
80
81 RenderBlockFlow::RenderBlockFlow(Element* element)
82     : RenderBlock(element, RenderBlockFlowFlag)
83 {
84     COMPILE_ASSERT(sizeof(RenderBlockFlow::MarginInfo) == sizeof(SameSizeAsMarginInfo), MarginInfo_should_stay_small);
85 }
86
87 RenderBlockFlow::~RenderBlockFlow()
88 {
89 }
90
91 void RenderBlockFlow::willBeDestroyed()
92 {
93     if (lineGridBox())
94         lineGridBox()->destroy(renderArena());
95
96     RenderBlock::willBeDestroyed();
97 }
98
99 void RenderBlockFlow::clearFloats()
100 {
101     if (m_floatingObjects)
102         m_floatingObjects->setHorizontalWritingMode(isHorizontalWritingMode());
103
104     HashSet<RenderBox*> oldIntrudingFloatSet;
105     if (!childrenInline() && m_floatingObjects) {
106         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
107         auto end = floatingObjectSet.end();
108         for (auto it = floatingObjectSet.begin(); it != end; ++it) {
109             FloatingObject* floatingObject = it->get();
110             if (!floatingObject->isDescendant())
111                 oldIntrudingFloatSet.add(&floatingObject->renderer());
112         }
113     }
114
115     // Inline blocks are covered by the isReplaced() check in the avoidFloats method.
116     if (avoidsFloats() || isRoot() || isRenderView() || isFloatingOrOutOfFlowPositioned() || isTableCell()) {
117         if (m_floatingObjects) {
118             m_floatingObjects->clear();
119         }
120         if (!oldIntrudingFloatSet.isEmpty())
121             markAllDescendantsWithFloatsForLayout();
122         return;
123     }
124
125     RendererToFloatInfoMap floatMap;
126
127     if (m_floatingObjects) {
128         if (childrenInline())
129             m_floatingObjects->moveAllToFloatInfoMap(floatMap);
130         else
131             m_floatingObjects->clear();
132     }
133
134     // We should not process floats if the parent node is not a RenderBlock. Otherwise, we will add 
135     // floats in an invalid context. This will cause a crash arising from a bad cast on the parent.
136     // See <rdar://problem/8049753>, where float property is applied on a text node in a SVG.
137     if (!parent() || !parent()->isRenderBlockFlow())
138         return;
139
140     // Attempt to locate a previous sibling with overhanging floats. We skip any elements that are
141     // out of flow (like floating/positioned elements), and we also skip over any objects that may have shifted
142     // to avoid floats.
143     RenderBlockFlow* parentBlock = toRenderBlockFlow(parent());
144     bool parentHasFloats = false;
145     RenderObject* prev = previousSibling();
146     while (prev && (prev->isFloatingOrOutOfFlowPositioned() || !prev->isBox() || !prev->isRenderBlockFlow() || toRenderBlockFlow(prev)->avoidsFloats())) {
147         if (prev->isFloating())
148             parentHasFloats = true;
149         prev = prev->previousSibling();
150     }
151
152     // First add in floats from the parent.
153     LayoutUnit logicalTopOffset = logicalTop();
154     if (parentHasFloats)
155         addIntrudingFloats(parentBlock, parentBlock->logicalLeftOffsetForContent(), logicalTopOffset);
156     
157     LayoutUnit logicalLeftOffset = 0;
158     if (prev)
159         logicalTopOffset -= toRenderBox(prev)->logicalTop();
160     else {
161         prev = parentBlock;
162         logicalLeftOffset += parentBlock->logicalLeftOffsetForContent();
163     }
164
165     // Add overhanging floats from the previous RenderBlock, but only if it has a float that intrudes into our space.    
166     RenderBlockFlow* block = toRenderBlockFlow(prev);
167     if (block->m_floatingObjects && block->lowestFloatLogicalBottom() > logicalTopOffset)
168         addIntrudingFloats(block, logicalLeftOffset, logicalTopOffset);
169
170     if (childrenInline()) {
171         LayoutUnit changeLogicalTop = LayoutUnit::max();
172         LayoutUnit changeLogicalBottom = LayoutUnit::min();
173         if (m_floatingObjects) {
174             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
175             auto end = floatingObjectSet.end();
176             for (auto it = floatingObjectSet.begin(); it != end; ++it) {
177                 FloatingObject* floatingObject = it->get();
178                 std::unique_ptr<FloatingObject> oldFloatingObject = floatMap.take(&floatingObject->renderer());
179                 LayoutUnit logicalBottom = logicalBottomForFloat(floatingObject);
180                 if (oldFloatingObject) {
181                     LayoutUnit oldLogicalBottom = logicalBottomForFloat(oldFloatingObject.get());
182                     if (logicalWidthForFloat(floatingObject) != logicalWidthForFloat(oldFloatingObject.get()) || logicalLeftForFloat(floatingObject) != logicalLeftForFloat(oldFloatingObject.get())) {
183                         changeLogicalTop = 0;
184                         changeLogicalBottom = max(changeLogicalBottom, max(logicalBottom, oldLogicalBottom));
185                     } else {
186                         if (logicalBottom != oldLogicalBottom) {
187                             changeLogicalTop = min(changeLogicalTop, min(logicalBottom, oldLogicalBottom));
188                             changeLogicalBottom = max(changeLogicalBottom, max(logicalBottom, oldLogicalBottom));
189                         }
190                         LayoutUnit logicalTop = logicalTopForFloat(floatingObject);
191                         LayoutUnit oldLogicalTop = logicalTopForFloat(oldFloatingObject.get());
192                         if (logicalTop != oldLogicalTop) {
193                             changeLogicalTop = min(changeLogicalTop, min(logicalTop, oldLogicalTop));
194                             changeLogicalBottom = max(changeLogicalBottom, max(logicalTop, oldLogicalTop));
195                         }
196                     }
197
198                     if (oldFloatingObject->originatingLine() && !selfNeedsLayout()) {
199                         ASSERT(&oldFloatingObject->originatingLine()->renderer() == this);
200                         oldFloatingObject->originatingLine()->markDirty();
201                     }
202                 } else {
203                     changeLogicalTop = 0;
204                     changeLogicalBottom = max(changeLogicalBottom, logicalBottom);
205                 }
206             }
207         }
208
209         auto end = floatMap.end();
210         for (auto it = floatMap.begin(); it != end; ++it) {
211             FloatingObject* floatingObject = it->value.get();
212             if (!floatingObject->isDescendant()) {
213                 changeLogicalTop = 0;
214                 changeLogicalBottom = max(changeLogicalBottom, logicalBottomForFloat(floatingObject));
215             }
216         }
217
218         markLinesDirtyInBlockRange(changeLogicalTop, changeLogicalBottom);
219     } else if (!oldIntrudingFloatSet.isEmpty()) {
220         // If there are previously intruding floats that no longer intrude, then children with floats
221         // should also get layout because they might need their floating object lists cleared.
222         if (m_floatingObjects->set().size() < oldIntrudingFloatSet.size())
223             markAllDescendantsWithFloatsForLayout();
224         else {
225             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
226             auto end = floatingObjectSet.end();
227             for (auto it = floatingObjectSet.begin(); it != end && !oldIntrudingFloatSet.isEmpty(); ++it)
228                 oldIntrudingFloatSet.remove(&(*it)->renderer());
229             if (!oldIntrudingFloatSet.isEmpty())
230                 markAllDescendantsWithFloatsForLayout();
231         }
232     }
233 }
234
235 void RenderBlockFlow::layoutBlock(bool relayoutChildren, LayoutUnit pageLogicalHeight)
236 {
237     ASSERT(needsLayout());
238
239     if (!relayoutChildren && simplifiedLayout())
240         return;
241
242     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
243
244     if (updateLogicalWidthAndColumnWidth())
245         relayoutChildren = true;
246
247     clearFloats();
248
249     LayoutUnit previousHeight = logicalHeight();
250     // FIXME: should this start out as borderAndPaddingLogicalHeight() + scrollbarLogicalHeight(),
251     // for consistency with other render classes?
252     setLogicalHeight(0);
253
254     bool pageLogicalHeightChanged = false;
255     bool hasSpecifiedPageLogicalHeight = false;
256     checkForPaginationLogicalHeightChange(pageLogicalHeight, pageLogicalHeightChanged, hasSpecifiedPageLogicalHeight);
257
258     RenderStyle* styleToUse = style();
259     LayoutStateMaintainer statePusher(&view(), this, locationOffset(), hasColumns() || hasTransform() || hasReflection() || styleToUse->isFlippedBlocksWritingMode(), pageLogicalHeight, pageLogicalHeightChanged, columnInfo());
260
261     // Regions changing widths can force us to relayout our children.
262     RenderFlowThread* flowThread = flowThreadContainingBlock();
263     if (logicalWidthChangedInRegions(flowThread))
264         relayoutChildren = true;
265     if (updateShapesBeforeBlockLayout())
266         relayoutChildren = true;
267
268     // We use four values, maxTopPos, maxTopNeg, maxBottomPos, and maxBottomNeg, to track
269     // our current maximal positive and negative margins. These values are used when we
270     // are collapsed with adjacent blocks, so for example, if you have block A and B
271     // collapsing together, then you'd take the maximal positive margin from both A and B
272     // and subtract it from the maximal negative margin from both A and B to get the
273     // true collapsed margin. This algorithm is recursive, so when we finish layout()
274     // our block knows its current maximal positive/negative values.
275     //
276     // Start out by setting our margin values to our current margins. Table cells have
277     // no margins, so we don't fill in the values for table cells.
278     bool isCell = isTableCell();
279     if (!isCell) {
280         initMaxMarginValues();
281         
282         setHasMarginBeforeQuirk(styleToUse->hasMarginBeforeQuirk());
283         setHasMarginAfterQuirk(styleToUse->hasMarginAfterQuirk());
284         setPaginationStrut(0);
285     }
286
287     LayoutUnit repaintLogicalTop = 0;
288     LayoutUnit repaintLogicalBottom = 0;
289     LayoutUnit maxFloatLogicalBottom = 0;
290     if (!firstChild() && !isAnonymousBlock())
291         setChildrenInline(true);
292     if (childrenInline())
293         layoutInlineChildren(relayoutChildren, repaintLogicalTop, repaintLogicalBottom);
294     else
295         layoutBlockChildren(relayoutChildren, maxFloatLogicalBottom);
296
297     // Expand our intrinsic height to encompass floats.
298     LayoutUnit toAdd = borderAndPaddingAfter() + scrollbarLogicalHeight();
299     if (lowestFloatLogicalBottom() > (logicalHeight() - toAdd) && expandsToEncloseOverhangingFloats())
300         setLogicalHeight(lowestFloatLogicalBottom() + toAdd);
301     
302     if (relayoutForPagination(hasSpecifiedPageLogicalHeight, pageLogicalHeight, statePusher) || relayoutToAvoidWidows(statePusher)) {
303         ASSERT(!shouldBreakAtLineToAvoidWidow());
304         return;
305     }
306
307     // Calculate our new height.
308     LayoutUnit oldHeight = logicalHeight();
309     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
310
311     // Before updating the final size of the flow thread make sure a forced break is applied after the content.
312     // This ensures the size information is correctly computed for the last auto-height region receiving content.
313     if (isRenderFlowThread())
314         toRenderFlowThread(this)->applyBreakAfterContent(oldClientAfterEdge);
315
316     updateLogicalHeight();
317     LayoutUnit newHeight = logicalHeight();
318     if (oldHeight != newHeight) {
319         if (oldHeight > newHeight && maxFloatLogicalBottom > newHeight && !childrenInline()) {
320             // One of our children's floats may have become an overhanging float for us. We need to look for it.
321             for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
322                 if (child->isRenderBlockFlow() && !child->isFloatingOrOutOfFlowPositioned()) {
323                     RenderBlockFlow* block = toRenderBlockFlow(child);
324                     if (block->lowestFloatLogicalBottom() + block->logicalTop() > newHeight)
325                         addOverhangingFloats(block, false);
326                 }
327             }
328         }
329     }
330
331     bool heightChanged = (previousHeight != newHeight);
332     if (heightChanged)
333         relayoutChildren = true;
334
335     layoutPositionedObjects(relayoutChildren || isRoot());
336
337     updateShapesAfterBlockLayout(heightChanged);
338
339     // Add overflow from children (unless we're multi-column, since in that case all our child overflow is clipped anyway).
340     computeOverflow(oldClientAfterEdge);
341     
342     statePusher.pop();
343
344     fitBorderToLinesIfNeeded();
345
346     if (view().layoutState()->m_pageLogicalHeight)
347         setPageLogicalOffset(view().layoutState()->pageLogicalOffset(this, logicalTop()));
348
349     updateLayerTransform();
350
351     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
352     // we overflow or not.
353     updateScrollInfoAfterLayout();
354
355     // FIXME: This repaint logic should be moved into a separate helper function!
356     // Repaint with our new bounds if they are different from our old bounds.
357     bool didFullRepaint = repainter.repaintAfterLayout();
358     if (!didFullRepaint && repaintLogicalTop != repaintLogicalBottom && (styleToUse->visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
359         // FIXME: We could tighten up the left and right invalidation points if we let layoutInlineChildren fill them in based off the particular lines
360         // it had to lay out. We wouldn't need the hasOverflowClip() hack in that case either.
361         LayoutUnit repaintLogicalLeft = logicalLeftVisualOverflow();
362         LayoutUnit repaintLogicalRight = logicalRightVisualOverflow();
363         if (hasOverflowClip()) {
364             // If we have clipped overflow, we should use layout overflow as well, since visual overflow from lines didn't propagate to our block's overflow.
365             // Note the old code did this as well but even for overflow:visible. The addition of hasOverflowClip() at least tightens up the hack a bit.
366             // layoutInlineChildren should be patched to compute the entire repaint rect.
367             repaintLogicalLeft = min(repaintLogicalLeft, logicalLeftLayoutOverflow());
368             repaintLogicalRight = max(repaintLogicalRight, logicalRightLayoutOverflow());
369         }
370         
371         LayoutRect repaintRect;
372         if (isHorizontalWritingMode())
373             repaintRect = LayoutRect(repaintLogicalLeft, repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop);
374         else
375             repaintRect = LayoutRect(repaintLogicalTop, repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft);
376
377         // The repaint rect may be split across columns, in which case adjustRectForColumns() will return the union.
378         adjustRectForColumns(repaintRect);
379
380         repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
381         
382         if (hasOverflowClip()) {
383             // Adjust repaint rect for scroll offset
384             repaintRect.move(-scrolledContentOffset());
385
386             // Don't allow this rect to spill out of our overflow box.
387             repaintRect.intersect(LayoutRect(LayoutPoint(), size()));
388         }
389
390         // Make sure the rect is still non-empty after intersecting for overflow above
391         if (!repaintRect.isEmpty()) {
392             repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
393             if (hasReflection())
394                 repaintRectangle(reflectedRect(repaintRect));
395         }
396     }
397
398     clearNeedsLayout();
399 }
400
401 void RenderBlockFlow::layoutBlockChildren(bool relayoutChildren, LayoutUnit& maxFloatLogicalBottom)
402 {
403     dirtyForLayoutFromPercentageHeightDescendants();
404
405     LayoutUnit beforeEdge = borderAndPaddingBefore();
406     LayoutUnit afterEdge = borderAndPaddingAfter() + scrollbarLogicalHeight();
407
408     setLogicalHeight(beforeEdge);
409     
410     // Lay out our hypothetical grid line as though it occurs at the top of the block.
411     if (view().layoutState()->lineGrid() == this)
412         layoutLineGridBox();
413
414     // The margin struct caches all our current margin collapsing state.
415     MarginInfo marginInfo(this, beforeEdge, afterEdge);
416
417     // Fieldsets need to find their legend and position it inside the border of the object.
418     // The legend then gets skipped during normal layout. The same is true for ruby text.
419     // It doesn't get included in the normal layout process but is instead skipped.
420     RenderObject* childToExclude = layoutSpecialExcludedChild(relayoutChildren);
421
422     LayoutUnit previousFloatLogicalBottom = 0;
423     maxFloatLogicalBottom = 0;
424
425     RenderBox* next = firstChildBox();
426
427     while (next) {
428         RenderBox* child = next;
429         next = child->nextSiblingBox();
430
431         if (childToExclude == child)
432             continue; // Skip this child, since it will be positioned by the specialized subclass (fieldsets and ruby runs).
433
434         updateBlockChildDirtyBitsBeforeLayout(relayoutChildren, child);
435
436         if (child->isOutOfFlowPositioned()) {
437             child->containingBlock()->insertPositionedObject(child);
438             adjustPositionedBlock(child, marginInfo);
439             continue;
440         }
441         if (child->isFloating()) {
442             insertFloatingObject(child);
443             adjustFloatingBlock(marginInfo);
444             continue;
445         }
446
447         // Lay out the child.
448         layoutBlockChild(child, marginInfo, previousFloatLogicalBottom, maxFloatLogicalBottom);
449     }
450     
451     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
452     // determining the correct collapsed bottom margin information.
453     handleAfterSideOfBlock(beforeEdge, afterEdge, marginInfo);
454 }
455
456 void RenderBlockFlow::layoutBlockChild(RenderBox* child, MarginInfo& marginInfo, LayoutUnit& previousFloatLogicalBottom, LayoutUnit& maxFloatLogicalBottom)
457 {
458     LayoutUnit oldPosMarginBefore = maxPositiveMarginBefore();
459     LayoutUnit oldNegMarginBefore = maxNegativeMarginBefore();
460
461     // The child is a normal flow object. Compute the margins we will use for collapsing now.
462     child->computeAndSetBlockDirectionMargins(this);
463
464     // Try to guess our correct logical top position. In most cases this guess will
465     // be correct. Only if we're wrong (when we compute the real logical top position)
466     // will we have to potentially relayout.
467     LayoutUnit estimateWithoutPagination;
468     LayoutUnit logicalTopEstimate = estimateLogicalTopPosition(child, marginInfo, estimateWithoutPagination);
469
470     // Cache our old rect so that we can dirty the proper repaint rects if the child moves.
471     LayoutRect oldRect = child->frameRect();
472     LayoutUnit oldLogicalTop = logicalTopForChild(child);
473
474 #if !ASSERT_DISABLED
475     LayoutSize oldLayoutDelta = view().layoutDelta();
476 #endif
477     // Go ahead and position the child as though it didn't collapse with the top.
478     setLogicalTopForChild(child, logicalTopEstimate, ApplyLayoutDelta);
479     estimateRegionRangeForBoxChild(child);
480
481     RenderBlockFlow* childBlockFlow = child->isRenderBlockFlow() ? toRenderBlockFlow(child) : 0;
482     bool markDescendantsWithFloats = false;
483     if (logicalTopEstimate != oldLogicalTop && !child->avoidsFloats() && childBlockFlow && childBlockFlow->containsFloats())
484         markDescendantsWithFloats = true;
485 #if ENABLE(SUBPIXEL_LAYOUT)
486     else if (UNLIKELY(logicalTopEstimate.mightBeSaturated()))
487         // logicalTopEstimate, returned by estimateLogicalTopPosition, might be saturated for
488         // very large elements. If it does the comparison with oldLogicalTop might yield a
489         // false negative as adding and removing margins, borders etc from a saturated number
490         // might yield incorrect results. If this is the case always mark for layout.
491         markDescendantsWithFloats = true;
492 #endif
493     else if (!child->avoidsFloats() || child->shrinkToAvoidFloats()) {
494         // If an element might be affected by the presence of floats, then always mark it for
495         // layout.
496         LayoutUnit fb = max(previousFloatLogicalBottom, lowestFloatLogicalBottom());
497         if (fb > logicalTopEstimate)
498             markDescendantsWithFloats = true;
499     }
500
501     if (childBlockFlow) {
502         if (markDescendantsWithFloats)
503             childBlockFlow->markAllDescendantsWithFloatsForLayout();
504         if (!child->isWritingModeRoot())
505             previousFloatLogicalBottom = max(previousFloatLogicalBottom, oldLogicalTop + childBlockFlow->lowestFloatLogicalBottom());
506     }
507
508     if (!child->needsLayout())
509         child->markForPaginationRelayoutIfNeeded();
510
511     bool childHadLayout = child->everHadLayout();
512     bool childNeededLayout = child->needsLayout();
513     if (childNeededLayout)
514         child->layout();
515
516     // Cache if we are at the top of the block right now.
517     bool atBeforeSideOfBlock = marginInfo.atBeforeSideOfBlock();
518
519     // Now determine the correct ypos based off examination of collapsing margin
520     // values.
521     LayoutUnit logicalTopBeforeClear = collapseMargins(child, marginInfo);
522
523     // Now check for clear.
524     LayoutUnit logicalTopAfterClear = clearFloatsIfNeeded(child, marginInfo, oldPosMarginBefore, oldNegMarginBefore, logicalTopBeforeClear);
525     
526     bool paginated = view().layoutState()->isPaginated();
527     if (paginated)
528         logicalTopAfterClear = adjustBlockChildForPagination(logicalTopAfterClear, estimateWithoutPagination, child,
529             atBeforeSideOfBlock && logicalTopBeforeClear == logicalTopAfterClear);
530
531     setLogicalTopForChild(child, logicalTopAfterClear, ApplyLayoutDelta);
532
533     // Now we have a final top position. See if it really does end up being different from our estimate.
534     // clearFloatsIfNeeded can also mark the child as needing a layout even though we didn't move. This happens
535     // when collapseMargins dynamically adds overhanging floats because of a child with negative margins.
536     if (logicalTopAfterClear != logicalTopEstimate || child->needsLayout() || (paginated && childBlockFlow && childBlockFlow->shouldBreakAtLineToAvoidWidow())) {
537         if (child->shrinkToAvoidFloats()) {
538             // The child's width depends on the line width.
539             // When the child shifts to clear an item, its width can
540             // change (because it has more available line width).
541             // So go ahead and mark the item as dirty.
542             child->setChildNeedsLayout(MarkOnlyThis);
543         }
544         
545         if (childBlockFlow) {
546             if (!child->avoidsFloats() && childBlockFlow->containsFloats())
547                 childBlockFlow->markAllDescendantsWithFloatsForLayout();
548             if (!child->needsLayout())
549                 child->markForPaginationRelayoutIfNeeded();
550         }
551
552         // Our guess was wrong. Make the child lay itself out again.
553         child->layoutIfNeeded();
554     }
555
556     if (updateRegionRangeForBoxChild(child)) {
557         child->setNeedsLayout(MarkOnlyThis);
558         child->layoutIfNeeded();
559     }
560
561     // We are no longer at the top of the block if we encounter a non-empty child.  
562     // This has to be done after checking for clear, so that margins can be reset if a clear occurred.
563     if (marginInfo.atBeforeSideOfBlock() && !child->isSelfCollapsingBlock())
564         marginInfo.setAtBeforeSideOfBlock(false);
565
566     // Now place the child in the correct left position
567     determineLogicalLeftPositionForChild(child, ApplyLayoutDelta);
568
569     LayoutSize childOffset = child->location() - oldRect.location();
570 #if ENABLE(CSS_SHAPES)
571     relayoutShapeDescendantIfMoved(child->isRenderBlock() ? toRenderBlock(child) : 0, childOffset);
572 #endif
573
574     // Update our height now that the child has been placed in the correct position.
575     setLogicalHeight(logicalHeight() + logicalHeightForChild(child));
576     if (mustSeparateMarginAfterForChild(child)) {
577         setLogicalHeight(logicalHeight() + marginAfterForChild(child));
578         marginInfo.clearMargin();
579     }
580     // If the child has overhanging floats that intrude into following siblings (or possibly out
581     // of this block), then the parent gets notified of the floats now.
582     if (childBlockFlow && childBlockFlow->containsFloats())
583         maxFloatLogicalBottom = max(maxFloatLogicalBottom, addOverhangingFloats(toRenderBlockFlow(child), !childNeededLayout));
584
585     if (childOffset.width() || childOffset.height()) {
586         view().addLayoutDelta(childOffset);
587
588         // If the child moved, we have to repaint it as well as any floating/positioned
589         // descendants. An exception is if we need a layout. In this case, we know we're going to
590         // repaint ourselves (and the child) anyway.
591         if (childHadLayout && !selfNeedsLayout() && child->checkForRepaintDuringLayout())
592             child->repaintDuringLayoutIfMoved(oldRect);
593     }
594
595     if (!childHadLayout && child->checkForRepaintDuringLayout()) {
596         child->repaint();
597         child->repaintOverhangingFloats(true);
598     }
599
600     if (paginated) {
601         // Check for an after page/column break.
602         LayoutUnit newHeight = applyAfterBreak(child, logicalHeight(), marginInfo);
603         if (newHeight != height())
604             setLogicalHeight(newHeight);
605     }
606
607     ASSERT(view().layoutDeltaMatches(oldLayoutDelta));
608 }
609
610 void RenderBlockFlow::adjustPositionedBlock(RenderBox* child, const MarginInfo& marginInfo)
611 {
612     bool isHorizontal = isHorizontalWritingMode();
613     bool hasStaticBlockPosition = child->style()->hasStaticBlockPosition(isHorizontal);
614     
615     LayoutUnit logicalTop = logicalHeight();
616     updateStaticInlinePositionForChild(child, logicalTop);
617
618     if (!marginInfo.canCollapseWithMarginBefore()) {
619         // Positioned blocks don't collapse margins, so add the margin provided by
620         // the container now. The child's own margin is added later when calculating its logical top.
621         LayoutUnit collapsedBeforePos = marginInfo.positiveMargin();
622         LayoutUnit collapsedBeforeNeg = marginInfo.negativeMargin();
623         logicalTop += collapsedBeforePos - collapsedBeforeNeg;
624     }
625     
626     RenderLayer* childLayer = child->layer();
627     if (childLayer->staticBlockPosition() != logicalTop) {
628         childLayer->setStaticBlockPosition(logicalTop);
629         if (hasStaticBlockPosition)
630             child->setChildNeedsLayout(MarkOnlyThis);
631     }
632 }
633
634 void RenderBlockFlow::adjustFloatingBlock(const MarginInfo& marginInfo)
635 {
636     // The float should be positioned taking into account the bottom margin
637     // of the previous flow. We add that margin into the height, get the
638     // float positioned properly, and then subtract the margin out of the
639     // height again. In the case of self-collapsing blocks, we always just
640     // use the top margins, since the self-collapsing block collapsed its
641     // own bottom margin into its top margin.
642     //
643     // Note also that the previous flow may collapse its margin into the top of
644     // our block. If this is the case, then we do not add the margin in to our
645     // height when computing the position of the float. This condition can be tested
646     // for by simply calling canCollapseWithMarginBefore. See
647     // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
648     // an example of this scenario.
649     LayoutUnit marginOffset = marginInfo.canCollapseWithMarginBefore() ? LayoutUnit() : marginInfo.margin();
650     setLogicalHeight(logicalHeight() + marginOffset);
651     positionNewFloats();
652     setLogicalHeight(logicalHeight() - marginOffset);
653 }
654
655 RenderBlockFlow::MarginValues RenderBlockFlow::marginValuesForChild(RenderBox* child) const
656 {
657     LayoutUnit childBeforePositive = 0;
658     LayoutUnit childBeforeNegative = 0;
659     LayoutUnit childAfterPositive = 0;
660     LayoutUnit childAfterNegative = 0;
661
662     LayoutUnit beforeMargin = 0;
663     LayoutUnit afterMargin = 0;
664
665     RenderBlockFlow* childRenderBlock = child->isRenderBlockFlow() ? toRenderBlockFlow(child) : 0;
666     
667     // If the child has the same directionality as we do, then we can just return its
668     // margins in the same direction.
669     if (!child->isWritingModeRoot()) {
670         if (childRenderBlock) {
671             childBeforePositive = childRenderBlock->maxPositiveMarginBefore();
672             childBeforeNegative = childRenderBlock->maxNegativeMarginBefore();
673             childAfterPositive = childRenderBlock->maxPositiveMarginAfter();
674             childAfterNegative = childRenderBlock->maxNegativeMarginAfter();
675         } else {
676             beforeMargin = child->marginBefore();
677             afterMargin = child->marginAfter();
678         }
679     } else if (child->isHorizontalWritingMode() == isHorizontalWritingMode()) {
680         // The child has a different directionality. If the child is parallel, then it's just
681         // flipped relative to us. We can use the margins for the opposite edges.
682         if (childRenderBlock) {
683             childBeforePositive = childRenderBlock->maxPositiveMarginAfter();
684             childBeforeNegative = childRenderBlock->maxNegativeMarginAfter();
685             childAfterPositive = childRenderBlock->maxPositiveMarginBefore();
686             childAfterNegative = childRenderBlock->maxNegativeMarginBefore();
687         } else {
688             beforeMargin = child->marginAfter();
689             afterMargin = child->marginBefore();
690         }
691     } else {
692         // The child is perpendicular to us, which means its margins don't collapse but are on the
693         // "logical left/right" sides of the child box. We can just return the raw margin in this case.
694         beforeMargin = marginBeforeForChild(child);
695         afterMargin = marginAfterForChild(child);
696     }
697
698     // Resolve uncollapsing margins into their positive/negative buckets.
699     if (beforeMargin) {
700         if (beforeMargin > 0)
701             childBeforePositive = beforeMargin;
702         else
703             childBeforeNegative = -beforeMargin;
704     }
705     if (afterMargin) {
706         if (afterMargin > 0)
707             childAfterPositive = afterMargin;
708         else
709             childAfterNegative = -afterMargin;
710     }
711
712     return MarginValues(childBeforePositive, childBeforeNegative, childAfterPositive, childAfterNegative);
713 }
714
715 LayoutUnit RenderBlockFlow::collapseMargins(RenderBox* child, MarginInfo& marginInfo)
716 {
717     bool childDiscardMarginBefore = mustDiscardMarginBeforeForChild(child);
718     bool childDiscardMarginAfter = mustDiscardMarginAfterForChild(child);
719     bool childIsSelfCollapsing = child->isSelfCollapsingBlock();
720
721     // The child discards the before margin when the the after margin has discard in the case of a self collapsing block.
722     childDiscardMarginBefore = childDiscardMarginBefore || (childDiscardMarginAfter && childIsSelfCollapsing);
723
724     // Get the four margin values for the child and cache them.
725     const MarginValues childMargins = marginValuesForChild(child);
726
727     // Get our max pos and neg top margins.
728     LayoutUnit posTop = childMargins.positiveMarginBefore();
729     LayoutUnit negTop = childMargins.negativeMarginBefore();
730
731     // For self-collapsing blocks, collapse our bottom margins into our
732     // top to get new posTop and negTop values.
733     if (childIsSelfCollapsing) {
734         posTop = max(posTop, childMargins.positiveMarginAfter());
735         negTop = max(negTop, childMargins.negativeMarginAfter());
736     }
737     
738     // See if the top margin is quirky. We only care if this child has
739     // margins that will collapse with us.
740     bool topQuirk = hasMarginBeforeQuirk(child);
741
742     if (marginInfo.canCollapseWithMarginBefore()) {
743         if (!childDiscardMarginBefore && !marginInfo.discardMargin()) {
744             // This child is collapsing with the top of the
745             // block. If it has larger margin values, then we need to update
746             // our own maximal values.
747             if (!document().inQuirksMode() || !marginInfo.quirkContainer() || !topQuirk)
748                 setMaxMarginBeforeValues(max(posTop, maxPositiveMarginBefore()), max(negTop, maxNegativeMarginBefore()));
749
750             // The minute any of the margins involved isn't a quirk, don't
751             // collapse it away, even if the margin is smaller (www.webreference.com
752             // has an example of this, a <dt> with 0.8em author-specified inside
753             // a <dl> inside a <td>.
754             if (!marginInfo.determinedMarginBeforeQuirk() && !topQuirk && (posTop - negTop)) {
755                 setHasMarginBeforeQuirk(false);
756                 marginInfo.setDeterminedMarginBeforeQuirk(true);
757             }
758
759             if (!marginInfo.determinedMarginBeforeQuirk() && topQuirk && !marginBefore())
760                 // We have no top margin and our top child has a quirky margin.
761                 // We will pick up this quirky margin and pass it through.
762                 // This deals with the <td><div><p> case.
763                 // Don't do this for a block that split two inlines though. You do
764                 // still apply margins in this case.
765                 setHasMarginBeforeQuirk(true);
766         } else
767             // The before margin of the container will also discard all the margins it is collapsing with.
768             setMustDiscardMarginBefore();
769     }
770
771     // Once we find a child with discardMarginBefore all the margins collapsing with us must also discard. 
772     if (childDiscardMarginBefore) {
773         marginInfo.setDiscardMargin(true);
774         marginInfo.clearMargin();
775     }
776
777     if (marginInfo.quirkContainer() && marginInfo.atBeforeSideOfBlock() && (posTop - negTop))
778         marginInfo.setHasMarginBeforeQuirk(topQuirk);
779
780     LayoutUnit beforeCollapseLogicalTop = logicalHeight();
781     LayoutUnit logicalTop = beforeCollapseLogicalTop;
782     if (childIsSelfCollapsing) {
783         // For a self collapsing block both the before and after margins get discarded. The block doesn't contribute anything to the height of the block.
784         // Also, the child's top position equals the logical height of the container.
785         if (!childDiscardMarginBefore && !marginInfo.discardMargin()) {
786             // This child has no height. We need to compute our
787             // position before we collapse the child's margins together,
788             // so that we can get an accurate position for the zero-height block.
789             LayoutUnit collapsedBeforePos = max(marginInfo.positiveMargin(), childMargins.positiveMarginBefore());
790             LayoutUnit collapsedBeforeNeg = max(marginInfo.negativeMargin(), childMargins.negativeMarginBefore());
791             marginInfo.setMargin(collapsedBeforePos, collapsedBeforeNeg);
792             
793             // Now collapse the child's margins together, which means examining our
794             // bottom margin values as well. 
795             marginInfo.setPositiveMarginIfLarger(childMargins.positiveMarginAfter());
796             marginInfo.setNegativeMarginIfLarger(childMargins.negativeMarginAfter());
797
798             if (!marginInfo.canCollapseWithMarginBefore())
799                 // We need to make sure that the position of the self-collapsing block
800                 // is correct, since it could have overflowing content
801                 // that needs to be positioned correctly (e.g., a block that
802                 // had a specified height of 0 but that actually had subcontent).
803                 logicalTop = logicalHeight() + collapsedBeforePos - collapsedBeforeNeg;
804         }
805     } else {
806         if (mustSeparateMarginBeforeForChild(child)) {
807             ASSERT(!marginInfo.discardMargin() || (marginInfo.discardMargin() && !marginInfo.margin()));
808             // If we are at the before side of the block and we collapse, ignore the computed margin
809             // and just add the child margin to the container height. This will correctly position
810             // the child inside the container.
811             LayoutUnit separateMargin = !marginInfo.canCollapseWithMarginBefore() ? marginInfo.margin() : LayoutUnit(0);
812             setLogicalHeight(logicalHeight() + separateMargin + marginBeforeForChild(child));
813             logicalTop = logicalHeight();
814         } else if (!marginInfo.discardMargin() && (!marginInfo.atBeforeSideOfBlock()
815             || (!marginInfo.canCollapseMarginBeforeWithChildren()
816             && (!document().inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.hasMarginBeforeQuirk())))) {
817             // We're collapsing with a previous sibling's margins and not
818             // with the top of the block.
819             setLogicalHeight(logicalHeight() + max(marginInfo.positiveMargin(), posTop) - max(marginInfo.negativeMargin(), negTop));
820             logicalTop = logicalHeight();
821         }
822
823         marginInfo.setDiscardMargin(childDiscardMarginAfter);
824         
825         if (!marginInfo.discardMargin()) {
826             marginInfo.setPositiveMargin(childMargins.positiveMarginAfter());
827             marginInfo.setNegativeMargin(childMargins.negativeMarginAfter());
828         } else
829             marginInfo.clearMargin();
830
831         if (marginInfo.margin())
832             marginInfo.setHasMarginAfterQuirk(hasMarginAfterQuirk(child));
833     }
834     
835     // If margins would pull us past the top of the next page, then we need to pull back and pretend like the margins
836     // collapsed into the page edge.
837     LayoutState* layoutState = view().layoutState();
838     if (layoutState->isPaginated() && layoutState->pageLogicalHeight() && logicalTop > beforeCollapseLogicalTop
839         && hasNextPage(beforeCollapseLogicalTop)) {
840         LayoutUnit oldLogicalTop = logicalTop;
841         logicalTop = min(logicalTop, nextPageLogicalTop(beforeCollapseLogicalTop));
842         setLogicalHeight(logicalHeight() + (logicalTop - oldLogicalTop));
843     }
844
845     // If we have collapsed into a previous sibling and so reduced the height of the parent, ensure any floats that now
846     // overhang from the previous sibling are added to our parent. If the child's previous sibling itself is a float the child will avoid
847     // or clear it anyway, so don't worry about any floating children it may contain.
848     LayoutUnit oldLogicalHeight = logicalHeight();
849     setLogicalHeight(logicalTop);
850     RenderObject* prev = child->previousSibling();
851     if (prev && prev->isRenderBlockFlow() && !prev->isFloatingOrOutOfFlowPositioned()) {
852         RenderBlockFlow* block = toRenderBlockFlow(prev);
853         if (block->containsFloats() && !block->avoidsFloats() && (block->logicalTop() + block->lowestFloatLogicalBottom()) > logicalTop) 
854             addOverhangingFloats(block, false);
855     }
856     setLogicalHeight(oldLogicalHeight);
857
858     return logicalTop;
859 }
860
861 LayoutUnit RenderBlockFlow::clearFloatsIfNeeded(RenderBox* child, MarginInfo& marginInfo, LayoutUnit oldTopPosMargin, LayoutUnit oldTopNegMargin, LayoutUnit yPos)
862 {
863     LayoutUnit heightIncrease = getClearDelta(child, yPos);
864     if (!heightIncrease)
865         return yPos;
866
867     if (child->isSelfCollapsingBlock()) {
868         bool childDiscardMargin = mustDiscardMarginBeforeForChild(child) || mustDiscardMarginAfterForChild(child);
869
870         // For self-collapsing blocks that clear, they can still collapse their
871         // margins with following siblings. Reset the current margins to represent
872         // the self-collapsing block's margins only.
873         // If DISCARD is specified for -webkit-margin-collapse, reset the margin values.
874         if (!childDiscardMargin) {
875             MarginValues childMargins = marginValuesForChild(child);
876             marginInfo.setPositiveMargin(max(childMargins.positiveMarginBefore(), childMargins.positiveMarginAfter()));
877             marginInfo.setNegativeMargin(max(childMargins.negativeMarginBefore(), childMargins.negativeMarginAfter()));
878         } else
879             marginInfo.clearMargin();
880         marginInfo.setDiscardMargin(childDiscardMargin);
881
882         // CSS2.1 states:
883         // "If the top and bottom margins of an element with clearance are adjoining, its margins collapse with 
884         // the adjoining margins of following siblings but that resulting margin does not collapse with the bottom margin of the parent block."
885         // So the parent's bottom margin cannot collapse through this block or any subsequent self-collapsing blocks. Check subsequent siblings
886         // for a block with height - if none is found then don't allow the margins to collapse with the parent.
887         bool wouldCollapseMarginsWithParent = marginInfo.canCollapseMarginAfterWithChildren();
888         for (RenderBox* curr = child->nextSiblingBox(); curr && wouldCollapseMarginsWithParent; curr = curr->nextSiblingBox()) {
889             if (!curr->isFloatingOrOutOfFlowPositioned() && !curr->isSelfCollapsingBlock())
890                 wouldCollapseMarginsWithParent = false;
891         }
892         if (wouldCollapseMarginsWithParent)
893             marginInfo.setCanCollapseMarginAfterWithChildren(false);
894
895         // CSS2.1: "the amount of clearance is set so that clearance + margin-top = [height of float], i.e., clearance = [height of float] - margin-top"
896         // Move the top of the child box to the bottom of the float ignoring the child's top margin.
897         LayoutUnit collapsedMargin = collapsedMarginBeforeForChild(child);
898         setLogicalHeight(child->logicalTop() - collapsedMargin);
899         // A negative collapsed margin-top value cancels itself out as it has already been factored into |yPos| above.
900         heightIncrease -= max(LayoutUnit(), collapsedMargin);
901     } else
902         // Increase our height by the amount we had to clear.
903         setLogicalHeight(logicalHeight() + heightIncrease);
904     
905     if (marginInfo.canCollapseWithMarginBefore()) {
906         // We can no longer collapse with the top of the block since a clear
907         // occurred. The empty blocks collapse into the cleared block.
908         // FIXME: This isn't quite correct. Need clarification for what to do
909         // if the height the cleared block is offset by is smaller than the
910         // margins involved.
911         setMaxMarginBeforeValues(oldTopPosMargin, oldTopNegMargin);
912         marginInfo.setAtBeforeSideOfBlock(false);
913
914         // In case the child discarded the before margin of the block we need to reset the mustDiscardMarginBefore flag to the initial value.
915         setMustDiscardMarginBefore(style()->marginBeforeCollapse() == MDISCARD);
916     }
917
918     LayoutUnit logicalTop = yPos + heightIncrease;
919     // After margin collapsing, one of our floats may now intrude into the child. If the child doesn't contain floats of its own it
920     // won't get picked up for relayout even though the logical top estimate was wrong - so add the newly intruding float now.
921     if (containsFloats() && child->isRenderBlockFlow() && !toRenderBlockFlow(child)->containsFloats() && !child->avoidsFloats() && lowestFloatLogicalBottom() > logicalTop)
922         toRenderBlockFlow(child)->addIntrudingFloats(this, logicalLeftOffsetForContent(), logicalTop);
923
924     return logicalTop;
925 }
926
927 void RenderBlockFlow::marginBeforeEstimateForChild(RenderBox* child, LayoutUnit& positiveMarginBefore, LayoutUnit& negativeMarginBefore, bool& discardMarginBefore) const
928 {
929     // Give up if in quirks mode and we're a body/table cell and the top margin of the child box is quirky.
930     // Give up if the child specified -webkit-margin-collapse: separate that prevents collapsing.
931     // FIXME: Use writing mode independent accessor for marginBeforeCollapse.
932     if ((document().inQuirksMode() && hasMarginAfterQuirk(child) && (isTableCell() || isBody())) || child->style()->marginBeforeCollapse() == MSEPARATE)
933         return;
934
935     // The margins are discarded by a child that specified -webkit-margin-collapse: discard.
936     // FIXME: Use writing mode independent accessor for marginBeforeCollapse.
937     if (child->style()->marginBeforeCollapse() == MDISCARD) {
938         positiveMarginBefore = 0;
939         negativeMarginBefore = 0;
940         discardMarginBefore = true;
941         return;
942     }
943
944     LayoutUnit beforeChildMargin = marginBeforeForChild(child);
945     positiveMarginBefore = max(positiveMarginBefore, beforeChildMargin);
946     negativeMarginBefore = max(negativeMarginBefore, -beforeChildMargin);
947
948     if (!child->isRenderBlockFlow())
949         return;
950     
951     RenderBlockFlow* childBlock = toRenderBlockFlow(child);
952     if (childBlock->childrenInline() || childBlock->isWritingModeRoot())
953         return;
954
955     MarginInfo childMarginInfo(childBlock, childBlock->borderAndPaddingBefore(), childBlock->borderAndPaddingAfter());
956     if (!childMarginInfo.canCollapseMarginBeforeWithChildren())
957         return;
958
959     RenderBox* grandchildBox = childBlock->firstChildBox();
960     for ( ; grandchildBox; grandchildBox = grandchildBox->nextSiblingBox()) {
961         if (!grandchildBox->isFloatingOrOutOfFlowPositioned())
962             break;
963     }
964     
965     // Give up if there is clearance on the box, since it probably won't collapse into us.
966     if (!grandchildBox || grandchildBox->style()->clear() != CNONE)
967         return;
968
969     // Make sure to update the block margins now for the grandchild box so that we're looking at current values.
970     if (grandchildBox->needsLayout()) {
971         grandchildBox->computeAndSetBlockDirectionMargins(this);
972         if (grandchildBox->isRenderBlock()) {
973             RenderBlock* grandchildBlock = toRenderBlock(grandchildBox);
974             grandchildBlock->setHasMarginBeforeQuirk(grandchildBox->style()->hasMarginBeforeQuirk());
975             grandchildBlock->setHasMarginAfterQuirk(grandchildBox->style()->hasMarginAfterQuirk());
976         }
977     }
978
979     // Collapse the margin of the grandchild box with our own to produce an estimate.
980     childBlock->marginBeforeEstimateForChild(grandchildBox, positiveMarginBefore, negativeMarginBefore, discardMarginBefore);
981 }
982
983 LayoutUnit RenderBlockFlow::estimateLogicalTopPosition(RenderBox* child, const MarginInfo& marginInfo, LayoutUnit& estimateWithoutPagination)
984 {
985     // FIXME: We need to eliminate the estimation of vertical position, because when it's wrong we sometimes trigger a pathological
986     // relayout if there are intruding floats.
987     LayoutUnit logicalTopEstimate = logicalHeight();
988     if (!marginInfo.canCollapseWithMarginBefore()) {
989         LayoutUnit positiveMarginBefore = 0;
990         LayoutUnit negativeMarginBefore = 0;
991         bool discardMarginBefore = false;
992         if (child->selfNeedsLayout()) {
993             // Try to do a basic estimation of how the collapse is going to go.
994             marginBeforeEstimateForChild(child, positiveMarginBefore, negativeMarginBefore, discardMarginBefore);
995         } else {
996             // Use the cached collapsed margin values from a previous layout. Most of the time they
997             // will be right.
998             MarginValues marginValues = marginValuesForChild(child);
999             positiveMarginBefore = max(positiveMarginBefore, marginValues.positiveMarginBefore());
1000             negativeMarginBefore = max(negativeMarginBefore, marginValues.negativeMarginBefore());
1001             discardMarginBefore = mustDiscardMarginBeforeForChild(child);
1002         }
1003
1004         // Collapse the result with our current margins.
1005         if (!discardMarginBefore)
1006             logicalTopEstimate += max(marginInfo.positiveMargin(), positiveMarginBefore) - max(marginInfo.negativeMargin(), negativeMarginBefore);
1007     }
1008
1009     // Adjust logicalTopEstimate down to the next page if the margins are so large that we don't fit on the current
1010     // page.
1011     LayoutState* layoutState = view().layoutState();
1012     if (layoutState->isPaginated() && layoutState->pageLogicalHeight() && logicalTopEstimate > logicalHeight()
1013         && hasNextPage(logicalHeight()))
1014         logicalTopEstimate = min(logicalTopEstimate, nextPageLogicalTop(logicalHeight()));
1015
1016     logicalTopEstimate += getClearDelta(child, logicalTopEstimate);
1017     
1018     estimateWithoutPagination = logicalTopEstimate;
1019
1020     if (layoutState->isPaginated()) {
1021         // If the object has a page or column break value of "before", then we should shift to the top of the next page.
1022         logicalTopEstimate = applyBeforeBreak(child, logicalTopEstimate);
1023     
1024         // For replaced elements and scrolled elements, we want to shift them to the next page if they don't fit on the current one.
1025         logicalTopEstimate = adjustForUnsplittableChild(child, logicalTopEstimate);
1026         
1027         if (!child->selfNeedsLayout() && child->isRenderBlock())
1028             logicalTopEstimate += toRenderBlock(child)->paginationStrut();
1029     }
1030
1031     return logicalTopEstimate;
1032 }
1033
1034 void RenderBlockFlow::setCollapsedBottomMargin(const MarginInfo& marginInfo)
1035 {
1036     if (marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()) {
1037         // Update the after side margin of the container to discard if the after margin of the last child also discards and we collapse with it.
1038         // Don't update the max margin values because we won't need them anyway.
1039         if (marginInfo.discardMargin()) {
1040             setMustDiscardMarginAfter();
1041             return;
1042         }
1043
1044         // Update our max pos/neg bottom margins, since we collapsed our bottom margins
1045         // with our children.
1046         setMaxMarginAfterValues(max(maxPositiveMarginAfter(), marginInfo.positiveMargin()), max(maxNegativeMarginAfter(), marginInfo.negativeMargin()));
1047
1048         if (!marginInfo.hasMarginAfterQuirk())
1049             setHasMarginAfterQuirk(false);
1050
1051         if (marginInfo.hasMarginAfterQuirk() && !marginAfter())
1052             // We have no bottom margin and our last child has a quirky margin.
1053             // We will pick up this quirky margin and pass it through.
1054             // This deals with the <td><div><p> case.
1055             setHasMarginAfterQuirk(true);
1056     }
1057 }
1058
1059 void RenderBlockFlow::handleAfterSideOfBlock(LayoutUnit beforeSide, LayoutUnit afterSide, MarginInfo& marginInfo)
1060 {
1061     marginInfo.setAtAfterSideOfBlock(true);
1062
1063     // If we can't collapse with children then go ahead and add in the bottom margin.
1064     if (!marginInfo.discardMargin() && (!marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()
1065         && (!document().inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.hasMarginAfterQuirk())))
1066         setLogicalHeight(logicalHeight() + marginInfo.margin());
1067         
1068     // Now add in our bottom border/padding.
1069     setLogicalHeight(logicalHeight() + afterSide);
1070
1071     // Negative margins can cause our height to shrink below our minimal height (border/padding).
1072     // If this happens, ensure that the computed height is increased to the minimal height.
1073     setLogicalHeight(max(logicalHeight(), beforeSide + afterSide));
1074
1075     // Update our bottom collapsed margin info.
1076     setCollapsedBottomMargin(marginInfo);
1077 }
1078
1079 void RenderBlockFlow::setMaxMarginBeforeValues(LayoutUnit pos, LayoutUnit neg)
1080 {
1081     if (!m_rareData) {
1082         if (pos == RenderBlockFlowRareData::positiveMarginBeforeDefault(this) && neg == RenderBlockFlowRareData::negativeMarginBeforeDefault(this))
1083             return;
1084         m_rareData = adoptPtr(new RenderBlockFlowRareData(this));
1085     }
1086     m_rareData->m_margins.setPositiveMarginBefore(pos);
1087     m_rareData->m_margins.setNegativeMarginBefore(neg);
1088 }
1089
1090 void RenderBlockFlow::setMaxMarginAfterValues(LayoutUnit pos, LayoutUnit neg)
1091 {
1092     if (!m_rareData) {
1093         if (pos == RenderBlockFlowRareData::positiveMarginAfterDefault(this) && neg == RenderBlockFlowRareData::negativeMarginAfterDefault(this))
1094             return;
1095         m_rareData = adoptPtr(new RenderBlockFlowRareData(this));
1096     }
1097     m_rareData->m_margins.setPositiveMarginAfter(pos);
1098     m_rareData->m_margins.setNegativeMarginAfter(neg);
1099 }
1100
1101 void RenderBlockFlow::setMustDiscardMarginBefore(bool value)
1102 {
1103     if (style()->marginBeforeCollapse() == MDISCARD) {
1104         ASSERT(value);
1105         return;
1106     }
1107     
1108     if (!m_rareData && !value)
1109         return;
1110
1111     if (!m_rareData)
1112         m_rareData = adoptPtr(new RenderBlockFlowRareData(this));
1113
1114     m_rareData->m_discardMarginBefore = value;
1115 }
1116
1117 void RenderBlockFlow::setMustDiscardMarginAfter(bool value)
1118 {
1119     if (style()->marginAfterCollapse() == MDISCARD) {
1120         ASSERT(value);
1121         return;
1122     }
1123
1124     if (!m_rareData && !value)
1125         return;
1126
1127     if (!m_rareData)
1128         m_rareData = adoptPtr(new RenderBlockFlowRareData(this));
1129
1130     m_rareData->m_discardMarginAfter = value;
1131 }
1132
1133 bool RenderBlockFlow::mustDiscardMarginBefore() const
1134 {
1135     return style()->marginBeforeCollapse() == MDISCARD || (m_rareData && m_rareData->m_discardMarginBefore);
1136 }
1137
1138 bool RenderBlockFlow::mustDiscardMarginAfter() const
1139 {
1140     return style()->marginAfterCollapse() == MDISCARD || (m_rareData && m_rareData->m_discardMarginAfter);
1141 }
1142
1143 bool RenderBlockFlow::mustDiscardMarginBeforeForChild(const RenderBox* child) const
1144 {
1145     ASSERT(!child->selfNeedsLayout());
1146     if (!child->isWritingModeRoot())
1147         return child->isRenderBlockFlow() ? toRenderBlockFlow(child)->mustDiscardMarginBefore() : (child->style()->marginBeforeCollapse() == MDISCARD);
1148     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
1149         return child->isRenderBlockFlow() ? toRenderBlockFlow(child)->mustDiscardMarginAfter() : (child->style()->marginAfterCollapse() == MDISCARD);
1150
1151     // FIXME: We return false here because the implementation is not geometrically complete. We have values only for before/after, not start/end.
1152     // In case the boxes are perpendicular we assume the property is not specified.
1153     return false;
1154 }
1155
1156 bool RenderBlockFlow::mustDiscardMarginAfterForChild(const RenderBox* child) const
1157 {
1158     ASSERT(!child->selfNeedsLayout());
1159     if (!child->isWritingModeRoot())
1160         return child->isRenderBlockFlow() ? toRenderBlockFlow(child)->mustDiscardMarginAfter() : (child->style()->marginAfterCollapse() == MDISCARD);
1161     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
1162         return child->isRenderBlockFlow() ? toRenderBlockFlow(child)->mustDiscardMarginBefore() : (child->style()->marginBeforeCollapse() == MDISCARD);
1163
1164     // FIXME: See |mustDiscardMarginBeforeForChild| above.
1165     return false;
1166 }
1167
1168 bool RenderBlockFlow::mustSeparateMarginBeforeForChild(const RenderBox* child) const
1169 {
1170     ASSERT(!child->selfNeedsLayout());
1171     const RenderStyle* childStyle = child->style();
1172     if (!child->isWritingModeRoot())
1173         return childStyle->marginBeforeCollapse() == MSEPARATE;
1174     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
1175         return childStyle->marginAfterCollapse() == MSEPARATE;
1176
1177     // FIXME: See |mustDiscardMarginBeforeForChild| above.
1178     return false;
1179 }
1180
1181 bool RenderBlockFlow::mustSeparateMarginAfterForChild(const RenderBox* child) const
1182 {
1183     ASSERT(!child->selfNeedsLayout());
1184     const RenderStyle* childStyle = child->style();
1185     if (!child->isWritingModeRoot())
1186         return childStyle->marginAfterCollapse() == MSEPARATE;
1187     if (child->isHorizontalWritingMode() == isHorizontalWritingMode())
1188         return childStyle->marginBeforeCollapse() == MSEPARATE;
1189
1190     // FIXME: See |mustDiscardMarginBeforeForChild| above.
1191     return false;
1192 }
1193
1194 static bool inNormalFlow(RenderBox* child)
1195 {
1196     RenderBlock* curr = child->containingBlock();
1197     while (curr && curr != &child->view()) {
1198         if (curr->hasColumns() || curr->isRenderFlowThread())
1199             return true;
1200         if (curr->isFloatingOrOutOfFlowPositioned())
1201             return false;
1202         curr = curr->containingBlock();
1203     }
1204     return true;
1205 }
1206
1207 LayoutUnit RenderBlockFlow::applyBeforeBreak(RenderBox* child, LayoutUnit logicalOffset)
1208 {
1209     // FIXME: Add page break checking here when we support printing.
1210     bool checkColumnBreaks = view().layoutState()->isPaginatingColumns();
1211     bool checkPageBreaks = !checkColumnBreaks && view().layoutState()->m_pageLogicalHeight; // FIXME: Once columns can print we have to check this.
1212     RenderFlowThread* flowThread = flowThreadContainingBlock();
1213     bool checkRegionBreaks = flowThread && flowThread->isRenderNamedFlowThread();
1214     bool checkBeforeAlways = (checkColumnBreaks && child->style()->columnBreakBefore() == PBALWAYS) || (checkPageBreaks && child->style()->pageBreakBefore() == PBALWAYS)
1215         || (checkRegionBreaks && child->style()->regionBreakBefore() == PBALWAYS);
1216     if (checkBeforeAlways && inNormalFlow(child) && hasNextPage(logicalOffset, IncludePageBoundary)) {
1217         if (checkColumnBreaks)
1218             view().layoutState()->addForcedColumnBreak(child, logicalOffset);
1219         if (checkRegionBreaks) {
1220             LayoutUnit offsetBreakAdjustment = 0;
1221             if (flowThread->addForcedRegionBreak(this, offsetFromLogicalTopOfFirstPage() + logicalOffset, child, true, &offsetBreakAdjustment))
1222                 return logicalOffset + offsetBreakAdjustment;
1223         }
1224         return nextPageLogicalTop(logicalOffset, IncludePageBoundary);
1225     }
1226     return logicalOffset;
1227 }
1228
1229 LayoutUnit RenderBlockFlow::applyAfterBreak(RenderBox* child, LayoutUnit logicalOffset, MarginInfo& marginInfo)
1230 {
1231     // FIXME: Add page break checking here when we support printing.
1232     bool checkColumnBreaks = view().layoutState()->isPaginatingColumns();
1233     bool checkPageBreaks = !checkColumnBreaks && view().layoutState()->m_pageLogicalHeight; // FIXME: Once columns can print we have to check this.
1234     RenderFlowThread* flowThread = flowThreadContainingBlock();
1235     bool checkRegionBreaks = flowThread && flowThread->isRenderNamedFlowThread();
1236     bool checkAfterAlways = (checkColumnBreaks && child->style()->columnBreakAfter() == PBALWAYS) || (checkPageBreaks && child->style()->pageBreakAfter() == PBALWAYS)
1237         || (checkRegionBreaks && child->style()->regionBreakAfter() == PBALWAYS);
1238     if (checkAfterAlways && inNormalFlow(child) && hasNextPage(logicalOffset, IncludePageBoundary)) {
1239         LayoutUnit marginOffset = marginInfo.canCollapseWithMarginBefore() ? LayoutUnit() : marginInfo.margin();
1240
1241         // So our margin doesn't participate in the next collapsing steps.
1242         marginInfo.clearMargin();
1243
1244         if (checkColumnBreaks)
1245             view().layoutState()->addForcedColumnBreak(child, logicalOffset);
1246         if (checkRegionBreaks) {
1247             LayoutUnit offsetBreakAdjustment = 0;
1248             if (flowThread->addForcedRegionBreak(this, offsetFromLogicalTopOfFirstPage() + logicalOffset + marginOffset, child, false, &offsetBreakAdjustment))
1249                 return logicalOffset + marginOffset + offsetBreakAdjustment;
1250         }
1251         return nextPageLogicalTop(logicalOffset, IncludePageBoundary);
1252     }
1253     return logicalOffset;
1254 }
1255
1256 LayoutUnit RenderBlockFlow::adjustBlockChildForPagination(LayoutUnit logicalTopAfterClear, LayoutUnit estimateWithoutPagination, RenderBox* child, bool atBeforeSideOfBlock)
1257 {
1258     RenderBlock* childRenderBlock = child->isRenderBlock() ? toRenderBlock(child) : 0;
1259
1260     if (estimateWithoutPagination != logicalTopAfterClear) {
1261         // Our guess prior to pagination movement was wrong. Before we attempt to paginate, let's try again at the new
1262         // position.
1263         setLogicalHeight(logicalTopAfterClear);
1264         setLogicalTopForChild(child, logicalTopAfterClear, ApplyLayoutDelta);
1265
1266         if (child->shrinkToAvoidFloats()) {
1267             // The child's width depends on the line width.
1268             // When the child shifts to clear an item, its width can
1269             // change (because it has more available line width).
1270             // So go ahead and mark the item as dirty.
1271             child->setChildNeedsLayout(MarkOnlyThis);
1272         }
1273         
1274         if (childRenderBlock) {
1275             if (!child->avoidsFloats() && childRenderBlock->containsFloats())
1276                 toRenderBlockFlow(childRenderBlock)->markAllDescendantsWithFloatsForLayout();
1277             if (!child->needsLayout())
1278                 child->markForPaginationRelayoutIfNeeded();
1279         }
1280
1281         // Our guess was wrong. Make the child lay itself out again.
1282         child->layoutIfNeeded();
1283     }
1284
1285     LayoutUnit oldTop = logicalTopAfterClear;
1286
1287     // If the object has a page or column break value of "before", then we should shift to the top of the next page.
1288     LayoutUnit result = applyBeforeBreak(child, logicalTopAfterClear);
1289
1290     if (pageLogicalHeightForOffset(result)) {
1291         LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(result, ExcludePageBoundary);
1292         LayoutUnit spaceShortage = child->logicalHeight() - remainingLogicalHeight;
1293         if (spaceShortage > 0) {
1294             // If the child crosses a column boundary, report a break, in case nothing inside it has already
1295             // done so. The column balancer needs to know how much it has to stretch the columns to make more
1296             // content fit. If no breaks are reported (but do occur), the balancer will have no clue. FIXME:
1297             // This should be improved, though, because here we just pretend that the child is
1298             // unsplittable. A splittable child, on the other hand, has break opportunities at every position
1299             // where there's no child content, border or padding. In other words, we risk stretching more
1300             // than necessary.
1301             setPageBreak(result, spaceShortage);
1302         }
1303     }
1304
1305     // For replaced elements and scrolled elements, we want to shift them to the next page if they don't fit on the current one.
1306     LayoutUnit logicalTopBeforeUnsplittableAdjustment = result;
1307     LayoutUnit logicalTopAfterUnsplittableAdjustment = adjustForUnsplittableChild(child, result);
1308     
1309     LayoutUnit paginationStrut = 0;
1310     LayoutUnit unsplittableAdjustmentDelta = logicalTopAfterUnsplittableAdjustment - logicalTopBeforeUnsplittableAdjustment;
1311     if (unsplittableAdjustmentDelta)
1312         paginationStrut = unsplittableAdjustmentDelta;
1313     else if (childRenderBlock && childRenderBlock->paginationStrut())
1314         paginationStrut = childRenderBlock->paginationStrut();
1315
1316     if (paginationStrut) {
1317         // We are willing to propagate out to our parent block as long as we were at the top of the block prior
1318         // to collapsing our margins, and as long as we didn't clear or move as a result of other pagination.
1319         if (atBeforeSideOfBlock && oldTop == result && !isOutOfFlowPositioned() && !isTableCell()) {
1320             // FIXME: Should really check if we're exceeding the page height before propagating the strut, but we don't
1321             // have all the information to do so (the strut only has the remaining amount to push). Gecko gets this wrong too
1322             // and pushes to the next page anyway, so not too concerned about it.
1323             setPaginationStrut(result + paginationStrut);
1324             if (childRenderBlock)
1325                 childRenderBlock->setPaginationStrut(0);
1326         } else
1327             result += paginationStrut;
1328     }
1329
1330     // Similar to how we apply clearance. Go ahead and boost height() to be the place where we're going to position the child.
1331     setLogicalHeight(logicalHeight() + (result - oldTop));
1332     
1333     // Return the final adjusted logical top.
1334     return result;
1335 }
1336
1337 static inline LayoutUnit calculateMinimumPageHeight(RenderStyle* renderStyle, RootInlineBox* lastLine, LayoutUnit lineTop, LayoutUnit lineBottom)
1338 {
1339     // We may require a certain minimum number of lines per page in order to satisfy
1340     // orphans and widows, and that may affect the minimum page height.
1341     unsigned lineCount = max<unsigned>(renderStyle->hasAutoOrphans() ? 1 : renderStyle->orphans(), renderStyle->hasAutoWidows() ? 1 : renderStyle->widows());
1342     if (lineCount > 1) {
1343         RootInlineBox* line = lastLine;
1344         for (unsigned i = 1; i < lineCount && line->prevRootBox(); i++)
1345             line = line->prevRootBox();
1346
1347         // FIXME: Paginating using line overflow isn't all fine. See FIXME in
1348         // adjustLinePositionForPagination() for more details.
1349         LayoutRect overflow = line->logicalVisualOverflowRect(line->lineTop(), line->lineBottom());
1350         lineTop = min(line->lineTopWithLeading(), overflow.y());
1351     }
1352     return lineBottom - lineTop;
1353 }
1354
1355 void RenderBlockFlow::adjustLinePositionForPagination(RootInlineBox* lineBox, LayoutUnit& delta, RenderFlowThread* flowThread)
1356 {
1357     // FIXME: For now we paginate using line overflow. This ensures that lines don't overlap at all when we
1358     // put a strut between them for pagination purposes. However, this really isn't the desired rendering, since
1359     // the line on the top of the next page will appear too far down relative to the same kind of line at the top
1360     // of the first column.
1361     //
1362     // The rendering we would like to see is one where the lineTopWithLeading is at the top of the column, and any line overflow
1363     // simply spills out above the top of the column. This effect would match what happens at the top of the first column.
1364     // We can't achieve this rendering, however, until we stop columns from clipping to the column bounds (thus allowing
1365     // for overflow to occur), and then cache visible overflow for each column rect.
1366     //
1367     // Furthermore, the paint we have to do when a column has overflow has to be special. We need to exclude
1368     // content that paints in a previous column (and content that paints in the following column).
1369     //
1370     // For now we'll at least honor the lineTopWithLeading when paginating if it is above the logical top overflow. This will
1371     // at least make positive leading work in typical cases.
1372     //
1373     // FIXME: Another problem with simply moving lines is that the available line width may change (because of floats).
1374     // Technically if the location we move the line to has a different line width than our old position, then we need to dirty the
1375     // line and all following lines.
1376     LayoutRect logicalVisualOverflow = lineBox->logicalVisualOverflowRect(lineBox->lineTop(), lineBox->lineBottom());
1377     LayoutUnit logicalOffset = min(lineBox->lineTopWithLeading(), logicalVisualOverflow.y());
1378     LayoutUnit logicalBottom = max(lineBox->lineBottomWithLeading(), logicalVisualOverflow.maxY());
1379     LayoutUnit lineHeight = logicalBottom - logicalOffset;
1380     updateMinimumPageHeight(logicalOffset, calculateMinimumPageHeight(style(), lineBox, logicalOffset, logicalBottom));
1381     logicalOffset += delta;
1382     lineBox->setPaginationStrut(0);
1383     lineBox->setIsFirstAfterPageBreak(false);
1384     LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset);
1385     bool hasUniformPageLogicalHeight = !flowThread || flowThread->regionsHaveUniformLogicalHeight();
1386     // If lineHeight is greater than pageLogicalHeight, but logicalVisualOverflow.height() still fits, we are
1387     // still going to add a strut, so that the visible overflow fits on a single page.
1388     if (!pageLogicalHeight || (hasUniformPageLogicalHeight && logicalVisualOverflow.height() > pageLogicalHeight)
1389         || !hasNextPage(logicalOffset))
1390         // FIXME: In case the line aligns with the top of the page (or it's slightly shifted downwards) it will not be marked as the first line in the page.
1391         // From here, the fix is not straightforward because it's not easy to always determine when the current line is the first in the page.
1392         return;
1393     LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(logicalOffset, ExcludePageBoundary);
1394
1395     int lineIndex = lineCount(lineBox);
1396     if (remainingLogicalHeight < lineHeight || (shouldBreakAtLineToAvoidWidow() && lineBreakToAvoidWidow() == lineIndex)) {
1397         if (shouldBreakAtLineToAvoidWidow() && lineBreakToAvoidWidow() == lineIndex) {
1398             clearShouldBreakAtLineToAvoidWidow();
1399             setDidBreakAtLineToAvoidWidow();
1400         }
1401         // If we have a non-uniform page height, then we have to shift further possibly.
1402         if (!hasUniformPageLogicalHeight && !pushToNextPageWithMinimumLogicalHeight(remainingLogicalHeight, logicalOffset, lineHeight))
1403             return;
1404         if (lineHeight > pageLogicalHeight) {
1405             // Split the top margin in order to avoid splitting the visible part of the line.
1406             remainingLogicalHeight -= min(lineHeight - pageLogicalHeight, max<LayoutUnit>(0, logicalVisualOverflow.y() - lineBox->lineTopWithLeading()));
1407         }
1408         LayoutUnit totalLogicalHeight = lineHeight + max<LayoutUnit>(0, logicalOffset);
1409         LayoutUnit pageLogicalHeightAtNewOffset = hasUniformPageLogicalHeight ? pageLogicalHeight : pageLogicalHeightForOffset(logicalOffset + remainingLogicalHeight);
1410         setPageBreak(logicalOffset, lineHeight - remainingLogicalHeight);
1411         if (((lineBox == firstRootBox() && totalLogicalHeight < pageLogicalHeightAtNewOffset) || (!style()->hasAutoOrphans() && style()->orphans() >= lineIndex))
1412             && !isOutOfFlowPositioned() && !isTableCell())
1413             setPaginationStrut(remainingLogicalHeight + max<LayoutUnit>(0, logicalOffset));
1414         else {
1415             delta += remainingLogicalHeight;
1416             lineBox->setPaginationStrut(remainingLogicalHeight);
1417             lineBox->setIsFirstAfterPageBreak(true);
1418         }
1419     } else if (remainingLogicalHeight == pageLogicalHeight && lineBox != firstRootBox())
1420         lineBox->setIsFirstAfterPageBreak(true);
1421 }
1422
1423 void RenderBlockFlow::setBreakAtLineToAvoidWidow(int lineToBreak)
1424 {
1425     ASSERT(lineToBreak >= 0);
1426     if (!m_rareData)
1427         m_rareData = adoptPtr(new RenderBlockFlowRareData(this));
1428
1429     ASSERT(!m_rareData->m_didBreakAtLineToAvoidWidow);
1430     m_rareData->m_lineBreakToAvoidWidow = lineToBreak;
1431 }
1432
1433 void RenderBlockFlow::setDidBreakAtLineToAvoidWidow()
1434 {
1435     ASSERT(!shouldBreakAtLineToAvoidWidow());
1436     if (!m_rareData)
1437         return;
1438
1439     m_rareData->m_didBreakAtLineToAvoidWidow = true;
1440 }
1441
1442 void RenderBlockFlow::clearDidBreakAtLineToAvoidWidow()
1443 {
1444     if (!m_rareData)
1445         return;
1446
1447     m_rareData->m_didBreakAtLineToAvoidWidow = false;
1448 }
1449
1450 void RenderBlockFlow::clearShouldBreakAtLineToAvoidWidow() const
1451 {
1452     ASSERT(shouldBreakAtLineToAvoidWidow());
1453     if (!m_rareData)
1454         return;
1455
1456     m_rareData->m_lineBreakToAvoidWidow = -1;
1457 }
1458
1459 bool RenderBlockFlow::relayoutToAvoidWidows(LayoutStateMaintainer& statePusher)
1460 {
1461     if (!shouldBreakAtLineToAvoidWidow())
1462         return false;
1463
1464     statePusher.pop();
1465     setEverHadLayout(true);
1466     layoutBlock(false);
1467     return true;
1468 }
1469
1470 void RenderBlockFlow::layoutLineGridBox()
1471 {
1472     if (style()->lineGrid() == RenderStyle::initialLineGrid()) {
1473         setLineGridBox(0);
1474         return;
1475     }
1476     
1477     setLineGridBox(0);
1478
1479     RootInlineBox* lineGridBox = new (renderArena()) RootInlineBox(*this);
1480     lineGridBox->setHasTextChildren(); // Needed to make the line ascent/descent actually be honored in quirks mode.
1481     lineGridBox->setConstructed();
1482     GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1483     VerticalPositionCache verticalPositionCache;
1484     lineGridBox->alignBoxesInBlockDirection(logicalHeight(), textBoxDataMap, verticalPositionCache);
1485     
1486     setLineGridBox(lineGridBox);
1487     
1488     // FIXME: If any of the characteristics of the box change compared to the old one, then we need to do a deep dirtying
1489     // (similar to what happens when the page height changes). Ideally, though, we only do this if someone is actually snapping
1490     // to this grid.
1491 }
1492
1493 bool RenderBlockFlow::containsFloat(RenderBox* renderer) const
1494 {
1495     return m_floatingObjects && m_floatingObjects->set().contains<RenderBox&, FloatingObjectHashTranslator>(*renderer);
1496 }
1497
1498 void RenderBlockFlow::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
1499 {
1500     RenderBlock::styleDidChange(diff, oldStyle);
1501     
1502     // After our style changed, if we lose our ability to propagate floats into next sibling
1503     // blocks, then we need to find the top most parent containing that overhanging float and
1504     // then mark its descendants with floats for layout and clear all floats from its next
1505     // sibling blocks that exist in our floating objects list. See bug 56299 and 62875.
1506     bool canPropagateFloatIntoSibling = !isFloatingOrOutOfFlowPositioned() && !avoidsFloats();
1507     if (diff == StyleDifferenceLayout && s_canPropagateFloatIntoSibling && !canPropagateFloatIntoSibling && hasOverhangingFloats()) {
1508         RenderBlockFlow* parentBlock = this;
1509         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1510         auto end = floatingObjectSet.end();
1511
1512         for (RenderObject* curr = parent(); curr && !curr->isRenderView(); curr = curr->parent()) {
1513             if (curr->isRenderBlockFlow()) {
1514                 RenderBlockFlow* currBlock = toRenderBlockFlow(curr);
1515
1516                 if (currBlock->hasOverhangingFloats()) {
1517                     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1518                         RenderBox& renderer = (*it)->renderer();
1519                         if (currBlock->hasOverhangingFloat(&renderer)) {
1520                             parentBlock = currBlock;
1521                             break;
1522                         }
1523                     }
1524                 }
1525             }
1526         }
1527
1528         parentBlock->markAllDescendantsWithFloatsForLayout();
1529         parentBlock->markSiblingsWithFloatsForLayout();
1530     }
1531 }
1532
1533 void RenderBlockFlow::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)
1534 {
1535     RenderStyle* oldStyle = style();
1536     s_canPropagateFloatIntoSibling = oldStyle ? !isFloatingOrOutOfFlowPositioned() && !avoidsFloats() : false;
1537
1538     if (oldStyle && parent() && diff == StyleDifferenceLayout && oldStyle->position() != newStyle->position()) {
1539         if (containsFloats() && !isFloating() && !isOutOfFlowPositioned() && newStyle->hasOutOfFlowPosition())
1540             markAllDescendantsWithFloatsForLayout();
1541     }
1542
1543     RenderBlock::styleWillChange(diff, newStyle);
1544 }
1545
1546 void RenderBlockFlow::deleteLineBoxTree()
1547 {
1548     if (containsFloats())
1549         m_floatingObjects->clearLineBoxTreePointers();
1550     RenderBlock::deleteLineBoxTree();
1551 }
1552
1553 void RenderBlockFlow::moveAllChildrenIncludingFloatsTo(RenderBlock* toBlock, bool fullRemoveInsert)
1554 {
1555     RenderBlockFlow* toBlockFlow = toRenderBlockFlow(toBlock);
1556     moveAllChildrenTo(toBlockFlow, fullRemoveInsert);
1557
1558     // When a portion of the render tree is being detached, anonymous blocks
1559     // will be combined as their children are deleted. In this process, the
1560     // anonymous block later in the tree is merged into the one preceeding it.
1561     // It can happen that the later block (this) contains floats that the
1562     // previous block (toBlockFlow) did not contain, and thus are not in the
1563     // floating objects list for toBlockFlow. This can result in toBlockFlow
1564     // containing floats that are not in it's floating objects list, but are in
1565     // the floating objects lists of siblings and parents. This can cause
1566     // problems when the float itself is deleted, since the deletion code
1567     // assumes that if a float is not in it's containing block's floating
1568     // objects list, it isn't in any floating objects list. In order to
1569     // preserve this condition (removing it has serious performance
1570     // implications), we need to copy the floating objects from the old block
1571     // (this) to the new block (toBlockFlow). The float's metrics will likely
1572     // all be wrong, but since toBlockFlow is already marked for layout, this
1573     // will get fixed before anything gets displayed.
1574     // See bug https://bugs.webkit.org/show_bug.cgi?id=115566
1575     if (m_floatingObjects) {
1576         if (!toBlockFlow->m_floatingObjects)
1577             toBlockFlow->createFloatingObjects();
1578
1579         const FloatingObjectSet& fromFloatingObjectSet = m_floatingObjects->set();
1580         auto end = fromFloatingObjectSet.end();
1581
1582         for (auto it = fromFloatingObjectSet.begin(); it != end; ++it) {
1583             FloatingObject* floatingObject = it->get();
1584
1585             // Don't insert the object again if it's already in the list
1586             if (toBlockFlow->containsFloat(&floatingObject->renderer()))
1587                 continue;
1588
1589             toBlockFlow->m_floatingObjects->add(floatingObject->unsafeClone());
1590         }
1591     }
1592 }
1593
1594 void RenderBlockFlow::addOverflowFromFloats()
1595 {
1596     if (!m_floatingObjects)
1597         return;
1598
1599     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1600     auto end = floatingObjectSet.end();
1601     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1602         FloatingObject* r = it->get();
1603         if (r->isDescendant())
1604             addOverflowFromChild(&r->renderer(), IntSize(xPositionForFloatIncludingMargin(r), yPositionForFloatIncludingMargin(r)));
1605     }
1606 }
1607
1608 void RenderBlockFlow::computeOverflow(LayoutUnit oldClientAfterEdge, bool recomputeFloats)
1609 {
1610     RenderBlock::computeOverflow(oldClientAfterEdge, recomputeFloats);
1611
1612     if (!hasColumns() && (recomputeFloats || isRoot() || expandsToEncloseOverhangingFloats() || hasSelfPaintingLayer()))
1613         addOverflowFromFloats();
1614 }
1615
1616 void RenderBlockFlow::repaintOverhangingFloats(bool paintAllDescendants)
1617 {
1618     // Repaint any overhanging floats (if we know we're the one to paint them).
1619     // Otherwise, bail out.
1620     if (!hasOverhangingFloats())
1621         return;
1622
1623     // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
1624     // in this block. Better yet would be to push extra state for the containers of other floats.
1625     LayoutStateDisabler layoutStateDisabler(&view());
1626     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1627     auto end = floatingObjectSet.end();
1628     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1629         FloatingObject* floatingObject = it->get();
1630         // Only repaint the object if it is overhanging, is not in its own layer, and
1631         // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
1632         // condition is replaced with being a descendant of us.
1633         if (logicalBottomForFloat(floatingObject) > logicalHeight()
1634             && !floatingObject->renderer().hasSelfPaintingLayer()
1635             && (floatingObject->shouldPaint() || (paintAllDescendants && floatingObject->renderer().isDescendantOf(this)))) {
1636             floatingObject->renderer().repaint();
1637             floatingObject->renderer().repaintOverhangingFloats(false);
1638         }
1639     }
1640 }
1641
1642 void RenderBlockFlow::paintFloats(PaintInfo& paintInfo, const LayoutPoint& paintOffset, bool preservePhase)
1643 {
1644     if (!m_floatingObjects)
1645         return;
1646
1647     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1648     auto end = floatingObjectSet.end();
1649     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1650         FloatingObject* r = it->get();
1651         // Only paint the object if our m_shouldPaint flag is set.
1652         if (r->shouldPaint() && !r->renderer().hasSelfPaintingLayer()) {
1653             PaintInfo currentPaintInfo(paintInfo);
1654             currentPaintInfo.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
1655             // FIXME: LayoutPoint version of xPositionForFloatIncludingMargin would make this much cleaner.
1656             LayoutPoint childPoint = flipFloatForWritingModeForChild(r, LayoutPoint(paintOffset.x() + xPositionForFloatIncludingMargin(r) - r->renderer().x(), paintOffset.y() + yPositionForFloatIncludingMargin(r) - r->renderer().y()));
1657             r->renderer().paint(currentPaintInfo, childPoint);
1658             if (!preservePhase) {
1659                 currentPaintInfo.phase = PaintPhaseChildBlockBackgrounds;
1660                 r->renderer().paint(currentPaintInfo, childPoint);
1661                 currentPaintInfo.phase = PaintPhaseFloat;
1662                 r->renderer().paint(currentPaintInfo, childPoint);
1663                 currentPaintInfo.phase = PaintPhaseForeground;
1664                 r->renderer().paint(currentPaintInfo, childPoint);
1665                 currentPaintInfo.phase = PaintPhaseOutline;
1666                 r->renderer().paint(currentPaintInfo, childPoint);
1667             }
1668         }
1669     }
1670 }
1671
1672
1673 void RenderBlockFlow::clipOutFloatingObjects(RenderBlock* rootBlock, const PaintInfo* paintInfo, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock)
1674 {
1675     if (m_floatingObjects) {
1676         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1677         auto end = floatingObjectSet.end();
1678         for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1679             FloatingObject* floatingObject = it->get();
1680             LayoutRect floatBox(offsetFromRootBlock.width() + xPositionForFloatIncludingMargin(floatingObject),
1681                 offsetFromRootBlock.height() + yPositionForFloatIncludingMargin(floatingObject),
1682                 floatingObject->renderer().width(), floatingObject->renderer().height());
1683             rootBlock->flipForWritingMode(floatBox);
1684             floatBox.move(rootBlockPhysicalPosition.x(), rootBlockPhysicalPosition.y());
1685             paintInfo->context->clipOut(pixelSnappedIntRect(floatBox));
1686         }
1687     }
1688 }
1689
1690 void RenderBlockFlow::createFloatingObjects()
1691 {
1692     m_floatingObjects = adoptPtr(new FloatingObjects(this, isHorizontalWritingMode()));
1693 }
1694
1695 void RenderBlockFlow::removeFloatingObjects()
1696 {
1697     if (!m_floatingObjects)
1698         return;
1699
1700     m_floatingObjects->clear();
1701 }
1702
1703 FloatingObject* RenderBlockFlow::insertFloatingObject(RenderBox* floatBox)
1704 {
1705     ASSERT(floatBox->isFloating());
1706
1707     // Create the list of special objects if we don't aleady have one
1708     if (!m_floatingObjects)
1709         createFloatingObjects();
1710     else {
1711         // Don't insert the floatingObject again if it's already in the list
1712         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1713         auto it = floatingObjectSet.find<RenderBox&, FloatingObjectHashTranslator>(*floatBox);
1714         if (it != floatingObjectSet.end())
1715             return it->get();
1716     }
1717
1718     // Create the special floatingObject entry & append it to the list
1719
1720     std::unique_ptr<FloatingObject> floatingObject = FloatingObject::create(*floatBox);
1721     
1722     // Our location is irrelevant if we're unsplittable or no pagination is in effect.
1723     // Just go ahead and lay out the float.
1724     bool isChildRenderBlock = floatBox->isRenderBlock();
1725     if (isChildRenderBlock && !floatBox->needsLayout() && view().layoutState()->pageLogicalHeightChanged())
1726         floatBox->setChildNeedsLayout(MarkOnlyThis);
1727             
1728     bool needsBlockDirectionLocationSetBeforeLayout = isChildRenderBlock && view().layoutState()->needsBlockDirectionLocationSetBeforeLayout();
1729     if (!needsBlockDirectionLocationSetBeforeLayout || isWritingModeRoot()) // We are unsplittable if we're a block flow root.
1730         floatBox->layoutIfNeeded();
1731     else {
1732         floatBox->updateLogicalWidth();
1733         floatBox->computeAndSetBlockDirectionMargins(this);
1734     }
1735
1736     setLogicalWidthForFloat(floatingObject.get(), logicalWidthForChild(floatBox) + marginStartForChild(floatBox) + marginEndForChild(floatBox));
1737
1738 #if ENABLE(CSS_SHAPES)
1739     if (ShapeOutsideInfo* shapeOutside = floatBox->shapeOutsideInfo())
1740         shapeOutside->setShapeSize(logicalWidthForChild(floatBox), logicalHeightForChild(floatBox));
1741 #endif
1742
1743     return m_floatingObjects->add(std::move(floatingObject));
1744 }
1745
1746 void RenderBlockFlow::removeFloatingObject(RenderBox* floatBox)
1747 {
1748     if (m_floatingObjects) {
1749         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1750         auto it = floatingObjectSet.find<RenderBox&, FloatingObjectHashTranslator>(*floatBox);
1751         if (it != floatingObjectSet.end()) {
1752             FloatingObject* floatingObject = it->get();
1753             if (childrenInline()) {
1754                 LayoutUnit logicalTop = logicalTopForFloat(floatingObject);
1755                 LayoutUnit logicalBottom = logicalBottomForFloat(floatingObject);
1756
1757                 // Fix for https://bugs.webkit.org/show_bug.cgi?id=54995.
1758                 if (logicalBottom < 0 || logicalBottom < logicalTop || logicalTop == LayoutUnit::max())
1759                     logicalBottom = LayoutUnit::max();
1760                 else {
1761                     // Special-case zero- and less-than-zero-height floats: those don't touch
1762                     // the line that they're on, but it still needs to be dirtied. This is
1763                     // accomplished by pretending they have a height of 1.
1764                     logicalBottom = max(logicalBottom, logicalTop + 1);
1765                 }
1766                 if (floatingObject->originatingLine()) {
1767                     if (!selfNeedsLayout()) {
1768                         ASSERT(&floatingObject->originatingLine()->renderer() == this);
1769                         floatingObject->originatingLine()->markDirty();
1770                     }
1771 #if !ASSERT_DISABLED
1772                     floatingObject->setOriginatingLine(0);
1773 #endif
1774                 }
1775                 markLinesDirtyInBlockRange(0, logicalBottom);
1776             }
1777             m_floatingObjects->remove(floatingObject);
1778         }
1779     }
1780 }
1781
1782 void RenderBlockFlow::removeFloatingObjectsBelow(FloatingObject* lastFloat, int logicalOffset)
1783 {
1784     if (!containsFloats())
1785         return;
1786     
1787     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1788     FloatingObject* curr = floatingObjectSet.last().get();
1789     while (curr != lastFloat && (!curr->isPlaced() || logicalTopForFloat(curr) >= logicalOffset)) {
1790         m_floatingObjects->remove(curr);
1791         if (floatingObjectSet.isEmpty())
1792             break;
1793         curr = floatingObjectSet.last().get();
1794     }
1795 }
1796
1797 LayoutPoint RenderBlockFlow::computeLogicalLocationForFloat(const FloatingObject* floatingObject, LayoutUnit logicalTopOffset) const
1798 {
1799     RenderBox* childBox = &floatingObject->renderer();
1800     LayoutUnit logicalLeftOffset = logicalLeftOffsetForContent(logicalTopOffset); // Constant part of left offset.
1801     LayoutUnit logicalRightOffset; // Constant part of right offset.
1802 #if ENABLE(CSS_SHAPES)
1803     // FIXME Bug 102948: This only works for shape outside directly set on this block.
1804     ShapeInsideInfo* shapeInsideInfo = this->layoutShapeInsideInfo();
1805     // FIXME: Implement behavior for right floats.
1806     if (shapeInsideInfo) {
1807         LayoutSize floatLogicalSize = logicalSizeForFloat(floatingObject);
1808         // floatingObject's logicalSize doesn't contain the actual height at this point, so we need to calculate it
1809         floatLogicalSize.setHeight(logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
1810
1811         // FIXME: If the float doesn't fit in the shape we should push it under the content box
1812         logicalTopOffset = shapeInsideInfo->computeFirstFitPositionForFloat(floatLogicalSize);
1813         if (logicalHeight() > logicalTopOffset)
1814             logicalTopOffset = logicalHeight();
1815
1816         SegmentList segments = shapeInsideInfo->computeSegmentsForLine(logicalTopOffset, floatLogicalSize.height());
1817         // FIXME Bug 102949: Add support for shapes with multiple segments.
1818         if (segments.size() == 1) {
1819             // The segment offsets are relative to the content box.
1820             logicalRightOffset = logicalLeftOffset + segments[0].logicalRight;
1821             logicalLeftOffset += segments[0].logicalLeft;
1822         }
1823     } else
1824 #endif
1825         logicalRightOffset = logicalRightOffsetForContent(logicalTopOffset);
1826
1827     LayoutUnit floatLogicalWidth = min(logicalWidthForFloat(floatingObject), logicalRightOffset - logicalLeftOffset); // The width we look for.
1828
1829     LayoutUnit floatLogicalLeft;
1830
1831     bool insideFlowThread = flowThreadContainingBlock();
1832
1833     if (childBox->style()->floating() == LeftFloat) {
1834         LayoutUnit heightRemainingLeft = 1;
1835         LayoutUnit heightRemainingRight = 1;
1836         floatLogicalLeft = logicalLeftOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalLeftOffset, false, &heightRemainingLeft);
1837         while (logicalRightOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalRightOffset, false, &heightRemainingRight) - floatLogicalLeft < floatLogicalWidth) {
1838             logicalTopOffset += min(heightRemainingLeft, heightRemainingRight);
1839             floatLogicalLeft = logicalLeftOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalLeftOffset, false, &heightRemainingLeft);
1840             if (insideFlowThread) {
1841                 // Have to re-evaluate all of our offsets, since they may have changed.
1842                 logicalRightOffset = logicalRightOffsetForContent(logicalTopOffset); // Constant part of right offset.
1843                 logicalLeftOffset = logicalLeftOffsetForContent(logicalTopOffset); // Constant part of left offset.
1844                 floatLogicalWidth = min(logicalWidthForFloat(floatingObject), logicalRightOffset - logicalLeftOffset);
1845             }
1846         }
1847         floatLogicalLeft = max(logicalLeftOffset - borderAndPaddingLogicalLeft(), floatLogicalLeft);
1848     } else {
1849         LayoutUnit heightRemainingLeft = 1;
1850         LayoutUnit heightRemainingRight = 1;
1851         floatLogicalLeft = logicalRightOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalRightOffset, false, &heightRemainingRight);
1852         while (floatLogicalLeft - logicalLeftOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalLeftOffset, false, &heightRemainingLeft) < floatLogicalWidth) {
1853             logicalTopOffset += min(heightRemainingLeft, heightRemainingRight);
1854             floatLogicalLeft = logicalRightOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalRightOffset, false, &heightRemainingRight);
1855             if (insideFlowThread) {
1856                 // Have to re-evaluate all of our offsets, since they may have changed.
1857                 logicalRightOffset = logicalRightOffsetForContent(logicalTopOffset); // Constant part of right offset.
1858                 logicalLeftOffset = logicalLeftOffsetForContent(logicalTopOffset); // Constant part of left offset.
1859                 floatLogicalWidth = min(logicalWidthForFloat(floatingObject), logicalRightOffset - logicalLeftOffset);
1860             }
1861         }
1862         // Use the original width of the float here, since the local variable
1863         // |floatLogicalWidth| was capped to the available line width. See
1864         // fast/block/float/clamped-right-float.html.
1865         floatLogicalLeft -= logicalWidthForFloat(floatingObject);
1866     }
1867     
1868     return LayoutPoint(floatLogicalLeft, logicalTopOffset);
1869 }
1870
1871 bool RenderBlockFlow::positionNewFloats()
1872 {
1873     if (!m_floatingObjects)
1874         return false;
1875
1876     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1877     if (floatingObjectSet.isEmpty())
1878         return false;
1879
1880     // If all floats have already been positioned, then we have no work to do.
1881     if (floatingObjectSet.last()->isPlaced())
1882         return false;
1883
1884     // Move backwards through our floating object list until we find a float that has
1885     // already been positioned. Then we'll be able to move forward, positioning all of
1886     // the new floats that need it.
1887     auto it = floatingObjectSet.end();
1888     --it; // Go to last item.
1889     auto begin = floatingObjectSet.begin();
1890     FloatingObject* lastPlacedFloatingObject = 0;
1891     while (it != begin) {
1892         --it;
1893         if ((*it)->isPlaced()) {
1894             lastPlacedFloatingObject = it->get();
1895             ++it;
1896             break;
1897         }
1898     }
1899
1900     LayoutUnit logicalTop = logicalHeight();
1901     
1902     // The float cannot start above the top position of the last positioned float.
1903     if (lastPlacedFloatingObject)
1904         logicalTop = max(logicalTopForFloat(lastPlacedFloatingObject), logicalTop);
1905
1906     auto end = floatingObjectSet.end();
1907     // Now walk through the set of unpositioned floats and place them.
1908     for (; it != end; ++it) {
1909         FloatingObject* floatingObject = it->get();
1910         // The containing block is responsible for positioning floats, so if we have floats in our
1911         // list that come from somewhere else, do not attempt to position them.
1912         if (floatingObject->renderer().containingBlock() != this)
1913             continue;
1914
1915         RenderBox* childBox = &floatingObject->renderer();
1916
1917         LayoutUnit childLogicalLeftMargin = style()->isLeftToRightDirection() ? marginStartForChild(childBox) : marginEndForChild(childBox);
1918
1919         LayoutRect oldRect = childBox->frameRect();
1920
1921         if (childBox->style()->clear() & CLEFT)
1922             logicalTop = max(lowestFloatLogicalBottom(FloatingObject::FloatLeft), logicalTop);
1923         if (childBox->style()->clear() & CRIGHT)
1924             logicalTop = max(lowestFloatLogicalBottom(FloatingObject::FloatRight), logicalTop);
1925
1926         LayoutPoint floatLogicalLocation = computeLogicalLocationForFloat(floatingObject, logicalTop);
1927
1928         setLogicalLeftForFloat(floatingObject, floatLogicalLocation.x());
1929
1930         setLogicalLeftForChild(childBox, floatLogicalLocation.x() + childLogicalLeftMargin);
1931         setLogicalTopForChild(childBox, floatLogicalLocation.y() + marginBeforeForChild(childBox));
1932
1933         estimateRegionRangeForBoxChild(childBox);
1934
1935         LayoutState* layoutState = view().layoutState();
1936         bool isPaginated = layoutState->isPaginated();
1937         if (isPaginated && !childBox->needsLayout())
1938             childBox->markForPaginationRelayoutIfNeeded();
1939         
1940         childBox->layoutIfNeeded();
1941
1942         if (isPaginated) {
1943             // If we are unsplittable and don't fit, then we need to move down.
1944             // We include our margins as part of the unsplittable area.
1945             LayoutUnit newLogicalTop = adjustForUnsplittableChild(childBox, floatLogicalLocation.y(), true);
1946             
1947             // See if we have a pagination strut that is making us move down further.
1948             // Note that an unsplittable child can't also have a pagination strut, so this is
1949             // exclusive with the case above.
1950             RenderBlock* childBlock = childBox->isRenderBlock() ? toRenderBlock(childBox) : 0;
1951             if (childBlock && childBlock->paginationStrut()) {
1952                 newLogicalTop += childBlock->paginationStrut();
1953                 childBlock->setPaginationStrut(0);
1954             }
1955             
1956             if (newLogicalTop != floatLogicalLocation.y()) {
1957                 floatingObject->setPaginationStrut(newLogicalTop - floatLogicalLocation.y());
1958
1959                 floatLogicalLocation = computeLogicalLocationForFloat(floatingObject, newLogicalTop);
1960                 setLogicalLeftForFloat(floatingObject, floatLogicalLocation.x());
1961
1962                 setLogicalLeftForChild(childBox, floatLogicalLocation.x() + childLogicalLeftMargin);
1963                 setLogicalTopForChild(childBox, floatLogicalLocation.y() + marginBeforeForChild(childBox));
1964         
1965                 if (childBlock)
1966                     childBlock->setChildNeedsLayout(MarkOnlyThis);
1967                 childBox->layoutIfNeeded();
1968             }
1969
1970             if (updateRegionRangeForBoxChild(childBox)) {
1971                 childBox->setNeedsLayout(MarkOnlyThis);
1972                 childBox->layoutIfNeeded();
1973             }
1974         }
1975
1976         setLogicalTopForFloat(floatingObject, floatLogicalLocation.y());
1977
1978         setLogicalHeightForFloat(floatingObject, logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
1979
1980         m_floatingObjects->addPlacedObject(floatingObject);
1981
1982         // If the child moved, we have to repaint it.
1983         if (childBox->checkForRepaintDuringLayout())
1984             childBox->repaintDuringLayoutIfMoved(oldRect);
1985     }
1986     return true;
1987 }
1988
1989 void RenderBlockFlow::newLine(EClear clear)
1990 {
1991     positionNewFloats();
1992     // set y position
1993     LayoutUnit newY = 0;
1994     switch (clear) {
1995     case CLEFT:
1996         newY = lowestFloatLogicalBottom(FloatingObject::FloatLeft);
1997         break;
1998     case CRIGHT:
1999         newY = lowestFloatLogicalBottom(FloatingObject::FloatRight);
2000         break;
2001     case CBOTH:
2002         newY = lowestFloatLogicalBottom();
2003     default:
2004         break;
2005     }
2006     if (height() < newY)
2007         setLogicalHeight(newY);
2008 }
2009
2010 LayoutUnit RenderBlockFlow::logicalLeftFloatOffsetForLine(LayoutUnit logicalTop, LayoutUnit fixedOffset, LayoutUnit* heightRemaining, LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode) const
2011 {
2012     if (m_floatingObjects && m_floatingObjects->hasLeftObjects())
2013         return m_floatingObjects->logicalLeftOffset(fixedOffset, logicalTop, logicalHeight, offsetMode, heightRemaining);
2014
2015     return fixedOffset;
2016 }
2017
2018 LayoutUnit RenderBlockFlow::logicalRightFloatOffsetForLine(LayoutUnit logicalTop, LayoutUnit fixedOffset, LayoutUnit* heightRemaining, LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode) const
2019 {
2020     if (m_floatingObjects && m_floatingObjects->hasRightObjects())
2021         return m_floatingObjects->logicalRightOffset(fixedOffset, logicalTop, logicalHeight, offsetMode, heightRemaining);
2022
2023     return fixedOffset;
2024 }
2025
2026 LayoutUnit RenderBlockFlow::nextFloatLogicalBottomBelow(LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode) const
2027 {
2028     if (!m_floatingObjects)
2029         return logicalHeight;
2030
2031     LayoutUnit bottom = LayoutUnit::max();
2032     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2033     auto end = floatingObjectSet.end();
2034     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2035         FloatingObject* floatingObject = it->get();
2036         LayoutUnit floatBottom = logicalBottomForFloat(floatingObject);
2037 #if ENABLE(CSS_SHAPES)
2038         ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo();
2039         if (offsetMode == ShapeOutsideFloatShapeOffset && shapeOutside) {
2040             LayoutUnit shapeBottom = logicalTopForFloat(floatingObject) + marginBeforeForChild(&(floatingObject->renderer())) + shapeOutside->shapeLogicalBottom();
2041             // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
2042             if (shapeBottom < floatBottom)
2043                 floatBottom = shapeBottom;
2044         }
2045 #endif
2046         if (floatBottom > logicalHeight)
2047             bottom = min(floatBottom, bottom);
2048     }
2049
2050     return bottom == LayoutUnit::max() ? LayoutUnit() : bottom;
2051 }
2052
2053 LayoutUnit RenderBlockFlow::lowestFloatLogicalBottom(FloatingObject::Type floatType) const
2054 {
2055     if (!m_floatingObjects)
2056         return 0;
2057     LayoutUnit lowestFloatBottom = 0;
2058     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2059     auto end = floatingObjectSet.end();
2060     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2061         FloatingObject* floatingObject = it->get();
2062         if (floatingObject->isPlaced() && floatingObject->type() & floatType)
2063             lowestFloatBottom = max(lowestFloatBottom, logicalBottomForFloat(floatingObject));
2064     }
2065     return lowestFloatBottom;
2066 }
2067
2068 LayoutUnit RenderBlockFlow::addOverhangingFloats(RenderBlockFlow* child, bool makeChildPaintOtherFloats)
2069 {
2070     // Prevent floats from being added to the canvas by the root element, e.g., <html>.
2071     if (child->hasOverflowClip() || !child->containsFloats() || child->isRoot() || child->hasColumns() || child->isWritingModeRoot())
2072         return 0;
2073
2074     LayoutUnit childLogicalTop = child->logicalTop();
2075     LayoutUnit childLogicalLeft = child->logicalLeft();
2076     LayoutUnit lowestFloatLogicalBottom = 0;
2077
2078     // Floats that will remain the child's responsibility to paint should factor into its
2079     // overflow.
2080     auto childEnd = child->m_floatingObjects->set().end();
2081     for (auto childIt = child->m_floatingObjects->set().begin(); childIt != childEnd; ++childIt) {
2082         FloatingObject* floatingObject = childIt->get();
2083         LayoutUnit floatLogicalBottom = min(logicalBottomForFloat(floatingObject), LayoutUnit::max() - childLogicalTop);
2084         LayoutUnit logicalBottom = childLogicalTop + floatLogicalBottom;
2085         lowestFloatLogicalBottom = max(lowestFloatLogicalBottom, logicalBottom);
2086
2087         if (logicalBottom > logicalHeight()) {
2088             // If the object is not in the list, we add it now.
2089             if (!containsFloat(&floatingObject->renderer())) {
2090                 LayoutSize offset = isHorizontalWritingMode() ? LayoutSize(-childLogicalLeft, -childLogicalTop) : LayoutSize(-childLogicalTop, -childLogicalLeft);
2091                 bool shouldPaint = false;
2092
2093                 // The nearest enclosing layer always paints the float (so that zindex and stacking
2094                 // behaves properly). We always want to propagate the desire to paint the float as
2095                 // far out as we can, to the outermost block that overlaps the float, stopping only
2096                 // if we hit a self-painting layer boundary.
2097                 if (floatingObject->renderer().enclosingFloatPaintingLayer() == enclosingFloatPaintingLayer()) {
2098                     floatingObject->setShouldPaint(false);
2099                     shouldPaint = true;
2100                 }
2101                 // We create the floating object list lazily.
2102                 if (!m_floatingObjects)
2103                     createFloatingObjects();
2104
2105                 m_floatingObjects->add(floatingObject->copyToNewContainer(offset, shouldPaint, true));
2106             }
2107         } else {
2108             if (makeChildPaintOtherFloats && !floatingObject->shouldPaint() && !floatingObject->renderer().hasSelfPaintingLayer()
2109                 && floatingObject->renderer().isDescendantOf(child) && floatingObject->renderer().enclosingFloatPaintingLayer() == child->enclosingFloatPaintingLayer()) {
2110                 // The float is not overhanging from this block, so if it is a descendant of the child, the child should
2111                 // paint it (the other case is that it is intruding into the child), unless it has its own layer or enclosing
2112                 // layer.
2113                 // If makeChildPaintOtherFloats is false, it means that the child must already know about all the floats
2114                 // it should paint.
2115                 floatingObject->setShouldPaint(true);
2116             }
2117             
2118             // Since the float doesn't overhang, it didn't get put into our list. We need to go ahead and add its overflow in to the
2119             // child now.
2120             if (floatingObject->isDescendant())
2121                 child->addOverflowFromChild(&floatingObject->renderer(), LayoutSize(xPositionForFloatIncludingMargin(floatingObject), yPositionForFloatIncludingMargin(floatingObject)));
2122         }
2123     }
2124     return lowestFloatLogicalBottom;
2125 }
2126
2127 bool RenderBlockFlow::hasOverhangingFloat(RenderBox* renderer)
2128 {
2129     if (!m_floatingObjects || hasColumns() || !parent())
2130         return false;
2131
2132     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2133     auto it = floatingObjectSet.find<RenderBox&, FloatingObjectHashTranslator>(*renderer);
2134     if (it == floatingObjectSet.end())
2135         return false;
2136
2137     return logicalBottomForFloat(it->get()) > logicalHeight();
2138 }
2139
2140 void RenderBlockFlow::addIntrudingFloats(RenderBlockFlow* prev, LayoutUnit logicalLeftOffset, LayoutUnit logicalTopOffset)
2141 {
2142     ASSERT(!avoidsFloats());
2143
2144     // If the parent or previous sibling doesn't have any floats to add, don't bother.
2145     if (!prev->m_floatingObjects)
2146         return;
2147
2148     logicalLeftOffset += marginLogicalLeft();
2149
2150     const FloatingObjectSet& prevSet = prev->m_floatingObjects->set();
2151     auto prevEnd = prevSet.end();
2152     for (auto prevIt = prevSet.begin(); prevIt != prevEnd; ++prevIt) {
2153         FloatingObject* floatingObject = prevIt->get();
2154         if (logicalBottomForFloat(floatingObject) > logicalTopOffset) {
2155             if (!m_floatingObjects || !m_floatingObjects->set().contains<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject)) {
2156                 // We create the floating object list lazily.
2157                 if (!m_floatingObjects)
2158                     createFloatingObjects();
2159
2160                 // Applying the child's margin makes no sense in the case where the child was passed in.
2161                 // since this margin was added already through the modification of the |logicalLeftOffset| variable
2162                 // above. |logicalLeftOffset| will equal the margin in this case, so it's already been taken
2163                 // into account. Only apply this code if prev is the parent, since otherwise the left margin
2164                 // will get applied twice.
2165                 LayoutSize offset = isHorizontalWritingMode()
2166                     ? LayoutSize(logicalLeftOffset - (prev != parent() ? prev->marginLeft() : LayoutUnit()), logicalTopOffset)
2167                     : LayoutSize(logicalTopOffset, logicalLeftOffset - (prev != parent() ? prev->marginTop() : LayoutUnit()));
2168
2169                 m_floatingObjects->add(floatingObject->copyToNewContainer(offset));
2170             }
2171         }
2172     }
2173 }
2174
2175 void RenderBlockFlow::markAllDescendantsWithFloatsForLayout(RenderBox* floatToRemove, bool inLayout)
2176 {
2177     if (!everHadLayout() && !containsFloats())
2178         return;
2179
2180     MarkingBehavior markParents = inLayout ? MarkOnlyThis : MarkContainingBlockChain;
2181     setChildNeedsLayout(markParents);
2182
2183     if (floatToRemove)
2184         removeFloatingObject(floatToRemove);
2185
2186     // Iterate over our children and mark them as needed.
2187     if (!childrenInline()) {
2188         for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
2189             if ((!floatToRemove && child->isFloatingOrOutOfFlowPositioned()) || !child->isRenderBlock())
2190                 continue;
2191             if (!child->isRenderBlockFlow()) {
2192                 RenderBlock* childBlock = toRenderBlock(child);
2193                 if (childBlock->shrinkToAvoidFloats() && childBlock->everHadLayout())
2194                     childBlock->setChildNeedsLayout(markParents);
2195                 continue;
2196             }
2197             RenderBlockFlow* childBlock = toRenderBlockFlow(child);
2198             if ((floatToRemove ? childBlock->containsFloat(floatToRemove) : childBlock->containsFloats()) || childBlock->shrinkToAvoidFloats())
2199                 childBlock->markAllDescendantsWithFloatsForLayout(floatToRemove, inLayout);
2200         }
2201     }
2202 }
2203
2204 void RenderBlockFlow::markSiblingsWithFloatsForLayout(RenderBox* floatToRemove)
2205 {
2206     if (!m_floatingObjects)
2207         return;
2208
2209     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2210     auto end = floatingObjectSet.end();
2211
2212     for (RenderObject* next = nextSibling(); next; next = next->nextSibling()) {
2213         if (!next->isRenderBlockFlow() || next->isFloatingOrOutOfFlowPositioned() || toRenderBlock(next)->avoidsFloats())
2214             continue;
2215
2216         RenderBlockFlow* nextBlock = toRenderBlockFlow(next);
2217         for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2218             RenderBox* floatingBox = &(*it)->renderer();
2219             if (floatToRemove && floatingBox != floatToRemove)
2220                 continue;
2221             if (nextBlock->containsFloat(floatingBox))
2222                 nextBlock->markAllDescendantsWithFloatsForLayout(floatingBox);
2223         }
2224     }
2225 }
2226
2227 LayoutUnit RenderBlockFlow::getClearDelta(RenderBox* child, LayoutUnit logicalTop)
2228 {
2229     // There is no need to compute clearance if we have no floats.
2230     if (!containsFloats())
2231         return 0;
2232     
2233     // At least one float is present. We need to perform the clearance computation.
2234     bool clearSet = child->style()->clear() != CNONE;
2235     LayoutUnit logicalBottom = 0;
2236     switch (child->style()->clear()) {
2237     case CNONE:
2238         break;
2239     case CLEFT:
2240         logicalBottom = lowestFloatLogicalBottom(FloatingObject::FloatLeft);
2241         break;
2242     case CRIGHT:
2243         logicalBottom = lowestFloatLogicalBottom(FloatingObject::FloatRight);
2244         break;
2245     case CBOTH:
2246         logicalBottom = lowestFloatLogicalBottom();
2247         break;
2248     }
2249
2250     // We also clear floats if we are too big to sit on the same line as a float (and wish to avoid floats by default).
2251     LayoutUnit result = clearSet ? max<LayoutUnit>(0, logicalBottom - logicalTop) : LayoutUnit();
2252     if (!result && child->avoidsFloats()) {
2253         LayoutUnit newLogicalTop = logicalTop;
2254         while (true) {
2255             LayoutUnit availableLogicalWidthAtNewLogicalTopOffset = availableLogicalWidthForLine(newLogicalTop, false, logicalHeightForChild(child));
2256             if (availableLogicalWidthAtNewLogicalTopOffset == availableLogicalWidthForContent(newLogicalTop))
2257                 return newLogicalTop - logicalTop;
2258
2259             RenderRegion* region = regionAtBlockOffset(logicalTopForChild(child));
2260             LayoutRect borderBox = child->borderBoxRectInRegion(region, DoNotCacheRenderBoxRegionInfo);
2261             LayoutUnit childLogicalWidthAtOldLogicalTopOffset = isHorizontalWritingMode() ? borderBox.width() : borderBox.height();
2262
2263             // FIXME: None of this is right for perpendicular writing-mode children.
2264             LayoutUnit childOldLogicalWidth = child->logicalWidth();
2265             LayoutUnit childOldMarginLeft = child->marginLeft();
2266             LayoutUnit childOldMarginRight = child->marginRight();
2267             LayoutUnit childOldLogicalTop = child->logicalTop();
2268
2269             child->setLogicalTop(newLogicalTop);
2270             child->updateLogicalWidth();
2271             region = regionAtBlockOffset(logicalTopForChild(child));
2272             borderBox = child->borderBoxRectInRegion(region, DoNotCacheRenderBoxRegionInfo);
2273             LayoutUnit childLogicalWidthAtNewLogicalTopOffset = isHorizontalWritingMode() ? borderBox.width() : borderBox.height();
2274
2275             child->setLogicalTop(childOldLogicalTop);
2276             child->setLogicalWidth(childOldLogicalWidth);
2277             child->setMarginLeft(childOldMarginLeft);
2278             child->setMarginRight(childOldMarginRight);
2279             
2280             if (childLogicalWidthAtNewLogicalTopOffset <= availableLogicalWidthAtNewLogicalTopOffset) {
2281                 // Even though we may not be moving, if the logical width did shrink because of the presence of new floats, then
2282                 // we need to force a relayout as though we shifted. This happens because of the dynamic addition of overhanging floats
2283                 // from previous siblings when negative margins exist on a child (see the addOverhangingFloats call at the end of collapseMargins).
2284                 if (childLogicalWidthAtOldLogicalTopOffset != childLogicalWidthAtNewLogicalTopOffset)
2285                     child->setChildNeedsLayout(MarkOnlyThis);
2286                 return newLogicalTop - logicalTop;
2287             }
2288
2289             newLogicalTop = nextFloatLogicalBottomBelow(newLogicalTop);
2290             ASSERT(newLogicalTop >= logicalTop);
2291             if (newLogicalTop < logicalTop)
2292                 break;
2293         }
2294         ASSERT_NOT_REACHED();
2295     }
2296     return result;
2297 }
2298
2299 bool RenderBlockFlow::hitTestFloats(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset)
2300 {
2301     if (!m_floatingObjects)
2302         return false;
2303
2304     LayoutPoint adjustedLocation = accumulatedOffset;
2305     if (isRenderView())
2306         adjustedLocation += toLayoutSize(toRenderView(*this).frameView().scrollPosition());
2307
2308     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2309     auto begin = floatingObjectSet.begin();
2310     for (auto it = floatingObjectSet.end(); it != begin;) {
2311         --it;
2312         FloatingObject* floatingObject = it->get();
2313         if (floatingObject->shouldPaint() && !floatingObject->renderer().hasSelfPaintingLayer()) {
2314             LayoutUnit xOffset = xPositionForFloatIncludingMargin(floatingObject) - floatingObject->renderer().x();
2315             LayoutUnit yOffset = yPositionForFloatIncludingMargin(floatingObject) - floatingObject->renderer().y();
2316             LayoutPoint childPoint = flipFloatForWritingModeForChild(floatingObject, adjustedLocation + LayoutSize(xOffset, yOffset));
2317             if (floatingObject->renderer().hitTest(request, result, locationInContainer, childPoint)) {
2318                 updateHitTestResult(result, locationInContainer.point() - toLayoutSize(childPoint));
2319                 return true;
2320             }
2321         }
2322     }
2323
2324     return false;
2325 }
2326
2327 void RenderBlockFlow::adjustForBorderFit(LayoutUnit x, LayoutUnit& left, LayoutUnit& right) const
2328 {
2329     RenderBlock::adjustForBorderFit(x, left, right);
2330         
2331     if (style()->visibility() == VISIBLE) {
2332         if (m_floatingObjects) {
2333             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2334             auto end = floatingObjectSet.end();
2335             for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2336                 FloatingObject* r = it->get();
2337                 // Only examine the object if our m_shouldPaint flag is set.
2338                 if (r->shouldPaint()) {
2339                     LayoutUnit floatLeft = xPositionForFloatIncludingMargin(r) - r->renderer().x();
2340                     LayoutUnit floatRight = floatLeft + r->renderer().width();
2341                     left = min(left, floatLeft);
2342                     right = max(right, floatRight);
2343                 }
2344             }
2345         }
2346     }
2347 }
2348
2349
2350 } // namespace WebCore