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