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