d2b0080a962d17a9903037f81d40166cc08eeee7
[WebKit-https.git] / Source / WebCore / rendering / RenderFlowThread.cpp
1 /*
2  * Copyright (C) 2011 Adobe Systems Incorporated. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above
9  *    copyright notice, this list of conditions and the following
10  *    disclaimer.
11  * 2. Redistributions in binary form must reproduce the above
12  *    copyright notice, this list of conditions and the following
13  *    disclaimer in the documentation and/or other materials
14  *    provided with the distribution.
15  * 
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER "AS IS" AND ANY
17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE
20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
21  * OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
25  * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
26  * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27  * SUCH DAMAGE.
28  */
29
30 #include "config.h"
31 #include "RenderFlowThread.h"
32
33 #include "FlowThreadController.h"
34 #include "HitTestRequest.h"
35 #include "HitTestResult.h"
36 #include "InlineElementBox.h"
37 #include "Node.h"
38 #include "PODIntervalTree.h"
39 #include "PaintInfo.h"
40 #include "RenderBoxRegionInfo.h"
41 #include "RenderInline.h"
42 #include "RenderLayer.h"
43 #include "RenderLayerCompositor.h"
44 #include "RenderNamedFlowFragment.h"
45 #include "RenderRegion.h"
46 #include "RenderTheme.h"
47 #include "RenderView.h"
48 #include "TransformState.h"
49 #include "WebKitNamedFlow.h"
50 #include <wtf/StackStats.h>
51
52 namespace WebCore {
53
54 RenderFlowThread::RenderFlowThread(Document& document, PassRef<RenderStyle> style)
55     : RenderBlockFlow(document, WTF::move(style))
56     , m_previousRegionCount(0)
57     , m_autoLogicalHeightRegionsCount(0)
58     , m_currentRegionMaintainer(nullptr)
59     , m_regionsInvalidated(false)
60     , m_regionsHaveUniformLogicalWidth(true)
61     , m_regionsHaveUniformLogicalHeight(true)
62     , m_pageLogicalSizeChanged(false)
63     , m_layoutPhase(LayoutPhaseMeasureContent)
64     , m_needsTwoPhasesLayout(false)
65     , m_layersToRegionMappingsDirty(true)
66 {
67     setFlowThreadState(InsideOutOfFlowThread);
68 }
69
70 PassRef<RenderStyle> RenderFlowThread::createFlowThreadStyle(RenderStyle* parentStyle)
71 {
72     auto newStyle = RenderStyle::create();
73     newStyle.get().inheritFrom(parentStyle);
74     newStyle.get().setDisplay(BLOCK);
75     newStyle.get().setPosition(AbsolutePosition);
76     newStyle.get().setZIndex(0);
77     newStyle.get().setLeft(Length(0, Fixed));
78     newStyle.get().setTop(Length(0, Fixed));
79     newStyle.get().setWidth(Length(100, Percent));
80     newStyle.get().setHeight(Length(100, Percent));
81     newStyle.get().font().update(0);
82     return newStyle;
83 }
84
85 void RenderFlowThread::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle)
86 {
87     RenderBlockFlow::styleDidChange(diff, oldStyle);
88
89     if (oldStyle && oldStyle->writingMode() != style().writingMode())
90         invalidateRegions();
91 }
92
93 void RenderFlowThread::removeFlowChildInfo(RenderObject* child)
94 {
95     if (is<RenderBlockFlow>(*child))
96         removeLineRegionInfo(downcast<RenderBlockFlow>(child));
97     if (is<RenderBox>(*child))
98         removeRenderBoxRegionInfo(downcast<RenderBox>(child));
99 }
100
101 void RenderFlowThread::removeRegionFromThread(RenderRegion* renderRegion)
102 {
103     ASSERT(renderRegion);
104     m_regionList.remove(renderRegion);
105 }
106
107 void RenderFlowThread::invalidateRegions()
108 {
109     ASSERT(!inFinalLayoutPhase());
110
111     if (m_regionsInvalidated) {
112         ASSERT(selfNeedsLayout());
113         return;
114     }
115
116     m_regionRangeMap.clear();
117     m_breakBeforeToRegionMap.clear();
118     m_breakAfterToRegionMap.clear();
119     if (m_layerToRegionMap)
120         m_layerToRegionMap->clear();
121     if (m_regionToLayerListMap)
122         m_regionToLayerListMap->clear();
123     if (m_lineToRegionMap)
124         m_lineToRegionMap->clear();
125     m_layersToRegionMappingsDirty = true;
126     setNeedsLayout();
127
128     m_regionsInvalidated = true;
129 }
130
131 void RenderFlowThread::validateRegions()
132 {
133     if (m_regionsInvalidated) {
134         m_regionsInvalidated = false;
135         m_regionsHaveUniformLogicalWidth = true;
136         m_regionsHaveUniformLogicalHeight = true;
137
138         if (hasRegions()) {
139             LayoutUnit previousRegionLogicalWidth = 0;
140             LayoutUnit previousRegionLogicalHeight = 0;
141             bool firstRegionVisited = false;
142             
143             for (auto& region : m_regionList) {
144                 ASSERT(!region->needsLayout() || region->isRenderRegionSet());
145
146                 region->deleteAllRenderBoxRegionInfo();
147
148                 // In the measure content layout phase we need to initialize the computedAutoHeight for auto-height regions.
149                 // See initializeRegionsComputedAutoHeight for the explanation.
150                 // Also, if we have auto-height regions we can't assume m_regionsHaveUniformLogicalHeight to be true in the first phase
151                 // because the auto-height regions don't have their height computed yet.
152                 if (inMeasureContentLayoutPhase() && region->hasAutoLogicalHeight()) {
153                     RenderNamedFlowFragment* namedFlowFragment = toRenderNamedFlowFragment(region);
154                     namedFlowFragment->setComputedAutoHeight(namedFlowFragment->maxPageLogicalHeight());
155                     m_regionsHaveUniformLogicalHeight = false;
156                 }
157
158                 LayoutUnit regionLogicalWidth = region->pageLogicalWidth();
159                 LayoutUnit regionLogicalHeight = region->pageLogicalHeight();
160
161                 if (!firstRegionVisited)
162                     firstRegionVisited = true;
163                 else {
164                     if (m_regionsHaveUniformLogicalWidth && previousRegionLogicalWidth != regionLogicalWidth)
165                         m_regionsHaveUniformLogicalWidth = false;
166                     if (m_regionsHaveUniformLogicalHeight && previousRegionLogicalHeight != regionLogicalHeight)
167                         m_regionsHaveUniformLogicalHeight = false;
168                 }
169
170                 previousRegionLogicalWidth = regionLogicalWidth;
171             }
172
173             setRegionRangeForBox(this, m_regionList.first(), m_regionList.last());
174         }
175     }
176
177     updateLogicalWidth(); // Called to get the maximum logical width for the region.
178     updateRegionsFlowThreadPortionRect();
179 }
180
181 void RenderFlowThread::layout()
182 {
183     StackStats::LayoutCheckPoint layoutCheckPoint;
184
185     m_pageLogicalSizeChanged = m_regionsInvalidated && everHadLayout();
186
187     // In case this is the second pass of the measure content phase we need to update the auto-height regions to their initial value.
188     // If the region chain was invalidated this will happen anyway.
189     if (!m_regionsInvalidated && inMeasureContentLayoutPhase())
190         initializeRegionsComputedAutoHeight();
191
192     // This is the first phase of the layout and because we have auto-height regions we'll need a second
193     // pass to update the flow with the computed auto-height regions.
194     // It's also possible to need a secondary layout if the overflow computation invalidated the region chain (e.g. overflow: auto scrollbars
195     // shrunk some regions) so repropagation is required.
196     m_needsTwoPhasesLayout = (inMeasureContentLayoutPhase() && hasAutoLogicalHeightRegions()) || (inOverflowLayoutPhase() && m_regionsInvalidated);
197
198     validateRegions();
199
200     RenderBlockFlow::layout();
201
202     m_pageLogicalSizeChanged = false;
203
204     // If there are children layers in the RenderFlowThread then we need to make sure that the
205     // composited children layers will land in the right RenderRegions. Also, the parent RenderRegions
206     // will get RenderLayers and become composited as needed.
207     // Note that there's no need to do so for the inline multi-column as we are not moving layers into different
208     // containers, but just adjusting the position of the RenderLayerBacking.
209     if (!m_needsTwoPhasesLayout) {
210         // If we have layers that moved from one region to another, we trigger
211         // a composited layers rebuild in here to make sure that the regions will collect the right layers.
212         if (updateAllLayerToRegionMappings())
213             layer()->compositor().setCompositingLayersNeedRebuild();
214     }
215 }
216
217 bool RenderFlowThread::hasCompositingRegionDescendant() const
218 {
219     for (auto& region : m_regionList) {
220         if (toRenderNamedFlowFragment(region)->layerOwner().layer()->hasCompositingDescendant())
221             return true;
222     }
223
224     return false;
225 }
226
227 const RenderLayerList* RenderFlowThread::getLayerListForRegion(RenderNamedFlowFragment* region) const
228 {
229     ASSERT(m_regionToLayerListMap);
230     auto iterator = m_regionToLayerListMap->find(region);
231     return iterator == m_regionToLayerListMap->end() ? nullptr : &iterator->value;
232 }
233
234 RenderNamedFlowFragment* RenderFlowThread::regionForCompositedLayer(RenderLayer& childLayer) const
235 {
236     if (childLayer.renderer().fixedPositionedWithNamedFlowContainingBlock())
237         return nullptr;
238
239     if (childLayer.renderBox()) {
240         RenderRegion* startRegion = nullptr;
241         RenderRegion* endRegion = nullptr;
242         if (getRegionRangeForBox(childLayer.renderBox(), startRegion, endRegion))
243             return toRenderNamedFlowFragment(startRegion);
244     }
245
246     // FIXME: remove this when we'll have region ranges for inlines as well.
247     LayoutPoint flowThreadOffset = flooredLayoutPoint(childLayer.renderer().localToContainerPoint(LayoutPoint(), this, ApplyContainerFlip));
248     return toRenderNamedFlowFragment(regionAtBlockOffset(0, flipForWritingMode(isHorizontalWritingMode() ? flowThreadOffset.y() : flowThreadOffset.x()), true));
249 }
250
251 RenderNamedFlowFragment* RenderFlowThread::cachedRegionForCompositedLayer(RenderLayer& childLayer) const
252 {
253     if (!m_layerToRegionMap) {
254         ASSERT(needsLayout());
255         ASSERT(m_layersToRegionMappingsDirty);
256         return nullptr;
257     }
258
259     RenderNamedFlowFragment* namedFlowFragment = m_layerToRegionMap->get(&childLayer);
260     ASSERT(!namedFlowFragment || m_regionList.contains(namedFlowFragment));
261     return namedFlowFragment;
262 }
263
264 void RenderFlowThread::updateLayerToRegionMappings(RenderLayer& layer, LayerToRegionMap& layerToRegionMap, RegionToLayerListMap& regionToLayerListMap, bool& needsLayerUpdate)
265 {
266     RenderNamedFlowFragment* region = regionForCompositedLayer(layer);
267     if (!needsLayerUpdate) {
268         // Figure out if we moved this layer from a region to the other.
269         RenderNamedFlowFragment* previousRegion = cachedRegionForCompositedLayer(layer);
270         if (previousRegion != region)
271             needsLayerUpdate = true;
272     }
273
274     if (!region)
275         return;
276
277     layerToRegionMap.set(&layer, region);
278
279     auto iterator = regionToLayerListMap.find(region);
280     RenderLayerList& list = iterator == regionToLayerListMap.end() ? regionToLayerListMap.set(region, RenderLayerList()).iterator->value : iterator->value;
281     ASSERT(!list.contains(&layer));
282     list.append(&layer);
283 }
284
285 bool RenderFlowThread::updateAllLayerToRegionMappings()
286 {
287     if (!collectsGraphicsLayersUnderRegions())
288         return false;
289
290     // If the RenderFlowThread had a z-index layer update, then we need to update the composited layers too.
291     bool needsLayerUpdate = layer()->isDirtyRenderFlowThread() || m_layersToRegionMappingsDirty || !m_layerToRegionMap.get();
292     layer()->updateLayerListsIfNeeded();
293
294     LayerToRegionMap layerToRegionMap;
295     RegionToLayerListMap regionToLayerListMap;
296
297     RenderLayerList* lists[] = { layer()->negZOrderList(), layer()->normalFlowList(), layer()->posZOrderList() };
298     for (size_t listIndex = 0; listIndex < sizeof(lists) / sizeof(lists[0]); ++listIndex) {
299         if (RenderLayerList* list = lists[listIndex]) {
300             for (size_t i = 0, listSize = list->size(); i < listSize; ++i)
301                 updateLayerToRegionMappings(*list->at(i), layerToRegionMap, regionToLayerListMap, needsLayerUpdate);
302         }
303     }
304
305     if (needsLayerUpdate) {
306         if (!m_layerToRegionMap)
307             m_layerToRegionMap = std::make_unique<LayerToRegionMap>();
308         m_layerToRegionMap->swap(layerToRegionMap);
309
310         if (!m_regionToLayerListMap)
311             m_regionToLayerListMap = std::make_unique<RegionToLayerListMap>();
312         m_regionToLayerListMap->swap(regionToLayerListMap);
313     }
314
315     m_layersToRegionMappingsDirty = false;
316
317     return needsLayerUpdate;
318 }
319
320 bool RenderFlowThread::collectsGraphicsLayersUnderRegions() const
321 {
322     // We only need to map layers to regions for named flow threads.
323     // Multi-column threads are displayed on top of the regions and do not require
324     // distributing the layers.
325
326     return false;
327 }
328
329 void RenderFlowThread::updateLogicalWidth()
330 {
331     LayoutUnit logicalWidth = initialLogicalWidth();
332     for (auto& region : m_regionList) {
333         ASSERT(!region->needsLayout() || region->isRenderRegionSet());
334         logicalWidth = std::max(region->pageLogicalWidth(), logicalWidth);
335     }
336     setLogicalWidth(logicalWidth);
337
338     // If the regions have non-uniform logical widths, then insert inset information for the RenderFlowThread.
339     for (auto& region : m_regionList) {
340         LayoutUnit regionLogicalWidth = region->pageLogicalWidth();
341         LayoutUnit logicalLeft = style().direction() == LTR ? LayoutUnit() : logicalWidth - regionLogicalWidth;
342         region->setRenderBoxRegionInfo(this, logicalLeft, regionLogicalWidth, false);
343     }
344 }
345
346 void RenderFlowThread::computeLogicalHeight(LayoutUnit, LayoutUnit logicalTop, LogicalExtentComputedValues& computedValues) const
347 {
348     computedValues.m_position = logicalTop;
349     computedValues.m_extent = 0;
350
351     const LayoutUnit maxFlowSize = RenderFlowThread::maxLogicalHeight();
352     for (auto& region : m_regionList) {
353         ASSERT(!region->needsLayout() || region->isRenderRegionSet());
354
355         LayoutUnit distanceToMaxSize = maxFlowSize - computedValues.m_extent;
356         computedValues.m_extent += std::min(distanceToMaxSize, region->logicalHeightOfAllFlowThreadContent());
357
358         // If we reached the maximum size there's no point in going further.
359         if (computedValues.m_extent == maxFlowSize)
360             return;
361     }
362 }
363
364 bool RenderFlowThread::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction)
365 {
366     if (hitTestAction == HitTestBlockBackground)
367         return false;
368     return RenderBlockFlow::nodeAtPoint(request, result, locationInContainer, accumulatedOffset, hitTestAction);
369 }
370
371 bool RenderFlowThread::shouldRepaint(const LayoutRect& r) const
372 {
373     if (view().printing() || r.isEmpty())
374         return false;
375
376     return true;
377 }
378
379 void RenderFlowThread::repaintRectangleInRegions(const LayoutRect& repaintRect) const
380 {
381     if (!shouldRepaint(repaintRect) || !hasValidRegionInfo())
382         return;
383
384     LayoutStateDisabler layoutStateDisabler(&view()); // We can't use layout state to repaint, since the regions are somewhere else.
385
386     for (auto& region : m_regionList)
387         region->repaintFlowThreadContent(repaintRect);
388 }
389
390 RenderRegion* RenderFlowThread::regionAtBlockOffset(const RenderBox* clampBox, LayoutUnit offset, bool extendLastRegion) const
391 {
392     ASSERT(!m_regionsInvalidated);
393
394     if (m_regionList.isEmpty())
395         return nullptr;
396
397     if (m_regionList.size() == 1 && extendLastRegion)
398         return m_regionList.first();
399
400     if (offset <= 0)
401         return clampBox ? clampBox->clampToStartAndEndRegions(m_regionList.first()) : m_regionList.first();
402
403     RegionSearchAdapter adapter(offset);
404     m_regionIntervalTree.allOverlapsWithAdapter<RegionSearchAdapter>(adapter);
405
406     // If no region was found, the offset is in the flow thread overflow.
407     // The last region will contain the offset if extendLastRegion is set or if the last region is a set.
408     if (!adapter.result() && (extendLastRegion || m_regionList.last()->isRenderRegionSet()))
409         return clampBox ? clampBox->clampToStartAndEndRegions(m_regionList.last()) : m_regionList.last();
410
411     RenderRegion* region = adapter.result();
412     if (!clampBox)
413         return region;
414     return region ? clampBox->clampToStartAndEndRegions(region) : nullptr;
415 }
416
417 LayoutPoint RenderFlowThread::adjustedPositionRelativeToOffsetParent(const RenderBoxModelObject& boxModelObject, const LayoutPoint& startPoint) const
418 {
419     LayoutPoint referencePoint = startPoint;
420     
421     const RenderBlock* objContainingBlock = boxModelObject.containingBlock();
422     // FIXME: This needs to be adapted for different writing modes inside the flow thread.
423     RenderRegion* startRegion = regionAtBlockOffset(objContainingBlock, referencePoint.y());
424     if (startRegion) {
425         // Take into account the offset coordinates of the region.
426         RenderBoxModelObject* startRegionBox = is<RenderNamedFlowFragment>(*startRegion) ? downcast<RenderBoxModelObject>(startRegion->parent()) : startRegion;
427         RenderBoxModelObject* currObject = startRegionBox;
428         RenderBoxModelObject* currOffsetParent;
429         while ((currOffsetParent = currObject->offsetParent())) {
430             referencePoint.move(currObject->offsetLeft(), currObject->offsetTop());
431             
432             // Since we're looking for the offset relative to the body, we must also
433             // take into consideration the borders of the region's offsetParent.
434             if (is<RenderBox>(*currOffsetParent) && !currOffsetParent->isBody())
435                 referencePoint.move(downcast<RenderBox>(*currOffsetParent).borderLeft(), downcast<RenderBox>(*currOffsetParent).borderTop());
436             
437             currObject = currOffsetParent;
438         }
439         
440         // We need to check if any of this box's containing blocks start in a different region
441         // and if so, drop the object's top position (which was computed relative to its containing block
442         // and is no longer valid) and recompute it using the region in which it flows as reference.
443         bool wasComputedRelativeToOtherRegion = false;
444         while (objContainingBlock && !objContainingBlock->isRenderNamedFlowThread()) {
445             // Check if this object is in a different region.
446             RenderRegion* parentStartRegion = nullptr;
447             RenderRegion* parentEndRegion = nullptr;
448             if (getRegionRangeForBox(objContainingBlock, parentStartRegion, parentEndRegion) && parentStartRegion != startRegion) {
449                 wasComputedRelativeToOtherRegion = true;
450                 break;
451             }
452             objContainingBlock = objContainingBlock->containingBlock();
453         }
454         
455         if (wasComputedRelativeToOtherRegion) {
456             if (is<RenderBox>(boxModelObject)) {
457                 // Use borderBoxRectInRegion to account for variations such as percentage margins.
458                 LayoutRect borderBoxRect = downcast<RenderBox>(boxModelObject).borderBoxRectInRegion(startRegion, RenderBox::DoNotCacheRenderBoxRegionInfo);
459                 referencePoint.move(borderBoxRect.location().x(), 0);
460             }
461             
462             // Get the logical top coordinate of the current object.
463             LayoutUnit top = 0;
464             if (is<RenderBlock>(boxModelObject))
465                 top = downcast<RenderBlock>(boxModelObject).offsetFromLogicalTopOfFirstPage();
466             else {
467                 if (boxModelObject.containingBlock())
468                     top = boxModelObject.containingBlock()->offsetFromLogicalTopOfFirstPage();
469                 
470                 if (is<RenderBox>(boxModelObject))
471                     top += downcast<RenderBox>(boxModelObject).topLeftLocation().y();
472                 else if (is<RenderInline>(boxModelObject))
473                     top -= downcast<RenderInline>(boxModelObject).borderTop();
474             }
475             
476             // Get the logical top of the region this object starts in
477             // and compute the object's top, relative to the region's top.
478             LayoutUnit regionLogicalTop = startRegion->pageLogicalTopForOffset(top);
479             LayoutUnit topRelativeToRegion = top - regionLogicalTop;
480             referencePoint.setY(startRegionBox->offsetTop() + topRelativeToRegion);
481             
482             // Since the top has been overriden, check if the
483             // relative/sticky positioning must be reconsidered.
484             if (boxModelObject.isRelPositioned())
485                 referencePoint.move(0, boxModelObject.relativePositionOffset().height());
486             else if (boxModelObject.isStickyPositioned())
487                 referencePoint.move(0, boxModelObject.stickyPositionOffset().height());
488         }
489         
490         // Since we're looking for the offset relative to the body, we must also
491         // take into consideration the borders of the region.
492         referencePoint.move(startRegionBox->borderLeft(), startRegionBox->borderTop());
493     }
494     
495     return referencePoint;
496 }
497
498 LayoutUnit RenderFlowThread::pageLogicalTopForOffset(LayoutUnit offset) const
499 {
500     RenderRegion* region = regionAtBlockOffset(0, offset, false);
501     return region ? region->pageLogicalTopForOffset(offset) : LayoutUnit();
502 }
503
504 LayoutUnit RenderFlowThread::pageLogicalWidthForOffset(LayoutUnit offset) const
505 {
506     RenderRegion* region = regionAtBlockOffset(0, offset, true);
507     return region ? region->pageLogicalWidth() : contentLogicalWidth();
508 }
509
510 LayoutUnit RenderFlowThread::pageLogicalHeightForOffset(LayoutUnit offset) const
511 {
512     RenderRegion* region = regionAtBlockOffset(0, offset, false);
513     if (!region)
514         return 0;
515
516     return region->pageLogicalHeight();
517 }
518
519 LayoutUnit RenderFlowThread::pageRemainingLogicalHeightForOffset(LayoutUnit offset, PageBoundaryRule pageBoundaryRule) const
520 {
521     RenderRegion* region = regionAtBlockOffset(0, offset, false);
522     if (!region)
523         return 0;
524
525     LayoutUnit pageLogicalTop = region->pageLogicalTopForOffset(offset);
526     LayoutUnit pageLogicalHeight = region->pageLogicalHeight();
527     LayoutUnit pageLogicalBottom = pageLogicalTop + pageLogicalHeight;
528     LayoutUnit remainingHeight = pageLogicalBottom - offset;
529     if (pageBoundaryRule == IncludePageBoundary) {
530         // If IncludePageBoundary is set, the line exactly on the top edge of a
531         // region will act as being part of the previous region.
532         remainingHeight = intMod(remainingHeight, pageLogicalHeight);
533     }
534     return remainingHeight;
535 }
536
537 RenderRegion* RenderFlowThread::mapFromFlowToRegion(TransformState& transformState) const
538 {
539     if (!hasValidRegionInfo())
540         return nullptr;
541
542     RenderRegion* renderRegion = currentRegion();
543     if (!renderRegion) {
544         LayoutRect boxRect = transformState.mappedQuad().enclosingBoundingBox();
545         flipForWritingMode(boxRect);
546
547         LayoutPoint center = boxRect.center();
548         renderRegion = regionAtBlockOffset(this, isHorizontalWritingMode() ? center.y() : center.x(), true);
549         if (!renderRegion)
550             return nullptr;
551     }
552
553     LayoutRect flippedRegionRect(renderRegion->flowThreadPortionRect());
554     flipForWritingMode(flippedRegionRect);
555
556     transformState.move(renderRegion->contentBoxRect().location() - flippedRegionRect.location());
557
558     return renderRegion;
559 }
560
561 void RenderFlowThread::removeRenderBoxRegionInfo(RenderBox* box)
562 {
563     if (!hasRegions())
564         return;
565
566     // If the region chain was invalidated the next layout will clear the box information from all the regions.
567     if (m_regionsInvalidated) {
568         ASSERT(selfNeedsLayout());
569         return;
570     }
571
572     RenderRegion* startRegion = nullptr;
573     RenderRegion* endRegion = nullptr;
574     if (getRegionRangeForBox(box, startRegion, endRegion)) {
575         for (auto it = m_regionList.find(startRegion), end = m_regionList.end(); it != end; ++it) {
576             RenderRegion* region = *it;
577             region->removeRenderBoxRegionInfo(box);
578             if (region == endRegion)
579                 break;
580         }
581     }
582
583 #ifndef NDEBUG
584     // We have to make sure we did not leave any RenderBoxRegionInfo attached.
585     for (auto& region : m_regionList)
586         ASSERT(!region->renderBoxRegionInfo(box));
587 #endif
588
589     m_regionRangeMap.remove(box);
590 }
591
592 void RenderFlowThread::removeLineRegionInfo(const RenderBlockFlow* blockFlow)
593 {
594     if (!m_lineToRegionMap || blockFlow->m_lineLayoutPath == SimpleLinesPath)
595         return;
596
597     for (RootInlineBox* curr = blockFlow->firstRootBox(); curr; curr = curr->nextRootBox()) {
598         if (m_lineToRegionMap->contains(curr))
599             m_lineToRegionMap->remove(curr);
600     }
601
602     ASSERT_WITH_SECURITY_IMPLICATION(checkLinesConsistency(blockFlow));
603 }
604
605 void RenderFlowThread::logicalWidthChangedInRegionsForBlock(const RenderBlock* block, bool& relayoutChildren)
606 {
607     if (!hasValidRegionInfo()) {
608         // FIXME: Remove once we stop laying out flow threads without regions.
609         // If we had regions but don't any more, relayout the children because the code below
610         // can't properly detect this scenario.
611         relayoutChildren |= previousRegionCountChanged();
612         return;
613     }
614
615     auto it = m_regionRangeMap.find(block);
616     if (it == m_regionRangeMap.end())
617         return;
618
619     RenderRegionRange& range = it->value;
620     bool rangeInvalidated = range.rangeInvalidated();
621     range.clearRangeInvalidated();
622
623     // If there will be a relayout anyway skip the next steps because they only verify
624     // the state of the ranges.
625     if (relayoutChildren)
626         return;
627
628     // Not necessary for the flow thread, since we already computed the correct info for it.
629     // If the regions have changed invalidate the children.
630     if (block == this) {
631         relayoutChildren = m_pageLogicalSizeChanged;
632         return;
633     }
634
635     RenderRegion* startRegion = nullptr;
636     RenderRegion* endRegion = nullptr;
637     if (!getRegionRangeForBox(block, startRegion, endRegion))
638         return;
639
640     for (auto it = m_regionList.find(startRegion), end = m_regionList.end(); it != end; ++it) {
641         RenderRegion* region = *it;
642         ASSERT(!region->needsLayout() || region->isRenderRegionSet());
643
644         // We have no information computed for this region so we need to do it.
645         std::unique_ptr<RenderBoxRegionInfo> oldInfo = region->takeRenderBoxRegionInfo(block);
646         if (!oldInfo) {
647             relayoutChildren = rangeInvalidated;
648             return;
649         }
650
651         LayoutUnit oldLogicalWidth = oldInfo->logicalWidth();
652         RenderBoxRegionInfo* newInfo = block->renderBoxRegionInfo(region);
653         if (!newInfo || newInfo->logicalWidth() != oldLogicalWidth) {
654             relayoutChildren = true;
655             return;
656         }
657
658         if (region == endRegion)
659             break;
660     }
661 }
662
663 LayoutUnit RenderFlowThread::contentLogicalWidthOfFirstRegion() const
664 {
665     RenderRegion* firstValidRegionInFlow = firstRegion();
666     if (!firstValidRegionInFlow)
667         return 0;
668     return isHorizontalWritingMode() ? firstValidRegionInFlow->contentWidth() : firstValidRegionInFlow->contentHeight();
669 }
670
671 LayoutUnit RenderFlowThread::contentLogicalHeightOfFirstRegion() const
672 {
673     RenderRegion* firstValidRegionInFlow = firstRegion();
674     if (!firstValidRegionInFlow)
675         return 0;
676     return isHorizontalWritingMode() ? firstValidRegionInFlow->contentHeight() : firstValidRegionInFlow->contentWidth();
677 }
678
679 LayoutUnit RenderFlowThread::contentLogicalLeftOfFirstRegion() const
680 {
681     RenderRegion* firstValidRegionInFlow = firstRegion();
682     if (!firstValidRegionInFlow)
683         return 0;
684     return isHorizontalWritingMode() ? firstValidRegionInFlow->flowThreadPortionRect().x() : firstValidRegionInFlow->flowThreadPortionRect().y();
685 }
686
687 RenderRegion* RenderFlowThread::firstRegion() const
688 {
689     if (!hasRegions())
690         return nullptr;
691     return m_regionList.first();
692 }
693
694 RenderRegion* RenderFlowThread::lastRegion() const
695 {
696     if (!hasRegions())
697         return nullptr;
698     return m_regionList.last();
699 }
700
701 void RenderFlowThread::clearRenderBoxRegionInfoAndCustomStyle(const RenderBox* box,
702     const RenderRegion* newStartRegion, const RenderRegion* newEndRegion,
703     const RenderRegion* oldStartRegion, const RenderRegion* oldEndRegion)
704 {
705     ASSERT(newStartRegion && newEndRegion && oldStartRegion && oldEndRegion);
706
707     bool insideOldRegionRange = false;
708     bool insideNewRegionRange = false;
709     for (auto& region : m_regionList) {
710         if (oldStartRegion == region)
711             insideOldRegionRange = true;
712         if (newStartRegion == region)
713             insideNewRegionRange = true;
714
715         if (!(insideOldRegionRange && insideNewRegionRange)) {
716             if (region->isRenderNamedFlowFragment())
717                 toRenderNamedFlowFragment(region)->clearObjectStyleInRegion(box);
718             if (region->renderBoxRegionInfo(box))
719                 region->removeRenderBoxRegionInfo(box);
720         }
721
722         if (oldEndRegion == region)
723             insideOldRegionRange = false;
724         if (newEndRegion == region)
725             insideNewRegionRange = false;
726     }
727 }
728
729 void RenderFlowThread::setRegionRangeForBox(const RenderBox* box, RenderRegion* startRegion, RenderRegion* endRegion)
730 {
731     ASSERT(hasRegions());
732     ASSERT(startRegion && endRegion && startRegion->flowThread() == this && endRegion->flowThread() == this);
733
734     auto it = m_regionRangeMap.find(box);
735     if (it == m_regionRangeMap.end()) {
736         m_regionRangeMap.set(box, RenderRegionRange(startRegion, endRegion));
737         return;
738     }
739
740     // If nothing changed, just bail.
741     RenderRegionRange& range = it->value;
742     if (range.startRegion() == startRegion && range.endRegion() == endRegion)
743         return;
744
745     clearRenderBoxRegionInfoAndCustomStyle(box, startRegion, endRegion, range.startRegion(), range.endRegion());
746     range.setRange(startRegion, endRegion);
747 }
748
749 bool RenderFlowThread::hasCachedRegionRangeForBox(const RenderBox* box) const
750 {
751     ASSERT(box);
752
753     return m_regionRangeMap.contains(box);
754 }
755
756 bool RenderFlowThread::getRegionRangeForBoxFromCachedInfo(const RenderBox* box, RenderRegion*& startRegion, RenderRegion*& endRegion) const
757 {
758     ASSERT(box);
759     ASSERT(hasValidRegionInfo());
760     ASSERT((startRegion == nullptr) && (endRegion == nullptr));
761
762     auto it = m_regionRangeMap.find(box);
763     if (it != m_regionRangeMap.end()) {
764         const RenderRegionRange& range = it->value;
765         startRegion = range.startRegion();
766         endRegion = range.endRegion();
767         ASSERT(m_regionList.contains(startRegion) && m_regionList.contains(endRegion));
768         return true;
769     }
770
771     return false;
772 }
773
774 bool RenderFlowThread::getRegionRangeForBox(const RenderBox* box, RenderRegion*& startRegion, RenderRegion*& endRegion) const
775 {
776     ASSERT(box);
777
778     startRegion = endRegion = nullptr;
779     if (!hasValidRegionInfo()) // We clear the ranges when we invalidate the regions.
780         return false;
781
782     if (m_regionList.size() == 1) {
783         startRegion = endRegion = m_regionList.first();
784         return true;
785     }
786
787     if (getRegionRangeForBoxFromCachedInfo(box, startRegion, endRegion))
788         return true;
789
790     return false;
791 }
792
793 bool RenderFlowThread::computedRegionRangeForBox(const RenderBox* box, RenderRegion*& startRegion, RenderRegion*& endRegion) const
794 {
795     ASSERT(box);
796
797     startRegion = endRegion = nullptr;
798     if (!hasValidRegionInfo()) // We clear the ranges when we invalidate the regions.
799         return false;
800
801     if (getRegionRangeForBox(box, startRegion, endRegion))
802         return true;
803
804     // Search the region range using the information provided by the
805     // containing block chain.
806     RenderBox* cb = const_cast<RenderBox*>(box);
807     while (!cb->isRenderFlowThread()) {
808         InlineElementBox* boxWrapper = cb->inlineBoxWrapper();
809         if (boxWrapper && boxWrapper->root().containingRegion()) {
810             startRegion = endRegion = boxWrapper->root().containingRegion();
811             ASSERT(m_regionList.contains(startRegion));
812             return true;
813         }
814
815         // FIXME: Use the containingBlock() value once we patch all the layout systems to be region range aware
816         // (e.g. if we use containingBlock() the shadow controls of a video element won't get the range from the
817         // video box because it's not a block; they need to be patched separately).
818         ASSERT(cb->parent());
819         cb = &cb->parent()->enclosingBox();
820         ASSERT(cb);
821
822         // If a box doesn't have a cached region range it usually means the box belongs to a line so startRegion should be equal with endRegion.
823         // FIXME: Find the cases when this startRegion should not be equal with endRegion and make sure these boxes have cached region ranges.
824         if (hasCachedRegionRangeForBox(cb)) {
825             startRegion = endRegion = regionAtBlockOffset(cb, box->offsetFromLogicalTopOfFirstPage(), true);
826             return true;
827         }
828     }
829
830     ASSERT_NOT_REACHED();
831     return false;
832 }
833
834 bool RenderFlowThread::regionInRange(const RenderRegion* targetRegion, const RenderRegion* startRegion, const RenderRegion* endRegion) const
835 {
836     ASSERT(targetRegion);
837
838     for (auto it = m_regionList.find(const_cast<RenderRegion*>(startRegion)), end = m_regionList.end(); it != end; ++it) {
839         const RenderRegion* currRegion = *it;
840         if (targetRegion == currRegion)
841             return true;
842         if (currRegion == endRegion)
843             break;
844     }
845
846     return false;
847 }
848
849 bool RenderFlowThread::objectShouldFragmentInFlowRegion(const RenderObject* object, const RenderRegion* region) const
850 {
851     ASSERT(object);
852     ASSERT(region);
853     
854     RenderFlowThread* flowThread = object->flowThreadContainingBlock();
855     if (flowThread != this)
856         return false;
857
858     if (!m_regionList.contains(const_cast<RenderRegion*>(region)))
859         return false;
860     
861     RenderRegion* enclosingBoxStartRegion = nullptr;
862     RenderRegion* enclosingBoxEndRegion = nullptr;
863     // If the box has no range, do not check regionInRange. Boxes inside inlines do not get ranges.
864     // Instead, the containing RootInlineBox will abort when trying to paint inside the wrong region.
865     if (computedRegionRangeForBox(&object->enclosingBox(), enclosingBoxStartRegion, enclosingBoxEndRegion)
866         && !regionInRange(region, enclosingBoxStartRegion, enclosingBoxEndRegion))
867         return false;
868     
869     return object->isBox() || object->isRenderInline();
870 }
871
872 bool RenderFlowThread::objectInFlowRegion(const RenderObject* object, const RenderRegion* region) const
873 {
874     ASSERT(object);
875     ASSERT(region);
876
877     RenderFlowThread* flowThread = object->flowThreadContainingBlock();
878     if (flowThread != this)
879         return false;
880
881     if (!m_regionList.contains(const_cast<RenderRegion*>(region)))
882         return false;
883
884     RenderRegion* enclosingBoxStartRegion = nullptr;
885     RenderRegion* enclosingBoxEndRegion = nullptr;
886     if (!getRegionRangeForBox(&object->enclosingBox(), enclosingBoxStartRegion, enclosingBoxEndRegion))
887         return false;
888
889     if (!regionInRange(region, enclosingBoxStartRegion, enclosingBoxEndRegion))
890         return false;
891
892     if (object->isBox())
893         return true;
894
895     LayoutRect objectABBRect = object->absoluteBoundingBoxRect(true);
896     if (!objectABBRect.width())
897         objectABBRect.setWidth(1);
898     if (!objectABBRect.height())
899         objectABBRect.setHeight(1); 
900     if (objectABBRect.intersects(region->absoluteBoundingBoxRect(true)))
901         return true;
902
903     if (region == lastRegion()) {
904         // If the object does not intersect any of the enclosing box regions
905         // then the object is in last region.
906         for (auto it = m_regionList.find(enclosingBoxStartRegion), end = m_regionList.end(); it != end; ++it) {
907             const RenderRegion* currRegion = *it;
908             if (currRegion == region)
909                 break;
910             if (objectABBRect.intersects(currRegion->absoluteBoundingBoxRect(true)))
911                 return false;
912         }
913         return true;
914     }
915
916     return false;
917 }
918
919 #ifndef NDEBUG
920 bool RenderFlowThread::isAutoLogicalHeightRegionsCountConsistent() const
921 {
922     unsigned autoLogicalHeightRegions = 0;
923     for (const auto& region : m_regionList) {
924         if (region->hasAutoLogicalHeight())
925             autoLogicalHeightRegions++;
926     }
927
928     return autoLogicalHeightRegions == m_autoLogicalHeightRegionsCount;
929 }
930 #endif
931
932 #if !ASSERT_WITH_SECURITY_IMPLICATION_DISABLED
933 bool RenderFlowThread::checkLinesConsistency(const RenderBlockFlow* removedBlock) const
934 {
935     if (!m_lineToRegionMap)
936         return true;
937
938     for (auto& linePair : *m_lineToRegionMap.get()) {
939         const RootInlineBox* line = linePair.key;
940         RenderRegion* region = linePair.value;
941         if (&line->blockFlow() == removedBlock)
942             return false;
943         if (line->blockFlow().flowThreadState() == NotInsideFlowThread)
944             return false;
945         if (!m_regionList.contains(region))
946             return false;
947     }
948
949     return true;
950 }
951 #endif
952
953 void RenderFlowThread::clearLinesToRegionMap()
954 {
955     if (m_lineToRegionMap)
956         m_lineToRegionMap->clear();
957 }
958
959 void RenderFlowThread::deleteLines()
960 {
961     clearLinesToRegionMap();
962     RenderBlockFlow::deleteLines();
963 }
964
965 void RenderFlowThread::willBeDestroyed()
966 {
967     clearLinesToRegionMap();
968     RenderBlockFlow::willBeDestroyed();
969 }
970
971 // During the measure content layout phase of the named flow the regions are initialized with a height equal to their max-height.
972 // This way unforced breaks are automatically placed when a region is full and the content height/position correctly estimated.
973 // Also, the region where a forced break falls is exactly the region found at the forced break offset inside the flow content.
974 void RenderFlowThread::initializeRegionsComputedAutoHeight(RenderRegion* startRegion)
975 {
976     ASSERT(inMeasureContentLayoutPhase());
977     if (!hasAutoLogicalHeightRegions())
978         return;
979
980     for (auto regionIter = startRegion ? m_regionList.find(startRegion) : m_regionList.begin(), end = m_regionList.end(); regionIter != end; ++regionIter) {
981         RenderRegion* region = *regionIter;
982         if (region->hasAutoLogicalHeight()) {
983             RenderNamedFlowFragment* namedFlowFragment = toRenderNamedFlowFragment(region);
984             namedFlowFragment->setComputedAutoHeight(namedFlowFragment->maxPageLogicalHeight());
985         }
986     }
987 }
988
989 void RenderFlowThread::markAutoLogicalHeightRegionsForLayout()
990 {
991     ASSERT(hasAutoLogicalHeightRegions());
992
993     for (auto& region : m_regionList) {
994         if (!region->hasAutoLogicalHeight())
995             continue;
996
997         // FIXME: We need to find a way to avoid marking all the regions ancestors for layout
998         // as we are already inside layout.
999         region->setNeedsLayout();
1000     }
1001 }
1002
1003 void RenderFlowThread::markRegionsForOverflowLayoutIfNeeded()
1004 {
1005     if (!hasRegions())
1006         return;
1007
1008     for (auto& region : m_regionList)
1009         region->setNeedsSimplifiedNormalFlowLayout();
1010 }
1011
1012 void RenderFlowThread::updateRegionsFlowThreadPortionRect(const RenderRegion* lastRegionWithContent)
1013 {
1014     ASSERT(!lastRegionWithContent || (inMeasureContentLayoutPhase() && hasAutoLogicalHeightRegions()));
1015     LayoutUnit logicalHeight = 0;
1016     bool emptyRegionsSegment = false;
1017     // FIXME: Optimize not to clear the interval all the time. This implies manually managing the tree nodes lifecycle.
1018     m_regionIntervalTree.clear();
1019     m_regionIntervalTree.initIfNeeded();
1020     for (auto& region : m_regionList) {
1021         // If we find an empty auto-height region, clear the computedAutoHeight value.
1022         if (emptyRegionsSegment && region->hasAutoLogicalHeight())
1023             toRenderNamedFlowFragment(region)->clearComputedAutoHeight();
1024
1025         LayoutUnit regionLogicalWidth = region->pageLogicalWidth();
1026         LayoutUnit regionLogicalHeight = std::min<LayoutUnit>(RenderFlowThread::maxLogicalHeight() - logicalHeight, region->logicalHeightOfAllFlowThreadContent());
1027
1028         LayoutRect regionRect(style().direction() == LTR ? LayoutUnit() : logicalWidth() - regionLogicalWidth, logicalHeight, regionLogicalWidth, regionLogicalHeight);
1029
1030         region->setFlowThreadPortionRect(isHorizontalWritingMode() ? regionRect : regionRect.transposedRect());
1031
1032         m_regionIntervalTree.add(RegionIntervalTree::createInterval(logicalHeight, logicalHeight + regionLogicalHeight, region));
1033
1034         logicalHeight += regionLogicalHeight;
1035
1036         // Once we find the last region with content the next regions are considered empty.
1037         if (lastRegionWithContent == region)
1038             emptyRegionsSegment = true;
1039     }
1040
1041     ASSERT(!lastRegionWithContent || emptyRegionsSegment);
1042 }
1043
1044 // Even if we require the break to occur at offsetBreakInFlowThread, because regions may have min/max-height values,
1045 // it is possible that the break will occur at a different offset than the original one required.
1046 // offsetBreakAdjustment measures the different between the requested break offset and the current break offset.
1047 bool RenderFlowThread::addForcedRegionBreak(const RenderBlock* block, LayoutUnit offsetBreakInFlowThread, RenderBox* breakChild, bool isBefore, LayoutUnit* offsetBreakAdjustment)
1048 {
1049     // We take breaks into account for height computation for auto logical height regions
1050     // only in the layout phase in which we lay out the flows threads unconstrained
1051     // and we use the content breaks to determine the computed auto height for
1052     // auto logical height regions.
1053     if (!inMeasureContentLayoutPhase())
1054         return false;
1055
1056     // Breaks can come before or after some objects. We need to track these objects, so that if we get
1057     // multiple breaks for the same object (for example because of multiple layouts on the same object),
1058     // we need to invalidate every other region after the old one and start computing from fresh.
1059     RenderBoxToRegionMap& mapToUse = isBefore ? m_breakBeforeToRegionMap : m_breakAfterToRegionMap;
1060     auto iter = mapToUse.find(breakChild);
1061     if (iter != mapToUse.end()) {
1062         auto regionIter = m_regionList.find(iter->value);
1063         ASSERT(regionIter != m_regionList.end());
1064         ASSERT((*regionIter)->hasAutoLogicalHeight());
1065         initializeRegionsComputedAutoHeight(*regionIter);
1066
1067         // We need to update the regions flow thread portion rect because we are going to process
1068         // a break on these regions.
1069         updateRegionsFlowThreadPortionRect();
1070     }
1071
1072     // Simulate a region break at offsetBreakInFlowThread. If it points inside an auto logical height region,
1073     // then it determines the region computed auto height.
1074     RenderRegion* region = regionAtBlockOffset(block, offsetBreakInFlowThread);
1075     if (!region)
1076         return false;
1077
1078     bool lastBreakAfterContent = breakChild == this;
1079     bool hasComputedAutoHeight = false;
1080
1081     LayoutUnit currentRegionOffsetInFlowThread = isHorizontalWritingMode() ? region->flowThreadPortionRect().y() : region->flowThreadPortionRect().x();
1082     LayoutUnit offsetBreakInCurrentRegion = offsetBreakInFlowThread - currentRegionOffsetInFlowThread;
1083
1084     if (region->hasAutoLogicalHeight()) {
1085         RenderNamedFlowFragment* namedFlowFragment = toRenderNamedFlowFragment(region);
1086
1087         // A forced break can appear only in an auto-height region that didn't have a forced break before.
1088         // This ASSERT is a good-enough heuristic to verify the above condition.
1089         ASSERT(namedFlowFragment->maxPageLogicalHeight() == namedFlowFragment->computedAutoHeight());
1090
1091         mapToUse.set(breakChild, namedFlowFragment);
1092
1093         hasComputedAutoHeight = true;
1094
1095         // Compute the region height pretending that the offsetBreakInCurrentRegion is the logicalHeight for the auto-height region.
1096         LayoutUnit regionComputedAutoHeight = namedFlowFragment->constrainContentBoxLogicalHeightByMinMax(offsetBreakInCurrentRegion);
1097
1098         // The new height of this region needs to be smaller than the initial value, the max height. A forced break is the only way to change the initial
1099         // height of an auto-height region besides content ending.
1100         ASSERT(regionComputedAutoHeight <= namedFlowFragment->maxPageLogicalHeight());
1101
1102         namedFlowFragment->setComputedAutoHeight(regionComputedAutoHeight);
1103
1104         currentRegionOffsetInFlowThread += regionComputedAutoHeight;
1105     } else
1106         currentRegionOffsetInFlowThread += isHorizontalWritingMode() ? region->flowThreadPortionRect().height() : region->flowThreadPortionRect().width();
1107
1108     // If the break was found inside an auto-height region its size changed so we need to recompute the flow thread portion rectangles.
1109     // Also, if this is the last break after the content we need to clear the computedAutoHeight value on the last empty regions.
1110     if (hasAutoLogicalHeightRegions() && lastBreakAfterContent)
1111         updateRegionsFlowThreadPortionRect(region);
1112     else if (hasComputedAutoHeight)
1113         updateRegionsFlowThreadPortionRect();
1114
1115     if (offsetBreakAdjustment)
1116         *offsetBreakAdjustment = std::max<LayoutUnit>(0, currentRegionOffsetInFlowThread - offsetBreakInFlowThread);
1117
1118     return hasComputedAutoHeight;
1119 }
1120
1121 void RenderFlowThread::incrementAutoLogicalHeightRegions()
1122 {
1123     if (!m_autoLogicalHeightRegionsCount)
1124         view().flowThreadController().incrementFlowThreadsWithAutoLogicalHeightRegions();
1125     ++m_autoLogicalHeightRegionsCount;
1126 }
1127
1128 void RenderFlowThread::decrementAutoLogicalHeightRegions()
1129 {
1130     ASSERT(m_autoLogicalHeightRegionsCount > 0);
1131     --m_autoLogicalHeightRegionsCount;
1132     if (!m_autoLogicalHeightRegionsCount)
1133         view().flowThreadController().decrementFlowThreadsWithAutoLogicalHeightRegions();
1134 }
1135
1136 void RenderFlowThread::collectLayerFragments(LayerFragments& layerFragments, const LayoutRect& layerBoundingBox, const LayoutRect& dirtyRect)
1137 {
1138     ASSERT(!m_regionsInvalidated);
1139     
1140     for (auto& region : m_regionList)
1141         region->collectLayerFragments(layerFragments, layerBoundingBox, dirtyRect);
1142 }
1143
1144 LayoutRect RenderFlowThread::fragmentsBoundingBox(const LayoutRect& layerBoundingBox)
1145 {
1146     ASSERT(!m_regionsInvalidated);
1147     
1148     LayoutRect result;
1149     for (auto& region : m_regionList) {
1150         LayerFragments fragments;
1151         region->collectLayerFragments(fragments, layerBoundingBox, LayoutRect::infiniteRect());
1152         for (const auto& fragment : fragments) {
1153             LayoutRect fragmentRect(layerBoundingBox);
1154             fragmentRect.intersect(fragment.paginationClip);
1155             fragmentRect.move(fragment.paginationOffset);
1156             result.unite(fragmentRect);
1157         }
1158     }
1159     
1160     return result;
1161 }
1162
1163 bool RenderFlowThread::hasCachedOffsetFromLogicalTopOfFirstRegion(const RenderBox* box) const
1164 {
1165     return m_boxesToOffsetMap.contains(box);
1166 }
1167
1168 LayoutUnit RenderFlowThread::cachedOffsetFromLogicalTopOfFirstRegion(const RenderBox* box) const
1169 {
1170     return m_boxesToOffsetMap.get(box);
1171 }
1172
1173 void RenderFlowThread::setOffsetFromLogicalTopOfFirstRegion(const RenderBox* box, LayoutUnit offset)
1174 {
1175     m_boxesToOffsetMap.set(box, offset);
1176 }
1177
1178 void RenderFlowThread::clearOffsetFromLogicalTopOfFirstRegion(const RenderBox* box)
1179 {
1180     ASSERT(m_boxesToOffsetMap.contains(box));
1181     m_boxesToOffsetMap.remove(box);
1182 }
1183
1184 const RenderBox* RenderFlowThread::currentActiveRenderBox() const
1185 {
1186     if (m_activeObjectsStack.isEmpty())
1187         return nullptr;
1188
1189     const RenderObject* currentObject = m_activeObjectsStack.last();
1190     return is<RenderBox>(*currentObject) ? downcast<RenderBox>(currentObject) : nullptr;
1191 }
1192
1193 void RenderFlowThread::pushFlowThreadLayoutState(const RenderObject& object)
1194 {
1195     m_activeObjectsStack.add(&object);
1196
1197     if (const RenderBox* currentBoxDescendant = currentActiveRenderBox()) {
1198         LayoutState* layoutState = currentBoxDescendant->view().layoutState();
1199         if (layoutState && layoutState->isPaginated()) {
1200             ASSERT(layoutState->m_renderer == currentBoxDescendant);
1201             LayoutSize offsetDelta = layoutState->m_layoutOffset - layoutState->m_pageOffset;
1202             setOffsetFromLogicalTopOfFirstRegion(currentBoxDescendant, currentBoxDescendant->isHorizontalWritingMode() ? offsetDelta.height() : offsetDelta.width());
1203         }
1204     }
1205 }
1206
1207 void RenderFlowThread::popFlowThreadLayoutState()
1208 {
1209     if (const RenderBox* currentBoxDescendant = currentActiveRenderBox()) {
1210         LayoutState* layoutState = currentBoxDescendant->view().layoutState();
1211         if (layoutState && layoutState->isPaginated())
1212             clearOffsetFromLogicalTopOfFirstRegion(currentBoxDescendant);
1213     }
1214
1215     m_activeObjectsStack.removeLast();
1216 }
1217
1218 LayoutUnit RenderFlowThread::offsetFromLogicalTopOfFirstRegion(const RenderBlock* currentBlock) const
1219 {
1220     // First check if we cached the offset for the block if it's an ancestor containing block of the box
1221     // being currently laid out.
1222     if (hasCachedOffsetFromLogicalTopOfFirstRegion(currentBlock))
1223         return cachedOffsetFromLogicalTopOfFirstRegion(currentBlock);
1224
1225     // As a last resort, take the slow path.
1226     LayoutRect blockRect(0, 0, currentBlock->width(), currentBlock->height());
1227     while (currentBlock && !currentBlock->isRenderFlowThread()) {
1228         RenderBlock* containerBlock = currentBlock->containingBlock();
1229         ASSERT(containerBlock);
1230         if (!containerBlock)
1231             return 0;
1232         LayoutPoint currentBlockLocation = currentBlock->location();
1233
1234         if (containerBlock->style().writingMode() != currentBlock->style().writingMode()) {
1235             // We have to put the block rect in container coordinates
1236             // and we have to take into account both the container and current block flipping modes
1237             if (containerBlock->style().isFlippedBlocksWritingMode()) {
1238                 if (containerBlock->isHorizontalWritingMode())
1239                     blockRect.setY(currentBlock->height() - blockRect.maxY());
1240                 else
1241                     blockRect.setX(currentBlock->width() - blockRect.maxX());
1242             }
1243             currentBlock->flipForWritingMode(blockRect);
1244         }
1245         blockRect.moveBy(currentBlockLocation);
1246         currentBlock = containerBlock;
1247     }
1248
1249     return currentBlock->isHorizontalWritingMode() ? blockRect.y() : blockRect.x();
1250 }
1251
1252 void RenderFlowThread::RegionSearchAdapter::collectIfNeeded(const RegionInterval& interval)
1253 {
1254     if (m_result)
1255         return;
1256     if (interval.low() <= m_offset && interval.high() > m_offset)
1257         m_result = interval.data();
1258 }
1259
1260 void RenderFlowThread::mapLocalToContainer(const RenderLayerModelObject* repaintContainer, TransformState& transformState, MapCoordinatesFlags mode, bool* wasFixed) const
1261 {
1262     if (this == repaintContainer)
1263         return;
1264
1265     if (RenderRegion* region = mapFromFlowToRegion(transformState)) {
1266         // FIXME: The cast below is probably not the best solution, we may need to find a better way.
1267         const RenderObject* regionObject = static_cast<const RenderObject*>(region);
1268
1269         // If the repaint container is nullptr, we have to climb up to the RenderView, otherwise swap
1270         // it with the region's repaint container.
1271         repaintContainer = repaintContainer ? region->containerForRepaint() : nullptr;
1272
1273         if (RenderFlowThread* regionFlowThread = region->flowThreadContainingBlock()) {
1274             RenderRegion* startRegion = nullptr;
1275             RenderRegion* endRegion = nullptr;
1276             if (regionFlowThread->getRegionRangeForBox(region, startRegion, endRegion)) {
1277                 CurrentRenderRegionMaintainer regionMaintainer(*startRegion);
1278                 regionObject->mapLocalToContainer(repaintContainer, transformState, mode, wasFixed);
1279                 return;
1280             }
1281         }
1282
1283         regionObject->mapLocalToContainer(repaintContainer, transformState, mode, wasFixed);
1284     }
1285 }
1286
1287 // FIXME: Make this function faster. Walking the render tree is slow, better use a caching mechanism (e.g. |cachedOffsetFromLogicalTopOfFirstRegion|).
1288 LayoutRect RenderFlowThread::mapFromLocalToFlowThread(const RenderBox* box, const LayoutRect& localRect) const
1289 {
1290     LayoutRect boxRect = localRect;
1291
1292     while (box && box != this) {
1293         RenderBlock* containerBlock = box->containingBlock();
1294         ASSERT(containerBlock);
1295         if (!containerBlock)
1296             return LayoutRect();
1297         LayoutPoint currentBoxLocation = box->location();
1298
1299         if (containerBlock->style().writingMode() != box->style().writingMode())
1300             box->flipForWritingMode(boxRect);
1301
1302         boxRect.moveBy(currentBoxLocation);
1303         box = containerBlock;
1304     }
1305
1306     return boxRect;
1307 }
1308
1309 // FIXME: Make this function faster. Walking the render tree is slow, better use a caching mechanism (e.g. |cachedOffsetFromLogicalTopOfFirstRegion|).
1310 LayoutRect RenderFlowThread::mapFromFlowThreadToLocal(const RenderBox* box, const LayoutRect& rect) const
1311 {
1312     LayoutRect localRect = rect;
1313     if (box == this)
1314         return localRect;
1315
1316     RenderBlock* containerBlock = box->containingBlock();
1317     ASSERT(containerBlock);
1318     if (!containerBlock)
1319         return LayoutRect();
1320     localRect = mapFromFlowThreadToLocal(containerBlock, localRect);
1321
1322     LayoutPoint currentBoxLocation = box->location();
1323     localRect.moveBy(-currentBoxLocation);
1324
1325     if (containerBlock->style().writingMode() != box->style().writingMode())
1326         box->flipForWritingMode(localRect);
1327
1328     return localRect;
1329 }
1330
1331 void RenderFlowThread::flipForWritingModeLocalCoordinates(LayoutRect& rect) const
1332 {
1333     if (!style().isFlippedBlocksWritingMode())
1334         return;
1335     
1336     if (isHorizontalWritingMode())
1337         rect.setY(0 - rect.maxY());
1338     else
1339         rect.setX(0 - rect.maxX());
1340 }
1341
1342 void RenderFlowThread::addRegionsVisualEffectOverflow(const RenderBox* box)
1343 {
1344     RenderRegion* startRegion = nullptr;
1345     RenderRegion* endRegion = nullptr;
1346     if (!getRegionRangeForBox(box, startRegion, endRegion))
1347         return;
1348
1349     for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1350         RenderRegion* region = *iter;
1351
1352         LayoutRect borderBox = box->borderBoxRectInRegion(region);
1353         borderBox = box->applyVisualEffectOverflow(borderBox);
1354         borderBox = region->rectFlowPortionForBox(box, borderBox);
1355
1356         region->addVisualOverflowForBox(box, borderBox);
1357         if (region == endRegion)
1358             break;
1359     }
1360 }
1361
1362 void RenderFlowThread::addRegionsVisualOverflowFromTheme(const RenderBlock* block)
1363 {
1364     RenderRegion* startRegion = nullptr;
1365     RenderRegion* endRegion = nullptr;
1366     if (!getRegionRangeForBox(block, startRegion, endRegion))
1367         return;
1368
1369     for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1370         RenderRegion* region = *iter;
1371
1372         LayoutRect borderBox = block->borderBoxRectInRegion(region);
1373         borderBox = region->rectFlowPortionForBox(block, borderBox);
1374
1375         FloatRect inflatedRect = borderBox;
1376         block->theme().adjustRepaintRect(*block, inflatedRect);
1377
1378         region->addVisualOverflowForBox(block, snappedIntRect(LayoutRect(inflatedRect)));
1379         if (region == endRegion)
1380             break;
1381     }
1382 }
1383
1384 void RenderFlowThread::addRegionsOverflowFromChild(const RenderBox* box, const RenderBox* child, const LayoutSize& delta)
1385 {
1386     RenderRegion* startRegion = nullptr;
1387     RenderRegion* endRegion = nullptr;
1388     if (!getRegionRangeForBox(child, startRegion, endRegion))
1389         return;
1390
1391     RenderRegion* containerStartRegion = nullptr;
1392     RenderRegion* containerEndRegion = nullptr;
1393     if (!getRegionRangeForBox(box, containerStartRegion, containerEndRegion))
1394         return;
1395
1396     for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1397         RenderRegion* region = *iter;
1398         if (!regionInRange(region, containerStartRegion, containerEndRegion)) {
1399             if (region == endRegion)
1400                 break;
1401             continue;
1402         }
1403
1404         LayoutRect childLayoutOverflowRect = region->layoutOverflowRectForBoxForPropagation(child);
1405         childLayoutOverflowRect.move(delta);
1406         
1407         // When propagating the layout overflow to the flow thread object, make sure to include
1408         // the logical bottom padding of the scrollable region and the bottom margin of the flowed element.
1409         // In order to behave in a similar manner to the non-regions case, content overflowing the box
1410         // flowed into the region must be painted on top of the region's padding and the box's margin.
1411         // See http://lists.w3.org/Archives/Public/www-style/2014Jan/0089.html
1412         if (box->isRenderNamedFlowThread()) {
1413             ASSERT(box == this);
1414             RenderBlockFlow& fragmentContainer = toRenderNamedFlowFragment(region)->fragmentContainer();
1415             LayoutUnit spacingAfterLayout = fragmentContainer.paddingAfter() + child->marginAfter();
1416             if (isHorizontalWritingMode()) {
1417                 if (fragmentContainer.scrollsOverflowY()) {
1418                     LayoutUnit layoutMaxLogicalY = region->rectFlowPortionForBox(child, child->frameRect()).maxY() + spacingAfterLayout;
1419                     LayoutUnit maxYDiff = layoutMaxLogicalY - childLayoutOverflowRect.maxY();
1420                     if (maxYDiff > 0)
1421                         childLayoutOverflowRect.expand(0, maxYDiff);
1422                 }
1423             } else {
1424                 if (fragmentContainer.scrollsOverflowX()) {
1425                     LayoutUnit layoutMaxLogicalY = region->rectFlowPortionForBox(child, child->frameRect()).maxX() + spacingAfterLayout;
1426                     LayoutUnit maxYDiff = layoutMaxLogicalY - childLayoutOverflowRect.maxX();
1427                     if (maxYDiff > 0)
1428                         childLayoutOverflowRect.expand(maxYDiff, 0);
1429                 }
1430             }
1431         }
1432         
1433         region->addLayoutOverflowForBox(box, childLayoutOverflowRect);
1434
1435         if (child->hasSelfPaintingLayer() || box->hasOverflowClip()) {
1436             if (region == endRegion)
1437                 break;
1438             continue;
1439         }
1440         LayoutRect childVisualOverflowRect = region->visualOverflowRectForBoxForPropagation(*child);
1441         childVisualOverflowRect.move(delta);
1442         region->addVisualOverflowForBox(box, childVisualOverflowRect);
1443
1444         if (region == endRegion)
1445             break;
1446     }
1447 }
1448     
1449 void RenderFlowThread::addRegionsLayoutOverflow(const RenderBox* box, const LayoutRect& layoutOverflow)
1450 {
1451     RenderRegion* startRegion = nullptr;
1452     RenderRegion* endRegion = nullptr;
1453     if (!getRegionRangeForBox(box, startRegion, endRegion))
1454         return;
1455
1456     for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1457         RenderRegion* region = *iter;
1458         LayoutRect layoutOverflowInRegion = region->rectFlowPortionForBox(box, layoutOverflow);
1459
1460         region->addLayoutOverflowForBox(box, layoutOverflowInRegion);
1461
1462         if (region == endRegion)
1463             break;
1464     }
1465 }
1466
1467 void RenderFlowThread::addRegionsVisualOverflow(const RenderBox* box, const LayoutRect& visualOverflow)
1468 {
1469     RenderRegion* startRegion = nullptr;
1470     RenderRegion* endRegion = nullptr;
1471     if (!getRegionRangeForBox(box, startRegion, endRegion))
1472         return;
1473     
1474     for (RenderRegionList::iterator iter = m_regionList.find(startRegion); iter != m_regionList.end(); ++iter) {
1475         RenderRegion* region = *iter;
1476         LayoutRect visualOverflowInRegion = region->rectFlowPortionForBox(box, visualOverflow);
1477         
1478         region->addVisualOverflowForBox(box, visualOverflowInRegion);
1479         
1480         if (region == endRegion)
1481             break;
1482     }
1483 }
1484
1485 void RenderFlowThread::clearRegionsOverflow(const RenderBox* box)
1486 {
1487     RenderRegion* startRegion = nullptr;
1488     RenderRegion* endRegion = nullptr;
1489     if (!getRegionRangeForBox(box, startRegion, endRegion))
1490         return;
1491
1492     for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1493         RenderRegion* region = *iter;
1494         RenderBoxRegionInfo* boxInfo = region->renderBoxRegionInfo(box);
1495         if (boxInfo && boxInfo->overflow())
1496             boxInfo->clearOverflow();
1497
1498         if (region == endRegion)
1499             break;
1500     }
1501 }
1502
1503 RenderRegion* RenderFlowThread::currentRegion() const
1504 {
1505     return m_currentRegionMaintainer ? &m_currentRegionMaintainer->region() : nullptr;
1506 }
1507
1508 ContainingRegionMap& RenderFlowThread::containingRegionMap()
1509 {
1510     if (!m_lineToRegionMap)
1511         m_lineToRegionMap = std::make_unique<ContainingRegionMap>();
1512
1513     return *m_lineToRegionMap.get();
1514 }
1515
1516
1517 } // namespace WebCore