- Revision
- 143268
- Author
- jchaffr...@webkit.org
- Date
- 2013-02-18 15:15:51 -0800 (Mon, 18 Feb 2013)
Log Message
[CSS Grid Layout] Refactor grid position resolution code to support an internal grid representation
https://bugs.webkit.org/show_bug.cgi?id=109718
Reviewed by Ojan Vafai.
In order to support auto placement (where we can't infer a grid item's position from its style),
we need to have 2 code paths:
- One that places the elements on the grid representation.
- One that reuse the grid representation to return the position.
This code path implements this split so that we can add auto placement in a follow-up patch(es).
Also in order to avoid a O(n^2) behavior [walking over our grid to find a grid item's position],
the cached position code path needed an efficient way to find the grid items -> position mapping.
Refactoring, covered by existing tests.
* rendering/RenderGrid.cpp:
(WebCore::RenderGrid::cachedGridCoordinate):
(WebCore::RenderGrid::resolveGridPositionFromStyle):
These methods implements the above split. The first one
reuses our cached information whereas the other one is
used to build the cache.
(WebCore::RenderGrid::computeIntrinsicLogicalWidths):
(WebCore::RenderGrid::layoutGridItems):
Added some code to clear the grid items' position.
(WebCore::RenderGrid::findChildLogicalPosition):
(WebCore::RenderGrid::logicalContentHeightForChild):
Updated these functions to use cachedGridPosition.
(WebCore::RenderGrid::maximumIndexInDirection):
Added a comment about why we don't use cachedGridPosition.
(WebCore::RenderGrid::insertItemIntoGrid):
Added this helper function to insert into the grid and
cache the position in the reverse lookup map.
(WebCore::RenderGrid::placeItemsOnGrid):
Updated to call insertItemIntoGrid. Also added an ASSERT
similar to m_grid.
(WebCore::RenderGrid::clearGrid):
Added this helper function to clear our grid structure.
* rendering/RenderGrid.h:
(GridCoordinate):
(WebCore::RenderGrid::GridCoordinate::GridCoordinate):
Added this POD to hold the coordinates in our reverse map.
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (143267 => 143268)
--- trunk/Source/WebCore/ChangeLog 2013-02-18 23:07:00 UTC (rev 143267)
+++ trunk/Source/WebCore/ChangeLog 2013-02-18 23:15:51 UTC (rev 143268)
@@ -1,3 +1,55 @@
+2013-02-18 Julien Chaffraix <jchaffr...@webkit.org>
+
+ [CSS Grid Layout] Refactor grid position resolution code to support an internal grid representation
+ https://bugs.webkit.org/show_bug.cgi?id=109718
+
+ Reviewed by Ojan Vafai.
+
+ In order to support auto placement (where we can't infer a grid item's position from its style),
+ we need to have 2 code paths:
+ - One that places the elements on the grid representation.
+ - One that reuse the grid representation to return the position.
+
+ This code path implements this split so that we can add auto placement in a follow-up patch(es).
+ Also in order to avoid a O(n^2) behavior [walking over our grid to find a grid item's position],
+ the cached position code path needed an efficient way to find the grid items -> position mapping.
+
+ Refactoring, covered by existing tests.
+
+ * rendering/RenderGrid.cpp:
+ (WebCore::RenderGrid::cachedGridCoordinate):
+ (WebCore::RenderGrid::resolveGridPositionFromStyle):
+ These methods implements the above split. The first one
+ reuses our cached information whereas the other one is
+ used to build the cache.
+
+ (WebCore::RenderGrid::computeIntrinsicLogicalWidths):
+ (WebCore::RenderGrid::layoutGridItems):
+ Added some code to clear the grid items' position.
+
+ (WebCore::RenderGrid::findChildLogicalPosition):
+ (WebCore::RenderGrid::logicalContentHeightForChild):
+ Updated these functions to use cachedGridPosition.
+
+ (WebCore::RenderGrid::maximumIndexInDirection):
+ Added a comment about why we don't use cachedGridPosition.
+
+ (WebCore::RenderGrid::insertItemIntoGrid):
+ Added this helper function to insert into the grid and
+ cache the position in the reverse lookup map.
+
+ (WebCore::RenderGrid::placeItemsOnGrid):
+ Updated to call insertItemIntoGrid. Also added an ASSERT
+ similar to m_grid.
+
+ (WebCore::RenderGrid::clearGrid):
+ Added this helper function to clear our grid structure.
+
+ * rendering/RenderGrid.h:
+ (GridCoordinate):
+ (WebCore::RenderGrid::GridCoordinate::GridCoordinate):
+ Added this POD to hold the coordinates in our reverse map.
+
2013-02-18 Stephen Chenney <schen...@chromium.org>
feFlood incorrectly applied color-interpolation-filters
Modified: trunk/Source/WebCore/rendering/RenderGrid.cpp (143267 => 143268)
--- trunk/Source/WebCore/rendering/RenderGrid.cpp 2013-02-18 23:07:00 UTC (rev 143267)
+++ trunk/Source/WebCore/rendering/RenderGrid.cpp 2013-02-18 23:15:51 UTC (rev 143268)
@@ -184,7 +184,7 @@
// FIXME: This should add in the scrollbarWidth (e.g. see RenderFlexibleBox).
}
- const_cast<RenderGrid*>(this)->m_grid.clear();
+ const_cast<RenderGrid*>(this)->clearGrid();
}
void RenderGrid::computePreferredLogicalWidths()
@@ -316,8 +316,9 @@
size_t maximumIndex = trackStyles.size();
for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
- GridPosition position = (direction == ForColumns) ? child->style()->gridItemColumn() : child->style()->gridItemRow();
- maximumIndex = std::max(maximumIndex, resolveGridPosition(position) + 1);
+ const GridPosition& position = (direction == ForColumns) ? child->style()->gridItemColumn() : child->style()->gridItemRow();
+ // This function bypasses the cache as it is used to build it. Also 'auto' items will need to be resolved in seperate phases anyway.
+ maximumIndex = std::max(maximumIndex, resolveGridPositionFromStyle(position) + 1);
}
return maximumIndex;
@@ -332,8 +333,8 @@
if (!child->needsLayout())
child->setNeedsLayout(true, MarkOnlyThis);
- size_t columnTrack = resolveGridPosition(ForColumns, child);
- child->setOverrideContainingBlockContentLogicalWidth(columnTracks[columnTrack].m_usedBreadth);
+ const GridCoordinate& coordinate = cachedGridCoordinate(child);
+ child->setOverrideContainingBlockContentLogicalWidth(columnTracks[coordinate.columnIndex].m_usedBreadth);
child->clearOverrideContainingBlockContentLogicalHeight();
child->layout();
return child->logicalHeight();
@@ -469,22 +470,35 @@
}
#endif
+void RenderGrid::insertItemIntoGrid(RenderBox* child, size_t rowTrack, size_t columnTrack)
+{
+ m_grid[rowTrack][columnTrack].append(child);
+ m_gridItemCoordinate.set(child, GridCoordinate(rowTrack, columnTrack));
+}
+
void RenderGrid::placeItemsOnGrid()
{
ASSERT(m_grid.isEmpty());
+ ASSERT(m_gridItemCoordinate.isEmpty());
+
m_grid.grow(maximumIndexInDirection(ForRows));
size_t maximumColumnIndex = maximumIndexInDirection(ForColumns);
for (size_t i = 0; i < gridRowCount(); ++i)
m_grid[i].grow(maximumColumnIndex);
for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
- size_t columnTrack = resolveGridPosition(child->style()->gridItemColumn());
- size_t rowTrack = resolveGridPosition(child->style()->gridItemRow());
-
- m_grid[rowTrack][columnTrack].append(child);
+ size_t columnTrack = resolveGridPositionFromStyle(child->style()->gridItemColumn());
+ size_t rowTrack = resolveGridPositionFromStyle(child->style()->gridItemRow());
+ insertItemIntoGrid(child, rowTrack, columnTrack);
}
}
+void RenderGrid::clearGrid()
+{
+ m_grid.clear();
+ m_gridItemCoordinate.clear();
+}
+
void RenderGrid::layoutGridItems()
{
placeItemsOnGrid();
@@ -499,8 +513,7 @@
for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
LayoutPoint childPosition = findChildLogicalPosition(child, columnTracks, rowTracks);
- size_t columnTrack = resolveGridPosition(child->style()->gridItemColumn());
- size_t rowTrack = resolveGridPosition(child->style()->gridItemRow());
+ const GridCoordinate& childCoordinate = cachedGridCoordinate(child);
// Because the grid area cannot be styled, we don't need to adjust
// the grid breadth to account for 'box-sizing'.
@@ -509,11 +522,11 @@
// FIXME: For children in a content sized track, we clear the overrideContainingBlockContentLogicalHeight
// in minContentForChild / maxContentForChild which means that we will always relayout the child.
- if (oldOverrideContainingBlockContentLogicalWidth != columnTracks[columnTrack].m_usedBreadth || oldOverrideContainingBlockContentLogicalHeight != rowTracks[rowTrack].m_usedBreadth)
+ if (oldOverrideContainingBlockContentLogicalWidth != columnTracks[childCoordinate.columnIndex].m_usedBreadth || oldOverrideContainingBlockContentLogicalHeight != rowTracks[childCoordinate.rowIndex].m_usedBreadth)
child->setNeedsLayout(true, MarkOnlyThis);
- child->setOverrideContainingBlockContentLogicalWidth(columnTracks[columnTrack].m_usedBreadth);
- child->setOverrideContainingBlockContentLogicalHeight(rowTracks[rowTrack].m_usedBreadth);
+ child->setOverrideContainingBlockContentLogicalWidth(columnTracks[childCoordinate.columnIndex].m_usedBreadth);
+ child->setOverrideContainingBlockContentLogicalHeight(rowTracks[childCoordinate.rowIndex].m_usedBreadth);
// FIXME: Grid items should stretch to fill their cells. Once we
// implement grid-{column,row}-align, we can also shrink to fit. For
@@ -530,16 +543,16 @@
// FIXME: We should handle min / max logical height.
setLogicalHeight(logicalHeight() + borderAndPaddingLogicalHeight());
- m_grid.clear();
+ clearGrid();
}
-size_t RenderGrid::resolveGridPosition(TrackSizingDirection direction, const RenderObject* gridItem) const
+RenderGrid::GridCoordinate RenderGrid::cachedGridCoordinate(const RenderBox* gridItem) const
{
- const GridPosition& position = (direction == ForColumns) ? gridItem->style()->gridItemColumn() : gridItem->style()->gridItemRow();
- return resolveGridPosition(position);
+ ASSERT(m_gridItemCoordinate.contains(gridItem));
+ return m_gridItemCoordinate.get(gridItem);
}
-size_t RenderGrid::resolveGridPosition(const GridPosition& position) const
+size_t RenderGrid::resolveGridPositionFromStyle(const GridPosition& position) const
{
// FIXME: Handle other values for grid-{row,column} like ranges or line names.
switch (position.type()) {
@@ -561,14 +574,13 @@
LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks)
{
- size_t columnTrack = resolveGridPosition(child->style()->gridItemColumn());
- size_t rowTrack = resolveGridPosition(child->style()->gridItemRow());
+ const GridCoordinate& coordinate = cachedGridCoordinate(child);
LayoutPoint offset;
// FIXME: |columnTrack| and |rowTrack| should be smaller than our column / row count.
- for (size_t i = 0; i < columnTrack && i < columnTracks.size(); ++i)
+ for (size_t i = 0; i < coordinate.columnIndex && i < columnTracks.size(); ++i)
offset.setX(offset.x() + columnTracks[i].m_usedBreadth);
- for (size_t i = 0; i < rowTrack && i < rowTracks.size(); ++i)
+ for (size_t i = 0; i < coordinate.rowIndex && i < rowTracks.size(); ++i)
offset.setY(offset.y() + rowTracks[i].m_usedBreadth);
// FIXME: Handle margins on the grid item.
Modified: trunk/Source/WebCore/rendering/RenderGrid.h (143267 => 143268)
--- trunk/Source/WebCore/rendering/RenderGrid.h 2013-02-18 23:07:00 UTC (rev 143267)
+++ trunk/Source/WebCore/rendering/RenderGrid.h 2013-02-18 23:15:51 UTC (rev 143268)
@@ -51,6 +51,23 @@
LayoutUnit computePreferredTrackWidth(const Length&, size_t) const;
+ struct GridCoordinate {
+ // HashMap requires a default constuctor.
+ GridCoordinate()
+ : columnIndex(0)
+ , rowIndex(0)
+ {
+ }
+
+ GridCoordinate(size_t row, size_t column)
+ : columnIndex(column)
+ , rowIndex(row)
+ {
+ }
+
+ size_t columnIndex;
+ size_t rowIndex;
+ };
class GridIterator;
enum TrackSizingDirection { ForColumns, ForRows };
void computedUsedBreadthOfGridTracks(TrackSizingDirection, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks);
@@ -58,8 +75,10 @@
LayoutUnit computeUsedBreadthOfMaxLength(TrackSizingDirection, const Length&) const;
LayoutUnit computeUsedBreadthOfSpecifiedLength(TrackSizingDirection, const Length&) const;
void resolveContentBasedTrackSizingFunctions(TrackSizingDirection, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, LayoutUnit& availableLogicalSpace);
+ void insertItemIntoGrid(RenderBox*, size_t rowTrack, size_t columnTrack);
void placeItemsOnGrid();
void layoutGridItems();
+ void clearGrid();
typedef LayoutUnit (RenderGrid::* SizingFunction)(RenderBox*, TrackSizingDirection, Vector<GridTrack>&);
typedef LayoutUnit (GridTrack::* AccumulatorGetter)() const;
@@ -74,8 +93,8 @@
LayoutUnit minContentForChild(RenderBox*, TrackSizingDirection, Vector<GridTrack>& columnTracks);
LayoutUnit maxContentForChild(RenderBox*, TrackSizingDirection, Vector<GridTrack>& columnTracks);
LayoutPoint findChildLogicalPosition(RenderBox*, const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks);
- size_t resolveGridPosition(TrackSizingDirection, const RenderObject*) const;
- size_t resolveGridPosition(const GridPosition&) const;
+ GridCoordinate cachedGridCoordinate(const RenderBox*) const;
+ size_t resolveGridPositionFromStyle(const GridPosition&) const;
#ifndef NDEBUG
bool tracksAreWiderThanMinTrackBreadth(TrackSizingDirection, const Vector<GridTrack>&);
@@ -85,6 +104,7 @@
size_t gridRowCount() const { return m_grid.size(); }
Vector<Vector<Vector<RenderBox*, 1> > > m_grid;
+ HashMap<const RenderBox*, GridCoordinate> m_gridItemCoordinate;
};
} // namespace WebCore