Use "= default" to denote default constructor or destructor
[WebKit-https.git] / Source / WebCore / rendering / RenderMultiColumnFlow.cpp
1 /*
2  * Copyright (C) 2012 Apple Inc.  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  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS IN..0TERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "RenderMultiColumnFlow.h"
28
29 #include "HitTestResult.h"
30 #include "LayoutState.h"
31 #include "RenderIterator.h"
32 #include "RenderMultiColumnSet.h"
33 #include "RenderMultiColumnSpannerPlaceholder.h"
34 #include "RenderView.h"
35 #include "TransformState.h"
36
37 namespace WebCore {
38
39 bool RenderMultiColumnFlow::gShiftingSpanner = false;
40
41 RenderMultiColumnFlow::RenderMultiColumnFlow(Document& document, RenderStyle&& style)
42     : RenderFragmentedFlow(document, WTFMove(style))
43     , m_spannerMap(std::make_unique<SpannerMap>())
44     , m_lastSetWorkedOn(nullptr)
45     , m_columnCount(1)
46     , m_columnWidth(0)
47     , m_columnHeightAvailable(0)
48     , m_inLayout(false)
49     , m_inBalancingPass(false)
50     , m_needsHeightsRecalculation(false)
51     , m_progressionIsInline(false)
52     , m_progressionIsReversed(false)
53 {
54     setFragmentedFlowState(InsideInFragmentedFlow);
55 }
56
57 RenderMultiColumnFlow::~RenderMultiColumnFlow() = default;
58
59 const char* RenderMultiColumnFlow::renderName() const
60 {    
61     return "RenderMultiColumnFlowThread";
62 }
63
64 RenderMultiColumnSet* RenderMultiColumnFlow::firstMultiColumnSet() const
65 {
66     for (RenderObject* sibling = nextSibling(); sibling; sibling = sibling->nextSibling()) {
67         if (is<RenderMultiColumnSet>(*sibling))
68             return downcast<RenderMultiColumnSet>(sibling);
69     }
70     return nullptr;
71 }
72
73 RenderMultiColumnSet* RenderMultiColumnFlow::lastMultiColumnSet() const
74 {
75     for (RenderObject* sibling = multiColumnBlockFlow()->lastChild(); sibling; sibling = sibling->previousSibling()) {
76         if (is<RenderMultiColumnSet>(*sibling))
77             return downcast<RenderMultiColumnSet>(sibling);
78     }
79     return nullptr;
80 }
81
82 RenderBox* RenderMultiColumnFlow::firstColumnSetOrSpanner() const
83 {
84     if (RenderObject* sibling = nextSibling()) {
85         ASSERT(is<RenderBox>(*sibling));
86         ASSERT(is<RenderMultiColumnSet>(*sibling) || findColumnSpannerPlaceholder(downcast<RenderBox>(sibling)));
87         return downcast<RenderBox>(sibling);
88     }
89     return nullptr;
90 }
91
92 RenderBox* RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(const RenderBox* child)
93 {
94     if (!child)
95         return nullptr;
96     if (RenderObject* sibling = child->nextSibling())
97         return downcast<RenderBox>(sibling);
98     return nullptr;
99 }
100
101 RenderBox* RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(const RenderBox* child)
102 {
103     if (!child)
104         return nullptr;
105     if (RenderObject* sibling = child->previousSibling()) {
106         if (is<RenderFragmentedFlow>(*sibling))
107             return nullptr;
108         return downcast<RenderBox>(sibling);
109     }
110     return nullptr;
111 }
112
113 void RenderMultiColumnFlow::layout()
114 {
115     ASSERT(!m_inLayout);
116     m_inLayout = true;
117     m_lastSetWorkedOn = nullptr;
118     if (RenderBox* first = firstColumnSetOrSpanner()) {
119         if (is<RenderMultiColumnSet>(*first)) {
120             m_lastSetWorkedOn = downcast<RenderMultiColumnSet>(first);
121             m_lastSetWorkedOn->beginFlow(this);
122         }
123     }
124     RenderFragmentedFlow::layout();
125     if (RenderMultiColumnSet* lastSet = lastMultiColumnSet()) {
126         if (!nextColumnSetOrSpannerSiblingOf(lastSet))
127             lastSet->endFlow(this, logicalHeight());
128         lastSet->expandToEncompassFragmentedFlowContentsIfNeeded();
129     }
130     m_inLayout = false;
131     m_lastSetWorkedOn = nullptr;
132 }
133
134 static RenderMultiColumnSet* findSetRendering(const RenderMultiColumnFlow& fragmentedFlow, const RenderObject& renderer)
135 {
136     // Find the set inside which the specified renderer would be rendered.
137     for (auto* multicolSet = fragmentedFlow.firstMultiColumnSet(); multicolSet; multicolSet = multicolSet->nextSiblingMultiColumnSet()) {
138         if (multicolSet->containsRendererInFragmentedFlow(renderer))
139             return multicolSet;
140     }
141     return nullptr;
142 }
143
144 void RenderMultiColumnFlow::addFragmentToThread(RenderFragmentContainer* RenderFragmentContainer)
145 {
146     auto* columnSet = downcast<RenderMultiColumnSet>(RenderFragmentContainer);
147     if (RenderMultiColumnSet* nextSet = columnSet->nextSiblingMultiColumnSet()) {
148         RenderFragmentContainerList::iterator it = m_fragmentList.find(nextSet);
149         ASSERT(it != m_fragmentList.end());
150         m_fragmentList.insertBefore(it, columnSet);
151     } else
152         m_fragmentList.add(columnSet);
153     RenderFragmentContainer->setIsValid(true);
154 }
155
156 void RenderMultiColumnFlow::willBeRemovedFromTree()
157 {
158     // Detach all column sets from the flow thread. Cannot destroy them at this point, since they
159     // are siblings of this object, and there may be pointers to this object's sibling somewhere
160     // further up on the call stack.
161     for (RenderMultiColumnSet* columnSet = firstMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet())
162         columnSet->detachFragment();
163     RenderFragmentedFlow::willBeRemovedFromTree();
164 }
165
166 RenderObject* RenderMultiColumnFlow::resolveMovedChild(RenderObject* child) const
167 {
168     if (!child)
169         return nullptr;
170
171     if (child->style().columnSpan() != ColumnSpanAll || !is<RenderBox>(*child)) {
172         // We only need to resolve for column spanners.
173         return child;
174     }
175     // The renderer for the actual DOM node that establishes a spanner is moved from its original
176     // location in the render tree to becoming a sibling of the column sets. In other words, it's
177     // moved out from the flow thread (and becomes a sibling of it). When we for instance want to
178     // create and insert a renderer for the sibling node immediately preceding the spanner, we need
179     // to map that spanner renderer to the spanner's placeholder, which is where the new inserted
180     // renderer belongs.
181     if (RenderMultiColumnSpannerPlaceholder* placeholder = findColumnSpannerPlaceholder(downcast<RenderBox>(child)))
182         return placeholder;
183
184     // This is an invalid spanner, or its placeholder hasn't been created yet. This happens when
185     // moving an entire subtree into the flow thread, when we are processing the insertion of this
186     // spanner's preceding sibling, and we obviously haven't got as far as processing this spanner
187     // yet.
188     return child;
189 }
190
191 static bool isValidColumnSpanner(const RenderMultiColumnFlow& fragmentedFlow, const RenderObject& descendant)
192 {
193     // We assume that we're inside the flow thread. This function is not to be called otherwise.
194     ASSERT(descendant.isDescendantOf(&fragmentedFlow));
195     // First make sure that the renderer itself has the right properties for becoming a spanner.
196     if (!is<RenderBox>(descendant))
197         return false;
198
199     auto& descendantBox = downcast<RenderBox>(descendant);
200     if (descendantBox.isFloatingOrOutOfFlowPositioned())
201         return false;
202
203     if (descendantBox.style().columnSpan() != ColumnSpanAll)
204         return false;
205
206     auto* parent = descendantBox.parent();
207     if (!is<RenderBlockFlow>(*parent) || parent->childrenInline()) {
208         // Needs to be block-level.
209         return false;
210     }
211     
212     // We need to have the flow thread as the containing block. A spanner cannot break out of the flow thread.
213     auto* enclosingFragmentedFlow = descendantBox.enclosingFragmentedFlow();
214     if (enclosingFragmentedFlow != &fragmentedFlow)
215         return false;
216
217     // This looks like a spanner, but if we're inside something unbreakable, it's not to be treated as one.
218     for (auto* ancestor = descendantBox.containingBlock(); ancestor; ancestor = ancestor->containingBlock()) {
219         if (is<RenderView>(*ancestor))
220             return false;
221         if (is<RenderFragmentedFlow>(*ancestor)) {
222             // Don't allow any intervening non-multicol fragmentation contexts. The spec doesn't say
223             // anything about disallowing this, but it's just going to be too complicated to
224             // implement (not to mention specify behavior).
225             return ancestor == &fragmentedFlow;
226         }
227         // This ancestor (descendent of the fragmentedFlow) will create columns later. The spanner belongs to it.
228         if (is<RenderBlockFlow>(*ancestor) && downcast<RenderBlockFlow>(*ancestor).willCreateColumns())
229             return false;
230         ASSERT(ancestor->style().columnSpan() != ColumnSpanAll || !isValidColumnSpanner(fragmentedFlow, *ancestor));
231         if (ancestor->isUnsplittableForPagination())
232             return false;
233     }
234     ASSERT_NOT_REACHED();
235     return false;
236 }
237
238 static RenderObject* spannerPlacehoderCandidate(const RenderObject& renderer, const RenderMultiColumnFlow& stayWithin)
239 {
240     // Spanner candidate is a next sibling/ancestor's next child within the flow thread and
241     // it is in the same inflow/out-of-flow layout context.
242     if (renderer.isOutOfFlowPositioned())
243         return nullptr;
244
245     ASSERT(renderer.isDescendantOf(&stayWithin));
246     auto* current = &renderer;
247     while (true) {
248         // Skip to the first in-flow sibling.
249         auto* nextSibling = current->nextSibling();
250         while (nextSibling && nextSibling->isOutOfFlowPositioned())
251             nextSibling = nextSibling->nextSibling();
252         if (nextSibling)
253             return nextSibling;
254         // No sibling candidate, jump to the parent and check its siblings.
255         current = current->parent();
256         if (!current || current == &stayWithin || current->isOutOfFlowPositioned())
257             return nullptr;
258     }
259     return nullptr;
260 }
261
262 RenderObject* RenderMultiColumnFlow::processPossibleSpannerDescendant(RenderObject*& subtreeRoot, RenderObject& descendant)
263 {
264     RenderBlockFlow* multicolContainer = multiColumnBlockFlow();
265     RenderObject* nextRendererInFragmentedFlow = spannerPlacehoderCandidate(descendant, *this);
266     RenderObject* insertBeforeMulticolChild = nullptr;
267     RenderObject* nextDescendant = &descendant;
268
269     if (isValidColumnSpanner(*this, descendant)) {
270         // This is a spanner (column-span:all). Such renderers are moved from where they would
271         // otherwise occur in the render tree to becoming a direct child of the multicol container,
272         // so that they live among the column sets. This simplifies the layout implementation, and
273         // basically just relies on regular block layout done by the RenderBlockFlow that
274         // establishes the multicol container.
275         RenderBlockFlow* container = downcast<RenderBlockFlow>(descendant.parent());
276         RenderMultiColumnSet* setToSplit = nullptr;
277         if (nextRendererInFragmentedFlow) {
278             setToSplit = findSetRendering(*this, descendant);
279             if (setToSplit) {
280                 setToSplit->setNeedsLayout();
281                 insertBeforeMulticolChild = setToSplit->nextSibling();
282             }
283         }
284         // Moving a spanner's renderer so that it becomes a sibling of the column sets requires us
285         // to insert an anonymous placeholder in the tree where the spanner's renderer otherwise
286         // would have been. This is needed for a two reasons: We need a way of separating inline
287         // content before and after the spanner, so that it becomes separate line boxes. Secondly,
288         // this placeholder serves as a break point for column sets, so that, when encountered, we
289         // end flowing one column set and move to the next one.
290         auto newPlaceholder = RenderMultiColumnSpannerPlaceholder::createAnonymous(*this, downcast<RenderBox>(descendant), container->style());
291         auto& placeholder = *newPlaceholder;
292         container->addChild(WTFMove(newPlaceholder), descendant.nextSibling());
293         auto takenDescendant = container->takeChild(descendant);
294         
295         // This is a guard to stop an ancestor flow thread from processing the spanner.
296         gShiftingSpanner = true;
297         multicolContainer->RenderBlock::addChild(WTFMove(takenDescendant), insertBeforeMulticolChild);
298         gShiftingSpanner = false;
299         
300         // The spanner has now been moved out from the flow thread, but we don't want to
301         // examine its children anyway. They are all part of the spanner and shouldn't trigger
302         // creation of column sets or anything like that. Continue at its original position in
303         // the tree, i.e. where the placeholder was just put.
304         if (subtreeRoot == &descendant)
305             subtreeRoot = &placeholder;
306         nextDescendant = &placeholder;
307     } else {
308         // This is regular multicol content, i.e. not part of a spanner.
309         if (is<RenderMultiColumnSpannerPlaceholder>(nextRendererInFragmentedFlow)) {
310             // Inserted right before a spanner. Is there a set for us there?
311             RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*nextRendererInFragmentedFlow);
312             if (RenderObject* previous = placeholder.spanner()->previousSibling()) {
313                 if (is<RenderMultiColumnSet>(*previous))
314                     return nextDescendant; // There's already a set there. Nothing to do.
315             }
316             insertBeforeMulticolChild = placeholder.spanner();
317         } else if (RenderMultiColumnSet* lastSet = lastMultiColumnSet()) {
318             // This child is not an immediate predecessor of a spanner, which means that if this
319             // child precedes a spanner at all, there has to be a column set created for us there
320             // already. If it doesn't precede any spanner at all, on the other hand, we need a
321             // column set at the end of the multicol container. We don't really check here if the
322             // child inserted precedes any spanner or not (as that's an expensive operation). Just
323             // make sure we have a column set at the end. It's no big deal if it remains unused.
324             if (!lastSet->nextSibling())
325                 return nextDescendant;
326         }
327     }
328     // Need to create a new column set when there's no set already created. We also always insert
329     // another column set after a spanner. Even if it turns out that there are no renderers
330     // following the spanner, there may be bottom margins there, which take up space.
331     auto newSet = createRenderer<RenderMultiColumnSet>(*this, RenderStyle::createAnonymousStyleWithDisplay(multicolContainer->style(), BLOCK));
332     newSet->initializeStyle();
333     auto& set = *newSet;
334     multicolContainer->RenderBlock::addChild(WTFMove(newSet), insertBeforeMulticolChild);
335     invalidateFragments();
336
337     // We cannot handle immediate column set siblings at the moment (and there's no need for
338     // it, either). There has to be at least one spanner separating them.
339     ASSERT_UNUSED(set, !previousColumnSetOrSpannerSiblingOf(&set) || !previousColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet());
340     ASSERT(!nextColumnSetOrSpannerSiblingOf(&set) || !nextColumnSetOrSpannerSiblingOf(&set)->isRenderMultiColumnSet());
341     
342     return nextDescendant;
343 }
344
345 void RenderMultiColumnFlow::fragmentedFlowDescendantInserted(RenderObject& newDescendant)
346 {
347     if (gShiftingSpanner || newDescendant.isInFlowRenderFragmentedFlow())
348         return;
349
350     Vector<RenderPtr<RenderObject>> spannersToDelete;
351
352     RenderObject* subtreeRoot = &newDescendant;
353     for (auto* descendant = &newDescendant; descendant; descendant = (descendant ? descendant->nextInPreOrder(subtreeRoot) : nullptr)) {
354         if (is<RenderMultiColumnSpannerPlaceholder>(*descendant)) {
355             // A spanner's placeholder has been inserted. The actual spanner renderer is moved from
356             // where it would otherwise occur (if it weren't a spanner) to becoming a sibling of the
357             // column sets.
358             RenderMultiColumnSpannerPlaceholder& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*descendant);
359             if (placeholder.fragmentedFlow() != this) {
360                 // This isn't our spanner! It shifted here from an ancestor multicolumn block. It's going to end up
361                 // becoming our spanner instead, but for it to do that we first have to nuke the original spanner,
362                 // and get the spanner content back into this flow thread.
363                 RenderBox* spanner = placeholder.spanner();
364                 
365                 // Insert after the placeholder, but don't let a notification happen.
366                 gShiftingSpanner = true;
367                 RenderBlockFlow& ancestorBlock = downcast<RenderBlockFlow>(*spanner->parent());
368                 ancestorBlock.moveChildTo(placeholder.parentBox(), spanner, placeholder.nextSibling(), true);
369                 gShiftingSpanner = false;
370                 
371                 // We have to nuke the placeholder, since the ancestor already lost the mapping to it when
372                 // we shifted the placeholder down into this flow thread.
373                 placeholder.fragmentedFlow()->spannerMap().remove(spanner);
374
375                 spannersToDelete.append(placeholder.parent()->takeChild(placeholder));
376
377                 if (subtreeRoot == descendant)
378                     subtreeRoot = spanner;
379                 // Now we process the spanner.
380                 descendant = processPossibleSpannerDescendant(subtreeRoot, *spanner);
381                 continue;
382             }
383             
384             ASSERT(!spannerMap().get(placeholder.spanner()));
385             spannerMap().add(placeholder.spanner(), makeWeakPtr(placeholder));
386             ASSERT(!placeholder.firstChild()); // There should be no children here, but if there are, we ought to skip them.
387             continue;
388         }
389         descendant = processPossibleSpannerDescendant(subtreeRoot, *descendant);
390     }
391 }
392
393 void RenderMultiColumnFlow::handleSpannerRemoval(RenderObject& spanner)
394 {
395     // The placeholder may already have been removed, but if it hasn't, do so now.
396     if (auto placeholder = spannerMap().take(&downcast<RenderBox>(spanner)))
397         placeholder->removeFromParentAndDestroy();
398
399     if (RenderObject* next = spanner.nextSibling()) {
400         if (RenderObject* previous = spanner.previousSibling()) {
401             if (previous->isRenderMultiColumnSet() && next->isRenderMultiColumnSet()) {
402                 // Merge two sets that no longer will be separated by a spanner.
403                 next->removeFromParentAndDestroy();
404                 previous->setNeedsLayout();
405             }
406         }
407     }
408 }
409
410 void RenderMultiColumnFlow::fragmentedFlowRelativeWillBeRemoved(RenderObject& relative)
411 {
412     invalidateFragments();
413     if (is<RenderMultiColumnSpannerPlaceholder>(relative)) {
414         // Remove the map entry for this spanner, but leave the actual spanner renderer alone. Also
415         // keep the reference to the spanner, since the placeholder may be about to be re-inserted
416         // in the tree.
417         ASSERT(relative.isDescendantOf(this));
418         spannerMap().remove(downcast<RenderMultiColumnSpannerPlaceholder>(relative).spanner());
419         return;
420     }
421     if (relative.style().columnSpan() == ColumnSpanAll) {
422         if (relative.parent() != parent())
423             return; // not a valid spanner.
424         
425         handleSpannerRemoval(relative);
426     }
427     // Note that we might end up with empty column sets if all column content is removed. That's no
428     // big deal though (and locating them would be expensive), and they will be found and re-used if
429     // content is added again later.
430 }
431
432 void RenderMultiColumnFlow::fragmentedFlowDescendantBoxLaidOut(RenderBox* descendant)
433 {
434     if (!is<RenderMultiColumnSpannerPlaceholder>(*descendant))
435         return;
436     auto& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*descendant);
437     RenderBlock* container = placeholder.containingBlock();
438
439     for (RenderBox* prev = previousColumnSetOrSpannerSiblingOf(placeholder.spanner()); prev; prev = previousColumnSetOrSpannerSiblingOf(prev)) {
440         if (is<RenderMultiColumnSet>(*prev)) {
441             downcast<RenderMultiColumnSet>(*prev).endFlow(container, placeholder.logicalTop());
442             break;
443         }
444     }
445
446     for (RenderBox* next = nextColumnSetOrSpannerSiblingOf(placeholder.spanner()); next; next = nextColumnSetOrSpannerSiblingOf(next)) {
447         if (is<RenderMultiColumnSet>(*next)) {
448             m_lastSetWorkedOn = downcast<RenderMultiColumnSet>(next);
449             m_lastSetWorkedOn->beginFlow(container);
450             break;
451         }
452     }
453 }
454
455 RenderBox::LogicalExtentComputedValues RenderMultiColumnFlow::computeLogicalHeight(LayoutUnit logicalHeight, LayoutUnit logicalTop) const
456 {
457     // We simply remain at our intrinsic height.
458     return { logicalHeight, logicalTop, ComputedMarginValues() };
459 }
460
461 LayoutUnit RenderMultiColumnFlow::initialLogicalWidth() const
462 {
463     return columnWidth();
464 }
465
466 void RenderMultiColumnFlow::setPageBreak(const RenderBlock* block, LayoutUnit offset, LayoutUnit spaceShortage)
467 {
468     if (auto* multicolSet = downcast<RenderMultiColumnSet>(fragmentAtBlockOffset(block, offset)))
469         multicolSet->recordSpaceShortage(spaceShortage);
470 }
471
472 void RenderMultiColumnFlow::updateMinimumPageHeight(const RenderBlock* block, LayoutUnit offset, LayoutUnit minHeight)
473 {
474     if (auto* multicolSet = downcast<RenderMultiColumnSet>(fragmentAtBlockOffset(block, offset)))
475         multicolSet->updateMinimumColumnHeight(minHeight);
476 }
477
478 RenderFragmentContainer* RenderMultiColumnFlow::fragmentAtBlockOffset(const RenderBox* box, LayoutUnit offset, bool extendLastFragment) const
479 {
480     if (!m_inLayout)
481         return RenderFragmentedFlow::fragmentAtBlockOffset(box, offset, extendLastFragment);
482
483     // Layout in progress. We are calculating the set heights as we speak, so the fragment range
484     // information is not up-to-date.
485
486     RenderMultiColumnSet* columnSet = m_lastSetWorkedOn ? m_lastSetWorkedOn : firstMultiColumnSet();
487     if (!columnSet) {
488         // If there's no set, bail. This multicol is empty or only consists of spanners. There
489         // are no fragments.
490         return nullptr;
491     }
492     // The last set worked on is a good guess. But if we're not within the bounds, search for the
493     // right one.
494     if (offset < columnSet->logicalTopInFragmentedFlow()) {
495         do {
496             if (RenderMultiColumnSet* prev = columnSet->previousSiblingMultiColumnSet())
497                 columnSet = prev;
498             else
499                 break;
500         } while (offset < columnSet->logicalTopInFragmentedFlow());
501     } else {
502         while (offset >= columnSet->logicalBottomInFragmentedFlow()) {
503             RenderMultiColumnSet* next = columnSet->nextSiblingMultiColumnSet();
504             if (!next || !next->hasBeenFlowed())
505                 break;
506             columnSet = next;
507         }
508     }
509     return columnSet;
510 }
511
512 void RenderMultiColumnFlow::setFragmentRangeForBox(const RenderBox& box, RenderFragmentContainer* startFragment, RenderFragmentContainer* endFragment)
513 {
514     // Some column sets may have zero height, which means that two or more sets may start at the
515     // exact same flow thread position, which means that some parts of the code may believe that a
516     // given box lives in sets that it doesn't really live in. Make some adjustments here and
517     // include such sets if they are adjacent to the start and/or end fragments.
518     for (RenderMultiColumnSet* columnSet = downcast<RenderMultiColumnSet>(*startFragment).previousSiblingMultiColumnSet(); columnSet; columnSet = columnSet->previousSiblingMultiColumnSet()) {
519         if (columnSet->logicalHeightInFragmentedFlow())
520             break;
521         startFragment = columnSet;
522     }
523     for (RenderMultiColumnSet* columnSet = downcast<RenderMultiColumnSet>(*startFragment).nextSiblingMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet()) {
524         if (columnSet->logicalHeightInFragmentedFlow())
525             break;
526         endFragment = columnSet;
527     }
528
529     RenderFragmentedFlow::setFragmentRangeForBox(box, startFragment, endFragment);
530 }
531
532 bool RenderMultiColumnFlow::addForcedFragmentBreak(const RenderBlock* block, LayoutUnit offset, RenderBox* /*breakChild*/, bool /*isBefore*/, LayoutUnit* offsetBreakAdjustment)
533 {
534     if (auto* multicolSet = downcast<RenderMultiColumnSet>(fragmentAtBlockOffset(block, offset))) {
535         multicolSet->addForcedBreak(offset);
536         if (offsetBreakAdjustment)
537             *offsetBreakAdjustment = pageLogicalHeightForOffset(offset) ? pageRemainingLogicalHeightForOffset(offset, IncludePageBoundary) : LayoutUnit::fromPixel(0);
538         return true;
539     }
540     return false;
541 }
542
543 void RenderMultiColumnFlow::computeLineGridPaginationOrigin(LayoutState& layoutState) const
544 {
545     if (!progressionIsInline())
546         return;
547     
548     // We need to cache a line grid pagination origin so that we understand how to reset the line grid
549     // at the top of each column.
550     // Get the current line grid and offset.
551     const auto lineGrid = layoutState.lineGrid();
552     if (!lineGrid)
553         return;
554
555     // Get the hypothetical line box used to establish the grid.
556     auto lineGridBox = lineGrid->lineGridBox();
557     if (!lineGridBox)
558         return;
559     
560     bool isHorizontalWritingMode = lineGrid->isHorizontalWritingMode();
561
562     LayoutUnit lineGridBlockOffset = isHorizontalWritingMode ? layoutState.lineGridOffset().height() : layoutState.lineGridOffset().width();
563
564     // Now determine our position on the grid. Our baseline needs to be adjusted to the nearest baseline multiple
565     // as established by the line box.
566     // FIXME: Need to handle crazy line-box-contain values that cause the root line box to not be considered. I assume
567     // the grid should honor line-box-contain.
568     LayoutUnit gridLineHeight = lineGridBox->lineBottomWithLeading() - lineGridBox->lineTopWithLeading();
569     if (!gridLineHeight)
570         return;
571
572     LayoutUnit firstLineTopWithLeading = lineGridBlockOffset + lineGridBox->lineTopWithLeading();
573     
574     if (layoutState.isPaginated() && layoutState.pageLogicalHeight()) {
575         LayoutUnit pageLogicalTop = isHorizontalWritingMode ? layoutState.pageOffset().height() : layoutState.pageOffset().width();
576         if (pageLogicalTop > firstLineTopWithLeading) {
577             // Shift to the next highest line grid multiple past the page logical top. Cache the delta
578             // between this new value and the page logical top as the pagination origin.
579             LayoutUnit remainder = roundToInt(pageLogicalTop - firstLineTopWithLeading) % roundToInt(gridLineHeight);
580             LayoutUnit paginationDelta = gridLineHeight - remainder;
581             if (isHorizontalWritingMode)
582                 layoutState.setLineGridPaginationOrigin(LayoutSize(layoutState.lineGridPaginationOrigin().width(), paginationDelta));
583             else
584                 layoutState.setLineGridPaginationOrigin(LayoutSize(paginationDelta, layoutState.lineGridPaginationOrigin().height()));
585         }
586     }
587 }
588
589 LayoutSize RenderMultiColumnFlow::offsetFromContainer(RenderElement& enclosingContainer, const LayoutPoint& physicalPoint, bool* offsetDependsOnPoint) const
590 {
591     ASSERT(&enclosingContainer == container());
592
593     if (offsetDependsOnPoint)
594         *offsetDependsOnPoint = true;
595     
596     LayoutPoint translatedPhysicalPoint(physicalPoint);
597     if (RenderFragmentContainer* fragment = physicalTranslationFromFlowToFragment(translatedPhysicalPoint))
598         translatedPhysicalPoint.moveBy(fragment->topLeftLocation());
599     
600     LayoutSize offset(translatedPhysicalPoint.x(), translatedPhysicalPoint.y());
601     if (is<RenderBox>(enclosingContainer))
602         offset -= toLayoutSize(downcast<RenderBox>(enclosingContainer).scrollPosition());
603     return offset;
604 }
605     
606 void RenderMultiColumnFlow::mapAbsoluteToLocalPoint(MapCoordinatesFlags mode, TransformState& transformState) const
607 {
608     // First get the transform state's point into the block flow thread's physical coordinate space.
609     parent()->mapAbsoluteToLocalPoint(mode, transformState);
610     LayoutPoint transformPoint(transformState.mappedPoint());
611     
612     // Now walk through each fragment.
613     const RenderMultiColumnSet* candidateColumnSet = nullptr;
614     LayoutPoint candidatePoint;
615     LayoutSize candidateContainerOffset;
616     
617     for (const auto& columnSet : childrenOfType<RenderMultiColumnSet>(*parent())) {
618         candidateContainerOffset = columnSet.offsetFromContainer(*parent(), LayoutPoint());
619         
620         candidatePoint = transformPoint - candidateContainerOffset;
621         candidateColumnSet = &columnSet;
622         
623         // We really have no clue what to do with overflow. We'll just use the closest fragment to the point in that case.
624         LayoutUnit pointOffset = isHorizontalWritingMode() ? candidatePoint.y() : candidatePoint.x();
625         LayoutUnit fragmentOffset = isHorizontalWritingMode() ? columnSet.topLeftLocation().y() : columnSet.topLeftLocation().x();
626         if (pointOffset < fragmentOffset + columnSet.logicalHeight())
627             break;
628     }
629     
630     // Once we have a good guess as to which fragment we hit tested through (and yes, this was just a heuristic, but it's
631     // the best we could do), then we can map from the fragment into the flow thread.
632     LayoutSize translationOffset = physicalTranslationFromFragmentToFlow(candidateColumnSet, candidatePoint) + candidateContainerOffset;
633     bool preserve3D = mode & UseTransforms && (parent()->style().preserves3D() || style().preserves3D());
634     if (mode & UseTransforms && shouldUseTransformFromContainer(parent())) {
635         TransformationMatrix t;
636         getTransformFromContainer(parent(), translationOffset, t);
637         transformState.applyTransform(t, preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
638     } else
639         transformState.move(translationOffset.width(), translationOffset.height(), preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
640 }
641
642 LayoutSize RenderMultiColumnFlow::physicalTranslationFromFragmentToFlow(const RenderMultiColumnSet* columnSet, const LayoutPoint& physicalPoint) const
643 {
644     LayoutPoint logicalPoint = columnSet->flipForWritingMode(physicalPoint);
645     LayoutPoint translatedPoint = columnSet->translateFragmentPointToFragmentedFlow(logicalPoint);
646     LayoutPoint physicalTranslatedPoint = columnSet->flipForWritingMode(translatedPoint);
647     return physicalPoint - physicalTranslatedPoint;
648 }
649
650 RenderFragmentContainer* RenderMultiColumnFlow::mapFromFlowToFragment(TransformState& transformState) const
651 {
652     if (!hasValidFragmentInfo())
653         return nullptr;
654
655     // Get back into our local flow thread space.
656     LayoutRect boxRect = transformState.mappedQuad().enclosingBoundingBox();
657     flipForWritingMode(boxRect);
658
659     // FIXME: We need to refactor RenderObject::absoluteQuads to be able to split the quads across fragments,
660     // for now we just take the center of the mapped enclosing box and map it to a column.
661     LayoutPoint centerPoint = boxRect.center();
662     LayoutUnit centerLogicalOffset = isHorizontalWritingMode() ? centerPoint.y() : centerPoint.x();
663     RenderFragmentContainer* RenderFragmentContainer = fragmentAtBlockOffset(this, centerLogicalOffset, true);
664     if (!RenderFragmentContainer)
665         return nullptr;
666     transformState.move(physicalTranslationOffsetFromFlowToFragment(RenderFragmentContainer, centerLogicalOffset));
667     return RenderFragmentContainer;
668 }
669
670 LayoutSize RenderMultiColumnFlow::physicalTranslationOffsetFromFlowToFragment(const RenderFragmentContainer* RenderFragmentContainer, const LayoutUnit logicalOffset) const
671 {
672     // Now that we know which multicolumn set we hit, we need to get the appropriate translation offset for the column.
673     const auto* columnSet = downcast<RenderMultiColumnSet>(RenderFragmentContainer);
674     LayoutPoint translationOffset = columnSet->columnTranslationForOffset(logicalOffset);
675     
676     // Now we know how we want the rect to be translated into the fragment. At this point we're converting
677     // back to physical coordinates.
678     if (style().isFlippedBlocksWritingMode()) {
679         LayoutRect portionRect(columnSet->fragmentedFlowPortionRect());
680         LayoutRect columnRect = columnSet->columnRectAt(0);
681         LayoutUnit physicalDeltaFromPortionBottom = logicalHeight() - columnSet->logicalBottomInFragmentedFlow();
682         if (isHorizontalWritingMode())
683             columnRect.setHeight(portionRect.height());
684         else
685             columnRect.setWidth(portionRect.width());
686         columnSet->flipForWritingMode(columnRect);
687         if (isHorizontalWritingMode())
688             translationOffset.move(0, columnRect.y() - portionRect.y() - physicalDeltaFromPortionBottom);
689         else
690             translationOffset.move(columnRect.x() - portionRect.x() - physicalDeltaFromPortionBottom, 0);
691     }
692     
693     return LayoutSize(translationOffset.x(), translationOffset.y());
694 }
695
696 RenderFragmentContainer* RenderMultiColumnFlow::physicalTranslationFromFlowToFragment(LayoutPoint& physicalPoint) const
697 {
698     if (!hasValidFragmentInfo())
699         return nullptr;
700     
701     // Put the physical point into the flow thread's coordinate space.
702     LayoutPoint logicalPoint = flipForWritingMode(physicalPoint);
703     
704     // Now get the fragment that we are in.
705     LayoutUnit logicalOffset = isHorizontalWritingMode() ? logicalPoint.y() : logicalPoint.x();
706     RenderFragmentContainer* RenderFragmentContainer = fragmentAtBlockOffset(this, logicalOffset, true);
707     if (!RenderFragmentContainer)
708         return nullptr;
709     
710     // Translate to the coordinate space of the fragment.
711     LayoutSize translationOffset = physicalTranslationOffsetFromFlowToFragment(RenderFragmentContainer, logicalOffset);
712     
713     // Now shift the physical point into the fragment's coordinate space.
714     physicalPoint += translationOffset;
715     
716     return RenderFragmentContainer;
717 }
718
719 bool RenderMultiColumnFlow::isPageLogicalHeightKnown() const
720 {
721     if (RenderMultiColumnSet* columnSet = lastMultiColumnSet())
722         return columnSet->columnHeightComputed();
723     return false;
724 }
725
726 bool RenderMultiColumnFlow::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction)
727 {
728     // You cannot be inside an in-flow RenderFragmentedFlow without a corresponding DOM node. It's better to
729     // just let the ancestor figure out where we are instead.
730     if (hitTestAction == HitTestBlockBackground)
731         return false;
732     bool inside = RenderFragmentedFlow::nodeAtPoint(request, result, locationInContainer, accumulatedOffset, hitTestAction);
733     if (inside && !result.innerNode())
734         return false;
735     return inside;
736 }
737
738 bool RenderMultiColumnFlow::shouldCheckColumnBreaks() const
739 {
740     if (!parent()->isRenderView())
741         return true;
742     return view().frameView().pagination().behavesLikeColumns;
743 }
744
745 }