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