There are some problems when referencing named grid lines with the presence of the auto repeat() syntax: - If the 1st track is defined with auto repeat(), then the code assumes that the referenced line appears after the repeated tracks. But it may actually precede them. - If the referenced line appears both inside and outside the auto repeat(), then it can resolve to the outside raw index, without expanding the auto repeat(). - The logic for placing a placement property set to both an integer and an identifier is wrong with auto repeat(). - The indices of both implicit grid lines defined in grid-template-areas and explicit ones defined in grid-template-rows/columns are stored together in NamedGridColumnLines and NamedGridRowLines. This is problematic because the former indices already refer to the final explicit grid so they don't have to be increased when expanding an auto repeat(), but the latter ones should. This causes some WPT failures: https://wpt.fyi/results/css/css-grid/placement/grid-placement-using-named-grid-lines-002.html https://wpt.fyi/results/css/css-grid/placement/grid-placement-using-named-grid-lines-004.html https://wpt.fyi/results/css/css-grid/placement/grid-placement-using-named-grid-lines-005.html Chromium was already fixed in https://crbug.com/966090
Created attachment 394562 [details] Patch
Comment on attachment 394562 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=394562&action=review Looks good assuming these new tests all pass. > Source/WebCore/rendering/style/GridPositionsResolver.cpp:76 > + m_implicitNamedLinesIndexes = implicitGridLinesIterator == implicitGridLineNames.end() ? nullptr : &implicitGridLinesIterator->value; It’s really risky to store a pointer to a value slot in a HashMap. If any change is made to the map, adding or removing anything, rehashing means the pointer can end up invalid. Worse, it’s basically unpredictable how often this will happen so you could do a lot of testing and never observe it. How does the new code and existing code protect itself from this? > Source/WebCore/rendering/style/GridPositionsResolver.cpp:93 > bool NamedLineCollection::contains(unsigned line) const I’m concerned about how many times this loops through a vector. Seems like it could have poor performance, O(n^2), if we have a lot of these. There’s a reason we use maps and sets so much in WebKit. Sometimes they are bad for simple cases, but they help us avoid creating O(n^2) algorithms by accident. What prevents this from leading to pathological performance problems in large grids? > Source/WebCore/rendering/style/GridPositionsResolver.cpp:100 > + auto find = [](const Vector<unsigned>* indexes, size_t line) { Normally we’d call this operation "contains" rather than "find" since it returns a boolean. Why are we mixing unsigned and size_t for line? Should just use unsigned. > Source/WebCore/rendering/style/GridPositionsResolver.h:62 > + const Vector<unsigned>* m_implicitNamedLinesIndexes = { nullptr }; Don’t need the "=" here. The two lines above don’t have it.
Created attachment 394564 [details] Patch
(In reply to Darin Adler from comment #2) > Comment on attachment 394562 [details] > Patch > > View in context: > https://bugs.webkit.org/attachment.cgi?id=394562&action=review > > Looks good assuming these new tests all pass. They pass locally. > > Source/WebCore/rendering/style/GridPositionsResolver.cpp:76 > > + m_implicitNamedLinesIndexes = implicitGridLinesIterator == implicitGridLineNames.end() ? nullptr : &implicitGridLinesIterator->value; > > It’s really risky to store a pointer to a value slot in a HashMap. If any > change is made to the map, adding or removing anything, rehashing means the > pointer can end up invalid. Worse, it’s basically unpredictable how often > this will happen so you could do a lot of testing and never observe it. How > does the new code and existing code protect itself from this? Not completely sure. I didn't write the existing code, now I'm just trying to copy that. But layout only has acces to a const RenderStyle, so it seems unlikely for the map to change. > > Source/WebCore/rendering/style/GridPositionsResolver.cpp:93 > > bool NamedLineCollection::contains(unsigned line) const > > I’m concerned about how many times this loops through a vector. Seems like > it could have poor performance, O(n^2), if we have a lot of these. There’s a > reason we use maps and sets so much in WebKit. Sometimes they are bad for > simple cases, but they help us avoid creating O(n^2) algorithms by accident. > What prevents this from leading to pathological performance problems in > large grids? Can you clarify the O(n^2)? It seems to me that the worst that can happen is that we may iterate all m_implicitNamedLinesIndexes, m_namedLinesIndexes, and m_autoRepeatNamedLinesIndexes. If each vector has size n, wouldn't that be O(3n)? > > Source/WebCore/rendering/style/GridPositionsResolver.cpp:100 > > + auto find = [](const Vector<unsigned>* indexes, size_t line) { > > Normally we’d call this operation "contains" rather than "find" since it > returns a boolean. Done. > Why are we mixing unsigned and size_t for line? Should just use unsigned. Done. > > > Source/WebCore/rendering/style/GridPositionsResolver.h:62 > > + const Vector<unsigned>* m_implicitNamedLinesIndexes = { nullptr }; > > Don’t need the "=" here. The two lines above don’t have it. Done. Also added some initializing stuff in StyleGridData.cpp
(In reply to Oriol Brufau from comment #4) > > > Source/WebCore/rendering/style/GridPositionsResolver.cpp:93 > > > bool NamedLineCollection::contains(unsigned line) const > > > > I’m concerned about how many times this loops through a vector. Seems like > > it could have poor performance, O(n^2), if we have a lot of these. There’s a > > reason we use maps and sets so much in WebKit. Sometimes they are bad for > > simple cases, but they help us avoid creating O(n^2) algorithms by accident. > > What prevents this from leading to pathological performance problems in > > large grids? > > Can you clarify the O(n^2)? It seems to me that the worst that can happen is > that > we may iterate all m_implicitNamedLinesIndexes, m_namedLinesIndexes, and > m_autoRepeatNamedLinesIndexes. If each vector has size n, wouldn't that be > O(3n)? I’m assuming the number of times this contains function is called is also proportion to the size of the grid/document.
(In reply to Darin Adler from comment #5) > I’m assuming the number of times this contains function is called is also > proportion to the size of the grid/document. Ah, you mean having a grid with n named lines and n grid items referencing named lines. Then yes, it seems O(n^2), but that was already the case before this patch.
(In reply to Oriol Brufau from comment #6) > (In reply to Darin Adler from comment #5) > > I’m assuming the number of times this contains function is called is also > > proportion to the size of the grid/document. > > Ah, you mean having a grid with n named lines and n grid items referencing > named lines. Then yes, it seems O(n^2), but that was already the case before > this patch. That’s right. I wasn’t limiting my remarks to the patch, but rather about the algorithms in the code including but not limited to the new bits in the patch.
(In reply to Oriol Brufau from comment #6) > Ah, you mean having a grid with n named lines and n grid items referencing > named lines. Then yes, it seems O(n^2), but that was already the case before > this patch. Looking better at it, with a single grid item suffices. Because lookAheadForNamedGridLine and lookBackForNamedGridLine call NamedLineCollection::contains in a loop. So using 'grid-column: foo n' means n calls, each of which iterates the vectors. This should definitely be addressed before increasing the maximum number of tracks.
*** Bug 209756 has been marked as a duplicate of this bug. ***
Created attachment 400396 [details] Patch
Created attachment 400397 [details] Patch
I have rebased the patch and included https://crrev.com/771984 Darin, regarding the HashMap value pointers, are you fine with deferring their substitution to another bug? They are already being used right now anyways, I'm only adding a 3rd one.
/Volumes/Data/worker/Commit-Queue/build/LayoutTests/imported/w3c/ChangeLog neither lists a valid reviewer nor contains the string "Unreviewed" or "Rubber stamp" (case insensitive).
Created attachment 400505 [details] Patch
Committed r262262: <https://trac.webkit.org/changeset/262262> All reviewed patches have been landed. Closing bug and clearing flags on attachment 400505 [details].
<rdar://problem/63734311>