Bug 133543 – [CSS Grid Layout] Simplify the named grid lines resolution algorithm

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

[Sergio Villar Senin]

The support for placing grid items using named grid lines was added in r164869 and later improved in r166299. Despite being correct the code turned out to be quite complex. It's difficult to understand and maintain. It can be heavily simplified if we previously insert the implicit named grid lines generated by grid areas into the list of user-defined named grid lines. If we do that we could directly apply the algorithm described in the spec http://dev.w3.org/csswg/css-grid/#grid-placement-slot

As a nice side effect, we'll get for free the use case specified in section "5.2.2 Implicit Named Areas", i.e., explicitly adding named lines of the form (foo-start/foo-end) will effectively create a named grid area.

[Sergio Villar Senin]

Created attachment 232536 [details]
Patch

[Radu Stavila]

Comment on attachment 232536 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=232536&action=review

> Source/WebCore/css/StyleResolver.cpp:2684
> +        if (!namedGridAreas.isEmpty())

I don't think this condition is necessary. It would be faster to just let it through with the call to createImplicitNamedGridLinesFromGridArea, as it won't fork the code path and it would return immediately anyway.

> Source/WebCore/css/StyleResolver.cpp:2711
> +        if (!namedGridAreas.isEmpty())

Ditto.

> Source/WebCore/rendering/RenderGrid.cpp:868
> +    return lineName + ((side == ColumnStartSide || side == RowStartSide) ? "-start" : "-end");

For consistency, I think you should add an isStartSide(GridPositionSide) method, similar to isColumnSide.

> Source/WebCore/rendering/RenderGrid.cpp:980
> +        // First attempt to match the grid areaâs edge to a named grid area: if there is a named line with the name

"â" character instead of '

It shows up multiple times in the comments.

[Sergio Villar Senin]

Thanks for the review.

(In reply to comment #2)
> (From update of attachment 232536 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=232536&action=review
> 
> > Source/WebCore/css/StyleResolver.cpp:2684
> > +        if (!namedGridAreas.isEmpty())
> 
> I don't think this condition is necessary. It would be faster to just let it through with the call to createImplicitNamedGridLinesFromGridArea, as it won't fork the code path and it would return immediately anyway.

I am not sure that is true, I don't think there is a unique answer for that as it depends a lot on the branch-prediction features of the CPU architecture and so on.

> > Source/WebCore/rendering/RenderGrid.cpp:868
> > +    return lineName + ((side == ColumnStartSide || side == RowStartSide) ? "-start" : "-end");
> 
> For consistency, I think you should add an isStartSide(GridPositionSide) method, similar to isColumnSide.

Good point.
 
> > Source/WebCore/rendering/RenderGrid.cpp:980
> > +        // First attempt to match the grid areaâs edge to a named grid area: if there is a named line with the name
> 
> "â" character instead of '
> 
> It shows up multiple times in the comments.

Weird likely some issue copy-pasting. I'll fix that.

[Sergio Villar Senin]

Created attachment 232559 [details]
Patch

[Darin Adler]

Comment on attachment 232559 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=232559&action=review

I’ll say review+, but the use of a vector and a std::sort each time we add something is definitely not the right data structure / algorithm choice.

> Source/WebCore/css/StyleResolver.cpp:1862
> +    for (auto it = namedGridAreas.begin(), end = namedGridAreas.end(); it != end; ++it) {

This should use a modern for loop:

    for (auto& area : namedGridAreas)

Then below instead of "it->" it would be "area."

> Source/WebCore/css/StyleResolver.cpp:1868
> +        {
> +            NamedGridLinesMap::AddResult startResult = namedGridLines.add(it->key + "-start", Vector<size_t>());
> +            startResult.iterator->value.append(areaSpan.initialPositionIndex);
> +            std::sort(startResult.iterator->value.begin(), startResult.iterator->value.end());
> +        }

This code only uses the value, so I would write more like this:

    auto& startVector = namedGridLines.add(it->key + "-start", Vector<size_t>()).iterator->value;
    startVector.append(areaSpan.initialPositionIndex);
    std::sort(vector.begin(), vector.end());

But also, to keep a vector sorted, it is *not* efficient to use keep adding items to the end and then doing a std::sort on the whole vector each time. There are webpages telling you not to do this, such as <http://stackoverflow.com/questions/2710221/is-there-a-sorted-vector-class-which-supports-insert-etc>. Please rethink the data structure here.

I also don’t understand the reason for the use of size_t for this. Is it the size of some memory object? If not, then it should be some other type, maybe unsigned or even uint64_t.

> Source/WebCore/css/StyleResolver.cpp:1873
> +        {
> +            NamedGridLinesMap::AddResult endResult = namedGridLines.add(it->key + "-end", Vector<size_t>());
> +            endResult.iterator->value.append(areaSpan.finalPositionIndex + 1);
> +            std::sort(endResult.iterator->value.begin(), endResult.iterator->value.end());
> +        }

Same comment again.

> Source/WebCore/css/StyleResolver.cpp:2776
> +        NamedGridLinesMap namedGridColumnLines = state.style()->namedGridColumnLines();
> +        NamedGridLinesMap namedGridRowLines = state.style()->namedGridRowLines();

This looks kind of expensive. Do we really want to copy hash maps here?

> Source/WebCore/rendering/RenderGrid.cpp:988
> +        const String namedGridLine = position.namedGridLine();

Not sure why this is "const String" instead of just String.

> Source/WebCore/rendering/RenderGrid.cpp:992
> +        auto implicitLineIter = gridLineNames.find(implicitNamedGridLineForSide(namedGridLine, side));

The use of "xxxIter" here is not a normal naming style we use in WebKit. I think you could just leave off the Iter suffix, or use the entire word Iterator, or think of another way to name it.

[Darin Adler]

For example, if the only reason for sorting is that we always want to be able to find the first item, then what we want is a heap, and STL has heap algorithms for us to use to maintain the heap (std::push_heap and friends).

[Sergio Villar Senin]

(In reply to comment #5)
> (From update of attachment 232559 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=232559&action=review
> 
> I’ll say review+, but the use of a vector and a std::sort each time we add something is definitely not the right data structure / algorithm choice.
> 
> > Source/WebCore/css/StyleResolver.cpp:1862
> > +    for (auto it = namedGridAreas.begin(), end = namedGridAreas.end(); it != end; ++it) {
> 
> This should use a modern for loop:
> 
>     for (auto& area : namedGridAreas)
> 
> Then below instead of "it->" it would be "area."

I had thought about that but I needed both the key and the value and I didn't remember the KeyValuePair thing :)

> > Source/WebCore/css/StyleResolver.cpp:1868
> > +        {
> > +            NamedGridLinesMap::AddResult startResult = namedGridLines.add(it->key + "-start", Vector<size_t>());
> > +            startResult.iterator->value.append(areaSpan.initialPositionIndex);
> > +            std::sort(startResult.iterator->value.begin(), startResult.iterator->value.end());
> > +        }
> 
> This code only uses the value, so I would write more like this:
> 
>     auto& startVector = namedGridLines.add(it->key + "-start", Vector<size_t>()).iterator->value;
>     startVector.append(areaSpan.initialPositionIndex);
>     std::sort(vector.begin(), vector.end());
> 
> But also, to keep a vector sorted, it is *not* efficient to use keep adding items to the end and then doing a std::sort on the whole vector each time. There are webpages telling you not to do this, such as <http://stackoverflow.com/questions/2710221/is-there-a-sorted-vector-class-which-supports-insert-etc>. Please rethink the data structure here.

I know, ideally we'd be using a std::set but std:: data types are not allowed in the project, aren't they?

> I also don’t understand the reason for the use of size_t for this. Is it the size of some memory object? If not, then it should be some other type, maybe unsigned or even uint64_t.

It's just an index, as we don't expect grids to be extremely huge I guess it would be more than enough to have an unsigned there, but I'd change it in a different patch.

> > Source/WebCore/css/StyleResolver.cpp:1873
> > +        {
> > +            NamedGridLinesMap::AddResult endResult = namedGridLines.add(it->key + "-end", Vector<size_t>());
> > +            endResult.iterator->value.append(areaSpan.finalPositionIndex + 1);
> > +            std::sort(endResult.iterator->value.begin(), endResult.iterator->value.end());
> > +        }
> 
> Same comment again.
> 
> > Source/WebCore/css/StyleResolver.cpp:2776
> > +        NamedGridLinesMap namedGridColumnLines = state.style()->namedGridColumnLines();
> > +        NamedGridLinesMap namedGridRowLines = state.style()->namedGridRowLines();
> 
> This looks kind of expensive. Do we really want to copy hash maps here?

No, we don't but the style returns a const reference, so there is no other way to change it than to do a copy+set() unless we add something like mutableNamedGridColumnLines(). I thought about that but there is only one method in the whole RenderStyle like that, so it seems that is really uncommon.
 
> > Source/WebCore/rendering/RenderGrid.cpp:988
> > +        const String namedGridLine = position.namedGridLine();
> 
> Not sure why this is "const String" instead of just String.

No particular reason.
 
> > Source/WebCore/rendering/RenderGrid.cpp:992
> > +        auto implicitLineIter = gridLineNames.find(implicitNamedGridLineForSide(namedGridLine, side));
> 
> The use of "xxxIter" here is not a normal naming style we use in WebKit. I think you could just leave off the Iter suffix, or use the entire word Iterator, or think of another way to name it.

Will change that.

[Sergio Villar Senin]

(In reply to comment #6)
> For example, if the only reason for sorting is that we always want to be able to find the first item, then what we want is a heap, and STL has heap algorithms for us to use to maintain the heap (std::push_heap and friends).

Unfortunately that's not the case. We need to keep all the indexes sorted.

Another option could be to perform all the insertions and then in another loop do a single sort per vector.

In any case, although I totally agree that the usage is not correct, in practice those vectors won't be very bug I'd say.

[Sergio Villar Senin]

Comment on attachment 232559 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=232559&action=review

>>> Source/WebCore/css/StyleResolver.cpp:1868
>>> +        }
>> 
>> This code only uses the value, so I would write more like this:
>> 
>>     auto& startVector = namedGridLines.add(it->key + "-start", Vector<size_t>()).iterator->value;
>>     startVector.append(areaSpan.initialPositionIndex);
>>     std::sort(vector.begin(), vector.end());
>> 
>> But also, to keep a vector sorted, it is *not* efficient to use keep adding items to the end and then doing a std::sort on the whole vector each time. There are webpages telling you not to do this, such as <http://stackoverflow.com/questions/2710221/is-there-a-sorted-vector-class-which-supports-insert-etc>. Please rethink the data structure here.
>> 
>> I also don’t understand the reason for the use of size_t for this. Is it the size of some memory object? If not, then it should be some other type, maybe unsigned or even uint64_t.
> 
> I know, ideally we'd be using a std::set but std:: data types are not allowed in the project, aren't they?

Also note that we only insert 1 item and sort each vector once. As we iterate over grid areas with different names, we'll be accessing different vectors all the time.

[Sergio Villar Senin]

Committed r169744: <http://trac.webkit.org/changeset/169744>