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