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