Bug 209572 – [css-grid] Problems when referencing grid line names with auto repeat()

• Status: RESOLVED
• Resolution: FIXED
• Component: CSS

[Oriol Brufau]

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

[Oriol Brufau]

Created attachment 394562 [details]
Patch

[Darin Adler]

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.

[Oriol Brufau]

Created attachment 394564 [details]
Patch

[Oriol Brufau]

(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

[Darin Adler]

(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.

[Oriol Brufau]

(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.

[Darin Adler]

(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.

[Oriol Brufau]

(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.

[Oriol Brufau]

*** Bug 209756 has been marked as a duplicate of this bug. ***

[Oriol Brufau]

Created attachment 400396 [details]
Patch

[Oriol Brufau]

Created attachment 400397 [details]
Patch

[Oriol Brufau]

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.

[EWS]

/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).

[Oriol Brufau]

Created attachment 400505 [details]
Patch

[EWS]

Committed r262262: <https://trac.webkit.org/changeset/262262>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 400505 [details].

[Radar WebKit Bug Importer]

<rdar://problem/63734311>