Source/WebCore/rendering/AutoTableLayout.cpp

   1 /*
   2  * Copyright (C) 2002 Lars Knoll (knoll@kde.org)
   3  *           (C) 2002 Dirk Mueller (mueller@kde.org)
   4  * Copyright (C) 2003, 2006, 2008, 2010 Apple Inc. All rights reserved.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Library General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Library General Public License
  17  * along with this library; see the file COPYING.LIB.  If not, write to
  18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  19  * Boston, MA 02110-1301, USA.
  20  */
  21
  22 #include "config.h"
  23 #include "AutoTableLayout.h"
  24
  25 #include "RenderTable.h"
  26 #include "RenderTableCell.h"
  27 #include "RenderTableCol.h"
  28 #include "RenderTableSection.h"
  29
  30 using namespace std;
  31
  32 namespace WebCore {
  33
  34 AutoTableLayout::AutoTableLayout(RenderTable* table)
  35     : TableLayout(table)
  36     , m_hasPercent(false)
  37     , m_effectiveLogicalWidthDirty(true)
  38 {
  39 }
  40
  41 AutoTableLayout::~AutoTableLayout()
  42 {
  43 }
  44
  45 void AutoTableLayout::recalcColumn(unsigned effCol)
  46 {
  47     Layout& columnLayout = m_layoutStruct[effCol];
  48
  49     RenderTableCell* fixedContributor = 0;
  50     RenderTableCell* maxContributor = 0;
  51
  52     for (RenderObject* child = m_table->firstChild(); child; child = child->nextSibling()) {
  53         if (child->isRenderTableCol())
  54             toRenderTableCol(child)->computePreferredLogicalWidths();
  55         else if (child->isTableSection()) {
  56             RenderTableSection* section = toRenderTableSection(child);
  57             unsigned numRows = section->numRows();
  58             for (unsigned i = 0; i < numRows; i++) {
  59                 RenderTableSection::CellStruct current = section->cellAt(i, effCol);
  60                 RenderTableCell* cell = current.primaryCell();
  61
  62                 if (current.inColSpan || !cell)
  63                     continue;
  64
  65                 bool cellHasContent = cell->firstChild() || cell->style()->hasBorder() || cell->style()->hasPadding();
  66                 if (cellHasContent)
  67                     columnLayout.emptyCellsOnly = false;
  68
  69                 // A cell originates in this column. Ensure we have
  70                 // a min/max width of at least 1px for this column now.
  71                 columnLayout.minLogicalWidth = max<int>(columnLayout.minLogicalWidth, cellHasContent ? 1 : 0);
  72                 columnLayout.maxLogicalWidth = max<int>(columnLayout.maxLogicalWidth, 1);
  73
  74                 if (cell->colSpan() == 1) {
  75                     if (cell->preferredLogicalWidthsDirty())
  76                         cell->computePreferredLogicalWidths();
  77                     columnLayout.minLogicalWidth = max<int>(cell->minPreferredLogicalWidth(), columnLayout.minLogicalWidth);
  78                     if (cell->maxPreferredLogicalWidth() > columnLayout.maxLogicalWidth) {
  79                         columnLayout.maxLogicalWidth = cell->maxPreferredLogicalWidth();
  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 int cCellMaxWidth = 32760;
  87                     Length cellLogicalWidth = cell->styleOrColLogicalWidth();
  88                     if (cellLogicalWidth.value() > cCellMaxWidth)
  89                         cellLogicalWidth.setValue(cCellMaxWidth);
  90                     if (cellLogicalWidth.isNegative())
  91                         cellLogicalWidth.setValue(0);
  92                     switch (cellLogicalWidth.type()) {
  93                     case Fixed:
  94                         // ignore width=0
  95                         if (cellLogicalWidth.isPositive() && !columnLayout.logicalWidth.isPercent()) {
  96                             int logicalWidth = cell->computeBorderBoxLogicalWidth(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.value() > columnLayout.logicalWidth.value()))
 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                     default:
 121                         break;
 122                     }
 123                 } else if (!effCol || section->primaryCellAt(i, effCol - 1) != cell) {
 124                     // This spanning cell originates in this column. Insert the cell into spanning cells list.
 125                     insertSpanCell(cell);
 126                 }
 127             }
 128         }
 129     }
 130
 131     // Nav/IE weirdness
 132     if (columnLayout.logicalWidth.isFixed()) {
 133         if (m_table->document()->inQuirksMode() && columnLayout.maxLogicalWidth > columnLayout.logicalWidth.value() && fixedContributor != maxContributor) {
 134             columnLayout.logicalWidth = Length();
 135             fixedContributor = 0;
 136         }
 137     }
 138
 139     columnLayout.maxLogicalWidth = max(columnLayout.maxLogicalWidth, columnLayout.minLogicalWidth);
 140 }
 141
 142 void AutoTableLayout::fullRecalc()
 143 {
 144     m_hasPercent = false;
 145     m_effectiveLogicalWidthDirty = true;
 146
 147     unsigned nEffCols = m_table->numEffCols();
 148     m_layoutStruct.resize(nEffCols);
 149     m_layoutStruct.fill(Layout());
 150     m_spanCells.fill(0);
 151
 152     Length groupLogicalWidth;
 153     unsigned currentColumn = 0;
 154     for (RenderTableCol* column = m_table->firstColumn(); column; column = column->nextColumn()) {
 155         if (column->isTableColumnGroupWithColumnChildren())
 156             groupLogicalWidth = column->style()->logicalWidth();
 157         else {
 158             Length colLogicalWidth = column->style()->logicalWidth();
 159             if (colLogicalWidth.isAuto())
 160                 colLogicalWidth = groupLogicalWidth;
 161             if ((colLogicalWidth.isFixed() || colLogicalWidth.isPercent()) && colLogicalWidth.isZero())
 162                 colLogicalWidth = Length();
 163             unsigned effCol = m_table->colToEffCol(currentColumn);
 164             unsigned span = column->span();
 165             if (!colLogicalWidth.isAuto() && span == 1 && effCol < nEffCols && m_table->spanOfEffCol(effCol) == 1) {
 166                 m_layoutStruct[effCol].logicalWidth = colLogicalWidth;
 167                 if (colLogicalWidth.isFixed() && m_layoutStruct[effCol].maxLogicalWidth < colLogicalWidth.value())
 168                     m_layoutStruct[effCol].maxLogicalWidth = colLogicalWidth.value();
 169             }
 170             currentColumn += span;
 171         }
 172
 173         // For the last column in a column-group, we invalidate our group logical width.
 174         if (column->isTableColumn() && !column->nextSibling())
 175             groupLogicalWidth = Length();
 176     }
 177
 178     for (unsigned i = 0; i < nEffCols; i++)
 179         recalcColumn(i);
 180 }
 181
 182 // FIXME: This needs to be adapted for vertical writing modes.
 183 static bool shouldScaleColumns(RenderTable* table)
 184 {
 185     // A special case.  If this table is not fixed width and contained inside
 186     // a cell, then don't bloat the maxwidth by examining percentage growth.
 187     bool scale = true;
 188     while (table) {
 189         Length tw = table->style()->width();
 190         if ((tw.isAuto() || tw.isPercent()) && !table->isOutOfFlowPositioned()) {
 191             RenderBlock* cb = table->containingBlock();
 192             while (cb && !cb->isRenderView() && !cb->isTableCell() &&
 193                 cb->style()->width().isAuto() && !cb->isOutOfFlowPositioned())
 194                 cb = cb->containingBlock();
 195
 196             table = 0;
 197             if (cb && cb->isTableCell() &&
 198                 (cb->style()->width().isAuto() || cb->style()->width().isPercent())) {
 199                 if (tw.isPercent())
 200                     scale = false;
 201                 else {
 202                     RenderTableCell* cell = toRenderTableCell(cb);
 203                     if (cell->colSpan() > 1 || cell->table()->style()->width().isAuto())
 204                         scale = false;
 205                     else
 206                         table = cell->table();
 207                 }
 208             }
 209         }
 210         else
 211             table = 0;
 212     }
 213     return scale;
 214 }
 215
 216 void AutoTableLayout::computePreferredLogicalWidths(LayoutUnit& minWidth, LayoutUnit& maxWidth)
 217 {
 218     fullRecalc();
 219
 220     int spanMaxLogicalWidth = calcEffectiveLogicalWidth();
 221     minWidth = 0;
 222     maxWidth = 0;
 223     float maxPercent = 0;
 224     float maxNonPercent = 0;
 225     bool scaleColumns = shouldScaleColumns(m_table);
 226
 227     // We substitute 0 percent by (epsilon / percentScaleFactor) percent in two places below to avoid division by zero.
 228     // FIXME: Handle the 0% cases properly.
 229     const float epsilon = 1 / 128.0f;
 230
 231     float remainingPercent = 100;
 232     for (size_t i = 0; i < m_layoutStruct.size(); ++i) {
 233         minWidth += m_layoutStruct[i].effectiveMinLogicalWidth;
 234         maxWidth += m_layoutStruct[i].effectiveMaxLogicalWidth;
 235         if (scaleColumns) {
 236             if (m_layoutStruct[i].effectiveLogicalWidth.isPercent()) {
 237                 float percent = min(static_cast<float>(m_layoutStruct[i].effectiveLogicalWidth.percent()), remainingPercent);
 238                 float logicalWidth = static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) * 100 / max(percent, epsilon);
 239                 maxPercent = max(logicalWidth,  maxPercent);
 240                 remainingPercent -= percent;
 241             } else
 242                 maxNonPercent += m_layoutStruct[i].effectiveMaxLogicalWidth;
 243         }
 244     }
 245
 246     if (scaleColumns) {
 247         maxNonPercent = maxNonPercent * 100 / max(remainingPercent, epsilon);
 248         maxWidth = max<int>(maxWidth, static_cast<int>(min(maxNonPercent, static_cast<float>(tableMaxWidth))));
 249         maxWidth = max<int>(maxWidth, static_cast<int>(min(maxPercent, static_cast<float>(tableMaxWidth))));
 250     }
 251
 252     maxWidth = max<int>(maxWidth, spanMaxLogicalWidth);
 253
 254     int bordersPaddingAndSpacing = m_table->bordersPaddingAndSpacingInRowDirection();
 255     minWidth += bordersPaddingAndSpacing;
 256     maxWidth += bordersPaddingAndSpacing;
 257
 258     Length tableLogicalWidth = m_table->style()->logicalWidth();
 259     if (tableLogicalWidth.isFixed() && tableLogicalWidth.isPositive()) {
 260         minWidth = max<int>(minWidth, tableLogicalWidth.value());
 261         maxWidth = minWidth;
 262     } else if (!remainingPercent && maxNonPercent) {
 263         // if there was no remaining percent, maxWidth is invalid
 264         maxWidth = tableMaxWidth;
 265     }
 266
 267     Length tableLogicalMinWidth = m_table->style()->logicalMinWidth();
 268     if (tableLogicalMinWidth.isFixed() && tableLogicalMinWidth.isPositive()) {
 269         minWidth = max<int>(minWidth, tableLogicalMinWidth.value());
 270         maxWidth = max<int>(minWidth, maxWidth);
 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  */
 278 int 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         unsigned span = cell->colSpan();
 297
 298         Length cellLogicalWidth = cell->styleOrColLogicalWidth();
 299         if (!cellLogicalWidth.isRelative() && cellLogicalWidth.isZero())
 300             cellLogicalWidth = Length(); // make it Auto
 301
 302         unsigned 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, static_cast<int>(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 if (allColsArePercent) {
 398                 // In this case, we just split the colspan's min amd max widths following the percentage.
 399                 int allocatedMinLogicalWidth = 0;
 400                 float allocatedMaxLogicalWidth = 0;
 401                 for (unsigned pos = effCol; pos < lastCol; ++pos) {
 402                     ASSERT(m_layoutStruct[pos].logicalWidth.isPercent() || m_layoutStruct[pos].effectiveLogicalWidth.isPercent());
 403                     // |allColsArePercent| means that either the logicalWidth *or* the effectiveLogicalWidth are percents, handle both of them here.
 404                     float percent = m_layoutStruct[pos].logicalWidth.isPercent() ? m_layoutStruct[pos].logicalWidth.percent() : m_layoutStruct[pos].effectiveLogicalWidth.percent();
 405                     int columnMinLogicalWidth = static_cast<int>(percent * cellMinLogicalWidth / totalPercent);
 406                     float columnMaxLogicalWidth = percent * cellMaxLogicalWidth / totalPercent;
 407                     m_layoutStruct[pos].effectiveMinLogicalWidth = max(m_layoutStruct[pos].effectiveMinLogicalWidth, columnMinLogicalWidth);
 408                     m_layoutStruct[pos].effectiveMaxLogicalWidth = columnMaxLogicalWidth;
 409                     allocatedMinLogicalWidth += columnMinLogicalWidth;
 410                     allocatedMaxLogicalWidth += columnMaxLogicalWidth;
 411                 }
 412                 ASSERT(allocatedMinLogicalWidth <= cellMinLogicalWidth);
 413                 ASSERT(allocatedMaxLogicalWidth <= cellMaxLogicalWidth);
 414                 cellMinLogicalWidth -= allocatedMinLogicalWidth;
 415                 cellMaxLogicalWidth -= allocatedMaxLogicalWidth;
 416             } else {
 417                 float remainingMaxLogicalWidth = spanMaxLogicalWidth;
 418                 int remainingMinLogicalWidth = spanMinLogicalWidth;
 419
 420                 // Give min to variable first, to fixed second, and to others third.
 421                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
 422                     if (m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth) {
 423                         int colMinLogicalWidth = max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, m_layoutStruct[pos].logicalWidth.value());
 424                         fixedWidth -= m_layoutStruct[pos].logicalWidth.value();
 425                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
 426                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
 427                         cellMinLogicalWidth -= colMinLogicalWidth;
 428                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
 429                     }
 430                 }
 431
 432                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol && remainingMinLogicalWidth < cellMinLogicalWidth; ++pos) {
 433                     if (!(m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth)) {
 434                         int colMinLogicalWidth = max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, static_cast<int>(remainingMaxLogicalWidth ? cellMinLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / remainingMaxLogicalWidth : cellMinLogicalWidth));
 435                         colMinLogicalWidth = min<int>(m_layoutStruct[pos].effectiveMinLogicalWidth + (cellMinLogicalWidth - remainingMinLogicalWidth), colMinLogicalWidth);
 436                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
 437                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
 438                         cellMinLogicalWidth -= colMinLogicalWidth;
 439                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
 440                     }
 441                 }
 442             }
 443         }
 444         if (!cellLogicalWidth.isPercent()) {
 445             if (cellMaxLogicalWidth > spanMaxLogicalWidth) {
 446                 for (unsigned pos = effCol; spanMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
 447                     int colMaxLogicalWidth = max(m_layoutStruct[pos].effectiveMaxLogicalWidth, static_cast<int>(spanMaxLogicalWidth ? cellMaxLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / spanMaxLogicalWidth : cellMaxLogicalWidth));
 448                     spanMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
 449                     cellMaxLogicalWidth -= colMaxLogicalWidth;
 450                     m_layoutStruct[pos].effectiveMaxLogicalWidth = colMaxLogicalWidth;
 451                 }
 452             }
 453         } else {
 454             for (unsigned pos = effCol; pos < lastCol; ++pos)
 455                 m_layoutStruct[pos].maxLogicalWidth = max(m_layoutStruct[pos].maxLogicalWidth, m_layoutStruct[pos].minLogicalWidth);
 456         }
 457         // treat span ranges consisting of empty cells only as if they had content
 458         if (spanHasEmptyCellsOnly) {
 459             for (unsigned pos = effCol; pos < lastCol; ++pos)
 460                 m_layoutStruct[pos].emptyCellsOnly = false;
 461         }
 462     }
 463     m_effectiveLogicalWidthDirty = false;
 464
 465     return static_cast<int>(min(maxLogicalWidth, INT_MAX / 2.0f));
 466 }
 467
 468 /* gets all cells that originate in a column and have a cellspan > 1
 469    Sorts them by increasing cellspan
 470 */
 471 void AutoTableLayout::insertSpanCell(RenderTableCell *cell)
 472 {
 473     ASSERT_ARG(cell, cell && cell->colSpan() != 1);
 474     if (!cell || cell->colSpan() == 1)
 475         return;
 476
 477     unsigned size = m_spanCells.size();
 478     if (!size || m_spanCells[size-1] != 0) {
 479         m_spanCells.grow(size + 10);
 480         for (unsigned i = 0; i < 10; i++)
 481             m_spanCells[size+i] = 0;
 482         size += 10;
 483     }
 484
 485     // add them in sort. This is a slow algorithm, and a binary search or a fast sorting after collection would be better
 486     unsigned pos = 0;
 487     unsigned span = cell->colSpan();
 488     while (pos < m_spanCells.size() && m_spanCells[pos] && span > m_spanCells[pos]->colSpan())
 489         pos++;
 490     memmove(m_spanCells.data()+pos+1, m_spanCells.data()+pos, (size-pos-1)*sizeof(RenderTableCell *));
 491     m_spanCells[pos] = cell;
 492 }
 493
 494
 495 void AutoTableLayout::layout()
 496 {
 497     // table layout based on the values collected in the layout structure.
 498     int tableLogicalWidth = m_table->logicalWidth() - m_table->bordersPaddingAndSpacingInRowDirection();
 499     int available = tableLogicalWidth;
 500     size_t nEffCols = m_table->numEffCols();
 501
 502     // FIXME: It is possible to be called without having properly updated our internal representation.
 503     // This means that our preferred logical widths were not recomputed as expected.
 504     if (nEffCols != m_layoutStruct.size()) {
 505         fullRecalc();
 506         // FIXME: Table layout shouldn't modify our table structure (but does due to columns and column-groups).
 507         nEffCols = m_table->numEffCols();
 508     }
 509
 510     if (m_effectiveLogicalWidthDirty)
 511         calcEffectiveLogicalWidth();
 512
 513     bool havePercent = false;
 514     int totalRelative = 0;
 515     int numAuto = 0;
 516     int numFixed = 0;
 517     float totalAuto = 0;
 518     float totalFixed = 0;
 519     float totalPercent = 0;
 520     int allocAuto = 0;
 521     unsigned numAutoEmptyCellsOnly = 0;
 522
 523     // fill up every cell with its minWidth
 524     for (size_t i = 0; i < nEffCols; ++i) {
 525         int cellLogicalWidth = m_layoutStruct[i].effectiveMinLogicalWidth;
 526         m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
 527         available -= cellLogicalWidth;
 528         Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 529         switch (logicalWidth.type()) {
 530         case Percent:
 531             havePercent = true;
 532             totalPercent += logicalWidth.percent();
 533             break;
 534         case Relative:
 535             totalRelative += logicalWidth.value();
 536             break;
 537         case Fixed:
 538             numFixed++;
 539             totalFixed += m_layoutStruct[i].effectiveMaxLogicalWidth;
 540             // fall through
 541             break;
 542         case Auto:
 543             if (m_layoutStruct[i].emptyCellsOnly)
 544                 numAutoEmptyCellsOnly++;
 545             else {
 546                 numAuto++;
 547                 totalAuto += m_layoutStruct[i].effectiveMaxLogicalWidth;
 548                 allocAuto += cellLogicalWidth;
 549             }
 550             break;
 551         default:
 552             break;
 553         }
 554     }
 555
 556     // allocate width to percent cols
 557     if (available > 0 && havePercent) {
 558         for (size_t i = 0; i < nEffCols; ++i) {
 559             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 560             if (logicalWidth.isPercent()) {
 561                 int cellLogicalWidth = max<int>(m_layoutStruct[i].effectiveMinLogicalWidth, minimumValueForLength(logicalWidth, tableLogicalWidth));
 562                 available += m_layoutStruct[i].computedLogicalWidth - cellLogicalWidth;
 563                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
 564             }
 565         }
 566         if (totalPercent > 100) {
 567             // remove overallocated space from the last columns
 568             int excess = tableLogicalWidth * (totalPercent - 100) / 100;
 569             for (unsigned i = nEffCols; i; ) {
 570                 --i;
 571                 if (m_layoutStruct[i].effectiveLogicalWidth.isPercent()) {
 572                     int cellLogicalWidth = m_layoutStruct[i].computedLogicalWidth;
 573                     int reduction = min(cellLogicalWidth,  excess);
 574                     // the lines below might look inconsistent, but that's the way it's handled in mozilla
 575                     excess -= reduction;
 576                     int newLogicalWidth = max<int>(m_layoutStruct[i].effectiveMinLogicalWidth, cellLogicalWidth - reduction);
 577                     available += cellLogicalWidth - newLogicalWidth;
 578                     m_layoutStruct[i].computedLogicalWidth = newLogicalWidth;
 579                 }
 580             }
 581         }
 582     }
 583
 584     // then allocate width to fixed cols
 585     if (available > 0) {
 586         for (size_t i = 0; i < nEffCols; ++i) {
 587             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 588             if (logicalWidth.isFixed() && logicalWidth.value() > m_layoutStruct[i].computedLogicalWidth) {
 589                 available += m_layoutStruct[i].computedLogicalWidth - logicalWidth.value();
 590                 m_layoutStruct[i].computedLogicalWidth = logicalWidth.value();
 591             }
 592         }
 593     }
 594
 595     // now satisfy relative
 596     if (available > 0) {
 597         for (size_t i = 0; i < nEffCols; ++i) {
 598             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 599             if (logicalWidth.isRelative() && logicalWidth.value() != 0) {
 600                 // width=0* gets effMinWidth.
 601                 int cellLogicalWidth = logicalWidth.value() * tableLogicalWidth / totalRelative;
 602                 available += m_layoutStruct[i].computedLogicalWidth - cellLogicalWidth;
 603                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
 604             }
 605         }
 606     }
 607
 608     // now satisfy variable
 609     if (available > 0 && numAuto) {
 610         available += allocAuto; // this gets redistributed
 611         for (size_t i = 0; i < nEffCols; ++i) {
 612             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 613             if (logicalWidth.isAuto() && totalAuto && !m_layoutStruct[i].emptyCellsOnly) {
 614                 int cellLogicalWidth = max<int>(m_layoutStruct[i].computedLogicalWidth, static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) / totalAuto));
 615                 available -= cellLogicalWidth;
 616                 totalAuto -= m_layoutStruct[i].effectiveMaxLogicalWidth;
 617                 m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
 618             }
 619         }
 620     }
 621
 622     // spread over fixed columns
 623     if (available > 0 && numFixed) {
 624         for (size_t i = 0; i < nEffCols; ++i) {
 625             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 626             if (logicalWidth.isFixed()) {
 627                 int cellLogicalWidth = static_cast<int>(available * static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) / totalFixed);
 628                 available -= cellLogicalWidth;
 629                 totalFixed -= m_layoutStruct[i].effectiveMaxLogicalWidth;
 630                 m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
 631             }
 632         }
 633     }
 634
 635     // spread over percent colums
 636     if (available > 0 && m_hasPercent && totalPercent < 100) {
 637         for (size_t i = 0; i < nEffCols; ++i) {
 638             Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 639             if (logicalWidth.isPercent()) {
 640                 int cellLogicalWidth = available * logicalWidth.percent() / totalPercent;
 641                 available -= cellLogicalWidth;
 642                 totalPercent -= logicalWidth.percent();
 643                 m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
 644                 if (!available || !totalPercent)
 645                     break;
 646             }
 647         }
 648     }
 649
 650     // spread over the rest
 651     if (available > 0 && nEffCols > numAutoEmptyCellsOnly) {
 652         unsigned total = nEffCols - numAutoEmptyCellsOnly;
 653         // still have some width to spread
 654         for (unsigned i = nEffCols; i; ) {
 655             --i;
 656             // variable columns with empty cells only don't get any width
 657             if (m_layoutStruct[i].effectiveLogicalWidth.isAuto() && m_layoutStruct[i].emptyCellsOnly)
 658                 continue;
 659             int cellLogicalWidth = available / total;
 660             available -= cellLogicalWidth;
 661             total--;
 662             m_layoutStruct[i].computedLogicalWidth += cellLogicalWidth;
 663         }
 664     }
 665
 666     // If we have overallocated, reduce every cell according to the difference between desired width and minwidth
 667     // this seems to produce to the pixel exact results with IE. Wonder is some of this also holds for width distributing.
 668     if (available < 0) {
 669         // Need to reduce cells with the following prioritization:
 670         // (1) Auto
 671         // (2) Relative
 672         // (3) Fixed
 673         // (4) Percent
 674         // This is basically the reverse of how we grew the cells.
 675         if (available < 0) {
 676             int logicalWidthBeyondMin = 0;
 677             for (unsigned i = nEffCols; i; ) {
 678                 --i;
 679                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 680                 if (logicalWidth.isAuto())
 681                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 682             }
 683
 684             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
 685                 --i;
 686                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 687                 if (logicalWidth.isAuto()) {
 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 (unsigned i = nEffCols; i; ) {
 702                 --i;
 703                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 704                 if (logicalWidth.isRelative())
 705                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 706             }
 707
 708             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
 709                 --i;
 710                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 711                 if (logicalWidth.isRelative()) {
 712                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 713                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
 714                     m_layoutStruct[i].computedLogicalWidth += reduce;
 715                     available -= reduce;
 716                     logicalWidthBeyondMin -= minMaxDiff;
 717                     if (available >= 0)
 718                         break;
 719                 }
 720             }
 721         }
 722
 723         if (available < 0) {
 724             int logicalWidthBeyondMin = 0;
 725             for (unsigned i = nEffCols; i; ) {
 726                 --i;
 727                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 728                 if (logicalWidth.isFixed())
 729                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 730             }
 731
 732             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
 733                 --i;
 734                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 735                 if (logicalWidth.isFixed()) {
 736                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 737                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
 738                     m_layoutStruct[i].computedLogicalWidth += reduce;
 739                     available -= reduce;
 740                     logicalWidthBeyondMin -= minMaxDiff;
 741                     if (available >= 0)
 742                         break;
 743                 }
 744             }
 745         }
 746
 747         if (available < 0) {
 748             int logicalWidthBeyondMin = 0;
 749             for (unsigned i = nEffCols; i; ) {
 750                 --i;
 751                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 752                 if (logicalWidth.isPercent())
 753                     logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 754             }
 755
 756             for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
 757                 --i;
 758                 Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 759                 if (logicalWidth.isPercent()) {
 760                     int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 761                     int reduce = available * minMaxDiff / logicalWidthBeyondMin;
 762                     m_layoutStruct[i].computedLogicalWidth += reduce;
 763                     available -= reduce;
 764                     logicalWidthBeyondMin -= minMaxDiff;
 765                     if (available >= 0)
 766                         break;
 767                 }
 768             }
 769         }
 770     }
 771
 772     int pos = 0;
 773     for (size_t i = 0; i < nEffCols; ++i) {
 774         m_table->columnPositions()[i] = pos;
 775         pos += m_layoutStruct[i].computedLogicalWidth + m_table->hBorderSpacing();
 776     }
 777     m_table->columnPositions()[m_table->columnPositions().size() - 1] = pos;
 778 }
 779
 780 }