2300edc92e564eb321851b4ae70944eb77ce0e9e
[WebKit-https.git] / WebCore / rendering / RenderFlexibleBox.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., 59 Temple Place - Suite 330,
21  * Boston, MA 02111-1307, USA.
22  *
23  */
24
25 #include "config.h"
26 #include "RenderFlexibleBox.h"
27
28 #include "CharacterNames.h"
29 #include "RenderLayer.h"
30 #include "RenderView.h"
31
32 using namespace std;
33
34 namespace WebCore {
35
36 class FlexBoxIterator {
37 public:
38     FlexBoxIterator(RenderFlexibleBox* parent) {
39         box = parent;
40         if (box->style()->boxOrient() == HORIZONTAL && box->style()->direction() == RTL)
41             forward = box->style()->boxDirection() != BNORMAL;
42         else
43             forward = box->style()->boxDirection() == BNORMAL;
44         lastOrdinal = 1; 
45         if (!forward) {
46             // No choice, since we're going backwards, we have to find out the highest ordinal up front.
47             RenderObject* child = box->firstChild();
48             while (child) {
49                 if (child->style()->boxOrdinalGroup() > lastOrdinal)
50                     lastOrdinal = child->style()->boxOrdinalGroup();
51                 child = child->nextSibling();
52             }
53         }
54         
55         reset();
56     }
57
58     void reset() {
59         current = 0;
60         currentOrdinal = forward ? 0 : lastOrdinal+1;
61     }
62
63     RenderObject* first() {
64         reset();
65         return next();
66     }
67     
68     RenderObject* next() {
69
70         do { 
71             if (!current) {
72                 if (forward) {
73                     currentOrdinal++; 
74                     if (currentOrdinal > lastOrdinal)
75                         return 0;
76                     current = box->firstChild();
77                 } else {
78                     currentOrdinal--;
79                     if (currentOrdinal == 0)
80                         return 0;
81                     current = box->lastChild();
82                 }
83             }
84             else
85                 current = forward ? current->nextSibling() : current->previousSibling();
86             if (current && current->style()->boxOrdinalGroup() > lastOrdinal)
87                 lastOrdinal = current->style()->boxOrdinalGroup();
88         } while (!current || current->style()->boxOrdinalGroup() != currentOrdinal ||
89                  current->style()->visibility() == COLLAPSE);
90         return current;
91     }
92
93 private:
94     RenderFlexibleBox* box;
95     RenderObject* current;
96     bool forward;
97     unsigned int currentOrdinal;
98     unsigned int lastOrdinal;
99 };
100     
101 RenderFlexibleBox::RenderFlexibleBox(Node* node)
102 :RenderBlock(node)
103 {
104     setChildrenInline(false); // All of our children must be block-level
105     m_flexingChildren = m_stretchingChildren = false;
106 }
107
108 RenderFlexibleBox::~RenderFlexibleBox()
109 {
110 }
111
112 void RenderFlexibleBox::calcHorizontalMinMaxWidth()
113 {
114     RenderObject *child = firstChild();
115     while (child) {
116         // positioned children don't affect the minmaxwidth
117         if (child->isPositioned() || child->style()->visibility() == COLLAPSE)
118         {
119             child = child->nextSibling();
120             continue;
121         }
122
123         int margin=0;
124         //  auto margins don't affect minwidth
125
126         Length ml = child->style()->marginLeft();
127         Length mr = child->style()->marginRight();
128
129         // Call calcWidth on the child to ensure that our margins are
130         // up to date.  This method can be called before the child has actually
131         // calculated its margins (which are computed inside calcWidth).
132         child->calcWidth();
133
134         if (!ml.isAuto() && !mr.isAuto()) {
135             if (!child->style()->width().isAuto()) {
136                 if (child->style()->direction()==LTR)
137                     margin = child->marginLeft();
138                 else
139                     margin = child->marginRight();
140             } else
141                 margin = child->marginLeft()+child->marginRight();
142         } else if (!ml.isAuto())
143             margin = child->marginLeft();
144         else if (!mr.isAuto())
145             margin = child->marginRight();
146
147         if (margin < 0) margin = 0;
148
149         m_minWidth += child->minWidth() + margin;
150         m_maxWidth += child->maxWidth() + margin;
151
152         child = child->nextSibling();
153     }    
154 }
155
156 void RenderFlexibleBox::calcVerticalMinMaxWidth()
157 {
158     RenderObject *child = firstChild();
159     while(child != 0)
160     {
161         // Positioned children and collapsed children don't affect the min/max width
162         if (child->isPositioned() || child->style()->visibility() == COLLAPSE) {
163             child = child->nextSibling();
164             continue;
165         }
166
167         Length ml = child->style()->marginLeft();
168         Length mr = child->style()->marginRight();
169
170         // Call calcWidth on the child to ensure that our margins are
171         // up to date.  This method can be called before the child has actually
172         // calculated its margins (which are computed inside calcWidth).
173         if (ml.isPercent() || mr.isPercent())
174             calcWidth();
175
176         // A margin basically has three types: fixed, percentage, and auto (variable).
177         // Auto margins simply become 0 when computing min/max width.
178         // Fixed margins can be added in as is.
179         // Percentage margins are computed as a percentage of the width we calculated in
180         // the calcWidth call above.  In this case we use the actual cached margin values on
181         // the RenderObject itself.
182         int margin = 0;
183         if (ml.isFixed())
184             margin += ml.value();
185         else if (ml.isPercent())
186             margin += child->marginLeft();
187
188         if (mr.isFixed())
189             margin += mr.value();
190         else if (mr.isAuto())
191             margin += child->marginRight();
192
193         if (margin < 0) margin = 0;
194         
195         int w = child->minWidth() + margin;
196         if(m_minWidth < w) m_minWidth = w;
197         
198         w = child->maxWidth() + margin;
199
200         if(m_maxWidth < w) m_maxWidth = w;
201
202         child = child->nextSibling();
203     }    
204 }
205
206 void RenderFlexibleBox::calcMinMaxWidth()
207 {
208     ASSERT( !minMaxKnown() );
209
210     m_minWidth = 0;
211     m_maxWidth = 0;
212
213     if (hasMultipleLines() || isVertical())
214         calcVerticalMinMaxWidth();
215     else
216         calcHorizontalMinMaxWidth();
217
218     if(m_maxWidth < m_minWidth) m_maxWidth = m_minWidth;
219
220     if (style()->width().isFixed() && style()->width().value() > 0)
221         m_minWidth = m_maxWidth = calcContentBoxWidth(style()->width().value());
222    
223     if (style()->minWidth().isFixed() && style()->minWidth().value() > 0) {
224         m_maxWidth = max(m_maxWidth, calcContentBoxWidth(style()->minWidth().value()));
225         m_minWidth = max(m_minWidth, calcContentBoxWidth(style()->minWidth().value()));
226     }
227     
228     if (style()->maxWidth().isFixed() && style()->maxWidth().value() != undefinedLength) {
229         m_maxWidth = min(m_maxWidth, calcContentBoxWidth(style()->maxWidth().value()));
230         m_minWidth = min(m_minWidth, calcContentBoxWidth(style()->maxWidth().value()));
231     }
232
233     int toAdd = borderLeft() + borderRight() + paddingLeft() + paddingRight();
234     m_minWidth += toAdd;
235     m_maxWidth += toAdd;
236
237     setMinMaxKnown();
238 }
239
240 void RenderFlexibleBox::layoutBlock(bool relayoutChildren)
241 {
242     ASSERT(needsLayout());
243     ASSERT(minMaxKnown());
244
245     if (!relayoutChildren && posChildNeedsLayout() && !normalChildNeedsLayout() && !selfNeedsLayout()) {
246         // All we have to is lay out our positioned objects.
247         layoutPositionedObjects(false);
248         if (hasOverflowClip())
249             m_layer->updateScrollInfoAfterLayout();
250         setNeedsLayout(false);
251         return;
252     }
253
254     IntRect oldBounds;
255     IntRect oldOutlineBox;
256     bool checkForRepaint = checkForRepaintDuringLayout();
257     if (checkForRepaint) {
258         oldBounds = absoluteClippedOverflowRect();
259         oldBounds.move(view()->layoutDelta());
260         oldOutlineBox = absoluteOutlineBox();
261         oldOutlineBox.move(view()->layoutDelta());
262     }
263
264     int previousWidth = m_width;
265     int previousHeight = m_height;
266     
267     calcWidth();
268     calcHeight();
269     m_overflowWidth = m_width;
270
271     if (previousWidth != m_width || previousHeight != m_height ||
272         (parent()->isFlexibleBox() && parent()->style()->boxOrient() == HORIZONTAL &&
273          parent()->style()->boxAlign() == BSTRETCH))
274         relayoutChildren = true;
275
276     m_height = 0;
277     m_overflowHeight = 0;
278     m_flexingChildren = m_stretchingChildren = false;
279
280     initMaxMarginValues();
281
282     // For overflow:scroll blocks, ensure we have both scrollbars in place always.
283     if (scrollsOverflow()) {
284         if (style()->overflowX() == OSCROLL)
285             m_layer->setHasHorizontalScrollbar(true);
286         if (style()->overflowY() == OSCROLL)
287             m_layer->setHasVerticalScrollbar(true);
288     }
289
290     if (isHorizontal())
291         layoutHorizontalBox(relayoutChildren);
292     else
293         layoutVerticalBox(relayoutChildren);
294
295     int oldHeight = m_height;
296     calcHeight();
297     if (oldHeight != m_height) {
298         // If the block got expanded in size, then increase our overflowheight to match.
299         if (m_overflowHeight > m_height)
300             m_overflowHeight -= (borderBottom() + paddingBottom() + horizontalScrollbarHeight());
301         if (m_overflowHeight < m_height)
302             m_overflowHeight = m_height;
303     }
304     if (previousHeight != m_height)
305         relayoutChildren = true;
306
307     layoutPositionedObjects(relayoutChildren || isRoot());
308
309     if (!isFloatingOrPositioned() && m_height == 0) {
310         // We are a block with no border and padding and a computed height
311         // of 0.  The CSS spec states that zero-height blocks collapse their margins
312         // together.
313         // When blocks are self-collapsing, we just use the top margin values and set the
314         // bottom margin max values to 0.  This way we don't factor in the values
315         // twice when we collapse with our previous vertically adjacent and
316         // following vertically adjacent blocks.
317         int pos = maxTopPosMargin();
318         int neg = maxTopNegMargin();
319         if (maxBottomPosMargin() > pos)
320             pos = maxBottomPosMargin();
321         if (maxBottomNegMargin() > neg)
322             neg = maxBottomNegMargin();
323         setMaxTopMargins(pos, neg);
324         setMaxBottomMargins(0, 0);
325     }
326
327     // Always ensure our overflow width is at least as large as our width.
328     if (m_overflowWidth < m_width)
329         m_overflowWidth = m_width;
330
331     // Update our scrollbars if we're overflow:auto/scroll/hidden now that we know if
332     // we overflow or not.
333     if (hasOverflowClip())
334         m_layer->updateScrollInfoAfterLayout();
335
336     // Repaint with our new bounds if they are different from our old bounds.
337     if (checkForRepaint)
338         repaintAfterLayoutIfNeeded(oldBounds, oldOutlineBox);
339     
340     setNeedsLayout(false);
341 }
342
343 void RenderFlexibleBox::layoutHorizontalBox(bool relayoutChildren)
344 {
345     int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
346     int yPos = borderTop() + paddingTop();
347     int xPos = borderLeft() + paddingLeft();
348     bool heightSpecified = false;
349     int oldHeight = 0;
350     
351     unsigned int highestFlexGroup = 0;
352     unsigned int lowestFlexGroup = 0;
353     bool haveFlex = false;
354     int remainingSpace = 0;
355     m_overflowHeight = m_height;
356
357     // The first walk over our kids is to find out if we have any flexible children.
358     FlexBoxIterator iterator(this);
359     RenderObject* child = iterator.next();
360     while (child) {
361         // Check to see if this child flexes.
362         if (!child->isPositioned() && child->style()->boxFlex() > 0.0f) {
363             // We always have to lay out flexible objects again, since the flex distribution
364             // may have changed, and we need to reallocate space.
365             child->setOverrideSize(-1);
366             if (!relayoutChildren)
367                 child->setChildNeedsLayout(true, false);
368             haveFlex = true;
369             unsigned int flexGroup = child->style()->boxFlexGroup();
370             if (lowestFlexGroup == 0)
371                 lowestFlexGroup = flexGroup;
372             if (flexGroup < lowestFlexGroup)
373                 lowestFlexGroup = flexGroup;
374             if (flexGroup > highestFlexGroup)
375                 highestFlexGroup = flexGroup;
376         }
377         child = iterator.next();
378     }
379     
380     // We do 2 passes.  The first pass is simply to lay everyone out at
381     // their preferred widths.  The second pass handles flexing the children.
382     do {
383         // Reset our height.
384         m_height = yPos;
385         m_overflowHeight = m_height;
386         xPos = borderLeft() + paddingLeft();
387                 
388         // Our first pass is done without flexing.  We simply lay the children
389         // out within the box.  We have to do a layout first in order to determine
390         // our box's intrinsic height.
391         int maxAscent = 0, maxDescent = 0;
392         child = iterator.first();
393         while (child) {
394             // make sure we relayout children if we need it.
395             if (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent())))
396                 child->setChildNeedsLayout(true, false);
397             
398             if (child->isPositioned()) {
399                 child = iterator.next();
400                 continue;
401             }
402     
403             // Compute the child's vertical margins.
404             child->calcVerticalMargins();
405     
406             // Now do the layout.
407             child->layoutIfNeeded();
408     
409             // Update our height and overflow height.
410             if (style()->boxAlign() == BBASELINE) {
411                 int ascent = child->marginTop() + child->getBaselineOfFirstLineBox();
412                 if (ascent == -1)
413                     ascent = child->marginTop() + child->height() + child->marginBottom();
414                 int descent = (child->marginTop() + child->height() + child->marginBottom()) - ascent;
415                 
416                 // Update our maximum ascent.
417                 maxAscent = max(maxAscent, ascent);
418                 
419                 // Update our maximum descent.
420                 maxDescent = max(maxDescent, descent);
421                 
422                 // Now update our height.
423                 m_height = max(yPos + maxAscent + maxDescent, m_height);
424             }
425             else
426                 m_height = max(m_height, yPos + child->marginTop() + child->height() + child->marginBottom());
427
428             child = iterator.next();
429         }
430         
431         if (!iterator.first() && hasLineIfEmpty())
432             m_height += lineHeight(true, true);
433         
434         m_height += toAdd;
435
436         // Always make sure our overflowheight is at least our height.
437         if (m_overflowHeight < m_height)
438             m_overflowHeight = m_height;
439         
440         oldHeight = m_height;
441         calcHeight();
442
443         relayoutChildren = false;
444         if (oldHeight != m_height)
445             heightSpecified = true;
446         
447         // Now that our height is actually known, we can place our boxes.
448         m_stretchingChildren = (style()->boxAlign() == BSTRETCH);
449         child = iterator.first();
450         while (child) {
451             if (child->isPositioned()) {
452                 child->containingBlock()->insertPositionedObject(child);
453                 if (child->hasStaticX()) {
454                     if (style()->direction() == LTR)
455                         child->setStaticX(xPos);
456                     else child->setStaticX(width() - xPos);
457                 }
458                 if (child->hasStaticY())
459                     child->setStaticY(yPos);
460                 child = iterator.next();
461                 continue;
462             }
463     
464             // We need to see if this child's height has changed, since we make block elements
465             // fill the height of a containing box by default.
466             // Now do a layout.
467             int oldChildHeight = child->height();
468             static_cast<RenderBox*>(child)->calcHeight();
469             if (oldChildHeight != child->height())
470                 child->setChildNeedsLayout(true, false);
471             child->layoutIfNeeded();
472     
473             // We can place the child now, using our value of box-align.
474             xPos += child->marginLeft();
475             int childY = yPos;
476             switch (style()->boxAlign()) {
477                 case BCENTER:
478                     childY += child->marginTop() + max(0, (contentHeight() - (child->height() + child->marginTop() + child->marginBottom()))/2);
479                     break;
480                 case BBASELINE: {
481                     int ascent = child->marginTop() + child->getBaselineOfFirstLineBox();
482                     if (ascent == -1)
483                         ascent = child->marginTop() + child->height() + child->marginBottom();
484                     childY += child->marginTop() + (maxAscent - ascent);
485                     break;
486                 }
487                 case BEND:
488                     childY += contentHeight() - child->marginBottom() - child->height();
489                     break;
490                 default: // BSTART
491                     childY += child->marginTop();
492                     break;
493             }
494
495             placeChild(child, xPos, childY);
496
497             if (child->isRenderBlock())
498                 static_cast<RenderBlock*>(child)->addVisualOverflow(static_cast<RenderBlock*>(child)->floatRect());
499
500             m_overflowHeight = max(m_overflowHeight, childY + child->overflowHeight(false));
501             m_overflowTop = min(m_overflowTop, child->yPos() + child->overflowTop(false));
502             
503             xPos += child->width() + child->marginRight();
504     
505             child = iterator.next();
506         }
507
508         remainingSpace = borderLeft() + paddingLeft() + contentWidth() - xPos;
509         
510         m_stretchingChildren = false;
511         if (m_flexingChildren)
512             haveFlex = false; // We're done.
513         else if (haveFlex) {
514             // We have some flexible objects.  See if we need to grow/shrink them at all.
515             if (!remainingSpace)
516                 break;
517
518             // Allocate the remaining space among the flexible objects.  If we are trying to
519             // grow, then we go from the lowest flex group to the highest flex group.  For shrinking,
520             // we go from the highest flex group to the lowest group.
521             bool expanding = remainingSpace > 0;
522             unsigned int start = expanding ? lowestFlexGroup : highestFlexGroup;
523             unsigned int end = expanding? highestFlexGroup : lowestFlexGroup;
524             for (unsigned int i = start; i <= end && remainingSpace; i++) {
525                 // Always start off by assuming the group can get all the remaining space.
526                 int groupRemainingSpace = remainingSpace;
527                 do {
528                     // Flexing consists of multiple passes, since we have to change ratios every time an object hits its max/min-width
529                     // For a given pass, we always start off by computing the totalFlex of all objects that can grow/shrink at all, and
530                     // computing the allowed growth before an object hits its min/max width (and thus
531                     // forces a totalFlex recomputation).
532                     float totalFlex = 0.0f;
533                     child = iterator.first();
534                     while (child) {
535                         if (allowedChildFlex(child, expanding, i))
536                             totalFlex += child->style()->boxFlex();
537                         child = iterator.next();
538                     }
539                     child = iterator.first();
540                     int spaceAvailableThisPass = groupRemainingSpace;
541                     while (child) {
542                         int allowedFlex = allowedChildFlex(child, expanding, i);
543                         if (allowedFlex) {
544                             int projectedFlex = (allowedFlex == INT_MAX) ? allowedFlex : (int)(allowedFlex * (totalFlex / child->style()->boxFlex()));
545                             spaceAvailableThisPass = expanding ? min(spaceAvailableThisPass, projectedFlex) : max(spaceAvailableThisPass, projectedFlex);
546                         }
547                         child = iterator.next();
548                     }
549
550                     // The flex groups may not have any flexible objects this time around. 
551                     if (!spaceAvailableThisPass || totalFlex == 0.0f) {
552                         // If we just couldn't grow/shrink any more, then it's time to transition to the next flex group.
553                         groupRemainingSpace = 0;
554                         continue;
555                     }
556
557                     // Now distribute the space to objects.
558                     child = iterator.first();
559                     while (child && spaceAvailableThisPass && totalFlex) {
560                         if (allowedChildFlex(child, expanding, i)) {
561                             int spaceAdd = (int)(spaceAvailableThisPass * (child->style()->boxFlex()/totalFlex));
562                             if (spaceAdd) {
563                                 child->setOverrideSize(child->overrideWidth() + spaceAdd);
564                                 m_flexingChildren = true;
565                                 relayoutChildren = true;
566                             }
567
568                             spaceAvailableThisPass -= spaceAdd;
569                             remainingSpace -= spaceAdd;
570                             groupRemainingSpace -= spaceAdd;
571                             
572                             totalFlex -= child->style()->boxFlex();
573                         }
574                         child = iterator.next();
575                     }
576                 } while (groupRemainingSpace);
577             }
578
579             // We didn't find any children that could grow.
580             if (haveFlex && !m_flexingChildren)
581                 haveFlex = false;
582         }
583     } while (haveFlex);
584
585     m_flexingChildren = false;
586     
587     if (remainingSpace > 0 && ((style()->direction() == LTR && style()->boxPack() != BSTART) ||
588                                (style()->direction() == RTL && style()->boxPack() != BEND))) {
589         // Children must be repositioned.
590         int offset = 0;
591         if (style()->boxPack() == BJUSTIFY) {
592             // Determine the total number of children.
593             int totalChildren = 0;
594             child = iterator.first();
595             while (child) {
596                 if (child->isPositioned()) {
597                     child = iterator.next();
598                     continue;
599                 }
600                 totalChildren++;
601                 child = iterator.next();
602             }
603
604             // Iterate over the children and space them out according to the
605             // justification level.
606             if (totalChildren > 1) {
607                 totalChildren--;
608                 bool firstChild = true;
609                 child = iterator.first();
610                 while (child) {
611                     if (child->isPositioned()) {
612                         child = iterator.next();
613                         continue;
614                     }
615
616                     if (firstChild) {
617                         firstChild = false;
618                         child = iterator.next();
619                         continue;
620                     }
621
622                     offset += remainingSpace/totalChildren;
623                     remainingSpace -= (remainingSpace/totalChildren);
624                     totalChildren--;
625
626                     placeChild(child, child->xPos()+offset, child->yPos());
627                     child = iterator.next();
628                 }
629             }
630         } else {
631             if (style()->boxPack() == BCENTER)
632                 offset += remainingSpace/2;
633             else // END for LTR, START for RTL
634                 offset += remainingSpace;
635             child = iterator.first();
636             while (child) {
637                 if (child->isPositioned()) {
638                     child = iterator.next();
639                     continue;
640                 }
641                 placeChild(child, child->xPos()+offset, child->yPos());
642                 child = iterator.next();
643             }
644         }
645     }
646     
647     child = iterator.first();
648     while (child && child->isPositioned()) {
649         child = iterator.next();
650     }
651     
652     if (child) {
653         m_overflowLeft = min(child->xPos() + child->overflowLeft(false), m_overflowLeft);
654
655         RenderObject* lastChild = child;
656         while ((child = iterator.next())) {
657             if (!child->isPositioned())
658                 lastChild = child;
659         }
660         m_overflowWidth = max(lastChild->xPos() + lastChild->overflowWidth(false), m_overflowWidth);
661     }
662     
663     // So that the calcHeight in layoutBlock() knows to relayout positioned objects because of
664     // a height change, we revert our height back to the intrinsic height before returning.
665     if (heightSpecified)
666         m_height = oldHeight;
667 }
668
669 void RenderFlexibleBox::layoutVerticalBox(bool relayoutChildren)
670 {
671     int xPos = borderLeft() + paddingLeft();
672     int yPos = borderTop() + paddingTop();
673     if( style()->direction() == RTL )
674         xPos = m_width - paddingRight() - borderRight();
675     int toAdd = borderBottom() + paddingBottom() + horizontalScrollbarHeight();
676     bool heightSpecified = false;
677     int oldHeight = 0;
678     
679     unsigned int highestFlexGroup = 0;
680     unsigned int lowestFlexGroup = 0;
681     bool haveFlex = false;
682     int remainingSpace = 0;
683     
684     // The first walk over our kids is to find out if we have any flexible children.
685     FlexBoxIterator iterator(this);
686     RenderObject *child = iterator.next();
687     while (child) {
688         // Check to see if this child flexes.
689         if (!child->isPositioned() && child->style()->boxFlex() > 0.0f) {
690             // We always have to lay out flexible objects again, since the flex distribution
691             // may have changed, and we need to reallocate space.
692             child->setOverrideSize(-1);
693             if (!relayoutChildren)
694                 child->setChildNeedsLayout(true, false);
695             haveFlex = true;
696             unsigned int flexGroup = child->style()->boxFlexGroup();
697             if (lowestFlexGroup == 0)
698                 lowestFlexGroup = flexGroup;
699             if (flexGroup < lowestFlexGroup)
700                 lowestFlexGroup = flexGroup;
701             if (flexGroup > highestFlexGroup)
702                 highestFlexGroup = flexGroup;
703         }
704         child = iterator.next();
705     }
706
707     // We confine the line clamp ugliness to vertical flexible boxes (thus keeping it out of
708     // mainstream block layout); this is not really part of the XUL box model.
709     bool haveLineClamp = style()->lineClamp() >= 0 && style()->lineClamp() <= 100;
710     if (haveLineClamp) {
711         int maxLineCount = 0;
712         child = iterator.first();
713         while (child) {
714             if (!child->isPositioned()) {
715                 if (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent())) ||
716                     (child->style()->height().isAuto() && child->isBlockFlow() && !child->needsLayout())) {
717                     child->setChildNeedsLayout(true, false);
718                     
719                     // Dirty all the positioned objects.
720                     static_cast<RenderBlock*>(child)->markPositionedObjectsForLayout();
721                     static_cast<RenderBlock*>(child)->clearTruncation();
722                 }
723                 child->layoutIfNeeded();
724                 if (child->style()->height().isAuto() && child->isBlockFlow())
725                     maxLineCount = max(maxLineCount, static_cast<RenderBlock*>(child)->lineCount());
726             }
727             child = iterator.next();
728         }
729         
730         // Get the # of lines and then alter all block flow children with auto height to use the
731         // specified height.
732         int numVisibleLines = int((maxLineCount+1)*style()->lineClamp()/100.0);
733         if (numVisibleLines < maxLineCount) {
734             for (child = iterator.first(); child; child = iterator.next()) {
735                 if (child->isPositioned() || !child->style()->height().isAuto() || !child->isBlockFlow())
736                     continue;
737                 
738                 RenderBlock* blockChild = static_cast<RenderBlock*>(child);
739                 int lineCount = blockChild->lineCount();
740                 if (lineCount <= numVisibleLines)
741                     continue;
742                 
743                 int newHeight = blockChild->heightForLineCount(numVisibleLines);
744                 if (newHeight == child->height())
745                     continue;
746                 
747                 child->setChildNeedsLayout(true, false);
748                 child->setOverrideSize(newHeight);
749                 m_flexingChildren = true;
750                 child->layoutIfNeeded();
751                 m_flexingChildren = false;
752                 child->setOverrideSize(-1);
753                 
754                 // FIXME: For now don't support RTL.
755                 if (style()->direction() != LTR)
756                     continue;
757                 
758                 // Get the last line
759                 RootInlineBox* lastLine = blockChild->lineAtIndex(lineCount-1);
760                 if (!lastLine)
761                     continue;
762                 
763                 // See if the last item is an anchor
764                 InlineBox* anchorBox = lastLine->lastChild();
765                 if (!anchorBox)
766                     continue;
767                 if (!anchorBox->object()->element())
768                     continue;
769                 if (!anchorBox->object()->element()->isLink())
770                     continue;
771                 
772                 RootInlineBox* lastVisibleLine = blockChild->lineAtIndex(numVisibleLines-1);
773                 if (!lastVisibleLine)
774                     continue;
775
776                 const UChar ellipsisAndSpace[2] = { horizontalEllipsis, ' ' };
777                 static AtomicString ellipsisAndSpaceStr(ellipsisAndSpace, 2);
778
779                 const Font& font = style(numVisibleLines == 1)->font();
780                 int ellipsisAndSpaceWidth = font.width(TextRun(ellipsisAndSpace, 2));
781
782                 // Get ellipsis width + " " + anchor width
783                 int totalWidth = ellipsisAndSpaceWidth + anchorBox->width();
784                 
785                 // See if this width can be accommodated on the last visible line
786                 RenderBlock* destBlock = static_cast<RenderBlock*>(lastVisibleLine->object());
787                 RenderBlock* srcBlock = static_cast<RenderBlock*>(lastLine->object());
788                 
789                 // FIXME: Directions of src/destBlock could be different from our direction and from one another.
790                 if (srcBlock->style()->direction() != LTR)
791                     continue;
792                 if (destBlock->style()->direction() != LTR)
793                     continue;
794
795                 int blockEdge = destBlock->rightOffset(lastVisibleLine->yPos());
796                 if (!lastVisibleLine->canAccommodateEllipsis(true, blockEdge, 
797                                                              lastVisibleLine->xPos() + lastVisibleLine->width(),
798                                                              totalWidth))
799                     continue;
800
801                 // Let the truncation code kick in.
802                 lastVisibleLine->placeEllipsis(ellipsisAndSpaceStr, true, blockEdge, totalWidth, anchorBox);
803                 destBlock->setHasMarkupTruncation(true);
804             }
805         }
806     }
807
808     // We do 2 passes.  The first pass is simply to lay everyone out at
809     // their preferred widths.  The second pass handles flexing the children.
810     // Our first pass is done without flexing.  We simply lay the children
811     // out within the box.
812     do {
813         m_height = borderTop() + paddingTop();
814         int minHeight = m_height + toAdd;
815         m_overflowHeight = m_height;
816
817         child = iterator.first();
818         while (child) {
819             // make sure we relayout children if we need it.
820             if (!haveLineClamp && (relayoutChildren || (child->isReplaced() && (child->style()->width().isPercent() || child->style()->height().isPercent()))))
821                 child->setChildNeedsLayout(true, false);
822     
823             if (child->isPositioned())
824             {
825                 child->containingBlock()->insertPositionedObject(child);
826                 if (child->hasStaticX()) {
827                     if (style()->direction() == LTR)
828                         child->setStaticX(borderLeft()+paddingLeft());
829                     else
830                         child->setStaticX(borderRight()+paddingRight());
831                 }
832                 if (child->hasStaticY())
833                     child->setStaticY(m_height);
834                 child = iterator.next();
835                 continue;
836             } 
837     
838             // Compute the child's vertical margins.
839             child->calcVerticalMargins();
840     
841             // Add in the child's marginTop to our height.
842             m_height += child->marginTop();
843     
844             // Now do a layout.
845             child->layoutIfNeeded();
846     
847             // We can place the child now, using our value of box-align.
848             int childX = borderLeft() + paddingLeft();
849             switch (style()->boxAlign()) {
850                 case BCENTER:
851                 case BBASELINE: // Baseline just maps to center for vertical boxes
852                     childX += child->marginLeft() + max(0, (contentWidth() - (child->width() + child->marginLeft() + child->marginRight()))/2);
853                     break;
854                 case BEND:
855                     if (style()->direction() == RTL)
856                         childX += child->marginLeft();
857                     else
858                         childX += contentWidth() - child->marginRight() - child->width();
859                     break;
860                 default: // BSTART/BSTRETCH
861                     if (style()->direction() == LTR)
862                         childX += child->marginLeft();
863                     else
864                         childX += contentWidth() - child->marginRight() - child->width();
865                     break;
866             }
867     
868             // Place the child.
869             placeChild(child, childX, m_height);
870             m_height += child->height() + child->marginBottom();
871     
872             if (child->isRenderBlock())
873                 static_cast<RenderBlock*>(child)->addVisualOverflow(static_cast<RenderBlock*>(child)->floatRect());
874
875             // See if this child has made our overflow need to grow.
876             m_overflowWidth = max(child->xPos() + child->overflowWidth(false), m_overflowWidth);
877             m_overflowLeft = min(child->xPos() + child->overflowLeft(false), m_overflowLeft);
878             
879             child = iterator.next();
880         }
881
882         yPos = m_height;
883         
884         if (!iterator.first() && hasLineIfEmpty())
885             m_height += lineHeight(true, true);
886     
887         m_height += toAdd;
888
889         // Negative margins can cause our height to shrink below our minimal height (border/padding).
890         // If this happens, ensure that the computed height is increased to the minimal height.
891         if (m_height < minHeight)
892             m_height = minHeight;
893
894         // Always make sure our overflowheight is at least our height.
895         if (m_overflowHeight < m_height)
896             m_overflowHeight = m_height;
897
898         // Now we have to calc our height, so we know how much space we have remaining.
899         oldHeight = m_height;
900         calcHeight();
901         if (oldHeight != m_height)
902             heightSpecified = true;
903
904         remainingSpace = borderTop() + paddingTop() + contentHeight() - yPos;
905         
906         if (m_flexingChildren)
907             haveFlex = false; // We're done.
908         else if (haveFlex) {
909             // We have some flexible objects.  See if we need to grow/shrink them at all.
910             if (!remainingSpace)
911                 break;
912
913             // Allocate the remaining space among the flexible objects.  If we are trying to
914             // grow, then we go from the lowest flex group to the highest flex group.  For shrinking,
915             // we go from the highest flex group to the lowest group.
916             bool expanding = remainingSpace > 0;
917             unsigned int start = expanding ? lowestFlexGroup : highestFlexGroup;
918             unsigned int end = expanding? highestFlexGroup : lowestFlexGroup;
919             for (unsigned int i = start; i <= end && remainingSpace; i++) {
920                 // Always start off by assuming the group can get all the remaining space.
921                 int groupRemainingSpace = remainingSpace;
922                 do {
923                     // Flexing consists of multiple passes, since we have to change ratios every time an object hits its max/min-width
924                     // For a given pass, we always start off by computing the totalFlex of all objects that can grow/shrink at all, and
925                     // computing the allowed growth before an object hits its min/max width (and thus
926                     // forces a totalFlex recomputation).
927                     float totalFlex = 0.0f;
928                     child = iterator.first();
929                     while (child) {
930                         if (allowedChildFlex(child, expanding, i))
931                             totalFlex += child->style()->boxFlex();
932                         child = iterator.next();
933                     }
934                     child = iterator.first();
935                     int spaceAvailableThisPass = groupRemainingSpace;
936                     while (child) {
937                         int allowedFlex = allowedChildFlex(child, expanding, i);
938                         if (allowedFlex) {
939                             int projectedFlex = (allowedFlex == INT_MAX) ? allowedFlex : (int)(allowedFlex * (totalFlex / child->style()->boxFlex()));
940                             spaceAvailableThisPass = expanding ? min(spaceAvailableThisPass, projectedFlex) : max(spaceAvailableThisPass, projectedFlex);
941                         }
942                         child = iterator.next();
943                     }
944
945                     // The flex groups may not have any flexible objects this time around. 
946                     if (!spaceAvailableThisPass || totalFlex == 0.0f) {
947                         // If we just couldn't grow/shrink any more, then it's time to transition to the next flex group.
948                         groupRemainingSpace = 0;
949                         continue;
950                     }
951             
952                     // Now distribute the space to objects.
953                     child = iterator.first();
954                     while (child && spaceAvailableThisPass && totalFlex) {
955                         if (allowedChildFlex(child, expanding, i)) {
956                             int spaceAdd = (int)(spaceAvailableThisPass * (child->style()->boxFlex()/totalFlex));
957                             if (spaceAdd) {
958                                 child->setOverrideSize(child->overrideHeight() + spaceAdd);
959                                 m_flexingChildren = true;
960                                 relayoutChildren = true;
961                             }
962
963                             spaceAvailableThisPass -= spaceAdd;
964                             remainingSpace -= spaceAdd;
965                             groupRemainingSpace -= spaceAdd;
966                             
967                             totalFlex -= child->style()->boxFlex();
968                         }
969                         child = iterator.next();
970                     }
971                 } while (groupRemainingSpace);
972             }
973
974             // We didn't find any children that could grow.
975             if (haveFlex && !m_flexingChildren)
976                 haveFlex = false;
977         }        
978     } while (haveFlex);
979
980     if (style()->boxPack() != BSTART && remainingSpace > 0) {
981         // Children must be repositioned.
982         int offset = 0;
983         if (style()->boxPack() == BJUSTIFY) {
984             // Determine the total number of children.
985             int totalChildren = 0;
986             child = iterator.first();
987             while (child) {
988                 if (child->isPositioned()) {
989                     child = iterator.next();
990                     continue;
991                 }
992                 totalChildren++;
993                 child = iterator.next();
994             }
995             
996             // Iterate over the children and space them out according to the
997             // justification level.
998             if (totalChildren > 1) {
999                 totalChildren--;
1000                 bool firstChild = true;
1001                 child = iterator.first();
1002                 while (child) {
1003                     if (child->isPositioned()) {
1004                         child = iterator.next();
1005                         continue;
1006                     }
1007                     
1008                     if (firstChild) {
1009                         firstChild = false;
1010                         child = iterator.next();
1011                         continue;
1012                     }
1013
1014                     offset += remainingSpace/totalChildren;
1015                     remainingSpace -= (remainingSpace/totalChildren);
1016                     totalChildren--;
1017                     placeChild(child, child->xPos(), child->yPos()+offset);
1018                     child = iterator.next();
1019                 }
1020             }
1021         } else {
1022             if (style()->boxPack() == BCENTER)
1023                 offset += remainingSpace/2;
1024             else // END
1025                 offset += remainingSpace;
1026             child = iterator.first();
1027             while (child) {
1028                 if (child->isPositioned()) {
1029                     child = iterator.next();
1030                     continue;
1031                 }
1032                 placeChild(child, child->xPos(), child->yPos()+offset);
1033                 child = iterator.next();
1034             }
1035         }
1036     }
1037     
1038     child = iterator.first();
1039     while (child && child->isPositioned()) {
1040         child = iterator.next();
1041     }
1042     
1043     if (child) {
1044         m_overflowTop = min(child->yPos() + child->overflowTop(false), m_overflowTop);
1045
1046         RenderObject* lastChild = child;
1047         while ((child = iterator.next())) {
1048             if (!child->isPositioned())
1049                 lastChild = child;
1050         }
1051         m_overflowHeight = max(lastChild->yPos() + lastChild->overflowHeight(false), m_overflowHeight);
1052     }
1053
1054     // So that the calcHeight in layoutBlock() knows to relayout positioned objects because of
1055     // a height change, we revert our height back to the intrinsic height before returning.
1056     if (heightSpecified)
1057         m_height = oldHeight; 
1058 }
1059
1060 void RenderFlexibleBox::placeChild(RenderObject* child, int x, int y)
1061 {
1062     IntRect oldRect(child->xPos(), child->yPos() , child->width(), child->height());
1063
1064     // Place the child.
1065     child->setPos(x, y);
1066
1067     // If the child moved, we have to repaint it as well as any floating/positioned
1068     // descendants.  An exception is if we need a layout.  In this case, we know we're going to
1069     // repaint ourselves (and the child) anyway.
1070     if (!selfNeedsLayout() && child->checkForRepaintDuringLayout())
1071         child->repaintDuringLayoutIfMoved(oldRect);
1072 }
1073
1074 int RenderFlexibleBox::allowedChildFlex(RenderObject* child, bool expanding, unsigned int group)
1075 {
1076     if (child->isPositioned() || child->style()->boxFlex() == 0.0f || child->style()->boxFlexGroup() != group)
1077         return 0;
1078                         
1079     if (expanding) {
1080         if (isHorizontal()) {
1081             // FIXME: For now just handle fixed values.
1082             int maxW = INT_MAX;
1083             int w = child->overrideWidth() - (child->borderLeft() + child->borderRight() + child->paddingLeft() + child->paddingRight());
1084             if (!child->style()->maxWidth().isUndefined() &&
1085                 child->style()->maxWidth().isFixed())
1086                 maxW = child->style()->maxWidth().value();
1087             else if (child->style()->maxWidth().type() == Intrinsic)
1088                 maxW = child->maxWidth();
1089             else if (child->style()->maxWidth().type() == MinIntrinsic)
1090                 maxW = child->minWidth();
1091             if (maxW == INT_MAX)
1092                 return maxW;
1093             return max(0, maxW - w);
1094         } else {
1095             // FIXME: For now just handle fixed values.
1096             int maxH = INT_MAX;
1097             int h = child->overrideHeight() - (child->borderTop() + child->borderBottom() + child->paddingTop() + child->paddingBottom());
1098             if (!child->style()->maxHeight().isUndefined() &&
1099                 child->style()->maxHeight().isFixed())
1100                 maxH = child->style()->maxHeight().value();
1101             if (maxH == INT_MAX)
1102                 return maxH;
1103             return max(0, maxH - h);
1104         }
1105     }
1106
1107     // FIXME: For now just handle fixed values.
1108     if (isHorizontal()) {
1109         int minW = child->minWidth();
1110         int w = child->overrideWidth() - (child->borderLeft() + child->borderRight() + child->paddingLeft() + child->paddingRight());
1111         if (child->style()->minWidth().isFixed())
1112             minW = child->style()->minWidth().value();
1113         else if (child->style()->minWidth().type() == Intrinsic)
1114             minW = child->maxWidth();
1115         else if (child->style()->minWidth().type() == MinIntrinsic)
1116             minW = child->minWidth();
1117             
1118         int allowedShrinkage = min(0, minW - w);
1119         return allowedShrinkage;
1120     } else {
1121         if (child->style()->minHeight().isFixed()) {
1122             int minH = child->style()->minHeight().value();
1123             int h = child->overrideHeight() - (child->borderLeft() + child->borderRight() + child->paddingLeft() + child->paddingRight());
1124             int allowedShrinkage = min(0, minH - h);
1125             return allowedShrinkage;
1126         }
1127     }
1128     
1129     return 0;
1130 }
1131
1132 const char *RenderFlexibleBox::renderName() const
1133 {
1134     if (isFloating())
1135         return "RenderFlexibleBox (floating)";
1136     if (isPositioned())
1137         return "RenderFlexibleBox (positioned)";
1138     if (isRelPositioned())
1139         return "RenderFlexibleBox (relative positioned)";
1140     return "RenderFlexibleBox";
1141 }
1142
1143 } // namespace WebCore