9bb9a539d6642df90026a782af8cf84dc49da2a9
[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 "RenderIterator.h"
31 #include "RenderLayoutState.h"
32 #include "RenderMultiColumnSet.h"
33 #include "RenderMultiColumnSpannerPlaceholder.h"
34 #include "RenderTreeBuilder.h"
35 #include "RenderView.h"
36 #include "TransformState.h"
37 #include <wtf/IsoMallocInlines.h>
38
39 namespace WebCore {
40
41 WTF_MAKE_ISO_ALLOCATED_IMPL(RenderMultiColumnFlow);
42
43 RenderMultiColumnFlow::RenderMultiColumnFlow(Document& document, RenderStyle&& style)
44     : RenderFragmentedFlow(document, WTFMove(style))
45     , m_spannerMap(std::make_unique<SpannerMap>())
46     , m_lastSetWorkedOn(nullptr)
47     , m_columnCount(1)
48     , m_columnWidth(0)
49     , m_columnHeightAvailable(0)
50     , m_inLayout(false)
51     , m_inBalancingPass(false)
52     , m_needsHeightsRecalculation(false)
53     , m_progressionIsInline(false)
54     , m_progressionIsReversed(false)
55 {
56     setFragmentedFlowState(InsideInFragmentedFlow);
57 }
58
59 RenderMultiColumnFlow::~RenderMultiColumnFlow() = default;
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     return child ? child->nextSiblingBox() : nullptr;
97 }
98
99 RenderBox* RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(const RenderBox* child)
100 {
101     if (!child)
102         return nullptr;
103     if (auto* sibling = child->previousSiblingBox()) {
104         if (!is<RenderFragmentedFlow>(*sibling))
105             return sibling;
106     }
107     return nullptr;
108 }
109
110 RenderMultiColumnSpannerPlaceholder* RenderMultiColumnFlow::findColumnSpannerPlaceholder(RenderBox* spanner) const
111 {
112     return m_spannerMap->get(spanner).get();
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 void RenderMultiColumnFlow::addFragmentToThread(RenderFragmentContainer* RenderFragmentContainer)
137 {
138     auto* columnSet = downcast<RenderMultiColumnSet>(RenderFragmentContainer);
139     if (RenderMultiColumnSet* nextSet = columnSet->nextSiblingMultiColumnSet()) {
140         RenderFragmentContainerList::iterator it = m_fragmentList.find(nextSet);
141         ASSERT(it != m_fragmentList.end());
142         m_fragmentList.insertBefore(it, columnSet);
143     } else
144         m_fragmentList.add(columnSet);
145     RenderFragmentContainer->setIsValid(true);
146 }
147
148 void RenderMultiColumnFlow::willBeRemovedFromTree()
149 {
150     // Detach all column sets from the flow thread. Cannot destroy them at this point, since they
151     // are siblings of this object, and there may be pointers to this object's sibling somewhere
152     // further up on the call stack.
153     for (RenderMultiColumnSet* columnSet = firstMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet())
154         columnSet->detachFragment();
155     RenderFragmentedFlow::willBeRemovedFromTree();
156 }
157
158 void RenderMultiColumnFlow::fragmentedFlowDescendantBoxLaidOut(RenderBox* descendant)
159 {
160     if (!is<RenderMultiColumnSpannerPlaceholder>(*descendant))
161         return;
162     auto& placeholder = downcast<RenderMultiColumnSpannerPlaceholder>(*descendant);
163     RenderBlock* container = placeholder.containingBlock();
164
165     for (RenderBox* prev = previousColumnSetOrSpannerSiblingOf(placeholder.spanner()); prev; prev = previousColumnSetOrSpannerSiblingOf(prev)) {
166         if (is<RenderMultiColumnSet>(*prev)) {
167             downcast<RenderMultiColumnSet>(*prev).endFlow(container, placeholder.logicalTop());
168             break;
169         }
170     }
171
172     for (RenderBox* next = nextColumnSetOrSpannerSiblingOf(placeholder.spanner()); next; next = nextColumnSetOrSpannerSiblingOf(next)) {
173         if (is<RenderMultiColumnSet>(*next)) {
174             m_lastSetWorkedOn = downcast<RenderMultiColumnSet>(next);
175             m_lastSetWorkedOn->beginFlow(container);
176             break;
177         }
178     }
179 }
180
181 RenderBox::LogicalExtentComputedValues RenderMultiColumnFlow::computeLogicalHeight(LayoutUnit logicalHeight, LayoutUnit logicalTop) const
182 {
183     // We simply remain at our intrinsic height.
184     return { logicalHeight, logicalTop, ComputedMarginValues() };
185 }
186
187 LayoutUnit RenderMultiColumnFlow::initialLogicalWidth() const
188 {
189     return columnWidth();
190 }
191
192 void RenderMultiColumnFlow::setPageBreak(const RenderBlock* block, LayoutUnit offset, LayoutUnit spaceShortage)
193 {
194     if (auto* multicolSet = downcast<RenderMultiColumnSet>(fragmentAtBlockOffset(block, offset)))
195         multicolSet->recordSpaceShortage(spaceShortage);
196 }
197
198 void RenderMultiColumnFlow::updateMinimumPageHeight(const RenderBlock* block, LayoutUnit offset, LayoutUnit minHeight)
199 {
200     if (auto* multicolSet = downcast<RenderMultiColumnSet>(fragmentAtBlockOffset(block, offset)))
201         multicolSet->updateMinimumColumnHeight(minHeight);
202 }
203
204 RenderFragmentContainer* RenderMultiColumnFlow::fragmentAtBlockOffset(const RenderBox* box, LayoutUnit offset, bool extendLastFragment) const
205 {
206     if (!m_inLayout)
207         return RenderFragmentedFlow::fragmentAtBlockOffset(box, offset, extendLastFragment);
208
209     // Layout in progress. We are calculating the set heights as we speak, so the fragment range
210     // information is not up-to-date.
211
212     RenderMultiColumnSet* columnSet = m_lastSetWorkedOn ? m_lastSetWorkedOn : firstMultiColumnSet();
213     if (!columnSet) {
214         // If there's no set, bail. This multicol is empty or only consists of spanners. There
215         // are no fragments.
216         return nullptr;
217     }
218     // The last set worked on is a good guess. But if we're not within the bounds, search for the
219     // right one.
220     if (offset < columnSet->logicalTopInFragmentedFlow()) {
221         do {
222             if (RenderMultiColumnSet* prev = columnSet->previousSiblingMultiColumnSet())
223                 columnSet = prev;
224             else
225                 break;
226         } while (offset < columnSet->logicalTopInFragmentedFlow());
227     } else {
228         while (offset >= columnSet->logicalBottomInFragmentedFlow()) {
229             RenderMultiColumnSet* next = columnSet->nextSiblingMultiColumnSet();
230             if (!next || !next->hasBeenFlowed())
231                 break;
232             columnSet = next;
233         }
234     }
235     return columnSet;
236 }
237
238 void RenderMultiColumnFlow::setFragmentRangeForBox(const RenderBox& box, RenderFragmentContainer* startFragment, RenderFragmentContainer* endFragment)
239 {
240     // Some column sets may have zero height, which means that two or more sets may start at the
241     // exact same flow thread position, which means that some parts of the code may believe that a
242     // given box lives in sets that it doesn't really live in. Make some adjustments here and
243     // include such sets if they are adjacent to the start and/or end fragments.
244     for (RenderMultiColumnSet* columnSet = downcast<RenderMultiColumnSet>(*startFragment).previousSiblingMultiColumnSet(); columnSet; columnSet = columnSet->previousSiblingMultiColumnSet()) {
245         if (columnSet->logicalHeightInFragmentedFlow())
246             break;
247         startFragment = columnSet;
248     }
249     for (RenderMultiColumnSet* columnSet = downcast<RenderMultiColumnSet>(*startFragment).nextSiblingMultiColumnSet(); columnSet; columnSet = columnSet->nextSiblingMultiColumnSet()) {
250         if (columnSet->logicalHeightInFragmentedFlow())
251             break;
252         endFragment = columnSet;
253     }
254
255     RenderFragmentedFlow::setFragmentRangeForBox(box, startFragment, endFragment);
256 }
257
258 bool RenderMultiColumnFlow::addForcedFragmentBreak(const RenderBlock* block, LayoutUnit offset, RenderBox* /*breakChild*/, bool /*isBefore*/, LayoutUnit* offsetBreakAdjustment)
259 {
260     if (auto* multicolSet = downcast<RenderMultiColumnSet>(fragmentAtBlockOffset(block, offset))) {
261         multicolSet->addForcedBreak(offset);
262         if (offsetBreakAdjustment)
263             *offsetBreakAdjustment = pageLogicalHeightForOffset(offset) ? pageRemainingLogicalHeightForOffset(offset, IncludePageBoundary) : 0_lu;
264         return true;
265     }
266     return false;
267 }
268
269 LayoutSize RenderMultiColumnFlow::offsetFromContainer(RenderElement& enclosingContainer, const LayoutPoint& physicalPoint, bool* offsetDependsOnPoint) const
270 {
271     ASSERT(&enclosingContainer == container());
272
273     if (offsetDependsOnPoint)
274         *offsetDependsOnPoint = true;
275     
276     LayoutPoint translatedPhysicalPoint(physicalPoint);
277     if (RenderFragmentContainer* fragment = physicalTranslationFromFlowToFragment(translatedPhysicalPoint))
278         translatedPhysicalPoint.moveBy(fragment->topLeftLocation());
279     
280     LayoutSize offset(translatedPhysicalPoint.x(), translatedPhysicalPoint.y());
281     if (is<RenderBox>(enclosingContainer))
282         offset -= toLayoutSize(downcast<RenderBox>(enclosingContainer).scrollPosition());
283     return offset;
284 }
285     
286 void RenderMultiColumnFlow::mapAbsoluteToLocalPoint(MapCoordinatesFlags mode, TransformState& transformState) const
287 {
288     // First get the transform state's point into the block flow thread's physical coordinate space.
289     parent()->mapAbsoluteToLocalPoint(mode, transformState);
290     LayoutPoint transformPoint(transformState.mappedPoint());
291     
292     // Now walk through each fragment.
293     const RenderMultiColumnSet* candidateColumnSet = nullptr;
294     LayoutPoint candidatePoint;
295     LayoutSize candidateContainerOffset;
296     
297     for (const auto& columnSet : childrenOfType<RenderMultiColumnSet>(*parent())) {
298         candidateContainerOffset = columnSet.offsetFromContainer(*parent(), LayoutPoint());
299         
300         candidatePoint = transformPoint - candidateContainerOffset;
301         candidateColumnSet = &columnSet;
302         
303         // We really have no clue what to do with overflow. We'll just use the closest fragment to the point in that case.
304         LayoutUnit pointOffset = isHorizontalWritingMode() ? candidatePoint.y() : candidatePoint.x();
305         LayoutUnit fragmentOffset = isHorizontalWritingMode() ? columnSet.topLeftLocation().y() : columnSet.topLeftLocation().x();
306         if (pointOffset < fragmentOffset + columnSet.logicalHeight())
307             break;
308     }
309     
310     // Once we have a good guess as to which fragment we hit tested through (and yes, this was just a heuristic, but it's
311     // the best we could do), then we can map from the fragment into the flow thread.
312     LayoutSize translationOffset = physicalTranslationFromFragmentToFlow(candidateColumnSet, candidatePoint) + candidateContainerOffset;
313     bool preserve3D = mode & UseTransforms && (parent()->style().preserves3D() || style().preserves3D());
314     if (mode & UseTransforms && shouldUseTransformFromContainer(parent())) {
315         TransformationMatrix t;
316         getTransformFromContainer(parent(), translationOffset, t);
317         transformState.applyTransform(t, preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
318     } else
319         transformState.move(translationOffset.width(), translationOffset.height(), preserve3D ? TransformState::AccumulateTransform : TransformState::FlattenTransform);
320 }
321
322 LayoutSize RenderMultiColumnFlow::physicalTranslationFromFragmentToFlow(const RenderMultiColumnSet* columnSet, const LayoutPoint& physicalPoint) const
323 {
324     LayoutPoint logicalPoint = columnSet->flipForWritingMode(physicalPoint);
325     LayoutPoint translatedPoint = columnSet->translateFragmentPointToFragmentedFlow(logicalPoint);
326     LayoutPoint physicalTranslatedPoint = columnSet->flipForWritingMode(translatedPoint);
327     return physicalPoint - physicalTranslatedPoint;
328 }
329
330 RenderFragmentContainer* RenderMultiColumnFlow::mapFromFlowToFragment(TransformState& transformState) const
331 {
332     if (!hasValidFragmentInfo())
333         return nullptr;
334
335     // Get back into our local flow thread space.
336     LayoutRect boxRect = transformState.mappedQuad().enclosingBoundingBox();
337     flipForWritingMode(boxRect);
338
339     // FIXME: We need to refactor RenderObject::absoluteQuads to be able to split the quads across fragments,
340     // for now we just take the center of the mapped enclosing box and map it to a column.
341     LayoutPoint centerPoint = boxRect.center();
342     LayoutUnit centerLogicalOffset = isHorizontalWritingMode() ? centerPoint.y() : centerPoint.x();
343     RenderFragmentContainer* RenderFragmentContainer = fragmentAtBlockOffset(this, centerLogicalOffset, true);
344     if (!RenderFragmentContainer)
345         return nullptr;
346     transformState.move(physicalTranslationOffsetFromFlowToFragment(RenderFragmentContainer, centerLogicalOffset));
347     return RenderFragmentContainer;
348 }
349
350 LayoutSize RenderMultiColumnFlow::physicalTranslationOffsetFromFlowToFragment(const RenderFragmentContainer* RenderFragmentContainer, const LayoutUnit logicalOffset) const
351 {
352     // Now that we know which multicolumn set we hit, we need to get the appropriate translation offset for the column.
353     const auto* columnSet = downcast<RenderMultiColumnSet>(RenderFragmentContainer);
354     LayoutPoint translationOffset = columnSet->columnTranslationForOffset(logicalOffset);
355     
356     // Now we know how we want the rect to be translated into the fragment. At this point we're converting
357     // back to physical coordinates.
358     if (style().isFlippedBlocksWritingMode()) {
359         LayoutRect portionRect(columnSet->fragmentedFlowPortionRect());
360         LayoutRect columnRect = columnSet->columnRectAt(0);
361         LayoutUnit physicalDeltaFromPortionBottom = logicalHeight() - columnSet->logicalBottomInFragmentedFlow();
362         if (isHorizontalWritingMode())
363             columnRect.setHeight(portionRect.height());
364         else
365             columnRect.setWidth(portionRect.width());
366         columnSet->flipForWritingMode(columnRect);
367         if (isHorizontalWritingMode())
368             translationOffset.move(0_lu, columnRect.y() - portionRect.y() - physicalDeltaFromPortionBottom);
369         else
370             translationOffset.move(columnRect.x() - portionRect.x() - physicalDeltaFromPortionBottom, 0_lu);
371     }
372     
373     return LayoutSize(translationOffset.x(), translationOffset.y());
374 }
375
376 RenderFragmentContainer* RenderMultiColumnFlow::physicalTranslationFromFlowToFragment(LayoutPoint& physicalPoint) const
377 {
378     if (!hasValidFragmentInfo())
379         return nullptr;
380     
381     // Put the physical point into the flow thread's coordinate space.
382     LayoutPoint logicalPoint = flipForWritingMode(physicalPoint);
383     
384     // Now get the fragment that we are in.
385     LayoutUnit logicalOffset = isHorizontalWritingMode() ? logicalPoint.y() : logicalPoint.x();
386     RenderFragmentContainer* RenderFragmentContainer = fragmentAtBlockOffset(this, logicalOffset, true);
387     if (!RenderFragmentContainer)
388         return nullptr;
389     
390     // Translate to the coordinate space of the fragment.
391     LayoutSize translationOffset = physicalTranslationOffsetFromFlowToFragment(RenderFragmentContainer, logicalOffset);
392     
393     // Now shift the physical point into the fragment's coordinate space.
394     physicalPoint += translationOffset;
395     
396     return RenderFragmentContainer;
397 }
398
399 bool RenderMultiColumnFlow::isPageLogicalHeightKnown() const
400 {
401     if (RenderMultiColumnSet* columnSet = lastMultiColumnSet())
402         return columnSet->columnHeightComputed();
403     return false;
404 }
405
406 bool RenderMultiColumnFlow::nodeAtPoint(const HitTestRequest& request, HitTestResult& result, const HitTestLocation& locationInContainer, const LayoutPoint& accumulatedOffset, HitTestAction hitTestAction)
407 {
408     // You cannot be inside an in-flow RenderFragmentedFlow without a corresponding DOM node. It's better to
409     // just let the ancestor figure out where we are instead.
410     if (hitTestAction == HitTestBlockBackground)
411         return false;
412     bool inside = RenderFragmentedFlow::nodeAtPoint(request, result, locationInContainer, accumulatedOffset, hitTestAction);
413     if (inside && !result.innerNode())
414         return false;
415     return inside;
416 }
417
418 bool RenderMultiColumnFlow::shouldCheckColumnBreaks() const
419 {
420     if (!parent()->isRenderView())
421         return true;
422     return view().frameView().pagination().behavesLikeColumns;
423 }
424
425 }