845d83133250aaf7cd24f7b694e290af75fde54d
[WebKit-https.git] / Source / WebCore / rendering / RenderDeprecatedFlexibleBox.cpp
1 /*
2  * This file is part of the render object implementation for KHTML.
3  *
4  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
5  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
6  * Copyright (C) 2003 Apple Computer, Inc.
7  *
8  * This library is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Library General Public
10  * License as published by the Free Software Foundation; either
11  * version 2 of the License, or (at your option) any later version.
12  *
13  * This library is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Library General Public License for more details.
17  *
18  * You should have received a copy of the GNU Library General Public License
19  * along with this library; see the file COPYING.LIB.  If not, write to
20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
21  * Boston, MA 02110-1301, USA.
22  *
23  */
24
25 #include "config.h"
26 #include "RenderDeprecatedFlexibleBox.h"
27
28 #include "Font.h"
29 #include "LayoutRepainter.h"
30 #include "RenderLayer.h"
31 #include "RenderView.h"
32 #include <wtf/StdLibExtras.h>
33 #include <wtf/unicode/CharacterNames.h>
34
35 using namespace std;
36
37 namespace WebCore {
38
39 class FlexBoxIterator {
40 public:
41     FlexBoxIterator(RenderDeprecatedFlexibleBox* parent)
42         : m_box(parent)
43         , m_largestOrdinal(1)
44     {
45         if (m_box->style()->boxOrient() == HORIZONTAL && !m_box->style()->isLeftToRightDirection())
46             m_forward = m_box->style()->boxDirection() != BNORMAL;
47         else
48             m_forward = m_box->style()->boxDirection() == BNORMAL;
49         if (!m_forward) {
50             // No choice, since we're going backwards, we have to find out the highest ordinal up front.
51             RenderBox* child = m_box->firstChildBox();
52             while (child) {
53                 if (child->style()->boxOrdinalGroup() > m_largestOrdinal)
54                     m_largestOrdinal = child->style()->boxOrdinalGroup();
55                 child = child->nextSiblingBox();
56             }
57         }
58
59         reset();
60     }
61
62     void reset()
63     {
64         m_currentChild = 0;
65         m_ordinalIteration = -1;
66     }
67
68     RenderBox* first()
69     {
70         reset();
71         return next();
72     }
73
74     RenderBox* next()
75     {
76         do {
77             if (!m_currentChild) {
78                 ++m_ordinalIteration;
79
80                 if (!m_ordinalIteration)
81                     m_currentOrdinal = m_forward ? 1 : m_largestOrdinal;
82                 else {
83                     if (m_ordinalIteration >= m_ordinalValues.size() + 1)
84                         return 0;
85
86                     // Only copy+sort the values once per layout even if the iterator is reset.
87                     if (static_cast<size_t>(m_ordinalValues.size()) != m_sortedOrdinalValues.size()) {
88                         copyToVector(m_ordinalValues, m_sortedOrdinalValues);
89                         sort(m_sortedOrdinalValues.begin(), m_sortedOrdinalValues.end());
90                     }
91                     m_currentOrdinal = m_forward ? m_sortedOrdinalValues[m_ordinalIteration - 1] : m_sortedOrdinalValues[m_sortedOrdinalValues.size() - m_ordinalIteration];
92                 }
93
94                 m_currentChild = m_forward ? m_box->firstChildBox() : m_box->lastChildBox();
95             } else
96                 m_currentChild = m_forward ? m_currentChild->nextSiblingBox() : m_currentChild->previousSiblingBox();
97
98             if (m_currentChild && notFirstOrdinalValue())
99                 m_ordinalValues.add(m_currentChild->style()->boxOrdinalGroup());
100         } while (!m_currentChild || (!m_currentChild->isAnonymous()
101                  && m_currentChild->style()->boxOrdinalGroup() != m_currentOrdinal));
102         return m_currentChild;
103     }
104
105 private:
106     bool notFirstOrdinalValue()
107     {
108         unsigned int firstOrdinalValue = m_forward ? 1 : m_largestOrdinal;
109         return m_currentOrdinal == firstOrdinalValue && m_currentChild->style()->boxOrdinalGroup() != firstOrdinalValue;
110     }
111
112     RenderDeprecatedFlexibleBox* m_box;
113     RenderBox* m_currentChild;
114     bool m_forward;
115     unsigned int m_currentOrdinal;
116     unsigned int m_largestOrdinal;
117     HashSet<unsigned int> m_ordinalValues;
118     Vector<unsigned int> m_sortedOrdinalValues;
119     int m_ordinalIteration;
120 };
121
122 RenderDeprecatedFlexibleBox::RenderDeprecatedFlexibleBox(Element* element)
123     : RenderBlock(element)
124 {
125     setChildrenInline(false); // All of our children must be block-level
126     m_stretchingChildren = false;
127 }
128
129 RenderDeprecatedFlexibleBox::~RenderDeprecatedFlexibleBox()
130 {
131 }
132
133 RenderDeprecatedFlexibleBox* RenderDeprecatedFlexibleBox::createAnonymous(Document* document)
134 {
135     RenderDeprecatedFlexibleBox* renderer = new (document->renderArena()) RenderDeprecatedFlexibleBox(0);
136     renderer->setDocumentForAnonymous(document);
137     return renderer;
138 }
139
140 static LayoutUnit marginWidthForChild(RenderBox* child)
141 {
142     // A margin basically has three types: fixed, percentage, and auto (variable).
143     // Auto and percentage margins simply become 0 when computing min/max width.
144     // Fixed margins can be added in as is.
145     Length marginLeft = child->style()->marginLeft();
146     Length marginRight = child->style()->marginRight();
147     LayoutUnit margin = 0;
148     if (marginLeft.isFixed())
149         margin += marginLeft.value();
150     if (marginRight.isFixed())
151         margin += marginRight.value();
152     return margin;
153 }
154
155 static bool childDoesNotAffectWidthOrFlexing(RenderObject* child)
156 {
157     // Positioned children and collapsed children don't affect the min/max width.
158     return child->isOutOfFlowPositioned() || child->style()->visibility() == COLLAPSE;
159 }
160
161 static LayoutUnit contentWidthForChild(RenderBox* child)
162 {
163     if (child->hasOverrideWidth())
164         return child->overrideLogicalContentWidth();
165     return child->logicalWidth() - child->borderAndPaddingLogicalWidth();
166 }
167
168 static LayoutUnit contentHeightForChild(RenderBox* child)
169 {
170     if (child->hasOverrideHeight())
171         return child->overrideLogicalContentHeight();
172     return child->logicalHeight() - child->borderAndPaddingLogicalHeight();
173 }
174
175 void RenderDeprecatedFlexibleBox::styleWillChange(StyleDifference diff, const RenderStyle* newStyle)
176 {
177     RenderStyle* oldStyle = style();
178     if (oldStyle && !oldStyle->lineClamp().isNone() && newStyle->lineClamp().isNone())
179         clearLineClamp();
180
181     RenderBlock::styleWillChange(diff, newStyle);
182 }
183
184 void RenderDeprecatedFlexibleBox::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
185 {
186     if (hasMultipleLines() || isVertical()) {
187         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
188             if (childDoesNotAffectWidthOrFlexing(child))
189                 continue;
190
191             LayoutUnit margin = marginWidthForChild(child);
192             LayoutUnit width = child->minPreferredLogicalWidth() + margin;
193             minLogicalWidth = max(width, minLogicalWidth);
194
195             width = child->maxPreferredLogicalWidth() + margin;
196             maxLogicalWidth = max(width, maxLogicalWidth);
197         }
198     } else {
199         for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
200             if (childDoesNotAffectWidthOrFlexing(child))
201                 continue;
202
203             LayoutUnit margin = marginWidthForChild(child);
204             minLogicalWidth += child->minPreferredLogicalWidth() + margin;
205             maxLogicalWidth += child->maxPreferredLogicalWidth() + margin;
206         }
207     }
208
209     maxLogicalWidth = max(minLogicalWidth, maxLogicalWidth);
210
211     LayoutUnit scrollbarWidth = instrinsicScrollbarLogicalWidth();
212     maxLogicalWidth += scrollbarWidth;
213     minLogicalWidth += scrollbarWidth;
214 }
215
216 void RenderDeprecatedFlexibleBox::computePreferredLogicalWidths()
217 {
218     ASSERT(preferredLogicalWidthsDirty());
219
220     m_minPreferredLogicalWidth = m_maxPreferredLogicalWidth = 0;
221     if (style()->width().isFixed() && style()->width().value() > 0)
222         m_minPreferredLogicalWidth = m_maxPreferredLogicalWidth = adjustContentBoxLogicalWidthForBoxSizing(style()->width().value());
223     else
224         computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
225
226     if (style()->minWidth().isFixed() && style()->minWidth().value() > 0) {
227         m_maxPreferredLogicalWidth = max(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(style()->minWidth().value()));
228         m_minPreferredLogicalWidth = max(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(style()->minWidth().value()));
229     }
230
231     if (style()->maxWidth().isFixed()) {
232         m_maxPreferredLogicalWidth = min(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(style()->maxWidth().value()));
233         m_minPreferredLogicalWidth = min(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(style()->maxWidth().value()));
234     }
235
236     LayoutUnit borderAndPadding = borderAndPaddingLogicalWidth();
237     m_minPreferredLogicalWidth += borderAndPadding;
238     m_maxPreferredLogicalWidth += borderAndPadding;
239
240     setPreferredLogicalWidthsDirty(false);
241 }
242
243 void RenderDeprecatedFlexibleBox::layoutBlock(bool relayoutChildren, LayoutUnit)
244 {
245     ASSERT(needsLayout());
246
247     if (!relayoutChildren && simplifiedLayout())
248         return;
249
250     LayoutRepainter repainter(*this, checkForRepaintDuringLayout());
251     LayoutStateMaintainer statePusher(view(), this, locationOffset(), hasTransform() || hasReflection() || style()->isFlippedBlocksWritingMode());
252
253     // Regions changing widths can force us to relayout our children.
254     RenderFlowThread* flowThread = flowThreadContainingBlock();
255     if (logicalWidthChangedInRegions(flowThread))
256         relayoutChildren = true;
257     if (updateRegionsAndExclusionsLogicalSize(flowThread))
258         relayoutChildren = true;
259
260     LayoutSize previousSize = size();
261
262     updateLogicalWidth();
263     updateLogicalHeight();
264
265     if (previousSize != size()
266         || (parent()->isDeprecatedFlexibleBox() && parent()->style()->boxOrient() == HORIZONTAL
267         && parent()->style()->boxAlign() == BSTRETCH))
268         relayoutChildren = true;
269
270     setHeight(0);
271
272     m_stretchingChildren = false;
273
274     initMaxMarginValues();
275
276     if (isHorizontal())
277         layoutHorizontalBox(relayoutChildren);
278     else
279         layoutVerticalBox(relayoutChildren);
280
281     LayoutUnit oldClientAfterEdge = clientLogicalBottom();
282     updateLogicalHeight();
283
284     if (previousSize.height() != height())
285         relayoutChildren = true;
286
287     layoutPositionedObjects(relayoutChildren || isRoot());
288
289     computeRegionRangeForBlock(flowThread);
290
291     if (!isFloatingOrOutOfFlowPositioned() && height() == 0) {
292         // We are a block with no border and padding and a computed height
293         // of 0.  The CSS spec states that zero-height blocks collapse their margins
294         // together.
295         // When blocks are self-collapsing, we just use the top margin values and set the
296         // bottom margin max values to 0.  This way we don't factor in the values
297         // twice when we collapse with our previous vertically adjacent and
298         // following vertically adjacent blocks.
299         LayoutUnit pos = maxPositiveMarginBefore();
300         LayoutUnit neg = maxNegativeMarginBefore();
301         if (maxPositiveMarginAfter() > pos)
302             pos = maxPositiveMarginAfter();
303         if (maxNegativeMarginAfter() > neg)
304             neg = maxNegativeMarginAfter();
305         setMaxMarginBeforeValues(pos, neg);
306         setMaxMarginAfterValues(0, 0);
307     }
308
309     computeOverflow(oldClientAfterEdge);
310
311     statePusher.pop();
312
313     updateLayerTransform();
314
315     if (view()->layoutState()->pageLogicalHeight())
316         setPageLogicalOffset(view()->layoutState()->pageLogicalOffset(this, logicalTop()));
317
318     // Update our scrollbars if we're overflow:auto/scroll/hidden now that we know if
319     // we overflow or not.
320     if (hasOverflowClip())
321         layer()->updateScrollInfoAfterLayout();
322
323     // Repaint with our new bounds if they are different from our old bounds.
324     repainter.repaintAfterLayout();
325
326     setNeedsLayout(false);
327 }
328
329 // The first walk over our kids is to find out if we have any flexible children.
330 static void gatherFlexChildrenInfo(FlexBoxIterator& iterator, bool relayoutChildren, unsigned int& highestFlexGroup, unsigned int& lowestFlexGroup, bool& haveFlex)
331 {
332     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
333         // Check to see if this child flexes.
334         if (!childDoesNotAffectWidthOrFlexing(child) && child->style()->boxFlex() > 0.0f) {
335             // We always have to lay out flexible objects again, since the flex distribution
336             // may have changed, and we need to reallocate space.
337             child->clearOverrideSize();
338             if (!relayoutChildren)
339                 child->setChildNeedsLayout(true, MarkOnlyThis);
340             haveFlex = true;
341             unsigned int flexGroup = child->style()->boxFlexGroup();
342             if (lowestFlexGroup == 0)
343                 lowestFlexGroup = flexGroup;
344             if (flexGroup < lowestFlexGroup)
345                 lowestFlexGroup = flexGroup;
346             if (flexGroup > highestFlexGroup)
347                 highestFlexGroup = flexGroup;
348         }
349     }
350 }
351
352 void RenderDeprecatedFlexibleBox::layoutHorizontalBox(bool relayoutChildren)
353 {
354     LayoutUnit toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
355     LayoutUnit yPos = borderTop() + paddingTop();
356     LayoutUnit xPos = borderLeft() + paddingLeft();
357     bool heightSpecified = false;
358     LayoutUnit oldHeight = 0;
359
360     LayoutUnit remainingSpace = 0;
361
362
363     FlexBoxIterator iterator(this);
364     unsigned int highestFlexGroup = 0;
365     unsigned int lowestFlexGroup = 0;
366     bool haveFlex = false, flexingChildren = false;
367     gatherFlexChildrenInfo(iterator, relayoutChildren, highestFlexGroup, lowestFlexGroup, haveFlex);
368
369     RenderBlock::startDelayUpdateScrollInfo();
370
371     // We do 2 passes.  The first pass is simply to lay everyone out at
372     // their preferred widths.  The second pass handles flexing the children.
373     do {
374         // Reset our height.
375         setHeight(yPos);
376
377         xPos = borderLeft() + paddingLeft();
378
379         // Our first pass is done without flexing.  We simply lay the children
380         // out within the box.  We have to do a layout first in order to determine
381         // our box's intrinsic height.
382         LayoutUnit maxAscent = 0, maxDescent = 0;
383         for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
384             // make sure we relayout children if we need it.
385             if (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent())))
386                 child->setChildNeedsLayout(true, MarkOnlyThis);
387
388             if (child->isOutOfFlowPositioned())
389                 continue;
390
391             // Compute the child's vertical margins.
392             child->computeAndSetBlockDirectionMargins(this);
393
394             if (!child->needsLayout())
395                 child->markForPaginationRelayoutIfNeeded();
396
397             // Now do the layout.
398             child->layoutIfNeeded();
399
400             // Update our height and overflow height.
401             if (style()->boxAlign() == BBASELINE) {
402                 LayoutUnit ascent = child->firstLineBoxBaseline();
403                 if (ascent == -1)
404                     ascent = child->height() + child->marginBottom();
405                 ascent += child->marginTop();
406                 LayoutUnit descent = (child->height() + child->marginHeight()) - ascent;
407
408                 // Update our maximum ascent.
409                 maxAscent = max(maxAscent, ascent);
410
411                 // Update our maximum descent.
412                 maxDescent = max(maxDescent, descent);
413
414                 // Now update our height.
415                 setHeight(max(yPos + maxAscent + maxDescent, height()));
416             }
417             else
418                 setHeight(max(height(), yPos + child->height() + child->marginHeight()));
419         }
420
421         if (!iterator.first() && hasLineIfEmpty())
422             setHeight(height() + lineHeight(true, style()->isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
423
424         setHeight(height() + toAdd);
425
426         oldHeight = height();
427         updateLogicalHeight();
428
429         relayoutChildren = false;
430         if (oldHeight != height())
431             heightSpecified = true;
432
433         // Now that our height is actually known, we can place our boxes.
434         m_stretchingChildren = (style()->boxAlign() == BSTRETCH);
435         for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
436             if (child->isOutOfFlowPositioned()) {
437                 child->containingBlock()->insertPositionedObject(child);
438                 RenderLayer* childLayer = child->layer();
439                 childLayer->setStaticInlinePosition(xPos); // FIXME: Not right for regions.
440                 if (childLayer->staticBlockPosition() != yPos) {
441                     childLayer->setStaticBlockPosition(yPos);
442                     if (child->style()->hasStaticBlockPosition(style()->isHorizontalWritingMode()))
443                         child->setChildNeedsLayout(true, MarkOnlyThis);
444                 }
445                 continue;
446             }
447             
448             if (child->style()->visibility() == COLLAPSE) {
449                 // visibility: collapsed children do not participate in our positioning.
450                 // But we need to lay them down.
451                 child->layoutIfNeeded();
452                 continue;
453             }
454
455
456             // We need to see if this child's height has changed, since we make block elements
457             // fill the height of a containing box by default.
458             // Now do a layout.
459             LayoutUnit oldChildHeight = child->height();
460             child->updateLogicalHeight();
461             if (oldChildHeight != child->height())
462                 child->setChildNeedsLayout(true, MarkOnlyThis);
463
464             if (!child->needsLayout())
465                 child->markForPaginationRelayoutIfNeeded();
466
467             child->layoutIfNeeded();
468
469             // We can place the child now, using our value of box-align.
470             xPos += child->marginLeft();
471             LayoutUnit childY = yPos;
472             switch (style()->boxAlign()) {
473                 case BCENTER:
474                     childY += child->marginTop() + max<LayoutUnit>(0, (contentHeight() - (child->height() + child->marginHeight())) / 2);
475                     break;
476                 case BBASELINE: {
477                     LayoutUnit ascent = child->firstLineBoxBaseline();
478                     if (ascent == -1)
479                         ascent = child->height() + child->marginBottom();
480                     ascent += child->marginTop();
481                     childY += child->marginTop() + (maxAscent - ascent);
482                     break;
483                 }
484                 case BEND:
485                     childY += contentHeight() - child->marginBottom() - child->height();
486                     break;
487                 default: // BSTART
488                     childY += child->marginTop();
489                     break;
490             }
491
492             placeChild(child, LayoutPoint(xPos, childY));
493
494             xPos += child->width() + child->marginRight();
495         }
496
497         remainingSpace = borderLeft() + paddingLeft() + contentWidth() - xPos;
498
499         m_stretchingChildren = false;
500         if (flexingChildren)
501             haveFlex = false; // We're done.
502         else if (haveFlex) {
503             // We have some flexible objects.  See if we need to grow/shrink them at all.
504             if (!remainingSpace)
505                 break;
506
507             // Allocate the remaining space among the flexible objects.  If we are trying to
508             // grow, then we go from the lowest flex group to the highest flex group.  For shrinking,
509             // we go from the highest flex group to the lowest group.
510             bool expanding = remainingSpace > 0;
511             unsigned int start = expanding ? lowestFlexGroup : highestFlexGroup;
512             unsigned int end = expanding? highestFlexGroup : lowestFlexGroup;
513             for (unsigned int i = start; i <= end && remainingSpace; i++) {
514                 // Always start off by assuming the group can get all the remaining space.
515                 LayoutUnit groupRemainingSpace = remainingSpace;
516                 do {
517                     // Flexing consists of multiple passes, since we have to change ratios every time an object hits its max/min-width
518                     // For a given pass, we always start off by computing the totalFlex of all objects that can grow/shrink at all, and
519                     // computing the allowed growth before an object hits its min/max width (and thus
520                     // forces a totalFlex recomputation).
521                     LayoutUnit groupRemainingSpaceAtBeginning = groupRemainingSpace;
522                     float totalFlex = 0.0f;
523                     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
524                         if (allowedChildFlex(child, expanding, i))
525                             totalFlex += child->style()->boxFlex();
526                     }
527                     LayoutUnit spaceAvailableThisPass = groupRemainingSpace;
528                     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
529                         LayoutUnit allowedFlex = allowedChildFlex(child, expanding, i);
530                         if (allowedFlex) {
531                             LayoutUnit projectedFlex = (allowedFlex == LayoutUnit::max()) ? allowedFlex : LayoutUnit(allowedFlex * (totalFlex / child->style()->boxFlex()));
532                             spaceAvailableThisPass = expanding ? min(spaceAvailableThisPass, projectedFlex) : max(spaceAvailableThisPass, projectedFlex);
533                         }
534                     }
535
536                     // The flex groups may not have any flexible objects this time around.
537                     if (!spaceAvailableThisPass || totalFlex == 0.0f) {
538                         // If we just couldn't grow/shrink any more, then it's time to transition to the next flex group.
539                         groupRemainingSpace = 0;
540                         continue;
541                     }
542
543                     // Now distribute the space to objects.
544                     for (RenderBox* child = iterator.first(); child && spaceAvailableThisPass && totalFlex; child = iterator.next()) {
545                         if (child->style()->visibility() == COLLAPSE)
546                             continue;
547
548                         if (allowedChildFlex(child, expanding, i)) {
549                             LayoutUnit spaceAdd = LayoutUnit(spaceAvailableThisPass * (child->style()->boxFlex() / totalFlex));
550                             if (spaceAdd) {
551                                 child->setOverrideLogicalContentWidth(contentWidthForChild(child) + spaceAdd);
552                                 flexingChildren = true;
553                                 relayoutChildren = true;
554                             }
555
556                             spaceAvailableThisPass -= spaceAdd;
557                             remainingSpace -= spaceAdd;
558                             groupRemainingSpace -= spaceAdd;
559
560                             totalFlex -= child->style()->boxFlex();
561                         }
562                     }
563                     if (groupRemainingSpace == groupRemainingSpaceAtBeginning) {
564                         // This is not advancing, avoid getting stuck by distributing the remaining pixels.
565                         LayoutUnit spaceAdd = groupRemainingSpace > 0 ? 1 : -1;
566                         for (RenderBox* child = iterator.first(); child && groupRemainingSpace; child = iterator.next()) {
567                             if (allowedChildFlex(child, expanding, i)) {
568                                 child->setOverrideLogicalContentWidth(contentWidthForChild(child) + spaceAdd);
569                                 flexingChildren = true;
570                                 relayoutChildren = true;
571                                 remainingSpace -= spaceAdd;
572                                 groupRemainingSpace -= spaceAdd;
573                             }
574                         }
575                     }
576                 } while (absoluteValue(groupRemainingSpace) >= 1);
577             }
578
579             // We didn't find any children that could grow.
580             if (haveFlex && !flexingChildren)
581                 haveFlex = false;
582         }
583     } while (haveFlex);
584
585     RenderBlock::finishDelayUpdateScrollInfo();
586
587     if (remainingSpace > 0 && ((style()->isLeftToRightDirection() && style()->boxPack() != Start)
588         || (!style()->isLeftToRightDirection() && style()->boxPack() != End))) {
589         // Children must be repositioned.
590         LayoutUnit offset = 0;
591         if (style()->boxPack() == Justify) {
592             // Determine the total number of children.
593             int totalChildren = 0;
594             for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
595                 if (childDoesNotAffectWidthOrFlexing(child))
596                     continue;
597                 ++totalChildren;
598             }
599
600             // Iterate over the children and space them out according to the
601             // justification level.
602             if (totalChildren > 1) {
603                 --totalChildren;
604                 bool firstChild = true;
605                 for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
606                     if (childDoesNotAffectWidthOrFlexing(child))
607                         continue;
608
609                     if (firstChild) {
610                         firstChild = false;
611                         continue;
612                     }
613
614                     offset += remainingSpace/totalChildren;
615                     remainingSpace -= (remainingSpace/totalChildren);
616                     --totalChildren;
617
618                     placeChild(child, child->location() + LayoutSize(offset, 0));
619                 }
620             }
621         } else {
622             if (style()->boxPack() == Center)
623                 offset += remainingSpace / 2;
624             else // END for LTR, START for RTL
625                 offset += remainingSpace;
626             for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
627                 if (childDoesNotAffectWidthOrFlexing(child))
628                     continue;
629
630                 placeChild(child, child->location() + LayoutSize(offset, 0));
631             }
632         }
633     }
634
635     // So that the computeLogicalHeight in layoutBlock() knows to relayout positioned objects because of
636     // a height change, we revert our height back to the intrinsic height before returning.
637     if (heightSpecified)
638         setHeight(oldHeight);
639 }
640
641 void RenderDeprecatedFlexibleBox::layoutVerticalBox(bool relayoutChildren)
642 {
643     LayoutUnit yPos = borderTop() + paddingTop();
644     LayoutUnit toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
645     bool heightSpecified = false;
646     LayoutUnit oldHeight = 0;
647
648     LayoutUnit remainingSpace = 0;
649
650     FlexBoxIterator iterator(this);
651     unsigned int highestFlexGroup = 0;
652     unsigned int lowestFlexGroup = 0;
653     bool haveFlex = false, flexingChildren = false;
654     gatherFlexChildrenInfo(iterator, relayoutChildren, highestFlexGroup, lowestFlexGroup, haveFlex);
655
656     // We confine the line clamp ugliness to vertical flexible boxes (thus keeping it out of
657     // mainstream block layout); this is not really part of the XUL box model.
658     bool haveLineClamp = !style()->lineClamp().isNone();
659     if (haveLineClamp)
660         applyLineClamp(iterator, relayoutChildren);
661
662     RenderBlock::startDelayUpdateScrollInfo();
663
664     // We do 2 passes.  The first pass is simply to lay everyone out at
665     // their preferred widths.  The second pass handles flexing the children.
666     // Our first pass is done without flexing.  We simply lay the children
667     // out within the box.
668     do {
669         setHeight(borderTop() + paddingTop());
670         LayoutUnit minHeight = height() + toAdd;
671
672         for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
673             // Make sure we relayout children if we need it.
674             if (!haveLineClamp && (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent()))))
675                 child->setChildNeedsLayout(true, MarkOnlyThis);
676
677             if (child->isOutOfFlowPositioned()) {
678                 child->containingBlock()->insertPositionedObject(child);
679                 RenderLayer* childLayer = child->layer();
680                 childLayer->setStaticInlinePosition(borderStart() + paddingStart()); // FIXME: Not right for regions.
681                 if (childLayer->staticBlockPosition() != height()) {
682                     childLayer->setStaticBlockPosition(height());
683                     if (child->style()->hasStaticBlockPosition(style()->isHorizontalWritingMode()))
684                         child->setChildNeedsLayout(true, MarkOnlyThis);
685                 }
686                 continue;
687             }
688             
689             if (child->style()->visibility() == COLLAPSE) {
690                 // visibility: collapsed children do not participate in our positioning.
691                 // But we need to lay them down.
692                 child->layoutIfNeeded();
693                 continue;
694             }
695
696             // Compute the child's vertical margins.
697             child->computeAndSetBlockDirectionMargins(this);
698
699             // Add in the child's marginTop to our height.
700             setHeight(height() + child->marginTop());
701
702             if (!child->needsLayout())
703                 child->markForPaginationRelayoutIfNeeded();
704
705             // Now do a layout.
706             child->layoutIfNeeded();
707
708             // We can place the child now, using our value of box-align.
709             LayoutUnit childX = borderLeft() + paddingLeft();
710             switch (style()->boxAlign()) {
711                 case BCENTER:
712                 case BBASELINE: // Baseline just maps to center for vertical boxes
713                     childX += child->marginLeft() + max<LayoutUnit>(0, (contentWidth() - (child->width() + child->marginWidth())) / 2);
714                     break;
715                 case BEND:
716                     if (!style()->isLeftToRightDirection())
717                         childX += child->marginLeft();
718                     else
719                         childX += contentWidth() - child->marginRight() - child->width();
720                     break;
721                 default: // BSTART/BSTRETCH
722                     if (style()->isLeftToRightDirection())
723                         childX += child->marginLeft();
724                     else
725                         childX += contentWidth() - child->marginRight() - child->width();
726                     break;
727             }
728
729             // Place the child.
730             placeChild(child, LayoutPoint(childX, height()));
731             setHeight(height() + child->height() + child->marginBottom());
732         }
733
734         yPos = height();
735
736         if (!iterator.first() && hasLineIfEmpty())
737             setHeight(height() + lineHeight(true, style()->isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
738
739         setHeight(height() + toAdd);
740
741         // Negative margins can cause our height to shrink below our minimal height (border/padding).
742         // If this happens, ensure that the computed height is increased to the minimal height.
743         if (height() < minHeight)
744             setHeight(minHeight);
745
746         // Now we have to calc our height, so we know how much space we have remaining.
747         oldHeight = height();
748         updateLogicalHeight();
749         if (oldHeight != height())
750             heightSpecified = true;
751
752         remainingSpace = borderTop() + paddingTop() + contentHeight() - yPos;
753
754         if (flexingChildren)
755             haveFlex = false; // We're done.
756         else if (haveFlex) {
757             // We have some flexible objects.  See if we need to grow/shrink them at all.
758             if (!remainingSpace)
759                 break;
760
761             // Allocate the remaining space among the flexible objects.  If we are trying to
762             // grow, then we go from the lowest flex group to the highest flex group.  For shrinking,
763             // we go from the highest flex group to the lowest group.
764             bool expanding = remainingSpace > 0;
765             unsigned int start = expanding ? lowestFlexGroup : highestFlexGroup;
766             unsigned int end = expanding? highestFlexGroup : lowestFlexGroup;
767             for (unsigned int i = start; i <= end && remainingSpace; i++) {
768                 // Always start off by assuming the group can get all the remaining space.
769                 LayoutUnit groupRemainingSpace = remainingSpace;
770                 do {
771                     // Flexing consists of multiple passes, since we have to change ratios every time an object hits its max/min-width
772                     // For a given pass, we always start off by computing the totalFlex of all objects that can grow/shrink at all, and
773                     // computing the allowed growth before an object hits its min/max width (and thus
774                     // forces a totalFlex recomputation).
775                     LayoutUnit groupRemainingSpaceAtBeginning = groupRemainingSpace;
776                     float totalFlex = 0.0f;
777                     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
778                         if (allowedChildFlex(child, expanding, i))
779                             totalFlex += child->style()->boxFlex();
780                     }
781                     LayoutUnit spaceAvailableThisPass = groupRemainingSpace;
782                     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
783                         LayoutUnit allowedFlex = allowedChildFlex(child, expanding, i);
784                         if (allowedFlex) {
785                             LayoutUnit projectedFlex = (allowedFlex == LayoutUnit::max()) ? allowedFlex : static_cast<LayoutUnit>(allowedFlex * (totalFlex / child->style()->boxFlex()));
786                             spaceAvailableThisPass = expanding ? min(spaceAvailableThisPass, projectedFlex) : max(spaceAvailableThisPass, projectedFlex);
787                         }
788                     }
789
790                     // The flex groups may not have any flexible objects this time around.
791                     if (!spaceAvailableThisPass || totalFlex == 0.0f) {
792                         // If we just couldn't grow/shrink any more, then it's time to transition to the next flex group.
793                         groupRemainingSpace = 0;
794                         continue;
795                     }
796
797                     // Now distribute the space to objects.
798                     for (RenderBox* child = iterator.first(); child && spaceAvailableThisPass && totalFlex; child = iterator.next()) {
799                         if (allowedChildFlex(child, expanding, i)) {
800                             LayoutUnit spaceAdd = static_cast<LayoutUnit>(spaceAvailableThisPass * (child->style()->boxFlex() / totalFlex));
801                             if (spaceAdd) {
802                                 child->setOverrideLogicalContentHeight(contentHeightForChild(child) + spaceAdd);
803                                 flexingChildren = true;
804                                 relayoutChildren = true;
805                             }
806
807                             spaceAvailableThisPass -= spaceAdd;
808                             remainingSpace -= spaceAdd;
809                             groupRemainingSpace -= spaceAdd;
810
811                             totalFlex -= child->style()->boxFlex();
812                         }
813                     }
814                     if (groupRemainingSpace == groupRemainingSpaceAtBeginning) {
815                         // This is not advancing, avoid getting stuck by distributing the remaining pixels.
816                         LayoutUnit spaceAdd = groupRemainingSpace > 0 ? 1 : -1;
817                         for (RenderBox* child = iterator.first(); child && groupRemainingSpace; child = iterator.next()) {
818                             if (allowedChildFlex(child, expanding, i)) {
819                                 child->setOverrideLogicalContentHeight(contentHeightForChild(child) + spaceAdd);
820                                 flexingChildren = true;
821                                 relayoutChildren = true;
822                                 remainingSpace -= spaceAdd;
823                                 groupRemainingSpace -= spaceAdd;
824                             }
825                         }
826                     }
827                 } while (absoluteValue(groupRemainingSpace) >= 1);
828             }
829
830             // We didn't find any children that could grow.
831             if (haveFlex && !flexingChildren)
832                 haveFlex = false;
833         }
834     } while (haveFlex);
835
836     RenderBlock::finishDelayUpdateScrollInfo();
837
838     if (style()->boxPack() != Start && remainingSpace > 0) {
839         // Children must be repositioned.
840         LayoutUnit offset = 0;
841         if (style()->boxPack() == Justify) {
842             // Determine the total number of children.
843             int totalChildren = 0;
844             for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
845                 if (childDoesNotAffectWidthOrFlexing(child))
846                     continue;
847
848                 ++totalChildren;
849             }
850
851             // Iterate over the children and space them out according to the
852             // justification level.
853             if (totalChildren > 1) {
854                 --totalChildren;
855                 bool firstChild = true;
856                 for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
857                     if (childDoesNotAffectWidthOrFlexing(child))
858                         continue;
859
860                     if (firstChild) {
861                         firstChild = false;
862                         continue;
863                     }
864
865                     offset += remainingSpace/totalChildren;
866                     remainingSpace -= (remainingSpace/totalChildren);
867                     --totalChildren;
868                     placeChild(child, child->location() + LayoutSize(0, offset));
869                 }
870             }
871         } else {
872             if (style()->boxPack() == Center)
873                 offset += remainingSpace / 2;
874             else // END
875                 offset += remainingSpace;
876             for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
877                 if (childDoesNotAffectWidthOrFlexing(child))
878                     continue;
879                 placeChild(child, child->location() + LayoutSize(0, offset));
880             }
881         }
882     }
883
884     // So that the computeLogicalHeight in layoutBlock() knows to relayout positioned objects because of
885     // a height change, we revert our height back to the intrinsic height before returning.
886     if (heightSpecified)
887         setHeight(oldHeight);
888 }
889
890 void RenderDeprecatedFlexibleBox::applyLineClamp(FlexBoxIterator& iterator, bool relayoutChildren)
891 {
892     int maxLineCount = 0;
893     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
894         if (childDoesNotAffectWidthOrFlexing(child))
895             continue;
896
897         child->clearOverrideSize();
898         if (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent()))
899             || (child->style()->height().isAuto() && child->isBlockFlow())) {
900             child->setChildNeedsLayout(true, MarkOnlyThis);
901
902             // Dirty all the positioned objects.
903             if (child->isRenderBlock()) {
904                 toRenderBlock(child)->markPositionedObjectsForLayout();
905                 toRenderBlock(child)->clearTruncation();
906             }
907         }
908         child->layoutIfNeeded();
909         if (child->style()->height().isAuto() && child->isBlockFlow())
910             maxLineCount = max(maxLineCount, toRenderBlock(child)->lineCount());
911     }
912
913     // Get the number of lines and then alter all block flow children with auto height to use the
914     // specified height. We always try to leave room for at least one line.
915     LineClampValue lineClamp = style()->lineClamp();
916     int numVisibleLines = lineClamp.isPercentage() ? max(1, (maxLineCount + 1) * lineClamp.value() / 100) : lineClamp.value();
917     if (numVisibleLines >= maxLineCount)
918         return;
919
920     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
921         if (childDoesNotAffectWidthOrFlexing(child) || !child->style()->height().isAuto() || !child->isBlockFlow())
922             continue;
923
924         RenderBlock* blockChild = toRenderBlock(child);
925         int lineCount = blockChild->lineCount();
926         if (lineCount <= numVisibleLines)
927             continue;
928
929         LayoutUnit newHeight = blockChild->heightForLineCount(numVisibleLines);
930         if (newHeight == child->height())
931             continue;
932
933         child->setChildNeedsLayout(true, MarkOnlyThis);
934         child->setOverrideLogicalContentHeight(newHeight - child->borderAndPaddingHeight());
935         child->layoutIfNeeded();
936
937         // FIXME: For now don't support RTL.
938         if (style()->direction() != LTR)
939             continue;
940
941         // Get the last line
942         RootInlineBox* lastLine = blockChild->lineAtIndex(lineCount - 1);
943         if (!lastLine)
944             continue;
945
946         RootInlineBox* lastVisibleLine = blockChild->lineAtIndex(numVisibleLines - 1);
947         if (!lastVisibleLine)
948             continue;
949
950         const UChar ellipsisAndSpace[2] = { horizontalEllipsis, ' ' };
951         DEFINE_STATIC_LOCAL(AtomicString, ellipsisAndSpaceStr, (ellipsisAndSpace, 2));
952         DEFINE_STATIC_LOCAL(AtomicString, ellipsisStr, (&horizontalEllipsis, 1));
953         const Font& font = style(numVisibleLines == 1)->font();
954
955         // Get ellipsis width, and if the last child is an anchor, it will go after the ellipsis, so add in a space and the anchor width too
956         LayoutUnit totalWidth;
957         InlineBox* anchorBox = lastLine->lastChild();
958         if (anchorBox && anchorBox->renderer()->style()->isLink())
959             totalWidth = anchorBox->logicalWidth() + font.width(constructTextRun(this, font, ellipsisAndSpace, 2, style()));
960         else {
961             anchorBox = 0;
962             totalWidth = font.width(constructTextRun(this, font, &horizontalEllipsis, 1, style()));
963         }
964
965         // See if this width can be accommodated on the last visible line
966         RenderBlock* destBlock = toRenderBlock(lastVisibleLine->renderer());
967         RenderBlock* srcBlock = toRenderBlock(lastLine->renderer());
968
969         // FIXME: Directions of src/destBlock could be different from our direction and from one another.
970         if (!srcBlock->style()->isLeftToRightDirection())
971             continue;
972
973         bool leftToRight = destBlock->style()->isLeftToRightDirection();
974         if (!leftToRight)
975             continue;
976
977         LayoutUnit blockRightEdge = destBlock->logicalRightOffsetForLine(lastVisibleLine->y(), false);
978         if (!lastVisibleLine->lineCanAccommodateEllipsis(leftToRight, blockRightEdge, lastVisibleLine->x() + lastVisibleLine->logicalWidth(), totalWidth))
979             continue;
980
981         // Let the truncation code kick in.
982         // FIXME: the text alignment should be recomputed after the width changes due to truncation.
983         LayoutUnit blockLeftEdge = destBlock->logicalLeftOffsetForLine(lastVisibleLine->y(), false);
984         lastVisibleLine->placeEllipsis(anchorBox ? ellipsisAndSpaceStr : ellipsisStr, leftToRight, blockLeftEdge, blockRightEdge, totalWidth, anchorBox);
985         destBlock->setHasMarkupTruncation(true);
986     }
987 }
988
989 void RenderDeprecatedFlexibleBox::clearLineClamp()
990 {
991     FlexBoxIterator iterator(this);
992     for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
993         if (childDoesNotAffectWidthOrFlexing(child))
994             continue;
995
996         child->clearOverrideSize();
997         if ((child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent()))
998             || (child->style()->height().isAuto() && child->isBlockFlow())) {
999             child->setChildNeedsLayout(true);
1000
1001             if (child->isRenderBlock()) {
1002                 toRenderBlock(child)->markPositionedObjectsForLayout();
1003                 toRenderBlock(child)->clearTruncation();
1004             }
1005         }
1006     }
1007 }
1008
1009 void RenderDeprecatedFlexibleBox::placeChild(RenderBox* child, const LayoutPoint& location)
1010 {
1011     LayoutRect oldRect = child->frameRect();
1012
1013     // Place the child.
1014     child->setLocation(location);
1015
1016     // If the child moved, we have to repaint it as well as any floating/positioned
1017     // descendants.  An exception is if we need a layout.  In this case, we know we're going to
1018     // repaint ourselves (and the child) anyway.
1019     if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
1020         child->repaintDuringLayoutIfMoved(oldRect);
1021 }
1022
1023 LayoutUnit RenderDeprecatedFlexibleBox::allowedChildFlex(RenderBox* child, bool expanding, unsigned int group)
1024 {
1025     if (childDoesNotAffectWidthOrFlexing(child) || child->style()->boxFlex() == 0.0f || child->style()->boxFlexGroup() != group)
1026         return 0;
1027
1028     if (expanding) {
1029         if (isHorizontal()) {
1030             // FIXME: For now just handle fixed values.
1031             LayoutUnit maxWidth = LayoutUnit::max();
1032             LayoutUnit width = contentWidthForChild(child);
1033             if (!child->style()->maxWidth().isUndefined() && child->style()->maxWidth().isFixed())
1034                 maxWidth = child->style()->maxWidth().value();
1035             else if (child->style()->maxWidth().type() == Intrinsic)
1036                 maxWidth = child->maxPreferredLogicalWidth();
1037             else if (child->style()->maxWidth().type() == MinIntrinsic)
1038                 maxWidth = child->minPreferredLogicalWidth();
1039             if (maxWidth == LayoutUnit::max())
1040                 return maxWidth;
1041             return max<LayoutUnit>(0, maxWidth - width);
1042         } else {
1043             // FIXME: For now just handle fixed values.
1044             LayoutUnit maxHeight = LayoutUnit::max();
1045             LayoutUnit height = contentHeightForChild(child);
1046             if (!child->style()->maxHeight().isUndefined() && child->style()->maxHeight().isFixed())
1047                 maxHeight = child->style()->maxHeight().value();
1048             if (maxHeight == LayoutUnit::max())
1049                 return maxHeight;
1050             return max<LayoutUnit>(0, maxHeight - height);
1051         }
1052     }
1053
1054     // FIXME: For now just handle fixed values.
1055     if (isHorizontal()) {
1056         LayoutUnit minWidth = child->minPreferredLogicalWidth();
1057         LayoutUnit width = contentWidthForChild(child);
1058         if (child->style()->minWidth().isFixed())
1059             minWidth = child->style()->minWidth().value();
1060         else if (child->style()->minWidth().type() == Intrinsic)
1061             minWidth = child->maxPreferredLogicalWidth();
1062         else if (child->style()->minWidth().type() == MinIntrinsic)
1063             minWidth = child->minPreferredLogicalWidth();
1064         else if (child->style()->minWidth().type() == Auto)
1065             minWidth = 0;
1066
1067         LayoutUnit allowedShrinkage = min<LayoutUnit>(0, minWidth - width);
1068         return allowedShrinkage;
1069     } else {
1070         Length minHeight = child->style()->minHeight();
1071         if (minHeight.isFixed() || minHeight.isAuto()) {
1072             LayoutUnit minHeight = child->style()->minHeight().value();
1073             LayoutUnit height = contentHeightForChild(child);
1074             LayoutUnit allowedShrinkage = min<LayoutUnit>(0, minHeight - height);
1075             return allowedShrinkage;
1076         }
1077     }
1078
1079     return 0;
1080 }
1081
1082 const char* RenderDeprecatedFlexibleBox::renderName() const
1083 {
1084     if (isFloating())
1085         return "RenderDeprecatedFlexibleBox (floating)";
1086     if (isOutOfFlowPositioned())
1087         return "RenderDeprecatedFlexibleBox (positioned)";
1088     // FIXME: Temporary hack while the new generated content system is being implemented.
1089     if (isPseudoElement())
1090         return "RenderDeprecatedFlexibleBox (generated)";
1091     if (isAnonymous())
1092         return "RenderDeprecatedFlexibleBox (generated)";
1093     if (isRelPositioned())
1094         return "RenderDeprecatedFlexibleBox (relative positioned)";
1095     return "RenderDeprecatedFlexibleBox";
1096 }
1097
1098 } // namespace WebCore