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