Unreviewed, rolling out r111094.
[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_maxPreferredLogicalWidth += maxPreferredLogicalWidth;
192                 if (isMultiline()) {
193                     // For multiline, the min preferred width is if you put a break between each item.
194                     m_minPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, minPreferredLogicalWidth);
195                 } else
196                     m_minPreferredLogicalWidth += minPreferredLogicalWidth;
197             } else {
198                 m_minPreferredLogicalWidth = std::max(minPreferredLogicalWidth, m_minPreferredLogicalWidth);
199                 if (isMultiline()) {
200                     // For multiline, the max preferred width is if you put a break between each item.
201                     m_maxPreferredLogicalWidth += maxPreferredLogicalWidth;
202                 } else
203                     m_maxPreferredLogicalWidth = std::max(maxPreferredLogicalWidth, m_maxPreferredLogicalWidth);
204             }
205         }
206
207         m_maxPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
208     }
209
210     LayoutUnit scrollbarWidth = 0;
211     if (hasOverflowClip()) {
212         if (isHorizontalWritingMode() && styleToUse->overflowY() == OSCROLL) {
213             layer()->setHasVerticalScrollbar(true);
214             scrollbarWidth = verticalScrollbarWidth();
215         } else if (!isHorizontalWritingMode() && styleToUse->overflowX() == OSCROLL) {
216             layer()->setHasHorizontalScrollbar(true);
217             scrollbarWidth = horizontalScrollbarHeight();
218         }
219     }
220
221     m_maxPreferredLogicalWidth += scrollbarWidth;
222     m_minPreferredLogicalWidth += scrollbarWidth;
223
224     if (styleToUse->logicalMinWidth().isFixed() && styleToUse->logicalMinWidth().value() > 0) {
225         m_maxPreferredLogicalWidth = std::max(m_maxPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMinWidth().value()));
226         m_minPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMinWidth().value()));
227     }
228
229     if (styleToUse->logicalMaxWidth().isFixed()) {
230         m_maxPreferredLogicalWidth = std::min(m_maxPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMaxWidth().value()));
231         m_minPreferredLogicalWidth = std::min(m_minPreferredLogicalWidth, computeContentBoxLogicalWidth(styleToUse->logicalMaxWidth().value()));
232     }
233
234     LayoutUnit borderAndPadding = borderAndPaddingLogicalWidth();
235     m_minPreferredLogicalWidth += borderAndPadding;
236     m_maxPreferredLogicalWidth += borderAndPadding;
237
238     setPreferredLogicalWidthsDirty(false);
239 }
240
241 void RenderFlexibleBox::layoutBlock(bool relayoutChildren, int, BlockLayoutPass)
242 {
243     ASSERT(needsLayout());
244
245     if (!relayoutChildren && simplifiedLayout())
246         return;
247
248     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
249     LayoutStateMaintainer statePusher(view(), this, locationOffset(), hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
250
251     if (inRenderFlowThread()) {
252         // Regions changing widths can force us to relayout our children.
253         if (logicalWidthChangedInRegions())
254             relayoutChildren = true;
255     }
256     computeInitialRegionRangeForBlock();
257
258     IntSize previousSize = size();
259
260     setLogicalHeight(0);
261     // We need to call both of these because we grab both crossAxisExtent and mainAxisExtent in layoutFlexItems.
262     computeLogicalWidth();
263     computeLogicalHeight();
264
265     m_overflow.clear();
266
267     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
268     if (scrollsOverflow()) {
269         if (style()->overflowX() == OSCROLL)
270             layer()->setHasHorizontalScrollbar(true);
271         if (style()->overflowY() == OSCROLL)
272             layer()->setHasVerticalScrollbar(true);
273     }
274
275     layoutFlexItems(relayoutChildren);
276
277     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
278     computeLogicalHeight();
279
280     if (size() != previousSize)
281         relayoutChildren = true;
282
283     layoutPositionedObjects(relayoutChildren || isRoot());
284
285     computeRegionRangeForBlock();
286
287     // FIXME: css3/flexbox/repaint-rtl-column.html seems to repaint more overflow than it needs to.
288     computeOverflow(oldClientAfterEdge);
289     statePusher.pop();
290
291     updateLayerTransform();
292
293     // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if
294     // we overflow or not.
295     updateScrollInfoAfterLayout();
296
297     repainter.repaintAfterLayout();
298
299     setNeedsLayout(false);
300 }
301
302 bool RenderFlexibleBox::hasOrthogonalFlow(RenderBox* child) const
303 {
304     // FIXME: If the child is a flexbox, then we need to check isHorizontalFlow.
305     return isHorizontalFlow() != child->isHorizontalWritingMode();
306 }
307
308 bool RenderFlexibleBox::isColumnFlow() const
309 {
310     return style()->isColumnFlexDirection();
311 }
312
313 bool RenderFlexibleBox::isHorizontalFlow() const
314 {
315     if (isHorizontalWritingMode())
316         return !isColumnFlow();
317     return isColumnFlow();
318 }
319
320 bool RenderFlexibleBox::isLeftToRightFlow() const
321 {
322     if (isColumnFlow())
323         return style()->writingMode() == TopToBottomWritingMode || style()->writingMode() == LeftToRightWritingMode;
324     return style()->isLeftToRightDirection() ^ (style()->flexDirection() == FlowRowReverse);
325 }
326
327 bool RenderFlexibleBox::isMultiline() const
328 {
329     return style()->flexWrap() != FlexWrapNone;
330 }
331
332 Length RenderFlexibleBox::mainAxisLengthForChild(RenderBox* child) const
333 {
334     return isHorizontalFlow() ? child->style()->width() : child->style()->height();
335 }
336
337 Length RenderFlexibleBox::crossAxisLength() const
338 {
339     return isHorizontalFlow() ? style()->height() : style()->width();
340 }
341
342 void RenderFlexibleBox::setCrossAxisExtent(LayoutUnit extent)
343 {
344     if (isHorizontalFlow())
345         setHeight(extent);
346     else
347         setWidth(extent);
348 }
349
350 LayoutUnit RenderFlexibleBox::crossAxisExtentForChild(RenderBox* child)
351 {
352     return isHorizontalFlow() ? child->height() : child->width();
353 }
354
355 LayoutUnit RenderFlexibleBox::mainAxisExtentForChild(RenderBox* child)
356 {
357     return isHorizontalFlow() ? child->width() : child->height();
358 }
359
360 LayoutUnit RenderFlexibleBox::crossAxisExtent() const
361 {
362     return isHorizontalFlow() ? height() : width();
363 }
364
365 LayoutUnit RenderFlexibleBox::mainAxisExtent() const
366 {
367     return isHorizontalFlow() ? width() : height();
368 }
369
370 LayoutUnit RenderFlexibleBox::crossAxisContentExtent() const
371 {
372     return isHorizontalFlow() ? contentHeight() : contentWidth();
373 }
374
375 LayoutUnit RenderFlexibleBox::mainAxisContentExtent() const
376 {
377     return isHorizontalFlow() ? contentWidth() : contentHeight();
378 }
379
380 WritingMode RenderFlexibleBox::transformedWritingMode() const
381 {
382     WritingMode mode = style()->writingMode();
383     if (!isColumnFlow())
384         return mode;
385
386     switch (mode) {
387     case TopToBottomWritingMode:
388     case BottomToTopWritingMode:
389         return style()->isLeftToRightDirection() ? LeftToRightWritingMode : RightToLeftWritingMode;
390     case LeftToRightWritingMode:
391     case RightToLeftWritingMode:
392         return style()->isLeftToRightDirection() ? TopToBottomWritingMode : BottomToTopWritingMode;
393     }
394     ASSERT_NOT_REACHED();
395     return TopToBottomWritingMode;
396 }
397
398 LayoutUnit RenderFlexibleBox::flowAwareBorderStart() const
399 {
400     if (isHorizontalFlow())
401         return isLeftToRightFlow() ? borderLeft() : borderRight();
402     return isLeftToRightFlow() ? borderTop() : borderBottom();
403 }
404
405 LayoutUnit RenderFlexibleBox::flowAwareBorderEnd() const
406 {
407     if (isHorizontalFlow())
408         return isLeftToRightFlow() ? borderRight() : borderLeft();
409     return isLeftToRightFlow() ? borderBottom() : borderTop();
410 }
411
412 LayoutUnit RenderFlexibleBox::flowAwareBorderBefore() const
413 {
414     switch (transformedWritingMode()) {
415     case TopToBottomWritingMode:
416         return borderTop();
417     case BottomToTopWritingMode:
418         return borderBottom();
419     case LeftToRightWritingMode:
420         return borderLeft();
421     case RightToLeftWritingMode:
422         return borderRight();
423     }
424     ASSERT_NOT_REACHED();
425     return borderTop();
426 }
427
428 LayoutUnit RenderFlexibleBox::flowAwareBorderAfter() const
429 {
430     switch (transformedWritingMode()) {
431     case TopToBottomWritingMode:
432         return borderBottom();
433     case BottomToTopWritingMode:
434         return borderTop();
435     case LeftToRightWritingMode:
436         return borderRight();
437     case RightToLeftWritingMode:
438         return borderLeft();
439     }
440     ASSERT_NOT_REACHED();
441     return borderTop();
442 }
443
444 LayoutUnit RenderFlexibleBox::flowAwarePaddingStart() const
445 {
446     if (isHorizontalFlow())
447         return isLeftToRightFlow() ? paddingLeft() : paddingRight();
448     return isLeftToRightFlow() ? paddingTop() : paddingBottom();
449 }
450
451 LayoutUnit RenderFlexibleBox::flowAwarePaddingEnd() const
452 {
453     if (isHorizontalFlow())
454         return isLeftToRightFlow() ? paddingRight() : paddingLeft();
455     return isLeftToRightFlow() ? paddingBottom() : paddingTop();
456 }
457
458 LayoutUnit RenderFlexibleBox::flowAwarePaddingBefore() const
459 {
460     switch (transformedWritingMode()) {
461     case TopToBottomWritingMode:
462         return paddingTop();
463     case BottomToTopWritingMode:
464         return paddingBottom();
465     case LeftToRightWritingMode:
466         return paddingLeft();
467     case RightToLeftWritingMode:
468         return paddingRight();
469     }
470     ASSERT_NOT_REACHED();
471     return paddingTop();
472 }
473
474 LayoutUnit RenderFlexibleBox::flowAwarePaddingAfter() const
475 {
476     switch (transformedWritingMode()) {
477     case TopToBottomWritingMode:
478         return paddingBottom();
479     case BottomToTopWritingMode:
480         return paddingTop();
481     case LeftToRightWritingMode:
482         return paddingRight();
483     case RightToLeftWritingMode:
484         return paddingLeft();
485     }
486     ASSERT_NOT_REACHED();
487     return paddingTop();
488 }
489
490 LayoutUnit RenderFlexibleBox::flowAwareMarginStartForChild(RenderBox* child) const
491 {
492     if (isHorizontalFlow())
493         return isLeftToRightFlow() ? child->marginLeft() : child->marginRight();
494     return isLeftToRightFlow() ? child->marginTop() : child->marginBottom();
495 }
496
497 LayoutUnit RenderFlexibleBox::flowAwareMarginEndForChild(RenderBox* child) const
498 {
499     if (isHorizontalFlow())
500         return isLeftToRightFlow() ? child->marginRight() : child->marginLeft();
501     return isLeftToRightFlow() ? child->marginBottom() : child->marginTop();
502 }
503
504 LayoutUnit RenderFlexibleBox::flowAwareMarginBeforeForChild(RenderBox* child) const
505 {
506     switch (transformedWritingMode()) {
507     case TopToBottomWritingMode:
508         return child->marginTop();
509     case BottomToTopWritingMode:
510         return child->marginBottom();
511     case LeftToRightWritingMode:
512         return child->marginLeft();
513     case RightToLeftWritingMode:
514         return child->marginRight();
515     }
516     ASSERT_NOT_REACHED();
517     return marginTop();
518 }
519
520 LayoutUnit RenderFlexibleBox::flowAwareMarginAfterForChild(RenderBox* child) const
521 {
522     switch (transformedWritingMode()) {
523     case TopToBottomWritingMode:
524         return child->marginBottom();
525     case BottomToTopWritingMode:
526         return child->marginTop();
527     case LeftToRightWritingMode:
528         return child->marginRight();
529     case RightToLeftWritingMode:
530         return child->marginLeft();
531     }
532     ASSERT_NOT_REACHED();
533     return marginBottom();
534 }
535
536 LayoutUnit RenderFlexibleBox::crossAxisMarginExtentForChild(RenderBox* child) const
537 {
538     return isHorizontalFlow() ? child->marginHeight() : child->marginWidth();
539 }
540
541 LayoutUnit RenderFlexibleBox::crossAxisScrollbarExtent() const
542 {
543     return isHorizontalFlow() ? horizontalScrollbarHeight() : verticalScrollbarWidth();
544 }
545
546 LayoutPoint RenderFlexibleBox::flowAwareLocationForChild(RenderBox* child) const
547 {
548     return isHorizontalFlow() ? child->location() : child->location().transposedPoint();
549 }
550
551 void RenderFlexibleBox::setFlowAwareLocationForChild(RenderBox* child, const LayoutPoint& location)
552 {
553     if (isHorizontalFlow())
554         child->setLocation(location);
555     else
556         child->setLocation(location.transposedPoint());
557 }
558
559 LayoutUnit RenderFlexibleBox::mainAxisBorderAndPaddingExtentForChild(RenderBox* child) const
560 {
561     return isHorizontalFlow() ? child->borderAndPaddingWidth() : child->borderAndPaddingHeight();
562 }
563
564 LayoutUnit RenderFlexibleBox::mainAxisScrollbarExtentForChild(RenderBox* child) const
565 {
566     return isHorizontalFlow() ? child->verticalScrollbarWidth() : child->horizontalScrollbarHeight();
567 }
568
569 LayoutUnit RenderFlexibleBox::preferredMainAxisContentExtentForChild(RenderBox* child) const
570 {
571     Length mainAxisLength = mainAxisLengthForChild(child);
572     if (mainAxisLength.isAuto()) {
573         LayoutUnit mainAxisExtent = hasOrthogonalFlow(child) ? child->logicalHeight() : child->maxPreferredLogicalWidth();
574         return mainAxisExtent - mainAxisBorderAndPaddingExtentForChild(child);
575     }
576     return mainAxisLength.calcMinValue(mainAxisContentExtent());
577 }
578
579 LayoutUnit RenderFlexibleBox::computeAvailableFreeSpace(LayoutUnit preferredMainAxisExtent)
580 {
581     if (!isColumnFlow())
582         return mainAxisContentExtent() - preferredMainAxisExtent;
583
584     if (hasOverrideHeight())
585         return overrideHeight();
586
587     LayoutUnit heightResult = computeContentLogicalHeightUsing(style()->logicalHeight());
588     if (heightResult == -1)
589         heightResult = preferredMainAxisExtent;
590     LayoutUnit minHeight = computeContentLogicalHeightUsing(style()->logicalMinHeight()); // Leave as -1 if unset.
591     LayoutUnit maxHeight = style()->logicalMaxHeight().isUndefined() ? heightResult : computeContentLogicalHeightUsing(style()->logicalMaxHeight());
592     if (maxHeight == -1)
593         maxHeight = heightResult;
594     heightResult = std::min(maxHeight, heightResult);
595     heightResult = std::max(minHeight, heightResult);
596
597     return heightResult - preferredMainAxisExtent;
598 }
599
600 void RenderFlexibleBox::layoutFlexItems(bool relayoutChildren)
601 {
602     FlexOrderHashSet flexOrderValues;
603     computeMainAxisPreferredSizes(relayoutChildren, flexOrderValues);
604
605     OrderedFlexItemList orderedChildren;
606     LayoutUnit preferredMainAxisExtent;
607     float totalPositiveFlexibility;
608     float totalNegativeFlexibility;
609     FlexOrderIterator flexIterator(this, flexOrderValues);
610
611     // For wrap-reverse, we need to layout as wrap, then reverse the lines. The next two arrays
612     // are some extra information so it's possible to reverse the lines.
613     WrapReverseContext wrapReverseContext(style()->flexWrap());
614
615     LayoutUnit crossAxisOffset = flowAwareBorderBefore() + flowAwarePaddingBefore();
616     while (computeNextFlexLine(flexIterator, orderedChildren, preferredMainAxisExtent, totalPositiveFlexibility, totalNegativeFlexibility)) {
617         LayoutUnit availableFreeSpace = computeAvailableFreeSpace(preferredMainAxisExtent);
618         InflexibleFlexItemSize inflexibleItems;
619         WTF::Vector<LayoutUnit> childSizes;
620         while (!runFreeSpaceAllocationAlgorithm(orderedChildren, availableFreeSpace, totalPositiveFlexibility, totalNegativeFlexibility, inflexibleItems, childSizes)) {
621             ASSERT(totalPositiveFlexibility >= 0 && totalNegativeFlexibility >= 0);
622             ASSERT(inflexibleItems.size() > 0);
623         }
624
625         wrapReverseContext.addNumberOfChildrenOnLine(orderedChildren.size());
626         wrapReverseContext.addCrossAxisOffset(crossAxisOffset);
627         layoutAndPlaceChildren(crossAxisOffset, orderedChildren, childSizes, availableFreeSpace);
628     }
629
630     if (wrapReverseContext.isWrapReverse) {
631         wrapReverseContext.addCrossAxisOffset(crossAxisOffset);
632         flipForWrapReverse(flexIterator, wrapReverseContext);
633     }
634
635     // direction:rtl + flex-direction:column means the cross-axis direction is flipped.
636     flipForRightToLeftColumn(flexIterator);
637 }
638
639 float RenderFlexibleBox::positiveFlexForChild(RenderBox* child) const
640 {
641     return isHorizontalFlow() ? child->style()->flexboxWidthPositiveFlex() : child->style()->flexboxHeightPositiveFlex();
642 }
643
644 float RenderFlexibleBox::negativeFlexForChild(RenderBox* child) const
645 {
646     return isHorizontalFlow() ? child->style()->flexboxWidthNegativeFlex() : child->style()->flexboxHeightNegativeFlex();
647 }
648
649 LayoutUnit RenderFlexibleBox::availableAlignmentSpaceForChild(LayoutUnit lineCrossAxisExtent, RenderBox* child)
650 {
651     LayoutUnit childCrossExtent = crossAxisMarginExtentForChild(child) + crossAxisExtentForChild(child);
652     return lineCrossAxisExtent - childCrossExtent;
653 }
654
655 LayoutUnit RenderFlexibleBox::marginBoxAscentForChild(RenderBox* child)
656 {
657     LayoutUnit ascent = child->firstLineBoxBaseline();
658     if (ascent == -1)
659         ascent = crossAxisExtentForChild(child) + flowAwareMarginAfterForChild(child);
660     return ascent + flowAwareMarginBeforeForChild(child);
661 }
662
663 void RenderFlexibleBox::computeMainAxisPreferredSizes(bool relayoutChildren, FlexOrderHashSet& flexOrderValues)
664 {
665     LayoutUnit flexboxAvailableContentExtent = mainAxisContentExtent();
666     for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
667         flexOrderValues.add(child->style()->flexOrder());
668
669         if (child->isPositioned())
670             continue;
671
672         child->clearOverrideSize();
673         if (mainAxisLengthForChild(child).isAuto()) {
674             if (!relayoutChildren)
675                 child->setChildNeedsLayout(true);
676             child->layoutIfNeeded();
677         }
678
679         // We set the margins because we want to make sure 'auto' has a margin
680         // of 0 and because if we're not auto sizing, we don't do a layout that
681         // computes the start/end margins.
682         if (isHorizontalFlow()) {
683             child->setMarginLeft(child->style()->marginLeft().calcMinValue(flexboxAvailableContentExtent));
684             child->setMarginRight(child->style()->marginRight().calcMinValue(flexboxAvailableContentExtent));
685         } else {
686             child->setMarginTop(child->style()->marginTop().calcMinValue(flexboxAvailableContentExtent));
687             child->setMarginBottom(child->style()->marginBottom().calcMinValue(flexboxAvailableContentExtent));
688         }
689     }
690 }
691
692 LayoutUnit RenderFlexibleBox::lineBreakLength()
693 {
694     if (!isColumnFlow())
695         return mainAxisContentExtent();
696
697     LayoutUnit height = computeContentLogicalHeightUsing(style()->logicalHeight());
698     if (height == -1)
699         height = std::numeric_limits<LayoutUnit>::max();
700     LayoutUnit maxHeight = computeContentLogicalHeightUsing(style()->logicalMaxHeight());
701     if (maxHeight != -1)
702         height = std::min(height, maxHeight);
703     return height;
704 }
705
706 bool RenderFlexibleBox::computeNextFlexLine(FlexOrderIterator& iterator, OrderedFlexItemList& orderedChildren, LayoutUnit& preferredMainAxisExtent, float& totalPositiveFlexibility, float& totalNegativeFlexibility)
707 {
708     orderedChildren.clear();
709     preferredMainAxisExtent = 0;
710     totalPositiveFlexibility = totalNegativeFlexibility = 0;
711
712     if (!iterator.currentChild())
713         return false;
714
715     LayoutUnit lineBreak = lineBreakLength();
716
717     for (RenderBox* child = iterator.currentChild(); child; child = iterator.next()) {
718         if (child->isPositioned()) {
719             orderedChildren.append(child);
720             continue;
721         }
722
723         LayoutUnit childMainAxisExtent = mainAxisBorderAndPaddingExtentForChild(child) + preferredMainAxisContentExtentForChild(child);
724         if (isHorizontalFlow())
725             childMainAxisExtent += child->marginWidth();
726         else
727             childMainAxisExtent += child->marginHeight();
728
729         if (isMultiline() && preferredMainAxisExtent + childMainAxisExtent > lineBreak && orderedChildren.size() > 0)
730             break;
731         orderedChildren.append(child);
732         preferredMainAxisExtent += childMainAxisExtent;
733         totalPositiveFlexibility += positiveFlexForChild(child);
734         totalNegativeFlexibility += negativeFlexForChild(child);
735     }
736     return true;
737 }
738
739 // Returns true if we successfully ran the algorithm and sized the flex items.
740 bool RenderFlexibleBox::runFreeSpaceAllocationAlgorithm(const OrderedFlexItemList& children, LayoutUnit& availableFreeSpace, float& totalPositiveFlexibility, float& totalNegativeFlexibility, InflexibleFlexItemSize& inflexibleItems, WTF::Vector<LayoutUnit>& childSizes)
741 {
742     childSizes.clear();
743
744     LayoutUnit flexboxAvailableContentExtent = mainAxisContentExtent();
745     for (size_t i = 0; i < children.size(); ++i) {
746         RenderBox* child = children[i];
747         if (child->isPositioned()) {
748             childSizes.append(0);
749             continue;
750         }
751
752         LayoutUnit childPreferredSize;
753         if (inflexibleItems.contains(child))
754             childPreferredSize = inflexibleItems.get(child);
755         else {
756             childPreferredSize = preferredMainAxisContentExtentForChild(child);
757             if (availableFreeSpace > 0 && totalPositiveFlexibility > 0) {
758                 childPreferredSize += lroundf(availableFreeSpace * positiveFlexForChild(child) / totalPositiveFlexibility);
759
760                 Length childLogicalMaxWidth = isHorizontalFlow() ? child->style()->maxWidth() : child->style()->maxHeight();
761                 if (childLogicalMaxWidth.isSpecified() && childPreferredSize > childLogicalMaxWidth.calcValue(flexboxAvailableContentExtent)) {
762                     childPreferredSize = childLogicalMaxWidth.calcValue(flexboxAvailableContentExtent);
763                     availableFreeSpace -= childPreferredSize - preferredMainAxisContentExtentForChild(child);
764                     totalPositiveFlexibility -= positiveFlexForChild(child);
765
766                     inflexibleItems.set(child, childPreferredSize);
767                     return false;
768                 }
769             } else if (availableFreeSpace < 0 && totalNegativeFlexibility > 0) {
770                 childPreferredSize += lroundf(availableFreeSpace * negativeFlexForChild(child) / totalNegativeFlexibility);
771
772                 Length childLogicalMinWidth = isHorizontalFlow() ? child->style()->minWidth() : child->style()->minHeight();
773                 if (childLogicalMinWidth.isSpecified() && childPreferredSize < childLogicalMinWidth.calcValue(flexboxAvailableContentExtent)) {
774                     childPreferredSize = childLogicalMinWidth.calcValue(flexboxAvailableContentExtent);
775                     availableFreeSpace += preferredMainAxisContentExtentForChild(child) - childPreferredSize;
776                     totalNegativeFlexibility -= negativeFlexForChild(child);
777
778                     inflexibleItems.set(child, childPreferredSize);
779                     return false;
780                 }
781             }
782         }
783         childSizes.append(childPreferredSize);
784     }
785     return true;
786 }
787
788 static LayoutUnit initialPackingOffset(LayoutUnit availableFreeSpace, EFlexPack flexPack, size_t numberOfChildren)
789 {
790     if (availableFreeSpace > 0) {
791         if (flexPack == PackEnd)
792             return availableFreeSpace;
793         if (flexPack == PackCenter)
794             return availableFreeSpace / 2;
795         if (flexPack == PackDistribute && numberOfChildren)
796             return availableFreeSpace / (2 * numberOfChildren);
797     } else if (availableFreeSpace < 0) {
798         if (flexPack == PackCenter || flexPack == PackDistribute)
799             return availableFreeSpace / 2;
800     }
801     return 0;
802 }
803
804 static LayoutUnit packingSpaceBetweenChildren(LayoutUnit availableFreeSpace, EFlexPack flexPack, size_t numberOfChildren)
805 {
806     if (availableFreeSpace > 0 && numberOfChildren > 1) {
807         if (flexPack == PackJustify)
808             return availableFreeSpace / (numberOfChildren - 1);
809         if (flexPack == PackDistribute)
810             return availableFreeSpace / numberOfChildren;
811     }
812     return 0;
813 }
814
815 void RenderFlexibleBox::setLogicalOverrideSize(RenderBox* child, LayoutUnit childPreferredSize)
816 {
817     // FIXME: Rename setOverrideWidth/setOverrideHeight to setOverrideLogicalWidth/setOverrideLogicalHeight.
818     if (hasOrthogonalFlow(child))
819         child->setOverrideHeight(childPreferredSize);
820     else
821         child->setOverrideWidth(childPreferredSize);
822 }
823
824 void RenderFlexibleBox::prepareChildForPositionedLayout(RenderBox* child, LayoutUnit mainAxisOffset, LayoutUnit crossAxisOffset)
825 {
826     ASSERT(child->isPositioned());
827     child->containingBlock()->insertPositionedObject(child);
828     RenderLayer* childLayer = child->layer();
829     LayoutUnit inlinePosition = isColumnFlow() ? crossAxisOffset : mainAxisOffset;
830     if (style()->flexDirection() == FlowRowReverse)
831         inlinePosition = mainAxisExtent() - mainAxisOffset;
832     childLayer->setStaticInlinePosition(inlinePosition); // FIXME: Not right for regions.
833
834     LayoutUnit staticBlockPosition = isColumnFlow() ? mainAxisOffset : crossAxisOffset;
835     if (childLayer->staticBlockPosition() != staticBlockPosition) {
836         childLayer->setStaticBlockPosition(staticBlockPosition);
837         if (child->style()->hasStaticBlockPosition(style()->isHorizontalWritingMode()))
838             child->setChildNeedsLayout(true, false);
839     }
840 }
841
842 static EFlexAlign flexAlignForChild(RenderBox* child)
843 {
844     EFlexAlign align = child->style()->flexItemAlign();
845     if (align == AlignAuto)
846         align = child->parent()->style()->flexAlign();
847
848     if (child->parent()->style()->flexWrap() == FlexWrapReverse) {
849         if (align == AlignStart)
850             align = AlignEnd;
851         else if (align == AlignEnd)
852             align = AlignStart;
853     }
854
855     return align;
856 }
857
858 void RenderFlexibleBox::layoutAndPlaceChildren(LayoutUnit& crossAxisOffset, const OrderedFlexItemList& children, const WTF::Vector<LayoutUnit>& childSizes, LayoutUnit availableFreeSpace)
859 {
860     LayoutUnit mainAxisOffset = flowAwareBorderStart() + flowAwarePaddingStart();
861     mainAxisOffset += initialPackingOffset(availableFreeSpace, style()->flexPack(), childSizes.size());
862     if (style()->flexDirection() == FlowRowReverse)
863         mainAxisOffset += isHorizontalFlow() ? verticalScrollbarWidth() : horizontalScrollbarHeight();
864
865     LayoutUnit totalMainExtent = mainAxisExtent();
866     LayoutUnit maxAscent = 0, maxDescent = 0; // Used when flex-align: baseline.
867     LayoutUnit maxChildCrossAxisExtent = 0;
868     bool shouldFlipMainAxis = !isColumnFlow() && !isLeftToRightFlow();
869     for (size_t i = 0; i < children.size(); ++i) {
870         RenderBox* child = children[i];
871         if (child->isPositioned()) {
872             prepareChildForPositionedLayout(child, mainAxisOffset, crossAxisOffset);
873             mainAxisOffset += packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
874             continue;
875         }
876         LayoutUnit childPreferredSize = childSizes[i] + mainAxisBorderAndPaddingExtentForChild(child);
877         setLogicalOverrideSize(child, childPreferredSize);
878         child->setChildNeedsLayout(true);
879         child->layoutIfNeeded();
880
881         LayoutUnit childCrossAxisMarginBoxExtent;
882         if (flexAlignForChild(child) == AlignBaseline) {
883             LayoutUnit ascent = marginBoxAscentForChild(child);
884             LayoutUnit descent = (crossAxisMarginExtentForChild(child) + crossAxisExtentForChild(child)) - ascent;
885
886             maxAscent = std::max(maxAscent, ascent);
887             maxDescent = std::max(maxDescent, descent);
888
889             childCrossAxisMarginBoxExtent = maxAscent + maxDescent;
890         } else
891             childCrossAxisMarginBoxExtent = crossAxisExtentForChild(child) + crossAxisMarginExtentForChild(child);
892         if (!isColumnFlow() && style()->logicalHeight().isAuto())
893             setLogicalHeight(std::max(logicalHeight(), crossAxisOffset + flowAwareBorderAfter() + flowAwarePaddingAfter() + childCrossAxisMarginBoxExtent + crossAxisScrollbarExtent()));
894         maxChildCrossAxisExtent = std::max(maxChildCrossAxisExtent, childCrossAxisMarginBoxExtent);
895
896         mainAxisOffset += flowAwareMarginStartForChild(child);
897
898         LayoutUnit childMainExtent = mainAxisExtentForChild(child);
899         IntPoint childLocation(shouldFlipMainAxis ? totalMainExtent - mainAxisOffset - childMainExtent : mainAxisOffset,
900             crossAxisOffset + flowAwareMarginBeforeForChild(child));
901
902         // FIXME: Supporting layout deltas.
903         setFlowAwareLocationForChild(child, childLocation);
904         mainAxisOffset += childMainExtent + flowAwareMarginEndForChild(child);
905
906         mainAxisOffset += packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
907     }
908
909     if (isColumnFlow())
910         setLogicalHeight(mainAxisOffset + flowAwareBorderEnd() + flowAwarePaddingEnd() + scrollbarLogicalHeight());
911
912     if (style()->flexDirection() == FlowColumnReverse) {
913         // We have to do an extra pass for column-reverse to reposition the flex items since the start depends
914         // on the height of the flexbox, which we only know after we've positioned all the flex items.
915         computeLogicalHeight();
916         layoutColumnReverse(children, childSizes, crossAxisOffset, availableFreeSpace);
917     }
918
919     LayoutUnit lineCrossAxisExtent = isMultiline() ? maxChildCrossAxisExtent : crossAxisContentExtent();
920     alignChildren(children, lineCrossAxisExtent, maxAscent);
921
922     crossAxisOffset += lineCrossAxisExtent;
923 }
924
925 void RenderFlexibleBox::layoutColumnReverse(const OrderedFlexItemList& children, const WTF::Vector<LayoutUnit>& childSizes, LayoutUnit crossAxisOffset, LayoutUnit availableFreeSpace)
926 {
927     // This is similar to the logic in layoutAndPlaceChildren, except we place the children
928     // starting from the end of the flexbox. We also don't need to layout anything since we're
929     // just moving the children to a new position.
930     LayoutUnit mainAxisOffset = logicalHeight() - flowAwareBorderEnd() - flowAwarePaddingEnd();
931     mainAxisOffset -= initialPackingOffset(availableFreeSpace, style()->flexPack(), childSizes.size());
932     mainAxisOffset -= isHorizontalFlow() ? verticalScrollbarWidth() : horizontalScrollbarHeight();
933
934     for (size_t i = 0; i < children.size(); ++i) {
935         RenderBox* child = children[i];
936         if (child->isPositioned()) {
937             child->layer()->setStaticBlockPosition(mainAxisOffset);
938             mainAxisOffset -= packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
939             continue;
940         }
941         mainAxisOffset -= mainAxisExtentForChild(child) + flowAwareMarginEndForChild(child);
942
943         LayoutRect oldRect = child->frameRect();
944         setFlowAwareLocationForChild(child, IntPoint(mainAxisOffset, crossAxisOffset + flowAwareMarginBeforeForChild(child)));
945         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
946             child->repaintDuringLayoutIfMoved(oldRect);
947
948         mainAxisOffset -= flowAwareMarginStartForChild(child);
949         mainAxisOffset -= packingSpaceBetweenChildren(availableFreeSpace, style()->flexPack(), childSizes.size());
950     }
951 }
952
953 void RenderFlexibleBox::adjustAlignmentForChild(RenderBox* child, LayoutUnit delta)
954 {
955     LayoutRect oldRect = child->frameRect();
956
957     setFlowAwareLocationForChild(child, flowAwareLocationForChild(child) + LayoutSize(0, delta));
958
959     // If the child moved, we have to repaint it as well as any floating/positioned
960     // descendants. An exception is if we need a layout. In this case, we know we're going to
961     // repaint ourselves (and the child) anyway.
962     if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
963         child->repaintDuringLayoutIfMoved(oldRect);
964 }
965
966 void RenderFlexibleBox::alignChildren(const OrderedFlexItemList& children, LayoutUnit lineCrossAxisExtent, LayoutUnit maxAscent)
967 {
968     LayoutUnit minMarginAfterBaseline = std::numeric_limits<LayoutUnit>::max();
969
970     for (size_t i = 0; i < children.size(); ++i) {
971         RenderBox* child = children[i];
972         switch (flexAlignForChild(child)) {
973         case AlignAuto:
974             ASSERT_NOT_REACHED();
975             break;
976         case AlignStretch: {
977             if (!isColumnFlow() && child->style()->logicalHeight().isAuto()) {
978                 LayoutUnit logicalHeightBefore = child->logicalHeight();
979                 LayoutUnit stretchedLogicalHeight = child->logicalHeight() + availableAlignmentSpaceForChild(lineCrossAxisExtent, child);
980                 child->setLogicalHeight(stretchedLogicalHeight);
981                 child->computeLogicalHeight();
982
983                 if (child->logicalHeight() != logicalHeightBefore) {
984                     child->setOverrideHeight(child->logicalHeight());
985                     child->setLogicalHeight(0);
986                     child->setChildNeedsLayout(true);
987                     child->layoutIfNeeded();
988                 }
989             } else if (isColumnFlow() && child->style()->logicalWidth().isAuto() && isMultiline()) {
990                 // FIXME: Handle min-width and max-width.
991                 LayoutUnit childWidth = lineCrossAxisExtent - crossAxisMarginExtentForChild(child);
992                 child->setOverrideWidth(std::max(0, childWidth));
993                 child->setChildNeedsLayout(true);
994                 child->layoutIfNeeded();
995             }
996             // Since wrap-reverse flips cross start and cross end, strech children should be aligned with the cross end.
997             if (style()->flexWrap() == FlexWrapReverse)
998                 adjustAlignmentForChild(child, availableAlignmentSpaceForChild(lineCrossAxisExtent, child));
999             break;
1000         }
1001         case AlignStart:
1002             break;
1003         case AlignEnd:
1004             adjustAlignmentForChild(child, availableAlignmentSpaceForChild(lineCrossAxisExtent, child));
1005             break;
1006         case AlignCenter:
1007             adjustAlignmentForChild(child, availableAlignmentSpaceForChild(lineCrossAxisExtent, child) / 2);
1008             break;
1009         case AlignBaseline: {
1010             LayoutUnit ascent = marginBoxAscentForChild(child);
1011             LayoutUnit startOffset = maxAscent - ascent;
1012             adjustAlignmentForChild(child, startOffset);
1013
1014             if (style()->flexWrap() == FlexWrapReverse)
1015                 minMarginAfterBaseline = std::min(minMarginAfterBaseline, availableAlignmentSpaceForChild(lineCrossAxisExtent, child) - startOffset);
1016             break;
1017         }
1018         }
1019     }
1020
1021     // wrap-reverse flips the cross axis start and end. For baseline alignment, this means we
1022     // need to align the after edge of baseline elements with the after edge of the flex line.
1023     if (style()->flexWrap() == FlexWrapReverse && minMarginAfterBaseline) {
1024         for (size_t i = 0; i < children.size(); ++i) {
1025             RenderBox* child = children[i];
1026             if (flexAlignForChild(child) == AlignBaseline)
1027                 adjustAlignmentForChild(child, minMarginAfterBaseline);
1028         }
1029     }
1030 }
1031
1032 void RenderFlexibleBox::flipForRightToLeftColumn(FlexOrderIterator& iterator)
1033 {
1034     if (style()->isLeftToRightDirection() || !isColumnFlow())
1035         return;
1036
1037     LayoutUnit crossExtent = crossAxisExtent();
1038     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
1039         LayoutPoint location = flowAwareLocationForChild(child);
1040         location.setY(crossExtent - crossAxisExtentForChild(child) - location.y());
1041         setFlowAwareLocationForChild(child, location);
1042     }
1043 }
1044
1045 void RenderFlexibleBox::flipForWrapReverse(FlexOrderIterator& iterator, const WrapReverseContext& wrapReverseContext)
1046 {
1047     if (!isColumnFlow())
1048         computeLogicalHeight();
1049
1050     size_t currentChild = 0;
1051     size_t lineNumber = 0;
1052     LayoutUnit contentExtent = crossAxisContentExtent();
1053     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
1054         LayoutPoint location = flowAwareLocationForChild(child);
1055         location.setY(location.y() + wrapReverseContext.lineCrossAxisDelta(lineNumber, contentExtent));
1056
1057         LayoutRect oldRect = child->frameRect();
1058         setFlowAwareLocationForChild(child, location);
1059         if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
1060             child->repaintDuringLayoutIfMoved(oldRect);
1061
1062         if (++currentChild == wrapReverseContext.childrenPerLine[lineNumber]) {
1063             ++lineNumber;
1064             currentChild = 0;
1065         }
1066     }
1067 }
1068
1069 }