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