1 /* 2 * Copyright (C) 2011 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 #include "core/rendering/RenderGrid.h" 28 29 #include "core/rendering/FastTextAutosizer.h" 30 #include "core/rendering/LayoutRepainter.h" 31 #include "core/rendering/RenderLayer.h" 32 #include "core/rendering/RenderView.h" 33 #include "core/rendering/style/GridCoordinate.h" 34 #include "platform/LengthFunctions.h" 35 36 namespace WebCore { 37 38 static const int infinity = -1; 39 40 class GridTrack { 41 public: 42 GridTrack() 43 : m_usedBreadth(0) 44 , m_maxBreadth(0) 45 { 46 } 47 48 void growUsedBreadth(LayoutUnit growth) 49 { 50 ASSERT(growth >= 0); 51 m_usedBreadth += growth; 52 } 53 LayoutUnit usedBreadth() const { return m_usedBreadth; } 54 55 void growMaxBreadth(LayoutUnit growth) 56 { 57 if (m_maxBreadth == infinity) 58 m_maxBreadth = m_usedBreadth + growth; 59 else 60 m_maxBreadth += growth; 61 } 62 LayoutUnit maxBreadthIfNotInfinite() const 63 { 64 return (m_maxBreadth == infinity) ? m_usedBreadth : m_maxBreadth; 65 } 66 67 LayoutUnit m_usedBreadth; 68 LayoutUnit m_maxBreadth; 69 }; 70 71 struct GridTrackForNormalization { 72 GridTrackForNormalization(const GridTrack& track, double flex) 73 : m_track(&track) 74 , m_flex(flex) 75 , m_normalizedFlexValue(track.m_usedBreadth / flex) 76 { 77 } 78 79 // Required by std::sort. 80 GridTrackForNormalization& operator=(const GridTrackForNormalization& o) 81 { 82 m_track = o.m_track; 83 m_flex = o.m_flex; 84 m_normalizedFlexValue = o.m_normalizedFlexValue; 85 return *this; 86 } 87 88 const GridTrack* m_track; 89 double m_flex; 90 LayoutUnit m_normalizedFlexValue; 91 }; 92 93 class RenderGrid::GridIterator { 94 WTF_MAKE_NONCOPYABLE(GridIterator); 95 public: 96 // |direction| is the direction that is fixed to |fixedTrackIndex| so e.g 97 // GridIterator(m_grid, ForColumns, 1) will walk over the rows of the 2nd column. 98 GridIterator(const GridRepresentation& grid, GridTrackSizingDirection direction, size_t fixedTrackIndex) 99 : m_grid(grid) 100 , m_direction(direction) 101 , m_rowIndex((direction == ForColumns) ? 0 : fixedTrackIndex) 102 , m_columnIndex((direction == ForColumns) ? fixedTrackIndex : 0) 103 , m_childIndex(0) 104 { 105 ASSERT(m_rowIndex < m_grid.size()); 106 ASSERT(m_columnIndex < m_grid[0].size()); 107 } 108 109 RenderBox* nextGridItem() 110 { 111 ASSERT(!m_grid.isEmpty()); 112 113 size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex; 114 const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size(); 115 for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) { 116 const GridCell& children = m_grid[m_rowIndex][m_columnIndex]; 117 if (m_childIndex < children.size()) 118 return children[m_childIndex++]; 119 120 m_childIndex = 0; 121 } 122 return 0; 123 } 124 125 bool checkEmptyCells(size_t rowSpan, size_t columnSpan) const 126 { 127 // Ignore cells outside current grid as we will grow it later if needed. 128 size_t maxRows = std::min(m_rowIndex + rowSpan, m_grid.size()); 129 size_t maxColumns = std::min(m_columnIndex + columnSpan, m_grid[0].size()); 130 131 // This adds a O(N^2) behavior that shouldn't be a big deal as we expect spanning areas to be small. 132 for (size_t row = m_rowIndex; row < maxRows; ++row) { 133 for (size_t column = m_columnIndex; column < maxColumns; ++column) { 134 const GridCell& children = m_grid[row][column]; 135 if (!children.isEmpty()) 136 return false; 137 } 138 } 139 140 return true; 141 } 142 143 PassOwnPtr<GridCoordinate> nextEmptyGridArea(size_t fixedTrackSpan, size_t varyingTrackSpan) 144 { 145 ASSERT(!m_grid.isEmpty()); 146 ASSERT(fixedTrackSpan >= 1 && varyingTrackSpan >= 1); 147 148 size_t rowSpan = (m_direction == ForColumns) ? varyingTrackSpan : fixedTrackSpan; 149 size_t columnSpan = (m_direction == ForColumns) ? fixedTrackSpan : varyingTrackSpan; 150 151 size_t& varyingTrackIndex = (m_direction == ForColumns) ? m_rowIndex : m_columnIndex; 152 const size_t endOfVaryingTrackIndex = (m_direction == ForColumns) ? m_grid.size() : m_grid[0].size(); 153 for (; varyingTrackIndex < endOfVaryingTrackIndex; ++varyingTrackIndex) { 154 if (checkEmptyCells(rowSpan, columnSpan)) { 155 OwnPtr<GridCoordinate> result = adoptPtr(new GridCoordinate(GridSpan(m_rowIndex, m_rowIndex + rowSpan - 1), GridSpan(m_columnIndex, m_columnIndex + columnSpan - 1))); 156 // Advance the iterator to avoid an infinite loop where we would return the same grid area over and over. 157 ++varyingTrackIndex; 158 return result.release(); 159 } 160 } 161 return nullptr; 162 } 163 164 private: 165 const GridRepresentation& m_grid; 166 GridTrackSizingDirection m_direction; 167 size_t m_rowIndex; 168 size_t m_columnIndex; 169 size_t m_childIndex; 170 }; 171 172 struct RenderGrid::GridSizingData { 173 WTF_MAKE_NONCOPYABLE(GridSizingData); 174 public: 175 GridSizingData(size_t gridColumnCount, size_t gridRowCount) 176 : columnTracks(gridColumnCount) 177 , rowTracks(gridRowCount) 178 { 179 } 180 181 Vector<GridTrack> columnTracks; 182 Vector<GridTrack> rowTracks; 183 Vector<size_t> contentSizedTracksIndex; 184 185 // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free. 186 Vector<LayoutUnit> distributeTrackVector; 187 Vector<GridTrack*> filteredTracks; 188 }; 189 190 RenderGrid::RenderGrid(Element* element) 191 : RenderBlock(element) 192 , m_gridIsDirty(true) 193 , m_orderIterator(this) 194 { 195 // All of our children must be block level. 196 setChildrenInline(false); 197 } 198 199 RenderGrid::~RenderGrid() 200 { 201 } 202 203 void RenderGrid::addChild(RenderObject* newChild, RenderObject* beforeChild) 204 { 205 RenderBlock::addChild(newChild, beforeChild); 206 207 if (gridIsDirty()) 208 return; 209 210 if (!newChild->isBox()) { 211 dirtyGrid(); 212 return; 213 } 214 215 if (style()->gridAutoFlow() != AutoFlowNone) { 216 // The grid needs to be recomputed as it might contain auto-placed items that will change their position. 217 dirtyGrid(); 218 return; 219 } 220 221 RenderBox* newChildBox = toRenderBox(newChild); 222 OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForRows); 223 OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *newChildBox, ForColumns); 224 if (!rowPositions || !columnPositions) { 225 // The new child requires the auto-placement algorithm to run so we need to recompute the grid fully. 226 dirtyGrid(); 227 return; 228 } else { 229 insertItemIntoGrid(newChildBox, GridCoordinate(*rowPositions, *columnPositions)); 230 addChildToIndexesMap(newChildBox); 231 } 232 } 233 234 void RenderGrid::addChildToIndexesMap(RenderBox* child) 235 { 236 ASSERT(!m_gridItemsIndexesMap.contains(child)); 237 RenderBox* sibling = child->nextSiblingBox(); 238 bool lastSibling = !sibling; 239 240 if (lastSibling) 241 sibling = child->previousSiblingBox(); 242 243 size_t index = 0; 244 if (sibling) 245 index = lastSibling ? m_gridItemsIndexesMap.get(sibling) + 1 : m_gridItemsIndexesMap.get(sibling); 246 247 if (sibling && !lastSibling) { 248 for (; sibling; sibling = sibling->nextSiblingBox()) 249 m_gridItemsIndexesMap.set(sibling, m_gridItemsIndexesMap.get(sibling) + 1); 250 } 251 252 m_gridItemsIndexesMap.set(child, index); 253 } 254 255 void RenderGrid::removeChild(RenderObject* child) 256 { 257 RenderBlock::removeChild(child); 258 259 if (gridIsDirty()) 260 return; 261 262 ASSERT(child->isBox()); 263 264 if (style()->gridAutoFlow() != AutoFlowNone) { 265 // The grid needs to be recomputed as it might contain auto-placed items that will change their position. 266 dirtyGrid(); 267 return; 268 } 269 270 const RenderBox* childBox = toRenderBox(child); 271 GridCoordinate coordinate = m_gridItemCoordinate.take(childBox); 272 273 for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) { 274 for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column) { 275 GridCell& cell = m_grid[row.toInt()][column.toInt()]; 276 cell.remove(cell.find(childBox)); 277 } 278 } 279 280 m_gridItemsIndexesMap.remove(childBox); 281 } 282 283 void RenderGrid::styleDidChange(StyleDifference diff, const RenderStyle* oldStyle) 284 { 285 RenderBlock::styleDidChange(diff, oldStyle); 286 if (!oldStyle) 287 return; 288 289 // FIXME: The following checks could be narrowed down if we kept track of which type of grid items we have: 290 // - explicit grid size changes impact negative explicitely positioned and auto-placed grid items. 291 // - named grid lines only impact grid items with named grid lines. 292 // - auto-flow changes only impacts auto-placed children. 293 294 if (explicitGridDidResize(oldStyle) 295 || namedGridLinesDefinitionDidChange(oldStyle) 296 || oldStyle->gridAutoFlow() != style()->gridAutoFlow()) 297 dirtyGrid(); 298 } 299 300 bool RenderGrid::explicitGridDidResize(const RenderStyle* oldStyle) const 301 { 302 return oldStyle->gridTemplateColumns().size() != style()->gridTemplateColumns().size() 303 || oldStyle->gridTemplateRows().size() != style()->gridTemplateRows().size(); 304 } 305 306 bool RenderGrid::namedGridLinesDefinitionDidChange(const RenderStyle* oldStyle) const 307 { 308 return oldStyle->namedGridRowLines() != style()->namedGridRowLines() 309 || oldStyle->namedGridColumnLines() != style()->namedGridColumnLines(); 310 } 311 312 void RenderGrid::layoutBlock(bool relayoutChildren) 313 { 314 ASSERT(needsLayout()); 315 316 if (!relayoutChildren && simplifiedLayout()) 317 return; 318 319 // FIXME: Much of this method is boiler plate that matches RenderBox::layoutBlock and Render*FlexibleBox::layoutBlock. 320 // It would be nice to refactor some of the duplicate code. 321 LayoutRepainter repainter(*this, checkForPaintInvalidationDuringLayout()); 322 LayoutState state(*this, locationOffset()); 323 324 LayoutSize previousSize = size(); 325 326 setLogicalHeight(0); 327 updateLogicalWidth(); 328 329 FastTextAutosizer::LayoutScope fastTextAutosizerLayoutScope(this); 330 331 layoutGridItems(); 332 333 LayoutUnit oldClientAfterEdge = clientLogicalBottom(); 334 updateLogicalHeight(); 335 336 if (size() != previousSize) 337 relayoutChildren = true; 338 339 layoutPositionedObjects(relayoutChildren || isDocumentElement()); 340 341 computeRegionRangeForBlock(flowThreadContainingBlock()); 342 343 computeOverflow(oldClientAfterEdge); 344 345 updateLayerTransformAfterLayout(); 346 347 // Update our scroll information if we're overflow:auto/scroll/hidden now that we know if 348 // we overflow or not. 349 if (hasOverflowClip()) 350 layer()->scrollableArea()->updateAfterLayout(); 351 352 repainter.repaintAfterLayout(); 353 354 clearNeedsLayout(); 355 } 356 357 void RenderGrid::computeIntrinsicLogicalWidths(LayoutUnit& minLogicalWidth, LayoutUnit& maxLogicalWidth) const 358 { 359 const_cast<RenderGrid*>(this)->placeItemsOnGrid(); 360 361 GridSizingData sizingData(gridColumnCount(), gridRowCount()); 362 LayoutUnit availableLogicalSpace = 0; 363 const_cast<RenderGrid*>(this)->computeUsedBreadthOfGridTracks(ForColumns, sizingData, availableLogicalSpace); 364 365 for (size_t i = 0; i < sizingData.columnTracks.size(); ++i) { 366 LayoutUnit minTrackBreadth = sizingData.columnTracks[i].m_usedBreadth; 367 LayoutUnit maxTrackBreadth = sizingData.columnTracks[i].m_maxBreadth; 368 maxTrackBreadth = std::max(maxTrackBreadth, minTrackBreadth); 369 370 minLogicalWidth += minTrackBreadth; 371 maxLogicalWidth += maxTrackBreadth; 372 373 // FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox). 374 } 375 } 376 377 void RenderGrid::computePreferredLogicalWidths() 378 { 379 ASSERT(preferredLogicalWidthsDirty()); 380 381 m_minPreferredLogicalWidth = 0; 382 m_maxPreferredLogicalWidth = 0; 383 384 // FIXME: We don't take our own logical width into account. Once we do, we need to make sure 385 // we apply (and test the interaction with) min-width / max-width. 386 387 computeIntrinsicLogicalWidths(m_minPreferredLogicalWidth, m_maxPreferredLogicalWidth); 388 389 LayoutUnit borderAndPaddingInInlineDirection = borderAndPaddingLogicalWidth(); 390 m_minPreferredLogicalWidth += borderAndPaddingInInlineDirection; 391 m_maxPreferredLogicalWidth += borderAndPaddingInInlineDirection; 392 393 clearPreferredLogicalWidthsDirty(); 394 } 395 396 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData) 397 { 398 LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding); 399 computeUsedBreadthOfGridTracks(direction, sizingData, availableLogicalSpace); 400 } 401 402 bool RenderGrid::gridElementIsShrinkToFit() 403 { 404 return isFloatingOrOutOfFlowPositioned(); 405 } 406 407 void RenderGrid::computeUsedBreadthOfGridTracks(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace) 408 { 409 Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks; 410 Vector<size_t> flexibleSizedTracksIndex; 411 sizingData.contentSizedTracksIndex.shrink(0); 412 413 // 1. Initialize per Grid track variables. 414 for (size_t i = 0; i < tracks.size(); ++i) { 415 GridTrack& track = tracks[i]; 416 const GridTrackSize& trackSize = gridTrackSize(direction, i); 417 const GridLength& minTrackBreadth = trackSize.minTrackBreadth(); 418 const GridLength& maxTrackBreadth = trackSize.maxTrackBreadth(); 419 420 track.m_usedBreadth = computeUsedBreadthOfMinLength(direction, minTrackBreadth); 421 track.m_maxBreadth = computeUsedBreadthOfMaxLength(direction, maxTrackBreadth, track.m_usedBreadth); 422 423 track.m_maxBreadth = std::max(track.m_maxBreadth, track.m_usedBreadth); 424 425 if (trackSize.isContentSized()) 426 sizingData.contentSizedTracksIndex.append(i); 427 if (trackSize.maxTrackBreadth().isFlex()) 428 flexibleSizedTracksIndex.append(i); 429 } 430 431 // 2. Resolve content-based TrackSizingFunctions. 432 if (!sizingData.contentSizedTracksIndex.isEmpty()) 433 resolveContentBasedTrackSizingFunctions(direction, sizingData, availableLogicalSpace); 434 435 for (size_t i = 0; i < tracks.size(); ++i) { 436 ASSERT(tracks[i].m_maxBreadth != infinity); 437 availableLogicalSpace -= tracks[i].m_usedBreadth; 438 } 439 440 const bool hasUndefinedRemainingSpace = (direction == ForRows) ? style()->logicalHeight().isAuto() : gridElementIsShrinkToFit(); 441 442 if (!hasUndefinedRemainingSpace && availableLogicalSpace <= 0) 443 return; 444 445 // 3. Grow all Grid tracks in GridTracks from their UsedBreadth up to their MaxBreadth value until 446 // availableLogicalSpace (RemainingSpace in the specs) is exhausted. 447 const size_t tracksSize = tracks.size(); 448 if (!hasUndefinedRemainingSpace) { 449 Vector<GridTrack*> tracksForDistribution(tracksSize); 450 for (size_t i = 0; i < tracksSize; ++i) 451 tracksForDistribution[i] = tracks.data() + i; 452 453 distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, sizingData, availableLogicalSpace); 454 } else { 455 for (size_t i = 0; i < tracksSize; ++i) 456 tracks[i].m_usedBreadth = tracks[i].m_maxBreadth; 457 } 458 459 if (flexibleSizedTracksIndex.isEmpty()) 460 return; 461 462 // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction. 463 double normalizedFractionBreadth = 0; 464 if (!hasUndefinedRemainingSpace) { 465 normalizedFractionBreadth = computeNormalizedFractionBreadth(tracks, GridSpan(0, tracks.size() - 1), direction, availableLogicalSpace); 466 } else { 467 for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) { 468 const size_t trackIndex = flexibleSizedTracksIndex[i]; 469 const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex); 470 normalizedFractionBreadth = std::max(normalizedFractionBreadth, tracks[trackIndex].m_usedBreadth / trackSize.maxTrackBreadth().flex()); 471 } 472 473 for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) { 474 GridIterator iterator(m_grid, direction, flexibleSizedTracksIndex[i]); 475 while (RenderBox* gridItem = iterator.nextGridItem()) { 476 const GridCoordinate coordinate = cachedGridCoordinate(gridItem); 477 const GridSpan span = (direction == ForColumns) ? coordinate.columns : coordinate.rows; 478 479 // Do not include already processed items. 480 if (i > 0 && span.resolvedInitialPosition.toInt() <= flexibleSizedTracksIndex[i - 1]) 481 continue; 482 483 double itemNormalizedFlexBreadth = computeNormalizedFractionBreadth(tracks, span, direction, maxContentForChild(gridItem, direction, sizingData.columnTracks)); 484 normalizedFractionBreadth = std::max(normalizedFractionBreadth, itemNormalizedFlexBreadth); 485 } 486 } 487 } 488 489 for (size_t i = 0; i < flexibleSizedTracksIndex.size(); ++i) { 490 const size_t trackIndex = flexibleSizedTracksIndex[i]; 491 const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex); 492 493 tracks[trackIndex].m_usedBreadth = std::max<LayoutUnit>(tracks[trackIndex].m_usedBreadth, normalizedFractionBreadth * trackSize.maxTrackBreadth().flex()); 494 } 495 } 496 497 LayoutUnit RenderGrid::computeUsedBreadthOfMinLength(GridTrackSizingDirection direction, const GridLength& gridLength) const 498 { 499 if (gridLength.isFlex()) 500 return 0; 501 502 const Length& trackLength = gridLength.length(); 503 ASSERT(!trackLength.isAuto()); 504 if (trackLength.isSpecified()) 505 return computeUsedBreadthOfSpecifiedLength(direction, trackLength); 506 507 ASSERT(trackLength.isMinContent() || trackLength.isMaxContent()); 508 return 0; 509 } 510 511 LayoutUnit RenderGrid::computeUsedBreadthOfMaxLength(GridTrackSizingDirection direction, const GridLength& gridLength, LayoutUnit usedBreadth) const 512 { 513 if (gridLength.isFlex()) 514 return usedBreadth; 515 516 const Length& trackLength = gridLength.length(); 517 ASSERT(!trackLength.isAuto()); 518 if (trackLength.isSpecified()) { 519 LayoutUnit computedBreadth = computeUsedBreadthOfSpecifiedLength(direction, trackLength); 520 ASSERT(computedBreadth != infinity); 521 return computedBreadth; 522 } 523 524 ASSERT(trackLength.isMinContent() || trackLength.isMaxContent()); 525 return infinity; 526 } 527 528 LayoutUnit RenderGrid::computeUsedBreadthOfSpecifiedLength(GridTrackSizingDirection direction, const Length& trackLength) const 529 { 530 ASSERT(trackLength.isSpecified()); 531 // FIXME: The -1 here should be replaced by whatever the intrinsic height of the grid is. 532 return valueForLength(trackLength, direction == ForColumns ? logicalWidth() : computeContentLogicalHeight(style()->logicalHeight(), -1)); 533 } 534 535 static bool sortByGridNormalizedFlexValue(const GridTrackForNormalization& track1, const GridTrackForNormalization& track2) 536 { 537 return track1.m_normalizedFlexValue < track2.m_normalizedFlexValue; 538 } 539 540 double RenderGrid::computeNormalizedFractionBreadth(Vector<GridTrack>& tracks, const GridSpan& tracksSpan, GridTrackSizingDirection direction, LayoutUnit availableLogicalSpace) const 541 { 542 // |availableLogicalSpace| already accounts for the used breadths so no need to remove it here. 543 544 Vector<GridTrackForNormalization> tracksForNormalization; 545 for (GridSpan::iterator resolvedPosition = tracksSpan.begin(); resolvedPosition != tracksSpan.end(); ++resolvedPosition) { 546 const GridTrackSize& trackSize = gridTrackSize(direction, resolvedPosition.toInt()); 547 if (!trackSize.maxTrackBreadth().isFlex()) 548 continue; 549 550 tracksForNormalization.append(GridTrackForNormalization(tracks[resolvedPosition.toInt()], trackSize.maxTrackBreadth().flex())); 551 } 552 553 // The function is not called if we don't have <flex> grid tracks 554 ASSERT(!tracksForNormalization.isEmpty()); 555 556 std::sort(tracksForNormalization.begin(), tracksForNormalization.end(), sortByGridNormalizedFlexValue); 557 558 // These values work together: as we walk over our grid tracks, we increase fractionValueBasedOnGridItemsRatio 559 // to match a grid track's usedBreadth to <flex> ratio until the total fractions sized grid tracks wouldn't 560 // fit into availableLogicalSpaceIgnoringFractionTracks. 561 double accumulatedFractions = 0; 562 LayoutUnit fractionValueBasedOnGridItemsRatio = 0; 563 LayoutUnit availableLogicalSpaceIgnoringFractionTracks = availableLogicalSpace; 564 565 for (size_t i = 0; i < tracksForNormalization.size(); ++i) { 566 const GridTrackForNormalization& track = tracksForNormalization[i]; 567 if (track.m_normalizedFlexValue > fractionValueBasedOnGridItemsRatio) { 568 // If the normalized flex value (we ordered |tracksForNormalization| by increasing normalized flex value) 569 // will make us overflow our container, then stop. We have the previous step's ratio is the best fit. 570 if (track.m_normalizedFlexValue * accumulatedFractions > availableLogicalSpaceIgnoringFractionTracks) 571 break; 572 573 fractionValueBasedOnGridItemsRatio = track.m_normalizedFlexValue; 574 } 575 576 accumulatedFractions += track.m_flex; 577 // This item was processed so we re-add its used breadth to the available space to accurately count the remaining space. 578 availableLogicalSpaceIgnoringFractionTracks += track.m_track->m_usedBreadth; 579 } 580 581 return availableLogicalSpaceIgnoringFractionTracks / accumulatedFractions; 582 } 583 584 const GridTrackSize& RenderGrid::gridTrackSize(GridTrackSizingDirection direction, size_t i) const 585 { 586 const Vector<GridTrackSize>& trackStyles = (direction == ForColumns) ? style()->gridTemplateColumns() : style()->gridTemplateRows(); 587 if (i >= trackStyles.size()) 588 return (direction == ForColumns) ? style()->gridAutoColumns() : style()->gridAutoRows(); 589 590 const GridTrackSize& trackSize = trackStyles[i]; 591 // If the logical width/height of the grid container is indefinite, percentage values are treated as <auto>. 592 if (trackSize.isPercentage()) { 593 Length logicalSize = direction == ForColumns ? style()->logicalWidth() : style()->logicalHeight(); 594 if (logicalSize.isIntrinsicOrAuto()) { 595 DEFINE_STATIC_LOCAL(GridTrackSize, autoTrackSize, (Length(Auto))); 596 return autoTrackSize; 597 } 598 } 599 600 return trackSize; 601 } 602 603 LayoutUnit RenderGrid::logicalHeightForChild(RenderBox* child, Vector<GridTrack>& columnTracks) 604 { 605 SubtreeLayoutScope layoutScope(*child); 606 LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit(); 607 LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks); 608 if (child->style()->logicalHeight().isPercent() || oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth) 609 layoutScope.setNeedsLayout(child); 610 611 child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth); 612 // If |child| has a percentage logical height, we shouldn't let it override its intrinsic height, which is 613 // what we are interested in here. Thus we need to set the override logical height to -1 (no possible resolution). 614 child->setOverrideContainingBlockContentLogicalHeight(-1); 615 child->layoutIfNeeded(); 616 return child->logicalHeight() + child->marginLogicalHeight(); 617 } 618 619 LayoutUnit RenderGrid::minContentForChild(RenderBox* child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks) 620 { 621 bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode(); 622 // FIXME: Properly support orthogonal writing mode. 623 if (hasOrthogonalWritingMode) 624 return 0; 625 626 if (direction == ForColumns) { 627 // FIXME: It's unclear if we should return the intrinsic width or the preferred width. 628 // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html 629 return child->minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child); 630 } 631 632 return logicalHeightForChild(child, columnTracks); 633 } 634 635 LayoutUnit RenderGrid::maxContentForChild(RenderBox* child, GridTrackSizingDirection direction, Vector<GridTrack>& columnTracks) 636 { 637 bool hasOrthogonalWritingMode = child->isHorizontalWritingMode() != isHorizontalWritingMode(); 638 // FIXME: Properly support orthogonal writing mode. 639 if (hasOrthogonalWritingMode) 640 return LayoutUnit(); 641 642 if (direction == ForColumns) { 643 // FIXME: It's unclear if we should return the intrinsic width or the preferred width. 644 // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html 645 return child->maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(child); 646 } 647 648 return logicalHeightForChild(child, columnTracks); 649 } 650 651 void RenderGrid::resolveContentBasedTrackSizingFunctions(GridTrackSizingDirection direction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace) 652 { 653 // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track (crbug.com/235258). 654 655 // FIXME: Per step 2 of the specification, we should order the grid items by increasing span. 656 657 for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) { 658 GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]); 659 while (RenderBox* gridItem = iterator.nextGridItem()) { 660 resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth); 661 resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth); 662 resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth); 663 resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth); 664 } 665 666 GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[i] : sizingData.rowTracks[i]; 667 if (track.m_maxBreadth == infinity) 668 track.m_maxBreadth = track.m_usedBreadth; 669 } 670 } 671 672 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(GridTrackSizingDirection direction, GridSizingData& sizingData, RenderBox* gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction) 673 { 674 const GridCoordinate coordinate = cachedGridCoordinate(gridItem); 675 const GridResolvedPosition initialTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedInitialPosition : coordinate.rows.resolvedInitialPosition; 676 const GridResolvedPosition finalTrackPosition = (direction == ForColumns) ? coordinate.columns.resolvedFinalPosition : coordinate.rows.resolvedFinalPosition; 677 678 sizingData.filteredTracks.shrink(0); 679 for (GridResolvedPosition trackPosition = initialTrackPosition; trackPosition <= finalTrackPosition; ++trackPosition) { 680 const GridTrackSize& trackSize = gridTrackSize(direction, trackPosition.toInt()); 681 if (!(trackSize.*filterFunction)()) 682 continue; 683 684 GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackPosition.toInt()] : sizingData.rowTracks[trackPosition.toInt()]; 685 sizingData.filteredTracks.append(&track); 686 } 687 688 if (sizingData.filteredTracks.isEmpty()) 689 return; 690 691 LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks); 692 for (GridResolvedPosition trackIndexForSpace = initialTrackPosition; trackIndexForSpace <= finalTrackPosition; ++trackIndexForSpace) { 693 GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndexForSpace.toInt()] : sizingData.rowTracks[trackIndexForSpace.toInt()]; 694 additionalBreadthSpace -= (track.*trackGetter)(); 695 } 696 697 // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|. 698 distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.filteredTracks, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace); 699 } 700 701 static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2) 702 { 703 return (track1->m_maxBreadth - track1->m_usedBreadth) < (track2->m_maxBreadth - track2->m_usedBreadth); 704 } 705 706 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace) 707 { 708 std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential); 709 710 size_t tracksSize = tracks.size(); 711 sizingData.distributeTrackVector.resize(tracksSize); 712 713 for (size_t i = 0; i < tracksSize; ++i) { 714 GridTrack& track = *tracks[i]; 715 LayoutUnit availableLogicalSpaceShare = availableLogicalSpace / (tracksSize - i); 716 LayoutUnit trackBreadth = (tracks[i]->*trackGetter)(); 717 LayoutUnit growthShare = std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth); 718 sizingData.distributeTrackVector[i] = trackBreadth; 719 // We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function. 720 if (growthShare > 0) { 721 sizingData.distributeTrackVector[i] += growthShare; 722 availableLogicalSpace -= growthShare; 723 } 724 } 725 726 if (availableLogicalSpace > 0 && tracksForGrowthAboveMaxBreadth) { 727 tracksSize = tracksForGrowthAboveMaxBreadth->size(); 728 for (size_t i = 0; i < tracksSize; ++i) { 729 LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i); 730 sizingData.distributeTrackVector[i] += growthShare; 731 availableLogicalSpace -= growthShare; 732 } 733 } 734 735 for (size_t i = 0; i < tracksSize; ++i) { 736 LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)(); 737 if (growth >= 0) 738 (tracks[i]->*trackGrowthFunction)(growth); 739 } 740 } 741 742 #ifndef NDEBUG 743 bool RenderGrid::tracksAreWiderThanMinTrackBreadth(GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) 744 { 745 for (size_t i = 0; i < tracks.size(); ++i) { 746 const GridTrackSize& trackSize = gridTrackSize(direction, i); 747 const GridLength& minTrackBreadth = trackSize.minTrackBreadth(); 748 if (computeUsedBreadthOfMinLength(direction, minTrackBreadth) > tracks[i].m_usedBreadth) 749 return false; 750 } 751 return true; 752 } 753 #endif 754 755 void RenderGrid::ensureGridSize(size_t maximumRowIndex, size_t maximumColumnIndex) 756 { 757 const size_t oldRowSize = gridRowCount(); 758 if (maximumRowIndex >= oldRowSize) { 759 m_grid.grow(maximumRowIndex + 1); 760 for (size_t row = oldRowSize; row < gridRowCount(); ++row) 761 m_grid[row].grow(gridColumnCount()); 762 } 763 764 if (maximumColumnIndex >= gridColumnCount()) { 765 for (size_t row = 0; row < gridRowCount(); ++row) 766 m_grid[row].grow(maximumColumnIndex + 1); 767 } 768 } 769 770 void RenderGrid::insertItemIntoGrid(RenderBox* child, const GridCoordinate& coordinate) 771 { 772 ensureGridSize(coordinate.rows.resolvedFinalPosition.toInt(), coordinate.columns.resolvedFinalPosition.toInt()); 773 774 for (GridSpan::iterator row = coordinate.rows.begin(); row != coordinate.rows.end(); ++row) { 775 for (GridSpan::iterator column = coordinate.columns.begin(); column != coordinate.columns.end(); ++column) 776 m_grid[row.toInt()][column.toInt()].append(child); 777 } 778 779 m_gridItemCoordinate.set(child, coordinate); 780 } 781 782 void RenderGrid::placeItemsOnGrid() 783 { 784 if (!gridIsDirty()) 785 return; 786 787 ASSERT(m_gridItemCoordinate.isEmpty()); 788 789 populateExplicitGridAndOrderIterator(); 790 791 // We clear the dirty bit here as the grid sizes have been updated, this means 792 // that we can safely call gridRowCount() / gridColumnCount(). 793 m_gridIsDirty = false; 794 795 Vector<RenderBox*> autoMajorAxisAutoGridItems; 796 Vector<RenderBox*> specifiedMajorAxisAutoGridItems; 797 GridAutoFlow autoFlow = style()->gridAutoFlow(); 798 for (RenderBox* child = m_orderIterator.first(); child; child = m_orderIterator.next()) { 799 // FIXME: We never re-resolve positions if the grid is grown during auto-placement which may lead auto / <integer> 800 // positions to not match the author's intent. The specification is unclear on what should be done in this case. 801 OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows); 802 OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns); 803 if (!rowPositions || !columnPositions) { 804 GridSpan* majorAxisPositions = (autoPlacementMajorAxisDirection() == ForColumns) ? columnPositions.get() : rowPositions.get(); 805 if (!majorAxisPositions) 806 autoMajorAxisAutoGridItems.append(child); 807 else 808 specifiedMajorAxisAutoGridItems.append(child); 809 continue; 810 } 811 insertItemIntoGrid(child, GridCoordinate(*rowPositions, *columnPositions)); 812 } 813 814 ASSERT(gridRowCount() >= style()->gridTemplateRows().size()); 815 ASSERT(gridColumnCount() >= style()->gridTemplateColumns().size()); 816 817 if (autoFlow == AutoFlowNone) { 818 // If we did collect some grid items, they won't be placed thus never laid out. 819 ASSERT(!autoMajorAxisAutoGridItems.size()); 820 ASSERT(!specifiedMajorAxisAutoGridItems.size()); 821 return; 822 } 823 824 placeSpecifiedMajorAxisItemsOnGrid(specifiedMajorAxisAutoGridItems); 825 placeAutoMajorAxisItemsOnGrid(autoMajorAxisAutoGridItems); 826 827 m_grid.shrinkToFit(); 828 } 829 830 void RenderGrid::populateExplicitGridAndOrderIterator() 831 { 832 OrderIteratorPopulator populator(m_orderIterator); 833 834 size_t maximumRowIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridRowCount(*style())); 835 size_t maximumColumnIndex = std::max<size_t>(1, GridResolvedPosition::explicitGridColumnCount(*style())); 836 837 ASSERT(m_gridItemsIndexesMap.isEmpty()); 838 size_t childIndex = 0; 839 for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) { 840 populator.collectChild(child); 841 m_gridItemsIndexesMap.set(child, childIndex++); 842 843 // This function bypasses the cache (cachedGridCoordinate()) as it is used to build it. 844 OwnPtr<GridSpan> rowPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForRows); 845 OwnPtr<GridSpan> columnPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *child, ForColumns); 846 847 // |positions| is 0 if we need to run the auto-placement algorithm. 848 if (rowPositions) { 849 maximumRowIndex = std::max<size_t>(maximumRowIndex, rowPositions->resolvedFinalPosition.next().toInt()); 850 } else { 851 // Grow the grid for items with a definite row span, getting the largest such span. 852 GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForRows, GridResolvedPosition(0)); 853 maximumRowIndex = std::max<size_t>(maximumRowIndex, positions.resolvedFinalPosition.next().toInt()); 854 } 855 856 if (columnPositions) { 857 maximumColumnIndex = std::max<size_t>(maximumColumnIndex, columnPositions->resolvedFinalPosition.next().toInt()); 858 } else { 859 // Grow the grid for items with a definite column span, getting the largest such span. 860 GridSpan positions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *child, ForColumns, GridResolvedPosition(0)); 861 maximumColumnIndex = std::max<size_t>(maximumColumnIndex, positions.resolvedFinalPosition.next().toInt()); 862 } 863 } 864 865 m_grid.grow(maximumRowIndex); 866 for (size_t i = 0; i < m_grid.size(); ++i) 867 m_grid[i].grow(maximumColumnIndex); 868 } 869 870 PassOwnPtr<GridCoordinate> RenderGrid::createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(const RenderBox* gridItem, GridTrackSizingDirection specifiedDirection, const GridSpan& specifiedPositions) const 871 { 872 GridTrackSizingDirection crossDirection = specifiedDirection == ForColumns ? ForRows : ForColumns; 873 const size_t endOfCrossDirection = crossDirection == ForColumns ? gridColumnCount() : gridRowCount(); 874 GridSpan crossDirectionPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, crossDirection, GridResolvedPosition(endOfCrossDirection)); 875 return adoptPtr(new GridCoordinate(specifiedDirection == ForColumns ? crossDirectionPositions : specifiedPositions, specifiedDirection == ForColumns ? specifiedPositions : crossDirectionPositions)); 876 } 877 878 void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems) 879 { 880 for (size_t i = 0; i < autoGridItems.size(); ++i) { 881 OwnPtr<GridSpan> majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *autoGridItems[i], autoPlacementMajorAxisDirection()); 882 GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *autoGridItems[i], autoPlacementMinorAxisDirection(), GridResolvedPosition(0)); 883 884 GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisPositions->resolvedInitialPosition.toInt()); 885 OwnPtr<GridCoordinate> emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions->integerSpan(), minorAxisPositions.integerSpan()); 886 if (!emptyGridArea) 887 emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(autoGridItems[i], autoPlacementMajorAxisDirection(), *majorAxisPositions); 888 insertItemIntoGrid(autoGridItems[i], *emptyGridArea); 889 } 890 } 891 892 void RenderGrid::placeAutoMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems) 893 { 894 for (size_t i = 0; i < autoGridItems.size(); ++i) 895 placeAutoMajorAxisItemOnGrid(autoGridItems[i]); 896 } 897 898 void RenderGrid::placeAutoMajorAxisItemOnGrid(RenderBox* gridItem) 899 { 900 OwnPtr<GridSpan> minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMinorAxisDirection()); 901 ASSERT(!GridResolvedPosition::resolveGridPositionsFromStyle(*style(), *gridItem, autoPlacementMajorAxisDirection())); 902 GridSpan majorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMajorAxisDirection(), GridResolvedPosition(0)); 903 OwnPtr<GridCoordinate> emptyGridArea; 904 if (minorAxisPositions) { 905 GridIterator iterator(m_grid, autoPlacementMinorAxisDirection(), minorAxisPositions->resolvedInitialPosition.toInt()); 906 emptyGridArea = iterator.nextEmptyGridArea(minorAxisPositions->integerSpan(), majorAxisPositions.integerSpan()); 907 if (!emptyGridArea) 908 emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), *minorAxisPositions); 909 } else { 910 GridSpan minorAxisPositions = GridResolvedPosition::resolveGridPositionsFromAutoPlacementPosition(*style(), *gridItem, autoPlacementMinorAxisDirection(), GridResolvedPosition(0)); 911 912 const size_t endOfMajorAxis = (autoPlacementMajorAxisDirection() == ForColumns) ? gridColumnCount() : gridRowCount(); 913 for (size_t majorAxisIndex = 0; majorAxisIndex < endOfMajorAxis; ++majorAxisIndex) { 914 GridIterator iterator(m_grid, autoPlacementMajorAxisDirection(), majorAxisIndex); 915 emptyGridArea = iterator.nextEmptyGridArea(majorAxisPositions.integerSpan(), minorAxisPositions.integerSpan()); 916 917 if (emptyGridArea) { 918 // Check that it fits in the minor axis direction, as we shouldn't grow in that direction here (it was already managed in populateExplicitGridAndOrderIterator()). 919 GridResolvedPosition minorAxisFinalPositionIndex = autoPlacementMinorAxisDirection() == ForColumns ? emptyGridArea->columns.resolvedFinalPosition : emptyGridArea->rows.resolvedFinalPosition; 920 const size_t endOfMinorAxis = autoPlacementMinorAxisDirection() == ForColumns ? gridColumnCount() : gridRowCount(); 921 if (minorAxisFinalPositionIndex.toInt() < endOfMinorAxis) 922 break; 923 924 // Discard empty grid area as it does not fit in the minor axis direction. 925 // We don't need to create a new empty grid area yet as we might find a valid one in the next iteration. 926 emptyGridArea = nullptr; 927 } 928 } 929 930 if (!emptyGridArea) 931 emptyGridArea = createEmptyGridAreaAtSpecifiedPositionsOutsideGrid(gridItem, autoPlacementMinorAxisDirection(), minorAxisPositions); 932 } 933 934 insertItemIntoGrid(gridItem, *emptyGridArea); 935 } 936 937 GridTrackSizingDirection RenderGrid::autoPlacementMajorAxisDirection() const 938 { 939 GridAutoFlow flow = style()->gridAutoFlow(); 940 ASSERT(flow != AutoFlowNone); 941 return (flow == AutoFlowColumn) ? ForColumns : ForRows; 942 } 943 944 GridTrackSizingDirection RenderGrid::autoPlacementMinorAxisDirection() const 945 { 946 GridAutoFlow flow = style()->gridAutoFlow(); 947 ASSERT(flow != AutoFlowNone); 948 return (flow == AutoFlowColumn) ? ForRows : ForColumns; 949 } 950 951 void RenderGrid::dirtyGrid() 952 { 953 m_grid.resize(0); 954 m_gridItemCoordinate.clear(); 955 m_gridIsDirty = true; 956 m_gridItemsOverflowingGridArea.resize(0); 957 m_gridItemsIndexesMap.clear(); 958 } 959 960 void RenderGrid::layoutGridItems() 961 { 962 placeItemsOnGrid(); 963 964 GridSizingData sizingData(gridColumnCount(), gridRowCount()); 965 computeUsedBreadthOfGridTracks(ForColumns, sizingData); 966 ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks)); 967 computeUsedBreadthOfGridTracks(ForRows, sizingData); 968 ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks)); 969 970 populateGridPositions(sizingData); 971 m_gridItemsOverflowingGridArea.resize(0); 972 973 for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) { 974 // Because the grid area cannot be styled, we don't need to adjust 975 // the grid breadth to account for 'box-sizing'. 976 LayoutUnit oldOverrideContainingBlockContentLogicalWidth = child->hasOverrideContainingBlockLogicalWidth() ? child->overrideContainingBlockContentLogicalWidth() : LayoutUnit(); 977 LayoutUnit oldOverrideContainingBlockContentLogicalHeight = child->hasOverrideContainingBlockLogicalHeight() ? child->overrideContainingBlockContentLogicalHeight() : LayoutUnit(); 978 979 LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, sizingData.columnTracks); 980 LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(child, ForRows, sizingData.rowTracks); 981 982 SubtreeLayoutScope layoutScope(*child); 983 if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && child->hasRelativeLogicalHeight())) 984 layoutScope.setNeedsLayout(child); 985 986 child->setOverrideContainingBlockContentLogicalWidth(overrideContainingBlockContentLogicalWidth); 987 child->setOverrideContainingBlockContentLogicalHeight(overrideContainingBlockContentLogicalHeight); 988 989 LayoutRect oldChildRect = child->frameRect(); 990 991 // FIXME: Grid items should stretch to fill their cells. Once we 992 // implement grid-{column,row}-align, we can also shrink to fit. For 993 // now, just size as if we were a regular child. 994 child->layoutIfNeeded(); 995 996 #ifndef NDEBUG 997 const GridCoordinate& coordinate = cachedGridCoordinate(child); 998 ASSERT(coordinate.columns.resolvedInitialPosition.toInt() < sizingData.columnTracks.size()); 999 ASSERT(coordinate.rows.resolvedInitialPosition.toInt() < sizingData.rowTracks.size()); 1000 #endif 1001 child->setLogicalLocation(findChildLogicalPosition(child)); 1002 1003 // Keep track of children overflowing their grid area as we might need to paint them even if the grid-area is 1004 // not visible 1005 if (child->logicalHeight() > overrideContainingBlockContentLogicalHeight 1006 || child->logicalWidth() > overrideContainingBlockContentLogicalWidth) 1007 m_gridItemsOverflowingGridArea.append(child); 1008 1009 // If the child moved, we have to repaint it as well as any floating/positioned 1010 // descendants. An exception is if we need a layout. In this case, we know we're going to 1011 // repaint ourselves (and the child) anyway. 1012 if (!selfNeedsLayout() && child->checkForPaintInvalidationDuringLayout()) 1013 child->repaintDuringLayoutIfMoved(oldChildRect); 1014 } 1015 1016 for (size_t i = 0; i < sizingData.rowTracks.size(); ++i) 1017 setLogicalHeight(logicalHeight() + sizingData.rowTracks[i].m_usedBreadth); 1018 1019 // Min / max logical height is handled by the call to updateLogicalHeight in layoutBlock. 1020 1021 setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight()); 1022 } 1023 1024 GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox* gridItem) const 1025 { 1026 ASSERT(m_gridItemCoordinate.contains(gridItem)); 1027 return m_gridItemCoordinate.get(gridItem); 1028 } 1029 1030 LayoutUnit RenderGrid::gridAreaBreadthForChild(const RenderBox* child, GridTrackSizingDirection direction, const Vector<GridTrack>& tracks) const 1031 { 1032 const GridCoordinate& coordinate = cachedGridCoordinate(child); 1033 const GridSpan& span = (direction == ForColumns) ? coordinate.columns : coordinate.rows; 1034 LayoutUnit gridAreaBreadth = 0; 1035 for (GridSpan::iterator trackPosition = span.begin(); trackPosition != span.end(); ++trackPosition) 1036 gridAreaBreadth += tracks[trackPosition.toInt()].m_usedBreadth; 1037 return gridAreaBreadth; 1038 } 1039 1040 void RenderGrid::populateGridPositions(const GridSizingData& sizingData) 1041 { 1042 m_columnPositions.resize(sizingData.columnTracks.size() + 1); 1043 m_columnPositions[0] = borderAndPaddingStart(); 1044 for (size_t i = 0; i < m_columnPositions.size() - 1; ++i) 1045 m_columnPositions[i + 1] = m_columnPositions[i] + sizingData.columnTracks[i].m_usedBreadth; 1046 1047 m_rowPositions.resize(sizingData.rowTracks.size() + 1); 1048 m_rowPositions[0] = borderAndPaddingBefore(); 1049 for (size_t i = 0; i < m_rowPositions.size() - 1; ++i) 1050 m_rowPositions[i + 1] = m_rowPositions[i] + sizingData.rowTracks[i].m_usedBreadth; 1051 } 1052 1053 LayoutUnit RenderGrid::startOfColumnForChild(const RenderBox* child) const 1054 { 1055 const GridCoordinate& coordinate = cachedGridCoordinate(child); 1056 LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()]; 1057 // The grid items should be inside the grid container's border box, that's why they need to be shifted. 1058 // FIXME: This should account for the grid item's <overflow-position>. 1059 return startOfColumn + marginStartForChild(child); 1060 } 1061 1062 LayoutUnit RenderGrid::endOfColumnForChild(const RenderBox* child) const 1063 { 1064 const GridCoordinate& coordinate = cachedGridCoordinate(child); 1065 LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()]; 1066 // The grid items should be inside the grid container's border box, that's why they need to be shifted. 1067 LayoutUnit columnPosition = startOfColumn + marginStartForChild(child); 1068 1069 LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()]; 1070 // FIXME: This should account for the grid item's <overflow-position>. 1071 return columnPosition + std::max<LayoutUnit>(0, endOfColumn - m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()] - child->logicalWidth()); 1072 } 1073 1074 LayoutUnit RenderGrid::columnPositionAlignedWithGridContainerStart(const RenderBox* child) const 1075 { 1076 if (style()->isLeftToRightDirection()) 1077 return startOfColumnForChild(child); 1078 1079 return endOfColumnForChild(child); 1080 } 1081 1082 LayoutUnit RenderGrid::columnPositionAlignedWithGridContainerEnd(const RenderBox* child) const 1083 { 1084 if (!style()->isLeftToRightDirection()) 1085 return startOfColumnForChild(child); 1086 1087 return endOfColumnForChild(child); 1088 } 1089 1090 LayoutUnit RenderGrid::centeredColumnPositionForChild(const RenderBox* child) const 1091 { 1092 const GridCoordinate& coordinate = cachedGridCoordinate(child); 1093 LayoutUnit startOfColumn = m_columnPositions[coordinate.columns.resolvedInitialPosition.toInt()]; 1094 LayoutUnit endOfColumn = m_columnPositions[coordinate.columns.resolvedFinalPosition.next().toInt()]; 1095 LayoutUnit columnPosition = startOfColumn + marginStartForChild(child); 1096 return columnPosition + std::max<LayoutUnit>(0, endOfColumn - startOfColumn - child->logicalWidth()) / 2; 1097 } 1098 1099 LayoutUnit RenderGrid::columnPositionForChild(const RenderBox* child) const 1100 { 1101 ItemPosition childJustifySelf = child->style()->justifySelf(); 1102 switch (childJustifySelf) { 1103 case ItemPositionSelfStart: 1104 // self-start is based on the child's direction. That's why we need to check against the grid container's direction. 1105 if (child->style()->direction() != style()->direction()) 1106 return columnPositionAlignedWithGridContainerEnd(child); 1107 1108 return columnPositionAlignedWithGridContainerStart(child); 1109 case ItemPositionSelfEnd: 1110 // self-end is based on the child's direction. That's why we need to check against the grid container's direction. 1111 if (child->style()->direction() != style()->direction()) 1112 return columnPositionAlignedWithGridContainerStart(child); 1113 1114 return columnPositionAlignedWithGridContainerEnd(child); 1115 1116 case ItemPositionFlexStart: 1117 case ItemPositionFlexEnd: 1118 // Only used in flex layout, for other layout, it's equivalent to 'start'. 1119 return columnPositionAlignedWithGridContainerStart(child); 1120 1121 case ItemPositionLeft: 1122 // If the property's axis is not parallel with the inline axis, this is equivalent to start. 1123 if (!isHorizontalWritingMode()) 1124 return columnPositionAlignedWithGridContainerStart(child); 1125 1126 if (style()->isLeftToRightDirection()) 1127 return columnPositionAlignedWithGridContainerStart(child); 1128 1129 return columnPositionAlignedWithGridContainerEnd(child); 1130 case ItemPositionRight: 1131 // If the property's axis is not parallel with the inline axis, this is equivalent to start. 1132 if (!isHorizontalWritingMode()) 1133 return columnPositionAlignedWithGridContainerStart(child); 1134 1135 if (style()->isLeftToRightDirection()) 1136 return columnPositionAlignedWithGridContainerEnd(child); 1137 1138 return columnPositionAlignedWithGridContainerStart(child); 1139 1140 case ItemPositionCenter: 1141 return centeredColumnPositionForChild(child); 1142 case ItemPositionStart: 1143 return columnPositionAlignedWithGridContainerStart(child); 1144 case ItemPositionEnd: 1145 return columnPositionAlignedWithGridContainerEnd(child); 1146 1147 case ItemPositionAuto: 1148 case ItemPositionStretch: 1149 case ItemPositionBaseline: 1150 // FIXME: Implement the previous values. For now, we always start align the child. 1151 return startOfColumnForChild(child); 1152 } 1153 1154 ASSERT_NOT_REACHED(); 1155 return 0; 1156 } 1157 1158 LayoutUnit RenderGrid::rowPositionForChild(const RenderBox* child) const 1159 { 1160 const GridCoordinate& coordinate = cachedGridCoordinate(child); 1161 1162 // The grid items should be inside the grid container's border box, that's why they need to be shifted. 1163 LayoutUnit startOfRow = m_rowPositions[coordinate.rows.resolvedInitialPosition.toInt()]; 1164 LayoutUnit rowPosition = startOfRow + marginBeforeForChild(child); 1165 1166 // FIXME: This function should account for 'align-self'. 1167 1168 return rowPosition; 1169 } 1170 1171 LayoutPoint RenderGrid::findChildLogicalPosition(const RenderBox* child) const 1172 { 1173 return LayoutPoint(columnPositionForChild(child), rowPositionForChild(child)); 1174 } 1175 1176 static GridSpan dirtiedGridAreas(const Vector<LayoutUnit>& coordinates, LayoutUnit start, LayoutUnit end) 1177 { 1178 // This function does a binary search over the coordinates. 1179 // This doesn't work with grid items overflowing their grid areas, but that is managed with m_gridItemsOverflowingGridArea. 1180 1181 size_t startGridAreaIndex = std::upper_bound(coordinates.begin(), coordinates.end() - 1, start) - coordinates.begin(); 1182 if (startGridAreaIndex > 0) 1183 --startGridAreaIndex; 1184 1185 size_t endGridAreaIndex = std::upper_bound(coordinates.begin() + startGridAreaIndex, coordinates.end() - 1, end) - coordinates.begin(); 1186 if (endGridAreaIndex > 0) 1187 --endGridAreaIndex; 1188 1189 return GridSpan(startGridAreaIndex, endGridAreaIndex); 1190 } 1191 1192 class GridItemsSorter { 1193 public: 1194 bool operator()(const std::pair<RenderBox*, size_t> firstChild, const std::pair<RenderBox*, size_t> secondChild) const 1195 { 1196 if (firstChild.first->style()->order() != secondChild.first->style()->order()) 1197 return firstChild.first->style()->order() < secondChild.first->style()->order(); 1198 1199 return firstChild.second < secondChild.second; 1200 } 1201 }; 1202 1203 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint& paintOffset) 1204 { 1205 ASSERT_WITH_SECURITY_IMPLICATION(!gridIsDirty()); 1206 1207 LayoutRect localRepaintRect = paintInfo.rect; 1208 localRepaintRect.moveBy(-paintOffset); 1209 1210 GridSpan dirtiedColumns = dirtiedGridAreas(m_columnPositions, localRepaintRect.x(), localRepaintRect.maxX()); 1211 GridSpan dirtiedRows = dirtiedGridAreas(m_rowPositions, localRepaintRect.y(), localRepaintRect.maxY()); 1212 1213 Vector<std::pair<RenderBox*, size_t> > gridItemsToBePainted; 1214 1215 for (GridSpan::iterator row = dirtiedRows.begin(); row != dirtiedRows.end(); ++row) { 1216 for (GridSpan::iterator column = dirtiedColumns.begin(); column != dirtiedColumns.end(); ++column) { 1217 const Vector<RenderBox*, 1>& children = m_grid[row.toInt()][column.toInt()]; 1218 for (size_t j = 0; j < children.size(); ++j) 1219 gridItemsToBePainted.append(std::make_pair(children[j], m_gridItemsIndexesMap.get(children[j]))); 1220 } 1221 } 1222 1223 for (Vector<RenderBox*>::const_iterator it = m_gridItemsOverflowingGridArea.begin(); it != m_gridItemsOverflowingGridArea.end(); ++it) { 1224 if ((*it)->frameRect().intersects(localRepaintRect)) 1225 gridItemsToBePainted.append(std::make_pair(*it, m_gridItemsIndexesMap.get(*it))); 1226 } 1227 1228 // Sort grid items following order-modified document order. 1229 // See http://www.w3.org/TR/css-flexbox/#order-modified-document-order 1230 std::stable_sort(gridItemsToBePainted.begin(), gridItemsToBePainted.end(), GridItemsSorter()); 1231 1232 RenderBox* previous = 0; 1233 for (Vector<std::pair<RenderBox*, size_t> >::const_iterator it = gridItemsToBePainted.begin(); it != gridItemsToBePainted.end(); ++it) { 1234 // We might have duplicates because of spanning children are included in all cells they span. 1235 // Skip them here to avoid painting items several times. 1236 RenderBox* current = (*it).first; 1237 if (current == previous) 1238 continue; 1239 1240 paintChild(current, paintInfo, paintOffset); 1241 previous = current; 1242 } 1243 } 1244 1245 const char* RenderGrid::renderName() const 1246 { 1247 if (isFloating()) 1248 return "RenderGrid (floating)"; 1249 if (isOutOfFlowPositioned()) 1250 return "RenderGrid (positioned)"; 1251 if (isAnonymous()) 1252 return "RenderGrid (generated)"; 1253 if (isRelPositioned()) 1254 return "RenderGrid (relative positioned)"; 1255 return "RenderGrid"; 1256 } 1257 1258 } // namespace WebCore 1259