RenderElement::style() should return a reference.
[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 "Editor.h"
28 #include "FloatingObjects.h"
29 #include "Frame.h"
30 #include "HitTestLocation.h"
31 #include "InlineTextBox.h"
32 #include "LayoutRepainter.h"
33 #include "RenderFlowThread.h"
34 #include "RenderLayer.h"
35 #include "RenderNamedFlowFragment.h"
36 #include "RenderText.h"
37 #include "RenderView.h"
38 #include "SimpleLineLayoutFunctions.h"
39 #include "VerticalPositionCache.h"
40 #include "VisiblePosition.h"
41
42 using namespace std;
43
44 namespace WebCore {
45
46 bool RenderBlock::s_canPropagateFloatIntoSibling = false;
47
48 struct SameSizeAsMarginInfo {
49     uint32_t bitfields : 16;
50     LayoutUnit margins[2];
51 };
52
53 COMPILE_ASSERT(sizeof(RenderBlockFlow::MarginValues) == sizeof(LayoutUnit[4]), MarginValues_should_stay_small);
54 COMPILE_ASSERT(sizeof(RenderBlockFlow::MarginInfo) == sizeof(SameSizeAsMarginInfo), MarginInfo_should_stay_small);
55
56 // Our MarginInfo state used when laying out block children.
57 RenderBlockFlow::MarginInfo::MarginInfo(RenderBlockFlow& block, LayoutUnit beforeBorderPadding, LayoutUnit afterBorderPadding)
58     : m_atBeforeSideOfBlock(true)
59     , m_atAfterSideOfBlock(false)
60     , m_hasMarginBeforeQuirk(false)
61     , m_hasMarginAfterQuirk(false)
62     , m_determinedMarginBeforeQuirk(false)
63     , m_discardMargin(false)
64 {
65     const RenderStyle& blockStyle = block.style();
66     ASSERT(block.isRenderView() || block.parent());
67     m_canCollapseWithChildren = !block.isRenderView() && !block.isRoot() && !block.isOutOfFlowPositioned()
68         && !block.isFloating() && !block.isTableCell() && !block.hasOverflowClip() && !block.isInlineBlockOrInlineTable()
69         && !block.isRenderFlowThread() && !block.isWritingModeRoot() && !block.parent()->isFlexibleBox()
70         && blockStyle.hasAutoColumnCount() && blockStyle.hasAutoColumnWidth() && !blockStyle.columnSpan();
71
72     m_canCollapseMarginBeforeWithChildren = m_canCollapseWithChildren && !beforeBorderPadding && blockStyle.marginBeforeCollapse() != MSEPARATE;
73
74     // If any height other than auto is specified in CSS, then we don't collapse our bottom
75     // margins with our children's margins. To do otherwise would be to risk odd visual
76     // effects when the children overflow out of the parent block and yet still collapse
77     // with it. We also don't collapse if we have any bottom border/padding.
78     m_canCollapseMarginAfterWithChildren = m_canCollapseWithChildren && !afterBorderPadding
79         && (blockStyle.logicalHeight().isAuto() && !blockStyle.logicalHeight().value()) && blockStyle.marginAfterCollapse() != MSEPARATE;
80     
81     m_quirkContainer = block.isTableCell() || block.isBody();
82
83     m_discardMargin = m_canCollapseMarginBeforeWithChildren && block.mustDiscardMarginBefore();
84
85     m_positiveMargin = (m_canCollapseMarginBeforeWithChildren && !block.mustDiscardMarginBefore()) ? block.maxPositiveMarginBefore() : LayoutUnit();
86     m_negativeMargin = (m_canCollapseMarginBeforeWithChildren && !block.mustDiscardMarginBefore()) ? block.maxNegativeMarginBefore() : LayoutUnit();
87 }
88
89 RenderBlockFlow::RenderBlockFlow(Element& element, PassRef<RenderStyle> style)
90     : RenderBlock(element, std::move(style), RenderBlockFlowFlag)
91 {
92     setChildrenInline(true);
93 }
94
95 RenderBlockFlow::RenderBlockFlow(Document& document, PassRef<RenderStyle> style)
96     : RenderBlock(document, std::move(style), RenderBlockFlowFlag)
97 {
98     setChildrenInline(true);
99 }
100
101 RenderBlockFlow::~RenderBlockFlow()
102 {
103 }
104
105 void RenderBlockFlow::insertedIntoTree()
106 {
107     RenderBlock::insertedIntoTree();
108     createRenderNamedFlowFragmentIfNeeded();
109 }
110
111 void RenderBlockFlow::willBeDestroyed()
112 {
113     // Mark as being destroyed to avoid trouble with merges in removeChild().
114     m_beingDestroyed = true;
115
116     if (lineGridBox())
117         lineGridBox()->destroy(renderArena());
118
119     if (renderNamedFlowFragment())
120         setRenderNamedFlowFragment(0);
121
122     if (!documentBeingDestroyed()) {
123         if (firstChild() && firstChild()->isRunIn())
124             moveRunInToOriginalPosition(*firstChild());
125     }
126
127     // Make sure to destroy anonymous children first while they are still connected to the rest of the tree, so that they will
128     // properly dirty line boxes that they are removed from. Effects that do :before/:after only on hover could crash otherwise.
129     destroyLeftoverChildren();
130
131     // Destroy our continuation before anything other than anonymous children.
132     // The reason we don't destroy it before anonymous children is that they may
133     // have continuations of their own that are anonymous children of our continuation.
134     RenderBoxModelObject* continuation = this->continuation();
135     if (continuation) {
136         continuation->destroy();
137         setContinuation(0);
138     }
139
140     if (!documentBeingDestroyed()) {
141         if (firstLineBox()) {
142             // We can't wait for RenderBox::destroy to clear the selection,
143             // because by then we will have nuked the line boxes.
144             // FIXME: The FrameSelection should be responsible for this when it
145             // is notified of DOM mutations.
146             if (isSelectionBorder())
147                 view().clearSelection();
148
149             // If we are an anonymous block, then our line boxes might have children
150             // that will outlast this block. In the non-anonymous block case those
151             // children will be destroyed by the time we return from this function.
152             if (isAnonymousBlock()) {
153                 for (auto box = firstLineBox(); box; box = box->nextLineBox()) {
154                     while (auto childBox = box->firstChild())
155                         childBox->removeFromParent();
156                 }
157             }
158         } else if (parent())
159             parent()->dirtyLinesFromChangedChild(this);
160     }
161
162     m_lineBoxes.deleteLineBoxes(renderArena());
163
164     removeFromDelayedUpdateScrollInfoSet();
165
166     // NOTE: This jumps down to RenderBox, bypassing RenderBlock since it would do duplicate work.
167     RenderBox::willBeDestroyed();
168 }
169
170 void RenderBlockFlow::clearFloats()
171 {
172     if (m_floatingObjects)
173         m_floatingObjects->setHorizontalWritingMode(isHorizontalWritingMode());
174
175     HashSet<RenderBox*> oldIntrudingFloatSet;
176     if (!childrenInline() && m_floatingObjects) {
177         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
178         auto end = floatingObjectSet.end();
179         for (auto it = floatingObjectSet.begin(); it != end; ++it) {
180             FloatingObject* floatingObject = it->get();
181             if (!floatingObject->isDescendant())
182                 oldIntrudingFloatSet.add(&floatingObject->renderer());
183         }
184     }
185
186     // Inline blocks are covered by the isReplaced() check in the avoidFloats method.
187     if (avoidsFloats() || isRoot() || isRenderView() || isFloatingOrOutOfFlowPositioned() || isTableCell()) {
188         if (m_floatingObjects)
189             m_floatingObjects->clear();
190         if (!oldIntrudingFloatSet.isEmpty())
191             markAllDescendantsWithFloatsForLayout();
192         return;
193     }
194
195     RendererToFloatInfoMap floatMap;
196
197     if (m_floatingObjects) {
198         if (childrenInline())
199             m_floatingObjects->moveAllToFloatInfoMap(floatMap);
200         else
201             m_floatingObjects->clear();
202     }
203
204     // We should not process floats if the parent node is not a RenderBlock. Otherwise, we will add 
205     // floats in an invalid context. This will cause a crash arising from a bad cast on the parent.
206     // See <rdar://problem/8049753>, where float property is applied on a text node in a SVG.
207     if (!parent() || !parent()->isRenderBlockFlow())
208         return;
209
210     // Attempt to locate a previous sibling with overhanging floats. We skip any elements that are
211     // out of flow (like floating/positioned elements), and we also skip over any objects that may have shifted
212     // to avoid floats.
213     RenderBlockFlow* parentBlock = toRenderBlockFlow(parent());
214     bool parentHasFloats = false;
215     RenderObject* prev = previousSibling();
216     while (prev && (prev->isFloatingOrOutOfFlowPositioned() || !prev->isBox() || !prev->isRenderBlockFlow() || toRenderBlockFlow(prev)->avoidsFloats())) {
217         if (prev->isFloating())
218             parentHasFloats = true;
219         prev = prev->previousSibling();
220     }
221
222     // First add in floats from the parent.
223     LayoutUnit logicalTopOffset = logicalTop();
224     if (parentHasFloats)
225         addIntrudingFloats(parentBlock, parentBlock->logicalLeftOffsetForContent(), logicalTopOffset);
226     
227     LayoutUnit logicalLeftOffset = 0;
228     if (prev)
229         logicalTopOffset -= toRenderBox(prev)->logicalTop();
230     else {
231         prev = parentBlock;
232         logicalLeftOffset += parentBlock->logicalLeftOffsetForContent();
233     }
234
235     // Add overhanging floats from the previous RenderBlock, but only if it has a float that intrudes into our space.    
236     RenderBlockFlow* block = toRenderBlockFlow(prev);
237     if (block->m_floatingObjects && block->lowestFloatLogicalBottom() > logicalTopOffset)
238         addIntrudingFloats(block, logicalLeftOffset, logicalTopOffset);
239
240     if (childrenInline()) {
241         LayoutUnit changeLogicalTop = LayoutUnit::max();
242         LayoutUnit changeLogicalBottom = LayoutUnit::min();
243         if (m_floatingObjects) {
244             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
245             auto end = floatingObjectSet.end();
246             for (auto it = floatingObjectSet.begin(); it != end; ++it) {
247                 FloatingObject* floatingObject = it->get();
248                 std::unique_ptr<FloatingObject> oldFloatingObject = floatMap.take(&floatingObject->renderer());
249                 LayoutUnit logicalBottom = logicalBottomForFloat(floatingObject);
250                 if (oldFloatingObject) {
251                     LayoutUnit oldLogicalBottom = logicalBottomForFloat(oldFloatingObject.get());
252                     if (logicalWidthForFloat(floatingObject) != logicalWidthForFloat(oldFloatingObject.get()) || logicalLeftForFloat(floatingObject) != logicalLeftForFloat(oldFloatingObject.get())) {
253                         changeLogicalTop = 0;
254                         changeLogicalBottom = max(changeLogicalBottom, max(logicalBottom, oldLogicalBottom));
255                     } else {
256                         if (logicalBottom != oldLogicalBottom) {
257                             changeLogicalTop = min(changeLogicalTop, min(logicalBottom, oldLogicalBottom));
258                             changeLogicalBottom = max(changeLogicalBottom, max(logicalBottom, oldLogicalBottom));
259                         }
260                         LayoutUnit logicalTop = logicalTopForFloat(floatingObject);
261                         LayoutUnit oldLogicalTop = logicalTopForFloat(oldFloatingObject.get());
262                         if (logicalTop != oldLogicalTop) {
263                             changeLogicalTop = min(changeLogicalTop, min(logicalTop, oldLogicalTop));
264                             changeLogicalBottom = max(changeLogicalBottom, max(logicalTop, oldLogicalTop));
265                         }
266                     }
267
268                     if (oldFloatingObject->originatingLine() && !selfNeedsLayout()) {
269                         ASSERT(&oldFloatingObject->originatingLine()->renderer() == this);
270                         oldFloatingObject->originatingLine()->markDirty();
271                     }
272                 } else {
273                     changeLogicalTop = 0;
274                     changeLogicalBottom = max(changeLogicalBottom, logicalBottom);
275                 }
276             }
277         }
278
279         auto end = floatMap.end();
280         for (auto it = floatMap.begin(); it != end; ++it) {
281             FloatingObject* floatingObject = it->value.get();
282             if (!floatingObject->isDescendant()) {
283                 changeLogicalTop = 0;
284                 changeLogicalBottom = max(changeLogicalBottom, logicalBottomForFloat(floatingObject));
285             }
286         }
287
288         markLinesDirtyInBlockRange(changeLogicalTop, changeLogicalBottom);
289     } else if (!oldIntrudingFloatSet.isEmpty()) {
290         // If there are previously intruding floats that no longer intrude, then children with floats
291         // should also get layout because they might need their floating object lists cleared.
292         if (m_floatingObjects->set().size() < oldIntrudingFloatSet.size())
293             markAllDescendantsWithFloatsForLayout();
294         else {
295             const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
296             auto end = floatingObjectSet.end();
297             for (auto it = floatingObjectSet.begin(); it != end && !oldIntrudingFloatSet.isEmpty(); ++it)
298                 oldIntrudingFloatSet.remove(&(*it)->renderer());
299             if (!oldIntrudingFloatSet.isEmpty())
300                 markAllDescendantsWithFloatsForLayout();
301         }
302     }
303 }
304
305 void RenderBlockFlow::layoutBlock(bool relayoutChildren, LayoutUnit pageLogicalHeight)
306 {
307     ASSERT(needsLayout());
308
309     if (!relayoutChildren && simplifiedLayout())
310         return;
311
312     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
313
314     if (updateLogicalWidthAndColumnWidth())
315         relayoutChildren = true;
316
317     clearFloats();
318
319     LayoutUnit previousHeight = logicalHeight();
320     // FIXME: should this start out as borderAndPaddingLogicalHeight() + scrollbarLogicalHeight(),
321     // for consistency with other render classes?
322     setLogicalHeight(0);
323
324     bool pageLogicalHeightChanged = false;
325     bool hasSpecifiedPageLogicalHeight = false;
326     checkForPaginationLogicalHeightChange(pageLogicalHeight, pageLogicalHeightChanged, hasSpecifiedPageLogicalHeight);
327
328     const RenderStyle& styleToUse = style();
329     LayoutStateMaintainer statePusher(&view(), this, locationOffset(), hasColumns() || hasTransform() || hasReflection() || styleToUse.isFlippedBlocksWritingMode(), pageLogicalHeight, pageLogicalHeightChanged, columnInfo());
330
331     prepareShapesAndPaginationBeforeBlockLayout(relayoutChildren);
332     if (!relayoutChildren)
333         relayoutChildren = namedFlowFragmentNeedsUpdate();
334
335     // We use four values, maxTopPos, maxTopNeg, maxBottomPos, and maxBottomNeg, to track
336     // our current maximal positive and negative margins. These values are used when we
337     // are collapsed with adjacent blocks, so for example, if you have block A and B
338     // collapsing together, then you'd take the maximal positive margin from both A and B
339     // and subtract it from the maximal negative margin from both A and B to get the
340     // true collapsed margin. This algorithm is recursive, so when we finish layout()
341     // our block knows its current maximal positive/negative values.
342     //
343     // Start out by setting our margin values to our current margins. Table cells have
344     // no margins, so we don't fill in the values for table cells.
345     bool isCell = isTableCell();
346     if (!isCell) {
347         initMaxMarginValues();
348         
349         setHasMarginBeforeQuirk(styleToUse.hasMarginBeforeQuirk());
350         setHasMarginAfterQuirk(styleToUse.hasMarginAfterQuirk());
351         setPaginationStrut(0);
352     }
353
354     LayoutUnit repaintLogicalTop = 0;
355     LayoutUnit repaintLogicalBottom = 0;
356     LayoutUnit maxFloatLogicalBottom = 0;
357     if (!firstChild() && !isAnonymousBlock())
358         setChildrenInline(true);
359     if (childrenInline())
360         layoutInlineChildren(relayoutChildren, repaintLogicalTop, repaintLogicalBottom);
361     else
362         layoutBlockChildren(relayoutChildren, maxFloatLogicalBottom);
363
364     // Expand our intrinsic height to encompass floats.
365     LayoutUnit toAdd = borderAndPaddingAfter() + scrollbarLogicalHeight();
366     if (lowestFloatLogicalBottom() > (logicalHeight() - toAdd) && expandsToEncloseOverhangingFloats())
367         setLogicalHeight(lowestFloatLogicalBottom() + toAdd);
368     
369     if (relayoutForPagination(hasSpecifiedPageLogicalHeight, pageLogicalHeight, statePusher) || relayoutToAvoidWidows(statePusher)) {
370         ASSERT(!shouldBreakAtLineToAvoidWidow());
371         return;
372     }
373
374     // Calculate our new height.
375     LayoutUnit oldHeight = logicalHeight();
376     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
377
378     // Before updating the final size of the flow thread make sure a forced break is applied after the content.
379     // This ensures the size information is correctly computed for the last auto-height region receiving content.
380     if (isRenderFlowThread())
381         toRenderFlowThread(this)->applyBreakAfterContent(oldClientAfterEdge);
382
383     updateLogicalHeight();
384     LayoutUnit newHeight = logicalHeight();
385     if (oldHeight != newHeight) {
386         if (oldHeight > newHeight && maxFloatLogicalBottom > newHeight && !childrenInline()) {
387             // One of our children's floats may have become an overhanging float for us. We need to look for it.
388             for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
389                 if (child->isRenderBlockFlow() && !child->isFloatingOrOutOfFlowPositioned()) {
390                     RenderBlockFlow& block = toRenderBlockFlow(*child);
391                     if (block.lowestFloatLogicalBottom() + block.logicalTop() > newHeight)
392                         addOverhangingFloats(block, false);
393                 }
394             }
395         }
396     }
397
398     bool heightChanged = (previousHeight != newHeight);
399     if (heightChanged)
400         relayoutChildren = true;
401
402     layoutPositionedObjects(relayoutChildren || isRoot());
403
404     updateShapesAfterBlockLayout(heightChanged);
405
406     // Add overflow from children (unless we're multi-column, since in that case all our child overflow is clipped anyway).
407     computeOverflow(oldClientAfterEdge);
408     
409     statePusher.pop();
410
411     fitBorderToLinesIfNeeded();
412
413     if (view().layoutState()->m_pageLogicalHeight)
414         setPageLogicalOffset(view().layoutState()->pageLogicalOffset(this, logicalTop()));
415
416     updateLayerTransform();
417
418     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
419     // we overflow or not.
420     updateScrollInfoAfterLayout();
421
422     // FIXME: This repaint logic should be moved into a separate helper function!
423     // Repaint with our new bounds if they are different from our old bounds.
424     bool didFullRepaint = repainter.repaintAfterLayout();
425     if (!didFullRepaint && repaintLogicalTop != repaintLogicalBottom && (styleToUse.visibility() == VISIBLE || enclosingLayer()->hasVisibleContent())) {
426         // FIXME: We could tighten up the left and right invalidation points if we let layoutInlineChildren fill them in based off the particular lines
427         // it had to lay out. We wouldn't need the hasOverflowClip() hack in that case either.
428         LayoutUnit repaintLogicalLeft = logicalLeftVisualOverflow();
429         LayoutUnit repaintLogicalRight = logicalRightVisualOverflow();
430         if (hasOverflowClip()) {
431             // 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.
432             // 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.
433             // layoutInlineChildren should be patched to compute the entire repaint rect.
434             repaintLogicalLeft = min(repaintLogicalLeft, logicalLeftLayoutOverflow());
435             repaintLogicalRight = max(repaintLogicalRight, logicalRightLayoutOverflow());
436         }
437         
438         LayoutRect repaintRect;
439         if (isHorizontalWritingMode())
440             repaintRect = LayoutRect(repaintLogicalLeft, repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop);
441         else
442             repaintRect = LayoutRect(repaintLogicalTop, repaintLogicalLeft, repaintLogicalBottom - repaintLogicalTop, repaintLogicalRight - repaintLogicalLeft);
443
444         // The repaint rect may be split across columns, in which case adjustRectForColumns() will return the union.
445         adjustRectForColumns(repaintRect);
446
447         repaintRect.inflate(maximalOutlineSize(PaintPhaseOutline));
448         
449         if (hasOverflowClip()) {
450             // Adjust repaint rect for scroll offset
451             repaintRect.move(-scrolledContentOffset());
452
453             // Don't allow this rect to spill out of our overflow box.
454             repaintRect.intersect(LayoutRect(LayoutPoint(), size()));
455         }
456
457         // Make sure the rect is still non-empty after intersecting for overflow above
458         if (!repaintRect.isEmpty()) {
459             repaintRectangle(repaintRect); // We need to do a partial repaint of our content.
460             if (hasReflection())
461                 repaintRectangle(reflectedRect(repaintRect));
462         }
463     }
464
465     clearNeedsLayout();
466 }
467
468 void RenderBlockFlow::layoutBlockChildren(bool relayoutChildren, LayoutUnit& maxFloatLogicalBottom)
469 {
470     dirtyForLayoutFromPercentageHeightDescendants();
471
472     LayoutUnit beforeEdge = borderAndPaddingBefore();
473     LayoutUnit afterEdge = borderAndPaddingAfter() + scrollbarLogicalHeight();
474
475     setLogicalHeight(beforeEdge);
476     
477     // Lay out our hypothetical grid line as though it occurs at the top of the block.
478     if (view().layoutState()->lineGrid() == this)
479         layoutLineGridBox();
480
481     // The margin struct caches all our current margin collapsing state.
482     MarginInfo marginInfo(*this, beforeEdge, afterEdge);
483
484     // Fieldsets need to find their legend and position it inside the border of the object.
485     // The legend then gets skipped during normal layout. The same is true for ruby text.
486     // It doesn't get included in the normal layout process but is instead skipped.
487     RenderObject* childToExclude = layoutSpecialExcludedChild(relayoutChildren);
488
489     LayoutUnit previousFloatLogicalBottom = 0;
490     maxFloatLogicalBottom = 0;
491
492     RenderBox* next = firstChildBox();
493
494     while (next) {
495         RenderBox& child = *next;
496         next = child.nextSiblingBox();
497
498         if (childToExclude == &child)
499             continue; // Skip this child, since it will be positioned by the specialized subclass (fieldsets and ruby runs).
500
501         updateBlockChildDirtyBitsBeforeLayout(relayoutChildren, child);
502
503         if (child.isOutOfFlowPositioned()) {
504             child.containingBlock()->insertPositionedObject(child);
505             adjustPositionedBlock(child, marginInfo);
506             continue;
507         }
508         if (child.isFloating()) {
509             insertFloatingObject(child);
510             adjustFloatingBlock(marginInfo);
511             continue;
512         }
513
514         // Lay out the child.
515         layoutBlockChild(child, marginInfo, previousFloatLogicalBottom, maxFloatLogicalBottom);
516     }
517     
518     // Now do the handling of the bottom of the block, adding in our bottom border/padding and
519     // determining the correct collapsed bottom margin information.
520     handleAfterSideOfBlock(beforeEdge, afterEdge, marginInfo);
521 }
522
523 void RenderBlockFlow::layoutInlineChildren(bool relayoutChildren, LayoutUnit& repaintLogicalTop, LayoutUnit& repaintLogicalBottom)
524 {
525     if (m_lineLayoutPath == UndeterminedPath)
526         m_lineLayoutPath = SimpleLineLayout::canUseFor(*this) ? SimpleLinesPath : LineBoxesPath;
527
528     if (m_lineLayoutPath == SimpleLinesPath) {
529         deleteLineBoxesBeforeSimpleLineLayout();
530         layoutSimpleLines(repaintLogicalTop, repaintLogicalBottom);
531         return;
532     }
533
534     m_simpleLineLayout = nullptr;
535     layoutLineBoxes(relayoutChildren, repaintLogicalTop, repaintLogicalBottom);
536 }
537
538 void RenderBlockFlow::layoutBlockChild(RenderBox& child, MarginInfo& marginInfo, LayoutUnit& previousFloatLogicalBottom, LayoutUnit& maxFloatLogicalBottom)
539 {
540     LayoutUnit oldPosMarginBefore = maxPositiveMarginBefore();
541     LayoutUnit oldNegMarginBefore = maxNegativeMarginBefore();
542
543     // The child is a normal flow object. Compute the margins we will use for collapsing now.
544     child.computeAndSetBlockDirectionMargins(this);
545
546     // Try to guess our correct logical top position. In most cases this guess will
547     // be correct. Only if we're wrong (when we compute the real logical top position)
548     // will we have to potentially relayout.
549     LayoutUnit estimateWithoutPagination;
550     LayoutUnit logicalTopEstimate = estimateLogicalTopPosition(child, marginInfo, estimateWithoutPagination);
551
552     // Cache our old rect so that we can dirty the proper repaint rects if the child moves.
553     LayoutRect oldRect = child.frameRect();
554     LayoutUnit oldLogicalTop = logicalTopForChild(child);
555
556 #if !ASSERT_DISABLED
557     LayoutSize oldLayoutDelta = view().layoutDelta();
558 #endif
559     // Go ahead and position the child as though it didn't collapse with the top.
560     setLogicalTopForChild(child, logicalTopEstimate, ApplyLayoutDelta);
561     estimateRegionRangeForBoxChild(child);
562
563     RenderBlockFlow* childBlockFlow = child.isRenderBlockFlow() ? toRenderBlockFlow(&child) : nullptr;
564     bool markDescendantsWithFloats = false;
565     if (logicalTopEstimate != oldLogicalTop && !child.avoidsFloats() && childBlockFlow && childBlockFlow->containsFloats())
566         markDescendantsWithFloats = true;
567 #if ENABLE(SUBPIXEL_LAYOUT)
568     else if (UNLIKELY(logicalTopEstimate.mightBeSaturated()))
569         // logicalTopEstimate, returned by estimateLogicalTopPosition, might be saturated for
570         // very large elements. If it does the comparison with oldLogicalTop might yield a
571         // false negative as adding and removing margins, borders etc from a saturated number
572         // might yield incorrect results. If this is the case always mark for layout.
573         markDescendantsWithFloats = true;
574 #endif
575     else if (!child.avoidsFloats() || child.shrinkToAvoidFloats()) {
576         // If an element might be affected by the presence of floats, then always mark it for
577         // layout.
578         LayoutUnit fb = max(previousFloatLogicalBottom, lowestFloatLogicalBottom());
579         if (fb > logicalTopEstimate)
580             markDescendantsWithFloats = true;
581     }
582
583     if (childBlockFlow) {
584         if (markDescendantsWithFloats)
585             childBlockFlow->markAllDescendantsWithFloatsForLayout();
586         if (!child.isWritingModeRoot())
587             previousFloatLogicalBottom = max(previousFloatLogicalBottom, oldLogicalTop + childBlockFlow->lowestFloatLogicalBottom());
588     }
589
590     if (!child.needsLayout())
591         child.markForPaginationRelayoutIfNeeded();
592
593     bool childHadLayout = child.everHadLayout();
594     bool childNeededLayout = child.needsLayout();
595     if (childNeededLayout)
596         child.layout();
597
598     // Cache if we are at the top of the block right now.
599     bool atBeforeSideOfBlock = marginInfo.atBeforeSideOfBlock();
600
601     // Now determine the correct ypos based off examination of collapsing margin
602     // values.
603     LayoutUnit logicalTopBeforeClear = collapseMargins(child, marginInfo);
604
605     // Now check for clear.
606     LayoutUnit logicalTopAfterClear = clearFloatsIfNeeded(child, marginInfo, oldPosMarginBefore, oldNegMarginBefore, logicalTopBeforeClear);
607     
608     bool paginated = view().layoutState()->isPaginated();
609     if (paginated)
610         logicalTopAfterClear = adjustBlockChildForPagination(logicalTopAfterClear, estimateWithoutPagination, child, atBeforeSideOfBlock && logicalTopBeforeClear == logicalTopAfterClear);
611
612     setLogicalTopForChild(child, logicalTopAfterClear, ApplyLayoutDelta);
613
614     // Now we have a final top position. See if it really does end up being different from our estimate.
615     // clearFloatsIfNeeded can also mark the child as needing a layout even though we didn't move. This happens
616     // when collapseMargins dynamically adds overhanging floats because of a child with negative margins.
617     if (logicalTopAfterClear != logicalTopEstimate || child.needsLayout() || (paginated && childBlockFlow && childBlockFlow->shouldBreakAtLineToAvoidWidow())) {
618         if (child.shrinkToAvoidFloats()) {
619             // The child's width depends on the line width.
620             // When the child shifts to clear an item, its width can
621             // change (because it has more available line width).
622             // So go ahead and mark the item as dirty.
623             child.setChildNeedsLayout(MarkOnlyThis);
624         }
625         
626         if (childBlockFlow) {
627             if (!child.avoidsFloats() && childBlockFlow->containsFloats())
628                 childBlockFlow->markAllDescendantsWithFloatsForLayout();
629             if (!child.needsLayout())
630                 child.markForPaginationRelayoutIfNeeded();
631         }
632
633         // Our guess was wrong. Make the child lay itself out again.
634         child.layoutIfNeeded();
635     }
636
637     if (updateRegionRangeForBoxChild(child)) {
638         child.setNeedsLayout(MarkOnlyThis);
639         child.layoutIfNeeded();
640     }
641
642     // We are no longer at the top of the block if we encounter a non-empty child.  
643     // This has to be done after checking for clear, so that margins can be reset if a clear occurred.
644     if (marginInfo.atBeforeSideOfBlock() && !child.isSelfCollapsingBlock())
645         marginInfo.setAtBeforeSideOfBlock(false);
646
647     // Now place the child in the correct left position
648     determineLogicalLeftPositionForChild(child, ApplyLayoutDelta);
649
650     LayoutSize childOffset = child.location() - oldRect.location();
651 #if ENABLE(CSS_SHAPES)
652     relayoutShapeDescendantIfMoved(child.isRenderBlock() ? toRenderBlock(&child) : nullptr, childOffset);
653 #endif
654
655     // Update our height now that the child has been placed in the correct position.
656     setLogicalHeight(logicalHeight() + logicalHeightForChild(child));
657     if (mustSeparateMarginAfterForChild(child)) {
658         setLogicalHeight(logicalHeight() + marginAfterForChild(child));
659         marginInfo.clearMargin();
660     }
661     // If the child has overhanging floats that intrude into following siblings (or possibly out
662     // of this block), then the parent gets notified of the floats now.
663     if (childBlockFlow && childBlockFlow->containsFloats())
664         maxFloatLogicalBottom = max(maxFloatLogicalBottom, addOverhangingFloats(*childBlockFlow, !childNeededLayout));
665
666     if (childOffset.width() || childOffset.height()) {
667         view().addLayoutDelta(childOffset);
668
669         // If the child moved, we have to repaint it as well as any floating/positioned
670         // descendants. An exception is if we need a layout. In this case, we know we're going to
671         // repaint ourselves (and the child) anyway.
672         if (childHadLayout && !selfNeedsLayout() && child.checkForRepaintDuringLayout())
673             child.repaintDuringLayoutIfMoved(oldRect);
674     }
675
676     if (!childHadLayout && child.checkForRepaintDuringLayout()) {
677         child.repaint();
678         child.repaintOverhangingFloats(true);
679     }
680
681     if (paginated) {
682         // Check for an after page/column break.
683         LayoutUnit newHeight = applyAfterBreak(child, logicalHeight(), marginInfo);
684         if (newHeight != height())
685             setLogicalHeight(newHeight);
686     }
687
688     ASSERT(view().layoutDeltaMatches(oldLayoutDelta));
689 }
690
691 void RenderBlockFlow::adjustPositionedBlock(RenderBox& child, const MarginInfo& marginInfo)
692 {
693     bool isHorizontal = isHorizontalWritingMode();
694     bool hasStaticBlockPosition = child.style().hasStaticBlockPosition(isHorizontal);
695     
696     LayoutUnit logicalTop = logicalHeight();
697     updateStaticInlinePositionForChild(child, logicalTop);
698
699     if (!marginInfo.canCollapseWithMarginBefore()) {
700         // Positioned blocks don't collapse margins, so add the margin provided by
701         // the container now. The child's own margin is added later when calculating its logical top.
702         LayoutUnit collapsedBeforePos = marginInfo.positiveMargin();
703         LayoutUnit collapsedBeforeNeg = marginInfo.negativeMargin();
704         logicalTop += collapsedBeforePos - collapsedBeforeNeg;
705     }
706     
707     RenderLayer* childLayer = child.layer();
708     if (childLayer->staticBlockPosition() != logicalTop) {
709         childLayer->setStaticBlockPosition(logicalTop);
710         if (hasStaticBlockPosition)
711             child.setChildNeedsLayout(MarkOnlyThis);
712     }
713 }
714
715 void RenderBlockFlow::adjustFloatingBlock(const MarginInfo& marginInfo)
716 {
717     // The float should be positioned taking into account the bottom margin
718     // of the previous flow. We add that margin into the height, get the
719     // float positioned properly, and then subtract the margin out of the
720     // height again. In the case of self-collapsing blocks, we always just
721     // use the top margins, since the self-collapsing block collapsed its
722     // own bottom margin into its top margin.
723     //
724     // Note also that the previous flow may collapse its margin into the top of
725     // our block. If this is the case, then we do not add the margin in to our
726     // height when computing the position of the float. This condition can be tested
727     // for by simply calling canCollapseWithMarginBefore. See
728     // http://www.hixie.ch/tests/adhoc/css/box/block/margin-collapse/046.html for
729     // an example of this scenario.
730     LayoutUnit marginOffset = marginInfo.canCollapseWithMarginBefore() ? LayoutUnit() : marginInfo.margin();
731     setLogicalHeight(logicalHeight() + marginOffset);
732     positionNewFloats();
733     setLogicalHeight(logicalHeight() - marginOffset);
734 }
735
736 void RenderBlockFlow::updateStaticInlinePositionForChild(RenderBox& child, LayoutUnit logicalTop)
737 {
738     if (child.style().isOriginalDisplayInlineType())
739         setStaticInlinePositionForChild(child, logicalTop, startAlignedOffsetForLine(logicalTop, false));
740     else
741         setStaticInlinePositionForChild(child, logicalTop, startOffsetForContent(logicalTop));
742 }
743
744 void RenderBlockFlow::setStaticInlinePositionForChild(RenderBox& child, LayoutUnit blockOffset, LayoutUnit inlinePosition)
745 {
746     if (flowThreadContainingBlock()) {
747         // Shift the inline position to exclude the region offset.
748         inlinePosition += startOffsetForContent() - startOffsetForContent(blockOffset);
749     }
750     child.layer()->setStaticInlinePosition(inlinePosition);
751 }
752
753 RenderBlockFlow::MarginValues RenderBlockFlow::marginValuesForChild(RenderBox& child) const
754 {
755     LayoutUnit childBeforePositive = 0;
756     LayoutUnit childBeforeNegative = 0;
757     LayoutUnit childAfterPositive = 0;
758     LayoutUnit childAfterNegative = 0;
759
760     LayoutUnit beforeMargin = 0;
761     LayoutUnit afterMargin = 0;
762
763     RenderBlockFlow* childRenderBlock = child.isRenderBlockFlow() ? toRenderBlockFlow(&child) : nullptr;
764     
765     // If the child has the same directionality as we do, then we can just return its
766     // margins in the same direction.
767     if (!child.isWritingModeRoot()) {
768         if (childRenderBlock) {
769             childBeforePositive = childRenderBlock->maxPositiveMarginBefore();
770             childBeforeNegative = childRenderBlock->maxNegativeMarginBefore();
771             childAfterPositive = childRenderBlock->maxPositiveMarginAfter();
772             childAfterNegative = childRenderBlock->maxNegativeMarginAfter();
773         } else {
774             beforeMargin = child.marginBefore();
775             afterMargin = child.marginAfter();
776         }
777     } else if (child.isHorizontalWritingMode() == isHorizontalWritingMode()) {
778         // The child has a different directionality. If the child is parallel, then it's just
779         // flipped relative to us. We can use the margins for the opposite edges.
780         if (childRenderBlock) {
781             childBeforePositive = childRenderBlock->maxPositiveMarginAfter();
782             childBeforeNegative = childRenderBlock->maxNegativeMarginAfter();
783             childAfterPositive = childRenderBlock->maxPositiveMarginBefore();
784             childAfterNegative = childRenderBlock->maxNegativeMarginBefore();
785         } else {
786             beforeMargin = child.marginAfter();
787             afterMargin = child.marginBefore();
788         }
789     } else {
790         // The child is perpendicular to us, which means its margins don't collapse but are on the
791         // "logical left/right" sides of the child box. We can just return the raw margin in this case.
792         beforeMargin = marginBeforeForChild(child);
793         afterMargin = marginAfterForChild(child);
794     }
795
796     // Resolve uncollapsing margins into their positive/negative buckets.
797     if (beforeMargin) {
798         if (beforeMargin > 0)
799             childBeforePositive = beforeMargin;
800         else
801             childBeforeNegative = -beforeMargin;
802     }
803     if (afterMargin) {
804         if (afterMargin > 0)
805             childAfterPositive = afterMargin;
806         else
807             childAfterNegative = -afterMargin;
808     }
809
810     return MarginValues(childBeforePositive, childBeforeNegative, childAfterPositive, childAfterNegative);
811 }
812
813 LayoutUnit RenderBlockFlow::collapseMargins(RenderBox& child, MarginInfo& marginInfo)
814 {
815     bool childDiscardMarginBefore = mustDiscardMarginBeforeForChild(child);
816     bool childDiscardMarginAfter = mustDiscardMarginAfterForChild(child);
817     bool childIsSelfCollapsing = child.isSelfCollapsingBlock();
818
819     // The child discards the before margin when the the after margin has discard in the case of a self collapsing block.
820     childDiscardMarginBefore = childDiscardMarginBefore || (childDiscardMarginAfter && childIsSelfCollapsing);
821
822     // Get the four margin values for the child and cache them.
823     const MarginValues childMargins = marginValuesForChild(child);
824
825     // Get our max pos and neg top margins.
826     LayoutUnit posTop = childMargins.positiveMarginBefore();
827     LayoutUnit negTop = childMargins.negativeMarginBefore();
828
829     // For self-collapsing blocks, collapse our bottom margins into our
830     // top to get new posTop and negTop values.
831     if (childIsSelfCollapsing) {
832         posTop = max(posTop, childMargins.positiveMarginAfter());
833         negTop = max(negTop, childMargins.negativeMarginAfter());
834     }
835     
836     // See if the top margin is quirky. We only care if this child has
837     // margins that will collapse with us.
838     bool topQuirk = hasMarginBeforeQuirk(child);
839
840     if (marginInfo.canCollapseWithMarginBefore()) {
841         if (!childDiscardMarginBefore && !marginInfo.discardMargin()) {
842             // This child is collapsing with the top of the
843             // block. If it has larger margin values, then we need to update
844             // our own maximal values.
845             if (!document().inQuirksMode() || !marginInfo.quirkContainer() || !topQuirk)
846                 setMaxMarginBeforeValues(max(posTop, maxPositiveMarginBefore()), max(negTop, maxNegativeMarginBefore()));
847
848             // The minute any of the margins involved isn't a quirk, don't
849             // collapse it away, even if the margin is smaller (www.webreference.com
850             // has an example of this, a <dt> with 0.8em author-specified inside
851             // a <dl> inside a <td>.
852             if (!marginInfo.determinedMarginBeforeQuirk() && !topQuirk && (posTop - negTop)) {
853                 setHasMarginBeforeQuirk(false);
854                 marginInfo.setDeterminedMarginBeforeQuirk(true);
855             }
856
857             if (!marginInfo.determinedMarginBeforeQuirk() && topQuirk && !marginBefore())
858                 // We have no top margin and our top child has a quirky margin.
859                 // We will pick up this quirky margin and pass it through.
860                 // This deals with the <td><div><p> case.
861                 // Don't do this for a block that split two inlines though. You do
862                 // still apply margins in this case.
863                 setHasMarginBeforeQuirk(true);
864         } else
865             // The before margin of the container will also discard all the margins it is collapsing with.
866             setMustDiscardMarginBefore();
867     }
868
869     // Once we find a child with discardMarginBefore all the margins collapsing with us must also discard. 
870     if (childDiscardMarginBefore) {
871         marginInfo.setDiscardMargin(true);
872         marginInfo.clearMargin();
873     }
874
875     if (marginInfo.quirkContainer() && marginInfo.atBeforeSideOfBlock() && (posTop - negTop))
876         marginInfo.setHasMarginBeforeQuirk(topQuirk);
877
878     LayoutUnit beforeCollapseLogicalTop = logicalHeight();
879     LayoutUnit logicalTop = beforeCollapseLogicalTop;
880     if (childIsSelfCollapsing) {
881         // 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.
882         // Also, the child's top position equals the logical height of the container.
883         if (!childDiscardMarginBefore && !marginInfo.discardMargin()) {
884             // This child has no height. We need to compute our
885             // position before we collapse the child's margins together,
886             // so that we can get an accurate position for the zero-height block.
887             LayoutUnit collapsedBeforePos = max(marginInfo.positiveMargin(), childMargins.positiveMarginBefore());
888             LayoutUnit collapsedBeforeNeg = max(marginInfo.negativeMargin(), childMargins.negativeMarginBefore());
889             marginInfo.setMargin(collapsedBeforePos, collapsedBeforeNeg);
890             
891             // Now collapse the child's margins together, which means examining our
892             // bottom margin values as well. 
893             marginInfo.setPositiveMarginIfLarger(childMargins.positiveMarginAfter());
894             marginInfo.setNegativeMarginIfLarger(childMargins.negativeMarginAfter());
895
896             if (!marginInfo.canCollapseWithMarginBefore())
897                 // We need to make sure that the position of the self-collapsing block
898                 // is correct, since it could have overflowing content
899                 // that needs to be positioned correctly (e.g., a block that
900                 // had a specified height of 0 but that actually had subcontent).
901                 logicalTop = logicalHeight() + collapsedBeforePos - collapsedBeforeNeg;
902         }
903     } else {
904         if (mustSeparateMarginBeforeForChild(child)) {
905             ASSERT(!marginInfo.discardMargin() || (marginInfo.discardMargin() && !marginInfo.margin()));
906             // If we are at the before side of the block and we collapse, ignore the computed margin
907             // and just add the child margin to the container height. This will correctly position
908             // the child inside the container.
909             LayoutUnit separateMargin = !marginInfo.canCollapseWithMarginBefore() ? marginInfo.margin() : LayoutUnit(0);
910             setLogicalHeight(logicalHeight() + separateMargin + marginBeforeForChild(child));
911             logicalTop = logicalHeight();
912         } else if (!marginInfo.discardMargin() && (!marginInfo.atBeforeSideOfBlock()
913             || (!marginInfo.canCollapseMarginBeforeWithChildren()
914             && (!document().inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.hasMarginBeforeQuirk())))) {
915             // We're collapsing with a previous sibling's margins and not
916             // with the top of the block.
917             setLogicalHeight(logicalHeight() + max(marginInfo.positiveMargin(), posTop) - max(marginInfo.negativeMargin(), negTop));
918             logicalTop = logicalHeight();
919         }
920
921         marginInfo.setDiscardMargin(childDiscardMarginAfter);
922         
923         if (!marginInfo.discardMargin()) {
924             marginInfo.setPositiveMargin(childMargins.positiveMarginAfter());
925             marginInfo.setNegativeMargin(childMargins.negativeMarginAfter());
926         } else
927             marginInfo.clearMargin();
928
929         if (marginInfo.margin())
930             marginInfo.setHasMarginAfterQuirk(hasMarginAfterQuirk(child));
931     }
932     
933     // If margins would pull us past the top of the next page, then we need to pull back and pretend like the margins
934     // collapsed into the page edge.
935     LayoutState* layoutState = view().layoutState();
936     if (layoutState->isPaginated() && layoutState->pageLogicalHeight() && logicalTop > beforeCollapseLogicalTop
937         && hasNextPage(beforeCollapseLogicalTop)) {
938         LayoutUnit oldLogicalTop = logicalTop;
939         logicalTop = min(logicalTop, nextPageLogicalTop(beforeCollapseLogicalTop));
940         setLogicalHeight(logicalHeight() + (logicalTop - oldLogicalTop));
941     }
942
943     // If we have collapsed into a previous sibling and so reduced the height of the parent, ensure any floats that now
944     // overhang from the previous sibling are added to our parent. If the child's previous sibling itself is a float the child will avoid
945     // or clear it anyway, so don't worry about any floating children it may contain.
946     LayoutUnit oldLogicalHeight = logicalHeight();
947     setLogicalHeight(logicalTop);
948     RenderObject* prev = child.previousSibling();
949     if (prev && prev->isRenderBlockFlow() && !prev->isFloatingOrOutOfFlowPositioned()) {
950         RenderBlockFlow& block = toRenderBlockFlow(*prev);
951         if (block.containsFloats() && !block.avoidsFloats() && (block.logicalTop() + block.lowestFloatLogicalBottom()) > logicalTop)
952             addOverhangingFloats(block, false);
953     }
954     setLogicalHeight(oldLogicalHeight);
955
956     return logicalTop;
957 }
958
959 LayoutUnit RenderBlockFlow::clearFloatsIfNeeded(RenderBox& child, MarginInfo& marginInfo, LayoutUnit oldTopPosMargin, LayoutUnit oldTopNegMargin, LayoutUnit yPos)
960 {
961     LayoutUnit heightIncrease = getClearDelta(child, yPos);
962     if (!heightIncrease)
963         return yPos;
964
965     if (child.isSelfCollapsingBlock()) {
966         bool childDiscardMargin = mustDiscardMarginBeforeForChild(child) || mustDiscardMarginAfterForChild(child);
967
968         // For self-collapsing blocks that clear, they can still collapse their
969         // margins with following siblings. Reset the current margins to represent
970         // the self-collapsing block's margins only.
971         // If DISCARD is specified for -webkit-margin-collapse, reset the margin values.
972         if (!childDiscardMargin) {
973             MarginValues childMargins = marginValuesForChild(child);
974             marginInfo.setPositiveMargin(max(childMargins.positiveMarginBefore(), childMargins.positiveMarginAfter()));
975             marginInfo.setNegativeMargin(max(childMargins.negativeMarginBefore(), childMargins.negativeMarginAfter()));
976         } else
977             marginInfo.clearMargin();
978         marginInfo.setDiscardMargin(childDiscardMargin);
979
980         // CSS2.1 states:
981         // "If the top and bottom margins of an element with clearance are adjoining, its margins collapse with 
982         // the adjoining margins of following siblings but that resulting margin does not collapse with the bottom margin of the parent block."
983         // So the parent's bottom margin cannot collapse through this block or any subsequent self-collapsing blocks. Check subsequent siblings
984         // for a block with height - if none is found then don't allow the margins to collapse with the parent.
985         bool wouldCollapseMarginsWithParent = marginInfo.canCollapseMarginAfterWithChildren();
986         for (RenderBox* curr = child.nextSiblingBox(); curr && wouldCollapseMarginsWithParent; curr = curr->nextSiblingBox()) {
987             if (!curr->isFloatingOrOutOfFlowPositioned() && !curr->isSelfCollapsingBlock())
988                 wouldCollapseMarginsWithParent = false;
989         }
990         if (wouldCollapseMarginsWithParent)
991             marginInfo.setCanCollapseMarginAfterWithChildren(false);
992
993         // CSS2.1: "the amount of clearance is set so that clearance + margin-top = [height of float], i.e., clearance = [height of float] - margin-top"
994         // Move the top of the child box to the bottom of the float ignoring the child's top margin.
995         LayoutUnit collapsedMargin = collapsedMarginBeforeForChild(child);
996         setLogicalHeight(child.logicalTop() - collapsedMargin);
997         // A negative collapsed margin-top value cancels itself out as it has already been factored into |yPos| above.
998         heightIncrease -= max(LayoutUnit(), collapsedMargin);
999     } else
1000         // Increase our height by the amount we had to clear.
1001         setLogicalHeight(logicalHeight() + heightIncrease);
1002     
1003     if (marginInfo.canCollapseWithMarginBefore()) {
1004         // We can no longer collapse with the top of the block since a clear
1005         // occurred. The empty blocks collapse into the cleared block.
1006         // FIXME: This isn't quite correct. Need clarification for what to do
1007         // if the height the cleared block is offset by is smaller than the
1008         // margins involved.
1009         setMaxMarginBeforeValues(oldTopPosMargin, oldTopNegMargin);
1010         marginInfo.setAtBeforeSideOfBlock(false);
1011
1012         // In case the child discarded the before margin of the block we need to reset the mustDiscardMarginBefore flag to the initial value.
1013         setMustDiscardMarginBefore(style().marginBeforeCollapse() == MDISCARD);
1014     }
1015
1016     LayoutUnit logicalTop = yPos + heightIncrease;
1017     // After margin collapsing, one of our floats may now intrude into the child. If the child doesn't contain floats of its own it
1018     // won't get picked up for relayout even though the logical top estimate was wrong - so add the newly intruding float now.
1019     if (containsFloats() && child.isRenderBlockFlow() && !toRenderBlockFlow(child).containsFloats() && !child.avoidsFloats() && lowestFloatLogicalBottom() > logicalTop)
1020         toRenderBlockFlow(child).addIntrudingFloats(this, logicalLeftOffsetForContent(), logicalTop);
1021
1022     return logicalTop;
1023 }
1024
1025 void RenderBlockFlow::marginBeforeEstimateForChild(RenderBox& child, LayoutUnit& positiveMarginBefore, LayoutUnit& negativeMarginBefore, bool& discardMarginBefore) const
1026 {
1027     // Give up if in quirks mode and we're a body/table cell and the top margin of the child box is quirky.
1028     // Give up if the child specified -webkit-margin-collapse: separate that prevents collapsing.
1029     // FIXME: Use writing mode independent accessor for marginBeforeCollapse.
1030     if ((document().inQuirksMode() && hasMarginAfterQuirk(child) && (isTableCell() || isBody())) || child.style().marginBeforeCollapse() == MSEPARATE)
1031         return;
1032
1033     // The margins are discarded by a child that specified -webkit-margin-collapse: discard.
1034     // FIXME: Use writing mode independent accessor for marginBeforeCollapse.
1035     if (child.style().marginBeforeCollapse() == MDISCARD) {
1036         positiveMarginBefore = 0;
1037         negativeMarginBefore = 0;
1038         discardMarginBefore = true;
1039         return;
1040     }
1041
1042     LayoutUnit beforeChildMargin = marginBeforeForChild(child);
1043     positiveMarginBefore = max(positiveMarginBefore, beforeChildMargin);
1044     negativeMarginBefore = max(negativeMarginBefore, -beforeChildMargin);
1045
1046     if (!child.isRenderBlockFlow())
1047         return;
1048     
1049     RenderBlockFlow& childBlock = toRenderBlockFlow(child);
1050     if (childBlock.childrenInline() || childBlock.isWritingModeRoot())
1051         return;
1052
1053     MarginInfo childMarginInfo(childBlock, childBlock.borderAndPaddingBefore(), childBlock.borderAndPaddingAfter());
1054     if (!childMarginInfo.canCollapseMarginBeforeWithChildren())
1055         return;
1056
1057     RenderBox* grandchildBox = childBlock.firstChildBox();
1058     for (; grandchildBox; grandchildBox = grandchildBox->nextSiblingBox()) {
1059         if (!grandchildBox->isFloatingOrOutOfFlowPositioned())
1060             break;
1061     }
1062     
1063     // Give up if there is clearance on the box, since it probably won't collapse into us.
1064     if (!grandchildBox || grandchildBox->style().clear() != CNONE)
1065         return;
1066
1067     // Make sure to update the block margins now for the grandchild box so that we're looking at current values.
1068     if (grandchildBox->needsLayout()) {
1069         grandchildBox->computeAndSetBlockDirectionMargins(this);
1070         if (grandchildBox->isRenderBlock()) {
1071             RenderBlock* grandchildBlock = toRenderBlock(grandchildBox);
1072             grandchildBlock->setHasMarginBeforeQuirk(grandchildBox->style().hasMarginBeforeQuirk());
1073             grandchildBlock->setHasMarginAfterQuirk(grandchildBox->style().hasMarginAfterQuirk());
1074         }
1075     }
1076
1077     // Collapse the margin of the grandchild box with our own to produce an estimate.
1078     childBlock.marginBeforeEstimateForChild(*grandchildBox, positiveMarginBefore, negativeMarginBefore, discardMarginBefore);
1079 }
1080
1081 LayoutUnit RenderBlockFlow::estimateLogicalTopPosition(RenderBox& child, const MarginInfo& marginInfo, LayoutUnit& estimateWithoutPagination)
1082 {
1083     // FIXME: We need to eliminate the estimation of vertical position, because when it's wrong we sometimes trigger a pathological
1084     // relayout if there are intruding floats.
1085     LayoutUnit logicalTopEstimate = logicalHeight();
1086     if (!marginInfo.canCollapseWithMarginBefore()) {
1087         LayoutUnit positiveMarginBefore = 0;
1088         LayoutUnit negativeMarginBefore = 0;
1089         bool discardMarginBefore = false;
1090         if (child.selfNeedsLayout()) {
1091             // Try to do a basic estimation of how the collapse is going to go.
1092             marginBeforeEstimateForChild(child, positiveMarginBefore, negativeMarginBefore, discardMarginBefore);
1093         } else {
1094             // Use the cached collapsed margin values from a previous layout. Most of the time they
1095             // will be right.
1096             MarginValues marginValues = marginValuesForChild(child);
1097             positiveMarginBefore = max(positiveMarginBefore, marginValues.positiveMarginBefore());
1098             negativeMarginBefore = max(negativeMarginBefore, marginValues.negativeMarginBefore());
1099             discardMarginBefore = mustDiscardMarginBeforeForChild(child);
1100         }
1101
1102         // Collapse the result with our current margins.
1103         if (!discardMarginBefore)
1104             logicalTopEstimate += max(marginInfo.positiveMargin(), positiveMarginBefore) - max(marginInfo.negativeMargin(), negativeMarginBefore);
1105     }
1106
1107     // Adjust logicalTopEstimate down to the next page if the margins are so large that we don't fit on the current
1108     // page.
1109     LayoutState* layoutState = view().layoutState();
1110     if (layoutState->isPaginated() && layoutState->pageLogicalHeight() && logicalTopEstimate > logicalHeight()
1111         && hasNextPage(logicalHeight()))
1112         logicalTopEstimate = min(logicalTopEstimate, nextPageLogicalTop(logicalHeight()));
1113
1114     logicalTopEstimate += getClearDelta(child, logicalTopEstimate);
1115     
1116     estimateWithoutPagination = logicalTopEstimate;
1117
1118     if (layoutState->isPaginated()) {
1119         // If the object has a page or column break value of "before", then we should shift to the top of the next page.
1120         logicalTopEstimate = applyBeforeBreak(child, logicalTopEstimate);
1121     
1122         // For replaced elements and scrolled elements, we want to shift them to the next page if they don't fit on the current one.
1123         logicalTopEstimate = adjustForUnsplittableChild(child, logicalTopEstimate);
1124         
1125         if (!child.selfNeedsLayout() && child.isRenderBlock())
1126             logicalTopEstimate += toRenderBlock(child).paginationStrut();
1127     }
1128
1129     return logicalTopEstimate;
1130 }
1131
1132 void RenderBlockFlow::setCollapsedBottomMargin(const MarginInfo& marginInfo)
1133 {
1134     if (marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()) {
1135         // 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.
1136         // Don't update the max margin values because we won't need them anyway.
1137         if (marginInfo.discardMargin()) {
1138             setMustDiscardMarginAfter();
1139             return;
1140         }
1141
1142         // Update our max pos/neg bottom margins, since we collapsed our bottom margins
1143         // with our children.
1144         setMaxMarginAfterValues(max(maxPositiveMarginAfter(), marginInfo.positiveMargin()), max(maxNegativeMarginAfter(), marginInfo.negativeMargin()));
1145
1146         if (!marginInfo.hasMarginAfterQuirk())
1147             setHasMarginAfterQuirk(false);
1148
1149         if (marginInfo.hasMarginAfterQuirk() && !marginAfter())
1150             // We have no bottom margin and our last child has a quirky margin.
1151             // We will pick up this quirky margin and pass it through.
1152             // This deals with the <td><div><p> case.
1153             setHasMarginAfterQuirk(true);
1154     }
1155 }
1156
1157 void RenderBlockFlow::handleAfterSideOfBlock(LayoutUnit beforeSide, LayoutUnit afterSide, MarginInfo& marginInfo)
1158 {
1159     marginInfo.setAtAfterSideOfBlock(true);
1160
1161     // If we can't collapse with children then go ahead and add in the bottom margin.
1162     if (!marginInfo.discardMargin() && (!marginInfo.canCollapseWithMarginAfter() && !marginInfo.canCollapseWithMarginBefore()
1163         && (!document().inQuirksMode() || !marginInfo.quirkContainer() || !marginInfo.hasMarginAfterQuirk())))
1164         setLogicalHeight(logicalHeight() + marginInfo.margin());
1165         
1166     // Now add in our bottom border/padding.
1167     setLogicalHeight(logicalHeight() + afterSide);
1168
1169     // Negative margins can cause our height to shrink below our minimal height (border/padding).
1170     // If this happens, ensure that the computed height is increased to the minimal height.
1171     setLogicalHeight(max(logicalHeight(), beforeSide + afterSide));
1172
1173     // Update our bottom collapsed margin info.
1174     setCollapsedBottomMargin(marginInfo);
1175 }
1176
1177 void RenderBlockFlow::setMaxMarginBeforeValues(LayoutUnit pos, LayoutUnit neg)
1178 {
1179     if (!m_rareData) {
1180         if (pos == RenderBlockFlowRareData::positiveMarginBeforeDefault(*this) && neg == RenderBlockFlowRareData::negativeMarginBeforeDefault(*this))
1181             return;
1182         m_rareData = adoptPtr(new RenderBlockFlowRareData(*this));
1183     }
1184     m_rareData->m_margins.setPositiveMarginBefore(pos);
1185     m_rareData->m_margins.setNegativeMarginBefore(neg);
1186 }
1187
1188 void RenderBlockFlow::setMaxMarginAfterValues(LayoutUnit pos, LayoutUnit neg)
1189 {
1190     if (!m_rareData) {
1191         if (pos == RenderBlockFlowRareData::positiveMarginAfterDefault(*this) && neg == RenderBlockFlowRareData::negativeMarginAfterDefault(*this))
1192             return;
1193         m_rareData = adoptPtr(new RenderBlockFlowRareData(*this));
1194     }
1195     m_rareData->m_margins.setPositiveMarginAfter(pos);
1196     m_rareData->m_margins.setNegativeMarginAfter(neg);
1197 }
1198
1199 void RenderBlockFlow::setMustDiscardMarginBefore(bool value)
1200 {
1201     if (style().marginBeforeCollapse() == MDISCARD) {
1202         ASSERT(value);
1203         return;
1204     }
1205     
1206     if (!m_rareData && !value)
1207         return;
1208
1209     if (!m_rareData)
1210         m_rareData = adoptPtr(new RenderBlockFlowRareData(*this));
1211
1212     m_rareData->m_discardMarginBefore = value;
1213 }
1214
1215 void RenderBlockFlow::setMustDiscardMarginAfter(bool value)
1216 {
1217     if (style().marginAfterCollapse() == MDISCARD) {
1218         ASSERT(value);
1219         return;
1220     }
1221
1222     if (!m_rareData && !value)
1223         return;
1224
1225     if (!m_rareData)
1226         m_rareData = adoptPtr(new RenderBlockFlowRareData(*this));
1227
1228     m_rareData->m_discardMarginAfter = value;
1229 }
1230
1231 bool RenderBlockFlow::mustDiscardMarginBefore() const
1232 {
1233     return style().marginBeforeCollapse() == MDISCARD || (m_rareData && m_rareData->m_discardMarginBefore);
1234 }
1235
1236 bool RenderBlockFlow::mustDiscardMarginAfter() const
1237 {
1238     return style().marginAfterCollapse() == MDISCARD || (m_rareData && m_rareData->m_discardMarginAfter);
1239 }
1240
1241 bool RenderBlockFlow::mustDiscardMarginBeforeForChild(const RenderBox& child) const
1242 {
1243     ASSERT(!child.selfNeedsLayout());
1244     if (!child.isWritingModeRoot())
1245         return child.isRenderBlockFlow() ? toRenderBlockFlow(child).mustDiscardMarginBefore() : (child.style().marginBeforeCollapse() == MDISCARD);
1246     if (child.isHorizontalWritingMode() == isHorizontalWritingMode())
1247         return child.isRenderBlockFlow() ? toRenderBlockFlow(child).mustDiscardMarginAfter() : (child.style().marginAfterCollapse() == MDISCARD);
1248
1249     // FIXME: We return false here because the implementation is not geometrically complete. We have values only for before/after, not start/end.
1250     // In case the boxes are perpendicular we assume the property is not specified.
1251     return false;
1252 }
1253
1254 bool RenderBlockFlow::mustDiscardMarginAfterForChild(const RenderBox& child) const
1255 {
1256     ASSERT(!child.selfNeedsLayout());
1257     if (!child.isWritingModeRoot())
1258         return child.isRenderBlockFlow() ? toRenderBlockFlow(child).mustDiscardMarginAfter() : (child.style().marginAfterCollapse() == MDISCARD);
1259     if (child.isHorizontalWritingMode() == isHorizontalWritingMode())
1260         return child.isRenderBlockFlow() ? toRenderBlockFlow(child).mustDiscardMarginBefore() : (child.style().marginBeforeCollapse() == MDISCARD);
1261
1262     // FIXME: See |mustDiscardMarginBeforeForChild| above.
1263     return false;
1264 }
1265
1266 bool RenderBlockFlow::mustSeparateMarginBeforeForChild(const RenderBox& child) const
1267 {
1268     ASSERT(!child.selfNeedsLayout());
1269     const RenderStyle& childStyle = child.style();
1270     if (!child.isWritingModeRoot())
1271         return childStyle.marginBeforeCollapse() == MSEPARATE;
1272     if (child.isHorizontalWritingMode() == isHorizontalWritingMode())
1273         return childStyle.marginAfterCollapse() == MSEPARATE;
1274
1275     // FIXME: See |mustDiscardMarginBeforeForChild| above.
1276     return false;
1277 }
1278
1279 bool RenderBlockFlow::mustSeparateMarginAfterForChild(const RenderBox& child) const
1280 {
1281     ASSERT(!child.selfNeedsLayout());
1282     const RenderStyle& childStyle = child.style();
1283     if (!child.isWritingModeRoot())
1284         return childStyle.marginAfterCollapse() == MSEPARATE;
1285     if (child.isHorizontalWritingMode() == isHorizontalWritingMode())
1286         return childStyle.marginBeforeCollapse() == MSEPARATE;
1287
1288     // FIXME: See |mustDiscardMarginBeforeForChild| above.
1289     return false;
1290 }
1291
1292 static bool inNormalFlow(RenderBox& child)
1293 {
1294     RenderBlock* curr = child.containingBlock();
1295     while (curr && curr != &child.view()) {
1296         if (curr->hasColumns() || curr->isRenderFlowThread())
1297             return true;
1298         if (curr->isFloatingOrOutOfFlowPositioned())
1299             return false;
1300         curr = curr->containingBlock();
1301     }
1302     return true;
1303 }
1304
1305 LayoutUnit RenderBlockFlow::applyBeforeBreak(RenderBox& child, LayoutUnit logicalOffset)
1306 {
1307     // FIXME: Add page break checking here when we support printing.
1308     bool checkColumnBreaks = view().layoutState()->isPaginatingColumns();
1309     bool checkPageBreaks = !checkColumnBreaks && view().layoutState()->m_pageLogicalHeight; // FIXME: Once columns can print we have to check this.
1310     RenderFlowThread* flowThread = flowThreadContainingBlock();
1311     bool checkRegionBreaks = flowThread && flowThread->isRenderNamedFlowThread();
1312     bool checkBeforeAlways = (checkColumnBreaks && child.style().columnBreakBefore() == PBALWAYS) || (checkPageBreaks && child.style().pageBreakBefore() == PBALWAYS)
1313         || (checkRegionBreaks && child.style().regionBreakBefore() == PBALWAYS);
1314     if (checkBeforeAlways && inNormalFlow(child) && hasNextPage(logicalOffset, IncludePageBoundary)) {
1315         if (checkColumnBreaks)
1316             view().layoutState()->addForcedColumnBreak(&child, logicalOffset);
1317         if (checkRegionBreaks) {
1318             LayoutUnit offsetBreakAdjustment = 0;
1319             if (flowThread->addForcedRegionBreak(this, offsetFromLogicalTopOfFirstPage() + logicalOffset, &child, true, &offsetBreakAdjustment))
1320                 return logicalOffset + offsetBreakAdjustment;
1321         }
1322         return nextPageLogicalTop(logicalOffset, IncludePageBoundary);
1323     }
1324     return logicalOffset;
1325 }
1326
1327 LayoutUnit RenderBlockFlow::applyAfterBreak(RenderBox& child, LayoutUnit logicalOffset, MarginInfo& marginInfo)
1328 {
1329     // FIXME: Add page break checking here when we support printing.
1330     bool checkColumnBreaks = view().layoutState()->isPaginatingColumns();
1331     bool checkPageBreaks = !checkColumnBreaks && view().layoutState()->m_pageLogicalHeight; // FIXME: Once columns can print we have to check this.
1332     RenderFlowThread* flowThread = flowThreadContainingBlock();
1333     bool checkRegionBreaks = flowThread && flowThread->isRenderNamedFlowThread();
1334     bool checkAfterAlways = (checkColumnBreaks && child.style().columnBreakAfter() == PBALWAYS) || (checkPageBreaks && child.style().pageBreakAfter() == PBALWAYS)
1335         || (checkRegionBreaks && child.style().regionBreakAfter() == PBALWAYS);
1336     if (checkAfterAlways && inNormalFlow(child) && hasNextPage(logicalOffset, IncludePageBoundary)) {
1337         LayoutUnit marginOffset = marginInfo.canCollapseWithMarginBefore() ? LayoutUnit() : marginInfo.margin();
1338
1339         // So our margin doesn't participate in the next collapsing steps.
1340         marginInfo.clearMargin();
1341
1342         if (checkColumnBreaks)
1343             view().layoutState()->addForcedColumnBreak(&child, logicalOffset);
1344         if (checkRegionBreaks) {
1345             LayoutUnit offsetBreakAdjustment = 0;
1346             if (flowThread->addForcedRegionBreak(this, offsetFromLogicalTopOfFirstPage() + logicalOffset + marginOffset, &child, false, &offsetBreakAdjustment))
1347                 return logicalOffset + marginOffset + offsetBreakAdjustment;
1348         }
1349         return nextPageLogicalTop(logicalOffset, IncludePageBoundary);
1350     }
1351     return logicalOffset;
1352 }
1353
1354 LayoutUnit RenderBlockFlow::adjustBlockChildForPagination(LayoutUnit logicalTopAfterClear, LayoutUnit estimateWithoutPagination, RenderBox& child, bool atBeforeSideOfBlock)
1355 {
1356     RenderBlock* childRenderBlock = child.isRenderBlock() ? toRenderBlock(&child) : nullptr;
1357
1358     if (estimateWithoutPagination != logicalTopAfterClear) {
1359         // Our guess prior to pagination movement was wrong. Before we attempt to paginate, let's try again at the new
1360         // position.
1361         setLogicalHeight(logicalTopAfterClear);
1362         setLogicalTopForChild(child, logicalTopAfterClear, ApplyLayoutDelta);
1363
1364         if (child.shrinkToAvoidFloats()) {
1365             // The child's width depends on the line width.
1366             // When the child shifts to clear an item, its width can
1367             // change (because it has more available line width).
1368             // So go ahead and mark the item as dirty.
1369             child.setChildNeedsLayout(MarkOnlyThis);
1370         }
1371         
1372         if (childRenderBlock) {
1373             if (!child.avoidsFloats() && childRenderBlock->containsFloats())
1374                 toRenderBlockFlow(childRenderBlock)->markAllDescendantsWithFloatsForLayout();
1375             if (!child.needsLayout())
1376                 child.markForPaginationRelayoutIfNeeded();
1377         }
1378
1379         // Our guess was wrong. Make the child lay itself out again.
1380         child.layoutIfNeeded();
1381     }
1382
1383     LayoutUnit oldTop = logicalTopAfterClear;
1384
1385     // If the object has a page or column break value of "before", then we should shift to the top of the next page.
1386     LayoutUnit result = applyBeforeBreak(child, logicalTopAfterClear);
1387
1388     if (pageLogicalHeightForOffset(result)) {
1389         LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(result, ExcludePageBoundary);
1390         LayoutUnit spaceShortage = child.logicalHeight() - remainingLogicalHeight;
1391         if (spaceShortage > 0) {
1392             // If the child crosses a column boundary, report a break, in case nothing inside it has already
1393             // done so. The column balancer needs to know how much it has to stretch the columns to make more
1394             // content fit. If no breaks are reported (but do occur), the balancer will have no clue. FIXME:
1395             // This should be improved, though, because here we just pretend that the child is
1396             // unsplittable. A splittable child, on the other hand, has break opportunities at every position
1397             // where there's no child content, border or padding. In other words, we risk stretching more
1398             // than necessary.
1399             setPageBreak(result, spaceShortage);
1400         }
1401     }
1402
1403     // For replaced elements and scrolled elements, we want to shift them to the next page if they don't fit on the current one.
1404     LayoutUnit logicalTopBeforeUnsplittableAdjustment = result;
1405     LayoutUnit logicalTopAfterUnsplittableAdjustment = adjustForUnsplittableChild(child, result);
1406     
1407     LayoutUnit paginationStrut = 0;
1408     LayoutUnit unsplittableAdjustmentDelta = logicalTopAfterUnsplittableAdjustment - logicalTopBeforeUnsplittableAdjustment;
1409     if (unsplittableAdjustmentDelta)
1410         paginationStrut = unsplittableAdjustmentDelta;
1411     else if (childRenderBlock && childRenderBlock->paginationStrut())
1412         paginationStrut = childRenderBlock->paginationStrut();
1413
1414     if (paginationStrut) {
1415         // We are willing to propagate out to our parent block as long as we were at the top of the block prior
1416         // to collapsing our margins, and as long as we didn't clear or move as a result of other pagination.
1417         if (atBeforeSideOfBlock && oldTop == result && !isOutOfFlowPositioned() && !isTableCell()) {
1418             // FIXME: Should really check if we're exceeding the page height before propagating the strut, but we don't
1419             // have all the information to do so (the strut only has the remaining amount to push). Gecko gets this wrong too
1420             // and pushes to the next page anyway, so not too concerned about it.
1421             setPaginationStrut(result + paginationStrut);
1422             if (childRenderBlock)
1423                 childRenderBlock->setPaginationStrut(0);
1424         } else
1425             result += paginationStrut;
1426     }
1427
1428     // Similar to how we apply clearance. Go ahead and boost height() to be the place where we're going to position the child.
1429     setLogicalHeight(logicalHeight() + (result - oldTop));
1430     
1431     // Return the final adjusted logical top.
1432     return result;
1433 }
1434
1435 static inline LayoutUnit calculateMinimumPageHeight(RenderStyle* renderStyle, RootInlineBox* lastLine, LayoutUnit lineTop, LayoutUnit lineBottom)
1436 {
1437     // We may require a certain minimum number of lines per page in order to satisfy
1438     // orphans and widows, and that may affect the minimum page height.
1439     unsigned lineCount = max<unsigned>(renderStyle->hasAutoOrphans() ? 1 : renderStyle->orphans(), renderStyle->hasAutoWidows() ? 1 : renderStyle->widows());
1440     if (lineCount > 1) {
1441         RootInlineBox* line = lastLine;
1442         for (unsigned i = 1; i < lineCount && line->prevRootBox(); i++)
1443             line = line->prevRootBox();
1444
1445         // FIXME: Paginating using line overflow isn't all fine. See FIXME in
1446         // adjustLinePositionForPagination() for more details.
1447         LayoutRect overflow = line->logicalVisualOverflowRect(line->lineTop(), line->lineBottom());
1448         lineTop = min(line->lineTopWithLeading(), overflow.y());
1449     }
1450     return lineBottom - lineTop;
1451 }
1452
1453 void RenderBlockFlow::adjustLinePositionForPagination(RootInlineBox* lineBox, LayoutUnit& delta, RenderFlowThread* flowThread)
1454 {
1455     // FIXME: For now we paginate using line overflow. This ensures that lines don't overlap at all when we
1456     // put a strut between them for pagination purposes. However, this really isn't the desired rendering, since
1457     // the line on the top of the next page will appear too far down relative to the same kind of line at the top
1458     // of the first column.
1459     //
1460     // The rendering we would like to see is one where the lineTopWithLeading is at the top of the column, and any line overflow
1461     // simply spills out above the top of the column. This effect would match what happens at the top of the first column.
1462     // We can't achieve this rendering, however, until we stop columns from clipping to the column bounds (thus allowing
1463     // for overflow to occur), and then cache visible overflow for each column rect.
1464     //
1465     // Furthermore, the paint we have to do when a column has overflow has to be special. We need to exclude
1466     // content that paints in a previous column (and content that paints in the following column).
1467     //
1468     // For now we'll at least honor the lineTopWithLeading when paginating if it is above the logical top overflow. This will
1469     // at least make positive leading work in typical cases.
1470     //
1471     // FIXME: Another problem with simply moving lines is that the available line width may change (because of floats).
1472     // Technically if the location we move the line to has a different line width than our old position, then we need to dirty the
1473     // line and all following lines.
1474     LayoutRect logicalVisualOverflow = lineBox->logicalVisualOverflowRect(lineBox->lineTop(), lineBox->lineBottom());
1475     LayoutUnit logicalOffset = min(lineBox->lineTopWithLeading(), logicalVisualOverflow.y());
1476     LayoutUnit logicalBottom = max(lineBox->lineBottomWithLeading(), logicalVisualOverflow.maxY());
1477     LayoutUnit lineHeight = logicalBottom - logicalOffset;
1478     updateMinimumPageHeight(logicalOffset, calculateMinimumPageHeight(&style(), lineBox, logicalOffset, logicalBottom));
1479     logicalOffset += delta;
1480     lineBox->setPaginationStrut(0);
1481     lineBox->setIsFirstAfterPageBreak(false);
1482     LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset);
1483     bool hasUniformPageLogicalHeight = !flowThread || flowThread->regionsHaveUniformLogicalHeight();
1484     // If lineHeight is greater than pageLogicalHeight, but logicalVisualOverflow.height() still fits, we are
1485     // still going to add a strut, so that the visible overflow fits on a single page.
1486     if (!pageLogicalHeight || (hasUniformPageLogicalHeight && logicalVisualOverflow.height() > pageLogicalHeight)
1487         || !hasNextPage(logicalOffset))
1488         // 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.
1489         // 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.
1490         return;
1491     LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(logicalOffset, ExcludePageBoundary);
1492
1493     int lineIndex = lineCount(lineBox);
1494     if (remainingLogicalHeight < lineHeight || (shouldBreakAtLineToAvoidWidow() && lineBreakToAvoidWidow() == lineIndex)) {
1495         if (shouldBreakAtLineToAvoidWidow() && lineBreakToAvoidWidow() == lineIndex) {
1496             clearShouldBreakAtLineToAvoidWidow();
1497             setDidBreakAtLineToAvoidWidow();
1498         }
1499         // If we have a non-uniform page height, then we have to shift further possibly.
1500         if (!hasUniformPageLogicalHeight && !pushToNextPageWithMinimumLogicalHeight(remainingLogicalHeight, logicalOffset, lineHeight))
1501             return;
1502         if (lineHeight > pageLogicalHeight) {
1503             // Split the top margin in order to avoid splitting the visible part of the line.
1504             remainingLogicalHeight -= min(lineHeight - pageLogicalHeight, max<LayoutUnit>(0, logicalVisualOverflow.y() - lineBox->lineTopWithLeading()));
1505         }
1506         LayoutUnit totalLogicalHeight = lineHeight + max<LayoutUnit>(0, logicalOffset);
1507         LayoutUnit pageLogicalHeightAtNewOffset = hasUniformPageLogicalHeight ? pageLogicalHeight : pageLogicalHeightForOffset(logicalOffset + remainingLogicalHeight);
1508         setPageBreak(logicalOffset, lineHeight - remainingLogicalHeight);
1509         if (((lineBox == firstRootBox() && totalLogicalHeight < pageLogicalHeightAtNewOffset) || (!style().hasAutoOrphans() && style().orphans() >= lineIndex))
1510             && !isOutOfFlowPositioned() && !isTableCell())
1511             setPaginationStrut(remainingLogicalHeight + max<LayoutUnit>(0, logicalOffset));
1512         else {
1513             delta += remainingLogicalHeight;
1514             lineBox->setPaginationStrut(remainingLogicalHeight);
1515             lineBox->setIsFirstAfterPageBreak(true);
1516         }
1517     } else if (remainingLogicalHeight == pageLogicalHeight && lineBox != firstRootBox())
1518         lineBox->setIsFirstAfterPageBreak(true);
1519 }
1520
1521 void RenderBlockFlow::setBreakAtLineToAvoidWidow(int lineToBreak)
1522 {
1523     ASSERT(lineToBreak >= 0);
1524     if (!m_rareData)
1525         m_rareData = adoptPtr(new RenderBlockFlowRareData(*this));
1526
1527     ASSERT(!m_rareData->m_didBreakAtLineToAvoidWidow);
1528     m_rareData->m_lineBreakToAvoidWidow = lineToBreak;
1529 }
1530
1531 void RenderBlockFlow::setDidBreakAtLineToAvoidWidow()
1532 {
1533     ASSERT(!shouldBreakAtLineToAvoidWidow());
1534     if (!m_rareData)
1535         return;
1536
1537     m_rareData->m_didBreakAtLineToAvoidWidow = true;
1538 }
1539
1540 void RenderBlockFlow::clearDidBreakAtLineToAvoidWidow()
1541 {
1542     if (!m_rareData)
1543         return;
1544
1545     m_rareData->m_didBreakAtLineToAvoidWidow = false;
1546 }
1547
1548 void RenderBlockFlow::clearShouldBreakAtLineToAvoidWidow() const
1549 {
1550     ASSERT(shouldBreakAtLineToAvoidWidow());
1551     if (!m_rareData)
1552         return;
1553
1554     m_rareData->m_lineBreakToAvoidWidow = -1;
1555 }
1556
1557 bool RenderBlockFlow::relayoutToAvoidWidows(LayoutStateMaintainer& statePusher)
1558 {
1559     if (!shouldBreakAtLineToAvoidWidow())
1560         return false;
1561
1562     statePusher.pop();
1563     setEverHadLayout(true);
1564     layoutBlock(false);
1565     return true;
1566 }
1567
1568 bool RenderBlockFlow::hasNextPage(LayoutUnit logicalOffset, PageBoundaryRule pageBoundaryRule) const
1569 {
1570     ASSERT(view().layoutState() && view().layoutState()->isPaginated());
1571
1572     RenderFlowThread* flowThread = flowThreadContainingBlock();
1573     if (!flowThread)
1574         return true; // Printing and multi-column both make new pages to accommodate content.
1575
1576     // See if we're in the last region.
1577     LayoutUnit pageOffset = offsetFromLogicalTopOfFirstPage() + logicalOffset;
1578     RenderRegion* region = flowThread->regionAtBlockOffset(this, pageOffset, this);
1579     if (!region)
1580         return false;
1581     if (region->isLastRegion())
1582         return region->isRenderRegionSet() || region->style().regionFragment() == BreakRegionFragment
1583             || (pageBoundaryRule == IncludePageBoundary && pageOffset == region->logicalTopForFlowThreadContent());
1584     return true;
1585 }
1586
1587 LayoutUnit RenderBlockFlow::adjustForUnsplittableChild(RenderBox& child, LayoutUnit logicalOffset, bool includeMargins)
1588 {
1589     bool checkColumnBreaks = view().layoutState()->isPaginatingColumns();
1590     bool checkPageBreaks = !checkColumnBreaks && view().layoutState()->m_pageLogicalHeight;
1591     RenderFlowThread* flowThread = flowThreadContainingBlock();
1592     bool checkRegionBreaks = flowThread && flowThread->isRenderNamedFlowThread();
1593     bool isUnsplittable = child.isUnsplittableForPagination() || (checkColumnBreaks && child.style().columnBreakInside() == PBAVOID)
1594         || (checkPageBreaks && child.style().pageBreakInside() == PBAVOID)
1595         || (checkRegionBreaks && child.style().regionBreakInside() == PBAVOID);
1596     if (!isUnsplittable)
1597         return logicalOffset;
1598     LayoutUnit childLogicalHeight = logicalHeightForChild(child) + (includeMargins ? marginBeforeForChild(child) + marginAfterForChild(child) : LayoutUnit());
1599     LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset);
1600     bool hasUniformPageLogicalHeight = !flowThread || flowThread->regionsHaveUniformLogicalHeight();
1601     updateMinimumPageHeight(logicalOffset, childLogicalHeight);
1602     if (!pageLogicalHeight || (hasUniformPageLogicalHeight && childLogicalHeight > pageLogicalHeight)
1603         || !hasNextPage(logicalOffset))
1604         return logicalOffset;
1605     LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(logicalOffset, ExcludePageBoundary);
1606     if (remainingLogicalHeight < childLogicalHeight) {
1607         if (!hasUniformPageLogicalHeight && !pushToNextPageWithMinimumLogicalHeight(remainingLogicalHeight, logicalOffset, childLogicalHeight))
1608             return logicalOffset;
1609         return logicalOffset + remainingLogicalHeight;
1610     }
1611     return logicalOffset;
1612 }
1613
1614 bool RenderBlockFlow::pushToNextPageWithMinimumLogicalHeight(LayoutUnit& adjustment, LayoutUnit logicalOffset, LayoutUnit minimumLogicalHeight) const
1615 {
1616     bool checkRegion = false;
1617     for (LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset + adjustment); pageLogicalHeight;
1618         pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset + adjustment)) {
1619         if (minimumLogicalHeight <= pageLogicalHeight)
1620             return true;
1621         if (!hasNextPage(logicalOffset + adjustment))
1622             return false;
1623         adjustment += pageLogicalHeight;
1624         checkRegion = true;
1625     }
1626     return !checkRegion;
1627 }
1628
1629 void RenderBlockFlow::setPageBreak(LayoutUnit offset, LayoutUnit spaceShortage)
1630 {
1631     if (RenderFlowThread* flowThread = flowThreadContainingBlock())
1632         flowThread->setPageBreak(this, offsetFromLogicalTopOfFirstPage() + offset, spaceShortage);
1633 }
1634
1635 void RenderBlockFlow::updateMinimumPageHeight(LayoutUnit offset, LayoutUnit minHeight)
1636 {
1637     if (RenderFlowThread* flowThread = flowThreadContainingBlock())
1638         flowThread->updateMinimumPageHeight(this, offsetFromLogicalTopOfFirstPage() + offset, minHeight);
1639     else if (ColumnInfo* colInfo = view().layoutState()->m_columnInfo)
1640         colInfo->updateMinimumColumnHeight(minHeight);
1641 }
1642
1643 LayoutUnit RenderBlockFlow::nextPageLogicalTop(LayoutUnit logicalOffset, PageBoundaryRule pageBoundaryRule) const
1644 {
1645     LayoutUnit pageLogicalHeight = pageLogicalHeightForOffset(logicalOffset);
1646     if (!pageLogicalHeight)
1647         return logicalOffset;
1648     
1649     // The logicalOffset is in our coordinate space.  We can add in our pushed offset.
1650     LayoutUnit remainingLogicalHeight = pageRemainingLogicalHeightForOffset(logicalOffset);
1651     if (pageBoundaryRule == ExcludePageBoundary)
1652         return logicalOffset + (remainingLogicalHeight ? remainingLogicalHeight : pageLogicalHeight);
1653     return logicalOffset + remainingLogicalHeight;
1654 }
1655
1656 LayoutUnit RenderBlockFlow::pageLogicalTopForOffset(LayoutUnit offset) const
1657 {
1658     LayoutUnit firstPageLogicalTop = isHorizontalWritingMode() ? view().layoutState()->m_pageOffset.height() : view().layoutState()->m_pageOffset.width();
1659     LayoutUnit blockLogicalTop = isHorizontalWritingMode() ? view().layoutState()->m_layoutOffset.height() : view().layoutState()->m_layoutOffset.width();
1660
1661     LayoutUnit cumulativeOffset = offset + blockLogicalTop;
1662     RenderFlowThread* flowThread = flowThreadContainingBlock();
1663     if (!flowThread) {
1664         LayoutUnit pageLogicalHeight = view().layoutState()->pageLogicalHeight();
1665         if (!pageLogicalHeight)
1666             return 0;
1667         return cumulativeOffset - roundToInt(cumulativeOffset - firstPageLogicalTop) % roundToInt(pageLogicalHeight);
1668     }
1669     return flowThread->pageLogicalTopForOffset(cumulativeOffset);
1670 }
1671
1672 LayoutUnit RenderBlockFlow::pageLogicalHeightForOffset(LayoutUnit offset) const
1673 {
1674     RenderFlowThread* flowThread = flowThreadContainingBlock();
1675     if (!flowThread)
1676         return view().layoutState()->m_pageLogicalHeight;
1677     return flowThread->pageLogicalHeightForOffset(offset + offsetFromLogicalTopOfFirstPage());
1678 }
1679
1680 LayoutUnit RenderBlockFlow::pageRemainingLogicalHeightForOffset(LayoutUnit offset, PageBoundaryRule pageBoundaryRule) const
1681 {
1682     offset += offsetFromLogicalTopOfFirstPage();
1683     
1684     RenderFlowThread* flowThread = flowThreadContainingBlock();
1685     if (!flowThread) {
1686         LayoutUnit pageLogicalHeight = view().layoutState()->m_pageLogicalHeight;
1687         LayoutUnit remainingHeight = pageLogicalHeight - intMod(offset, pageLogicalHeight);
1688         if (pageBoundaryRule == IncludePageBoundary) {
1689             // If includeBoundaryPoint is true the line exactly on the top edge of a
1690             // column will act as being part of the previous column.
1691             remainingHeight = intMod(remainingHeight, pageLogicalHeight);
1692         }
1693         return remainingHeight;
1694     }
1695     
1696     return flowThread->pageRemainingLogicalHeightForOffset(offset, pageBoundaryRule);
1697 }
1698
1699
1700 void RenderBlockFlow::layoutLineGridBox()
1701 {
1702     if (style().lineGrid() == RenderStyle::initialLineGrid()) {
1703         setLineGridBox(0);
1704         return;
1705     }
1706     
1707     setLineGridBox(0);
1708
1709     RootInlineBox* lineGridBox = new (renderArena()) RootInlineBox(*this);
1710     lineGridBox->setHasTextChildren(); // Needed to make the line ascent/descent actually be honored in quirks mode.
1711     lineGridBox->setConstructed();
1712     GlyphOverflowAndFallbackFontsMap textBoxDataMap;
1713     VerticalPositionCache verticalPositionCache;
1714     lineGridBox->alignBoxesInBlockDirection(logicalHeight(), textBoxDataMap, verticalPositionCache);
1715     
1716     setLineGridBox(lineGridBox);
1717     
1718     // FIXME: If any of the characteristics of the box change compared to the old one, then we need to do a deep dirtying
1719     // (similar to what happens when the page height changes). Ideally, though, we only do this if someone is actually snapping
1720     // to this grid.
1721 }
1722
1723 bool RenderBlockFlow::containsFloat(RenderBox& renderer) const
1724 {
1725     return m_floatingObjects && m_floatingObjects->set().contains<RenderBox&, FloatingObjectHashTranslator>(renderer);
1726 }
1727
1728 void RenderBlockFlow::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
1729 {
1730     RenderBlock::styleDidChange(diff, oldStyle);
1731     
1732     // After our style changed, if we lose our ability to propagate floats into next sibling
1733     // blocks, then we need to find the top most parent containing that overhanging float and
1734     // then mark its descendants with floats for layout and clear all floats from its next
1735     // sibling blocks that exist in our floating objects list. See bug 56299 and 62875.
1736     bool canPropagateFloatIntoSibling = !isFloatingOrOutOfFlowPositioned() && !avoidsFloats();
1737     if (diff == StyleDifferenceLayout && s_canPropagateFloatIntoSibling && !canPropagateFloatIntoSibling && hasOverhangingFloats()) {
1738         RenderBlockFlow* parentBlock = this;
1739         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1740         auto end = floatingObjectSet.end();
1741
1742         for (auto curr = parent(); curr && !curr->isRenderView(); curr = curr->parent()) {
1743             if (curr->isRenderBlockFlow()) {
1744                 RenderBlockFlow* currBlock = toRenderBlockFlow(curr);
1745
1746                 if (currBlock->hasOverhangingFloats()) {
1747                     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1748                         RenderBox& renderer = (*it)->renderer();
1749                         if (currBlock->hasOverhangingFloat(renderer)) {
1750                             parentBlock = currBlock;
1751                             break;
1752                         }
1753                     }
1754                 }
1755             }
1756         }
1757
1758         parentBlock->markAllDescendantsWithFloatsForLayout();
1759         parentBlock->markSiblingsWithFloatsForLayout();
1760     }
1761
1762     if (auto fragment = renderNamedFlowFragment())
1763         fragment->setStyle(RenderNamedFlowFragment::createStyle(style()));
1764
1765     if (diff >= StyleDifferenceRepaint)
1766         invalidateLineLayoutPath();
1767 }
1768
1769 void RenderBlockFlow::styleWillChange(StyleDifference diff, const RenderStyle& newStyle)
1770 {
1771     const RenderStyle* oldStyle = hasInitializedStyle() ? &style() : nullptr;
1772     s_canPropagateFloatIntoSibling = oldStyle ? !isFloatingOrOutOfFlowPositioned() && !avoidsFloats() : false;
1773
1774     if (oldStyle && parent() && diff == StyleDifferenceLayout && oldStyle->position() != newStyle.position()) {
1775         if (containsFloats() && !isFloating() && !isOutOfFlowPositioned() && newStyle.hasOutOfFlowPosition())
1776             markAllDescendantsWithFloatsForLayout();
1777     }
1778
1779     RenderBlock::styleWillChange(diff, newStyle);
1780 }
1781
1782 void RenderBlockFlow::deleteLines()
1783 {
1784     if (containsFloats())
1785         m_floatingObjects->clearLineBoxTreePointers();
1786
1787     if (m_simpleLineLayout) {
1788         ASSERT(!m_lineBoxes.firstLineBox());
1789         m_simpleLineLayout = nullptr;
1790     } else
1791         m_lineBoxes.deleteLineBoxTree(renderArena());
1792
1793     RenderBlock::deleteLines();
1794 }
1795
1796 void RenderBlockFlow::moveAllChildrenIncludingFloatsTo(RenderBlock* toBlock, bool fullRemoveInsert)
1797 {
1798     RenderBlockFlow* toBlockFlow = toRenderBlockFlow(toBlock);
1799     moveAllChildrenTo(toBlockFlow, fullRemoveInsert);
1800
1801     // When a portion of the render tree is being detached, anonymous blocks
1802     // will be combined as their children are deleted. In this process, the
1803     // anonymous block later in the tree is merged into the one preceeding it.
1804     // It can happen that the later block (this) contains floats that the
1805     // previous block (toBlockFlow) did not contain, and thus are not in the
1806     // floating objects list for toBlockFlow. This can result in toBlockFlow
1807     // containing floats that are not in it's floating objects list, but are in
1808     // the floating objects lists of siblings and parents. This can cause
1809     // problems when the float itself is deleted, since the deletion code
1810     // assumes that if a float is not in it's containing block's floating
1811     // objects list, it isn't in any floating objects list. In order to
1812     // preserve this condition (removing it has serious performance
1813     // implications), we need to copy the floating objects from the old block
1814     // (this) to the new block (toBlockFlow). The float's metrics will likely
1815     // all be wrong, but since toBlockFlow is already marked for layout, this
1816     // will get fixed before anything gets displayed.
1817     // See bug https://bugs.webkit.org/show_bug.cgi?id=115566
1818     if (m_floatingObjects) {
1819         if (!toBlockFlow->m_floatingObjects)
1820             toBlockFlow->createFloatingObjects();
1821
1822         const FloatingObjectSet& fromFloatingObjectSet = m_floatingObjects->set();
1823         auto end = fromFloatingObjectSet.end();
1824
1825         for (auto it = fromFloatingObjectSet.begin(); it != end; ++it) {
1826             FloatingObject* floatingObject = it->get();
1827
1828             // Don't insert the object again if it's already in the list
1829             if (toBlockFlow->containsFloat(floatingObject->renderer()))
1830                 continue;
1831
1832             toBlockFlow->m_floatingObjects->add(floatingObject->unsafeClone());
1833         }
1834     }
1835 }
1836
1837 void RenderBlockFlow::addOverflowFromFloats()
1838 {
1839     if (!m_floatingObjects)
1840         return;
1841
1842     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1843     auto end = floatingObjectSet.end();
1844     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1845         FloatingObject* r = it->get();
1846         if (r->isDescendant())
1847             addOverflowFromChild(&r->renderer(), IntSize(xPositionForFloatIncludingMargin(r), yPositionForFloatIncludingMargin(r)));
1848     }
1849 }
1850
1851 void RenderBlockFlow::computeOverflow(LayoutUnit oldClientAfterEdge, bool recomputeFloats)
1852 {
1853     RenderBlock::computeOverflow(oldClientAfterEdge, recomputeFloats);
1854
1855     if (!hasColumns() && (recomputeFloats || isRoot() || expandsToEncloseOverhangingFloats() || hasSelfPaintingLayer()))
1856         addOverflowFromFloats();
1857 }
1858
1859 void RenderBlockFlow::repaintOverhangingFloats(bool paintAllDescendants)
1860 {
1861     // Repaint any overhanging floats (if we know we're the one to paint them).
1862     // Otherwise, bail out.
1863     if (!hasOverhangingFloats())
1864         return;
1865
1866     // FIXME: Avoid disabling LayoutState. At the very least, don't disable it for floats originating
1867     // in this block. Better yet would be to push extra state for the containers of other floats.
1868     LayoutStateDisabler layoutStateDisabler(&view());
1869     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1870     auto end = floatingObjectSet.end();
1871     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1872         FloatingObject* floatingObject = it->get();
1873         // Only repaint the object if it is overhanging, is not in its own layer, and
1874         // is our responsibility to paint (m_shouldPaint is set). When paintAllDescendants is true, the latter
1875         // condition is replaced with being a descendant of us.
1876         if (logicalBottomForFloat(floatingObject) > logicalHeight()
1877             && !floatingObject->renderer().hasSelfPaintingLayer()
1878             && (floatingObject->shouldPaint() || (paintAllDescendants && floatingObject->renderer().isDescendantOf(this)))) {
1879             floatingObject->renderer().repaint();
1880             floatingObject->renderer().repaintOverhangingFloats(false);
1881         }
1882     }
1883 }
1884
1885 void RenderBlockFlow::paintFloats(PaintInfo& paintInfo, const LayoutPoint& paintOffset, bool preservePhase)
1886 {
1887     if (!m_floatingObjects)
1888         return;
1889
1890     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1891     auto end = floatingObjectSet.end();
1892     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1893         FloatingObject* r = it->get();
1894         // Only paint the object if our m_shouldPaint flag is set.
1895         if (r->shouldPaint() && !r->renderer().hasSelfPaintingLayer()) {
1896             PaintInfo currentPaintInfo(paintInfo);
1897             currentPaintInfo.phase = preservePhase ? paintInfo.phase : PaintPhaseBlockBackground;
1898             // FIXME: LayoutPoint version of xPositionForFloatIncludingMargin would make this much cleaner.
1899             LayoutPoint childPoint = flipFloatForWritingModeForChild(r, LayoutPoint(paintOffset.x() + xPositionForFloatIncludingMargin(r) - r->renderer().x(), paintOffset.y() + yPositionForFloatIncludingMargin(r) - r->renderer().y()));
1900             r->renderer().paint(currentPaintInfo, childPoint);
1901             if (!preservePhase) {
1902                 currentPaintInfo.phase = PaintPhaseChildBlockBackgrounds;
1903                 r->renderer().paint(currentPaintInfo, childPoint);
1904                 currentPaintInfo.phase = PaintPhaseFloat;
1905                 r->renderer().paint(currentPaintInfo, childPoint);
1906                 currentPaintInfo.phase = PaintPhaseForeground;
1907                 r->renderer().paint(currentPaintInfo, childPoint);
1908                 currentPaintInfo.phase = PaintPhaseOutline;
1909                 r->renderer().paint(currentPaintInfo, childPoint);
1910             }
1911         }
1912     }
1913 }
1914
1915 void RenderBlockFlow::clipOutFloatingObjects(RenderBlock& rootBlock, const PaintInfo* paintInfo, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock)
1916 {
1917     if (m_floatingObjects) {
1918         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1919         auto end = floatingObjectSet.end();
1920         for (auto it = floatingObjectSet.begin(); it != end; ++it) {
1921             FloatingObject* floatingObject = it->get();
1922             LayoutRect floatBox(offsetFromRootBlock.width() + xPositionForFloatIncludingMargin(floatingObject),
1923                 offsetFromRootBlock.height() + yPositionForFloatIncludingMargin(floatingObject),
1924                 floatingObject->renderer().width(), floatingObject->renderer().height());
1925             rootBlock.flipForWritingMode(floatBox);
1926             floatBox.move(rootBlockPhysicalPosition.x(), rootBlockPhysicalPosition.y());
1927             paintInfo->context->clipOut(pixelSnappedIntRect(floatBox));
1928         }
1929     }
1930 }
1931
1932 void RenderBlockFlow::createFloatingObjects()
1933 {
1934     m_floatingObjects = adoptPtr(new FloatingObjects(this, isHorizontalWritingMode()));
1935 }
1936
1937 void RenderBlockFlow::removeFloatingObjects()
1938 {
1939     if (!m_floatingObjects)
1940         return;
1941
1942     m_floatingObjects->clear();
1943 }
1944
1945 FloatingObject* RenderBlockFlow::insertFloatingObject(RenderBox& floatBox)
1946 {
1947     ASSERT(floatBox.isFloating());
1948
1949     // Create the list of special objects if we don't aleady have one
1950     if (!m_floatingObjects)
1951         createFloatingObjects();
1952     else {
1953         // Don't insert the floatingObject again if it's already in the list
1954         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1955         auto it = floatingObjectSet.find<RenderBox&, FloatingObjectHashTranslator>(floatBox);
1956         if (it != floatingObjectSet.end())
1957             return it->get();
1958     }
1959
1960     // Create the special floatingObject entry & append it to the list
1961
1962     std::unique_ptr<FloatingObject> floatingObject = FloatingObject::create(floatBox);
1963     
1964     // Our location is irrelevant if we're unsplittable or no pagination is in effect.
1965     // Just go ahead and lay out the float.
1966     bool isChildRenderBlock = floatBox.isRenderBlock();
1967     if (isChildRenderBlock && !floatBox.needsLayout() && view().layoutState()->pageLogicalHeightChanged())
1968         floatBox.setChildNeedsLayout(MarkOnlyThis);
1969             
1970     bool needsBlockDirectionLocationSetBeforeLayout = isChildRenderBlock && view().layoutState()->needsBlockDirectionLocationSetBeforeLayout();
1971     if (!needsBlockDirectionLocationSetBeforeLayout || isWritingModeRoot()) // We are unsplittable if we're a block flow root.
1972         floatBox.layoutIfNeeded();
1973     else {
1974         floatBox.updateLogicalWidth();
1975         floatBox.computeAndSetBlockDirectionMargins(this);
1976     }
1977
1978     setLogicalWidthForFloat(floatingObject.get(), logicalWidthForChild(floatBox) + marginStartForChild(floatBox) + marginEndForChild(floatBox));
1979
1980 #if ENABLE(CSS_SHAPES)
1981     if (ShapeOutsideInfo* shapeOutside = floatBox.shapeOutsideInfo())
1982         shapeOutside->setShapeSize(logicalWidthForChild(floatBox), logicalHeightForChild(floatBox));
1983 #endif
1984
1985     return m_floatingObjects->add(std::move(floatingObject));
1986 }
1987
1988 void RenderBlockFlow::removeFloatingObject(RenderBox& floatBox)
1989 {
1990     if (m_floatingObjects) {
1991         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
1992         auto it = floatingObjectSet.find<RenderBox&, FloatingObjectHashTranslator>(floatBox);
1993         if (it != floatingObjectSet.end()) {
1994             FloatingObject* floatingObject = it->get();
1995             if (childrenInline()) {
1996                 LayoutUnit logicalTop = logicalTopForFloat(floatingObject);
1997                 LayoutUnit logicalBottom = logicalBottomForFloat(floatingObject);
1998
1999                 // Fix for https://bugs.webkit.org/show_bug.cgi?id=54995.
2000                 if (logicalBottom < 0 || logicalBottom < logicalTop || logicalTop == LayoutUnit::max())
2001                     logicalBottom = LayoutUnit::max();
2002                 else {
2003                     // Special-case zero- and less-than-zero-height floats: those don't touch
2004                     // the line that they're on, but it still needs to be dirtied. This is
2005                     // accomplished by pretending they have a height of 1.
2006                     logicalBottom = max(logicalBottom, logicalTop + 1);
2007                 }
2008                 if (floatingObject->originatingLine()) {
2009                     if (!selfNeedsLayout()) {
2010                         ASSERT(&floatingObject->originatingLine()->renderer() == this);
2011                         floatingObject->originatingLine()->markDirty();
2012                     }
2013 #if !ASSERT_DISABLED
2014                     floatingObject->setOriginatingLine(0);
2015 #endif
2016                 }
2017                 markLinesDirtyInBlockRange(0, logicalBottom);
2018             }
2019             m_floatingObjects->remove(floatingObject);
2020         }
2021     }
2022 }
2023
2024 void RenderBlockFlow::removeFloatingObjectsBelow(FloatingObject* lastFloat, int logicalOffset)
2025 {
2026     if (!containsFloats())
2027         return;
2028     
2029     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2030     FloatingObject* curr = floatingObjectSet.last().get();
2031     while (curr != lastFloat && (!curr->isPlaced() || logicalTopForFloat(curr) >= logicalOffset)) {
2032         m_floatingObjects->remove(curr);
2033         if (floatingObjectSet.isEmpty())
2034             break;
2035         curr = floatingObjectSet.last().get();
2036     }
2037 }
2038
2039 LayoutPoint RenderBlockFlow::computeLogicalLocationForFloat(const FloatingObject* floatingObject, LayoutUnit logicalTopOffset) const
2040 {
2041     RenderBox& childBox = floatingObject->renderer();
2042     LayoutUnit logicalLeftOffset = logicalLeftOffsetForContent(logicalTopOffset); // Constant part of left offset.
2043     LayoutUnit logicalRightOffset; // Constant part of right offset.
2044 #if ENABLE(CSS_SHAPES)
2045     // FIXME Bug 102948: This only works for shape outside directly set on this block.
2046     ShapeInsideInfo* shapeInsideInfo = this->layoutShapeInsideInfo();
2047     // FIXME: Implement behavior for right floats.
2048     if (shapeInsideInfo) {
2049         LayoutSize floatLogicalSize = logicalSizeForFloat(floatingObject);
2050         // floatingObject's logicalSize doesn't contain the actual height at this point, so we need to calculate it
2051         floatLogicalSize.setHeight(logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
2052
2053         // FIXME: If the float doesn't fit in the shape we should push it under the content box
2054         logicalTopOffset = shapeInsideInfo->computeFirstFitPositionForFloat(floatLogicalSize);
2055         if (logicalHeight() > logicalTopOffset)
2056             logicalTopOffset = logicalHeight();
2057
2058         SegmentList segments = shapeInsideInfo->computeSegmentsForLine(logicalTopOffset, floatLogicalSize.height());
2059         // FIXME Bug 102949: Add support for shapes with multiple segments.
2060         if (segments.size() == 1) {
2061             // The segment offsets are relative to the content box.
2062             logicalRightOffset = logicalLeftOffset + segments[0].logicalRight;
2063             logicalLeftOffset += segments[0].logicalLeft;
2064         }
2065     } else
2066 #endif
2067         logicalRightOffset = logicalRightOffsetForContent(logicalTopOffset);
2068
2069     LayoutUnit floatLogicalWidth = min(logicalWidthForFloat(floatingObject), logicalRightOffset - logicalLeftOffset); // The width we look for.
2070
2071     LayoutUnit floatLogicalLeft;
2072
2073     bool insideFlowThread = flowThreadContainingBlock();
2074
2075     if (childBox.style().floating() == LeftFloat) {
2076         LayoutUnit heightRemainingLeft = 1;
2077         LayoutUnit heightRemainingRight = 1;
2078         floatLogicalLeft = logicalLeftOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalLeftOffset, false, &heightRemainingLeft);
2079         while (logicalRightOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalRightOffset, false, &heightRemainingRight) - floatLogicalLeft < floatLogicalWidth) {
2080             logicalTopOffset += min(heightRemainingLeft, heightRemainingRight);
2081             floatLogicalLeft = logicalLeftOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalLeftOffset, false, &heightRemainingLeft);
2082             if (insideFlowThread) {
2083                 // Have to re-evaluate all of our offsets, since they may have changed.
2084                 logicalRightOffset = logicalRightOffsetForContent(logicalTopOffset); // Constant part of right offset.
2085                 logicalLeftOffset = logicalLeftOffsetForContent(logicalTopOffset); // Constant part of left offset.
2086                 floatLogicalWidth = min(logicalWidthForFloat(floatingObject), logicalRightOffset - logicalLeftOffset);
2087             }
2088         }
2089         floatLogicalLeft = max(logicalLeftOffset - borderAndPaddingLogicalLeft(), floatLogicalLeft);
2090     } else {
2091         LayoutUnit heightRemainingLeft = 1;
2092         LayoutUnit heightRemainingRight = 1;
2093         floatLogicalLeft = logicalRightOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalRightOffset, false, &heightRemainingRight);
2094         while (floatLogicalLeft - logicalLeftOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalLeftOffset, false, &heightRemainingLeft) < floatLogicalWidth) {
2095             logicalTopOffset += min(heightRemainingLeft, heightRemainingRight);
2096             floatLogicalLeft = logicalRightOffsetForLineIgnoringShapeOutside(logicalTopOffset, logicalRightOffset, false, &heightRemainingRight);
2097             if (insideFlowThread) {
2098                 // Have to re-evaluate all of our offsets, since they may have changed.
2099                 logicalRightOffset = logicalRightOffsetForContent(logicalTopOffset); // Constant part of right offset.
2100                 logicalLeftOffset = logicalLeftOffsetForContent(logicalTopOffset); // Constant part of left offset.
2101                 floatLogicalWidth = min(logicalWidthForFloat(floatingObject), logicalRightOffset - logicalLeftOffset);
2102             }
2103         }
2104         // Use the original width of the float here, since the local variable
2105         // |floatLogicalWidth| was capped to the available line width. See
2106         // fast/block/float/clamped-right-float.html.
2107         floatLogicalLeft -= logicalWidthForFloat(floatingObject);
2108     }
2109     
2110     return LayoutPoint(floatLogicalLeft, logicalTopOffset);
2111 }
2112
2113 bool RenderBlockFlow::positionNewFloats()
2114 {
2115     if (!m_floatingObjects)
2116         return false;
2117
2118     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2119     if (floatingObjectSet.isEmpty())
2120         return false;
2121
2122     // If all floats have already been positioned, then we have no work to do.
2123     if (floatingObjectSet.last()->isPlaced())
2124         return false;
2125
2126     // Move backwards through our floating object list until we find a float that has
2127     // already been positioned. Then we'll be able to move forward, positioning all of
2128     // the new floats that need it.
2129     auto it = floatingObjectSet.end();
2130     --it; // Go to last item.
2131     auto begin = floatingObjectSet.begin();
2132     FloatingObject* lastPlacedFloatingObject = 0;
2133     while (it != begin) {
2134         --it;
2135         if ((*it)->isPlaced()) {
2136             lastPlacedFloatingObject = it->get();
2137             ++it;
2138             break;
2139         }
2140     }
2141
2142     LayoutUnit logicalTop = logicalHeight();
2143     
2144     // The float cannot start above the top position of the last positioned float.
2145     if (lastPlacedFloatingObject)
2146         logicalTop = max(logicalTopForFloat(lastPlacedFloatingObject), logicalTop);
2147
2148     auto end = floatingObjectSet.end();
2149     // Now walk through the set of unpositioned floats and place them.
2150     for (; it != end; ++it) {
2151         FloatingObject* floatingObject = it->get();
2152         // The containing block is responsible for positioning floats, so if we have floats in our
2153         // list that come from somewhere else, do not attempt to position them.
2154         if (floatingObject->renderer().containingBlock() != this)
2155             continue;
2156
2157         RenderBox& childBox = floatingObject->renderer();
2158
2159         LayoutUnit childLogicalLeftMargin = style().isLeftToRightDirection() ? marginStartForChild(childBox) : marginEndForChild(childBox);
2160
2161         LayoutRect oldRect = childBox.frameRect();
2162
2163         if (childBox.style().clear() & CLEFT)
2164             logicalTop = max(lowestFloatLogicalBottom(FloatingObject::FloatLeft), logicalTop);
2165         if (childBox.style().clear() & CRIGHT)
2166             logicalTop = max(lowestFloatLogicalBottom(FloatingObject::FloatRight), logicalTop);
2167
2168         LayoutPoint floatLogicalLocation = computeLogicalLocationForFloat(floatingObject, logicalTop);
2169
2170         setLogicalLeftForFloat(floatingObject, floatLogicalLocation.x());
2171
2172         setLogicalLeftForChild(childBox, floatLogicalLocation.x() + childLogicalLeftMargin);
2173         setLogicalTopForChild(childBox, floatLogicalLocation.y() + marginBeforeForChild(childBox));
2174
2175         estimateRegionRangeForBoxChild(childBox);
2176
2177         LayoutState* layoutState = view().layoutState();
2178         bool isPaginated = layoutState->isPaginated();
2179         if (isPaginated && !childBox.needsLayout())
2180             childBox.markForPaginationRelayoutIfNeeded();
2181         
2182         childBox.layoutIfNeeded();
2183
2184         if (isPaginated) {
2185             // If we are unsplittable and don't fit, then we need to move down.
2186             // We include our margins as part of the unsplittable area.
2187             LayoutUnit newLogicalTop = adjustForUnsplittableChild(childBox, floatLogicalLocation.y(), true);
2188             
2189             // See if we have a pagination strut that is making us move down further.
2190             // Note that an unsplittable child can't also have a pagination strut, so this is
2191             // exclusive with the case above.
2192             RenderBlock* childBlock = childBox.isRenderBlock() ? toRenderBlock(&childBox) : nullptr;
2193             if (childBlock && childBlock->paginationStrut()) {
2194                 newLogicalTop += childBlock->paginationStrut();
2195                 childBlock->setPaginationStrut(0);
2196             }
2197             
2198             if (newLogicalTop != floatLogicalLocation.y()) {
2199                 floatingObject->setPaginationStrut(newLogicalTop - floatLogicalLocation.y());
2200
2201                 floatLogicalLocation = computeLogicalLocationForFloat(floatingObject, newLogicalTop);
2202                 setLogicalLeftForFloat(floatingObject, floatLogicalLocation.x());
2203
2204                 setLogicalLeftForChild(childBox, floatLogicalLocation.x() + childLogicalLeftMargin);
2205                 setLogicalTopForChild(childBox, floatLogicalLocation.y() + marginBeforeForChild(childBox));
2206         
2207                 if (childBlock)
2208                     childBlock->setChildNeedsLayout(MarkOnlyThis);
2209                 childBox.layoutIfNeeded();
2210             }
2211
2212             if (updateRegionRangeForBoxChild(childBox)) {
2213                 childBox.setNeedsLayout(MarkOnlyThis);
2214                 childBox.layoutIfNeeded();
2215             }
2216         }
2217
2218         setLogicalTopForFloat(floatingObject, floatLogicalLocation.y());
2219
2220         setLogicalHeightForFloat(floatingObject, logicalHeightForChild(childBox) + marginBeforeForChild(childBox) + marginAfterForChild(childBox));
2221
2222         m_floatingObjects->addPlacedObject(floatingObject);
2223
2224         // If the child moved, we have to repaint it.
2225         if (childBox.checkForRepaintDuringLayout())
2226             childBox.repaintDuringLayoutIfMoved(oldRect);
2227     }
2228     return true;
2229 }
2230
2231 void RenderBlockFlow::newLine(EClear clear)
2232 {
2233     positionNewFloats();
2234     // set y position
2235     LayoutUnit newY = 0;
2236     switch (clear) {
2237     case CLEFT:
2238         newY = lowestFloatLogicalBottom(FloatingObject::FloatLeft);
2239         break;
2240     case CRIGHT:
2241         newY = lowestFloatLogicalBottom(FloatingObject::FloatRight);
2242         break;
2243     case CBOTH:
2244         newY = lowestFloatLogicalBottom();
2245     default:
2246         break;
2247     }
2248     if (height() < newY)
2249         setLogicalHeight(newY);
2250 }
2251
2252 LayoutUnit RenderBlockFlow::logicalLeftFloatOffsetForLine(LayoutUnit logicalTop, LayoutUnit fixedOffset, LayoutUnit* heightRemaining, LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode) const
2253 {
2254     if (m_floatingObjects && m_floatingObjects->hasLeftObjects())
2255         return m_floatingObjects->logicalLeftOffset(fixedOffset, logicalTop, logicalHeight, offsetMode, heightRemaining);
2256
2257     return fixedOffset;
2258 }
2259
2260 LayoutUnit RenderBlockFlow::logicalRightFloatOffsetForLine(LayoutUnit logicalTop, LayoutUnit fixedOffset, LayoutUnit* heightRemaining, LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode) const
2261 {
2262     if (m_floatingObjects && m_floatingObjects->hasRightObjects())
2263         return m_floatingObjects->logicalRightOffset(fixedOffset, logicalTop, logicalHeight, offsetMode, heightRemaining);
2264
2265     return fixedOffset;
2266 }
2267
2268 LayoutUnit RenderBlockFlow::nextFloatLogicalBottomBelow(LayoutUnit logicalHeight, ShapeOutsideFloatOffsetMode offsetMode) const
2269 {
2270     if (!m_floatingObjects)
2271         return logicalHeight;
2272
2273     LayoutUnit bottom = LayoutUnit::max();
2274     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2275     auto end = floatingObjectSet.end();
2276     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2277         FloatingObject* floatingObject = it->get();
2278         LayoutUnit floatBottom = logicalBottomForFloat(floatingObject);
2279 #if ENABLE(CSS_SHAPES)
2280         ShapeOutsideInfo* shapeOutside = floatingObject->renderer().shapeOutsideInfo();
2281         if (offsetMode == ShapeOutsideFloatShapeOffset && shapeOutside) {
2282             LayoutUnit shapeBottom = logicalTopForFloat(floatingObject) + marginBeforeForChild(floatingObject->renderer()) + shapeOutside->shapeLogicalBottom();
2283             // Use the shapeBottom unless it extends outside of the margin box, in which case it is clipped.
2284             if (shapeBottom < floatBottom)
2285                 floatBottom = shapeBottom;
2286         }
2287 #endif
2288         if (floatBottom > logicalHeight)
2289             bottom = min(floatBottom, bottom);
2290     }
2291
2292     return bottom == LayoutUnit::max() ? LayoutUnit() : bottom;
2293 }
2294
2295 LayoutUnit RenderBlockFlow::lowestFloatLogicalBottom(FloatingObject::Type floatType) const
2296 {
2297     if (!m_floatingObjects)
2298         return 0;
2299     LayoutUnit lowestFloatBottom = 0;
2300     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2301     auto end = floatingObjectSet.end();
2302     for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2303         FloatingObject* floatingObject = it->get();
2304         if (floatingObject->isPlaced() && floatingObject->type() & floatType)
2305             lowestFloatBottom = max(lowestFloatBottom, logicalBottomForFloat(floatingObject));
2306     }
2307     return lowestFloatBottom;
2308 }
2309
2310 LayoutUnit RenderBlockFlow::addOverhangingFloats(RenderBlockFlow& child, bool makeChildPaintOtherFloats)
2311 {
2312     // Prevent floats from being added to the canvas by the root element, e.g., <html>.
2313     if (child.hasOverflowClip() || !child.containsFloats() || child.isRoot() || child.hasColumns() || child.isWritingModeRoot())
2314         return 0;
2315
2316     LayoutUnit childLogicalTop = child.logicalTop();
2317     LayoutUnit childLogicalLeft = child.logicalLeft();
2318     LayoutUnit lowestFloatLogicalBottom = 0;
2319
2320     // Floats that will remain the child's responsibility to paint should factor into its
2321     // overflow.
2322     auto childEnd = child.m_floatingObjects->set().end();
2323     for (auto childIt = child.m_floatingObjects->set().begin(); childIt != childEnd; ++childIt) {
2324         FloatingObject* floatingObject = childIt->get();
2325         LayoutUnit floatLogicalBottom = min(logicalBottomForFloat(floatingObject), LayoutUnit::max() - childLogicalTop);
2326         LayoutUnit logicalBottom = childLogicalTop + floatLogicalBottom;
2327         lowestFloatLogicalBottom = max(lowestFloatLogicalBottom, logicalBottom);
2328
2329         if (logicalBottom > logicalHeight()) {
2330             // If the object is not in the list, we add it now.
2331             if (!containsFloat(floatingObject->renderer())) {
2332                 LayoutSize offset = isHorizontalWritingMode() ? LayoutSize(-childLogicalLeft, -childLogicalTop) : LayoutSize(-childLogicalTop, -childLogicalLeft);
2333                 bool shouldPaint = false;
2334
2335                 // The nearest enclosing layer always paints the float (so that zindex and stacking
2336                 // behaves properly). We always want to propagate the desire to paint the float as
2337                 // far out as we can, to the outermost block that overlaps the float, stopping only
2338                 // if we hit a self-painting layer boundary.
2339                 if (floatingObject->renderer().enclosingFloatPaintingLayer() == enclosingFloatPaintingLayer()) {
2340                     floatingObject->setShouldPaint(false);
2341                     shouldPaint = true;
2342                 }
2343                 // We create the floating object list lazily.
2344                 if (!m_floatingObjects)
2345                     createFloatingObjects();
2346
2347                 m_floatingObjects->add(floatingObject->copyToNewContainer(offset, shouldPaint, true));
2348             }
2349         } else {
2350             if (makeChildPaintOtherFloats && !floatingObject->shouldPaint() && !floatingObject->renderer().hasSelfPaintingLayer()
2351                 && floatingObject->renderer().isDescendantOf(&child) && floatingObject->renderer().enclosingFloatPaintingLayer() == child.enclosingFloatPaintingLayer()) {
2352                 // The float is not overhanging from this block, so if it is a descendant of the child, the child should
2353                 // paint it (the other case is that it is intruding into the child), unless it has its own layer or enclosing
2354                 // layer.
2355                 // If makeChildPaintOtherFloats is false, it means that the child must already know about all the floats
2356                 // it should paint.
2357                 floatingObject->setShouldPaint(true);
2358             }
2359             
2360             // 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
2361             // child now.
2362             if (floatingObject->isDescendant())
2363                 child.addOverflowFromChild(&floatingObject->renderer(), LayoutSize(xPositionForFloatIncludingMargin(floatingObject), yPositionForFloatIncludingMargin(floatingObject)));
2364         }
2365     }
2366     return lowestFloatLogicalBottom;
2367 }
2368
2369 bool RenderBlockFlow::hasOverhangingFloat(RenderBox& renderer)
2370 {
2371     if (!m_floatingObjects || hasColumns() || !parent())
2372         return false;
2373
2374     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2375     auto it = floatingObjectSet.find<RenderBox&, FloatingObjectHashTranslator>(renderer);
2376     if (it == floatingObjectSet.end())
2377         return false;
2378
2379     return logicalBottomForFloat(it->get()) > logicalHeight();
2380 }
2381
2382 void RenderBlockFlow::addIntrudingFloats(RenderBlockFlow* prev, LayoutUnit logicalLeftOffset, LayoutUnit logicalTopOffset)
2383 {
2384     ASSERT(!avoidsFloats());
2385
2386     // If the parent or previous sibling doesn't have any floats to add, don't bother.
2387     if (!prev->m_floatingObjects)
2388         return;
2389
2390     logicalLeftOffset += marginLogicalLeft();
2391
2392     const FloatingObjectSet& prevSet = prev->m_floatingObjects->set();
2393     auto prevEnd = prevSet.end();
2394     for (auto prevIt = prevSet.begin(); prevIt != prevEnd; ++prevIt) {
2395         FloatingObject* floatingObject = prevIt->get();
2396         if (logicalBottomForFloat(floatingObject) > logicalTopOffset) {
2397             if (!m_floatingObjects || !m_floatingObjects->set().contains<FloatingObject&, FloatingObjectHashTranslator>(*floatingObject)) {
2398                 // We create the floating object list lazily.
2399                 if (!m_floatingObjects)
2400                     createFloatingObjects();
2401
2402                 // Applying the child's margin makes no sense in the case where the child was passed in.
2403                 // since this margin was added already through the modification of the |logicalLeftOffset| variable
2404                 // above. |logicalLeftOffset| will equal the margin in this case, so it's already been taken
2405                 // into account. Only apply this code if prev is the parent, since otherwise the left margin
2406                 // will get applied twice.
2407                 LayoutSize offset = isHorizontalWritingMode()
2408                     ? LayoutSize(logicalLeftOffset - (prev != parent() ? prev->marginLeft() : LayoutUnit()), logicalTopOffset)
2409                     : LayoutSize(logicalTopOffset, logicalLeftOffset - (prev != parent() ? prev->marginTop() : LayoutUnit()));
2410
2411                 m_floatingObjects->add(floatingObject->copyToNewContainer(offset));
2412             }
2413         }
2414     }
2415 }
2416
2417 void RenderBlockFlow::markAllDescendantsWithFloatsForLayout(RenderBox* floatToRemove, bool inLayout)
2418 {
2419     if (!everHadLayout() && !containsFloats())
2420         return;
2421
2422     MarkingBehavior markParents = inLayout ? MarkOnlyThis : MarkContainingBlockChain;
2423     setChildNeedsLayout(markParents);
2424
2425     if (floatToRemove)
2426         removeFloatingObject(*floatToRemove);
2427
2428     // Iterate over our children and mark them as needed.
2429     if (!childrenInline()) {
2430         for (RenderObject* child = firstChild(); child; child = child->nextSibling()) {
2431             if ((!floatToRemove && child->isFloatingOrOutOfFlowPositioned()) || !child->isRenderBlock())
2432                 continue;
2433             if (!child->isRenderBlockFlow()) {
2434                 RenderBlock* childBlock = toRenderBlock(child);
2435                 if (childBlock->shrinkToAvoidFloats() && childBlock->everHadLayout())
2436                     childBlock->setChildNeedsLayout(markParents);
2437                 continue;
2438             }
2439             RenderBlockFlow* childBlock = toRenderBlockFlow(child);
2440             if ((floatToRemove ? childBlock->containsFloat(*floatToRemove) : childBlock->containsFloats()) || childBlock->shrinkToAvoidFloats())
2441                 childBlock->markAllDescendantsWithFloatsForLayout(floatToRemove, inLayout);
2442         }
2443     }
2444 }
2445
2446 void RenderBlockFlow::markSiblingsWithFloatsForLayout(RenderBox* floatToRemove)
2447 {
2448     if (!m_floatingObjects)
2449         return;
2450
2451     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2452     auto end = floatingObjectSet.end();
2453
2454     for (RenderObject* next = nextSibling(); next; next = next->nextSibling()) {
2455         if (!next->isRenderBlockFlow() || next->isFloatingOrOutOfFlowPositioned() || toRenderBlock(next)->avoidsFloats())
2456             continue;
2457
2458         RenderBlockFlow* nextBlock = toRenderBlockFlow(next);
2459         for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2460             RenderBox& floatingBox = (*it)->renderer();
2461             if (floatToRemove && &floatingBox != floatToRemove)
2462                 continue;
2463             if (nextBlock->containsFloat(floatingBox))
2464                 nextBlock->markAllDescendantsWithFloatsForLayout(&floatingBox);
2465         }
2466     }
2467 }
2468
2469 LayoutPoint RenderBlockFlow::flipFloatForWritingModeForChild(const FloatingObject* child, const LayoutPoint& point) const
2470 {
2471     if (!style().isFlippedBlocksWritingMode())
2472         return point;
2473     
2474     // This is similar to RenderBox::flipForWritingModeForChild. We have to subtract out our left/top offsets twice, since
2475     // it's going to get added back in. We hide this complication here so that the calling code looks normal for the unflipped
2476     // case.
2477     if (isHorizontalWritingMode())
2478         return LayoutPoint(point.x(), point.y() + height() - child->renderer().height() - 2 * yPositionForFloatIncludingMargin(child));
2479     return LayoutPoint(point.x() + width() - child->renderer().width() - 2 * xPositionForFloatIncludingMargin(child), point.y());
2480 }
2481
2482 LayoutUnit RenderBlockFlow::getClearDelta(RenderBox& child, LayoutUnit logicalTop)
2483 {
2484     // There is no need to compute clearance if we have no floats.
2485     if (!containsFloats())
2486         return 0;
2487     
2488     // At least one float is present. We need to perform the clearance computation.
2489     bool clearSet = child.style().clear() != CNONE;
2490     LayoutUnit logicalBottom = 0;
2491     switch (child.style().clear()) {
2492     case CNONE:
2493         break;
2494     case CLEFT:
2495         logicalBottom = lowestFloatLogicalBottom(FloatingObject::FloatLeft);
2496         break;
2497     case CRIGHT:
2498         logicalBottom = lowestFloatLogicalBottom(FloatingObject::FloatRight);
2499         break;
2500     case CBOTH:
2501         logicalBottom = lowestFloatLogicalBottom();
2502         break;
2503     }
2504
2505     // 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).
2506     LayoutUnit result = clearSet ? max<LayoutUnit>(0, logicalBottom - logicalTop) : LayoutUnit();
2507     if (!result && child.avoidsFloats()) {
2508         LayoutUnit newLogicalTop = logicalTop;
2509         while (true) {
2510             LayoutUnit availableLogicalWidthAtNewLogicalTopOffset = availableLogicalWidthForLine(newLogicalTop, false, logicalHeightForChild(child));
2511             if (availableLogicalWidthAtNewLogicalTopOffset == availableLogicalWidthForContent(newLogicalTop))
2512                 return newLogicalTop - logicalTop;
2513
2514             RenderRegion* region = regionAtBlockOffset(logicalTopForChild(child));
2515             LayoutRect borderBox = child.borderBoxRectInRegion(region, DoNotCacheRenderBoxRegionInfo);
2516             LayoutUnit childLogicalWidthAtOldLogicalTopOffset = isHorizontalWritingMode() ? borderBox.width() : borderBox.height();
2517
2518             // FIXME: None of this is right for perpendicular writing-mode children.
2519             LayoutUnit childOldLogicalWidth = child.logicalWidth();
2520             LayoutUnit childOldMarginLeft = child.marginLeft();
2521             LayoutUnit childOldMarginRight = child.marginRight();
2522             LayoutUnit childOldLogicalTop = child.logicalTop();
2523
2524             child.setLogicalTop(newLogicalTop);
2525             child.updateLogicalWidth();
2526             region = regionAtBlockOffset(logicalTopForChild(child));
2527             borderBox = child.borderBoxRectInRegion(region, DoNotCacheRenderBoxRegionInfo);
2528             LayoutUnit childLogicalWidthAtNewLogicalTopOffset = isHorizontalWritingMode() ? borderBox.width() : borderBox.height();
2529
2530             child.setLogicalTop(childOldLogicalTop);
2531             child.setLogicalWidth(childOldLogicalWidth);
2532             child.setMarginLeft(childOldMarginLeft);
2533             child.setMarginRight(childOldMarginRight);
2534             
2535             if (childLogicalWidthAtNewLogicalTopOffset <= availableLogicalWidthAtNewLogicalTopOffset) {
2536                 // Even though we may not be moving, if the logical width did shrink because of the presence of new floats, then
2537                 // we need to force a relayout as though we shifted. This happens because of the dynamic addition of overhanging floats
2538                 // from previous siblings when negative margins exist on a child (see the addOverhangingFloats call at the end of collapseMargins).
2539                 if (childLogicalWidthAtOldLogicalTopOffset != childLogicalWidthAtNewLogicalTopOffset)
2540                     child.setChildNeedsLayout(MarkOnlyThis);
2541                 return newLogicalTop - logicalTop;
2542             }
2543
2544             newLogicalTop = nextFloatLogicalBottomBelow(newLogicalTop);
2545             ASSERT(newLogicalTop >= logicalTop);
2546             if (newLogicalTop < logicalTop)
2547                 break;
2548         }
2549         ASSERT_NOT_REACHED();
2550     }
2551     return result;
2552 }
2553
2554 bool RenderBlockFlow::hitTestFloats(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset)
2555 {
2556     if (!m_floatingObjects)
2557         return false;
2558
2559     LayoutPoint adjustedLocation = accumulatedOffset;
2560     if (isRenderView())
2561         adjustedLocation += toLayoutSize(toRenderView(*this).frameView().scrollPosition());
2562
2563     const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2564     auto begin = floatingObjectSet.begin();
2565     for (auto it = floatingObjectSet.end(); it != begin;) {
2566         --it;
2567         FloatingObject* floatingObject = it->get();
2568         if (floatingObject->shouldPaint() && !floatingObject->renderer().hasSelfPaintingLayer()) {
2569             LayoutUnit xOffset = xPositionForFloatIncludingMargin(floatingObject) - floatingObject->renderer().x();
2570             LayoutUnit yOffset = yPositionForFloatIncludingMargin(floatingObject) - floatingObject->renderer().y();
2571             LayoutPoint childPoint = flipFloatForWritingModeForChild(floatingObject, adjustedLocation + LayoutSize(xOffset, yOffset));
2572             if (floatingObject->renderer().hitTest(request, result, locationInContainer, childPoint)) {
2573                 updateHitTestResult(result, locationInContainer.point() - toLayoutSize(childPoint));
2574                 return true;
2575             }
2576         }
2577     }
2578
2579     return false;
2580 }
2581
2582 bool RenderBlockFlow::hitTestInlineChildren(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction)
2583 {
2584     ASSERT(childrenInline());
2585
2586     if (m_simpleLineLayout)
2587         return SimpleLineLayout::hitTestFlow(*this, *m_simpleLineLayout, request, result, locationInContainer, accumulatedOffset, hitTestAction);
2588
2589     return m_lineBoxes.hitTest(this, request, result, locationInContainer, accumulatedOffset, hitTestAction);
2590 }
2591
2592 void RenderBlockFlow::adjustForBorderFit(LayoutUnit x, LayoutUnit& left, LayoutUnit& right) const
2593 {
2594     if (style().visibility() != VISIBLE)
2595         return;
2596
2597     // We don't deal with relative positioning.  Our assumption is that you shrink to fit the lines without accounting
2598     // for either overflow or translations via relative positioning.
2599     if (childrenInline()) {
2600         const_cast<RenderBlockFlow&>(*this).ensureLineBoxes();
2601
2602         for (auto box = firstRootBox(); box; box = box->nextRootBox()) {
2603             if (box->firstChild())
2604                 left = min(left, x + static_cast<LayoutUnit>(box->firstChild()->x()));
2605             if (box->lastChild())
2606                 right = max(right, x + static_cast<LayoutUnit>(ceilf(box->lastChild()->logicalRight())));
2607         }
2608     } else {
2609         for (RenderBox* obj = firstChildBox(); obj; obj = obj->nextSiblingBox()) {
2610             if (!obj->isFloatingOrOutOfFlowPositioned()) {
2611                 if (obj->isRenderBlockFlow() && !obj->hasOverflowClip())
2612                     toRenderBlockFlow(obj)->adjustForBorderFit(x + obj->x(), left, right);
2613                 else if (obj->style().visibility() == VISIBLE) {
2614                     // We are a replaced element or some kind of non-block-flow object.
2615                     left = min(left, x + obj->x());
2616                     right = max(right, x + obj->x() + obj->width());
2617                 }
2618             }
2619         }
2620     }
2621
2622     if (m_floatingObjects) {
2623         const FloatingObjectSet& floatingObjectSet = m_floatingObjects->set();
2624         auto end = floatingObjectSet.end();
2625         for (auto it = floatingObjectSet.begin(); it != end; ++it) {
2626             FloatingObject* r = it->get();
2627             // Only examine the object if our m_shouldPaint flag is set.
2628             if (r->shouldPaint()) {
2629                 LayoutUnit floatLeft = xPositionForFloatIncludingMargin(r) - r->renderer().x();
2630                 LayoutUnit floatRight = floatLeft + r->renderer().width();
2631                 left = min(left, floatLeft);
2632                 right = max(right, floatRight);
2633             }
2634         }
2635     }
2636 }
2637
2638 void RenderBlockFlow::fitBorderToLinesIfNeeded()
2639 {
2640     if (style().borderFit() == BorderFitBorder || hasOverrideWidth())
2641         return;
2642
2643     // Walk any normal flow lines to snugly fit.
2644     LayoutUnit left = LayoutUnit::max();
2645     LayoutUnit right = LayoutUnit::min();
2646     LayoutUnit oldWidth = contentWidth();
2647     adjustForBorderFit(0, left, right);
2648     
2649     // Clamp to our existing edges. We can never grow. We only shrink.
2650     LayoutUnit leftEdge = borderLeft() + paddingLeft();
2651     LayoutUnit rightEdge = leftEdge + oldWidth;
2652     left = min(rightEdge, max(leftEdge, left));
2653     right = max(leftEdge, min(rightEdge, right));
2654     
2655     LayoutUnit newContentWidth = right - left;
2656     if (newContentWidth == oldWidth)
2657         return;
2658     
2659     setOverrideLogicalContentWidth(newContentWidth);
2660     layoutBlock(false);
2661     clearOverrideLogicalContentWidth();
2662 }
2663
2664 void RenderBlockFlow::markLinesDirtyInBlockRange(LayoutUnit logicalTop, LayoutUnit logicalBottom, RootInlineBox* highest)
2665 {
2666     if (logicalTop >= logicalBottom)
2667         return;
2668
2669     RootInlineBox* lowestDirtyLine = lastRootBox();
2670     RootInlineBox* afterLowest = lowestDirtyLine;
2671     while (lowestDirtyLine && lowestDirtyLine->lineBottomWithLeading() >= logicalBottom && logicalBottom < LayoutUnit::max()) {
2672         afterLowest = lowestDirtyLine;
2673         lowestDirtyLine = lowestDirtyLine->prevRootBox();
2674     }
2675
2676     while (afterLowest && afterLowest != highest && (afterLowest->lineBottomWithLeading() >= logicalTop || afterLowest->lineBottomWithLeading() < 0)) {
2677         afterLowest->markDirty();
2678         afterLowest = afterLowest->prevRootBox();
2679     }
2680 }
2681
2682 int RenderBlockFlow::firstLineBaseline() const
2683 {
2684     if (isWritingModeRoot() && !isRubyRun())
2685         return -1;
2686
2687     if (!childrenInline())
2688         return RenderBlock::firstLineBaseline();
2689
2690     if (!hasLines())
2691         return -1;
2692
2693     if (m_simpleLineLayout)
2694         return SimpleLineLayout::computeFlowFirstLineBaseline(*this, *m_simpleLineLayout);
2695
2696     ASSERT(firstLineBox());
2697     return firstLineBox()->logicalTop() + firstLineStyle().fontMetrics().ascent(firstRootBox()->baselineType());
2698 }
2699
2700 int RenderBlockFlow::inlineBlockBaseline(LineDirectionMode lineDirection) const
2701 {
2702     if (isWritingModeRoot() && !isRubyRun())
2703         return -1;
2704
2705     if (!childrenInline())
2706         return RenderBlock::inlineBlockBaseline(lineDirection);
2707
2708     if (!hasLines()) {
2709         if (!hasLineIfEmpty())
2710             return -1;
2711         const FontMetrics& fontMetrics = firstLineStyle().fontMetrics();
2712         return fontMetrics.ascent()
2713              + (lineHeight(true, lineDirection, PositionOfInteriorLineBoxes) - fontMetrics.height()) / 2
2714              + (lineDirection == HorizontalLine ? borderTop() + paddingTop() : borderRight() + paddingRight());
2715     }
2716
2717     if (m_simpleLineLayout)
2718         return SimpleLineLayout::computeFlowLastLineBaseline(*this, *m_simpleLineLayout);
2719
2720     bool isFirstLine = lastLineBox() == firstLineBox();
2721     const RenderStyle& style = isFirstLine ? firstLineStyle() : this->style();
2722     return lastLineBox()->logicalTop() + style.fontMetrics().ascent(lastRootBox()->baselineType());
2723 }
2724
2725 GapRects RenderBlockFlow::inlineSelectionGaps(RenderBlock& rootBlock, const LayoutPoint& rootBlockPhysicalPosition, const LayoutSize& offsetFromRootBlock,
2726     LayoutUnit& lastLogicalTop, LayoutUnit& lastLogicalLeft, LayoutUnit& lastLogicalRight, const LogicalSelectionOffsetCaches& cache, const PaintInfo* paintInfo)
2727 {
2728     ASSERT(!m_simpleLineLayout);
2729
2730     GapRects result;
2731
2732     bool containsStart = selectionState() == SelectionStart || selectionState() == SelectionBoth;
2733
2734     if (!hasLines()) {
2735         if (containsStart) {
2736             // Go ahead and update our lastLogicalTop to be the bottom of the block.  <hr>s or empty blocks with height can trip this
2737             // case.
2738             lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + logicalHeight();
2739             lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, logicalHeight(), cache);
2740             lastLogicalRight = logicalRightSelectionOffset(rootBlock, logicalHeight(), cache);
2741         }
2742         return result;
2743     }
2744
2745     RootInlineBox* lastSelectedLine = 0;
2746     RootInlineBox* curr;
2747     for (curr = firstRootBox(); curr && !curr->hasSelectedChildren(); curr = curr->nextRootBox()) { }
2748
2749     // Now paint the gaps for the lines.
2750     for (; curr && curr->hasSelectedChildren(); curr = curr->nextRootBox()) {
2751         LayoutUnit selTop =  curr->selectionTopAdjustedForPrecedingBlock();
2752         LayoutUnit selHeight = curr->selectionHeightAdjustedForPrecedingBlock();
2753
2754         if (!containsStart && !lastSelectedLine &&
2755             selectionState() != SelectionStart && selectionState() != SelectionBoth)
2756             result.uniteCenter(blockSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, lastLogicalTop, lastLogicalLeft, lastLogicalRight, selTop, cache, paintInfo));
2757         
2758         LayoutRect logicalRect(curr->logicalLeft(), selTop, curr->logicalWidth(), selTop + selHeight);
2759         logicalRect.move(isHorizontalWritingMode() ? offsetFromRootBlock : offsetFromRootBlock.transposedSize());
2760         LayoutRect physicalRect = rootBlock.logicalRectToPhysicalRect(rootBlockPhysicalPosition, logicalRect);
2761         if (!paintInfo || (isHorizontalWritingMode() && physicalRect.y() < paintInfo->rect.maxY() && physicalRect.maxY() > paintInfo->rect.y())
2762             || (!isHorizontalWritingMode() && physicalRect.x() < paintInfo->rect.maxX() && physicalRect.maxX() > paintInfo->rect.x()))
2763             result.unite(curr->lineSelectionGap(rootBlock, rootBlockPhysicalPosition, offsetFromRootBlock, selTop, selHeight, cache, paintInfo));
2764
2765         lastSelectedLine = curr;
2766     }
2767
2768     if (containsStart && !lastSelectedLine)
2769         // VisibleSelection must start just after our last line.
2770         lastSelectedLine = lastRootBox();
2771
2772     if (lastSelectedLine && selectionState() != SelectionEnd && selectionState() != SelectionBoth) {
2773         // Go ahead and update our lastY to be the bottom of the last selected line.
2774         lastLogicalTop = blockDirectionOffset(rootBlock, offsetFromRootBlock) + lastSelectedLine->selectionBottom();
2775         lastLogicalLeft = logicalLeftSelectionOffset(rootBlock, lastSelectedLine->selectionBottom(), cache);
2776         lastLogicalRight = logicalRightSelectionOffset(rootBlock, lastSelectedLine->selectionBottom(), cache);
2777     }
2778     return result;
2779 }
2780
2781 void RenderBlockFlow::createRenderNamedFlowFragmentIfNeeded()
2782 {
2783     if (!document().cssRegionsEnabled() || renderNamedFlowFragment() || isRenderNamedFlowFragment())
2784         return;
2785
2786     if (style().isDisplayRegionType() && style().hasFlowFrom()) {
2787         RenderNamedFlowFragment* flowFragment = new RenderNamedFlowFragment(document(), RenderNamedFlowFragment::createStyle(style()));
2788         flowFragment->initializeStyle();
2789         setRenderNamedFlowFragment(flowFragment);
2790         addChild(renderNamedFlowFragment());
2791     }
2792 }
2793
2794 bool RenderBlockFlow::canHaveChildren() const
2795 {
2796     return !renderNamedFlowFragment() ? RenderBlock::canHaveChildren() : renderNamedFlowFragment()->canHaveChildren();
2797 }
2798
2799 bool RenderBlockFlow::canHaveGeneratedChildren() const
2800 {
2801     return !renderNamedFlowFragment() ? RenderBlock::canHaveGeneratedChildren() : renderNamedFlowFragment()->canHaveGeneratedChildren();
2802 }
2803
2804 bool RenderBlockFlow::namedFlowFragmentNeedsUpdate() const
2805 {
2806     if (!isRenderNamedFlowFragmentContainer())
2807         return false;
2808
2809     return hasRelativeLogicalHeight() && !isRenderView();
2810 }
2811
2812 void RenderBlockFlow::updateLogicalHeight()
2813 {
2814     RenderBlock::updateLogicalHeight();
2815
2816     if (renderNamedFlowFragment())
2817         renderNamedFlowFragment()->setLogicalHeight(max<LayoutUnit>(0, logicalHeight() - borderAndPaddingLogicalHeight()));
2818 }
2819
2820 void RenderBlockFlow::setRenderNamedFlowFragment(RenderNamedFlowFragment* flowFragment)
2821 {
2822     RenderBlockFlowRareData& rareData = ensureRareData();
2823     if (rareData.m_renderNamedFlowFragment)
2824         rareData.m_renderNamedFlowFragment->destroy();
2825     rareData.m_renderNamedFlowFragment = flowFragment;
2826 }
2827
2828 // FIXME: Use this function in more places.
2829 RenderBlockFlow::RenderBlockFlowRareData& RenderBlockFlow::ensureRareData()
2830 {
2831     if (m_rareData)
2832         return *m_rareData;
2833
2834     m_rareData = adoptPtr(new RenderBlockFlowRareData(*this));
2835     return *m_rareData;
2836 }
2837
2838 static bool shouldCheckLines(RenderObject& obj)
2839 {
2840     return !obj.isFloatingOrOutOfFlowPositioned() && !obj.isRunIn() && obj.isRenderBlockFlow() && obj.style().height().isAuto() && (!obj.isDeprecatedFlexibleBox() || obj.style().boxOrient() == VERTICAL);
2841 }
2842
2843 RootInlineBox* RenderBlockFlow::lineAtIndex(int i) const
2844 {
2845     ASSERT(i >= 0);
2846
2847     if (style().visibility() != VISIBLE)
2848         return nullptr;
2849
2850     if (childrenInline()) {
2851         for (auto box = firstRootBox(); box; box = box->nextRootBox()) {
2852             if (!i--)
2853                 return box;
2854         }
2855     } else {
2856         for (auto child = firstChild(); child; child = child->nextSibling()) {
2857             if (!shouldCheckLines(*child))
2858                 continue;
2859             if (RootInlineBox* box = toRenderBlockFlow(child)->lineAtIndex(i))
2860                 return box;
2861         }
2862     }
2863
2864     return nullptr;
2865 }
2866
2867 int RenderBlockFlow::lineCount(const RootInlineBox* stopRootInlineBox, bool* found) const
2868 {
2869     if (style().visibility() != VISIBLE)
2870         return 0;
2871
2872     int count = 0;
2873
2874     if (childrenInline()) {
2875         for (auto box = firstRootBox(); box; box = box->nextRootBox()) {
2876             count++;
2877             if (box == stopRootInlineBox) {
2878                 if (found)
2879                     *found = true;
2880                 break;
2881             }
2882         }
2883     } else {
2884         for (auto child = firstChild(); child; child = child->nextSibling()) {
2885             if (shouldCheckLines(*child)) {
2886                 bool recursiveFound = false;
2887                 count += toRenderBlockFlow(child)->lineCount(stopRootInlineBox, &recursiveFound);
2888                 if (recursiveFound) {
2889                     if (found)
2890                         *found = true;
2891                     break;
2892                 }
2893             }
2894         }
2895     }
2896
2897     return count;
2898 }
2899
2900 static int getHeightForLineCount(const RenderBlockFlow& block, int lineCount, bool includeBottom, int& count)
2901 {
2902     if (block.style().visibility() != VISIBLE)
2903         return -1;
2904
2905     if (block.childrenInline()) {
2906         for (auto box = block.firstRootBox(); box; box = box->nextRootBox()) {
2907             if (++count == lineCount)
2908                 return box->lineBottom() + (includeBottom ? (block.borderBottom() + block.paddingBottom()) : LayoutUnit());
2909         }
2910     } else {
2911         RenderBox* normalFlowChildWithoutLines = 0;
2912         for (auto obj = block.firstChildBox(); obj; obj = obj->nextSiblingBox()) {
2913             if (shouldCheckLines(*obj)) {
2914                 int result = getHeightForLineCount(toRenderBlockFlow(*obj), lineCount, false, count);
2915                 if (result != -1)
2916                     return result + obj->y() + (includeBottom ? (block.borderBottom() + block.paddingBottom()) : LayoutUnit());
2917             } else if (!obj->isFloatingOrOutOfFlowPositioned() && !obj->isRunIn())
2918                 normalFlowChildWithoutLines = obj;
2919         }
2920         if (normalFlowChildWithoutLines && !lineCount)
2921             return normalFlowChildWithoutLines->y() + normalFlowChildWithoutLines->height();
2922     }
2923     
2924     return -1;
2925 }
2926
2927 int RenderBlockFlow::heightForLineCount(int lineCount)
2928 {
2929     int count = 0;
2930     return getHeightForLineCount(*this, lineCount, true, count);
2931 }
2932
2933 void RenderBlockFlow::clearTruncation()
2934 {
2935     if (style().visibility() != VISIBLE)
2936         return;
2937
2938     if (childrenInline() && hasMarkupTruncation()) {
2939         ensureLineBoxes();
2940
2941         setHasMarkupTruncation(false);
2942         for (auto box = firstRootBox(); box; box = box->nextRootBox())
2943             box->clearTruncation();
2944     } else {
2945         for (auto child = firstChild(); child; child = child->nextSibling()) {
2946             if (shouldCheckLines(*child))
2947                 toRenderBlockFlow(child)->clearTruncation();
2948         }
2949     }
2950 }
2951
2952 bool RenderBlockFlow::containsNonZeroBidiLevel() const
2953 {
2954     for (auto root = firstRootBox(); root; root = root->nextRootBox()) {
2955         for (auto box = root->firstLeafChild(); box; box = box->nextLeafChild()) {
2956             if (box->bidiLevel())
2957                 return true;
2958         }
2959     }
2960     return false;
2961 }
2962
2963 Position RenderBlockFlow::positionForBox(InlineBox *box, bool start) const
2964 {
2965     if (!box)
2966         return Position();
2967
2968     if (!box->renderer().nonPseudoNode())
2969         return createLegacyEditingPosition(nonPseudoElement(), start ? caretMinOffset() : caretMaxOffset());
2970
2971     if (!box->isInlineTextBox())
2972         return createLegacyEditingPosition(box->renderer().nonPseudoNode(), start ? box->renderer().caretMinOffset() : box->renderer().caretMaxOffset());
2973
2974     InlineTextBox* textBox = toInlineTextBox(box);
2975     return createLegacyEditingPosition(box->renderer().nonPseudoNode(), start ? textBox->start() : textBox->start() + textBox->len());
2976 }
2977
2978 VisiblePosition RenderBlockFlow::positionForPointWithInlineChildren(const LayoutPoint& pointInLogicalContents)
2979 {
2980     ASSERT(childrenInline());
2981
2982     ensureLineBoxes();
2983
2984     if (!firstRootBox())
2985         return createVisiblePosition(0, DOWNSTREAM);
2986
2987     bool linesAreFlipped = style().isFlippedLinesWritingMode();
2988     bool blocksAreFlipped = style().isFlippedBlocksWritingMode();
2989
2990     // look for the closest line box in the root box which is at the passed-in y coordinate
2991     InlineBox* closestBox = 0;
2992     RootInlineBox* firstRootBoxWithChildren = 0;
2993     RootInlineBox* lastRootBoxWithChildren = 0;
2994     for (RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox()) {
2995         if (!root->firstLeafChild())
2996             continue;
2997         if (!firstRootBoxWithChildren)
2998             firstRootBoxWithChildren = root;
2999
3000         if (!linesAreFlipped && root->isFirstAfterPageBreak() && (pointInLogicalContents.y() < root->lineTopWithLeading()
3001             || (blocksAreFlipped && pointInLogicalContents.y() == root->lineTopWithLeading())))
3002             break;
3003
3004         lastRootBoxWithChildren = root;
3005
3006         // check if this root line box is located at this y coordinate
3007         if (pointInLogicalContents.y() < root->selectionBottom() || (blocksAreFlipped && pointInLogicalContents.y() == root->selectionBottom())) {
3008             if (linesAreFlipped) {
3009                 RootInlineBox* nextRootBoxWithChildren = root->nextRootBox();
3010                 while (nextRootBoxWithChildren && !nextRootBoxWithChildren->firstLeafChild())
3011                     nextRootBoxWithChildren = nextRootBoxWithChildren->nextRootBox();
3012
3013                 if (nextRootBoxWithChildren && nextRootBoxWithChildren->isFirstAfterPageBreak() && (pointInLogicalContents.y() > nextRootBoxWithChildren->lineTopWithLeading()
3014                     || (!blocksAreFlipped && pointInLogicalContents.y() == nextRootBoxWithChildren->lineTopWithLeading())))
3015                     continue;
3016             }
3017             closestBox = root->closestLeafChildForLogicalLeftPosition(pointInLogicalContents.x());
3018             if (closestBox)
3019                 break;
3020         }
3021     }
3022
3023     bool moveCaretToBoundary = frame().editor().behavior().shouldMoveCaretToHorizontalBoundaryWhenPastTopOrBottom();
3024
3025     if (!moveCaretToBoundary && !closestBox && lastRootBoxWithChildren) {
3026         // y coordinate is below last root line box, pretend we hit it
3027         closestBox = lastRootBoxWithChildren->closestLeafChildForLogicalLeftPosition(pointInLogicalContents.x());
3028     }
3029
3030     if (closestBox) {
3031         if (moveCaretToBoundary) {
3032             LayoutUnit firstRootBoxWithChildrenTop = min<LayoutUnit>(firstRootBoxWithChildren->selectionTop(), firstRootBoxWithChildren->logicalTop());
3033             if (pointInLogicalContents.y() < firstRootBoxWithChildrenTop
3034                 || (blocksAreFlipped && pointInLogicalContents.y() == firstRootBoxWithChildrenTop)) {
3035                 InlineBox* box = firstRootBoxWithChildren->firstLeafChild();
3036                 if (box->isLineBreak()) {
3037                     if (InlineBox* newBox = box->nextLeafChildIgnoringLineBreak())
3038                         box = newBox;
3039                 }
3040                 // y coordinate is above first root line box, so return the start of the first
3041                 return VisiblePosition(positionForBox(box, true), DOWNSTREAM);
3042             }
3043         }
3044
3045         // pass the box a top position that is inside it
3046         LayoutPoint point(pointInLogicalContents.x(), closestBox->root().blockDirectionPointInLine());
3047         if (!isHorizontalWritingMode())
3048             point = point.transposedPoint();
3049         if (closestBox->renderer().isReplaced())
3050             return positionForPointRespectingEditingBoundaries(*this, toRenderBox(closestBox->renderer()), point);
3051         return closestBox->renderer().positionForPoint(point);
3052     }
3053
3054     if (lastRootBoxWithChildren) {
3055         // We hit this case for Mac behavior when the Y coordinate is below the last box.
3056         ASSERT(moveCaretToBoundary);
3057         InlineBox* logicallyLastBox;
3058         if (lastRootBoxWithChildren->getLogicalEndBoxWithNode(logicallyLastBox))
3059             return VisiblePosition(positionForBox(logicallyLastBox, false), DOWNSTREAM);
3060     }
3061
3062     // Can't reach this. We have a root line box, but it has no kids.
3063     // FIXME: This should ASSERT_NOT_REACHED(), but clicking on placeholder text
3064     // seems to hit this code path.
3065     return createVisiblePosition(0, DOWNSTREAM);
3066 }
3067
3068 void RenderBlockFlow::addFocusRingRectsForInlineChildren(Vector<IntRect>& rects, const LayoutPoint& additionalOffset, const RenderLayerModelObject*)
3069 {
3070     ASSERT(childrenInline());
3071
3072     ensureLineBoxes();
3073
3074     for (RootInlineBox* curr = firstRootBox(); curr; curr = curr->nextRootBox()) {
3075         LayoutUnit top = max<LayoutUnit>(curr->lineTop(), curr->top());
3076         LayoutUnit bottom = min<LayoutUnit>(curr->lineBottom(), curr->top() + curr->height());
3077         LayoutRect rect(additionalOffset.x() + curr->x(), additionalOffset.y() + top, curr->width(), bottom - top);
3078         if (!rect.isEmpty())
3079             rects.append(pixelSnappedIntRect(rect));
3080     }
3081 }
3082
3083 void RenderBlockFlow::paintInlineChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
3084 {
3085     ASSERT(childrenInline());
3086
3087     if (m_simpleLineLayout) {
3088         SimpleLineLayout::paintFlow(*this, *m_simpleLineLayout, paintInfo, paintOffset);
3089         return;
3090     }
3091     m_lineBoxes.paint(this, paintInfo, paintOffset);
3092 }
3093
3094 bool RenderBlockFlow::relayoutForPagination(bool hasSpecifiedPageLogicalHeight, LayoutUnit pageLogicalHeight, LayoutStateMaintainer& statePusher)
3095 {
3096     if (!hasColumns())
3097         return false;
3098
3099     OwnPtr<RenderOverflow> savedOverflow = m_overflow.release();
3100     if (childrenInline())
3101         addOverflowFromInlineChildren();
3102     else
3103         addOverflowFromBlockChildren();
3104     LayoutUnit layoutOverflowLogicalBottom = (isHorizontalWritingMode() ? layoutOverflowRect().maxY() : layoutOverflowRect().maxX()) - borderAndPaddingBefore();
3105
3106     // FIXME: We don't balance properly at all in the presence of forced page breaks.  We need to understand what
3107     // the distance between forced page breaks is so that we can avoid making the minimum column height too tall.
3108     ColumnInfo* colInfo = columnInfo();
3109     if (!hasSpecifiedPageLogicalHeight) {
3110         LayoutUnit columnHeight = pageLogicalHeight;
3111         int minColumnCount = colInfo->forcedBreaks() + 1;
3112         int desiredColumnCount = colInfo->desiredColumnCount();
3113         if (minColumnCount >= desiredColumnCount) {
3114             // The forced page breaks are in control of the balancing.  Just set the column height to the
3115             // maximum page break distance.
3116             if (!pageLogicalHeight) {
3117                 LayoutUnit distanceBetweenBreaks = max<LayoutUnit>(colInfo->maximumDistanceBetweenForcedBreaks(),
3118                     view().layoutState()->pageLogicalOffset(this, borderAndPaddingBefore() + layoutOverflowLogicalBottom) - colInfo->forcedBreakOffset());
3119                 columnHeight = max(colInfo->minimumColumnHeight(), distanceBetweenBreaks);
3120             }
3121         } else if (layoutOverflowLogicalBottom > boundedMultiply(pageLogicalHeight, desiredColumnCount)) {
3122             // Now that we know the intrinsic height of the columns, we have to rebalance them.
3123             columnHeight = max<LayoutUnit>(colInfo->minimumColumnHeight(), ceilf((float)layoutOverflowLogicalBottom / desiredColumnCount));
3124         }
3125         
3126         if (columnHeight && columnHeight != pageLogicalHeight) {
3127             statePusher.pop();
3128             setEverHadLayout(true);
3129             layoutBlock(false, columnHeight);
3130             return true;
3131         }
3132     } 
3133
3134     if (pageLogicalHeight)
3135         colInfo->setColumnCountAndHeight(ceilf((float)layoutOverflowLogicalBottom / pageLogicalHeight), pageLogicalHeight);
3136
3137     if (columnCount(colInfo)) {
3138         setLogicalHeight(borderAndPaddingBefore() + colInfo->columnHeight() + borderAndPaddingAfter() + scrollbarLogicalHeight());
3139         clearOverflow();
3140     } else
3141         m_overflow = savedOverflow.release();
3142     
3143     return false;
3144 }
3145
3146 bool RenderBlockFlow::hasLines() const
3147 {
3148     ASSERT(childrenInline());
3149
3150     if (m_simpleLineLayout)
3151         return m_simpleLineLayout->lineCount;
3152
3153     return lineBoxes().firstLineBox();
3154 }
3155
3156 void RenderBlockFlow::layoutSimpleLines(LayoutUnit& repaintLogicalTop, LayoutUnit& repaintLogicalBottom)
3157 {
3158     ASSERT(!m_lineBoxes.firstLineBox());
3159
3160     m_simpleLineLayout = SimpleLineLayout::create(*this);
3161
3162     LayoutUnit lineLayoutHeight = SimpleLineLayout::computeFlowHeight(*this, *m_simpleLineLayout);
3163     LayoutUnit lineLayoutTop = borderAndPaddingBefore();
3164
3165     repaintLogicalTop = lineLayoutTop;
3166     repaintLogicalBottom = lineLayoutTop + lineLayoutHeight;
3167
3168     setLogicalHeight(lineLayoutTop + lineLayoutHeight + borderAndPaddingAfter());
3169 }
3170
3171 void RenderBlockFlow::deleteLineBoxesBeforeSimpleLineLayout()
3172 {
3173     ASSERT(m_lineLayoutPath == SimpleLinesPath);
3174     lineBoxes().deleteLineBoxes(renderArena());
3175     toRenderText(firstChild())->deleteLineBoxesBeforeSimpleLineLayout();
3176 }
3177
3178 void RenderBlockFlow::ensureLineBoxes()
3179 {
3180     m_lineLayoutPath = ForceLineBoxesPath;
3181
3182     if (!m_simpleLineLayout)
3183         return;
3184     m_simpleLineLayout = nullptr;
3185
3186 #if !ASSERT_DISABLED
3187     LayoutUnit oldHeight = logicalHeight();
3188 #endif
3189     bool didNeedLayout = needsLayout();
3190
3191     bool relayoutChildren = false;
3192     LayoutUnit repaintLogicalTop;
3193     LayoutUnit repaintLogicalBottom;
3194     layoutLineBoxes(relayoutChildren, repaintLogicalTop, repaintLogicalBottom);
3195
3196     updateLogicalHeight();
3197     ASSERT(didNeedLayout || logicalHeight() == oldHeight);
3198
3199     if (!didNeedLayout)
3200         clearNeedsLayout();
3201 }
3202
3203 #ifndef NDEBUG
3204 void RenderBlockFlow::showLineTreeAndMark(const InlineBox* markedBox1, const char* markedLabel1, const InlineBox* markedBox2, const char* markedLabel2, const RenderObject* obj) const
3205 {
3206     RenderBlock::showLineTreeAndMark(markedBox1, markedLabel1, markedBox2, markedLabel2, obj);
3207     for (const RootInlineBox* root = firstRootBox(); root; root = root->nextRootBox())
3208         root->showLineTreeAndMark(markedBox1, markedLabel1, markedBox2, markedLabel2, obj, 1);
3209 }
3210 #endif
3211
3212 } // namespace WebCore