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 INTERRUPTION) 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 "RenderMultiColumnSet.h"
28
29 #include "FrameView.h"
30 #include "HitTestResult.h"
31 #include "PaintInfo.h"
32 #include "RenderBoxFragmentInfo.h"
33 #include "RenderLayer.h"
34 #include "RenderMultiColumnFlow.h"
35 #include "RenderMultiColumnSpannerPlaceholder.h"
36 #include "RenderView.h"
37 #include <wtf/IsoMallocInlines.h>
38
39 namespace WebCore {
40
41 WTF_MAKE_ISO_ALLOCATED_IMPL(RenderMultiColumnSet);
42
43 RenderMultiColumnSet::RenderMultiColumnSet(RenderFragmentedFlow& fragmentedFlow, RenderStyle&& style)
44 : RenderFragmentContainerSet(fragmentedFlow.document(), WTFMove(style), fragmentedFlow)
45 , m_computedColumnCount(1)
46 , m_computedColumnWidth(0)
47 , m_computedColumnHeight(0)
48 , m_availableColumnHeight(0)
49 , m_columnHeightComputed(false)
50 , m_maxColumnHeight(RenderFragmentedFlow::maxLogicalHeight())
51 , m_minSpaceShortage(RenderFragmentedFlow::maxLogicalHeight())
52 , m_minimumColumnHeight(0)
53 {
54 }
55
56 RenderMultiColumnSet* RenderMultiColumnSet::nextSiblingMultiColumnSet() const
57 {
58 for (RenderObject* sibling = nextSibling(); sibling; sibling = sibling->nextSibling()) {
59 if (is<RenderMultiColumnSet>(*sibling))
60 return downcast<RenderMultiColumnSet>(sibling);
61 }
62 return nullptr;
63 }
64
65 RenderMultiColumnSet* RenderMultiColumnSet::previousSiblingMultiColumnSet() const
66 {
67 for (RenderObject* sibling = previousSibling(); sibling; sibling = sibling->previousSibling()) {
68 if (is<RenderMultiColumnSet>(*sibling))
69 return downcast<RenderMultiColumnSet>(sibling);
70 }
71 return nullptr;
72 }
73
74 RenderObject* RenderMultiColumnSet::firstRendererInFragmentedFlow() const
75 {
76 if (RenderBox* sibling = RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(this)) {
77 // Adjacent sets should not occur. Currently we would have no way of figuring out what each
78 // of them contains then.
79 ASSERT(!sibling->isRenderMultiColumnSet());
80 if (RenderMultiColumnSpannerPlaceholder* placeholder = multiColumnFlow()->findColumnSpannerPlaceholder(sibling))
81 return placeholder->nextInPreOrderAfterChildren();
82 ASSERT_NOT_REACHED();
83 }
84 return fragmentedFlow()->firstChild();
85 }
86
87 RenderObject* RenderMultiColumnSet::lastRendererInFragmentedFlow() const
88 {
89 if (RenderBox* sibling = RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(this)) {
90 // Adjacent sets should not occur. Currently we would have no way of figuring out what each
91 // of them contains then.
92 ASSERT(!sibling->isRenderMultiColumnSet());
93 if (RenderMultiColumnSpannerPlaceholder* placeholder = multiColumnFlow()->findColumnSpannerPlaceholder(sibling))
94 return placeholder->previousInPreOrder();
95 ASSERT_NOT_REACHED();
96 }
97 return fragmentedFlow()->lastLeafChild();
98 }
99
100 static bool precedesRenderer(const RenderObject* renderer, const RenderObject* boundary)
101 {
102 for (; renderer; renderer = renderer->nextInPreOrder()) {
103 if (renderer == boundary)
104 return true;
105 }
106 return false;
107 }
108
109 bool RenderMultiColumnSet::containsRendererInFragmentedFlow(const RenderObject& renderer) const
110 {
111 if (!previousSiblingMultiColumnSet() && !nextSiblingMultiColumnSet()) {
112 // There is only one set. This is easy, then.
113 return renderer.isDescendantOf(m_fragmentedFlow);
114 }
115
116 RenderObject* firstRenderer = firstRendererInFragmentedFlow();
117 RenderObject* lastRenderer = lastRendererInFragmentedFlow();
118 ASSERT(firstRenderer);
119 ASSERT(lastRenderer);
120
121 // This is SLOW! But luckily very uncommon.
122 return precedesRenderer(firstRenderer, &renderer) && precedesRenderer(&renderer, lastRenderer);
123 }
124
125 void RenderMultiColumnSet::setLogicalTopInFragmentedFlow(LayoutUnit logicalTop)
126 {
127 LayoutRect rect = fragmentedFlowPortionRect();
128 if (isHorizontalWritingMode())
129 rect.setY(logicalTop);
130 else
131 rect.setX(logicalTop);
132 setFragmentedFlowPortionRect(rect);
133 }
134
135 void RenderMultiColumnSet::setLogicalBottomInFragmentedFlow(LayoutUnit logicalBottom)
136 {
137 LayoutRect rect = fragmentedFlowPortionRect();
138 if (isHorizontalWritingMode())
139 rect.shiftMaxYEdgeTo(logicalBottom);
140 else
141 rect.shiftMaxXEdgeTo(logicalBottom);
142 setFragmentedFlowPortionRect(rect);
143 }
144
145 LayoutUnit RenderMultiColumnSet::heightAdjustedForSetOffset(LayoutUnit height) const
146 {
147 RenderBlockFlow& multicolBlock = downcast<RenderBlockFlow>(*parent());
148 LayoutUnit contentLogicalTop = logicalTop() - multicolBlock.borderAndPaddingBefore();
149
150 height -= contentLogicalTop;
151 return std::max(height, LayoutUnit::fromPixel(1)); // Let's avoid zero height, as that would probably cause an infinite amount of columns to be created.
152 }
153
154 LayoutUnit RenderMultiColumnSet::pageLogicalTopForOffset(LayoutUnit offset) const
155 {
156 unsigned columnIndex = columnIndexAtOffset(offset, AssumeNewColumns);
157 return logicalTopInFragmentedFlow() + columnIndex * computedColumnHeight();
158 }
159
160 void RenderMultiColumnSet::setAndConstrainColumnHeight(LayoutUnit newHeight)
161 {
162 m_computedColumnHeight = newHeight;
163 if (m_computedColumnHeight > m_maxColumnHeight)
164 m_computedColumnHeight = m_maxColumnHeight;
165
166 // FIXME: The available column height is not the same as the constrained height specified
167 // by the pagination API. The column set in this case is allowed to be bigger than the
168 // height of a single column. We cache available column height in order to use it
169 // in computeLogicalHeight later. This is pretty gross, and maybe there's a better way
170 // to formalize the idea of clamped column heights without having a view dependency
171 // here.
172 m_availableColumnHeight = m_computedColumnHeight;
173 if (multiColumnFlow() && !multiColumnFlow()->progressionIsInline() && parent()->isRenderView()) {
174 int pageLength = view().frameView().pagination().pageLength;
175 if (pageLength)
176 m_computedColumnHeight = pageLength;
177 }
178
179 m_columnHeightComputed = true;
180
181 // FIXME: the height may also be affected by the enclosing pagination context, if any.
182 }
183
184 unsigned RenderMultiColumnSet::findRunWithTallestColumns() const
185 {
186 unsigned indexWithLargestHeight = 0;
187 LayoutUnit largestHeight;
188 LayoutUnit previousOffset;
189 size_t runCount = m_contentRuns.size();
190 ASSERT(runCount);
191 for (size_t i = 0; i < runCount; i++) {
192 const ContentRun& run = m_contentRuns[i];
193 LayoutUnit height = run.columnLogicalHeight(previousOffset);
194 if (largestHeight < height) {
195 largestHeight = height;
196 indexWithLargestHeight = i;
197 }
198 previousOffset = run.breakOffset();
199 }
200 return indexWithLargestHeight;
201 }
202
203 void RenderMultiColumnSet::distributeImplicitBreaks()
204 {
205 #ifndef NDEBUG
206 // There should be no implicit breaks assumed at this point.
207 for (unsigned i = 0; i < forcedBreaksCount(); i++)
208 ASSERT(!m_contentRuns[i].assumedImplicitBreaks());
209 #endif // NDEBUG
210
211 // Insert a final content run to encompass all content. This will include overflow if this is
212 // the last set.
213 addForcedBreak(logicalBottomInFragmentedFlow());
214 unsigned breakCount = forcedBreaksCount();
215
216 // If there is room for more breaks (to reach the used value of column-count), imagine that we
217 // insert implicit breaks at suitable locations. At any given time, the content run with the
218 // currently tallest columns will get another implicit break "inserted", which will increase its
219 // column count by one and shrink its columns' height. Repeat until we have the desired total
220 // number of breaks. The largest column height among the runs will then be the initial column
221 // height for the balancer to use.
222 while (breakCount < m_computedColumnCount) {
223 unsigned index = findRunWithTallestColumns();
224 m_contentRuns[index].assumeAnotherImplicitBreak();
225 breakCount++;
226 }
227 }
228
229 LayoutUnit RenderMultiColumnSet::calculateBalancedHeight(bool initial) const
230 {
231 if (initial) {
232 // Start with the lowest imaginable column height.
233 unsigned index = findRunWithTallestColumns();
234 LayoutUnit startOffset = index > 0 ? m_contentRuns[index - 1].breakOffset() : logicalTopInFragmentedFlow();
235 return std::max<LayoutUnit>(m_contentRuns[index].columnLogicalHeight(startOffset), m_minimumColumnHeight);
236 }
237
238 if (columnCount() <= computedColumnCount()) {
239 // With the current column height, the content fits without creating overflowing columns. We're done.
240 return m_computedColumnHeight;
241 }
242
243 if (forcedBreaksCount() >= computedColumnCount()) {
244 // Too many forced breaks to allow any implicit breaks. Initial balancing should already
245 // have set a good height. There's nothing more we should do.
246 return m_computedColumnHeight;
247 }
248
249 // If the initial guessed column height wasn't enough, stretch it now. Stretch by the lowest
250 // amount of space shortage found during layout.
251
252 ASSERT(m_minSpaceShortage > 0); // We should never _shrink_ the height!
253 // ASSERT(m_minSpaceShortage != RenderFragmentedFlow::maxLogicalHeight()); // If this happens, we probably have a bug.
254 if (m_minSpaceShortage == RenderFragmentedFlow::maxLogicalHeight())
255 return m_computedColumnHeight; // So bail out rather than looping infinitely.
256
257 return m_computedColumnHeight + m_minSpaceShortage;
258 }
259
260 void RenderMultiColumnSet::clearForcedBreaks()
261 {
262 m_contentRuns.clear();
263 }
264
265 void RenderMultiColumnSet::addForcedBreak(LayoutUnit offsetFromFirstPage)
266 {
267 if (!requiresBalancing())
268 return;
269 if (!m_contentRuns.isEmpty() && offsetFromFirstPage <= m_contentRuns.last().breakOffset())
270 return;
271 // Append another item as long as we haven't exceeded used column count. What ends up in the
272 // overflow area shouldn't affect column balancing.
273 if (m_contentRuns.size() < m_computedColumnCount)
274 m_contentRuns.append(ContentRun(offsetFromFirstPage));
275 }
276
277 bool RenderMultiColumnSet::recalculateColumnHeight(bool initial)
278 {
279 LayoutUnit oldColumnHeight = m_computedColumnHeight;
280 if (requiresBalancing()) {
281 if (initial)
282 distributeImplicitBreaks();
283 LayoutUnit newColumnHeight = calculateBalancedHeight(initial);
284 setAndConstrainColumnHeight(newColumnHeight);
285 // After having calculated an initial column height, the multicol container typically needs at
286 // least one more layout pass with a new column height, but if a height was specified, we only
287 // need to do this if we think that we need less space than specified. Conversely, if we
288 // determined that the columns need to be as tall as the specified height of the container, we
289 // have already laid it out correctly, and there's no need for another pass.
290 } else {
291 // The position of the column set may have changed, in which case height available for
292 // columns may have changed as well.
293 setAndConstrainColumnHeight(m_computedColumnHeight);
294 }
295 if (m_computedColumnHeight == oldColumnHeight)
296 return false; // No change. We're done.
297
298 m_minSpaceShortage = RenderFragmentedFlow::maxLogicalHeight();
299 return true; // Need another pass.
300 }
301
302 void RenderMultiColumnSet::recordSpaceShortage(LayoutUnit spaceShortage)
303 {
304 if (spaceShortage >= m_minSpaceShortage)
305 return;
306
307 // The space shortage is what we use as our stretch amount. We need a positive number here in
308 // order to get anywhere. Some lines actually have zero height. Ignore them.
309 if (spaceShortage > 0)
310 m_minSpaceShortage = spaceShortage;
311 }
312
313 void RenderMultiColumnSet::updateLogicalWidth()
314 {
315 setComputedColumnWidthAndCount(multiColumnFlow()->columnWidth(), multiColumnFlow()->columnCount()); // FIXME: This will eventually vary if we are contained inside fragments.
316
317 // FIXME: When we add fragments support, we'll start it off at the width of the multi-column
318 // block in that particular fragment.
319 setLogicalWidth(multiColumnBlockFlow()->contentLogicalWidth());
320 }
321
322 bool RenderMultiColumnSet::requiresBalancing() const
323 {
324 if (!multiColumnFlow()->progressionIsInline())
325 return false;
326
327 if (RenderBox* next = RenderMultiColumnFlow::nextColumnSetOrSpannerSiblingOf(this)) {
328 if (!next->isRenderMultiColumnSet() && !next->isLegend()) {
329 // If we're followed by a spanner, we need to balance.
330 ASSERT(multiColumnFlow()->findColumnSpannerPlaceholder(next));
331 return true;
332 }
333 }
334 RenderBlockFlow* container = multiColumnBlockFlow();
335 if (container->style().columnFill() == ColumnFillBalance)
336 return true;
337 return !multiColumnFlow()->columnHeightAvailable();
338 }
339
340 void RenderMultiColumnSet::prepareForLayout(bool initial)
341 {
342 // Guess box logical top. This might eliminate the need for another layout pass.
343 if (RenderBox* previous = RenderMultiColumnFlow::previousColumnSetOrSpannerSiblingOf(this))
344 setLogicalTop(previous->logicalBottom() + previous->marginAfter());
345 else
346 setLogicalTop(multiColumnBlockFlow()->borderAndPaddingBefore());
347
348 if (initial)
349 m_maxColumnHeight = calculateMaxColumnHeight();
350 if (requiresBalancing()) {
351 if (initial) {
352 m_computedColumnHeight = 0;
353 m_availableColumnHeight = 0;
354 m_columnHeightComputed = false;
355 }
356 } else
357 setAndConstrainColumnHeight(heightAdjustedForSetOffset(multiColumnFlow()->columnHeightAvailable()));
358
359 // Set box width.
360 updateLogicalWidth();
361
362 // Any breaks will be re-inserted during layout, so get rid of what we already have.
363 clearForcedBreaks();
364
365 // Nuke previously stored minimum column height. Contents may have changed for all we know.
366 m_minimumColumnHeight = 0;
367
368 // Start with "infinite" flow thread portion height until height is known.
369 setLogicalBottomInFragmentedFlow(RenderFragmentedFlow::maxLogicalHeight());
370
371 setNeedsLayout(MarkOnlyThis);
372 }
373
374 void RenderMultiColumnSet::beginFlow(RenderBlock* container)
375 {
376 RenderMultiColumnFlow* fragmentedFlow = multiColumnFlow();
377
378 // At this point layout is exactly at the beginning of this set. Store block offset from flow
379 // thread start.
380 LayoutUnit logicalTopInFragmentedFlow = fragmentedFlow->offsetFromLogicalTopOfFirstFragment(container) + container->logicalHeight();
381 setLogicalTopInFragmentedFlow(logicalTopInFragmentedFlow);
382 }
383
384 void RenderMultiColumnSet::endFlow(RenderBlock* container, LayoutUnit bottomInContainer)
385 {
386 RenderMultiColumnFlow* fragmentedFlow = multiColumnFlow();
387
388 // At this point layout is exactly at the end of this set. Store block offset from flow thread
389 // start. Also note that a new column height may have affected the height used in the flow
390 // thread (because of struts), which may affect the number of columns. So we also need to update
391 // the flow thread portion height in order to be able to calculate actual column-count.
392 LayoutUnit logicalBottomInFragmentedFlow = fragmentedFlow->offsetFromLogicalTopOfFirstFragment(container) + bottomInContainer;
393 setLogicalBottomInFragmentedFlow(logicalBottomInFragmentedFlow);
394 container->setLogicalHeight(bottomInContainer);
395 }
396
397 void RenderMultiColumnSet::layout()
398 {
399 RenderBlockFlow::layout();
400
401 // At this point the logical top and bottom of the column set are known. Update maximum column
402 // height (multicol height may be constrained).
403 m_maxColumnHeight = calculateMaxColumnHeight();
404
405 if (!nextSiblingMultiColumnSet()) {
406 // This is the last set, i.e. the last fragment. Seize the opportunity to validate them.
407 multiColumnFlow()->validateFragments();
408 }
409 }
410
411 RenderBox::LogicalExtentComputedValues RenderMultiColumnSet::computeLogicalHeight(LayoutUnit, LayoutUnit logicalTop) const
412 {
413 return { m_availableColumnHeight, logicalTop, ComputedMarginValues() };
414 }
415
416 LayoutUnit RenderMultiColumnSet::calculateMaxColumnHeight() const
417 {
418 RenderBlockFlow* multicolBlock = multiColumnBlockFlow();
419 const RenderStyle& multicolStyle = multicolBlock->style();
420 LayoutUnit availableHeight = multiColumnFlow()->columnHeightAvailable();
421 LayoutUnit maxColumnHeight = availableHeight ? availableHeight : RenderFragmentedFlow::maxLogicalHeight();
422 if (!multicolStyle.logicalMaxHeight().isUndefined())
423 maxColumnHeight = std::min(maxColumnHeight, multicolBlock->computeContentLogicalHeight(MaxSize, multicolStyle.logicalMaxHeight(), std::nullopt).value_or(maxColumnHeight));
424 return heightAdjustedForSetOffset(maxColumnHeight);
425 }
426
427 LayoutUnit RenderMultiColumnSet::columnGap() const
428 {
429 // FIXME: Eventually we will cache the column gap when the widths of columns start varying, but for now we just
430 // go to the parent block to get the gap.
431 RenderBlockFlow& parentBlock = downcast<RenderBlockFlow>(*parent());
432 if (parentBlock.style().columnGap().isNormal())
433 return parentBlock.style().fontDescription().computedPixelSize(); // "1em" is recommended as the normal gap setting. Matches <p> margins.
434 return valueForLength(parentBlock.style().columnGap().length(), parentBlock.availableLogicalWidth());
435 }
436
437 unsigned RenderMultiColumnSet::columnCount() const
438 {
439 // We must always return a value of 1 or greater. Column count = 0 is a meaningless situation,
440 // and will confuse and cause problems in other parts of the code.
441 if (!computedColumnHeight())
442 return 1;
443
444 // Our portion rect determines our column count. We have as many columns as needed to fit all the content.
445 LayoutUnit logicalHeightInColumns = fragmentedFlow()->isHorizontalWritingMode() ? fragmentedFlowPortionRect().height() : fragmentedFlowPortionRect().width();
446 if (!logicalHeightInColumns)
447 return 1;
448
449 unsigned count = ceil(static_cast<float>(logicalHeightInColumns) / computedColumnHeight());
450 ASSERT(count >= 1);
451 return count;
452 }
453
454 LayoutUnit RenderMultiColumnSet::columnLogicalLeft(unsigned index) const
455 {
456 LayoutUnit colLogicalWidth = computedColumnWidth();
457 LayoutUnit colLogicalLeft = borderAndPaddingLogicalLeft();
458 LayoutUnit colGap = columnGap();
459
460 bool progressionReversed = multiColumnFlow()->progressionIsReversed();
461 bool progressionInline = multiColumnFlow()->progressionIsInline();
462
463 if (progressionInline) {
464 if (style().isLeftToRightDirection() ^ progressionReversed)
465 colLogicalLeft += index * (colLogicalWidth + colGap);
466 else
467 colLogicalLeft += contentLogicalWidth() - colLogicalWidth - index * (colLogicalWidth + colGap);
468 }
469
470 return colLogicalLeft;
471 }
472
473 LayoutUnit RenderMultiColumnSet::columnLogicalTop(unsigned index) const
474 {
475 LayoutUnit colLogicalHeight = computedColumnHeight();
476 LayoutUnit colLogicalTop = borderAndPaddingBefore();
477 LayoutUnit colGap = columnGap();
478
479 bool progressionReversed = multiColumnFlow()->progressionIsReversed();
480 bool progressionInline = multiColumnFlow()->progressionIsInline();
481
482 if (!progressionInline) {
483 if (!progressionReversed)
484 colLogicalTop += index * (colLogicalHeight + colGap);
485 else
486 colLogicalTop += contentLogicalHeight() - colLogicalHeight - index * (colLogicalHeight + colGap);
487 }
488
489 return colLogicalTop;
490 }
491
492 LayoutRect RenderMultiColumnSet::columnRectAt(unsigned index) const
493 {
494 LayoutUnit colLogicalWidth = computedColumnWidth();
495 LayoutUnit colLogicalHeight = computedColumnHeight();
496
497 if (isHorizontalWritingMode())
498 return LayoutRect(columnLogicalLeft(index), columnLogicalTop(index), colLogicalWidth, colLogicalHeight);
499 return LayoutRect(columnLogicalTop(index), columnLogicalLeft(index), colLogicalHeight, colLogicalWidth);
500 }
501
502 unsigned RenderMultiColumnSet::columnIndexAtOffset(LayoutUnit offset, ColumnIndexCalculationMode mode) const
503 {
504 LayoutRect portionRect(fragmentedFlowPortionRect());
505
506 // Handle the offset being out of range.
507 LayoutUnit fragmentedFlowLogicalTop = isHorizontalWritingMode() ? portionRect.y() : portionRect.x();
508 if (offset < fragmentedFlowLogicalTop)
509 return 0;
510 // If we're laying out right now, we cannot constrain against some logical bottom, since it
511 // isn't known yet. Otherwise, just return the last column if we're past the logical bottom.
512 if (mode == ClampToExistingColumns) {
513 LayoutUnit fragmentedFlowLogicalBottom = isHorizontalWritingMode() ? portionRect.maxY() : portionRect.maxX();
514 if (offset >= fragmentedFlowLogicalBottom)
515 return columnCount() - 1;
516 }
517
518 // Sometimes computedColumnHeight() is 0 here: see https://bugs.webkit.org/show_bug.cgi?id=132884
519 if (!computedColumnHeight())
520 return 0;
521
522 // Just divide by the column height to determine the correct column.
523 return static_cast<float>(offset - fragmentedFlowLogicalTop) / computedColumnHeight();
524 }
525
526 LayoutRect RenderMultiColumnSet::fragmentedFlowPortionRectAt(unsigned index) const
527 {
528 LayoutRect portionRect = fragmentedFlowPortionRect();
529 if (isHorizontalWritingMode())
530 portionRect = LayoutRect(portionRect.x(), portionRect.y() + index * computedColumnHeight(), portionRect.width(), computedColumnHeight());
531 else
532 portionRect = LayoutRect(portionRect.x() + index * computedColumnHeight(), portionRect.y(), computedColumnHeight(), portionRect.height());
533 return portionRect;
534 }
535
536 LayoutRect RenderMultiColumnSet::fragmentedFlowPortionOverflowRect(const LayoutRect& portionRect, unsigned index, unsigned colCount, LayoutUnit colGap)
537 {
538 // This function determines the portion of the flow thread that paints for the column. Along the inline axis, columns are
539 // unclipped at outside edges (i.e., the first and last column in the set), and they clip to half the column
540 // gap along interior edges.
541 //
542 // In the block direction, we will not clip overflow out of the top of the first column, or out of the bottom of
543 // the last column. This applies only to the true first column and last column across all column sets.
544 //
545 // FIXME: Eventually we will know overflow on a per-column basis, but we can't do this until we have a painting
546 // mode that understands not to paint contents from a previous column in the overflow area of a following column.
547 // This problem applies to fragments and pages as well and is not unique to columns.
548
549 bool progressionReversed = multiColumnFlow()->progressionIsReversed();
550
551 bool isFirstColumn = !index;
552 bool isLastColumn = index == colCount - 1;
553 bool isLeftmostColumn = style().isLeftToRightDirection() ^ progressionReversed ? isFirstColumn : isLastColumn;
554 bool isRightmostColumn = style().isLeftToRightDirection() ^ progressionReversed ? isLastColumn : isFirstColumn;
555
556 // Calculate the overflow rectangle, based on the flow thread's, clipped at column logical
557 // top/bottom unless it's the first/last column.
558 LayoutRect overflowRect = overflowRectForFragmentedFlowPortion(portionRect, isFirstColumn && isFirstFragment(), isLastColumn && isLastFragment(), VisualOverflow);
559
560 // For RenderViews only (i.e., iBooks), avoid overflowing into neighboring columns, by clipping in the middle of adjacent column gaps. Also make sure that we avoid rounding errors.
561 if (&view() == parent()) {
562 if (isHorizontalWritingMode()) {
563 if (!isLeftmostColumn)
564 overflowRect.shiftXEdgeTo(portionRect.x() - colGap / 2);
565 if (!isRightmostColumn)
566 overflowRect.shiftMaxXEdgeTo(portionRect.maxX() + colGap - colGap / 2);
567 } else {
568 if (!isLeftmostColumn)
569 overflowRect.shiftYEdgeTo(portionRect.y() - colGap / 2);
570 if (!isRightmostColumn)
571 overflowRect.shiftMaxYEdgeTo(portionRect.maxY() + colGap - colGap / 2);
572 }
573 }
574 return overflowRect;
575 }
576
577 void RenderMultiColumnSet::paintColumnRules(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
578 {
579 if (paintInfo.context().paintingDisabled())
580 return;
581
582 RenderMultiColumnFlow* fragmentedFlow = multiColumnFlow();
583 const RenderStyle& blockStyle = parent()->style();
584 const Color& ruleColor = blockStyle.visitedDependentColor(CSSPropertyColumnRuleColor);
585 bool ruleTransparent = blockStyle.columnRuleIsTransparent();
586 EBorderStyle ruleStyle = collapsedBorderStyle(blockStyle.columnRuleStyle());
587 LayoutUnit ruleThickness = blockStyle.columnRuleWidth();
588 LayoutUnit colGap = columnGap();
589 bool renderRule = ruleStyle > BHIDDEN && !ruleTransparent;
590 if (!renderRule)
591 return;
592
593 unsigned colCount = columnCount();
594 if (colCount <= 1)
595 return;
596
597 bool antialias = shouldAntialiasLines(paintInfo.context());
598
599 if (fragmentedFlow->progressionIsInline()) {
600 bool leftToRight = style().isLeftToRightDirection() ^ fragmentedFlow->progressionIsReversed();
601 LayoutUnit currLogicalLeftOffset = leftToRight ? LayoutUnit() : contentLogicalWidth();
602 LayoutUnit ruleAdd = logicalLeftOffsetForContent();
603 LayoutUnit ruleLogicalLeft = leftToRight ? LayoutUnit() : contentLogicalWidth();
604 LayoutUnit inlineDirectionSize = computedColumnWidth();
605 BoxSide boxSide = isHorizontalWritingMode()
606 ? leftToRight ? BSLeft : BSRight
607 : leftToRight ? BSTop : BSBottom;
608
609 for (unsigned i = 0; i < colCount; i++) {
610 // Move to the next position.
611 if (leftToRight) {
612 ruleLogicalLeft += inlineDirectionSize + colGap / 2;
613 currLogicalLeftOffset += inlineDirectionSize + colGap;
614 } else {
615 ruleLogicalLeft -= (inlineDirectionSize + colGap / 2);
616 currLogicalLeftOffset -= (inlineDirectionSize + colGap);
617 }
618
619 // Now paint the column rule.
620 if (i < colCount - 1) {
621 LayoutUnit ruleLeft = isHorizontalWritingMode() ? paintOffset.x() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd : paintOffset.x() + borderLeft() + paddingLeft();
622 LayoutUnit ruleRight = isHorizontalWritingMode() ? ruleLeft + ruleThickness : ruleLeft + contentWidth();
623 LayoutUnit ruleTop = isHorizontalWritingMode() ? paintOffset.y() + borderTop() + paddingTop() : paintOffset.y() + ruleLogicalLeft - ruleThickness / 2 + ruleAdd;
624 LayoutUnit ruleBottom = isHorizontalWritingMode() ? ruleTop + contentHeight() : ruleTop + ruleThickness;
625 IntRect pixelSnappedRuleRect = snappedIntRect(ruleLeft, ruleTop, ruleRight - ruleLeft, ruleBottom - ruleTop);
626 drawLineForBoxSide(paintInfo.context(), pixelSnappedRuleRect, boxSide, ruleColor, ruleStyle, 0, 0, antialias);
627 }
628
629 ruleLogicalLeft = currLogicalLeftOffset;
630 }
631 } else {
632 bool topToBottom = !style().isFlippedBlocksWritingMode() ^ fragmentedFlow->progressionIsReversed();
633 LayoutUnit ruleLeft = isHorizontalWritingMode() ? LayoutUnit() : colGap / 2 - colGap - ruleThickness / 2;
634 LayoutUnit ruleWidth = isHorizontalWritingMode() ? contentWidth() : ruleThickness;
635 LayoutUnit ruleTop = isHorizontalWritingMode() ? colGap / 2 - colGap - ruleThickness / 2 : LayoutUnit();
636 LayoutUnit ruleHeight = isHorizontalWritingMode() ? ruleThickness : contentHeight();
637 LayoutRect ruleRect(ruleLeft, ruleTop, ruleWidth, ruleHeight);
638
639 if (!topToBottom) {
640 if (isHorizontalWritingMode())
641 ruleRect.setY(height() - ruleRect.maxY());
642 else
643 ruleRect.setX(width() - ruleRect.maxX());
644 }
645
646 ruleRect.moveBy(paintOffset);
647
648 BoxSide boxSide = isHorizontalWritingMode() ? topToBottom ? BSTop : BSBottom : topToBottom ? BSLeft : BSRight;
649
650 LayoutSize step(0, topToBottom ? computedColumnHeight() + colGap : -(computedColumnHeight() + colGap));
651 if (!isHorizontalWritingMode())
652 step = step.transposedSize();
653
654 for (unsigned i = 1; i < colCount; i++) {
655 ruleRect.move(step);
656 IntRect pixelSnappedRuleRect = snappedIntRect(ruleRect);
657 drawLineForBoxSide(paintInfo.context(), pixelSnappedRuleRect, boxSide, ruleColor, ruleStyle, 0, 0, antialias);
658 }
659 }
660 }
661
662 void RenderMultiColumnSet::repaintFragmentedFlowContent(const LayoutRect& repaintRect)
663 {
664 // Figure out the start and end columns and only check within that range so that we don't walk the
665 // entire column set. Put the repaint rect into flow thread coordinates by flipping it first.
666 LayoutRect fragmentedFlowRepaintRect(repaintRect);
667 fragmentedFlow()->flipForWritingMode(fragmentedFlowRepaintRect);
668
669 // Now we can compare this rect with the flow thread portions owned by each column. First let's
670 // just see if the repaint rect intersects our flow thread portion at all.
671 LayoutRect clippedRect(fragmentedFlowRepaintRect);
672 clippedRect.intersect(RenderFragmentContainer::fragmentedFlowPortionOverflowRect());
673 if (clippedRect.isEmpty())
674 return;
675
676 // Now we know we intersect at least one column. Let's figure out the logical top and logical
677 // bottom of the area we're repainting.
678 LayoutUnit repaintLogicalTop = isHorizontalWritingMode() ? fragmentedFlowRepaintRect.y() : fragmentedFlowRepaintRect.x();
679 LayoutUnit repaintLogicalBottom = (isHorizontalWritingMode() ? fragmentedFlowRepaintRect.maxY() : fragmentedFlowRepaintRect.maxX()) - 1;
680
681 unsigned startColumn = columnIndexAtOffset(repaintLogicalTop);
682 unsigned endColumn = columnIndexAtOffset(repaintLogicalBottom);
683
684 LayoutUnit colGap = columnGap();
685 unsigned colCount = columnCount();
686 for (unsigned i = startColumn; i <= endColumn; i++) {
687 LayoutRect colRect = columnRectAt(i);
688
689 // Get the portion of the flow thread that corresponds to this column.
690 LayoutRect fragmentedFlowPortion = fragmentedFlowPortionRectAt(i);
691
692 // Now get the overflow rect that corresponds to the column.
693 LayoutRect fragmentedFlowOverflowPortion = fragmentedFlowPortionOverflowRect(fragmentedFlowPortion, i, colCount, colGap);
694
695 // Do a repaint for this specific column.
696 flipForWritingMode(colRect);
697 repaintFragmentedFlowContentRectangle(repaintRect, fragmentedFlowPortion, colRect.location(), &fragmentedFlowOverflowPortion);
698 }
699 }
700
701 LayoutUnit RenderMultiColumnSet::initialBlockOffsetForPainting() const
702 {
703 bool progressionReversed = multiColumnFlow()->progressionIsReversed();
704 bool progressionIsInline = multiColumnFlow()->progressionIsInline();
705
706 LayoutUnit result = 0;
707 if (!progressionIsInline && progressionReversed) {
708 LayoutRect colRect = columnRectAt(0);
709 result = isHorizontalWritingMode() ? colRect.y() : colRect.x();
710 }
711 return result;
712 }
713
714 void RenderMultiColumnSet::collectLayerFragments(LayerFragments& fragments, const LayoutRect& layerBoundingBox, const LayoutRect& dirtyRect)
715 {
716 // Let's start by introducing the different coordinate systems involved here. They are different
717 // in how they deal with writing modes and columns. RenderLayer rectangles tend to be more
718 // physical than the rectangles used in RenderObject & co.
719 //
720 // The two rectangles passed to this method are physical, except that we pretend that there's
721 // only one long column (that's the flow thread). They are relative to the top left corner of
722 // the flow thread. All rectangles being compared to the dirty rect also need to be in this
723 // coordinate system.
724 //
725 // Then there's the output from this method - the stuff we put into the list of fragments. The
726 // translationOffset point is the actual physical translation required to get from a location in
727 // the flow thread to a location in some column. The paginationClip rectangle is in the same
728 // coordinate system as the two rectangles passed to this method (i.e. physical, in flow thread
729 // coordinates, pretending that there's only one long column).
730 //
731 // All other rectangles in this method are slightly less physical, when it comes to how they are
732 // used with different writing modes, but they aren't really logical either. They are just like
733 // RenderBox::frameRect(). More precisely, the sizes are physical, and the inline direction
734 // coordinate is too, but the block direction coordinate is always "logical top". These
735 // rectangles also pretend that there's only one long column, i.e. they are for the flow thread.
736 //
737 // To sum up: input and output from this method are "physical" RenderLayer-style rectangles and
738 // points, while inside this method we mostly use the RenderObject-style rectangles (with the
739 // block direction coordinate always being logical top).
740
741 // Put the layer bounds into flow thread-local coordinates by flipping it first. Since we're in
742 // a renderer, most rectangles are represented this way.
743 LayoutRect layerBoundsInFragmentedFlow(layerBoundingBox);
744 fragmentedFlow()->flipForWritingMode(layerBoundsInFragmentedFlow);
745
746 // Now we can compare with the flow thread portions owned by each column. First let's
747 // see if the rect intersects our flow thread portion at all.
748 LayoutRect clippedRect(layerBoundsInFragmentedFlow);
749 clippedRect.intersect(RenderFragmentContainer::fragmentedFlowPortionOverflowRect());
750 if (clippedRect.isEmpty())
751 return;
752
753 // Now we know we intersect at least one column. Let's figure out the logical top and logical
754 // bottom of the area we're checking.
755 LayoutUnit layerLogicalTop = isHorizontalWritingMode() ? layerBoundsInFragmentedFlow.y() : layerBoundsInFragmentedFlow.x();
756 LayoutUnit layerLogicalBottom = (isHorizontalWritingMode() ? layerBoundsInFragmentedFlow.maxY() : layerBoundsInFragmentedFlow.maxX()) - 1;
757
758 // Figure out the start and end columns and only check within that range so that we don't walk the
759 // entire column set.
760 unsigned startColumn = columnIndexAtOffset(layerLogicalTop);
761 unsigned endColumn = columnIndexAtOffset(layerLogicalBottom);
762
763 LayoutUnit colLogicalWidth = computedColumnWidth();
764 LayoutUnit colGap = columnGap();
765 unsigned colCount = columnCount();
766
767 bool progressionReversed = multiColumnFlow()->progressionIsReversed();
768 bool progressionIsInline = multiColumnFlow()->progressionIsInline();
769
770 LayoutUnit initialBlockOffset = initialBlockOffsetForPainting();
771
772 for (unsigned i = startColumn; i <= endColumn; i++) {
773 if (skipLayerFragmentCollectionForColumn(i))
774 continue;
775
776 // Get the portion of the flow thread that corresponds to this column.
777 LayoutRect fragmentedFlowPortion = fragmentedFlowPortionRectAt(i);
778
779 // Now get the overflow rect that corresponds to the column.
780 LayoutRect fragmentedFlowOverflowPortion = fragmentedFlowPortionOverflowRect(fragmentedFlowPortion, i, colCount, colGap);
781
782 // In order to create a fragment we must intersect the portion painted by this column.
783 LayoutRect clippedRect(layerBoundsInFragmentedFlow);
784 clippedRect.intersect(fragmentedFlowOverflowPortion);
785 if (clippedRect.isEmpty())
786 continue;
787
788 // We also need to intersect the dirty rect. We have to apply a translation and shift based off
789 // our column index.
790 LayoutSize translationOffset;
791 LayoutUnit inlineOffset = progressionIsInline ? i * (colLogicalWidth + colGap) : LayoutUnit();
792
793 bool leftToRight = style().isLeftToRightDirection() ^ progressionReversed;
794 if (!leftToRight) {
795 inlineOffset = -inlineOffset;
796 if (progressionReversed)
797 inlineOffset += contentLogicalWidth() - colLogicalWidth;
798 }
799 translationOffset.setWidth(inlineOffset);
800
801 LayoutUnit blockOffset = initialBlockOffset + logicalTop() - fragmentedFlow()->logicalTop() + (isHorizontalWritingMode() ? -fragmentedFlowPortion.y() : -fragmentedFlowPortion.x());
802 if (!progressionIsInline) {
803 if (!progressionReversed)
804 blockOffset = i * colGap + customBlockProgressionAdjustmentForColumn(i);
805 else
806 blockOffset -= i * (computedColumnHeight() + colGap);
807 }
808 if (isFlippedWritingMode(style().writingMode()))
809 blockOffset = -blockOffset;
810 translationOffset.setHeight(blockOffset);
811 if (!isHorizontalWritingMode())
812 translationOffset = translationOffset.transposedSize();
813
814 // Shift the dirty rect to be in flow thread coordinates with this translation applied.
815 LayoutRect translatedDirtyRect(dirtyRect);
816 translatedDirtyRect.move(-translationOffset);
817
818 // See if we intersect the dirty rect.
819 clippedRect = layerBoundingBox;
820 clippedRect.intersect(translatedDirtyRect);
821 if (clippedRect.isEmpty())
822 continue;
823
824 // Something does need to paint in this column. Make a fragment now and supply the physical translation
825 // offset and the clip rect for the column with that offset applied.
826 LayerFragment fragment;
827 fragment.paginationOffset = translationOffset;
828
829 LayoutRect flippedFragmentedFlowOverflowPortion(fragmentedFlowOverflowPortion);
830 // Flip it into more a physical (RenderLayer-style) rectangle.
831 fragmentedFlow()->flipForWritingMode(flippedFragmentedFlowOverflowPortion);
832 fragment.paginationClip = flippedFragmentedFlowOverflowPortion;
833 fragments.append(fragment);
834 }
835 }
836
837 LayoutPoint RenderMultiColumnSet::columnTranslationForOffset(const LayoutUnit& offset) const
838 {
839 unsigned startColumn = columnIndexAtOffset(offset);
840
841 LayoutUnit colGap = columnGap();
842
843 LayoutRect fragmentedFlowPortion = fragmentedFlowPortionRectAt(startColumn);
844 LayoutPoint translationOffset;
845
846 bool progressionReversed = multiColumnFlow()->progressionIsReversed();
847 bool progressionIsInline = multiColumnFlow()->progressionIsInline();
848
849 LayoutUnit initialBlockOffset = initialBlockOffsetForPainting();
850
851 translationOffset.setX(columnLogicalLeft(startColumn));
852
853 LayoutUnit blockOffset = initialBlockOffset - (isHorizontalWritingMode() ? fragmentedFlowPortion.y() : fragmentedFlowPortion.x());
854 if (!progressionIsInline) {
855 if (!progressionReversed)
856 blockOffset = startColumn * colGap + customBlockProgressionAdjustmentForColumn(startColumn);
857 else
858 blockOffset -= startColumn * (computedColumnHeight() + colGap);
859 }
860 if (isFlippedWritingMode(style().writingMode()))
861 blockOffset = -blockOffset;
862 translationOffset.setY(blockOffset);
863
864 if (!isHorizontalWritingMode())
865 translationOffset = translationOffset.transposedPoint();
866
867 return translationOffset;
868 }
869
870 void RenderMultiColumnSet::adjustFragmentBoundsFromFragmentedFlowPortionRect(LayoutRect&) const
871 {
872 // This only fires for named flow thread compositing code, so let's make sure to ASSERT if this ever gets invoked.
873 ASSERT_NOT_REACHED();
874 }
875
876 void RenderMultiColumnSet::addOverflowFromChildren()
877 {
878 // FIXME: Need to do much better here.
879 unsigned colCount = columnCount();
880 if (!colCount)
881 return;
882
883 LayoutRect lastRect = columnRectAt(colCount - 1);
884 addLayoutOverflow(lastRect);
885 if (!hasOverflowClip())
886 addVisualOverflow(lastRect);
887 }
888
889 VisiblePosition RenderMultiColumnSet::positionForPoint(const LayoutPoint& logicalPoint, const RenderFragmentContainer*)
890 {
891 return multiColumnFlow()->positionForPoint(translateFragmentPointToFragmentedFlow(logicalPoint, ClampHitTestTranslationToColumns), this);
892 }
893
894 LayoutPoint RenderMultiColumnSet::translateFragmentPointToFragmentedFlow(const LayoutPoint & logicalPoint, ColumnHitTestTranslationMode clampMode) const
895 {
896 // Determine which columns we intersect.
897 LayoutUnit colGap = columnGap();
898 LayoutUnit halfColGap = colGap / 2;
899
900 bool progressionIsInline = multiColumnFlow()->progressionIsInline();
901
902 LayoutPoint point = logicalPoint;
903
904 for (unsigned i = 0; i < columnCount(); i++) {
905 // Add in half the column gap to the left and right of the rect.
906 LayoutRect colRect = columnRectAt(i);
907 if (isHorizontalWritingMode() == progressionIsInline) {
908 LayoutRect gapAndColumnRect(colRect.x() - halfColGap, colRect.y(), colRect.width() + colGap, colRect.height());
909 if (point.x() >= gapAndColumnRect.x() && point.x() < gapAndColumnRect.maxX()) {
910 if (clampMode == ClampHitTestTranslationToColumns) {
911 if (progressionIsInline) {
912 // FIXME: The clamping that follows is not completely right for right-to-left
913 // content.
914 // Clamp everything above the column to its top left.
915 if (point.y() < gapAndColumnRect.y())
916 point = gapAndColumnRect.location();
917 // Clamp everything below the column to the next column's top left. If there is
918 // no next column, this still maps to just after this column.
919 else if (point.y() >= gapAndColumnRect.maxY()) {
920 point = gapAndColumnRect.location();
921 point.move(0, gapAndColumnRect.height());
922 }
923 } else {
924 if (point.x() < colRect.x())
925 point.setX(colRect.x());
926 else if (point.x() >= colRect.maxX())
927 point.setX(colRect.maxX() - 1);
928 }
929 }
930
931 LayoutSize offsetInColumn = point - colRect.location();
932 LayoutRect fragmentedFlowPortion = fragmentedFlowPortionRectAt(i);
933
934 return fragmentedFlowPortion.location() + offsetInColumn;
935 }
936 } else {
937 LayoutRect gapAndColumnRect(colRect.x(), colRect.y() - halfColGap, colRect.width(), colRect.height() + colGap);
938 if (point.y() >= gapAndColumnRect.y() && point.y() < gapAndColumnRect.maxY()) {
939 if (clampMode == ClampHitTestTranslationToColumns) {
940 if (progressionIsInline) {
941 // FIXME: The clamping that follows is not completely right for right-to-left
942 // content.
943 // Clamp everything above the column to its top left.
944 if (point.x() < gapAndColumnRect.x())
945 point = gapAndColumnRect.location();
946 // Clamp everything below the column to the next column's top left. If there is
947 // no next column, this still maps to just after this column.
948 else if (point.x() >= gapAndColumnRect.maxX()) {
949 point = gapAndColumnRect.location();
950 point.move(gapAndColumnRect.width(), 0);
951 }
952 } else {
953 if (point.y() < colRect.y())
954 point.setY(colRect.y());
955 else if (point.y() >= colRect.maxY())
956 point.setY(colRect.maxY() - 1);
957 }
958 }
959
960 LayoutSize offsetInColumn = point - colRect.location();
961 LayoutRect fragmentedFlowPortion = fragmentedFlowPortionRectAt(i);
962 return fragmentedFlowPortion.location() + offsetInColumn;
963 }
964 }
965 }
966
967 return logicalPoint;
968 }
969
970 void RenderMultiColumnSet::updateHitTestResult(HitTestResult& result, const LayoutPoint& point)
971 {
972 if (result.innerNode() || !parent()->isRenderView())
973 return;
974
975 // Note this does not work with column spans, but once we implement RenderPageSet, we can move this code
976 // over there instead (and spans of course won't be allowed on pages).
977 Node* node = document().documentElement();
978 if (node) {
979 result.setInnerNode(node);
980 if (!result.innerNonSharedNode())
981 result.setInnerNonSharedNode(node);
982 LayoutPoint adjustedPoint = translateFragmentPointToFragmentedFlow(point);
983 view().offsetForContents(adjustedPoint);
984 result.setLocalPoint(adjustedPoint);
985 }
986 }
987
988 const char* RenderMultiColumnSet::renderName() const
989 {
990 return "RenderMultiColumnSet";
991 }
992
993 }