implement flexbox wrap-reverse
[WebKit-https.git] / Source / WebCore / rendering / RenderFlexibleBox.cpp
1 /*
2  * Copyright (C) 2011 Google 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 are
6  * met:
7  *
8  *     * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  *     * Redistributions in binary form must reproduce the above
11  * copyright notice, this list of conditions and the following disclaimer
12  * in the documentation and/or other materials provided with the
13  * distribution.
14  *     * Neither the name of Google Inc. nor the names of its
15  * contributors may be used to endorse or promote products derived from
16  * this software without specific prior written permission.
17  *
18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29  */
30
31 #include "config.h"
32 #include "RenderFlexibleBox.h"
33
34 #include "LayoutRepainter.h"
35 #include "RenderLayer.h"
36 #include "RenderView.h"
37 #include <limits>
38
39 namespace WebCore {
40
41 // Normally, -1 and 0 are not valid in a HashSet, but these are relatively likely flex-order values. Instead,
42 // we make the two smallest int values invalid flex-order values (in the css parser code we clamp them to
43 // int min + 2).
44 struct RenderFlexibleBox::FlexOrderHashTraits : WTF::GenericHashTraits<int> {
45     static const bool emptyValueIsZero = false;
46     static int emptyValue() { return std::numeric_limits<int>::min(); }
47     static void constructDeletedValue(int& slot) { slot = std::numeric_limits<int>::min() + 1; }
48     static bool isDeletedValue(int value) { return value == std::numeric_limits<int>::min() + 1; }
49 };
50
51 class RenderFlexibleBox::FlexOrderIterator {
52 public:
53     FlexOrderIterator(RenderFlexibleBox* flexibleBox, const FlexOrderHashSet& flexOrderValues)
54         : m_flexibleBox(flexibleBox)
55         , m_currentChild(0)
56         , m_orderValuesIterator(0)
57     {
58         copyToVector(flexOrderValues, m_orderValues);
59         std::sort(m_orderValues.begin(), m_orderValues.end());
60         first();
61     }
62
63     RenderBox* currentChild() { return m_currentChild; }
64
65     RenderBox* first()
66     {
67         reset();
68         return next();
69     }
70
71     RenderBox* next()
72     {
73         do {
74             if (!m_currentChild) {
75                 if (m_orderValuesIterator == m_orderValues.end())
76                     return 0;
77                 if (m_orderValuesIterator) {
78                     ++m_orderValuesIterator;
79                     if (m_orderValuesIterator == m_orderValues.end())
80                         return 0;
81                 } else
82                     m_orderValuesIterator = m_orderValues.begin();
83
84                 m_currentChild = m_flexibleBox->firstChildBox();
85             } else
86                 m_currentChild = m_currentChild->nextSiblingBox();
87         } while (!m_currentChild || m_currentChild->style()->flexOrder() != *m_orderValuesIterator);
88
89         return m_currentChild;
90     }
91
92     void reset()
93     {
94         m_currentChild = 0;
95         m_orderValuesIterator = 0;
96     }
97
98 private:
99     RenderFlexibleBox* m_flexibleBox;
100     RenderBox* m_currentChild;
101     Vector<int> m_orderValues;
102     Vector<int>::const_iterator m_orderValuesIterator;
103 };
104
105 struct RenderFlexibleBox::WrapReverseContext {
106     explicit WrapReverseContext(EFlexWrap flexWrap)
107         : isWrapReverse(flexWrap == FlexWrapReverse)
108     {
109     }
110
111     void addCrossAxisOffset(LayoutUnit offset)
112     {
113         if (!isWrapReverse)
114             return;
115         crossAxisOffsets.append(offset);
116     }
117
118     void addNumberOfChildrenOnLine(size_t numberOfChildren)
119     {
120         if (!isWrapReverse)
121             return;
122         childrenPerLine.append(numberOfChildren);
123     }
124
125     LayoutUnit lineCrossAxisDelta(size_t line, LayoutUnit crossAxisContentExtent) const
126     {
127         ASSERT(line + 1 < crossAxisOffsets.size());
128         LayoutUnit lineHeight = crossAxisOffsets[line + 1] - crossAxisOffsets[line];
129         LayoutUnit originalOffset = crossAxisOffsets[line] - crossAxisOffsets[0];
130         LayoutUnit newOffset = crossAxisContentExtent - originalOffset - lineHeight;
131         return newOffset - originalOffset;
132     }
133
134     WTF::Vector<LayoutUnit> crossAxisOffsets;
135     WTF::Vector<size_t> childrenPerLine;
136     bool isWrapReverse;
137 };
138
139
140 RenderFlexibleBox::RenderFlexibleBox(Node* node)
141     : RenderBlock(node)
142 {
143     setChildrenInline(false); // All of our children must be block-level.
144 }
145
146 RenderFlexibleBox::~RenderFlexibleBox()
147 {
148 }
149
150 const char* RenderFlexibleBox::renderName() const
151 {
152     return "RenderFlexibleBox";
153 }
154
155 static LayoutUnit marginLogicalWidthForChild(RenderBox* child, RenderStyle* parentStyle)
156 {
157     // A margin has three types: fixed, percentage, and auto (variable).
158     // Auto and percentage margins become 0 when computing min/max width.
159     // Fixed margins can be added in as is.
160     Length marginLeft = child->style()->marginStartUsing(parentStyle);
161     Length marginRight = child->style()->marginEndUsing(parentStyle);
162     LayoutUnit margin = 0;
163     if (marginLeft.isFixed())
164         margin += marginLeft.value();
165     if (marginRight.isFixed())
166         margin += marginRight.value();
167     return margin;
168 }
169
170 void RenderFlexibleBox::computePreferredLogicalWidths()
171 {
172     ASSERT(preferredLogicalWidthsDirty());
173
174     RenderStyle* styleToUse = style();
175     if (styleToUse->logicalWidth().isFixed() && styleToUse->logicalWidth().value() > 0)
176         m_minPreferredLogicalWidth = m_maxPreferredLogicalWidth = computeContentBoxLogicalWidth(styleToUse->logicalWidth().value());
177     else {
178         m_minPreferredLogicalWidth = m_maxPreferredLogicalWidth = 0;
179
180         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
181             if (child->isPositioned())
182                 continue;
183
184             LayoutUnit margin = marginLogicalWidthForChild(child, style());
185             bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode();
186             LayoutUnit minPreferredLogicalWidth = hasOrthogonalWritingMode ? child->logicalHeight() : child->minPreferredLogicalWidth();
187             LayoutUnit maxPreferredLogicalWidth = hasOrthogonalWritingMode ? child->logicalHeight() : child->maxPreferredLogicalWidth();
188             minPreferredLogicalWidth += margin;
189             maxPreferredLogicalWidth += margin;
190             if (!isColumnFlow()) {
191                 m_minPreferredLogicalWidth += minPreferredLogicalWidth;
192                 m_maxPreferredLogicalWidth += maxPreferredLogicalWidth;
193             } else {
194                 m_minPreferredLogicalWidth = std::max(minPreferredLogicalWidth, m_minPreferredLogicalWidth);
195                 m_maxPreferredLogicalWidth = std::max(maxPreferredLogicalWidth, m_maxPreferredLogicalWidth);
196             }
197         }
198
199         m_maxPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
200     }
201
202     LayoutUnit scrollbarWidth = 0;
203     if (hasOverflowClip()) {
204         if (isHorizontalWritingMode() && styleToUse->overflowY() == OSCROLL) {
205             layer()->setHasVerticalScrollbar(true);
206             scrollbarWidth = verticalScrollbarWidth();
207         } else if (!isHorizontalWritingMode() && styleToUse->overflowX() == OSCROLL) {
208             layer()->setHasHorizontalScrollbar(true);
209             scrollbarWidth = horizontalScrollbarHeight();
210         }
211     }
212
213     m_maxPreferredLogicalWidth += scrollbarWidth;
214     m_minPreferredLogicalWidth += scrollbarWidth;
215
216     if (styleToUse->logicalMinWidth().isFixed() && styleToUse->logicalMinWidth().value() > 0) {
217         m_maxPreferredLogicalWidth = std::max(m_maxPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMinWidth().value()));
218         m_minPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMinWidth().value()));
219     }
220
221     if (styleToUse->logicalMaxWidth().isFixed()) {
222         m_maxPreferredLogicalWidth = std::min(m_maxPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMaxWidth().value()));
223         m_minPreferredLogicalWidth = std::min(m_minPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMaxWidth().value()));
224     }
225
226     LayoutUnit borderAndPadding = borderAndPaddingLogicalWidth();
227     m_minPreferredLogicalWidth += borderAndPadding;
228     m_maxPreferredLogicalWidth += borderAndPadding;
229
230     setPreferredLogicalWidthsDirty(false);
231 }
232
233 void RenderFlexibleBox::layoutBlock(bool relayoutChildren, int, BlockLayoutPass)
234 {
235     ASSERT(needsLayout());
236
237     if (!relayoutChildren && simplifiedLayout())
238         return;
239
240     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
241     LayoutStateMaintainer statePusher(view(), this, locationOffset(), hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
242
243     if (inRenderFlowThread()) {
244         // Regions changing widths can force us to relayout our children.
245         if (logicalWidthChangedInRegions())
246             relayoutChildren = true;
247     }
248     computeInitialRegionRangeForBlock();
249
250     IntSize previousSize = size();
251
252     setLogicalHeight(0);
253     // We need to call both of these because we grab both crossAxisExtent and mainAxisExtent in layoutFlexItems.
254     computeLogicalWidth();
255     computeLogicalHeight();
256
257     m_overflow.clear();
258
259     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
260     if (scrollsOverflow()) {
261         if (style()->overflowX() == OSCROLL)
262             layer()->setHasHorizontalScrollbar(true);
263         if (style()->overflowY() == OSCROLL)
264             layer()->setHasVerticalScrollbar(true);
265     }
266
267     layoutFlexItems(relayoutChildren);
268
269     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
270     computeLogicalHeight();
271
272     if (size() != previousSize)
273         relayoutChildren = true;
274
275     layoutPositionedObjects(relayoutChildren || isRoot());
276
277     computeRegionRangeForBlock();
278
279     // FIXME: css3/flexbox/repaint-rtl-column.html seems to repaint more overflow than it needs to.
280     computeOverflow(oldClientAfterEdge);
281     statePusher.pop();
282
283     updateLayerTransform();
284
285     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
286     // we overflow or not.
287     updateScrollInfoAfterLayout();
288
289     repainter.repaintAfterLayout();
290
291     setNeedsLayout(false);
292 }
293
294 bool RenderFlexibleBox::hasOrthogonalFlow(RenderBox* child) const
295 {
296     // FIXME: If the child is a flexbox, then we need to check isHorizontalFlow.
297     return isHorizontalFlow() != child->isHorizontalWritingMode();
298 }
299
300 bool RenderFlexibleBox::isColumnFlow() const
301 {
302     return style()->isColumnFlexDirection();
303 }
304
305 bool RenderFlexibleBox::isHorizontalFlow() const
306 {
307     if (isHorizontalWritingMode())
308         return !isColumnFlow();
309     return isColumnFlow();
310 }
311
312 bool RenderFlexibleBox::isLeftToRightFlow() const
313 {
314     if (isColumnFlow())
315         return style()->writingMode() == TopToBottomWritingMode || style()->writingMode() == LeftToRightWritingMode;
316     return style()->isLeftToRightDirection() ^ (style()->flexDirection() == FlowRowReverse);
317 }
318
319 bool RenderFlexibleBox::isMultiline() const
320 {
321     return style()->flexWrap() != FlexWrapNone;
322 }
323
324 Length RenderFlexibleBox::mainAxisLengthForChild(RenderBox* child) const
325 {
326     return isHorizontalFlow() ? child->style()->width() : child->style()->height();
327 }
328
329 Length RenderFlexibleBox::crossAxisLength() const
330 {
331     return isHorizontalFlow() ? style()->height() : style()->width();
332 }
333
334 void RenderFlexibleBox::setCrossAxisExtent(LayoutUnit extent)
335 {
336     if (isHorizontalFlow())
337         setHeight(extent);
338     else
339         setWidth(extent);
340 }
341
342 LayoutUnit RenderFlexibleBox::crossAxisExtentForChild(RenderBox* child)
343 {
344     return isHorizontalFlow() ? child->height() : child->width();
345 }
346
347 LayoutUnit RenderFlexibleBox::mainAxisExtentForChild(RenderBox* child)
348 {
349     return isHorizontalFlow() ? child->width() : child->height();
350 }
351
352 LayoutUnit RenderFlexibleBox::crossAxisExtent() const
353 {
354     return isHorizontalFlow() ? height() : width();
355 }
356
357 LayoutUnit RenderFlexibleBox::mainAxisExtent() const
358 {
359     return isHorizontalFlow() ? width() : height();
360 }
361
362 LayoutUnit RenderFlexibleBox::crossAxisContentExtent() const
363 {
364     return isHorizontalFlow() ? contentHeight() : contentWidth();
365 }
366
367 LayoutUnit RenderFlexibleBox::mainAxisContentExtent() const
368 {
369     return isHorizontalFlow() ? contentWidth() : contentHeight();
370 }
371
372 WritingMode RenderFlexibleBox::transformedWritingMode() const
373 {
374     WritingMode mode = style()->writingMode();
375     if (!isColumnFlow())
376         return mode;
377
378     switch (mode) {
379     case TopToBottomWritingMode:
380     case BottomToTopWritingMode:
381         return style()->isLeftToRightDirection() ? LeftToRightWritingMode : RightToLeftWritingMode;
382     case LeftToRightWritingMode:
383     case RightToLeftWritingMode:
384         return style()->isLeftToRightDirection() ? TopToBottomWritingMode : BottomToTopWritingMode;
385     }
386     ASSERT_NOT_REACHED();
387     return TopToBottomWritingMode;
388 }
389
390 LayoutUnit RenderFlexibleBox::flowAwareBorderStart() const
391 {
392     if (isHorizontalFlow())
393         return isLeftToRightFlow() ? borderLeft() : borderRight();
394     return isLeftToRightFlow() ? borderTop() : borderBottom();
395 }
396
397 LayoutUnit RenderFlexibleBox::flowAwareBorderEnd() const
398 {
399     if (isHorizontalFlow())
400         return isLeftToRightFlow() ? borderRight() : borderLeft();
401     return isLeftToRightFlow() ? borderBottom() : borderTop();
402 }
403
404 LayoutUnit RenderFlexibleBox::flowAwareBorderBefore() const
405 {
406     switch (transformedWritingMode()) {
407     case TopToBottomWritingMode:
408         return borderTop();
409     case BottomToTopWritingMode:
410         return borderBottom();
411     case LeftToRightWritingMode:
412         return borderLeft();
413     case RightToLeftWritingMode:
414         return borderRight();
415     }
416     ASSERT_NOT_REACHED();
417     return borderTop();
418 }
419
420 LayoutUnit RenderFlexibleBox::flowAwareBorderAfter() const
421 {
422     switch (transformedWritingMode()) {
423     case TopToBottomWritingMode:
424         return borderBottom();
425     case BottomToTopWritingMode:
426         return borderTop();
427     case LeftToRightWritingMode:
428         return borderRight();
429     case RightToLeftWritingMode:
430         return borderLeft();
431     }
432     ASSERT_NOT_REACHED();
433     return borderTop();
434 }
435
436 LayoutUnit RenderFlexibleBox::flowAwarePaddingStart() const
437 {
438     if (isHorizontalFlow())
439         return isLeftToRightFlow() ? paddingLeft() : paddingRight();
440     return isLeftToRightFlow() ? paddingTop() : paddingBottom();
441 }
442
443 LayoutUnit RenderFlexibleBox::flowAwarePaddingEnd() const
444 {
445     if (isHorizontalFlow())
446         return isLeftToRightFlow() ? paddingRight() : paddingLeft();
447     return isLeftToRightFlow() ? paddingBottom() : paddingTop();
448 }
449
450 LayoutUnit RenderFlexibleBox::flowAwarePaddingBefore() const
451 {
452     switch (transformedWritingMode()) {
453     case TopToBottomWritingMode:
454         return paddingTop();
455     case BottomToTopWritingMode:
456         return paddingBottom();
457     case LeftToRightWritingMode:
458         return paddingLeft();
459     case RightToLeftWritingMode:
460         return paddingRight();
461     }
462     ASSERT_NOT_REACHED();
463     return paddingTop();
464 }
465
466 LayoutUnit RenderFlexibleBox::flowAwarePaddingAfter() const
467 {
468     switch (transformedWritingMode()) {
469     case TopToBottomWritingMode:
470         return paddingBottom();
471     case BottomToTopWritingMode:
472         return paddingTop();
473     case LeftToRightWritingMode:
474         return paddingRight();
475     case RightToLeftWritingMode:
476         return paddingLeft();
477     }
478     ASSERT_NOT_REACHED();
479     return paddingTop();
480 }
481
482 LayoutUnit RenderFlexibleBox::flowAwareMarginStartForChild(RenderBox* child) const
483 {
484     if (isHorizontalFlow())
485         return isLeftToRightFlow() ? child->marginLeft() : child->marginRight();
486     return isLeftToRightFlow() ? child->marginTop() : child->marginBottom();
487 }
488
489 LayoutUnit RenderFlexibleBox::flowAwareMarginEndForChild(RenderBox* child) const
490 {
491     if (isHorizontalFlow())
492         return isLeftToRightFlow() ? child->marginRight() : child->marginLeft();
493     return isLeftToRightFlow() ? child->marginBottom() : child->marginTop();
494 }
495
496 LayoutUnit RenderFlexibleBox::flowAwareMarginBeforeForChild(RenderBox* child) const
497 {
498     switch (transformedWritingMode()) {
499     case TopToBottomWritingMode:
500         return child->marginTop();
501     case BottomToTopWritingMode:
502         return child->marginBottom();
503     case LeftToRightWritingMode:
504         return child->marginLeft();
505     case RightToLeftWritingMode:
506         return child->marginRight();
507     }
508     ASSERT_NOT_REACHED();
509     return marginTop();
510 }
511
512 LayoutUnit RenderFlexibleBox::flowAwareMarginAfterForChild(RenderBox* child) const
513 {
514     switch (transformedWritingMode()) {
515     case TopToBottomWritingMode:
516         return child->marginBottom();
517     case BottomToTopWritingMode:
518         return child->marginTop();
519     case LeftToRightWritingMode:
520         return child->marginRight();
521     case RightToLeftWritingMode:
522         return child->marginLeft();
523     }
524     ASSERT_NOT_REACHED();
525     return marginBottom();
526 }
527
528 LayoutUnit RenderFlexibleBox::crossAxisMarginExtentForChild(RenderBox* child) const
529 {
530     return isHorizontalFlow() ? child->marginHeight() : child->marginWidth();
531 }
532
533 LayoutUnit RenderFlexibleBox::crossAxisScrollbarExtent() const
534 {
535     return isHorizontalFlow() ? horizontalScrollbarHeight() : verticalScrollbarWidth();
536 }
537
538 LayoutPoint RenderFlexibleBox::flowAwareLocationForChild(RenderBox* child) const
539 {
540     return isHorizontalFlow() ? child->location() : child->location().transposedPoint();
541 }
542
543 void RenderFlexibleBox::setFlowAwareLocationForChild(RenderBox* child, const LayoutPoint& location)
544 {
545     if (isHorizontalFlow())
546         child->setLocation(location);
547     else
548         child->setLocation(location.transposedPoint());
549 }
550
551 LayoutUnit RenderFlexibleBox::mainAxisBorderAndPaddingExtentForChild(RenderBox* child) const
552 {
553     return isHorizontalFlow() ? child->borderAndPaddingWidth() : child->borderAndPaddingHeight();
554 }
555
556 LayoutUnit RenderFlexibleBox::mainAxisScrollbarExtentForChild(RenderBox* child) const
557 {
558     return isHorizontalFlow() ? child->verticalScrollbarWidth() : child->horizontalScrollbarHeight();
559 }
560
561 LayoutUnit RenderFlexibleBox::preferredMainAxisContentExtentForChild(RenderBox* child) const
562 {
563     Length mainAxisLength = mainAxisLengthForChild(child);
564     if (mainAxisLength.isAuto()) {
565         LayoutUnit mainAxisExtent = hasOrthogonalFlow(child) ? child->logicalHeight() : child->maxPreferredLogicalWidth();
566         return mainAxisExtent - mainAxisBorderAndPaddingExtentForChild(child) - mainAxisScrollbarExtentForChild(child);
567     }
568     return mainAxisLength.calcMinValue(mainAxisContentExtent());
569 }
570
571 void RenderFlexibleBox::layoutFlexItems(bool relayoutChildren)
572 {
573     FlexOrderHashSet flexOrderValues;
574     computeMainAxisPreferredSizes(relayoutChildren, flexOrderValues);
575
576     OrderedFlexItemList orderedChildren;
577     LayoutUnit preferredMainAxisExtent;
578     float totalPositiveFlexibility;
579     float totalNegativeFlexibility;
580     FlexOrderIterator flexIterator(this, flexOrderValues);
581
582     // For wrap-reverse, we need to layout as wrap, then reverse the lines. The next two arrays
583     // are some extra information so it's possible to reverse the lines.
584     WrapReverseContext wrapReverseContext(style()->flexWrap());
585
586     LayoutUnit crossAxisOffset = flowAwareBorderBefore() + flowAwarePaddingBefore();
587     LayoutUnit mainAxisFlexibleSpace = mainAxisContentExtent();
588     while (computeNextFlexLine(flexIterator, orderedChildren, preferredMainAxisExtent, totalPositiveFlexibility, totalNegativeFlexibility)) {
589         LayoutUnit availableFreeSpace = mainAxisFlexibleSpace - preferredMainAxisExtent;
590         InflexibleFlexItemSize inflexibleItems;
591         WTF::Vector<LayoutUnit> childSizes;
592         while (!runFreeSpaceAllocationAlgorithm(orderedChildren, availableFreeSpace, totalPositiveFlexibility, totalNegativeFlexibility, inflexibleItems, childSizes)) {
593             ASSERT(totalPositiveFlexibility >= 0 && totalNegativeFlexibility >= 0);
594             ASSERT(inflexibleItems.size() > 0);
595         }
596
597         wrapReverseContext.addNumberOfChildrenOnLine(orderedChildren.size());
598         wrapReverseContext.addCrossAxisOffset(crossAxisOffset);
599         layoutAndPlaceChildren(crossAxisOffset, orderedChildren, childSizes, availableFreeSpace);
600     }
601
602     if (wrapReverseContext.isWrapReverse) {
603         wrapReverseContext.addCrossAxisOffset(crossAxisOffset);
604         flipForWrapReverse(flexIterator, wrapReverseContext);
605     }
606
607     // direction:rtl + flex-direction:column means the cross-axis direction is flipped.
608     flipForRightToLeftColumn(flexIterator);
609 }
610
611 float RenderFlexibleBox::positiveFlexForChild(RenderBox* child) const
612 {
613     return isHorizontalFlow() ? child->style()->flexboxWidthPositiveFlex() : child->style()->flexboxHeightPositiveFlex();
614 }
615
616 float RenderFlexibleBox::negativeFlexForChild(RenderBox* child) const
617 {
618     return isHorizontalFlow() ? child->style()->flexboxWidthNegativeFlex() : child->style()->flexboxHeightNegativeFlex();
619 }
620
621 LayoutUnit RenderFlexibleBox::availableAlignmentSpaceForChild(LayoutUnit lineCrossAxisExtent, RenderBox* child)
622 {
623     LayoutUnit childCrossExtent = crossAxisMarginExtentForChild(child) + crossAxisExtentForChild(child);
624     return lineCrossAxisExtent - childCrossExtent;
625 }
626
627 LayoutUnit RenderFlexibleBox::marginBoxAscentForChild(RenderBox* child)
628 {
629     LayoutUnit ascent = child->firstLineBoxBaseline();
630     if (ascent == -1)
631         ascent = crossAxisExtentForChild(child) + flowAwareMarginAfterForChild(child);
632     return ascent + flowAwareMarginBeforeForChild(child);
633 }
634
635 void RenderFlexibleBox::computeMainAxisPreferredSizes(bool relayoutChildren, FlexOrderHashSet& flexOrderValues)
636 {
637     LayoutUnit flexboxAvailableContentExtent = mainAxisContentExtent();
638     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
639         flexOrderValues.add(child->style()->flexOrder());
640
641         if (child->isPositioned())
642             continue;
643
644         child->clearOverrideSize();
645         if (mainAxisLengthForChild(child).isAuto()) {
646             if (!relayoutChildren)
647                 child->setChildNeedsLayout(true);
648             child->layoutIfNeeded();
649         }
650
651         // We set the margins because we want to make sure 'auto' has a margin
652         // of 0 and because if we're not auto sizing, we don't do a layout that
653         // computes the start/end margins.
654         if (isHorizontalFlow()) {
655             child->setMarginLeft(child->style()->marginLeft().calcMinValue(flexboxAvailableContentExtent));
656             child->setMarginRight(child->style()->marginRight().calcMinValue(flexboxAvailableContentExtent));
657         } else {
658             child->setMarginTop(child->style()->marginTop().calcMinValue(flexboxAvailableContentExtent));
659             child->setMarginBottom(child->style()->marginBottom().calcMinValue(flexboxAvailableContentExtent));
660         }
661     }
662 }
663
664 bool RenderFlexibleBox::computeNextFlexLine(FlexOrderIterator& iterator, OrderedFlexItemList& orderedChildren, LayoutUnit& preferredMainAxisExtent, float& totalPositiveFlexibility, float& totalNegativeFlexibility)
665 {
666     orderedChildren.clear();
667     preferredMainAxisExtent = 0;
668     totalPositiveFlexibility = totalNegativeFlexibility = 0;
669
670     if (!iterator.currentChild())
671         return false;
672
673     for (RenderBox* child = iterator.currentChild(); child; child = iterator.next()) {
674         if (child->isPositioned()) {
675             orderedChildren.append(child);
676             continue;
677         }
678
679         LayoutUnit childMainAxisExtent = mainAxisBorderAndPaddingExtentForChild(child) + preferredMainAxisContentExtentForChild(child);
680         if (isHorizontalFlow())
681             childMainAxisExtent += child->marginWidth();
682         else
683             childMainAxisExtent += child->marginHeight();
684
685         if (isMultiline() && preferredMainAxisExtent + childMainAxisExtent > mainAxisContentExtent() && orderedChildren.size() > 0)
686             break;
687         orderedChildren.append(child);
688         preferredMainAxisExtent += childMainAxisExtent;
689         totalPositiveFlexibility += positiveFlexForChild(child);
690         totalNegativeFlexibility += negativeFlexForChild(child);
691     }
692     return true;
693 }
694
695 // Returns true if we successfully ran the algorithm and sized the flex items.
696 bool RenderFlexibleBox::runFreeSpaceAllocationAlgorithm(const OrderedFlexItemList& children, LayoutUnit& availableFreeSpace, float& totalPositiveFlexibility, float& totalNegativeFlexibility, InflexibleFlexItemSize& inflexibleItems, WTF::Vector<LayoutUnit>& childSizes)
697 {
698     childSizes.clear();
699
700     LayoutUnit flexboxAvailableContentExtent = mainAxisContentExtent();
701     for (size_t i = 0; i < children.size(); ++i) {
702         RenderBox* child = children[i];
703         if (child->isPositioned()) {
704             childSizes.append(0);
705             continue;
706         }
707
708         LayoutUnit childPreferredSize;
709         if (inflexibleItems.contains(child))
710             childPreferredSize = inflexibleItems.get(child);
711         else {
712             childPreferredSize = preferredMainAxisContentExtentForChild(child);
713             if (availableFreeSpace > 0 && totalPositiveFlexibility > 0) {
714                 childPreferredSize += lroundf(availableFreeSpace * positiveFlexForChild(child) / totalPositiveFlexibility);
715
716                 Length childLogicalMaxWidth = isHorizontalFlow() ? child->style()->maxWidth() : child->style()->maxHeight();
717                 if (!childLogicalMaxWidth.isUndefined() && childLogicalMaxWidth.isSpecified() && childPreferredSize > childLogicalMaxWidth.calcValue(flexboxAvailableContentExtent)) {
718                     childPreferredSize = childLogicalMaxWidth.calcValue(flexboxAvailableContentExtent);
719                     availableFreeSpace -= childPreferredSize - preferredMainAxisContentExtentForChild(child);
720                     totalPositiveFlexibility -= positiveFlexForChild(child);
721
722                     inflexibleItems.set(child, childPreferredSize);
723                     return false;
724                 }
725             } else if (availableFreeSpace < 0 && totalNegativeFlexibility > 0) {
726                 childPreferredSize += lroundf(availableFreeSpace * negativeFlexForChild(child) / totalNegativeFlexibility);
727
728                 Length childLogicalMinWidth = isHorizontalFlow() ? child->style()->minWidth() : child->style()->minHeight();
729                 if (!childLogicalMinWidth.isUndefined() && childLogicalMinWidth.isSpecified() && childPreferredSize < childLogicalMinWidth.calcValue(flexboxAvailableContentExtent)) {
730                     childPreferredSize = childLogicalMinWidth.calcValue(flexboxAvailableContentExtent);
731                     availableFreeSpace += preferredMainAxisContentExtentForChild(child) - childPreferredSize;
732                     totalNegativeFlexibility -= negativeFlexForChild(child);
733
734                     inflexibleItems.set(child, childPreferredSize);
735                     return false;
736                 }
737             }
738         }
739         childSizes.append(childPreferredSize);
740     }
741     return true;
742 }
743
744 static LayoutUnit initialPackingOffset(LayoutUnit availableFreeSpace, EFlexPack flexPack, size_t numberOfChildren)
745 {
746     if (availableFreeSpace > 0) {
747         if (flexPack == PackEnd)
748             return availableFreeSpace;
749         if (flexPack == PackCenter)
750             return availableFreeSpace / 2;
751         if (flexPack == PackDistribute && numberOfChildren)
752             return availableFreeSpace / (2 * numberOfChildren);
753     } else if (availableFreeSpace < 0) {
754         if (flexPack == PackCenter || flexPack == PackDistribute)
755             return availableFreeSpace / 2;
756     }
757     return 0;
758 }
759
760 static LayoutUnit packingSpaceBetweenChildren(LayoutUnit availableFreeSpace, EFlexPack flexPack, size_t numberOfChildren)
761 {
762     if (availableFreeSpace > 0 && numberOfChildren > 1) {
763         if (flexPack == PackJustify)
764             return availableFreeSpace / (numberOfChildren - 1);
765         if (flexPack == PackDistribute)
766             return availableFreeSpace / numberOfChildren;
767     }
768     return 0;
769 }
770
771 void RenderFlexibleBox::setLogicalOverrideSize(RenderBox* child, LayoutUnit childPreferredSize)
772 {
773     // FIXME: Rename setOverrideWidth/setOverrideHeight to setOverrideLogicalWidth/setOverrideLogicalHeight.
774     if (hasOrthogonalFlow(child))
775         child->setOverrideHeight(childPreferredSize);
776     else
777         child->setOverrideWidth(childPreferredSize);
778 }
779
780 void RenderFlexibleBox::prepareChildForPositionedLayout(RenderBox* child, LayoutUnit mainAxisOffset, LayoutUnit crossAxisOffset)
781 {
782     ASSERT(child->isPositioned());
783     child->containingBlock()->insertPositionedObject(child);
784     RenderLayer* childLayer = child->layer();
785     LayoutUnit inlinePosition = isColumnFlow() ? crossAxisOffset : mainAxisOffset;
786     if (style()->flexDirection() == FlowRowReverse)
787         inlinePosition = mainAxisExtent() - mainAxisOffset;
788     childLayer->setStaticInlinePosition(inlinePosition); // FIXME: Not right for regions.
789
790     LayoutUnit staticBlockPosition = isColumnFlow() ? mainAxisOffset : crossAxisOffset;
791     if (childLayer->staticBlockPosition() != staticBlockPosition) {
792         childLayer->setStaticBlockPosition(staticBlockPosition);
793         if (child->style()->hasStaticBlockPosition(style()->isHorizontalWritingMode()))
794             child->setChildNeedsLayout(true, false);
795     }
796 }
797
798 static EFlexAlign flexAlignForChild(RenderBox* child)
799 {
800     EFlexAlign align = child->style()->flexItemAlign();
801     if (align == AlignAuto)
802         align = child->parent()->style()->flexAlign();
803
804     if (child->parent()->style()->flexWrap() == FlexWrapReverse) {
805         if (align == AlignStart)
806             align = AlignEnd;
807         else if (align == AlignEnd)
808             align = AlignStart;
809     }
810
811     return align;
812 }
813
814 void RenderFlexibleBox::layoutAndPlaceChildren(LayoutUnit& crossAxisOffset, const OrderedFlexItemList& children, const WTF::Vector<LayoutUnit>& childSizes, LayoutUnit availableFreeSpace)
815 {
816     LayoutUnit mainAxisOffset = flowAwareBorderStart() + flowAwarePaddingStart();
817     mainAxisOffset += initialPackingOffset(availableFreeSpace, style()->flexPack(), childSizes.size());
818     if (style()->flexDirection() == FlowRowReverse)
819         mainAxisOffset += isHorizontalFlow() ? verticalScrollbarWidth() : horizontalScrollbarHeight();
820
821     LayoutUnit totalMainExtent = mainAxisExtent();
822     LayoutUnit maxAscent = 0, maxDescent = 0; // Used when flex-align: baseline.
823     LayoutUnit maxChildCrossAxisExtent = 0;
824     bool shouldFlipMainAxis = !isColumnFlow() && !isLeftToRightFlow();
825     for (size_t i = 0; i < children.size(); ++i) {
826         RenderBox* child = children[i];
827         if (child->isPositioned()) {
828             prepareChildForPositionedLayout(child, mainAxisOffset, crossAxisOffset);
829             mainAxisOffset += packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
830             continue;
831         }
832         LayoutUnit childPreferredSize = childSizes[i] + mainAxisBorderAndPaddingExtentForChild(child);
833         setLogicalOverrideSize(child, childPreferredSize);
834         child->setChildNeedsLayout(true);
835         child->layoutIfNeeded();
836
837         LayoutUnit childCrossAxisExtent;
838         if (flexAlignForChild(child) == AlignBaseline) {
839             LayoutUnit ascent = marginBoxAscentForChild(child);
840             LayoutUnit descent = (crossAxisMarginExtentForChild(child) + crossAxisExtentForChild(child)) - ascent;
841
842             maxAscent = std::max(maxAscent, ascent);
843             maxDescent = std::max(maxDescent, descent);
844
845             childCrossAxisExtent = maxAscent + maxDescent;
846         } else
847             childCrossAxisExtent =  crossAxisExtentForChild(child);
848         if (crossAxisLength().isAuto())
849             setCrossAxisExtent(std::max(crossAxisExtent(), crossAxisOffset + flowAwareBorderAfter() + flowAwarePaddingAfter() + crossAxisMarginExtentForChild(child) + childCrossAxisExtent + crossAxisScrollbarExtent()));
850         maxChildCrossAxisExtent = std::max(maxChildCrossAxisExtent, childCrossAxisExtent + crossAxisMarginExtentForChild(child));
851
852         mainAxisOffset += flowAwareMarginStartForChild(child);
853
854         LayoutUnit childMainExtent = mainAxisExtentForChild(child);
855         IntPoint childLocation(shouldFlipMainAxis ? totalMainExtent - mainAxisOffset - childMainExtent : mainAxisOffset,
856             crossAxisOffset + flowAwareMarginBeforeForChild(child));
857
858         // FIXME: Supporting layout deltas.
859         setFlowAwareLocationForChild(child, childLocation);
860         mainAxisOffset += childMainExtent + flowAwareMarginEndForChild(child);
861
862         mainAxisOffset += packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
863     }
864
865     if (isColumnFlow())
866         setLogicalHeight(mainAxisOffset + flowAwareBorderEnd() + flowAwarePaddingEnd() + scrollbarLogicalHeight());
867
868     if (style()->flexDirection() == FlowColumnReverse) {
869         // We have to do an extra pass for column-reverse to reposition the flex items since the start depends
870         // on the height of the flexbox, which we only know after we've positioned all the flex items.
871         computeLogicalHeight();
872         layoutColumnReverse(children, childSizes, crossAxisOffset, availableFreeSpace);
873     }
874
875     LayoutUnit lineCrossAxisExtent = isMultiline() ? maxChildCrossAxisExtent : crossAxisContentExtent();
876     alignChildren(children, lineCrossAxisExtent, maxAscent);
877
878     crossAxisOffset += lineCrossAxisExtent;
879 }
880
881 void RenderFlexibleBox::layoutColumnReverse(const OrderedFlexItemList& children, const WTF::Vector<LayoutUnit>& childSizes, LayoutUnit crossAxisOffset, LayoutUnit availableFreeSpace)
882 {
883     // This is similar to the logic in layoutAndPlaceChildren, except we place the children
884     // starting from the end of the flexbox. We also don't need to layout anything since we're
885     // just moving the children to a new position.
886     LayoutUnit mainAxisOffset = logicalHeight() - flowAwareBorderEnd() - flowAwarePaddingEnd();
887     mainAxisOffset -= initialPackingOffset(availableFreeSpace, style()->flexPack(), childSizes.size());
888     mainAxisOffset -= isHorizontalFlow() ? verticalScrollbarWidth() : horizontalScrollbarHeight();
889
890     for (size_t i = 0; i < children.size(); ++i) {
891         RenderBox* child = children[i];
892         if (child->isPositioned()) {
893             child->layer()->setStaticBlockPosition(mainAxisOffset);
894             mainAxisOffset -= packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
895             continue;
896         }
897         mainAxisOffset -= mainAxisExtentForChild(child) + flowAwareMarginEndForChild(child);
898
899         LayoutRect oldRect = child->frameRect();
900         setFlowAwareLocationForChild(child, IntPoint(mainAxisOffset, crossAxisOffset + flowAwareMarginBeforeForChild(child)));
901         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
902             child->repaintDuringLayoutIfMoved(oldRect);
903
904         mainAxisOffset -= flowAwareMarginStartForChild(child);
905         mainAxisOffset -= packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
906     }
907 }
908
909 void RenderFlexibleBox::adjustAlignmentForChild(RenderBox* child, LayoutUnit delta)
910 {
911     LayoutRect oldRect = child->frameRect();
912
913     setFlowAwareLocationForChild(child, flowAwareLocationForChild(child) + LayoutSize(0, delta));
914
915     // If the child moved, we have to repaint it as well as any floating/positioned
916     // descendants. An exception is if we need a layout. In this case, we know we're going to
917     // repaint ourselves (and the child) anyway.
918     if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
919         child->repaintDuringLayoutIfMoved(oldRect);
920 }
921
922 void RenderFlexibleBox::alignChildren(const OrderedFlexItemList& children, LayoutUnit lineCrossAxisExtent, LayoutUnit maxAscent)
923 {
924     LayoutUnit minMarginAfterBaseline = std::numeric_limits<LayoutUnit>::max();
925
926     for (size_t i = 0; i < children.size(); ++i) {
927         RenderBox* child = children[i];
928         switch (flexAlignForChild(child)) {
929         case AlignAuto:
930             ASSERT_NOT_REACHED();
931             break;
932         case AlignStretch: {
933             if (!isColumnFlow() && child->style()->logicalHeight().isAuto()) {
934                 LayoutUnit logicalHeightBefore = child->logicalHeight();
935                 LayoutUnit stretchedLogicalHeight = child->logicalHeight() + availableAlignmentSpaceForChild(lineCrossAxisExtent, child);
936                 child->setLogicalHeight(stretchedLogicalHeight);
937                 child->computeLogicalHeight();
938
939                 if (child->logicalHeight() != logicalHeightBefore) {
940                     child->setOverrideHeight(child->logicalHeight());
941                     child->setLogicalHeight(0);
942                     child->setChildNeedsLayout(true);
943                     child->layoutIfNeeded();
944                 }
945             } else if (isColumnFlow() && child->style()->logicalWidth().isAuto() && isMultiline()) {
946                 // FIXME: Handle min-width and max-width.
947                 LayoutUnit childWidth = lineCrossAxisExtent - crossAxisMarginExtentForChild(child);
948                 child->setOverrideWidth(std::max(0, childWidth));
949                 child->setChildNeedsLayout(true);
950                 child->layoutIfNeeded();
951             }
952             // Since wrap-reverse flips cross start and cross end, strech children should be aligned with the cross end.
953             if (style()->flexWrap() == FlexWrapReverse)
954                 adjustAlignmentForChild(child, availableAlignmentSpaceForChild(lineCrossAxisExtent, child));
955             break;
956         }
957         case AlignStart:
958             break;
959         case AlignEnd:
960             adjustAlignmentForChild(child, availableAlignmentSpaceForChild(lineCrossAxisExtent, child));
961             break;
962         case AlignCenter:
963             adjustAlignmentForChild(child, availableAlignmentSpaceForChild(lineCrossAxisExtent, child) / 2);
964             break;
965         case AlignBaseline: {
966             LayoutUnit ascent = marginBoxAscentForChild(child);
967             LayoutUnit startOffset = maxAscent - ascent;
968             adjustAlignmentForChild(child, startOffset);
969
970             if (style()->flexWrap() == FlexWrapReverse)
971                 minMarginAfterBaseline = std::min(minMarginAfterBaseline, availableAlignmentSpaceForChild(lineCrossAxisExtent, child) - startOffset);
972             break;
973         }
974         }
975     }
976
977     // wrap-reverse flips the cross axis start and end. For baseline alignment, this means we
978     // need to align the after edge of baseline elements with the after edge of the flex line.
979     if (style()->flexWrap() == FlexWrapReverse && minMarginAfterBaseline) {
980         for (size_t i = 0; i < children.size(); ++i) {
981             RenderBox* child = children[i];
982             if (flexAlignForChild(child) == AlignBaseline)
983                 adjustAlignmentForChild(child, minMarginAfterBaseline);
984         }
985     }
986 }
987
988 void RenderFlexibleBox::flipForRightToLeftColumn(FlexOrderIterator& iterator)
989 {
990     if (style()->isLeftToRightDirection() || !isColumnFlow())
991         return;
992
993     LayoutUnit crossExtent = crossAxisExtent();
994     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
995         LayoutPoint location = flowAwareLocationForChild(child);
996         location.setY(crossExtent - crossAxisExtentForChild(child) - location.y());
997         setFlowAwareLocationForChild(child, location);
998     }
999 }
1000
1001 void RenderFlexibleBox::flipForWrapReverse(FlexOrderIterator& iterator, const WrapReverseContext& wrapReverseContext)
1002 {
1003     if (!isColumnFlow())
1004         computeLogicalHeight();
1005
1006     size_t currentChild = 0;
1007     size_t lineNumber = 0;
1008     LayoutUnit contentExtent = crossAxisContentExtent();
1009     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
1010         LayoutPoint location = flowAwareLocationForChild(child);
1011         location.setY(location.y() + wrapReverseContext.lineCrossAxisDelta(lineNumber, contentExtent));
1012
1013         LayoutRect oldRect = child->frameRect();
1014         setFlowAwareLocationForChild(child, location);
1015         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
1016             child->repaintDuringLayoutIfMoved(oldRect);
1017
1018         if (++currentChild == wrapReverseContext.childrenPerLine[lineNumber]) {
1019             ++lineNumber;
1020             currentChild = 0;
1021         }
1022     }
1023 }
1024
1025 }