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