Implement rendering support for the color-filter CSS property
[WebKit-https.git] / Source / WebCore / rendering / RenderMultiColumnSet.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 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.visitedDependentColorWithColorFilter(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 }