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