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