third_party/WebKit/Source/core/layout/TableLayoutAlgorithmAuto.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 "core/layout/TableLayoutAlgorithmAuto.h"
  24
  25 #include "core/layout/LayoutTable.h"
  26 #include "core/layout/LayoutTableCell.h"
  27 #include "core/layout/LayoutTableCol.h"
  28 #include "core/layout/LayoutTableSection.h"
  29 #include "core/layout/TextAutosizer.h"
  30
  31 namespace blink {
  32
  33 TableLayoutAlgorithmAuto::TableLayoutAlgorithmAuto(LayoutTable* table)
  34     : TableLayoutAlgorithm(table)
  35     , m_hasPercent(false)
  36     , m_effectiveLogicalWidthDirty(true)
  37 {
  38 }
  39
  40 TableLayoutAlgorithmAuto::~TableLayoutAlgorithmAuto()
  41 {
  42 }
  43
  44 void TableLayoutAlgorithmAuto::recalcColumn(unsigned effCol)
  45 {
  46     Layout& columnLayout = m_layoutStruct[effCol];
  47
  48     LayoutTableCell* fixedContributor = nullptr;
  49     LayoutTableCell* maxContributor = nullptr;
  50
  51     for (LayoutObject* child = m_table->children()->firstChild(); child; child = child->nextSibling()) {
  52         if (child->isLayoutTableCol()) {
  53             // LayoutTableCols don't have the concept of preferred logical width, but we need to clear their dirty bits
  54             // so that if we call setPreferredWidthsDirty(true) on a col or one of its descendants, we'll mark it's
  55             // ancestors as dirty.
  56             toLayoutTableCol(child)->clearPreferredLogicalWidthsDirtyBits();
  57         } else if (child->isTableSection()) {
  58             LayoutTableSection* section = toLayoutTableSection(child);
  59             unsigned numRows = section->numRows();
  60             for (unsigned i = 0; i < numRows; i++) {
  61                 LayoutTableSection::CellStruct current = section->cellAt(i, effCol);
  62                 LayoutTableCell* cell = current.primaryCell();
  63
  64                 if (current.inColSpan || !cell)
  65                     continue;
  66                 columnLayout.columnHasNoCells = false;
  67
  68                 if (cell->maxPreferredLogicalWidth())
  69                     columnLayout.emptyCellsOnly = false;
  70
  71                 if (cell->colSpan() == 1) {
  72                     columnLayout.minLogicalWidth = std::max<int>(cell->minPreferredLogicalWidth(), columnLayout.minLogicalWidth);
  73                     if (cell->maxPreferredLogicalWidth() > columnLayout.maxLogicalWidth) {
  74                         columnLayout.maxLogicalWidth = cell->maxPreferredLogicalWidth();
  75                         maxContributor = cell;
  76                     }
  77
  78                     // All browsers implement a size limit on the cell's max width.
  79                     // Our limit is based on KHTML's representation that used 16 bits widths.
  80                     // FIXME: Other browsers have a lower limit for the cell's max width.
  81                     const int cCellMaxWidth = 32760;
  82                     Length cellLogicalWidth = cell->styleOrColLogicalWidth();
  83                     // FIXME: calc() on tables should be handled consistently with other lengths. See bug: https://crbug.com/382725
  84                     if (cellLogicalWidth.isCalculated())
  85                         cellLogicalWidth = Length(); // Make it Auto
  86                     if (cellLogicalWidth.value() > cCellMaxWidth)
  87                         cellLogicalWidth.setValue(cCellMaxWidth);
  88                     if (cellLogicalWidth.isNegative())
  89                         cellLogicalWidth.setValue(0);
  90                     switch (cellLogicalWidth.type()) {
  91                     case Fixed:
  92                         // ignore width=0
  93                         if (cellLogicalWidth.isPositive() && !columnLayout.logicalWidth.hasPercent()) {
  94                             int logicalWidth = cell->adjustBorderBoxLogicalWidthForBoxSizing(cellLogicalWidth.value());
  95                             if (columnLayout.logicalWidth.isFixed()) {
  96                                 // Nav/IE weirdness
  97                                 if ((logicalWidth > columnLayout.logicalWidth.value())
  98                                     || ((columnLayout.logicalWidth.value() == logicalWidth) && (maxContributor == cell))) {
  99                                     columnLayout.logicalWidth.setValue(Fixed, logicalWidth);
 100                                     fixedContributor = cell;
 101                                 }
 102                             } else {
 103                                 columnLayout.logicalWidth.setValue(Fixed, logicalWidth);
 104                                 fixedContributor = cell;
 105                             }
 106                         }
 107                         break;
 108                     case Percent:
 109                         m_hasPercent = true;
 110                         // TODO(alancutter): Make this work correctly for calc lengths.
 111                         if (cellLogicalWidth.isPositive() && (!columnLayout.logicalWidth.hasPercent() || cellLogicalWidth.value() > columnLayout.logicalWidth.value()))
 112                             columnLayout.logicalWidth = cellLogicalWidth;
 113                         break;
 114                     default:
 115                         break;
 116                     }
 117                 } else if (!effCol || section->primaryCellAt(i, effCol - 1) != cell) {
 118                     // If a cell originates in this spanning column ensure we have a min/max width of at least 1px for it.
 119                     columnLayout.minLogicalWidth = std::max<int>(columnLayout.minLogicalWidth, cell->maxPreferredLogicalWidth() ? 1 : 0);
 120
 121                     // This spanning cell originates in this column. Insert the cell into spanning cells list.
 122                     insertSpanCell(cell);
 123                 }
 124             }
 125         }
 126     }
 127
 128     // Nav/IE weirdness
 129     if (columnLayout.logicalWidth.isFixed()) {
 130         if (m_table->document().inQuirksMode() && columnLayout.maxLogicalWidth > columnLayout.logicalWidth.value() && fixedContributor != maxContributor) {
 131             columnLayout.logicalWidth = Length();
 132             fixedContributor = nullptr;
 133         }
 134     }
 135
 136     columnLayout.maxLogicalWidth = std::max(columnLayout.maxLogicalWidth, columnLayout.minLogicalWidth);
 137 }
 138
 139 void TableLayoutAlgorithmAuto::fullRecalc()
 140 {
 141     m_hasPercent = false;
 142     m_effectiveLogicalWidthDirty = true;
 143
 144     unsigned nEffCols = m_table->numEffCols();
 145     m_layoutStruct.resize(nEffCols);
 146     m_layoutStruct.fill(Layout());
 147     m_spanCells.fill(0);
 148
 149     Length groupLogicalWidth;
 150     unsigned currentColumn = 0;
 151     for (LayoutTableCol* column = m_table->firstColumn(); column; column = column->nextColumn()) {
 152         if (column->isTableColumnGroupWithColumnChildren()) {
 153             groupLogicalWidth = column->style()->logicalWidth();
 154         } else {
 155             Length colLogicalWidth = column->style()->logicalWidth();
 156             // FIXME: calc() on tables should be handled consistently with other lengths. See bug: https://crbug.com/382725
 157             if (colLogicalWidth.isCalculated() || colLogicalWidth.isAuto())
 158                 colLogicalWidth = groupLogicalWidth;
 159             // TODO(alancutter): Make this work correctly for calc lengths.
 160             if ((colLogicalWidth.isFixed() || colLogicalWidth.hasPercent()) && colLogicalWidth.isZero())
 161                 colLogicalWidth = Length();
 162             unsigned effCol = m_table->colToEffCol(currentColumn);
 163             unsigned span = column->span();
 164             if (!colLogicalWidth.isAuto() && span == 1 && effCol < nEffCols && m_table->spanOfEffCol(effCol) == 1) {
 165                 m_layoutStruct[effCol].logicalWidth = colLogicalWidth;
 166                 if (colLogicalWidth.isFixed() && m_layoutStruct[effCol].maxLogicalWidth < colLogicalWidth.value())
 167                     m_layoutStruct[effCol].maxLogicalWidth = colLogicalWidth.value();
 168             }
 169             currentColumn += span;
 170         }
 171
 172         // For the last column in a column-group, we invalidate our group logical width.
 173         if (column->isTableColumn() && !column->nextSibling())
 174             groupLogicalWidth = Length();
 175     }
 176
 177     for (unsigned i = 0; i < nEffCols; i++)
 178         recalcColumn(i);
 179 }
 180
 181 // FIXME: This needs to be adapted for vertical writing modes.
 182 static bool shouldScaleColumns(LayoutTable* table)
 183 {
 184     // A special case.  If this table is not fixed width and contained inside
 185     // a cell, then don't bloat the maxwidth by examining percentage growth.
 186     bool scale = true;
 187     while (table) {
 188         Length tw = table->style()->width();
 189         if ((tw.isAuto() || tw.hasPercent()) && !table->isOutOfFlowPositioned()) {
 190             LayoutBlock* cb = table->containingBlock();
 191             while (cb && !cb->isLayoutView() && !cb->isTableCell()
 192                 && cb->style()->width().isAuto() && !cb->isOutOfFlowPositioned())
 193                 cb = cb->containingBlock();
 194
 195             table = 0;
 196             if (cb && cb->isTableCell()
 197                 && (cb->style()->width().isAuto() || cb->style()->width().hasPercent())) {
 198                 LayoutTableCell* cell = toLayoutTableCell(cb);
 199                 if (cell->colSpan() > 1 || cell->table()->style()->width().isAuto())
 200                     scale = false;
 201                 else
 202                     table = cell->table();
 203             }
 204         } else {
 205             table = 0;
 206         }
 207     }
 208     return scale;
 209 }
 210
 211 void TableLayoutAlgorithmAuto::computeIntrinsicLogicalWidths(LayoutUnit& minWidth, LayoutUnit& maxWidth)
 212 {
 213     TextAutosizer::TableLayoutScope textAutosizerTableLayoutScope(m_table);
 214
 215     fullRecalc();
 216
 217     int spanMaxLogicalWidth = calcEffectiveLogicalWidth();
 218     minWidth = 0;
 219     maxWidth = 0;
 220     float maxPercent = 0;
 221     float maxNonPercent = 0;
 222     bool scaleColumns = shouldScaleColumns(m_table);
 223
 224     // We substitute 0 percent by (epsilon / percentScaleFactor) percent in two places below to avoid division by zero.
 225     // FIXME: Handle the 0% cases properly.
 226     const float epsilon = 1 / 128.0f;
 227
 228     float remainingPercent = 100;
 229     for (size_t i = 0; i < m_layoutStruct.size(); ++i) {
 230         minWidth += m_layoutStruct[i].effectiveMinLogicalWidth;
 231         maxWidth += m_layoutStruct[i].effectiveMaxLogicalWidth;
 232         if (scaleColumns) {
 233             if (m_layoutStruct[i].effectiveLogicalWidth.hasPercent()) {
 234                 float percent = std::min(static_cast<float>(m_layoutStruct[i].effectiveLogicalWidth.percent()), remainingPercent);
 235                 float logicalWidth = static_cast<float>(m_layoutStruct[i].effectiveMaxLogicalWidth) * 100 / std::max(percent, epsilon);
 236                 maxPercent = std::max(logicalWidth,  maxPercent);
 237                 remainingPercent -= percent;
 238             } else {
 239                 maxNonPercent += m_layoutStruct[i].effectiveMaxLogicalWidth;
 240             }
 241         }
 242     }
 243
 244     if (scaleColumns) {
 245         maxNonPercent = maxNonPercent * 100 / std::max(remainingPercent, epsilon);
 246         maxWidth = std::max<int>(maxWidth, static_cast<int>(std::min(maxNonPercent, static_cast<float>(tableMaxWidth))));
 247         maxWidth = std::max<int>(maxWidth, static_cast<int>(std::min(maxPercent, static_cast<float>(tableMaxWidth))));
 248     }
 249
 250     maxWidth = std::max<int>(maxWidth, spanMaxLogicalWidth);
 251 }
 252
 253 void TableLayoutAlgorithmAuto::applyPreferredLogicalWidthQuirks(LayoutUnit& minWidth, LayoutUnit& maxWidth) const
 254 {
 255     Length tableLogicalWidth = m_table->style()->logicalWidth();
 256     if (tableLogicalWidth.isFixed() && tableLogicalWidth.isPositive()) {
 257         // |minWidth| is the result of measuring the intrinsic content's size. Keep it to
 258         // make sure we are *never* smaller than the actual content.
 259         LayoutUnit minContentWidth = minWidth;
 260         // FIXME: This line looks REALLY suspicious as it could allow the minimum
 261         // preferred logical width to be smaller than the table content. This has
 262         // to be cross-checked against other browsers.
 263         minWidth = maxWidth = std::max<int>(minWidth, tableLogicalWidth.value());
 264
 265         const Length& styleMaxLogicalWidth = m_table->style()->logicalMaxWidth();
 266         if (styleMaxLogicalWidth.isFixed() && !styleMaxLogicalWidth.isNegative()) {
 267             minWidth = std::min<int>(minWidth, styleMaxLogicalWidth.value());
 268             minWidth = std::max(minWidth, minContentWidth);
 269             maxWidth = minWidth;
 270         }
 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 TableLayoutAlgorithmAuto::calcEffectiveLogicalWidth()
 279 {
 280     int 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         LayoutTableCell* cell = m_spanCells[i];
 293         if (!cell)
 294             break;
 295
 296         unsigned span = cell->colSpan();
 297
 298         Length cellLogicalWidth = cell->styleOrColLogicalWidth();
 299         // FIXME: calc() on tables should be handled consistently with other lengths. See bug: https://crbug.com/382725
 300         if (cellLogicalWidth.isZero() || cellLogicalWidth.isCalculated())
 301             cellLogicalWidth = Length(); // Make it Auto
 302
 303         unsigned effCol = m_table->colToEffCol(cell->col());
 304         size_t lastCol = effCol;
 305         int cellMinLogicalWidth = cell->minPreferredLogicalWidth() + spacingInRowDirection;
 306         int cellMaxLogicalWidth = cell->maxPreferredLogicalWidth() + spacingInRowDirection;
 307         float totalPercent = 0;
 308         int spanMinLogicalWidth = 0;
 309         int spanMaxLogicalWidth = 0;
 310         bool allColsArePercent = true;
 311         bool allColsAreFixed = true;
 312         bool haveAuto = false;
 313         bool spanHasEmptyCellsOnly = true;
 314         int fixedWidth = 0;
 315         while (lastCol < nEffCols && span > 0) {
 316             Layout& columnLayout = m_layoutStruct[lastCol];
 317             switch (columnLayout.logicalWidth.type()) {
 318             case Percent:
 319                 totalPercent += columnLayout.logicalWidth.percent();
 320                 allColsAreFixed = false;
 321                 break;
 322             case Fixed:
 323                 if (columnLayout.logicalWidth.value() > 0) {
 324                     fixedWidth += columnLayout.logicalWidth.value();
 325                     allColsArePercent = false;
 326                     // IE resets effWidth to Auto here, but this breaks the konqueror about page and seems to be some bad
 327                     // legacy behaviour anyway. mozilla doesn't do this so I decided we don't neither.
 328                     break;
 329                 }
 330                 // fall through
 331             case Auto:
 332                 haveAuto = true;
 333                 // fall through
 334             default:
 335                 // If the column is a percentage width, do not let the spanning cell overwrite the
 336                 // width value.  This caused a mis-layout on amazon.com.
 337                 // Sample snippet:
 338                 // <table border=2 width=100%><
 339                 //   <tr><td>1</td><td colspan=2>2-3</tr>
 340                 //   <tr><td>1</td><td colspan=2 width=100%>2-3</td></tr>
 341                 // </table>
 342                 // TODO(alancutter): Make this work correctly for calc lengths.
 343                 if (!columnLayout.effectiveLogicalWidth.hasPercent()) {
 344                     columnLayout.effectiveLogicalWidth = Length();
 345                     allColsArePercent = false;
 346                 } else {
 347                     totalPercent += columnLayout.effectiveLogicalWidth.percent();
 348                 }
 349                 allColsAreFixed = false;
 350             }
 351             if (!columnLayout.emptyCellsOnly)
 352                 spanHasEmptyCellsOnly = false;
 353             span -= m_table->spanOfEffCol(lastCol);
 354             spanMinLogicalWidth += columnLayout.effectiveMinLogicalWidth;
 355             spanMaxLogicalWidth += columnLayout.effectiveMaxLogicalWidth;
 356             lastCol++;
 357             cellMinLogicalWidth -= spacingInRowDirection;
 358             cellMaxLogicalWidth -= spacingInRowDirection;
 359         }
 360
 361         // adjust table max width if needed
 362         if (cellLogicalWidth.hasPercent()) {
 363             if (totalPercent > cellLogicalWidth.percent() || allColsArePercent) {
 364                 // can't satify this condition, treat as variable
 365                 cellLogicalWidth = Length();
 366             } else {
 367                 maxLogicalWidth = std::max(maxLogicalWidth, static_cast<int>(std::max(spanMaxLogicalWidth, cellMaxLogicalWidth) * 100  / cellLogicalWidth.percent()));
 368
 369                 // all non percent columns in the span get percent values to sum up correctly.
 370                 float percentMissing = cellLogicalWidth.percent() - totalPercent;
 371                 int totalWidth = 0;
 372                 for (unsigned pos = effCol; pos < lastCol; ++pos) {
 373                     if (!m_layoutStruct[pos].effectiveLogicalWidth.hasPercent())
 374                         totalWidth += m_layoutStruct[pos].clampedEffectiveMaxLogicalWidth();
 375                 }
 376
 377                 for (unsigned pos = effCol; pos < lastCol && totalWidth > 0; ++pos) {
 378                     if (!m_layoutStruct[pos].effectiveLogicalWidth.hasPercent()) {
 379                         float percent = percentMissing * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / totalWidth;
 380                         totalWidth -= m_layoutStruct[pos].clampedEffectiveMaxLogicalWidth();
 381                         percentMissing -= percent;
 382                         if (percent > 0)
 383                             m_layoutStruct[pos].effectiveLogicalWidth.setValue(Percent, percent);
 384                         else
 385                             m_layoutStruct[pos].effectiveLogicalWidth = Length();
 386                     }
 387                 }
 388             }
 389         }
 390
 391         // make sure minWidth and maxWidth of the spanning cell are honoured
 392         if (cellMinLogicalWidth > spanMinLogicalWidth) {
 393             if (allColsAreFixed) {
 394                 for (unsigned pos = effCol; fixedWidth > 0 && pos < lastCol; ++pos) {
 395                     int cellLogicalWidth = std::max(m_layoutStruct[pos].effectiveMinLogicalWidth, static_cast<int>(cellMinLogicalWidth * m_layoutStruct[pos].logicalWidth.value() / fixedWidth));
 396                     fixedWidth -= m_layoutStruct[pos].logicalWidth.value();
 397                     cellMinLogicalWidth -= cellLogicalWidth;
 398                     m_layoutStruct[pos].effectiveMinLogicalWidth = cellLogicalWidth;
 399                 }
 400             } else if (allColsArePercent) {
 401                 // In this case, we just split the colspan's min amd max widths following the percentage.
 402                 int allocatedMinLogicalWidth = 0;
 403                 int allocatedMaxLogicalWidth = 0;
 404                 for (unsigned pos = effCol; pos < lastCol; ++pos) {
 405                     // TODO(alancutter): Make this work correctly for calc lengths.
 406                     ASSERT(m_layoutStruct[pos].logicalWidth.hasPercent() || m_layoutStruct[pos].effectiveLogicalWidth.hasPercent());
 407                     // |allColsArePercent| means that either the logicalWidth *or* the effectiveLogicalWidth are percents, handle both of them here.
 408                     float percent = m_layoutStruct[pos].logicalWidth.hasPercent() ? m_layoutStruct[pos].logicalWidth.percent() : m_layoutStruct[pos].effectiveLogicalWidth.percent();
 409                     int columnMinLogicalWidth = static_cast<int>(percent * cellMinLogicalWidth / totalPercent);
 410                     int columnMaxLogicalWidth = static_cast<int>(percent * cellMaxLogicalWidth / totalPercent);
 411                     m_layoutStruct[pos].effectiveMinLogicalWidth = std::max(m_layoutStruct[pos].effectiveMinLogicalWidth, columnMinLogicalWidth);
 412                     m_layoutStruct[pos].effectiveMaxLogicalWidth = columnMaxLogicalWidth;
 413                     allocatedMinLogicalWidth += columnMinLogicalWidth;
 414                     allocatedMaxLogicalWidth += columnMaxLogicalWidth;
 415                 }
 416                 ASSERT(allocatedMinLogicalWidth <= cellMinLogicalWidth);
 417                 ASSERT(allocatedMaxLogicalWidth <= cellMaxLogicalWidth);
 418                 cellMinLogicalWidth -= allocatedMinLogicalWidth;
 419                 cellMaxLogicalWidth -= allocatedMaxLogicalWidth;
 420             } else {
 421                 int remainingMaxLogicalWidth = spanMaxLogicalWidth;
 422                 int remainingMinLogicalWidth = spanMinLogicalWidth;
 423
 424                 // Give min to variable first, to fixed second, and to others third.
 425                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
 426                     if (m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth) {
 427                         int colMinLogicalWidth = std::max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, m_layoutStruct[pos].logicalWidth.value());
 428                         fixedWidth -= m_layoutStruct[pos].logicalWidth.value();
 429                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
 430                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
 431                         cellMinLogicalWidth -= colMinLogicalWidth;
 432                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
 433                     }
 434                 }
 435
 436                 for (unsigned pos = effCol; remainingMaxLogicalWidth >= 0 && pos < lastCol && remainingMinLogicalWidth < cellMinLogicalWidth; ++pos) {
 437                     if (!(m_layoutStruct[pos].logicalWidth.isFixed() && haveAuto && fixedWidth <= cellMinLogicalWidth)) {
 438                         int colMinLogicalWidth = std::max<int>(m_layoutStruct[pos].effectiveMinLogicalWidth, static_cast<int>(remainingMaxLogicalWidth ? cellMinLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / remainingMaxLogicalWidth : cellMinLogicalWidth));
 439                         colMinLogicalWidth = std::min<int>(m_layoutStruct[pos].effectiveMinLogicalWidth + (cellMinLogicalWidth - remainingMinLogicalWidth), colMinLogicalWidth);
 440                         remainingMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
 441                         remainingMinLogicalWidth -= m_layoutStruct[pos].effectiveMinLogicalWidth;
 442                         cellMinLogicalWidth -= colMinLogicalWidth;
 443                         m_layoutStruct[pos].effectiveMinLogicalWidth = colMinLogicalWidth;
 444                     }
 445                 }
 446             }
 447         }
 448         if (!cellLogicalWidth.hasPercent()) {
 449             if (cellMaxLogicalWidth > spanMaxLogicalWidth) {
 450                 for (unsigned pos = effCol; spanMaxLogicalWidth >= 0 && pos < lastCol; ++pos) {
 451                     int colMaxLogicalWidth = std::max(m_layoutStruct[pos].effectiveMaxLogicalWidth, static_cast<int>(spanMaxLogicalWidth ? cellMaxLogicalWidth * static_cast<float>(m_layoutStruct[pos].effectiveMaxLogicalWidth) / spanMaxLogicalWidth : cellMaxLogicalWidth));
 452                     spanMaxLogicalWidth -= m_layoutStruct[pos].effectiveMaxLogicalWidth;
 453                     cellMaxLogicalWidth -= colMaxLogicalWidth;
 454                     m_layoutStruct[pos].effectiveMaxLogicalWidth = colMaxLogicalWidth;
 455                 }
 456             }
 457         } else {
 458             for (unsigned pos = effCol; pos < lastCol; ++pos)
 459                 m_layoutStruct[pos].maxLogicalWidth = std::max(m_layoutStruct[pos].maxLogicalWidth, m_layoutStruct[pos].minLogicalWidth);
 460         }
 461         // treat span ranges consisting of empty cells only as if they had content
 462         if (spanHasEmptyCellsOnly) {
 463             for (unsigned pos = effCol; pos < lastCol; ++pos)
 464                 m_layoutStruct[pos].emptyCellsOnly = false;
 465         }
 466     }
 467     m_effectiveLogicalWidthDirty = false;
 468
 469     return std::min(maxLogicalWidth, INT_MAX / 2);
 470 }
 471
 472 /* gets all cells that originate in a column and have a cellspan > 1
 473    Sorts them by increasing cellspan
 474 */
 475 void TableLayoutAlgorithmAuto::insertSpanCell(LayoutTableCell *cell)
 476 {
 477     ASSERT_ARG(cell, cell && cell->colSpan() != 1);
 478     if (!cell || cell->colSpan() == 1)
 479         return;
 480
 481     unsigned size = m_spanCells.size();
 482     if (!size || m_spanCells[size-1] != 0) {
 483         m_spanCells.grow(size + 10);
 484         for (unsigned i = 0; i < 10; i++)
 485             m_spanCells[size+i] = 0;
 486         size += 10;
 487     }
 488
 489     // add them in sort. This is a slow algorithm, and a binary search or a fast sorting after collection would be better
 490     unsigned pos = 0;
 491     unsigned span = cell->colSpan();
 492     while (pos < m_spanCells.size() && m_spanCells[pos] && span > m_spanCells[pos]->colSpan())
 493         pos++;
 494     memmove(m_spanCells.data()+pos+1, m_spanCells.data()+pos, (size-pos-1)*sizeof(LayoutTableCell *));
 495     m_spanCells[pos] = cell;
 496 }
 497
 498
 499 void TableLayoutAlgorithmAuto::layout()
 500 {
 501     // table layout based on the values collected in the layout structure.
 502     int tableLogicalWidth = m_table->logicalWidth() - m_table->bordersPaddingAndSpacingInRowDirection();
 503     int available = tableLogicalWidth;
 504     size_t nEffCols = m_table->numEffCols();
 505
 506     // FIXME: It is possible to be called without having properly updated our internal representation.
 507     // This means that our preferred logical widths were not recomputed as expected.
 508     if (nEffCols != m_layoutStruct.size()) {
 509         fullRecalc();
 510         // FIXME: Table layout shouldn't modify our table structure (but does due to columns and column-groups).
 511         nEffCols = m_table->numEffCols();
 512     }
 513
 514     if (m_effectiveLogicalWidthDirty)
 515         calcEffectiveLogicalWidth();
 516
 517     bool havePercent = false;
 518     int numAuto = 0;
 519     int numFixed = 0;
 520     float totalAuto = 0;
 521     float totalFixed = 0;
 522     float totalPercent = 0;
 523     int allocAuto = 0;
 524     unsigned numAutoEmptyCellsOnly = 0;
 525
 526     // fill up every cell with its minWidth
 527     for (size_t i = 0; i < nEffCols; ++i) {
 528         int cellLogicalWidth = m_layoutStruct[i].effectiveMinLogicalWidth;
 529         m_layoutStruct[i].computedLogicalWidth = cellLogicalWidth;
 530         available -= cellLogicalWidth;
 531         Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 532         switch (logicalWidth.type()) {
 533         case Percent:
 534             havePercent = true;
 535             totalPercent += logicalWidth.percent();
 536             break;
 537         case Fixed:
 538             numFixed++;
 539             totalFixed += m_layoutStruct[i].clampedEffectiveMaxLogicalWidth();
 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].clampedEffectiveMaxLogicalWidth();
 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.hasPercent()) {
 561                 int cellLogicalWidth = std::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.hasPercent()) {
 572                     int cellLogicalWidth = m_layoutStruct[i].computedLogicalWidth;
 573                     int reduction = std::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 = std::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     // Give each auto width column its share of the available width, non-empty columns then empty columns.
 596     if (available > 0 && numAuto) {
 597         available += allocAuto;
 598         distributeWidthToColumns<float, Auto, NonEmptyCells, InitialWidth, StartToEnd>(available, totalAuto);
 599     }
 600     if (available > 0 && numAutoEmptyCellsOnly) {
 601         unsigned total = numAutoEmptyCellsOnly;
 602         distributeWidthToColumns<unsigned, Auto, EmptyCells, InitialWidth, StartToEnd>(available, total);
 603     }
 604
 605     // Any remaining available width expands fixed width, percent width, and non-empty auto width columns, in that order.
 606     if (available > 0 && numFixed)
 607         distributeWidthToColumns<float, Fixed, AllCells, ExtraWidth, StartToEnd>(available, totalFixed);
 608
 609     if (available > 0 && m_hasPercent && totalPercent < 100)
 610         distributeWidthToColumns<float, Percent, AllCells, ExtraWidth, StartToEnd>(available, totalPercent);
 611
 612     if (available > 0 && nEffCols > numAutoEmptyCellsOnly) {
 613         unsigned total = nEffCols - numAutoEmptyCellsOnly;
 614         // Starting from the last cell is for compatibility with FF/IE - it isn't specified anywhere.
 615         distributeWidthToColumns<unsigned, Auto, NonEmptyCells, LeftoverWidth, EndToStart>(available, total);
 616     }
 617
 618     // If we have overallocated, reduce every cell according to the difference between desired width and minwidth
 619     // this seems to produce to the pixel exact results with IE. Wonder is some of this also holds for width distributing.
 620     // This is basically the reverse of how we grew the cells.
 621     if (available < 0)
 622         shrinkColumnWidth(Auto, available);
 623     if (available < 0)
 624         shrinkColumnWidth(Fixed, available);
 625     if (available < 0)
 626         shrinkColumnWidth(Percent, available);
 627
 628     int pos = 0;
 629     for (size_t i = 0; i < nEffCols; ++i) {
 630         m_table->setColumnPosition(i, pos);
 631         pos += m_layoutStruct[i].computedLogicalWidth + m_table->hBorderSpacing();
 632     }
 633     m_table->setColumnPosition(m_table->columnPositions().size() - 1, pos);
 634 }
 635
 636 template<typename Total, LengthType lengthType, CellsToProcess cellsToProcess, DistributionMode distributionMode, DistributionDirection distributionDirection>
 637 void TableLayoutAlgorithmAuto::distributeWidthToColumns(int& available, Total total)
 638 {
 639     // TODO(alancutter): Make this work correctly for calc lengths.
 640     int nEffCols = static_cast<int>(m_table->numEffCols());
 641     bool startToEnd = distributionDirection == StartToEnd;
 642     for (int i = startToEnd ? 0 : nEffCols - 1; startToEnd ? i < nEffCols : i > -1; startToEnd ? ++i : --i) {
 643         const Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 644         if (cellsToProcess == NonEmptyCells && logicalWidth.isAuto() && m_layoutStruct[i].emptyCellsOnly)
 645             continue;
 646         // When allocating width to columns with nothing but empty cells we avoid
 647         // columns that exist only to flesh out a colspan and have no actual cells.
 648         if (cellsToProcess == EmptyCells && logicalWidth.isAuto() && (!m_layoutStruct[i].emptyCellsOnly || m_layoutStruct[i].columnHasNoCells))
 649             continue;
 650         if (distributionMode != LeftoverWidth && logicalWidth.type() != lengthType)
 651             continue;
 652
 653         float factor = 1;
 654         if (distributionMode != LeftoverWidth) {
 655             if (lengthType == Percent)
 656                 factor = logicalWidth.percent();
 657             else if (lengthType == Auto || lengthType == Fixed)
 658                 factor = m_layoutStruct[i].clampedEffectiveMaxLogicalWidth();
 659         }
 660
 661         int newWidth = available * factor / total;
 662         int cellLogicalWidth = (distributionMode == InitialWidth) ? max<int>(m_layoutStruct[i].computedLogicalWidth, newWidth) : newWidth;
 663         available -= cellLogicalWidth;
 664         total -= factor;
 665         m_layoutStruct[i].computedLogicalWidth = (distributionMode == InitialWidth) ? cellLogicalWidth : m_layoutStruct[i].computedLogicalWidth + cellLogicalWidth;
 666
 667         // If we have run out of width to allocate we're done.
 668         // TODO(rhogan): Extend this to Fixed as well.
 669         if (lengthType == Percent && (!available || !total))
 670             return;
 671         if (lengthType == Auto && !total)
 672             return;
 673     }
 674 }
 675
 676 void TableLayoutAlgorithmAuto::shrinkColumnWidth(const LengthType& lengthType, int& available)
 677 {
 678     size_t nEffCols = m_table->numEffCols();
 679     int logicalWidthBeyondMin = 0;
 680     for (unsigned i = nEffCols; i; ) {
 681         --i;
 682         Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 683         if (logicalWidth.type() == lengthType)
 684             logicalWidthBeyondMin += m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 685     }
 686
 687     for (unsigned i = nEffCols; i && logicalWidthBeyondMin > 0; ) {
 688         --i;
 689         Length& logicalWidth = m_layoutStruct[i].effectiveLogicalWidth;
 690         if (logicalWidth.type() == lengthType) {
 691             int minMaxDiff = m_layoutStruct[i].computedLogicalWidth - m_layoutStruct[i].effectiveMinLogicalWidth;
 692             int reduce = available * minMaxDiff / logicalWidthBeyondMin;
 693             m_layoutStruct[i].computedLogicalWidth += reduce;
 694             available -= reduce;
 695             logicalWidthBeyondMin -= minMaxDiff;
 696             if (available >= 0)
 697                 break;
 698         }
 699     }
 700 }
 701 }