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