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
52namespace WebCore {
53
54RenderFlowThread::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
70PassRef<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
85void 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
93void RenderFlowThread::removeFlowChildInfo(RenderObject* child)
94{
95    if (child->isRenderBlockFlow())
96        removeLineRegionInfo(toRenderBlockFlow(child));
97    if (child->isBox())
98        removeRenderBoxRegionInfo(toRenderBox(child));
99}
100
101void RenderFlowThread::removeRegionFromThread(RenderRegion* renderRegion)
102{
103    ASSERT(renderRegion);
104    m_regionList.remove(renderRegion);
105}
106
107void 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
131void 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
181void 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    CurrentRenderFlowThreadMaintainer currentFlowThreadSetter(this);
201    RenderBlockFlow::layout();
202
203    m_pageLogicalSizeChanged = false;
204
205    // If there are children layers in the RenderFlowThread then we need to make sure that the
206    // composited children layers will land in the right RenderRegions. Also, the parent RenderRegions
207    // will get RenderLayers and become composited as needed.
208    // Note that there's no need to do so for the inline multi-column as we are not moving layers into different
209    // containers, but just adjusting the position of the RenderLayerBacking.
210    if (!m_needsTwoPhasesLayout) {
211        // If we have layers that moved from one region to another, we trigger
212        // a composited layers rebuild in here to make sure that the regions will collect the right layers.
213        if (updateAllLayerToRegionMappings())
214            layer()->compositor().setCompositingLayersNeedRebuild();
215    }
216}
217
218bool RenderFlowThread::hasCompositingRegionDescendant() const
219{
220    for (auto& region : m_regionList) {
221        if (toRenderNamedFlowFragment(region)->layerOwner().layer()->hasCompositingDescendant())
222            return true;
223    }
224
225    return false;
226}
227
228const RenderLayerList* RenderFlowThread::getLayerListForRegion(RenderNamedFlowFragment* region) const
229{
230    ASSERT(m_regionToLayerListMap);
231    auto iterator = m_regionToLayerListMap->find(region);
232    return iterator == m_regionToLayerListMap->end() ? 0 : &iterator->value;
233}
234
235RenderNamedFlowFragment* RenderFlowThread::regionForCompositedLayer(RenderLayer& childLayer)
236{
237    if (childLayer.renderer().fixedPositionedWithNamedFlowContainingBlock())
238        return 0;
239
240    if (childLayer.renderBox()) {
241        RenderRegion* startRegion = nullptr;
242        RenderRegion* endRegion = nullptr;
243        if (getRegionRangeForBox(childLayer.renderBox(), startRegion, endRegion))
244            return toRenderNamedFlowFragment(startRegion);
245    }
246
247    // FIXME: remove this when we'll have region ranges for inlines as well.
248    LayoutPoint flowThreadOffset = flooredLayoutPoint(childLayer.renderer().localToContainerPoint(LayoutPoint(), this, ApplyContainerFlip));
249    return toRenderNamedFlowFragment(regionAtBlockOffset(0, flipForWritingMode(isHorizontalWritingMode() ? flowThreadOffset.y() : flowThreadOffset.x()), true, DisallowRegionAutoGeneration));
250}
251
252RenderNamedFlowFragment* RenderFlowThread::cachedRegionForCompositedLayer(RenderLayer& childLayer) const
253{
254    ASSERT(m_layerToRegionMap);
255    RenderNamedFlowFragment* namedFlowFragment = m_layerToRegionMap->get(&childLayer);
256    ASSERT(!namedFlowFragment || m_regionList.contains(namedFlowFragment));
257    return namedFlowFragment;
258}
259
260void RenderFlowThread::updateLayerToRegionMappings(RenderLayer& layer, LayerToRegionMap& layerToRegionMap, RegionToLayerListMap& regionToLayerListMap, bool& needsLayerUpdate)
261{
262    RenderNamedFlowFragment* region = regionForCompositedLayer(layer);
263    if (!needsLayerUpdate) {
264        // Figure out if we moved this layer from a region to the other.
265        RenderNamedFlowFragment* previousRegion = cachedRegionForCompositedLayer(layer);
266        if (previousRegion != region)
267            needsLayerUpdate = true;
268    }
269
270    if (!region)
271        return;
272
273    layerToRegionMap.set(&layer, region);
274
275    auto iterator = regionToLayerListMap.find(region);
276    RenderLayerList& list = iterator == regionToLayerListMap.end() ? regionToLayerListMap.set(region, RenderLayerList()).iterator->value : iterator->value;
277    ASSERT(!list.contains(&layer));
278    list.append(&layer);
279}
280
281bool RenderFlowThread::updateAllLayerToRegionMappings()
282{
283    if (!collectsGraphicsLayersUnderRegions())
284        return false;
285
286    // We can't use currentFlowThread as it is possible to have interleaved flow threads and the wrong one could be used.
287    // Let each region figure out the proper enclosing flow thread.
288    CurrentRenderFlowThreadDisabler disabler(&view());
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
320bool 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
329void 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
346void 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
364bool 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
371bool RenderFlowThread::shouldRepaint(const LayoutRect& r) const
372{
373    if (view().printing() || r.isEmpty())
374        return false;
375
376    return true;
377}
378
379void 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    // We can't use currentFlowThread as it is possible to have interleaved flow threads and the wrong one could be used.
387    // Let each region figure out the proper enclosing flow thread.
388    CurrentRenderFlowThreadDisabler disabler(&view());
389
390    for (auto& region : m_regionList)
391        region->repaintFlowThreadContent(repaintRect);
392}
393
394RenderRegion* RenderFlowThread::regionAtBlockOffset(const RenderBox* clampBox, LayoutUnit offset, bool extendLastRegion, RegionAutoGenerationPolicy autoGenerationPolicy)
395{
396    ASSERT(!m_regionsInvalidated);
397
398    if (autoGenerationPolicy == AllowRegionAutoGeneration)
399        autoGenerateRegionsToBlockOffset(offset);
400
401    if (m_regionList.isEmpty())
402        return 0;
403
404    if (m_regionList.size() == 1 && extendLastRegion)
405        return m_regionList.first();
406
407    if (offset <= 0)
408        return clampBox ? clampBox->clampToStartAndEndRegions(m_regionList.first()) : m_regionList.first();
409
410    RegionSearchAdapter adapter(offset);
411    m_regionIntervalTree.allOverlapsWithAdapter<RegionSearchAdapter>(adapter);
412
413    // If no region was found, the offset is in the flow thread overflow.
414    // The last region will contain the offset if extendLastRegion is set or if the last region is a set.
415    if (!adapter.result() && (extendLastRegion || m_regionList.last()->isRenderRegionSet()))
416        return clampBox ? clampBox->clampToStartAndEndRegions(m_regionList.last()) : m_regionList.last();
417
418    RenderRegion* region = adapter.result();
419    if (!clampBox)
420        return region;
421    return region ? clampBox->clampToStartAndEndRegions(region) : 0;
422}
423
424LayoutPoint RenderFlowThread::adjustedPositionRelativeToOffsetParent(const RenderBoxModelObject& boxModelObject, const LayoutPoint& startPoint)
425{
426    LayoutPoint referencePoint = startPoint;
427
428    const RenderBlock* objContainingBlock = boxModelObject.containingBlock();
429    // FIXME: This needs to be adapted for different writing modes inside the flow thread.
430    RenderRegion* startRegion = regionAtBlockOffset(objContainingBlock, referencePoint.y());
431    if (startRegion) {
432        // Take into account the offset coordinates of the region.
433        RenderBoxModelObject* startRegionBox = startRegion->isRenderNamedFlowFragment() ? toRenderBoxModelObject(startRegion->parent()) : startRegion;
434        RenderBoxModelObject* currObject = startRegionBox;
435        RenderBoxModelObject* currOffsetParent;
436        while ((currOffsetParent = currObject->offsetParent())) {
437            referencePoint.move(currObject->offsetLeft(), currObject->offsetTop());
438
439            // Since we're looking for the offset relative to the body, we must also
440            // take into consideration the borders of the region's offsetParent.
441            if (currOffsetParent->isBox() && !currOffsetParent->isBody())
442                referencePoint.move(toRenderBox(currOffsetParent)->borderLeft(), toRenderBox(currOffsetParent)->borderTop());
443
444            currObject = currOffsetParent;
445        }
446
447        // We need to check if any of this box's containing blocks start in a different region
448        // and if so, drop the object's top position (which was computed relative to its containing block
449        // and is no longer valid) and recompute it using the region in which it flows as reference.
450        bool wasComputedRelativeToOtherRegion = false;
451        while (objContainingBlock && !objContainingBlock->isRenderNamedFlowThread()) {
452            // Check if this object is in a different region.
453            RenderRegion* parentStartRegion = nullptr;
454            RenderRegion* parentEndRegion = nullptr;
455            if (getRegionRangeForBox(objContainingBlock, parentStartRegion, parentEndRegion) && parentStartRegion != startRegion) {
456                wasComputedRelativeToOtherRegion = true;
457                break;
458            }
459            objContainingBlock = objContainingBlock->containingBlock();
460        }
461
462        if (wasComputedRelativeToOtherRegion) {
463            if (boxModelObject.isBox()) {
464                // Use borderBoxRectInRegion to account for variations such as percentage margins.
465                LayoutRect borderBoxRect = toRenderBox(boxModelObject).borderBoxRectInRegion(startRegion, RenderBox::DoNotCacheRenderBoxRegionInfo);
466                referencePoint.move(borderBoxRect.location().x(), 0);
467            }
468
469            // Get the logical top coordinate of the current object.
470            LayoutUnit top = 0;
471            if (boxModelObject.isRenderBlock())
472                top = toRenderBlock(boxModelObject).offsetFromLogicalTopOfFirstPage();
473            else {
474                if (boxModelObject.containingBlock())
475                    top = boxModelObject.containingBlock()->offsetFromLogicalTopOfFirstPage();
476
477                if (boxModelObject.isBox())
478                    top += toRenderBox(boxModelObject).topLeftLocation().y();
479                else if (boxModelObject.isRenderInline())
480                    top -= toRenderInline(boxModelObject).borderTop();
481            }
482
483            // Get the logical top of the region this object starts in
484            // and compute the object's top, relative to the region's top.
485            LayoutUnit regionLogicalTop = startRegion->pageLogicalTopForOffset(top);
486            LayoutUnit topRelativeToRegion = top - regionLogicalTop;
487            referencePoint.setY(startRegionBox->offsetTop() + topRelativeToRegion);
488
489            // Since the top has been overriden, check if the
490            // relative/sticky positioning must be reconsidered.
491            if (boxModelObject.isRelPositioned())
492                referencePoint.move(0, boxModelObject.relativePositionOffset().height());
493            else if (boxModelObject.isStickyPositioned())
494                referencePoint.move(0, boxModelObject.stickyPositionOffset().height());
495        }
496
497        // Since we're looking for the offset relative to the body, we must also
498        // take into consideration the borders of the region.
499        referencePoint.move(startRegionBox->borderLeft(), startRegionBox->borderTop());
500    }
501
502    return referencePoint;
503}
504
505LayoutUnit RenderFlowThread::pageLogicalTopForOffset(LayoutUnit offset)
506{
507    RenderRegion* region = regionAtBlockOffset(0, offset, false, AllowRegionAutoGeneration);
508    return region ? region->pageLogicalTopForOffset(offset) : LayoutUnit();
509}
510
511LayoutUnit RenderFlowThread::pageLogicalWidthForOffset(LayoutUnit offset)
512{
513    RenderRegion* region = regionAtBlockOffset(0, offset, true, AllowRegionAutoGeneration);
514    return region ? region->pageLogicalWidth() : contentLogicalWidth();
515}
516
517LayoutUnit RenderFlowThread::pageLogicalHeightForOffset(LayoutUnit offset)
518{
519    RenderRegion* region = regionAtBlockOffset(0, offset, false, AllowRegionAutoGeneration);
520    if (!region)
521        return 0;
522
523    return region->pageLogicalHeight();
524}
525
526LayoutUnit RenderFlowThread::pageRemainingLogicalHeightForOffset(LayoutUnit offset, PageBoundaryRule pageBoundaryRule)
527{
528    RenderRegion* region = regionAtBlockOffset(0, offset, false, AllowRegionAutoGeneration);
529    if (!region)
530        return 0;
531
532    LayoutUnit pageLogicalTop = region->pageLogicalTopForOffset(offset);
533    LayoutUnit pageLogicalHeight = region->pageLogicalHeight();
534    LayoutUnit pageLogicalBottom = pageLogicalTop + pageLogicalHeight;
535    LayoutUnit remainingHeight = pageLogicalBottom - offset;
536    if (pageBoundaryRule == IncludePageBoundary) {
537        // If IncludePageBoundary is set, the line exactly on the top edge of a
538        // region will act as being part of the previous region.
539        remainingHeight = intMod(remainingHeight, pageLogicalHeight);
540    }
541    return remainingHeight;
542}
543
544RenderRegion* RenderFlowThread::mapFromFlowToRegion(TransformState& transformState) const
545{
546    if (!hasValidRegionInfo())
547        return 0;
548
549    RenderRegion* renderRegion = currentRegion();
550    if (!renderRegion) {
551        LayoutRect boxRect = transformState.mappedQuad().enclosingBoundingBox();
552        flipForWritingMode(boxRect);
553
554        LayoutPoint center = boxRect.center();
555        renderRegion = const_cast<RenderFlowThread*>(this)->regionAtBlockOffset(this, isHorizontalWritingMode() ? center.y() : center.x(), true, DisallowRegionAutoGeneration);
556        if (!renderRegion)
557            return 0;
558    }
559
560    LayoutRect flippedRegionRect(renderRegion->flowThreadPortionRect());
561    flipForWritingMode(flippedRegionRect);
562
563    transformState.move(renderRegion->contentBoxRect().location() - flippedRegionRect.location());
564
565    return renderRegion;
566}
567
568void RenderFlowThread::removeRenderBoxRegionInfo(RenderBox* box)
569{
570    if (!hasRegions())
571        return;
572
573    // If the region chain was invalidated the next layout will clear the box information from all the regions.
574    if (m_regionsInvalidated) {
575        ASSERT(selfNeedsLayout());
576        return;
577    }
578
579    RenderRegion* startRegion = nullptr;
580    RenderRegion* endRegion = nullptr;
581    if (getRegionRangeForBox(box, startRegion, endRegion)) {
582        for (auto it = m_regionList.find(startRegion), end = m_regionList.end(); it != end; ++it) {
583            RenderRegion* region = *it;
584            region->removeRenderBoxRegionInfo(box);
585            if (region == endRegion)
586                break;
587        }
588    }
589
590#ifndef NDEBUG
591    // We have to make sure we did not leave any RenderBoxRegionInfo attached.
592    for (auto& region : m_regionList)
593        ASSERT(!region->renderBoxRegionInfo(box));
594#endif
595
596    m_regionRangeMap.remove(box);
597}
598
599void RenderFlowThread::removeLineRegionInfo(const RenderBlockFlow* blockFlow)
600{
601    if (!m_lineToRegionMap || blockFlow->m_lineLayoutPath == SimpleLinesPath)
602        return;
603
604    for (RootInlineBox* curr = blockFlow->firstRootBox(); curr; curr = curr->nextRootBox()) {
605        if (m_lineToRegionMap->contains(curr))
606            m_lineToRegionMap->remove(curr);
607    }
608
609    ASSERT_WITH_SECURITY_IMPLICATION(checkLinesConsistency(blockFlow));
610}
611
612void RenderFlowThread::logicalWidthChangedInRegionsForBlock(const RenderBlock* block, bool& relayoutChildren)
613{
614    if (!hasValidRegionInfo()) {
615        // FIXME: Remove once we stop laying out flow threads without regions.
616        // If we had regions but don't any more, relayout the children because the code below
617        // can't properly detect this scenario.
618        relayoutChildren |= previousRegionCountChanged();
619        return;
620    }
621
622    auto it = m_regionRangeMap.find(block);
623    if (it == m_regionRangeMap.end())
624        return;
625
626    RenderRegionRange& range = it->value;
627    bool rangeInvalidated = range.rangeInvalidated();
628    range.clearRangeInvalidated();
629
630    // If there will be a relayout anyway skip the next steps because they only verify
631    // the state of the ranges.
632    if (relayoutChildren)
633        return;
634
635    // Not necessary for the flow thread, since we already computed the correct info for it.
636    // If the regions have changed invalidate the children.
637    if (block == this) {
638        relayoutChildren = m_pageLogicalSizeChanged;
639        return;
640    }
641
642    RenderRegion* startRegion = nullptr;
643    RenderRegion* endRegion = nullptr;
644    if (!getRegionRangeForBox(block, startRegion, endRegion))
645        return;
646
647    for (auto it = m_regionList.find(startRegion), end = m_regionList.end(); it != end; ++it) {
648        RenderRegion* region = *it;
649        ASSERT(!region->needsLayout() || region->isRenderRegionSet());
650
651        // We have no information computed for this region so we need to do it.
652        std::unique_ptr<RenderBoxRegionInfo> oldInfo = region->takeRenderBoxRegionInfo(block);
653        if (!oldInfo) {
654            relayoutChildren = rangeInvalidated;
655            return;
656        }
657
658        LayoutUnit oldLogicalWidth = oldInfo->logicalWidth();
659        RenderBoxRegionInfo* newInfo = block->renderBoxRegionInfo(region);
660        if (!newInfo || newInfo->logicalWidth() != oldLogicalWidth) {
661            relayoutChildren = true;
662            return;
663        }
664
665        if (region == endRegion)
666            break;
667    }
668}
669
670LayoutUnit RenderFlowThread::contentLogicalWidthOfFirstRegion() const
671{
672    RenderRegion* firstValidRegionInFlow = firstRegion();
673    if (!firstValidRegionInFlow)
674        return 0;
675    return isHorizontalWritingMode() ? firstValidRegionInFlow->contentWidth() : firstValidRegionInFlow->contentHeight();
676}
677
678LayoutUnit RenderFlowThread::contentLogicalHeightOfFirstRegion() const
679{
680    RenderRegion* firstValidRegionInFlow = firstRegion();
681    if (!firstValidRegionInFlow)
682        return 0;
683    return isHorizontalWritingMode() ? firstValidRegionInFlow->contentHeight() : firstValidRegionInFlow->contentWidth();
684}
685
686LayoutUnit RenderFlowThread::contentLogicalLeftOfFirstRegion() const
687{
688    RenderRegion* firstValidRegionInFlow = firstRegion();
689    if (!firstValidRegionInFlow)
690        return 0;
691    return isHorizontalWritingMode() ? firstValidRegionInFlow->flowThreadPortionRect().x() : firstValidRegionInFlow->flowThreadPortionRect().y();
692}
693
694RenderRegion* RenderFlowThread::firstRegion() const
695{
696    if (!hasRegions())
697        return 0;
698    return m_regionList.first();
699}
700
701RenderRegion* RenderFlowThread::lastRegion() const
702{
703    if (!hasRegions())
704        return 0;
705    return m_regionList.last();
706}
707
708void RenderFlowThread::clearRenderBoxRegionInfoAndCustomStyle(const RenderBox* box,
709    const RenderRegion* newStartRegion, const RenderRegion* newEndRegion,
710    const RenderRegion* oldStartRegion, const RenderRegion* oldEndRegion)
711{
712    ASSERT(newStartRegion && newEndRegion && oldStartRegion && oldEndRegion);
713
714    bool insideOldRegionRange = false;
715    bool insideNewRegionRange = false;
716    for (auto& region : m_regionList) {
717        if (oldStartRegion == region)
718            insideOldRegionRange = true;
719        if (newStartRegion == region)
720            insideNewRegionRange = true;
721
722        if (!(insideOldRegionRange && insideNewRegionRange)) {
723            if (region->isRenderNamedFlowFragment())
724                toRenderNamedFlowFragment(region)->clearObjectStyleInRegion(box);
725            if (region->renderBoxRegionInfo(box))
726                region->removeRenderBoxRegionInfo(box);
727        }
728
729        if (oldEndRegion == region)
730            insideOldRegionRange = false;
731        if (newEndRegion == region)
732            insideNewRegionRange = false;
733    }
734}
735
736void RenderFlowThread::setRegionRangeForBox(const RenderBox* box, RenderRegion* startRegion, RenderRegion* endRegion)
737{
738    ASSERT(hasRegions());
739    ASSERT(startRegion && endRegion && startRegion->flowThread() == this && endRegion->flowThread() == this);
740
741    auto it = m_regionRangeMap.find(box);
742    if (it == m_regionRangeMap.end()) {
743        m_regionRangeMap.set(box, RenderRegionRange(startRegion, endRegion));
744        return;
745    }
746
747    // If nothing changed, just bail.
748    RenderRegionRange& range = it->value;
749    if (range.startRegion() == startRegion && range.endRegion() == endRegion)
750        return;
751
752    clearRenderBoxRegionInfoAndCustomStyle(box, startRegion, endRegion, range.startRegion(), range.endRegion());
753    range.setRange(startRegion, endRegion);
754}
755
756bool RenderFlowThread::hasCachedRegionRangeForBox(const RenderBox* box) const
757{
758    ASSERT(box);
759
760    return m_regionRangeMap.contains(box);
761}
762
763bool RenderFlowThread::getRegionRangeForBoxFromCachedInfo(const RenderBox* box, RenderRegion*& startRegion, RenderRegion*& endRegion) const
764{
765    ASSERT(box);
766    ASSERT(hasValidRegionInfo());
767    ASSERT((startRegion == nullptr) && (endRegion == nullptr));
768
769    auto it = m_regionRangeMap.find(box);
770    if (it != m_regionRangeMap.end()) {
771        const RenderRegionRange& range = it->value;
772        startRegion = range.startRegion();
773        endRegion = range.endRegion();
774        ASSERT(m_regionList.contains(startRegion) && m_regionList.contains(endRegion));
775        return true;
776    }
777
778    return false;
779}
780
781bool RenderFlowThread::getRegionRangeForBox(const RenderBox* box, RenderRegion*& startRegion, RenderRegion*& endRegion) const
782{
783    ASSERT(box);
784
785    startRegion = endRegion = nullptr;
786    if (!hasValidRegionInfo()) // We clear the ranges when we invalidate the regions.
787        return false;
788
789    if (m_regionList.size() == 1) {
790        startRegion = endRegion = m_regionList.first();
791        return true;
792    }
793
794    if (getRegionRangeForBoxFromCachedInfo(box, startRegion, endRegion))
795        return true;
796
797    return false;
798}
799
800bool RenderFlowThread::computedRegionRangeForBox(const RenderBox* box, RenderRegion*& startRegion, RenderRegion*& endRegion) const
801{
802    ASSERT(box);
803
804    startRegion = endRegion = nullptr;
805    if (!hasValidRegionInfo()) // We clear the ranges when we invalidate the regions.
806        return false;
807
808    if (getRegionRangeForBox(box, startRegion, endRegion))
809        return true;
810
811    // Search the region range using the information provided by the
812    // containing block chain.
813    RenderBox* cb = const_cast<RenderBox*>(box);
814    while (!cb->isRenderFlowThread()) {
815        InlineElementBox* boxWrapper = cb->inlineBoxWrapper();
816        if (boxWrapper && boxWrapper->root().containingRegion()) {
817            startRegion = endRegion = boxWrapper->root().containingRegion();
818            ASSERT(m_regionList.contains(startRegion));
819            return true;
820        }
821
822        // FIXME: Use the containingBlock() value once we patch all the layout systems to be region range aware
823        // (e.g. if we use containingBlock() the shadow controls of a video element won't get the range from the
824        // video box because it's not a block; they need to be patched separately).
825        ASSERT(cb->parent());
826        cb = &cb->parent()->enclosingBox();
827        ASSERT(cb);
828
829        // 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.
830        // FIXME: Find the cases when this startRegion should not be equal with endRegion and make sure these boxes have cached region ranges.
831        if (hasCachedRegionRangeForBox(cb)) {
832            startRegion = endRegion = const_cast<RenderFlowThread*>(this)->regionAtBlockOffset(cb, box->offsetFromLogicalTopOfFirstPage(), true, DisallowRegionAutoGeneration);
833            return true;
834        }
835    }
836
837    ASSERT_NOT_REACHED();
838    return false;
839}
840
841bool RenderFlowThread::regionInRange(const RenderRegion* targetRegion, const RenderRegion* startRegion, const RenderRegion* endRegion) const
842{
843    ASSERT(targetRegion);
844
845    for (auto it = m_regionList.find(const_cast<RenderRegion*>(startRegion)), end = m_regionList.end(); it != end; ++it) {
846        const RenderRegion* currRegion = *it;
847        if (targetRegion == currRegion)
848            return true;
849        if (currRegion == endRegion)
850            break;
851    }
852
853    return false;
854}
855
856bool RenderFlowThread::objectShouldFragmentInFlowRegion(const RenderObject* object, const RenderRegion* region) const
857{
858    ASSERT(object);
859    ASSERT(region);
860
861    RenderFlowThread* flowThread = object->flowThreadContainingBlock();
862    if (flowThread != this)
863        return false;
864
865    if (!m_regionList.contains(const_cast<RenderRegion*>(region)))
866        return false;
867
868    RenderRegion* enclosingBoxStartRegion = nullptr;
869    RenderRegion* enclosingBoxEndRegion = nullptr;
870    // If the box has no range, do not check regionInRange. Boxes inside inlines do not get ranges.
871    // Instead, the containing RootInlineBox will abort when trying to paint inside the wrong region.
872    if (computedRegionRangeForBox(&object->enclosingBox(), enclosingBoxStartRegion, enclosingBoxEndRegion)
873        && !regionInRange(region, enclosingBoxStartRegion, enclosingBoxEndRegion))
874        return false;
875
876    return object->isBox() || object->isRenderInline();
877}
878
879bool RenderFlowThread::objectInFlowRegion(const RenderObject* object, const RenderRegion* region) const
880{
881    ASSERT(object);
882    ASSERT(region);
883
884    RenderFlowThread* flowThread = object->flowThreadContainingBlock();
885    if (flowThread != this)
886        return false;
887
888    if (!m_regionList.contains(const_cast<RenderRegion*>(region)))
889        return false;
890
891    RenderRegion* enclosingBoxStartRegion = nullptr;
892    RenderRegion* enclosingBoxEndRegion = nullptr;
893    if (!getRegionRangeForBox(&object->enclosingBox(), enclosingBoxStartRegion, enclosingBoxEndRegion))
894        return false;
895
896    if (!regionInRange(region, enclosingBoxStartRegion, enclosingBoxEndRegion))
897        return false;
898
899    if (object->isBox())
900        return true;
901
902    LayoutRect objectABBRect = object->absoluteBoundingBoxRect(true);
903    if (!objectABBRect.width())
904        objectABBRect.setWidth(1);
905    if (!objectABBRect.height())
906        objectABBRect.setHeight(1);
907    if (objectABBRect.intersects(region->absoluteBoundingBoxRect(true)))
908        return true;
909
910    if (region == lastRegion()) {
911        // If the object does not intersect any of the enclosing box regions
912        // then the object is in last region.
913        for (auto it = m_regionList.find(enclosingBoxStartRegion), end = m_regionList.end(); it != end; ++it) {
914            const RenderRegion* currRegion = *it;
915            if (currRegion == region)
916                break;
917            if (objectABBRect.intersects(currRegion->absoluteBoundingBoxRect(true)))
918                return false;
919        }
920        return true;
921    }
922
923    return false;
924}
925
926#ifndef NDEBUG
927bool RenderFlowThread::isAutoLogicalHeightRegionsCountConsistent() const
928{
929    unsigned autoLogicalHeightRegions = 0;
930    for (const auto& region : m_regionList) {
931        if (region->hasAutoLogicalHeight())
932            autoLogicalHeightRegions++;
933    }
934
935    return autoLogicalHeightRegions == m_autoLogicalHeightRegionsCount;
936}
937#endif
938
939#if !ASSERT_WITH_SECURITY_IMPLICATION_DISABLED
940bool RenderFlowThread::checkLinesConsistency(const RenderBlockFlow* removedBlock) const
941{
942    if (!m_lineToRegionMap)
943        return true;
944
945    for (auto& linePair : *m_lineToRegionMap.get()) {
946        const RootInlineBox* line = linePair.key;
947        RenderRegion* region = linePair.value;
948        if (&line->blockFlow() == removedBlock)
949            return false;
950        if (line->blockFlow().flowThreadState() == NotInsideFlowThread)
951            return false;
952        if (!m_regionList.contains(region))
953            return false;
954    }
955
956    return true;
957}
958#endif
959
960void RenderFlowThread::clearLinesToRegionMap()
961{
962    if (m_lineToRegionMap)
963        m_lineToRegionMap->clear();
964}
965
966void RenderFlowThread::deleteLines()
967{
968    clearLinesToRegionMap();
969    RenderBlockFlow::deleteLines();
970}
971
972void RenderFlowThread::willBeDestroyed()
973{
974    clearLinesToRegionMap();
975    RenderBlockFlow::willBeDestroyed();
976}
977
978// During the measure content layout phase of the named flow the regions are initialized with a height equal to their max-height.
979// This way unforced breaks are automatically placed when a region is full and the content height/position correctly estimated.
980// Also, the region where a forced break falls is exactly the region found at the forced break offset inside the flow content.
981void RenderFlowThread::initializeRegionsComputedAutoHeight(RenderRegion* startRegion)
982{
983    ASSERT(inMeasureContentLayoutPhase());
984    if (!hasAutoLogicalHeightRegions())
985        return;
986
987    for (auto regionIter = startRegion ? m_regionList.find(startRegion) : m_regionList.begin(), end = m_regionList.end(); regionIter != end; ++regionIter) {
988        RenderRegion* region = *regionIter;
989        if (region->hasAutoLogicalHeight()) {
990            RenderNamedFlowFragment* namedFlowFragment = toRenderNamedFlowFragment(region);
991            namedFlowFragment->setComputedAutoHeight(namedFlowFragment->maxPageLogicalHeight());
992        }
993    }
994}
995
996void RenderFlowThread::markAutoLogicalHeightRegionsForLayout()
997{
998    ASSERT(hasAutoLogicalHeightRegions());
999
1000    for (auto& region : m_regionList) {
1001        if (!region->hasAutoLogicalHeight())
1002            continue;
1003
1004        // FIXME: We need to find a way to avoid marking all the regions ancestors for layout
1005        // as we are already inside layout.
1006        region->setNeedsLayout();
1007    }
1008}
1009
1010void RenderFlowThread::markRegionsForOverflowLayoutIfNeeded()
1011{
1012    if (!hasRegions())
1013        return;
1014
1015    for (auto& region : m_regionList)
1016        region->setNeedsSimplifiedNormalFlowLayout();
1017}
1018
1019void RenderFlowThread::updateRegionsFlowThreadPortionRect(const RenderRegion* lastRegionWithContent)
1020{
1021    ASSERT(!lastRegionWithContent || (inMeasureContentLayoutPhase() && hasAutoLogicalHeightRegions()));
1022    LayoutUnit logicalHeight = 0;
1023    bool emptyRegionsSegment = false;
1024    // FIXME: Optimize not to clear the interval all the time. This implies manually managing the tree nodes lifecycle.
1025    m_regionIntervalTree.clear();
1026    m_regionIntervalTree.initIfNeeded();
1027    for (auto& region : m_regionList) {
1028        // If we find an empty auto-height region, clear the computedAutoHeight value.
1029        if (emptyRegionsSegment && region->hasAutoLogicalHeight())
1030            toRenderNamedFlowFragment(region)->clearComputedAutoHeight();
1031
1032        LayoutUnit regionLogicalWidth = region->pageLogicalWidth();
1033        LayoutUnit regionLogicalHeight = std::min<LayoutUnit>(RenderFlowThread::maxLogicalHeight() - logicalHeight, region->logicalHeightOfAllFlowThreadContent());
1034
1035        LayoutRect regionRect(style().direction() == LTR ? LayoutUnit() : logicalWidth() - regionLogicalWidth, logicalHeight, regionLogicalWidth, regionLogicalHeight);
1036
1037        region->setFlowThreadPortionRect(isHorizontalWritingMode() ? regionRect : regionRect.transposedRect());
1038
1039        m_regionIntervalTree.add(RegionIntervalTree::createInterval(logicalHeight, logicalHeight + regionLogicalHeight, region));
1040
1041        logicalHeight += regionLogicalHeight;
1042
1043        // Once we find the last region with content the next regions are considered empty.
1044        if (lastRegionWithContent == region)
1045            emptyRegionsSegment = true;
1046    }
1047
1048    ASSERT(!lastRegionWithContent || emptyRegionsSegment);
1049}
1050
1051// Even if we require the break to occur at offsetBreakInFlowThread, because regions may have min/max-height values,
1052// it is possible that the break will occur at a different offset than the original one required.
1053// offsetBreakAdjustment measures the different between the requested break offset and the current break offset.
1054bool RenderFlowThread::addForcedRegionBreak(const RenderBlock* block, LayoutUnit offsetBreakInFlowThread, RenderBox* breakChild, bool isBefore, LayoutUnit* offsetBreakAdjustment)
1055{
1056    // We take breaks into account for height computation for auto logical height regions
1057    // only in the layout phase in which we lay out the flows threads unconstrained
1058    // and we use the content breaks to determine the computed auto height for
1059    // auto logical height regions.
1060    if (!inMeasureContentLayoutPhase())
1061        return false;
1062
1063    // Breaks can come before or after some objects. We need to track these objects, so that if we get
1064    // multiple breaks for the same object (for example because of multiple layouts on the same object),
1065    // we need to invalidate every other region after the old one and start computing from fresh.
1066    RenderBoxToRegionMap& mapToUse = isBefore ? m_breakBeforeToRegionMap : m_breakAfterToRegionMap;
1067    auto iter = mapToUse.find(breakChild);
1068    if (iter != mapToUse.end()) {
1069        auto regionIter = m_regionList.find(iter->value);
1070        ASSERT(regionIter != m_regionList.end());
1071        ASSERT((*regionIter)->hasAutoLogicalHeight());
1072        initializeRegionsComputedAutoHeight(*regionIter);
1073
1074        // We need to update the regions flow thread portion rect because we are going to process
1075        // a break on these regions.
1076        updateRegionsFlowThreadPortionRect();
1077    }
1078
1079    // Simulate a region break at offsetBreakInFlowThread. If it points inside an auto logical height region,
1080    // then it determines the region computed auto height.
1081    RenderRegion* region = regionAtBlockOffset(block, offsetBreakInFlowThread);
1082    if (!region)
1083        return false;
1084
1085    bool lastBreakAfterContent = breakChild == this;
1086    bool hasComputedAutoHeight = false;
1087
1088    LayoutUnit currentRegionOffsetInFlowThread = isHorizontalWritingMode() ? region->flowThreadPortionRect().y() : region->flowThreadPortionRect().x();
1089    LayoutUnit offsetBreakInCurrentRegion = offsetBreakInFlowThread - currentRegionOffsetInFlowThread;
1090
1091    if (region->hasAutoLogicalHeight()) {
1092        RenderNamedFlowFragment* namedFlowFragment = toRenderNamedFlowFragment(region);
1093
1094        // A forced break can appear only in an auto-height region that didn't have a forced break before.
1095        // This ASSERT is a good-enough heuristic to verify the above condition.
1096        ASSERT(namedFlowFragment->maxPageLogicalHeight() == namedFlowFragment->computedAutoHeight());
1097
1098        mapToUse.set(breakChild, namedFlowFragment);
1099
1100        hasComputedAutoHeight = true;
1101
1102        // Compute the region height pretending that the offsetBreakInCurrentRegion is the logicalHeight for the auto-height region.
1103        LayoutUnit regionComputedAutoHeight = namedFlowFragment->constrainContentBoxLogicalHeightByMinMax(offsetBreakInCurrentRegion);
1104
1105        // 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
1106        // height of an auto-height region besides content ending.
1107        ASSERT(regionComputedAutoHeight <= namedFlowFragment->maxPageLogicalHeight());
1108
1109        namedFlowFragment->setComputedAutoHeight(regionComputedAutoHeight);
1110
1111        currentRegionOffsetInFlowThread += regionComputedAutoHeight;
1112    } else
1113        currentRegionOffsetInFlowThread += isHorizontalWritingMode() ? region->flowThreadPortionRect().height() : region->flowThreadPortionRect().width();
1114
1115    // If the break was found inside an auto-height region its size changed so we need to recompute the flow thread portion rectangles.
1116    // Also, if this is the last break after the content we need to clear the computedAutoHeight value on the last empty regions.
1117    if (hasAutoLogicalHeightRegions() && lastBreakAfterContent)
1118        updateRegionsFlowThreadPortionRect(region);
1119    else if (hasComputedAutoHeight)
1120        updateRegionsFlowThreadPortionRect();
1121
1122    if (offsetBreakAdjustment)
1123        *offsetBreakAdjustment = std::max<LayoutUnit>(0, currentRegionOffsetInFlowThread - offsetBreakInFlowThread);
1124
1125    return hasComputedAutoHeight;
1126}
1127
1128void RenderFlowThread::incrementAutoLogicalHeightRegions()
1129{
1130    if (!m_autoLogicalHeightRegionsCount)
1131        view().flowThreadController().incrementFlowThreadsWithAutoLogicalHeightRegions();
1132    ++m_autoLogicalHeightRegionsCount;
1133}
1134
1135void RenderFlowThread::decrementAutoLogicalHeightRegions()
1136{
1137    ASSERT(m_autoLogicalHeightRegionsCount > 0);
1138    --m_autoLogicalHeightRegionsCount;
1139    if (!m_autoLogicalHeightRegionsCount)
1140        view().flowThreadController().decrementFlowThreadsWithAutoLogicalHeightRegions();
1141}
1142
1143void RenderFlowThread::collectLayerFragments(LayerFragments& layerFragments, const LayoutRect& layerBoundingBox, const LayoutRect& dirtyRect)
1144{
1145    ASSERT(!m_regionsInvalidated);
1146
1147    for (auto& region : m_regionList)
1148        region->collectLayerFragments(layerFragments, layerBoundingBox, dirtyRect);
1149}
1150
1151LayoutRect RenderFlowThread::fragmentsBoundingBox(const LayoutRect& layerBoundingBox)
1152{
1153    ASSERT(!m_regionsInvalidated);
1154
1155    LayoutRect result;
1156    for (auto& region : m_regionList) {
1157        LayerFragments fragments;
1158        region->collectLayerFragments(fragments, layerBoundingBox, LayoutRect::infiniteRect());
1159        for (const auto& fragment : fragments) {
1160            LayoutRect fragmentRect(layerBoundingBox);
1161            fragmentRect.intersect(fragment.paginationClip);
1162            fragmentRect.move(fragment.paginationOffset);
1163            result.unite(fragmentRect);
1164        }
1165    }
1166
1167    return result;
1168}
1169
1170bool RenderFlowThread::hasCachedOffsetFromLogicalTopOfFirstRegion(const RenderBox* box) const
1171{
1172    return m_boxesToOffsetMap.contains(box);
1173}
1174
1175LayoutUnit RenderFlowThread::cachedOffsetFromLogicalTopOfFirstRegion(const RenderBox* box) const
1176{
1177    return m_boxesToOffsetMap.get(box);
1178}
1179
1180void RenderFlowThread::setOffsetFromLogicalTopOfFirstRegion(const RenderBox* box, LayoutUnit offset)
1181{
1182    m_boxesToOffsetMap.set(box, offset);
1183}
1184
1185void RenderFlowThread::clearOffsetFromLogicalTopOfFirstRegion(const RenderBox* box)
1186{
1187    ASSERT(m_boxesToOffsetMap.contains(box));
1188    m_boxesToOffsetMap.remove(box);
1189}
1190
1191const RenderBox* RenderFlowThread::currentActiveRenderBox() const
1192{
1193    if (m_activeObjectsStack.isEmpty())
1194        return 0;
1195
1196    const RenderObject* currentObject = m_activeObjectsStack.last();
1197    return currentObject->isBox() ? toRenderBox(currentObject) : 0;
1198}
1199
1200void RenderFlowThread::pushFlowThreadLayoutState(const RenderObject& object)
1201{
1202    m_activeObjectsStack.add(&object);
1203
1204    if (const RenderBox* currentBoxDescendant = currentActiveRenderBox()) {
1205        LayoutState* layoutState = currentBoxDescendant->view().layoutState();
1206        if (layoutState && layoutState->isPaginated()) {
1207            ASSERT(layoutState->m_renderer == currentBoxDescendant);
1208            LayoutSize offsetDelta = layoutState->m_layoutOffset - layoutState->m_pageOffset;
1209            setOffsetFromLogicalTopOfFirstRegion(currentBoxDescendant, currentBoxDescendant->isHorizontalWritingMode() ? offsetDelta.height() : offsetDelta.width());
1210        }
1211    }
1212}
1213
1214void RenderFlowThread::popFlowThreadLayoutState()
1215{
1216    if (const RenderBox* currentBoxDescendant = currentActiveRenderBox()) {
1217        LayoutState* layoutState = currentBoxDescendant->view().layoutState();
1218        if (layoutState && layoutState->isPaginated())
1219            clearOffsetFromLogicalTopOfFirstRegion(currentBoxDescendant);
1220    }
1221
1222    m_activeObjectsStack.removeLast();
1223}
1224
1225LayoutUnit RenderFlowThread::offsetFromLogicalTopOfFirstRegion(const RenderBlock* currentBlock) const
1226{
1227    // First check if we cached the offset for the block if it's an ancestor containing block of the box
1228    // being currently laid out.
1229    if (hasCachedOffsetFromLogicalTopOfFirstRegion(currentBlock))
1230        return cachedOffsetFromLogicalTopOfFirstRegion(currentBlock);
1231
1232    // As a last resort, take the slow path.
1233    LayoutRect blockRect(0, 0, currentBlock->width(), currentBlock->height());
1234    while (currentBlock && !currentBlock->isRenderFlowThread()) {
1235        RenderBlock* containerBlock = currentBlock->containingBlock();
1236        ASSERT(containerBlock);
1237        if (!containerBlock)
1238            return 0;
1239        LayoutPoint currentBlockLocation = currentBlock->location();
1240
1241        if (containerBlock->style().writingMode() != currentBlock->style().writingMode()) {
1242            // We have to put the block rect in container coordinates
1243            // and we have to take into account both the container and current block flipping modes
1244            if (containerBlock->style().isFlippedBlocksWritingMode()) {
1245                if (containerBlock->isHorizontalWritingMode())
1246                    blockRect.setY(currentBlock->height() - blockRect.maxY());
1247                else
1248                    blockRect.setX(currentBlock->width() - blockRect.maxX());
1249            }
1250            currentBlock->flipForWritingMode(blockRect);
1251        }
1252        blockRect.moveBy(currentBlockLocation);
1253        currentBlock = containerBlock;
1254    }
1255
1256    return currentBlock->isHorizontalWritingMode() ? blockRect.y() : blockRect.x();
1257}
1258
1259void RenderFlowThread::RegionSearchAdapter::collectIfNeeded(const RegionInterval& interval)
1260{
1261    if (m_result)
1262        return;
1263    if (interval.low() <= m_offset && interval.high() > m_offset)
1264        m_result = interval.data();
1265}
1266
1267void RenderFlowThread::mapLocalToContainer(const RenderLayerModelObject* repaintContainer, TransformState& transformState, MapCoordinatesFlags mode, bool* wasFixed) const
1268{
1269    if (this == repaintContainer)
1270        return;
1271
1272    if (RenderRegion* region = mapFromFlowToRegion(transformState)) {
1273        // FIXME: The cast below is probably not the best solution, we may need to find a better way.
1274        const RenderObject* regionObject = static_cast<const RenderObject*>(region);
1275
1276        // If the repaint container is nullptr, we have to climb up to the RenderView, otherwise swap
1277        // it with the region's repaint container.
1278        repaintContainer = repaintContainer ? region->containerForRepaint() : nullptr;
1279
1280        if (RenderFlowThread* regionFlowThread = region->flowThreadContainingBlock()) {
1281            RenderRegion* startRegion = nullptr;
1282            RenderRegion* endRegion = nullptr;
1283            if (regionFlowThread->getRegionRangeForBox(region, startRegion, endRegion)) {
1284                CurrentRenderRegionMaintainer regionMaintainer(*startRegion);
1285                regionObject->mapLocalToContainer(repaintContainer, transformState, mode, wasFixed);
1286                return;
1287            }
1288        }
1289
1290        regionObject->mapLocalToContainer(repaintContainer, transformState, mode, wasFixed);
1291    }
1292}
1293
1294// FIXME: Make this function faster. Walking the render tree is slow, better use a caching mechanism (e.g. |cachedOffsetFromLogicalTopOfFirstRegion|).
1295LayoutRect RenderFlowThread::mapFromLocalToFlowThread(const RenderBox* box, const LayoutRect& localRect) const
1296{
1297    LayoutRect boxRect = localRect;
1298
1299    while (box && box != this) {
1300        RenderBlock* containerBlock = box->containingBlock();
1301        ASSERT(containerBlock);
1302        if (!containerBlock)
1303            return LayoutRect();
1304        LayoutPoint currentBoxLocation = box->location();
1305
1306        if (containerBlock->style().writingMode() != box->style().writingMode())
1307            box->flipForWritingMode(boxRect);
1308
1309        boxRect.moveBy(currentBoxLocation);
1310        box = containerBlock;
1311    }
1312
1313    return boxRect;
1314}
1315
1316// FIXME: Make this function faster. Walking the render tree is slow, better use a caching mechanism (e.g. |cachedOffsetFromLogicalTopOfFirstRegion|).
1317LayoutRect RenderFlowThread::mapFromFlowThreadToLocal(const RenderBox* box, const LayoutRect& rect) const
1318{
1319    LayoutRect localRect = rect;
1320    if (box == this)
1321        return localRect;
1322
1323    RenderBlock* containerBlock = box->containingBlock();
1324    ASSERT(containerBlock);
1325    if (!containerBlock)
1326        return LayoutRect();
1327    localRect = mapFromFlowThreadToLocal(containerBlock, localRect);
1328
1329    LayoutPoint currentBoxLocation = box->location();
1330    localRect.moveBy(-currentBoxLocation);
1331
1332    if (containerBlock->style().writingMode() != box->style().writingMode())
1333        box->flipForWritingMode(localRect);
1334
1335    return localRect;
1336}
1337
1338void RenderFlowThread::flipForWritingModeLocalCoordinates(LayoutRect& rect) const
1339{
1340    if (!style().isFlippedBlocksWritingMode())
1341        return;
1342
1343    if (isHorizontalWritingMode())
1344        rect.setY(0 - rect.maxY());
1345    else
1346        rect.setX(0 - rect.maxX());
1347}
1348
1349void RenderFlowThread::addRegionsVisualEffectOverflow(const RenderBox* box)
1350{
1351    RenderRegion* startRegion = nullptr;
1352    RenderRegion* endRegion = nullptr;
1353    if (!getRegionRangeForBox(box, startRegion, endRegion))
1354        return;
1355
1356    for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1357        RenderRegion* region = *iter;
1358
1359        LayoutRect borderBox = box->borderBoxRectInRegion(region);
1360        borderBox = box->applyVisualEffectOverflow(borderBox);
1361        borderBox = region->rectFlowPortionForBox(box, borderBox);
1362
1363        region->addVisualOverflowForBox(box, borderBox);
1364        if (region == endRegion)
1365            break;
1366    }
1367}
1368
1369void RenderFlowThread::addRegionsVisualOverflowFromTheme(const RenderBlock* block)
1370{
1371    RenderRegion* startRegion = nullptr;
1372    RenderRegion* endRegion = nullptr;
1373    if (!getRegionRangeForBox(block, startRegion, endRegion))
1374        return;
1375
1376    for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1377        RenderRegion* region = *iter;
1378
1379        LayoutRect borderBox = block->borderBoxRectInRegion(region);
1380        borderBox = region->rectFlowPortionForBox(block, borderBox);
1381
1382        FloatRect inflatedRect = borderBox;
1383        block->theme().adjustRepaintRect(*block, inflatedRect);
1384
1385        region->addVisualOverflowForBox(block, pixelSnappedIntRect(LayoutRect(inflatedRect)));
1386        if (region == endRegion)
1387            break;
1388    }
1389}
1390
1391void RenderFlowThread::addRegionsOverflowFromChild(const RenderBox* box, const RenderBox* child, const LayoutSize& delta)
1392{
1393    RenderRegion* startRegion = nullptr;
1394    RenderRegion* endRegion = nullptr;
1395    if (!getRegionRangeForBox(child, startRegion, endRegion))
1396        return;
1397
1398    RenderRegion* containerStartRegion = nullptr;
1399    RenderRegion* containerEndRegion = nullptr;
1400    if (!getRegionRangeForBox(box, containerStartRegion, containerEndRegion))
1401        return;
1402
1403    for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1404        RenderRegion* region = *iter;
1405        if (!regionInRange(region, containerStartRegion, containerEndRegion)) {
1406            if (region == endRegion)
1407                break;
1408            continue;
1409        }
1410
1411        LayoutRect childLayoutOverflowRect = region->layoutOverflowRectForBoxForPropagation(child);
1412        childLayoutOverflowRect.move(delta);
1413
1414        // When propagating the layout overflow to the flow thread object, make sure to include
1415        // the logical bottom padding of the scrollable region and the bottom margin of the flowed element.
1416        // In order to behave in a similar manner to the non-regions case, content overflowing the box
1417        // flowed into the region must be painted on top of the region's padding and the box's margin.
1418        // See http://lists.w3.org/Archives/Public/www-style/2014Jan/0089.html
1419        if (box->isRenderNamedFlowThread()) {
1420            ASSERT(box == this);
1421            RenderBlockFlow& fragmentContainer = toRenderNamedFlowFragment(region)->fragmentContainer();
1422            LayoutUnit spacingAfterLayout = fragmentContainer.paddingAfter() + child->marginAfter();
1423            if (isHorizontalWritingMode()) {
1424                if (fragmentContainer.scrollsOverflowY()) {
1425                    LayoutUnit layoutMaxLogicalY = region->rectFlowPortionForBox(child, child->frameRect()).maxY() + spacingAfterLayout;
1426                    LayoutUnit maxYDiff = layoutMaxLogicalY - childLayoutOverflowRect.maxY();
1427                    if (maxYDiff > 0)
1428                        childLayoutOverflowRect.expand(0, maxYDiff);
1429                }
1430            } else {
1431                if (fragmentContainer.scrollsOverflowX()) {
1432                    LayoutUnit layoutMaxLogicalY = region->rectFlowPortionForBox(child, child->frameRect()).maxX() + spacingAfterLayout;
1433                    LayoutUnit maxYDiff = layoutMaxLogicalY - childLayoutOverflowRect.maxX();
1434                    if (maxYDiff > 0)
1435                        childLayoutOverflowRect.expand(maxYDiff, 0);
1436                }
1437            }
1438        }
1439
1440        region->addLayoutOverflowForBox(box, childLayoutOverflowRect);
1441
1442        if (child->hasSelfPaintingLayer() || box->hasOverflowClip()) {
1443            if (region == endRegion)
1444                break;
1445            continue;
1446        }
1447        LayoutRect childVisualOverflowRect = region->visualOverflowRectForBoxForPropagation(child);
1448        childVisualOverflowRect.move(delta);
1449        region->addVisualOverflowForBox(box, childVisualOverflowRect);
1450
1451        if (region == endRegion)
1452            break;
1453    }
1454}
1455
1456void RenderFlowThread::addRegionsLayoutOverflow(const RenderBox* box, const LayoutRect& layoutOverflow)
1457{
1458    RenderRegion* startRegion = nullptr;
1459    RenderRegion* endRegion = nullptr;
1460    if (!getRegionRangeForBox(box, startRegion, endRegion))
1461        return;
1462
1463    for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1464        RenderRegion* region = *iter;
1465        LayoutRect layoutOverflowInRegion = region->rectFlowPortionForBox(box, layoutOverflow);
1466
1467        region->addLayoutOverflowForBox(box, layoutOverflowInRegion);
1468
1469        if (region == endRegion)
1470            break;
1471    }
1472}
1473
1474void RenderFlowThread::addRegionsVisualOverflow(const RenderBox* box, const LayoutRect& visualOverflow)
1475{
1476    RenderRegion* startRegion = nullptr;
1477    RenderRegion* endRegion = nullptr;
1478    if (!getRegionRangeForBox(box, startRegion, endRegion))
1479        return;
1480
1481    for (RenderRegionList::iterator iter = m_regionList.find(startRegion); iter != m_regionList.end(); ++iter) {
1482        RenderRegion* region = *iter;
1483        LayoutRect visualOverflowInRegion = region->rectFlowPortionForBox(box, visualOverflow);
1484
1485        region->addVisualOverflowForBox(box, visualOverflowInRegion);
1486
1487        if (region == endRegion)
1488            break;
1489    }
1490}
1491
1492void RenderFlowThread::clearRegionsOverflow(const RenderBox* box)
1493{
1494    RenderRegion* startRegion = nullptr;
1495    RenderRegion* endRegion = nullptr;
1496    if (!getRegionRangeForBox(box, startRegion, endRegion))
1497        return;
1498
1499    for (auto iter = m_regionList.find(startRegion), end = m_regionList.end(); iter != end; ++iter) {
1500        RenderRegion* region = *iter;
1501        RenderBoxRegionInfo* boxInfo = region->renderBoxRegionInfo(box);
1502        if (boxInfo && boxInfo->overflow())
1503            boxInfo->clearOverflow();
1504
1505        if (region == endRegion)
1506            break;
1507    }
1508}
1509
1510RenderRegion* RenderFlowThread::currentRegion() const
1511{
1512    return m_currentRegionMaintainer ? &m_currentRegionMaintainer->region() : nullptr;
1513}
1514
1515ContainingRegionMap& RenderFlowThread::containingRegionMap()
1516{
1517    if (!m_lineToRegionMap)
1518        m_lineToRegionMap = std::make_unique<ContainingRegionMap>();
1519
1520    return *m_lineToRegionMap.get();
1521}
1522
1523CurrentRenderFlowThreadMaintainer::CurrentRenderFlowThreadMaintainer(RenderFlowThread* renderFlowThread)
1524    : m_renderFlowThread(renderFlowThread)
1525    , m_previousRenderFlowThread(0)
1526{
1527    if (!m_renderFlowThread)
1528        return;
1529    FlowThreadController& controller = m_renderFlowThread->view().flowThreadController();
1530    m_previousRenderFlowThread = controller.currentRenderFlowThread();
1531    // Remove the assert so we can use this to change the flow thread context.
1532    // ASSERT(!m_previousRenderFlowThread || !renderFlowThread->isRenderNamedFlowThread());
1533    controller.setCurrentRenderFlowThread(m_renderFlowThread);
1534}
1535
1536CurrentRenderFlowThreadMaintainer::~CurrentRenderFlowThreadMaintainer()
1537{
1538    if (!m_renderFlowThread)
1539        return;
1540    FlowThreadController& controller = m_renderFlowThread->view().flowThreadController();
1541    ASSERT(controller.currentRenderFlowThread() == m_renderFlowThread);
1542    controller.setCurrentRenderFlowThread(m_previousRenderFlowThread);
1543}
1544
1545CurrentRenderFlowThreadDisabler::CurrentRenderFlowThreadDisabler(RenderView* view)
1546    : m_view(view)
1547    , m_renderFlowThread(0)
1548{
1549    m_renderFlowThread = m_view->flowThreadController().currentRenderFlowThread();
1550    if (m_renderFlowThread)
1551        view->flowThreadController().setCurrentRenderFlowThread(0);
1552}
1553
1554CurrentRenderFlowThreadDisabler::~CurrentRenderFlowThreadDisabler()
1555{
1556    if (m_renderFlowThread)
1557        m_view->flowThreadController().setCurrentRenderFlowThread(m_renderFlowThread);
1558}
1559
1560
1561} // namespace WebCore
1562