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 "core/rendering/RenderDeprecatedFlexibleBox.h"
27
28#include "core/frame/UseCounter.h"
29#include "core/rendering/RenderLayer.h"
30#include "core/rendering/RenderView.h"
31#include "core/rendering/TextAutosizer.h"
32#include "core/rendering/TextRunConstructor.h"
33#include "platform/fonts/Font.h"
34#include "wtf/StdLibExtras.h"
35#include "wtf/unicode/CharacterNames.h"
36
37namespace blink {
38
39class FlexBoxIterator {
40public:
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 (static_cast<size_t>(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 (m_ordinalValues.size() != m_sortedOrdinalValues.size()) {
88                        copyToVector(m_ordinalValues, m_sortedOrdinalValues);
89                        std::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
105private:
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
122RenderDeprecatedFlexibleBox::RenderDeprecatedFlexibleBox(Element& element)
123    : RenderBlock(&element)
124{
125    ASSERT(!childrenInline());
126    m_stretchingChildren = false;
127    if (!isAnonymous()) {
128        const KURL& url = document().url();
129        if (url.protocolIs("chrome"))
130            UseCounter::count(document(), UseCounter::DeprecatedFlexboxChrome);
131        else if (url.protocolIs("chrome-extension"))
132            UseCounter::count(document(), UseCounter::DeprecatedFlexboxChromeExtension);
133        else
134            UseCounter::count(document(), UseCounter::DeprecatedFlexboxWebContent);
135    }
136}
137
138RenderDeprecatedFlexibleBox::~RenderDeprecatedFlexibleBox()
139{
140}
141
142static LayoutUnit marginWidthForChild(RenderBox* child)
143{
144    // A margin basically has three types: fixed, percentage, and auto (variable).
145    // Auto and percentage margins simply become 0 when computing min/max width.
146    // Fixed margins can be added in as is.
147    Length marginLeft = child->style()->marginLeft();
148    Length marginRight = child->style()->marginRight();
149    LayoutUnit margin = 0;
150    if (marginLeft.isFixed())
151        margin += marginLeft.value();
152    if (marginRight.isFixed())
153        margin += marginRight.value();
154    return margin;
155}
156
157static bool childDoesNotAffectWidthOrFlexing(RenderObject* child)
158{
159    // Positioned children and collapsed children don't affect the min/max width.
160    return child->isOutOfFlowPositioned() || child->style()->visibility() == COLLAPSE;
161}
162
163static LayoutUnit contentWidthForChild(RenderBox* child)
164{
165    if (child->hasOverrideWidth())
166        return child->overrideLogicalContentWidth();
167    return child->logicalWidth() - child->borderAndPaddingLogicalWidth();
168}
169
170static LayoutUnit contentHeightForChild(RenderBox* child)
171{
172    if (child->hasOverrideHeight())
173        return child->overrideLogicalContentHeight();
174    return child->logicalHeight() - child->borderAndPaddingLogicalHeight();
175}
176
177void RenderDeprecatedFlexibleBox::styleWillChange(StyleDifference diff, const RenderStyle& newStyle)
178{
179    RenderStyle* oldStyle = style();
180    if (oldStyle && !oldStyle->lineClamp().isNone() && newStyle.lineClamp().isNone())
181        clearLineClamp();
182
183    RenderBlock::styleWillChange(diff, newStyle);
184}
185
186void RenderDeprecatedFlexibleBox::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const
187{
188    if (hasMultipleLines() || isVertical()) {
189        for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
190            if (childDoesNotAffectWidthOrFlexing(child))
191                continue;
192
193            LayoutUnit margin = marginWidthForChild(child);
194            LayoutUnit width = child->minPreferredLogicalWidth() + margin;
195            minLogicalWidth = std::max(width, minLogicalWidth);
196
197            width = child->maxPreferredLogicalWidth() + margin;
198            maxLogicalWidth = std::max(width, maxLogicalWidth);
199        }
200    } else {
201        for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
202            if (childDoesNotAffectWidthOrFlexing(child))
203                continue;
204
205            LayoutUnit margin = marginWidthForChild(child);
206            minLogicalWidth += child->minPreferredLogicalWidth() + margin;
207            maxLogicalWidth += child->maxPreferredLogicalWidth() + margin;
208        }
209    }
210
211    maxLogicalWidth = std::max(minLogicalWidth, maxLogicalWidth);
212
213    LayoutUnit scrollbarWidth = instrinsicScrollbarLogicalWidth();
214    maxLogicalWidth += scrollbarWidth;
215    minLogicalWidth += scrollbarWidth;
216}
217
218void RenderDeprecatedFlexibleBox::computePreferredLogicalWidths()
219{
220    ASSERT(preferredLogicalWidthsDirty());
221
222    m_minPreferredLogicalWidth = m_maxPreferredLogicalWidth = 0;
223    RenderStyle* styleToUse = style();
224
225    if (styleToUse->width().isFixed() && styleToUse->width().value() > 0)
226        m_minPreferredLogicalWidth = m_maxPreferredLogicalWidth = adjustContentBoxLogicalWidthForBoxSizing(styleToUse->width().value());
227    else
228        computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth);
229
230    if (styleToUse->minWidth().isFixed() && styleToUse->minWidth().value() > 0) {
231        m_maxPreferredLogicalWidth = std::max(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->minWidth().value()));
232        m_minPreferredLogicalWidth = std::max(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->minWidth().value()));
233    }
234
235    if (styleToUse->maxWidth().isFixed()) {
236        m_maxPreferredLogicalWidth = std::min(m_maxPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->maxWidth().value()));
237        m_minPreferredLogicalWidth = std::min(m_minPreferredLogicalWidth, adjustContentBoxLogicalWidthForBoxSizing(styleToUse->maxWidth().value()));
238    }
239
240    LayoutUnit borderAndPadding = borderAndPaddingLogicalWidth();
241    m_minPreferredLogicalWidth += borderAndPadding;
242    m_maxPreferredLogicalWidth += borderAndPadding;
243
244    clearPreferredLogicalWidthsDirty();
245}
246
247void RenderDeprecatedFlexibleBox::layoutBlock(bool relayoutChildren)
248{
249    ASSERT(needsLayout());
250
251    if (!relayoutChildren && simplifiedLayout())
252        return;
253
254    {
255        // LayoutState needs this deliberate scope to pop before paint invalidation.
256        LayoutState state(*this, locationOffset());
257
258        LayoutSize previousSize = size();
259
260        updateLogicalWidth();
261        updateLogicalHeight();
262
263        TextAutosizer::LayoutScope textAutosizerLayoutScope(this);
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        if (isHorizontal())
275            layoutHorizontalBox(relayoutChildren);
276        else
277            layoutVerticalBox(relayoutChildren);
278
279        LayoutUnit oldClientAfterEdge = clientLogicalBottom();
280        updateLogicalHeight();
281
282        if (previousSize.height() != height())
283            relayoutChildren = true;
284
285        layoutPositionedObjects(relayoutChildren || isDocumentElement());
286
287        computeOverflow(oldClientAfterEdge);
288    }
289
290    updateLayerTransformAfterLayout();
291
292    if (view()->layoutState()->pageLogicalHeight())
293        setPageLogicalOffset(view()->layoutState()->pageLogicalOffset(*this, logicalTop()));
294
295    // Update our scrollbars if we're overflow:auto/scroll/hidden now that we know if
296    // we overflow or not.
297    if (hasOverflowClip())
298        layer()->scrollableArea()->updateAfterLayout();
299
300    clearNeedsLayout();
301}
302
303// The first walk over our kids is to find out if we have any flexible children.
304static void gatherFlexChildrenInfo(FlexBoxIterator& iterator, bool relayoutChildren, unsigned int& highestFlexGroup, unsigned int& lowestFlexGroup, bool& haveFlex)
305{
306    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
307        // Check to see if this child flexes.
308        if (!childDoesNotAffectWidthOrFlexing(child) && child->style()->boxFlex() > 0.0f) {
309            // We always have to lay out flexible objects again, since the flex distribution
310            // may have changed, and we need to reallocate space.
311            child->clearOverrideSize();
312            if (!relayoutChildren)
313                child->setChildNeedsLayout(MarkOnlyThis);
314            haveFlex = true;
315            unsigned int flexGroup = child->style()->boxFlexGroup();
316            if (lowestFlexGroup == 0)
317                lowestFlexGroup = flexGroup;
318            if (flexGroup < lowestFlexGroup)
319                lowestFlexGroup = flexGroup;
320            if (flexGroup > highestFlexGroup)
321                highestFlexGroup = flexGroup;
322        }
323    }
324}
325
326void RenderDeprecatedFlexibleBox::layoutHorizontalBox(bool relayoutChildren)
327{
328    LayoutUnit toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
329    LayoutUnit yPos = borderTop() + paddingTop();
330    LayoutUnit xPos = borderLeft() + paddingLeft();
331    bool heightSpecified = false;
332    LayoutUnit oldHeight = 0;
333
334    LayoutUnit remainingSpace = 0;
335
336
337    FlexBoxIterator iterator(this);
338    unsigned int highestFlexGroup = 0;
339    unsigned int lowestFlexGroup = 0;
340    bool haveFlex = false, flexingChildren = false;
341    gatherFlexChildrenInfo(iterator, relayoutChildren, highestFlexGroup, lowestFlexGroup, haveFlex);
342
343    RenderBlock::startDelayUpdateScrollInfo();
344
345    // We do 2 passes.  The first pass is simply to lay everyone out at
346    // their preferred widths.  The second pass handles flexing the children.
347    do {
348        // Reset our height.
349        setHeight(yPos);
350
351        xPos = borderLeft() + paddingLeft();
352
353        // Our first pass is done without flexing.  We simply lay the children
354        // out within the box.  We have to do a layout first in order to determine
355        // our box's intrinsic height.
356        LayoutUnit maxAscent = 0, maxDescent = 0;
357        for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
358            if (child->isOutOfFlowPositioned())
359                continue;
360
361            SubtreeLayoutScope layoutScope(*child);
362            if (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent())))
363                layoutScope.setChildNeedsLayout(child);
364
365            // Compute the child's vertical margins.
366            child->computeAndSetBlockDirectionMargins(this);
367
368            if (!child->needsLayout())
369                child->markForPaginationRelayoutIfNeeded(layoutScope);
370
371            // Now do the layout.
372            child->layoutIfNeeded();
373
374            // Update our height and overflow height.
375            if (style()->boxAlign() == BBASELINE) {
376                LayoutUnit ascent = child->firstLineBoxBaseline();
377                if (ascent == -1)
378                    ascent = child->height() + child->marginBottom();
379                ascent += child->marginTop();
380                LayoutUnit descent = (child->height() + child->marginHeight()) - ascent;
381
382                // Update our maximum ascent.
383                maxAscent = std::max(maxAscent, ascent);
384
385                // Update our maximum descent.
386                maxDescent = std::max(maxDescent, descent);
387
388                // Now update our height.
389                setHeight(std::max(yPos + maxAscent + maxDescent, height()));
390            } else {
391                setHeight(std::max(height(), yPos + child->height() + child->marginHeight()));
392            }
393        }
394
395        if (!iterator.first() && hasLineIfEmpty())
396            setHeight(height() + lineHeight(true, style()->isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
397
398        setHeight(height() + toAdd);
399
400        oldHeight = height();
401        updateLogicalHeight();
402
403        relayoutChildren = false;
404        if (oldHeight != height())
405            heightSpecified = true;
406
407        // Now that our height is actually known, we can place our boxes.
408        m_stretchingChildren = (style()->boxAlign() == BSTRETCH);
409        for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
410            if (child->isOutOfFlowPositioned()) {
411                child->containingBlock()->insertPositionedObject(child);
412                RenderLayer* childLayer = child->layer();
413                childLayer->setStaticInlinePosition(xPos);
414                if (childLayer->staticBlockPosition() != yPos) {
415                    childLayer->setStaticBlockPosition(yPos);
416                    if (child->style()->hasStaticBlockPosition(style()->isHorizontalWritingMode()))
417                        child->setChildNeedsLayout(MarkOnlyThis);
418                }
419                continue;
420            }
421
422            if (child->style()->visibility() == COLLAPSE) {
423                // visibility: collapsed children do not participate in our positioning.
424                // But we need to lay them down.
425                child->layoutIfNeeded();
426                continue;
427            }
428
429            SubtreeLayoutScope layoutScope(*child);
430
431            // We need to see if this child's height has changed, since we make block elements
432            // fill the height of a containing box by default.
433            // Now do a layout.
434            LayoutUnit oldChildHeight = child->height();
435            child->updateLogicalHeight();
436            if (oldChildHeight != child->height())
437                layoutScope.setChildNeedsLayout(child);
438
439            if (!child->needsLayout())
440                child->markForPaginationRelayoutIfNeeded(layoutScope);
441
442            child->layoutIfNeeded();
443
444            // We can place the child now, using our value of box-align.
445            xPos += child->marginLeft();
446            LayoutUnit childY = yPos;
447            switch (style()->boxAlign()) {
448                case BCENTER:
449                    childY += child->marginTop() + std::max<LayoutUnit>(0, (contentHeight() - (child->height() + child->marginHeight())) / 2);
450                    break;
451                case BBASELINE: {
452                    LayoutUnit ascent = child->firstLineBoxBaseline();
453                    if (ascent == -1)
454                        ascent = child->height() + child->marginBottom();
455                    ascent += child->marginTop();
456                    childY += child->marginTop() + (maxAscent - ascent);
457                    break;
458                }
459                case BEND:
460                    childY += contentHeight() - child->marginBottom() - child->height();
461                    break;
462                default: // BSTART
463                    childY += child->marginTop();
464                    break;
465            }
466
467            placeChild(child, LayoutPoint(xPos, childY));
468
469            xPos += child->width() + child->marginRight();
470        }
471
472        remainingSpace = borderLeft() + paddingLeft() + contentWidth() - xPos;
473
474        m_stretchingChildren = false;
475        if (flexingChildren)
476            haveFlex = false; // We're done.
477        else if (haveFlex) {
478            // We have some flexible objects.  See if we need to grow/shrink them at all.
479            if (!remainingSpace)
480                break;
481
482            // Allocate the remaining space among the flexible objects.  If we are trying to
483            // grow, then we go from the lowest flex group to the highest flex group.  For shrinking,
484            // we go from the highest flex group to the lowest group.
485            bool expanding = remainingSpace > 0;
486            unsigned int start = expanding ? lowestFlexGroup : highestFlexGroup;
487            unsigned int end = expanding? highestFlexGroup : lowestFlexGroup;
488            for (unsigned i = start; i <= end && remainingSpace; i++) {
489                // Always start off by assuming the group can get all the remaining space.
490                LayoutUnit groupRemainingSpace = remainingSpace;
491                do {
492                    // Flexing consists of multiple passes, since we have to change ratios every time an object hits its max/min-width
493                    // For a given pass, we always start off by computing the totalFlex of all objects that can grow/shrink at all, and
494                    // computing the allowed growth before an object hits its min/max width (and thus
495                    // forces a totalFlex recomputation).
496                    LayoutUnit groupRemainingSpaceAtBeginning = groupRemainingSpace;
497                    float totalFlex = 0.0f;
498                    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
499                        if (allowedChildFlex(child, expanding, i))
500                            totalFlex += child->style()->boxFlex();
501                    }
502                    LayoutUnit spaceAvailableThisPass = groupRemainingSpace;
503                    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
504                        LayoutUnit allowedFlex = allowedChildFlex(child, expanding, i);
505                        if (allowedFlex) {
506                            LayoutUnit projectedFlex = (allowedFlex == LayoutUnit::max()) ? allowedFlex : LayoutUnit(allowedFlex * (totalFlex / child->style()->boxFlex()));
507                            spaceAvailableThisPass = expanding ? std::min(spaceAvailableThisPass, projectedFlex) : std::max(spaceAvailableThisPass, projectedFlex);
508                        }
509                    }
510
511                    // The flex groups may not have any flexible objects this time around.
512                    if (!spaceAvailableThisPass || totalFlex == 0.0f) {
513                        // If we just couldn't grow/shrink any more, then it's time to transition to the next flex group.
514                        groupRemainingSpace = 0;
515                        continue;
516                    }
517
518                    // Now distribute the space to objects.
519                    for (RenderBox* child = iterator.first(); child && spaceAvailableThisPass && totalFlex; child = iterator.next()) {
520                        if (child->style()->visibility() == COLLAPSE)
521                            continue;
522
523                        if (allowedChildFlex(child, expanding, i)) {
524                            LayoutUnit spaceAdd = LayoutUnit(spaceAvailableThisPass * (child->style()->boxFlex() / totalFlex));
525                            if (spaceAdd) {
526                                child->setOverrideLogicalContentWidth(contentWidthForChild(child) + spaceAdd);
527                                flexingChildren = true;
528                                relayoutChildren = true;
529                            }
530
531                            spaceAvailableThisPass -= spaceAdd;
532                            remainingSpace -= spaceAdd;
533                            groupRemainingSpace -= spaceAdd;
534
535                            totalFlex -= child->style()->boxFlex();
536                        }
537                    }
538                    if (groupRemainingSpace == groupRemainingSpaceAtBeginning) {
539                        // This is not advancing, avoid getting stuck by distributing the remaining pixels.
540                        LayoutUnit spaceAdd = groupRemainingSpace > 0 ? 1 : -1;
541                        for (RenderBox* child = iterator.first(); child && groupRemainingSpace; child = iterator.next()) {
542                            if (allowedChildFlex(child, expanding, i)) {
543                                child->setOverrideLogicalContentWidth(contentWidthForChild(child) + spaceAdd);
544                                flexingChildren = true;
545                                relayoutChildren = true;
546                                remainingSpace -= spaceAdd;
547                                groupRemainingSpace -= spaceAdd;
548                            }
549                        }
550                    }
551                } while (absoluteValue(groupRemainingSpace) >= 1);
552            }
553
554            // We didn't find any children that could grow.
555            if (haveFlex && !flexingChildren)
556                haveFlex = false;
557        }
558    } while (haveFlex);
559
560    RenderBlock::finishDelayUpdateScrollInfo();
561
562    if (remainingSpace > 0 && ((style()->isLeftToRightDirection() && style()->boxPack() != Start)
563        || (!style()->isLeftToRightDirection() && style()->boxPack() != End))) {
564        // Children must be repositioned.
565        LayoutUnit offset = 0;
566        if (style()->boxPack() == Justify) {
567            // Determine the total number of children.
568            int totalChildren = 0;
569            for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
570                if (childDoesNotAffectWidthOrFlexing(child))
571                    continue;
572                ++totalChildren;
573            }
574
575            // Iterate over the children and space them out according to the
576            // justification level.
577            if (totalChildren > 1) {
578                --totalChildren;
579                bool firstChild = true;
580                for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
581                    if (childDoesNotAffectWidthOrFlexing(child))
582                        continue;
583
584                    if (firstChild) {
585                        firstChild = false;
586                        continue;
587                    }
588
589                    offset += remainingSpace/totalChildren;
590                    remainingSpace -= (remainingSpace/totalChildren);
591                    --totalChildren;
592
593                    placeChild(child, child->location() + LayoutSize(offset, 0));
594                }
595            }
596        } else {
597            if (style()->boxPack() == Center)
598                offset += remainingSpace / 2;
599            else // END for LTR, START for RTL
600                offset += remainingSpace;
601            for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
602                if (childDoesNotAffectWidthOrFlexing(child))
603                    continue;
604
605                placeChild(child, child->location() + LayoutSize(offset, 0));
606            }
607        }
608    }
609
610    // So that the computeLogicalHeight in layoutBlock() knows to relayout positioned objects because of
611    // a height change, we revert our height back to the intrinsic height before returning.
612    if (heightSpecified)
613        setHeight(oldHeight);
614}
615
616void RenderDeprecatedFlexibleBox::layoutVerticalBox(bool relayoutChildren)
617{
618    LayoutUnit yPos = borderTop() + paddingTop();
619    LayoutUnit toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
620    bool heightSpecified = false;
621    LayoutUnit oldHeight = 0;
622
623    LayoutUnit remainingSpace = 0;
624
625    FlexBoxIterator iterator(this);
626    unsigned int highestFlexGroup = 0;
627    unsigned int lowestFlexGroup = 0;
628    bool haveFlex = false, flexingChildren = false;
629    gatherFlexChildrenInfo(iterator, relayoutChildren, highestFlexGroup, lowestFlexGroup, haveFlex);
630
631    // We confine the line clamp ugliness to vertical flexible boxes (thus keeping it out of
632    // mainstream block layout); this is not really part of the XUL box model.
633    bool haveLineClamp = !style()->lineClamp().isNone();
634    if (haveLineClamp)
635        applyLineClamp(iterator, relayoutChildren);
636
637    RenderBlock::startDelayUpdateScrollInfo();
638
639    // We do 2 passes.  The first pass is simply to lay everyone out at
640    // their preferred widths.  The second pass handles flexing the children.
641    // Our first pass is done without flexing.  We simply lay the children
642    // out within the box.
643    do {
644        setHeight(borderTop() + paddingTop());
645        LayoutUnit minHeight = height() + toAdd;
646
647        for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
648            if (child->isOutOfFlowPositioned()) {
649                child->containingBlock()->insertPositionedObject(child);
650                RenderLayer* childLayer = child->layer();
651                childLayer->setStaticInlinePosition(borderStart() + paddingStart());
652                if (childLayer->staticBlockPosition() != height()) {
653                    childLayer->setStaticBlockPosition(height());
654                    if (child->style()->hasStaticBlockPosition(style()->isHorizontalWritingMode()))
655                        child->setChildNeedsLayout(MarkOnlyThis);
656                }
657                continue;
658            }
659
660            SubtreeLayoutScope layoutScope(*child);
661            if (!haveLineClamp && (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent()))))
662                layoutScope.setChildNeedsLayout(child);
663
664            if (child->style()->visibility() == COLLAPSE) {
665                // visibility: collapsed children do not participate in our positioning.
666                // But we need to lay them down.
667                child->layoutIfNeeded();
668                continue;
669            }
670
671            // Compute the child's vertical margins.
672            child->computeAndSetBlockDirectionMargins(this);
673
674            // Add in the child's marginTop to our height.
675            setHeight(height() + child->marginTop());
676
677            if (!child->needsLayout())
678                child->markForPaginationRelayoutIfNeeded(layoutScope);
679
680            // Now do a layout.
681            child->layoutIfNeeded();
682
683            // We can place the child now, using our value of box-align.
684            LayoutUnit childX = borderLeft() + paddingLeft();
685            switch (style()->boxAlign()) {
686                case BCENTER:
687                case BBASELINE: // Baseline just maps to center for vertical boxes
688                    childX += child->marginLeft() + std::max<LayoutUnit>(0, (contentWidth() - (child->width() + child->marginWidth())) / 2);
689                    break;
690                case BEND:
691                    if (!style()->isLeftToRightDirection())
692                        childX += child->marginLeft();
693                    else
694                        childX += contentWidth() - child->marginRight() - child->width();
695                    break;
696                default: // BSTART/BSTRETCH
697                    if (style()->isLeftToRightDirection())
698                        childX += child->marginLeft();
699                    else
700                        childX += contentWidth() - child->marginRight() - child->width();
701                    break;
702            }
703
704            // Place the child.
705            placeChild(child, LayoutPoint(childX, height()));
706            setHeight(height() + child->height() + child->marginBottom());
707        }
708
709        yPos = height();
710
711        if (!iterator.first() && hasLineIfEmpty())
712            setHeight(height() + lineHeight(true, style()->isHorizontalWritingMode() ? HorizontalLine : VerticalLine, PositionOfInteriorLineBoxes));
713
714        setHeight(height() + toAdd);
715
716        // Negative margins can cause our height to shrink below our minimal height (border/padding).
717        // If this happens, ensure that the computed height is increased to the minimal height.
718        if (height() < minHeight)
719            setHeight(minHeight);
720
721        // Now we have to calc our height, so we know how much space we have remaining.
722        oldHeight = height();
723        updateLogicalHeight();
724        if (oldHeight != height())
725            heightSpecified = true;
726
727        remainingSpace = borderTop() + paddingTop() + contentHeight() - yPos;
728
729        if (flexingChildren)
730            haveFlex = false; // We're done.
731        else if (haveFlex) {
732            // We have some flexible objects.  See if we need to grow/shrink them at all.
733            if (!remainingSpace)
734                break;
735
736            // Allocate the remaining space among the flexible objects.  If we are trying to
737            // grow, then we go from the lowest flex group to the highest flex group.  For shrinking,
738            // we go from the highest flex group to the lowest group.
739            bool expanding = remainingSpace > 0;
740            unsigned int start = expanding ? lowestFlexGroup : highestFlexGroup;
741            unsigned int end = expanding? highestFlexGroup : lowestFlexGroup;
742            for (unsigned i = start; i <= end && remainingSpace; i++) {
743                // Always start off by assuming the group can get all the remaining space.
744                LayoutUnit groupRemainingSpace = remainingSpace;
745                do {
746                    // Flexing consists of multiple passes, since we have to change ratios every time an object hits its max/min-width
747                    // For a given pass, we always start off by computing the totalFlex of all objects that can grow/shrink at all, and
748                    // computing the allowed growth before an object hits its min/max width (and thus
749                    // forces a totalFlex recomputation).
750                    LayoutUnit groupRemainingSpaceAtBeginning = groupRemainingSpace;
751                    float totalFlex = 0.0f;
752                    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
753                        if (allowedChildFlex(child, expanding, i))
754                            totalFlex += child->style()->boxFlex();
755                    }
756                    LayoutUnit spaceAvailableThisPass = groupRemainingSpace;
757                    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
758                        LayoutUnit allowedFlex = allowedChildFlex(child, expanding, i);
759                        if (allowedFlex) {
760                            LayoutUnit projectedFlex = (allowedFlex == LayoutUnit::max()) ? allowedFlex : static_cast<LayoutUnit>(allowedFlex * (totalFlex / child->style()->boxFlex()));
761                            spaceAvailableThisPass = expanding ? std::min(spaceAvailableThisPass, projectedFlex) : std::max(spaceAvailableThisPass, projectedFlex);
762                        }
763                    }
764
765                    // The flex groups may not have any flexible objects this time around.
766                    if (!spaceAvailableThisPass || totalFlex == 0.0f) {
767                        // If we just couldn't grow/shrink any more, then it's time to transition to the next flex group.
768                        groupRemainingSpace = 0;
769                        continue;
770                    }
771
772                    // Now distribute the space to objects.
773                    for (RenderBox* child = iterator.first(); child && spaceAvailableThisPass && totalFlex; child = iterator.next()) {
774                        if (allowedChildFlex(child, expanding, i)) {
775                            LayoutUnit spaceAdd = static_cast<LayoutUnit>(spaceAvailableThisPass * (child->style()->boxFlex() / totalFlex));
776                            if (spaceAdd) {
777                                child->setOverrideLogicalContentHeight(contentHeightForChild(child) + spaceAdd);
778                                flexingChildren = true;
779                                relayoutChildren = true;
780                            }
781
782                            spaceAvailableThisPass -= spaceAdd;
783                            remainingSpace -= spaceAdd;
784                            groupRemainingSpace -= spaceAdd;
785
786                            totalFlex -= child->style()->boxFlex();
787                        }
788                    }
789                    if (groupRemainingSpace == groupRemainingSpaceAtBeginning) {
790                        // This is not advancing, avoid getting stuck by distributing the remaining pixels.
791                        LayoutUnit spaceAdd = groupRemainingSpace > 0 ? 1 : -1;
792                        for (RenderBox* child = iterator.first(); child && groupRemainingSpace; child = iterator.next()) {
793                            if (allowedChildFlex(child, expanding, i)) {
794                                child->setOverrideLogicalContentHeight(contentHeightForChild(child) + spaceAdd);
795                                flexingChildren = true;
796                                relayoutChildren = true;
797                                remainingSpace -= spaceAdd;
798                                groupRemainingSpace -= spaceAdd;
799                            }
800                        }
801                    }
802                } while (absoluteValue(groupRemainingSpace) >= 1);
803            }
804
805            // We didn't find any children that could grow.
806            if (haveFlex && !flexingChildren)
807                haveFlex = false;
808        }
809    } while (haveFlex);
810
811    RenderBlock::finishDelayUpdateScrollInfo();
812
813    if (style()->boxPack() != Start && remainingSpace > 0) {
814        // Children must be repositioned.
815        LayoutUnit offset = 0;
816        if (style()->boxPack() == Justify) {
817            // Determine the total number of children.
818            int totalChildren = 0;
819            for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
820                if (childDoesNotAffectWidthOrFlexing(child))
821                    continue;
822
823                ++totalChildren;
824            }
825
826            // Iterate over the children and space them out according to the
827            // justification level.
828            if (totalChildren > 1) {
829                --totalChildren;
830                bool firstChild = true;
831                for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
832                    if (childDoesNotAffectWidthOrFlexing(child))
833                        continue;
834
835                    if (firstChild) {
836                        firstChild = false;
837                        continue;
838                    }
839
840                    offset += remainingSpace/totalChildren;
841                    remainingSpace -= (remainingSpace/totalChildren);
842                    --totalChildren;
843                    placeChild(child, child->location() + LayoutSize(0, offset));
844                }
845            }
846        } else {
847            if (style()->boxPack() == Center)
848                offset += remainingSpace / 2;
849            else // END
850                offset += remainingSpace;
851            for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
852                if (childDoesNotAffectWidthOrFlexing(child))
853                    continue;
854                placeChild(child, child->location() + LayoutSize(0, offset));
855            }
856        }
857    }
858
859    // So that the computeLogicalHeight in layoutBlock() knows to relayout positioned objects because of
860    // a height change, we revert our height back to the intrinsic height before returning.
861    if (heightSpecified)
862        setHeight(oldHeight);
863}
864
865void RenderDeprecatedFlexibleBox::applyLineClamp(FlexBoxIterator& iterator, bool relayoutChildren)
866{
867    UseCounter::count(document(), UseCounter::LineClamp);
868
869    int maxLineCount = 0;
870    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
871        if (childDoesNotAffectWidthOrFlexing(child))
872            continue;
873
874        child->clearOverrideSize();
875        if (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent()))
876            || (child->style()->height().isAuto() && child->isRenderBlock())) {
877            child->setChildNeedsLayout(MarkOnlyThis);
878
879            // Dirty all the positioned objects.
880            if (child->isRenderBlock()) {
881                toRenderBlock(child)->markPositionedObjectsForLayout();
882                toRenderBlock(child)->clearTruncation();
883            }
884        }
885        child->layoutIfNeeded();
886        if (child->style()->height().isAuto() && child->isRenderBlock())
887            maxLineCount = std::max(maxLineCount, toRenderBlock(child)->lineCount());
888    }
889
890    // Get the number of lines and then alter all block flow children with auto height to use the
891    // specified height. We always try to leave room for at least one line.
892    LineClampValue lineClamp = style()->lineClamp();
893    int numVisibleLines = lineClamp.isPercentage() ? std::max(1, (maxLineCount + 1) * lineClamp.value() / 100) : lineClamp.value();
894    if (numVisibleLines >= maxLineCount)
895        return;
896
897    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
898        if (childDoesNotAffectWidthOrFlexing(child) || !child->style()->height().isAuto() || !child->isRenderBlock())
899            continue;
900
901        RenderBlock* blockChild = toRenderBlock(child);
902        int lineCount = blockChild->lineCount();
903        if (lineCount <= numVisibleLines)
904            continue;
905
906        LayoutUnit newHeight = blockChild->heightForLineCount(numVisibleLines);
907        if (newHeight == child->height())
908            continue;
909
910        child->setOverrideLogicalContentHeight(newHeight - child->borderAndPaddingHeight());
911        child->forceChildLayout();
912
913        // FIXME: For now don't support RTL.
914        if (style()->direction() != LTR)
915            continue;
916
917        // Get the last line
918        RootInlineBox* lastLine = blockChild->lineAtIndex(lineCount - 1);
919        if (!lastLine)
920            continue;
921
922        RootInlineBox* lastVisibleLine = blockChild->lineAtIndex(numVisibleLines - 1);
923        if (!lastVisibleLine)
924            continue;
925
926        const UChar ellipsisAndSpace[2] = { horizontalEllipsis, ' ' };
927        DEFINE_STATIC_LOCAL(AtomicString, ellipsisAndSpaceStr, (ellipsisAndSpace, 2));
928        DEFINE_STATIC_LOCAL(AtomicString, ellipsisStr, (&horizontalEllipsis, 1));
929        const Font& font = style(numVisibleLines == 1)->font();
930
931        // 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
932        float totalWidth;
933        InlineBox* anchorBox = lastLine->lastChild();
934        if (anchorBox && anchorBox->renderer().style()->isLink())
935            totalWidth = anchorBox->logicalWidth() + font.width(constructTextRun(this, font, ellipsisAndSpace, 2, style(), style()->direction()));
936        else {
937            anchorBox = 0;
938            totalWidth = font.width(constructTextRun(this, font, &horizontalEllipsis, 1, style(), style()->direction()));
939        }
940
941        // See if this width can be accommodated on the last visible line
942        RenderBlockFlow& destBlock = lastVisibleLine->block();
943        RenderBlockFlow& srcBlock = lastLine->block();
944
945        // FIXME: Directions of src/destBlock could be different from our direction and from one another.
946        if (!srcBlock.style()->isLeftToRightDirection())
947            continue;
948
949        bool leftToRight = destBlock.style()->isLeftToRightDirection();
950        if (!leftToRight)
951            continue;
952
953        LayoutUnit blockRightEdge = destBlock.logicalRightOffsetForLine(lastVisibleLine->y(), false);
954        if (!lastVisibleLine->lineCanAccommodateEllipsis(leftToRight, blockRightEdge, lastVisibleLine->x() + lastVisibleLine->logicalWidth(), totalWidth))
955            continue;
956
957        // Let the truncation code kick in.
958        // FIXME: the text alignment should be recomputed after the width changes due to truncation.
959        LayoutUnit blockLeftEdge = destBlock.logicalLeftOffsetForLine(lastVisibleLine->y(), false);
960        lastVisibleLine->placeEllipsis(anchorBox ? ellipsisAndSpaceStr : ellipsisStr, leftToRight, blockLeftEdge.toFloat(), blockRightEdge.toFloat(), totalWidth, anchorBox);
961        destBlock.setHasMarkupTruncation(true);
962    }
963}
964
965void RenderDeprecatedFlexibleBox::clearLineClamp()
966{
967    FlexBoxIterator iterator(this);
968    for (RenderBox* child = iterator.first(); child; child = iterator.next()) {
969        if (childDoesNotAffectWidthOrFlexing(child))
970            continue;
971
972        child->clearOverrideSize();
973        if ((child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent()))
974            || (child->style()->height().isAuto() && child->isRenderBlock())) {
975            child->setChildNeedsLayout();
976
977            if (child->isRenderBlock()) {
978                toRenderBlock(child)->markPositionedObjectsForLayout();
979                toRenderBlock(child)->clearTruncation();
980            }
981        }
982    }
983}
984
985void RenderDeprecatedFlexibleBox::placeChild(RenderBox* child, const LayoutPoint& location)
986{
987    // FIXME Investigate if this can be removed based on other flags. crbug.com/370010
988    child->setMayNeedPaintInvalidation(true);
989
990    // Place the child.
991    child->setLocation(location);
992}
993
994LayoutUnit RenderDeprecatedFlexibleBox::allowedChildFlex(RenderBox* child, bool expanding, unsigned int group)
995{
996    if (childDoesNotAffectWidthOrFlexing(child) || child->style()->boxFlex() == 0.0f || child->style()->boxFlexGroup() != group)
997        return 0;
998
999    if (expanding) {
1000        if (isHorizontal()) {
1001            // FIXME: For now just handle fixed values.
1002            LayoutUnit maxWidth = LayoutUnit::max();
1003            LayoutUnit width = contentWidthForChild(child);
1004            if (child->style()->maxWidth().isFixed())
1005                maxWidth = child->style()->maxWidth().value();
1006            else if (child->style()->maxWidth().type() == Intrinsic)
1007                maxWidth = child->maxPreferredLogicalWidth();
1008            else if (child->style()->maxWidth().type() == MinIntrinsic)
1009                maxWidth = child->minPreferredLogicalWidth();
1010            if (maxWidth == LayoutUnit::max())
1011                return maxWidth;
1012            return std::max<LayoutUnit>(0, maxWidth - width);
1013        } else {
1014            // FIXME: For now just handle fixed values.
1015            LayoutUnit maxHeight = LayoutUnit::max();
1016            LayoutUnit height = contentHeightForChild(child);
1017            if (child->style()->maxHeight().isFixed())
1018                maxHeight = child->style()->maxHeight().value();
1019            if (maxHeight == LayoutUnit::max())
1020                return maxHeight;
1021            return std::max<LayoutUnit>(0, maxHeight - height);
1022        }
1023    }
1024
1025    // FIXME: For now just handle fixed values.
1026    if (isHorizontal()) {
1027        LayoutUnit minWidth = child->minPreferredLogicalWidth();
1028        LayoutUnit width = contentWidthForChild(child);
1029        if (child->style()->minWidth().isFixed())
1030            minWidth = child->style()->minWidth().value();
1031        else if (child->style()->minWidth().type() == Intrinsic)
1032            minWidth = child->maxPreferredLogicalWidth();
1033        else if (child->style()->minWidth().type() == MinIntrinsic)
1034            minWidth = child->minPreferredLogicalWidth();
1035        else if (child->style()->minWidth().type() == Auto)
1036            minWidth = 0;
1037
1038        LayoutUnit allowedShrinkage = std::min<LayoutUnit>(0, minWidth - width);
1039        return allowedShrinkage;
1040    } else {
1041        Length minHeight = child->style()->minHeight();
1042        if (minHeight.isFixed() || minHeight.isAuto()) {
1043            LayoutUnit minHeight = child->style()->minHeight().value();
1044            LayoutUnit height = contentHeightForChild(child);
1045            LayoutUnit allowedShrinkage = std::min<LayoutUnit>(0, minHeight - height);
1046            return allowedShrinkage;
1047        }
1048    }
1049
1050    return 0;
1051}
1052
1053const char* RenderDeprecatedFlexibleBox::renderName() const
1054{
1055    if (isFloating())
1056        return "RenderDeprecatedFlexibleBox (floating)";
1057    if (isOutOfFlowPositioned())
1058        return "RenderDeprecatedFlexibleBox (positioned)";
1059    // FIXME: Cleanup isPseudoElement duplication with other renderName methods.
1060    // crbug.com/415653
1061    if (isPseudoElement()) {
1062        if (style()->styleType() == BEFORE)
1063            return "RenderDeprecatedFlexibleBox (pseudo:before)";
1064        if (style()->styleType() == AFTER)
1065            return "RenderDeprecatedFlexibleBox (pseudo:after)";
1066        if (style()->styleType() == BACKDROP)
1067            return "RenderDeprecatedFlexibleBox (pseudo:backdrop)";
1068        ASSERT_NOT_REACHED();
1069    }
1070    if (isAnonymous())
1071        return "RenderDeprecatedFlexibleBox (generated)";
1072    if (isRelPositioned())
1073        return "RenderDeprecatedFlexibleBox (relative positioned)";
1074    return "RenderDeprecatedFlexibleBox";
1075}
1076
1077} // namespace blink
1078