3fb692884ca5c7d3d0202a3d596d50978c3af243
[WebKit-https.git] / Source / WebCore / rendering / AutoTableLayout.cpp
1 /*
2  * Copyright (C) 2002 Lars Knoll (knoll@kde.org)
3  *           (C) 2002 Dirk Mueller (mueller@kde.org)
4  * Copyright (C) 2003, 2006, 2008, 2010 Apple Inc. All rights reserved.
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB.  If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  */
21
22 #include "config.h"
23 #include "AutoTableLayout.h"
24
25 #include "RenderTable.h"
26 #include "RenderTableCell.h"
27 #include "RenderTableCol.h"
28 #include "RenderTableSection.h"
29
30 namespace WebCore {
31
32 AutoTableLayout::AutoTableLayout(RenderTable* table)
33     : TableLayout(table)
34     , m_hasPercent(false)
35     , m_effectiveLogicalWidthDirty(true)
36 {
37 }
38
39 AutoTableLayout::~AutoTableLayout()
40 {
41 }
42
43 void AutoTableLayout::recalcColumn(unsigned effCol)
44 {
45     Layout& columnLayout = m_layoutStruct[effCol];
46
47     RenderTableCell* fixedContributor = 0;
48     RenderTableCell* maxContributor = 0;
49
50     for (RenderObject* child = m_table->firstChild(); child; child = child->nextSibling()) {
51         if (child->isRenderTableCol()){
52             // RenderTableCols don't have the concept of preferred logical width, but we need to clear their dirty bits
53             // so that if we call setPreferredWidthsDirty(true) on a col or one of its descendants, we'll mark it's
54             // ancestors as dirty.
55             toRenderTableCol(child)->clearPreferredLogicalWidthsDirtyBits();
56         } else if (child->isTableSection()) {
57             RenderTableSection* section = toRenderTableSection(child);
58             unsigned numRows = section->numRows();
59             for (unsigned i = 0; i < numRows; i++) {
60                 RenderTableSection::CellStruct current = section->cellAt(i, effCol);
61                 RenderTableCell* cell = current.primaryCell();
62                 
63                 if (current.inColSpan || !cell)
64                     continue;
65
66                 bool cellHasContent = cell->firstChild() || cell->style().hasBorder() || cell->style().hasPadding();
67                 if (cellHasContent)
68                     columnLayout.emptyCellsOnly = false;
69
70                 // A cell originates in this column. Ensure we have
71                 // a min/max width of at least 1px for this column now.
72                 columnLayout.minLogicalWidth = std::max<int>(columnLayout.minLogicalWidth, cellHasContent ? 1 : 0);
73                 columnLayout.maxLogicalWidth = std::max<int>(columnLayout.maxLogicalWidth, 1);
74
75                 if (cell->colSpan() == 1) {
76                     columnLayout.minLogicalWidth = std::max<int>(cell->minPreferredLogicalWidth(), columnLayout.minLogicalWidth);
77                     if (cell->maxPreferredLogicalWidth() > columnLayout.maxLogicalWidth) {
78                         columnLayout.maxLogicalWidth = cell->maxPreferredLogicalWidth();
79                         maxContributor = cell;
80                     }
81
82                     // All browsers implement a size limit on the cell's max width. 
83                     // Our limit is based on KHTML's representation that used 16 bits widths.
84                     // FIXME: Other browsers have a lower limit for the cell's max width. 
85                     const int cCellMaxWidth = 32760;
86                     Length cellLogicalWidth = cell->styleOrColLogicalWidth();
87                     if (cellLogicalWidth.value() > cCellMaxWidth)
88                         cellLogicalWidth.setValue(cCellMaxWidth);
89                     if (cellLogicalWidth.isNegative())
90                         cellLogicalWidth.setValue(0);
91                     switch (cellLogicalWidth.type()) {
92                     case Fixed:
93                         // ignore width=0
94                         if (cellLogicalWidth.isPositive() && !columnLayout.logicalWidth.isPercent()) {
95                             int logicalWidth = cell->adjustBorderBoxLogicalWidthForBoxSizing(cellLogicalWidth.value());
96                             if (columnLayout.logicalWidth.isFixed()) {
97                                 // Nav/IE weirdness
98                                 if ((logicalWidth > columnLayout.logicalWidth.value()) 
99                                     || ((columnLayout.logicalWidth.value() == logicalWidth) && (maxContributor == cell))) {
100                                     columnLayout.logicalWidth.setValue(Fixed, logicalWidth);
101                                     fixedContributor = cell;
102                                 }
103                             } else {
104                                 columnLayout.logicalWidth.setValue(Fixed, logicalWidth);
105                                 fixedContributor = cell;
106                             }
107                         }
108                         break;
109                     case Percent:
110                         m_hasPercent = true;
111                         if (cellLogicalWidth.isPositive() && (!columnLayout.logicalWidth.isPercent() || cellLogicalWidth.value() > columnLayout.logicalWidth.value()))
112                             columnLayout.logicalWidth = cellLogicalWidth;
113                         break;
114                     case Relative:
115                         // FIXME: Need to understand this case and whether it makes sense to compare values
116                         // which are not necessarily of the same type.
117                         if (cellLogicalWidth.value() > columnLayout.logicalWidth.value())
118                             columnLayout.logicalWidth = cellLogicalWidth;
119                     default:
120                         break;
121                     }
122                 } else if (!effCol || section->primaryCellAt(i, effCol - 1) != cell) {
123                     // This spanning cell originates in this column. Insert the cell into spanning cells list.
124                     insertSpanCell(cell);
125                 }
126             }
127         }
128     }
129
130     // Nav/IE weirdness
131     if (columnLayout.logicalWidth.isFixed()) {
132         if (m_table->document().inQuirksMode() && columnLayout.maxLogicalWidth > columnLayout.logicalWidth.value() && fixedContributor != maxContributor) {
133             columnLayout.logicalWidth = Length();
134             fixedContributor = 0;
135         }
136     }
137
138     columnLayout.maxLogicalWidth = std::max(columnLayout.maxLogicalWidth, columnLayout.minLogicalWidth);
139 }
140
141 void AutoTableLayout::fullRecalc()
142 {
143     m_hasPercent = false;
144     m_effectiveLogicalWidthDirty = true;
145
146     unsigned nEffCols = m_table->numEffCols();
147     m_layoutStruct.resize(nEffCols);
148     m_layoutStruct.fill(Layout());
149     m_spanCells.fill(0);
150
151     Length groupLogicalWidth;
152     unsigned currentColumn = 0;
153     for (RenderTableCol* column = m_table->firstColumn(); column; column = column->nextColumn()) {
154         if (column->isTableColumnGroupWithColumnChildren())
155             groupLogicalWidth = column->style().logicalWidth();
156         else {
157             Length colLogicalWidth = column->style().logicalWidth();
158             if (colLogicalWidth.isAuto())
159                 colLogicalWidth = groupLogicalWidth;
160             if ((colLogicalWidth.isFixed() || colLogicalWidth.isPercent()) && colLogicalWidth.isZero())
161                 colLogicalWidth = Length();
162             unsigned effCol = m_table->colToEffCol(currentColumn);
163             unsigned span = column->span();
164             if (!colLogicalWidth.isAuto() && span == 1 && effCol < nEffCols && m_table->spanOfEffCol(effCol) == 1) {
165                 m_layoutStruct[effCol].logicalWidth = colLogicalWidth;
166                 if (colLogicalWidth.isFixed() && m_layoutStruct[effCol].maxLogicalWidth < colLogicalWidth.value())
167                     m_layoutStruct[effCol].maxLogicalWidth = colLogicalWidth.value();
168             }
169             currentColumn += span;
170         }
171
172         // For the last column in a column-group, we invalidate our group logical width.
173         if (column->isTableColumn() && !column->nextSibling())
174             groupLogicalWidth = Length();
175     }
176
177     for (unsigned i = 0; i < nEffCols; i++)
178         recalcColumn(i);
179 }
180
181 // FIXME: This needs to be adapted for vertical writing modes.
182 static bool shouldScaleColumns(RenderTable* table)
183 {
184     // A special case.  If this table is not fixed width and contained inside
185     // a cell, then don't bloat the maxwidth by examining percentage growth.
186     bool scale = true;
187     while (table) {
188         Length tw = table->style().width();
189         if ((tw.isAuto() || tw.isPercent()) && !table->isOutOfFlowPositioned()) {
190             RenderBlock* cb = table->containingBlock();
191             while (cb && !cb->isRenderView() && !cb->isTableCell() &&
192                 cb->style().width().isAuto() && !cb->isOutOfFlowPositioned())
193                 cb = cb->containingBlock();
194
195             table = 0;
196             if (cb && cb->isTableCell() &&
197                 (cb->style().width().isAuto() || cb->style().width().isPercent())) {
198                 RenderTableCell* cell = toRenderTableCell(cb);
199                 if (cell->colSpan() > 1 || cell->table()->style().width().isAuto())
200                     scale = false;
201                 else
202                     table = cell->table();
203             }
204         }
205         else
206             table = 0;
207     }
208     return scale;
209 }
210
211 void AutoTableLayout::computeIntrinsicLogicalWidths(LayoutUnit& minWidth, LayoutUnit& maxWidth)
212 {
213     fullRecalc();
214
215     int spanMaxLogicalWidth = calcEffectiveLogicalWidth();
216     minWidth = 0;
217     maxWidth = 0;
218     float maxPercent = 0;
219     float maxNonPercent = 0;
220     bool scaleColumns = shouldScaleColumns(m_table);
221
222     // We substitute 0 percent by (epsilon / percentScaleFactor) percent in two places below to avoid division by zero.
223     // FIXME: Handle the 0% cases properly.
224     const float epsilon = 1 / 128.0f;
225
226     float remainingPercent = 100;
227     for (size_t i = 0; i < m_layoutStruct.size(); ++i) {
228         minWidth += m_layoutStruct[i].effectiveMinLogicalWidth;
229         maxWidth += m_layoutStruct[i].effectiveMaxLogicalWidth;
230         if (scaleColumns) {
231             if (m_layoutStruct[i].effectiveLogicalWidth.isPercent()) {
232                 float percent = std::min(static_cast<float>(m_layoutStruct[i].effectiveLogicalWidth.percent()), remainingPercent);
233                 float logicalWidth = static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) * 100 / std::max(percent, epsilon);
234                 maxPercent = std::max(logicalWidth,  maxPercent);
235                 remainingPercent -= percent;
236             } else
237                 maxNonPercent += m_layoutStruct[i].effectiveMaxLogicalWidth;
238         }
239     }
240
241     if (scaleColumns) {
242         maxNonPercent = maxNonPercent * 100 / std::max(remainingPercent, epsilon);
243         maxWidth = std::max<int>(maxWidth, static_cast<int>(std::min(maxNonPercent, static_cast<float>(tableMaxWidth))));
244         maxWidth = std::max<int>(maxWidth, static_cast<int>(std::min(maxPercent, static_cast<float>(tableMaxWidth))));
245     }
246
247     maxWidth = std::max<int>(maxWidth, spanMaxLogicalWidth);
248 }
249
250 void AutoTableLayout::applyPreferredLogicalWidthQuirks(LayoutUnit& minWidth, LayoutUnit& maxWidth) const
251 {
252     Length tableLogicalWidth = m_table->style().logicalWidth();
253     if (tableLogicalWidth.isFixed() && tableLogicalWidth.isPositive())
254         minWidth = maxWidth = std::max<int>(minWidth, tableLogicalWidth.value());
255 }
256
257 /*
258   This method takes care of colspans.
259   effWidth is the same as width for cells without colspans. If we have colspans, they get modified.
260  */
261 int AutoTableLayout::calcEffectiveLogicalWidth()
262 {
263     int maxLogicalWidth = 0;
264
265     size_t nEffCols = m_layoutStruct.size();
266     int spacingInRowDirection = m_table->hBorderSpacing();
267
268     for (size_t i = 0; i < nEffCols; ++i) {
269         m_layoutStruct[i].effectiveLogicalWidth = m_layoutStruct[i].logicalWidth;
270         m_layoutStruct[i].effectiveMinLogicalWidth = m_layoutStruct[i].minLogicalWidth;
271         m_layoutStruct[i].effectiveMaxLogicalWidth = m_layoutStruct[i].maxLogicalWidth;
272     }
273
274     for (size_t i = 0; i < m_spanCells.size(); ++i) {
275         RenderTableCell* cell = m_spanCells[i];
276         if (!cell)
277             break;
278
279         unsigned span = cell->colSpan();
280
281         Length cellLogicalWidth = cell->styleOrColLogicalWidth();
282         if (!cellLogicalWidth.isRelative() && cellLogicalWidth.isZero())
283             cellLogicalWidth = Length(); // make it Auto
284
285         unsigned effCol = m_table->colToEffCol(cell->col());
286         size_t lastCol = effCol;
287         int cellMinLogicalWidth = cell->minPreferredLogicalWidth() + spacingInRowDirection;
288         int cellMaxLogicalWidth = cell->maxPreferredLogicalWidth() + spacingInRowDirection;
289         float totalPercent = 0;
290         int spanMinLogicalWidth = 0;
291         int spanMaxLogicalWidth = 0;
292         bool allColsArePercent = true;
293         bool allColsAreFixed = true;
294         bool haveAuto = false;
295         bool spanHasEmptyCellsOnly = true;
296         int fixedWidth = 0;
297         while (lastCol < nEffCols && span > 0) {
298             Layout& columnLayout = m_layoutStruct[lastCol];
299             switch (columnLayout.logicalWidth.type()) {
300             case Percent:
301                 totalPercent += columnLayout.logicalWidth.percent();
302                 allColsAreFixed = false;
303                 break;
304             case Fixed:
305                 if (columnLayout.logicalWidth.value() > 0) {
306                     fixedWidth += columnLayout.logicalWidth.value();
307                     allColsArePercent = false;
308                     // IE resets effWidth to Auto here, but this breaks the konqueror about page and seems to be some bad
309                     // legacy behaviour anyway. mozilla doesn't do this so I decided we don't neither.
310                     break;
311                 }
312                 // fall through
313             case Auto:
314                 haveAuto = true;
315                 // fall through
316             default:
317                 // If the column is a percentage width, do not let the spanning cell overwrite the
318                 // width value.  This caused a mis-rendering on amazon.com.
319                 // Sample snippet:
320                 // <table border=2 width=100%><
321                 //   <tr><td>1</td><td colspan=2>2-3</tr>
322                 //   <tr><td>1</td><td colspan=2 width=100%>2-3</td></tr>
323                 // </table>
324                 if (!columnLayout.effectiveLogicalWidth.isPercent()) {
325                     columnLayout.effectiveLogicalWidth = Length();
326                     allColsArePercent = false;
327                 } else
328                     totalPercent += columnLayout.effectiveLogicalWidth.percent();
329                 allColsAreFixed = false;
330             }
331             if (!columnLayout.emptyCellsOnly)
332                 spanHasEmptyCellsOnly = false;
333             span -= m_table->spanOfEffCol(lastCol);
334             spanMinLogicalWidth += columnLayout.effectiveMinLogicalWidth;
335             spanMaxLogicalWidth += columnLayout.effectiveMaxLogicalWidth;
336             lastCol++;
337             cellMinLogicalWidth -= spacingInRowDirection;
338             cellMaxLogicalWidth -= spacingInRowDirection;
339         }
340
341         // adjust table max width if needed
342         if (cellLogicalWidth.isPercent()) {
343             if (totalPercent > cellLogicalWidth.percent() || allColsArePercent) {
344                 // can't satify this condition, treat as variable
345                 cellLogicalWidth = Length();
346             } else {
347                 maxLogicalWidth = std::max(maxLogicalWidth, static_cast<int>(std::max(spanMaxLogicalWidth, cellMaxLogicalWidth) * 100  / cellLogicalWidth.percent()));
348
349                 // all non percent columns in the span get percent values to sum up correctly.
350                 float percentMissing = cellLogicalWidth.percent() - totalPercent;
351                 int totalWidth = 0;
352                 for (unsigned pos = effCol; pos < lastCol; ++pos) {
353                     if (!m_layoutStruct[pos].effectiveLogicalWidth.isPercent())
354                         totalWidth += m_layoutStruct[pos].effectiveMaxLogicalWidth;
355                 }
356
357                 for (unsigned pos = effCol; pos < lastCol && totalWidth > 0; ++pos) {
358                     if (!m_layoutStruct[pos].effectiveLogicalWidth.isPercent()) {
359                         float percent = percentMissing * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / totalWidth;
360                         totalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
361                         percentMissing -= percent;
362                         if (percent > 0)
363                             m_layoutStruct[pos].effectiveLogicalWidth.setValue(Percent, percent);
364                         else
365                             m_layoutStruct[pos].effectiveLogicalWidth = Length();
366                     }
367                 }
368             }
369         }
370
371         // make sure minWidth and maxWidth of the spanning cell are honoured
372         if (cellMinLogicalWidth > spanMinLogicalWidth) {
373             if (allColsAreFixed) {
374                 for (unsigned pos = effCol; fixedWidth > 0 && pos < lastCol; ++pos) {
375                     int cellLogicalWidth = std::max(m_layoutStruct[pos].effectiveMinLogicalWidth, static_cast<int>(cellMinLogicalWidth * m_layoutStruct[pos].logicalWidth.value() / fixedWidth));
376                     fixedWidth -= m_layoutStruct[pos].logicalWidth.value();
377                     cellMinLogicalWidth -= cellLogicalWidth;
378                     m_layoutStruct[pos].effectiveMinLogicalWidth = cellLogicalWidth;
379                 }
380             } else if (allColsArePercent) {
381                 // In this case, we just split the colspan's min amd max widths following the percentage.
382                 int allocatedMinLogicalWidth = 0;
383                 int allocatedMaxLogicalWidth = 0;
384                 for (unsigned pos = effCol; pos < lastCol; ++pos) {
385                     ASSERT(m_layoutStruct[pos].logicalWidth.isPercent() || m_layoutStruct[pos].effectiveLogicalWidth.isPercent());
386                     // |allColsArePercent| means that either the logicalWidth *or* the effectiveLogicalWidth are percents, handle both of them here.
387                     float percent = m_layoutStruct[pos].logicalWidth.isPercent() ? m_layoutStruct[pos].logicalWidth.percent() : m_layoutStruct[pos].effectiveLogicalWidth.percent();
388                     int columnMinLogicalWidth = static_cast<int>(percent * cellMinLogicalWidth / totalPercent);
389                     int columnMaxLogicalWidth = static_cast<int>(percent * cellMaxLogicalWidth / totalPercent);
390                     m_layoutStruct[pos].effectiveMinLogicalWidth = std::max(m_layoutStruct[pos].effectiveMinLogicalWidth, columnMinLogicalWidth);
391                     m_layoutStruct[pos].effectiveMaxLogicalWidth = columnMaxLogicalWidth;
392                     allocatedMinLogicalWidth += columnMinLogicalWidth;
393                     allocatedMaxLogicalWidth += columnMaxLogicalWidth;
394                 }
395                 ASSERT(allocatedMinLogicalWidth <= cellMinLogicalWidth);
396                 ASSERT(allocatedMaxLogicalWidth <= cellMaxLogicalWidth);
397                 cellMinLogicalWidth -= allocatedMinLogicalWidth;
398                 cellMaxLogicalWidth -= allocatedMaxLogicalWidth;
399             } else {
400                 int remainingMaxLogicalWidth = spanMaxLogicalWidth;
401                 int remainingMinLogicalWidth = spanMinLogicalWidth;
402                 
403                 // Give min to variable first, to fixed second, and to others third.
404                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
405                     if (m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth) {
406                         int colMinLogicalWidth = std::max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, m_layoutStruct[pos].logicalWidth.value());
407                         fixedWidth -= m_layoutStruct[pos].logicalWidth.value();
408                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
409                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
410                         cellMinLogicalWidth -= colMinLogicalWidth;
411                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
412                     }
413                 }
414
415                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol && remainingMinLogicalWidth < cellMinLogicalWidth; ++pos) {
416                     if (!(m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth)) {
417                         int colMinLogicalWidth = std::max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, static_cast<int>(remainingMaxLogicalWidth ? cellMinLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / remainingMaxLogicalWidth : cellMinLogicalWidth));
418                         colMinLogicalWidth = std::min<int>(m_layoutStruct[pos].effectiveMinLogicalWidth + (cellMinLogicalWidth - remainingMinLogicalWidth), colMinLogicalWidth);
419                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
420                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
421                         cellMinLogicalWidth -= colMinLogicalWidth;
422                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
423                     }
424                 }
425             }
426         }
427         if (!cellLogicalWidth.isPercent()) {
428             if (cellMaxLogicalWidth > spanMaxLogicalWidth) {
429                 for (unsigned pos = effCol; spanMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
430                     int colMaxLogicalWidth = std::max(m_layoutStruct[pos].effectiveMaxLogicalWidth, static_cast<int>(spanMaxLogicalWidth ? cellMaxLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / spanMaxLogicalWidth : cellMaxLogicalWidth));
431                     spanMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
432                     cellMaxLogicalWidth -= colMaxLogicalWidth;
433                     m_layoutStruct[pos].effectiveMaxLogicalWidth = colMaxLogicalWidth;
434                 }
435             }
436         } else {
437             for (unsigned pos = effCol; pos < lastCol; ++pos)
438                 m_layoutStruct[pos].maxLogicalWidth = std::max(m_layoutStruct[pos].maxLogicalWidth, m_layoutStruct[pos].minLogicalWidth);
439         }
440         // treat span ranges consisting of empty cells only as if they had content
441         if (spanHasEmptyCellsOnly) {
442             for (unsigned pos = effCol; pos < lastCol; ++pos)
443                 m_layoutStruct[pos].emptyCellsOnly = false;
444         }
445     }
446     m_effectiveLogicalWidthDirty = false;
447
448     return std::min(maxLogicalWidth, INT_MAX / 2);
449 }
450
451 /* gets all cells that originate in a column and have a cellspan > 1
452    Sorts them by increasing cellspan
453 */
454 void AutoTableLayout::insertSpanCell(RenderTableCell *cell)
455 {
456     ASSERT_ARG(cell, cell && cell->colSpan() != 1);
457     if (!cell || cell->colSpan() == 1)
458         return;
459
460     unsigned size = m_spanCells.size();
461     if (!size || m_spanCells[size-1] != 0) {
462         m_spanCells.grow(size + 10);
463         for (unsigned i = 0; i < 10; i++)
464             m_spanCells[size+i] = 0;
465         size += 10;
466     }
467
468     // add them in sort. This is a slow algorithm, and a binary search or a fast sorting after collection would be better
469     unsigned pos = 0;
470     unsigned span = cell->colSpan();
471     while (pos < m_spanCells.size() && m_spanCells[pos] && span > m_spanCells[pos]->colSpan())
472         pos++;
473     memmove(m_spanCells.data()+pos+1, m_spanCells.data()+pos, (size-pos-1)*sizeof(RenderTableCell *));
474     m_spanCells[pos] = cell;
475 }
476
477
478 void AutoTableLayout::layout()
479 {
480     // table layout based on the values collected in the layout structure.
481     int tableLogicalWidth = m_table->logicalWidth() - m_table->bordersPaddingAndSpacingInRowDirection();
482     int available = tableLogicalWidth;
483     size_t nEffCols = m_table->numEffCols();
484
485     // FIXME: It is possible to be called without having properly updated our internal representation.
486     // This means that our preferred logical widths were not recomputed as expected.
487     if (nEffCols != m_layoutStruct.size()) {
488         fullRecalc();
489         // FIXME: Table layout shouldn't modify our table structure (but does due to columns and column-groups).
490         nEffCols = m_table->numEffCols();
491     }
492
493     if (m_effectiveLogicalWidthDirty)
494         calcEffectiveLogicalWidth();
495
496     bool havePercent = false;
497     int totalRelative = 0;
498     int numAuto = 0;
499     int numFixed = 0;
500     float totalAuto = 0;
501     float totalFixed = 0;
502     float totalPercent = 0;
503     int allocAuto = 0;
504     unsigned numAutoEmptyCellsOnly = 0;
505
506     // fill up every cell with its minWidth
507     for (size_t i = 0; i < nEffCols; ++i) {
508         int cellLogicalWidth = m_layoutStruct[i].effectiveMinLogicalWidth;
509         m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
510         available -= cellLogicalWidth;
511         Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
512         switch (logicalWidth.type()) {
513         case Percent:
514             havePercent = true;
515             totalPercent += logicalWidth.percent();
516             break;
517         case Relative:
518             totalRelative += logicalWidth.value();
519             break;
520         case Fixed:
521             numFixed++;
522             totalFixed += m_layoutStruct[i].effectiveMaxLogicalWidth;
523             // fall through
524             break;
525         case Auto:
526             if (m_layoutStruct[i].emptyCellsOnly)
527                 numAutoEmptyCellsOnly++;
528             else {
529                 numAuto++;
530                 totalAuto += m_layoutStruct[i].effectiveMaxLogicalWidth;
531                 allocAuto += cellLogicalWidth;
532             }
533             break;
534         default:
535             break;
536         }
537     }
538
539     // allocate width to percent cols
540     if (available > 0 && havePercent) {
541         for (size_t i = 0; i < nEffCols; ++i) {
542             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
543             if (logicalWidth.isPercent()) {
544                 int cellLogicalWidth = std::max<int>(m_layoutStruct[i].effectiveMinLogicalWidth, minimumValueForLength(logicalWidth, tableLogicalWidth));
545                 available += m_layoutStruct[i].computedLogicalWidth - cellLogicalWidth;
546                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
547             }
548         }
549         if (totalPercent > 100) {
550             // remove overallocated space from the last columns
551             int excess = tableLogicalWidth * (totalPercent - 100) / 100;
552             for (unsigned i = nEffCols; i; ) {
553                 --i;
554                 if (m_layoutStruct[i].effectiveLogicalWidth.isPercent()) {
555                     int cellLogicalWidth = m_layoutStruct[i].computedLogicalWidth;
556                     int reduction = std::min(cellLogicalWidth,  excess);
557                     // the lines below might look inconsistent, but that's the way it's handled in mozilla
558                     excess -= reduction;
559                     int newLogicalWidth = std::max<int>(m_layoutStruct[i].effectiveMinLogicalWidth, cellLogicalWidth - reduction);
560                     available += cellLogicalWidth - newLogicalWidth;
561                     m_layoutStruct[i].computedLogicalWidth = newLogicalWidth;
562                 }
563             }
564         }
565     }
566     
567     // then allocate width to fixed cols
568     if (available > 0) {
569         for (size_t i = 0; i < nEffCols; ++i) {
570             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
571             if (logicalWidth.isFixed() && logicalWidth.value() > m_layoutStruct[i].computedLogicalWidth) {
572                 available += m_layoutStruct[i].computedLogicalWidth - logicalWidth.value();
573                 m_layoutStruct[i].computedLogicalWidth = logicalWidth.value();
574             }
575         }
576     }
577
578     // now satisfy relative
579     if (available > 0) {
580         for (size_t i = 0; i < nEffCols; ++i) {
581             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
582             if (logicalWidth.isRelative() && logicalWidth.value() != 0) {
583                 // width=0* gets effMinWidth.
584                 int cellLogicalWidth = logicalWidth.value() * tableLogicalWidth / totalRelative;
585                 available += m_layoutStruct[i].computedLogicalWidth - cellLogicalWidth;
586                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
587             }
588         }
589     }
590
591     // now satisfy variable
592     if (available > 0 && numAuto) {
593         available += allocAuto; // this gets redistributed
594         for (size_t i = 0; i < nEffCols; ++i) {
595             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
596             if (logicalWidth.isAuto() && totalAuto && !m_layoutStruct[i].emptyCellsOnly) {
597                 int cellLogicalWidth = std::max<int>(m_layoutStruct[i].computedLogicalWidth, static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) / totalAuto));
598                 available -= cellLogicalWidth;
599                 totalAuto -= m_layoutStruct[i].effectiveMaxLogicalWidth;
600                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
601             }
602         }
603     }
604
605     // spread over fixed columns
606     if (available > 0 && numFixed) {
607         for (size_t i = 0; i < nEffCols; ++i) {
608             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
609             if (logicalWidth.isFixed()) {
610                 int cellLogicalWidth = static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) / totalFixed);
611                 available -= cellLogicalWidth;
612                 totalFixed -= m_layoutStruct[i].effectiveMaxLogicalWidth;
613                 m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
614             }
615         }
616     }
617
618     // spread over percent colums
619     if (available > 0 && m_hasPercent && totalPercent < 100) {
620         for (size_t i = 0; i < nEffCols; ++i) {
621             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
622             if (logicalWidth.isPercent()) {
623                 int cellLogicalWidth = available * logicalWidth.percent() / totalPercent;
624                 available -= cellLogicalWidth;
625                 totalPercent -= logicalWidth.percent();
626                 m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
627                 if (!available || !totalPercent)
628                     break;
629             }
630         }
631     }
632
633     // spread over the rest
634     if (available > 0 && nEffCols > numAutoEmptyCellsOnly) {
635         unsigned total = nEffCols - numAutoEmptyCellsOnly;
636         // still have some width to spread
637         for (unsigned i = nEffCols; i; ) {
638             --i;
639             // variable columns with empty cells only don't get any width
640             if (m_layoutStruct[i].effectiveLogicalWidth.isAuto() && m_layoutStruct[i].emptyCellsOnly)
641                 continue;
642             int cellLogicalWidth = available / total;
643             available -= cellLogicalWidth;
644             total--;
645             m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
646         }
647     }
648
649     // If we have overallocated, reduce every cell according to the difference between desired width and minwidth
650     // this seems to produce to the pixel exact results with IE. Wonder is some of this also holds for width distributing.
651     if (available < 0) {
652         // Need to reduce cells with the following prioritization:
653         // (1) Auto
654         // (2) Relative
655         // (3) Fixed
656         // (4) Percent
657         // This is basically the reverse of how we grew the cells.
658         if (available < 0) {
659             int logicalWidthBeyondMin = 0;
660             for (unsigned i = nEffCols; i; ) {
661                 --i;
662                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
663                 if (logicalWidth.isAuto())
664                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
665             }
666             
667             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
668                 --i;
669                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
670                 if (logicalWidth.isAuto()) {
671                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
672                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
673                     m_layoutStruct[i].computedLogicalWidth += reduce;
674                     available -= reduce;
675                     logicalWidthBeyondMin -= minMaxDiff;
676                     if (available >= 0)
677                         break;
678                 }
679             }
680         }
681
682         if (available < 0) {
683             int logicalWidthBeyondMin = 0;
684             for (unsigned i = nEffCols; i; ) {
685                 --i;
686                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
687                 if (logicalWidth.isRelative())
688                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
689             }
690             
691             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
692                 --i;
693                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
694                 if (logicalWidth.isRelative()) {
695                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
696                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
697                     m_layoutStruct[i].computedLogicalWidth += reduce;
698                     available -= reduce;
699                     logicalWidthBeyondMin -= minMaxDiff;
700                     if (available >= 0)
701                         break;
702                 }
703             }
704         }
705
706         if (available < 0) {
707             int logicalWidthBeyondMin = 0;
708             for (unsigned i = nEffCols; i; ) {
709                 --i;
710                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
711                 if (logicalWidth.isFixed())
712                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
713             }
714             
715             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
716                 --i;
717                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
718                 if (logicalWidth.isFixed()) {
719                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
720                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
721                     m_layoutStruct[i].computedLogicalWidth += reduce;
722                     available -= reduce;
723                     logicalWidthBeyondMin -= minMaxDiff;
724                     if (available >= 0)
725                         break;
726                 }
727             }
728         }
729
730         if (available < 0) {
731             int logicalWidthBeyondMin = 0;
732             for (unsigned i = nEffCols; i; ) {
733                 --i;
734                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
735                 if (logicalWidth.isPercent())
736                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
737             }
738             
739             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
740                 --i;
741                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
742                 if (logicalWidth.isPercent()) {
743                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
744                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
745                     m_layoutStruct[i].computedLogicalWidth += reduce;
746                     available -= reduce;
747                     logicalWidthBeyondMin -= minMaxDiff;
748                     if (available >= 0)
749                         break;
750                 }
751             }
752         }
753     }
754
755     int pos = 0;
756     for (size_t i = 0; i < nEffCols; ++i) {
757         m_table->setColumnPosition(i, pos);
758         pos += m_layoutStruct[i].computedLogicalWidth + m_table->hBorderSpacing();
759     }
760     m_table->setColumnPosition(m_table->columnPositions().size() - 1, pos);
761 }
762
763 }