6abc0d049963fabb5914a6fd684394d2217c4733
[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     Length tableLogicalMinWidth = m_table->style()->logicalMinWidth();
265     if (tableLogicalMinWidth.isFixed() && tableLogicalMinWidth.isPositive()) {
266         minWidth = max<int>(minWidth, tableLogicalMinWidth.value());
267         maxWidth = max<int>(minWidth, maxWidth);
268     }
269 }
270
271 /*
272   This method takes care of colspans.
273   effWidth is the same as width for cells without colspans. If we have colspans, they get modified.
274  */
275 int AutoTableLayout::calcEffectiveLogicalWidth()
276 {
277     int maxLogicalWidth = 0;
278
279     size_t nEffCols = m_layoutStruct.size();
280     int spacingInRowDirection = m_table->hBorderSpacing();
281
282     for (size_t i = 0; i < nEffCols; ++i) {
283         m_layoutStruct[i].effectiveLogicalWidth = m_layoutStruct[i].logicalWidth;
284         m_layoutStruct[i].effectiveMinLogicalWidth = m_layoutStruct[i].minLogicalWidth;
285         m_layoutStruct[i].effectiveMaxLogicalWidth = m_layoutStruct[i].maxLogicalWidth;
286     }
287
288     for (size_t i = 0; i < m_spanCells.size(); ++i) {
289         RenderTableCell* cell = m_spanCells[i];
290         if (!cell)
291             break;
292
293         unsigned span = cell->colSpan();
294
295         Length cellLogicalWidth = cell->styleOrColLogicalWidth();
296         if (!cellLogicalWidth.isRelative() && cellLogicalWidth.isZero())
297             cellLogicalWidth = Length(); // make it Auto
298
299         unsigned effCol = m_table->colToEffCol(cell->col());
300         size_t lastCol = effCol;
301         int cellMinLogicalWidth = cell->minPreferredLogicalWidth() + spacingInRowDirection;
302         int cellMaxLogicalWidth = cell->maxPreferredLogicalWidth() + spacingInRowDirection;
303         float totalPercent = 0;
304         int spanMinLogicalWidth = 0;
305         int spanMaxLogicalWidth = 0;
306         bool allColsArePercent = true;
307         bool allColsAreFixed = true;
308         bool haveAuto = false;
309         bool spanHasEmptyCellsOnly = true;
310         int fixedWidth = 0;
311         while (lastCol < nEffCols && span > 0) {
312             Layout& columnLayout = m_layoutStruct[lastCol];
313             switch (columnLayout.logicalWidth.type()) {
314             case Percent:
315                 totalPercent += columnLayout.logicalWidth.percent();
316                 allColsAreFixed = false;
317                 break;
318             case Fixed:
319                 if (columnLayout.logicalWidth.value() > 0) {
320                     fixedWidth += columnLayout.logicalWidth.value();
321                     allColsArePercent = false;
322                     // IE resets effWidth to Auto here, but this breaks the konqueror about page and seems to be some bad
323                     // legacy behaviour anyway. mozilla doesn't do this so I decided we don't neither.
324                     break;
325                 }
326                 // fall through
327             case Auto:
328                 haveAuto = true;
329                 // fall through
330             default:
331                 // If the column is a percentage width, do not let the spanning cell overwrite the
332                 // width value.  This caused a mis-rendering on amazon.com.
333                 // Sample snippet:
334                 // <table border=2 width=100%><
335                 //   <tr><td>1</td><td colspan=2>2-3</tr>
336                 //   <tr><td>1</td><td colspan=2 width=100%>2-3</td></tr>
337                 // </table>
338                 if (!columnLayout.effectiveLogicalWidth.isPercent()) {
339                     columnLayout.effectiveLogicalWidth = Length();
340                     allColsArePercent = false;
341                 } else
342                     totalPercent += columnLayout.effectiveLogicalWidth.percent();
343                 allColsAreFixed = false;
344             }
345             if (!columnLayout.emptyCellsOnly)
346                 spanHasEmptyCellsOnly = false;
347             span -= m_table->spanOfEffCol(lastCol);
348             spanMinLogicalWidth += columnLayout.effectiveMinLogicalWidth;
349             spanMaxLogicalWidth += columnLayout.effectiveMaxLogicalWidth;
350             lastCol++;
351             cellMinLogicalWidth -= spacingInRowDirection;
352             cellMaxLogicalWidth -= spacingInRowDirection;
353         }
354
355         // adjust table max width if needed
356         if (cellLogicalWidth.isPercent()) {
357             if (totalPercent > cellLogicalWidth.percent() || allColsArePercent) {
358                 // can't satify this condition, treat as variable
359                 cellLogicalWidth = Length();
360             } else {
361                 maxLogicalWidth = max(maxLogicalWidth, static_cast<int>(max(spanMaxLogicalWidth, cellMaxLogicalWidth) * 100  / cellLogicalWidth.percent()));
362
363                 // all non percent columns in the span get percent values to sum up correctly.
364                 float percentMissing = cellLogicalWidth.percent() - totalPercent;
365                 int totalWidth = 0;
366                 for (unsigned pos = effCol; pos < lastCol; ++pos) {
367                     if (!m_layoutStruct[pos].effectiveLogicalWidth.isPercent())
368                         totalWidth += m_layoutStruct[pos].effectiveMaxLogicalWidth;
369                 }
370
371                 for (unsigned pos = effCol; pos < lastCol && totalWidth > 0; ++pos) {
372                     if (!m_layoutStruct[pos].effectiveLogicalWidth.isPercent()) {
373                         float percent = percentMissing * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / totalWidth;
374                         totalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
375                         percentMissing -= percent;
376                         if (percent > 0)
377                             m_layoutStruct[pos].effectiveLogicalWidth.setValue(Percent, percent);
378                         else
379                             m_layoutStruct[pos].effectiveLogicalWidth = Length();
380                     }
381                 }
382             }
383         }
384
385         // make sure minWidth and maxWidth of the spanning cell are honoured
386         if (cellMinLogicalWidth > spanMinLogicalWidth) {
387             if (allColsAreFixed) {
388                 for (unsigned pos = effCol; fixedWidth > 0 && pos < lastCol; ++pos) {
389                     int cellLogicalWidth = max(m_layoutStruct[pos].effectiveMinLogicalWidth, static_cast<int>(cellMinLogicalWidth * m_layoutStruct[pos].logicalWidth.value() / fixedWidth));
390                     fixedWidth -= m_layoutStruct[pos].logicalWidth.value();
391                     cellMinLogicalWidth -= cellLogicalWidth;
392                     m_layoutStruct[pos].effectiveMinLogicalWidth = cellLogicalWidth;
393                 }
394             } else if (allColsArePercent) {
395                 // In this case, we just split the colspan's min amd max widths following the percentage.
396                 int allocatedMinLogicalWidth = 0;
397                 int allocatedMaxLogicalWidth = 0;
398                 for (unsigned pos = effCol; pos < lastCol; ++pos) {
399                     ASSERT(m_layoutStruct[pos].logicalWidth.isPercent() || m_layoutStruct[pos].effectiveLogicalWidth.isPercent());
400                     // |allColsArePercent| means that either the logicalWidth *or* the effectiveLogicalWidth are percents, handle both of them here.
401                     float percent = m_layoutStruct[pos].logicalWidth.isPercent() ? m_layoutStruct[pos].logicalWidth.percent() : m_layoutStruct[pos].effectiveLogicalWidth.percent();
402                     int columnMinLogicalWidth = static_cast<int>(percent * cellMinLogicalWidth / totalPercent);
403                     int columnMaxLogicalWidth = static_cast<int>(percent * cellMaxLogicalWidth / totalPercent);
404                     m_layoutStruct[pos].effectiveMinLogicalWidth = max(m_layoutStruct[pos].effectiveMinLogicalWidth, columnMinLogicalWidth);
405                     m_layoutStruct[pos].effectiveMaxLogicalWidth = columnMaxLogicalWidth;
406                     allocatedMinLogicalWidth += columnMinLogicalWidth;
407                     allocatedMaxLogicalWidth += columnMaxLogicalWidth;
408                 }
409                 ASSERT(allocatedMinLogicalWidth <= cellMinLogicalWidth);
410                 ASSERT(allocatedMaxLogicalWidth <= cellMaxLogicalWidth);
411                 cellMinLogicalWidth -= allocatedMinLogicalWidth;
412                 cellMaxLogicalWidth -= allocatedMaxLogicalWidth;
413             } else {
414                 int remainingMaxLogicalWidth = spanMaxLogicalWidth;
415                 int remainingMinLogicalWidth = spanMinLogicalWidth;
416                 
417                 // Give min to variable first, to fixed second, and to others third.
418                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
419                     if (m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth) {
420                         int colMinLogicalWidth = max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, m_layoutStruct[pos].logicalWidth.value());
421                         fixedWidth -= m_layoutStruct[pos].logicalWidth.value();
422                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
423                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
424                         cellMinLogicalWidth -= colMinLogicalWidth;
425                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
426                     }
427                 }
428
429                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol && remainingMinLogicalWidth < cellMinLogicalWidth; ++pos) {
430                     if (!(m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth)) {
431                         int colMinLogicalWidth = max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, static_cast<int>(remainingMaxLogicalWidth ? cellMinLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / remainingMaxLogicalWidth : cellMinLogicalWidth));
432                         colMinLogicalWidth = min<int>(m_layoutStruct[pos].effectiveMinLogicalWidth + (cellMinLogicalWidth - remainingMinLogicalWidth), colMinLogicalWidth);
433                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
434                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
435                         cellMinLogicalWidth -= colMinLogicalWidth;
436                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
437                     }
438                 }
439             }
440         }
441         if (!cellLogicalWidth.isPercent()) {
442             if (cellMaxLogicalWidth > spanMaxLogicalWidth) {
443                 for (unsigned pos = effCol; spanMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
444                     int colMaxLogicalWidth = max(m_layoutStruct[pos].effectiveMaxLogicalWidth, static_cast<int>(spanMaxLogicalWidth ? cellMaxLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / spanMaxLogicalWidth : cellMaxLogicalWidth));
445                     spanMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
446                     cellMaxLogicalWidth -= colMaxLogicalWidth;
447                     m_layoutStruct[pos].effectiveMaxLogicalWidth = colMaxLogicalWidth;
448                 }
449             }
450         } else {
451             for (unsigned pos = effCol; pos < lastCol; ++pos)
452                 m_layoutStruct[pos].maxLogicalWidth = max(m_layoutStruct[pos].maxLogicalWidth, m_layoutStruct[pos].minLogicalWidth);
453         }
454         // treat span ranges consisting of empty cells only as if they had content
455         if (spanHasEmptyCellsOnly) {
456             for (unsigned pos = effCol; pos < lastCol; ++pos)
457                 m_layoutStruct[pos].emptyCellsOnly = false;
458         }
459     }
460     m_effectiveLogicalWidthDirty = false;
461
462     return min(maxLogicalWidth, INT_MAX / 2);
463 }
464
465 /* gets all cells that originate in a column and have a cellspan > 1
466    Sorts them by increasing cellspan
467 */
468 void AutoTableLayout::insertSpanCell(RenderTableCell *cell)
469 {
470     ASSERT_ARG(cell, cell && cell->colSpan() != 1);
471     if (!cell || cell->colSpan() == 1)
472         return;
473
474     unsigned size = m_spanCells.size();
475     if (!size || m_spanCells[size-1] != 0) {
476         m_spanCells.grow(size + 10);
477         for (unsigned i = 0; i < 10; i++)
478             m_spanCells[size+i] = 0;
479         size += 10;
480     }
481
482     // add them in sort. This is a slow algorithm, and a binary search or a fast sorting after collection would be better
483     unsigned pos = 0;
484     unsigned span = cell->colSpan();
485     while (pos < m_spanCells.size() && m_spanCells[pos] && span > m_spanCells[pos]->colSpan())
486         pos++;
487     memmove(m_spanCells.data()+pos+1, m_spanCells.data()+pos, (size-pos-1)*sizeof(RenderTableCell *));
488     m_spanCells[pos] = cell;
489 }
490
491
492 void AutoTableLayout::layout()
493 {
494     // table layout based on the values collected in the layout structure.
495     int tableLogicalWidth = m_table->logicalWidth() - m_table->bordersPaddingAndSpacingInRowDirection();
496     int available = tableLogicalWidth;
497     size_t nEffCols = m_table->numEffCols();
498
499     // FIXME: It is possible to be called without having properly updated our internal representation.
500     // This means that our preferred logical widths were not recomputed as expected.
501     if (nEffCols != m_layoutStruct.size()) {
502         fullRecalc();
503         // FIXME: Table layout shouldn't modify our table structure (but does due to columns and column-groups).
504         nEffCols = m_table->numEffCols();
505     }
506
507     if (m_effectiveLogicalWidthDirty)
508         calcEffectiveLogicalWidth();
509
510     bool havePercent = false;
511     int totalRelative = 0;
512     int numAuto = 0;
513     int numFixed = 0;
514     float totalAuto = 0;
515     float totalFixed = 0;
516     float totalPercent = 0;
517     int allocAuto = 0;
518     unsigned numAutoEmptyCellsOnly = 0;
519
520     // fill up every cell with its minWidth
521     for (size_t i = 0; i < nEffCols; ++i) {
522         int cellLogicalWidth = m_layoutStruct[i].effectiveMinLogicalWidth;
523         m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
524         available -= cellLogicalWidth;
525         Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
526         switch (logicalWidth.type()) {
527         case Percent:
528             havePercent = true;
529             totalPercent += logicalWidth.percent();
530             break;
531         case Relative:
532             totalRelative += logicalWidth.value();
533             break;
534         case Fixed:
535             numFixed++;
536             totalFixed += m_layoutStruct[i].effectiveMaxLogicalWidth;
537             // fall through
538             break;
539         case Auto:
540             if (m_layoutStruct[i].emptyCellsOnly)
541                 numAutoEmptyCellsOnly++;
542             else {
543                 numAuto++;
544                 totalAuto += m_layoutStruct[i].effectiveMaxLogicalWidth;
545                 allocAuto += cellLogicalWidth;
546             }
547             break;
548         default:
549             break;
550         }
551     }
552
553     // allocate width to percent cols
554     if (available > 0 && havePercent) {
555         for (size_t i = 0; i < nEffCols; ++i) {
556             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
557             if (logicalWidth.isPercent()) {
558                 int cellLogicalWidth = max<int>(m_layoutStruct[i].effectiveMinLogicalWidth, minimumValueForLength(logicalWidth, tableLogicalWidth));
559                 available += m_layoutStruct[i].computedLogicalWidth - cellLogicalWidth;
560                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
561             }
562         }
563         if (totalPercent > 100) {
564             // remove overallocated space from the last columns
565             int excess = tableLogicalWidth * (totalPercent - 100) / 100;
566             for (unsigned i = nEffCols; i; ) {
567                 --i;
568                 if (m_layoutStruct[i].effectiveLogicalWidth.isPercent()) {
569                     int cellLogicalWidth = m_layoutStruct[i].computedLogicalWidth;
570                     int reduction = min(cellLogicalWidth,  excess);
571                     // the lines below might look inconsistent, but that's the way it's handled in mozilla
572                     excess -= reduction;
573                     int newLogicalWidth = max<int>(m_layoutStruct[i].effectiveMinLogicalWidth, cellLogicalWidth - reduction);
574                     available += cellLogicalWidth - newLogicalWidth;
575                     m_layoutStruct[i].computedLogicalWidth = newLogicalWidth;
576                 }
577             }
578         }
579     }
580     
581     // then allocate width to fixed cols
582     if (available > 0) {
583         for (size_t i = 0; i < nEffCols; ++i) {
584             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
585             if (logicalWidth.isFixed() && logicalWidth.value() > m_layoutStruct[i].computedLogicalWidth) {
586                 available += m_layoutStruct[i].computedLogicalWidth - logicalWidth.value();
587                 m_layoutStruct[i].computedLogicalWidth = logicalWidth.value();
588             }
589         }
590     }
591
592     // now satisfy relative
593     if (available > 0) {
594         for (size_t i = 0; i < nEffCols; ++i) {
595             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
596             if (logicalWidth.isRelative() && logicalWidth.value() != 0) {
597                 // width=0* gets effMinWidth.
598                 int cellLogicalWidth = logicalWidth.value() * tableLogicalWidth / totalRelative;
599                 available += m_layoutStruct[i].computedLogicalWidth - cellLogicalWidth;
600                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
601             }
602         }
603     }
604
605     // now satisfy variable
606     if (available > 0 && numAuto) {
607         available += allocAuto; // this gets redistributed
608         for (size_t i = 0; i < nEffCols; ++i) {
609             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
610             if (logicalWidth.isAuto() && totalAuto && !m_layoutStruct[i].emptyCellsOnly) {
611                 int cellLogicalWidth = max<int>(m_layoutStruct[i].computedLogicalWidth, static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) / totalAuto));
612                 available -= cellLogicalWidth;
613                 totalAuto -= m_layoutStruct[i].effectiveMaxLogicalWidth;
614                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
615             }
616         }
617     }
618
619     // spread over fixed columns
620     if (available > 0 && numFixed) {
621         for (size_t i = 0; i < nEffCols; ++i) {
622             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
623             if (logicalWidth.isFixed()) {
624                 int cellLogicalWidth = static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) / totalFixed);
625                 available -= cellLogicalWidth;
626                 totalFixed -= m_layoutStruct[i].effectiveMaxLogicalWidth;
627                 m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
628             }
629         }
630     }
631
632     // spread over percent colums
633     if (available > 0 && m_hasPercent && totalPercent < 100) {
634         for (size_t i = 0; i < nEffCols; ++i) {
635             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
636             if (logicalWidth.isPercent()) {
637                 int cellLogicalWidth = available * logicalWidth.percent() / totalPercent;
638                 available -= cellLogicalWidth;
639                 totalPercent -= logicalWidth.percent();
640                 m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
641                 if (!available || !totalPercent)
642                     break;
643             }
644         }
645     }
646
647     // spread over the rest
648     if (available > 0 && nEffCols > numAutoEmptyCellsOnly) {
649         unsigned total = nEffCols - numAutoEmptyCellsOnly;
650         // still have some width to spread
651         for (unsigned i = nEffCols; i; ) {
652             --i;
653             // variable columns with empty cells only don't get any width
654             if (m_layoutStruct[i].effectiveLogicalWidth.isAuto() && m_layoutStruct[i].emptyCellsOnly)
655                 continue;
656             int cellLogicalWidth = available / total;
657             available -= cellLogicalWidth;
658             total--;
659             m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
660         }
661     }
662
663     // If we have overallocated, reduce every cell according to the difference between desired width and minwidth
664     // this seems to produce to the pixel exact results with IE. Wonder is some of this also holds for width distributing.
665     if (available < 0) {
666         // Need to reduce cells with the following prioritization:
667         // (1) Auto
668         // (2) Relative
669         // (3) Fixed
670         // (4) Percent
671         // This is basically the reverse of how we grew the cells.
672         if (available < 0) {
673             int logicalWidthBeyondMin = 0;
674             for (unsigned i = nEffCols; i; ) {
675                 --i;
676                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
677                 if (logicalWidth.isAuto())
678                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
679             }
680             
681             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
682                 --i;
683                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
684                 if (logicalWidth.isAuto()) {
685                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
686                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
687                     m_layoutStruct[i].computedLogicalWidth += reduce;
688                     available -= reduce;
689                     logicalWidthBeyondMin -= minMaxDiff;
690                     if (available >= 0)
691                         break;
692                 }
693             }
694         }
695
696         if (available < 0) {
697             int logicalWidthBeyondMin = 0;
698             for (unsigned i = nEffCols; i; ) {
699                 --i;
700                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
701                 if (logicalWidth.isRelative())
702                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
703             }
704             
705             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
706                 --i;
707                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
708                 if (logicalWidth.isRelative()) {
709                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
710                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
711                     m_layoutStruct[i].computedLogicalWidth += reduce;
712                     available -= reduce;
713                     logicalWidthBeyondMin -= minMaxDiff;
714                     if (available >= 0)
715                         break;
716                 }
717             }
718         }
719
720         if (available < 0) {
721             int logicalWidthBeyondMin = 0;
722             for (unsigned i = nEffCols; i; ) {
723                 --i;
724                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
725                 if (logicalWidth.isFixed())
726                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
727             }
728             
729             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
730                 --i;
731                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
732                 if (logicalWidth.isFixed()) {
733                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
734                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
735                     m_layoutStruct[i].computedLogicalWidth += reduce;
736                     available -= reduce;
737                     logicalWidthBeyondMin -= minMaxDiff;
738                     if (available >= 0)
739                         break;
740                 }
741             }
742         }
743
744         if (available < 0) {
745             int logicalWidthBeyondMin = 0;
746             for (unsigned i = nEffCols; i; ) {
747                 --i;
748                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
749                 if (logicalWidth.isPercent())
750                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
751             }
752             
753             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
754                 --i;
755                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
756                 if (logicalWidth.isPercent()) {
757                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
758                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
759                     m_layoutStruct[i].computedLogicalWidth += reduce;
760                     available -= reduce;
761                     logicalWidthBeyondMin -= minMaxDiff;
762                     if (available >= 0)
763                         break;
764                 }
765             }
766         }
767     }
768
769     int pos = 0;
770     for (size_t i = 0; i < nEffCols; ++i) {
771         m_table->setColumnPosition(i, pos);
772         pos += m_layoutStruct[i].computedLogicalWidth + m_table->hBorderSpacing();
773     }
774     m_table->setColumnPosition(m_table->columnPositions().size() - 1, pos);
775 }
776
777 }