Bug 132057 – CSS JIT: Backtracking with current matching element support for Child fragment.

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

[Yusuke Suzuki]

Calculate appropriate backtracking start height from descendant.
And at first, we use it for simple optimization.
When backtracking start height equals to current height, we can simply
jump to a descendant element check phase.
And When backtracking start height equals to current height + 1, we
can simply jump to a descendant element traversing phase.

We can apply this optimization to fragments with adjacent combinators.
In the meantime, we start to implement it for a fragment with child
combinator.

[Yusuke Suzuki]

Created attachment 229975 [details]
Patch

[Yusuke Suzuki]

Created attachment 229976 [details]
Patch

[Yusuke Suzuki]

Rebased patch.

[Yusuke Suzuki]

Created attachment 229977 [details]
Patch

[Yusuke Suzuki]

Created attachment 229978 [details]
Patch

[Build Bot]

Comment on attachment 229978 [details]
Patch

Attachment 229978 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/4712604832366592

New failing tests:
fast/selectors/tree-modifying-case-insensitive-selectors.html

[Build Bot]

Created attachment 229981 [details]
Archive of layout-test-results from webkit-ews-05 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-05  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 229978 [details]
Patch

Attachment 229978 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/4862825608511488

New failing tests:
fast/selectors/tree-modifying-case-insensitive-selectors.html
fast/selectors/nondeterministic-combinators.html

[Build Bot]

Created attachment 229985 [details]
Archive of layout-test-results from webkit-ews-13 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-13  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Yusuke Suzuki]

Created attachment 229989 [details]
Patch

[Yusuke Suzuki]

Created attachment 229991 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 229991 [details]
Patch

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

> Source/WebCore/cssjit/SelectorCompiler.cpp:124
> +        , heightFromDescendant(0)

We calculate backtracking start height from closest descendant combinator.

> Source/WebCore/cssjit/SelectorCompiler.cpp:196
> +    void generateElementMatching(Assembler::JumpList& tagNameMatchFailureCases, Assembler::JumpList& otherFailureCases, const SelectorFragment&);

Split failure cases to 1. tagNameMatchFailureCases and 2. otherFailureCases.

> Source/WebCore/cssjit/SelectorCompiler.cpp:603
> +        return BacktrackingAction::NoBacktracking;

For example, ".test > div div", ".test" has no tag name. So its tagNameMatchedBacktrackingStartHeightFromDescendant is InvalidHeight.

> Source/WebCore/cssjit/SelectorCompiler.cpp:607
> +        return BacktrackingAction::JumpToDescendantEntryPoint;

If backtrackingStartHeightFromDescendant equals to current fragment's height, we can use current element for descendant backtracking start element since this fragment's right relation is `Child`.

> Source/WebCore/cssjit/SelectorCompiler.cpp:611
> +        return BacktrackingAction::JumpToDescendantTreeWalkerEntryPoint;

If backtrackingStartHeightFromDescendant equals to current fragment's height + 1, we can use current element for child of descendant backtracking start element. So we jump to `JumpToDescendantTreeWalkerEntryPoint`.

> Source/WebCore/cssjit/SelectorCompiler.cpp:626
> +            fragment.matchingOtherBacktrackingAction = solveDescendantBacktrackingActionForChild(fragment, fragment.tagNameMatchedBacktrackingStartHeightFromDescendant);

More aggressively applying `JumpToDescendantTreeWalkerEntryPoint` and `JumpToDescendantEntryPoint`.
Above old optimization is generalized by `solveDescendantBacktrackingActionForChild`.

> Source/WebCore/cssjit/SelectorCompiler.cpp:664
> +            }

Now we don't apply this optimization to adjacent combinators since we need to start with simple optimization.

> Source/WebCore/cssjit/SelectorCompiler.cpp:703
> +        return StrictlyEqual;

I've changed this from a proposal implementaion.

> Source/WebCore/cssjit/SelectorCompiler.cpp:713
> +        return StrictlyEqual;

Same as above.

> Source/WebCore/cssjit/SelectorCompiler.cpp:-688
> -            needsDescendantTail = false;

I changed these logic. Set `SaveDescendantBacktrackingStart` to flags only when needsDescendantTail becomes true.

> Source/WebCore/cssjit/SelectorCompiler.cpp:855
> +                    m_selectorFragments[j].backtrackingFlags |= BacktrackingFlag::InChainWithDescendantTail;

And mark between saveDescendantBacktrackingStartFragment and current fragment as InChainWithDescendantTail.

> Source/WebCore/cssjit/SelectorCompiler.cpp:857
> +            saveDescendantBacktrackingStartFragmentIndex = 0;

Maybe initialized with std::numeric_limits<unsigned>::max() and inserging ASSERT(saveDescendantBacktrackingStartFragmentIndex != std::numeric_limits<unsigned>::max()); check is better?

> Source/WebCore/cssjit/SelectorCompiler.cpp:960
> +void SelectorCodeGenerator::generateWalkToParentElementWithoutElementCheck(Assembler::RegisterID targetRegister)

Extracted it.

> Source/WebCore/cssjit/SelectorCompiler.cpp:985
> +    linkFailures(failureCases, fragment.matchingOtherBacktrackingAction, matchingOtherFailureCases);

This optimization works here.

> Source/WebCore/cssjit/SelectorCompiler.cpp:1067
> +    linkFailures(failureCases, fragment.matchingOtherBacktrackingAction, matchingOtherFailureCases);

Currently, this optimization doesn't work here. It works as the old implementation works.

[Yusuke Suzuki]

I'll add more LayoutTests related to this patch.

[Yusuke Suzuki]

Created attachment 230071 [details]
Patch

Added LayoutTests, inserting saveDescendantBacktrackingStartFragment assertion

[Benjamin Poulain]

Comment on attachment 230071 [details]
Patch

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

Amazing start. This is a great patch. Some comments bellow:

> Source/WebCore/cssjit/SelectorCompiler.cpp:114
> +static const unsigned InvalidHeight = std::numeric_limits<unsigned>::max();

We do not capitalize the first letter of constant in WebKit.

> Source/WebCore/cssjit/SelectorCompiler.cpp:120
> +        , matchingOtherBacktrackingAction(BacktrackingAction::NoBacktracking)

maybe matchingOtherBacktrackingAction->matchingPostTagNameBacktrackingAction?
To make it more explicit that tag name must go first.

> Source/WebCore/cssjit/SelectorCompiler.cpp:177
> +    void generateWalkToParentElementWithoutElementCheck(Assembler::RegisterID targetRegister);

Without the element check, that would simply be generateWalkToParentNode().

> Source/WebCore/cssjit/SelectorCompiler.cpp:680
> +enum TagNameEquality {

Let's use a typed enum with "enum class".

> Source/WebCore/cssjit/SelectorCompiler.cpp:702
> +        // Since rhs & lhs have actual LocalName,
> +        // inverted lhs never matches on rhs.

This comment could be on a single line.

I believe this comment is useful but it should be in equalTagNamePatterns(). In equalTagNames(), we do not have the context of inverted/non-inverted.

> Source/WebCore/cssjit/SelectorCompiler.cpp:712
> +        // Since rhs & lhs have actual NamespaceURI,
> +        // inverted lhs never matches on rhs.

Ditto.

> Source/WebCore/cssjit/SelectorCompiler.cpp:731
> +static inline unsigned computeBacktrackingStartHeightFromDescendant(const TagNameList& tagNames)

This function could have a comment explaining it finds the largest matching prefix.

> Source/WebCore/cssjit/SelectorCompiler.cpp:733
> +    ASSERT(!tagNames.isEmpty());

You can use RELEASE_ASSERT here.

I try to be very aggressive with release assertion in this compiler to avoid any security issue. We can afford it because we compile very little compared to how many time the compiled code is executed.

> Source/WebCore/cssjit/SelectorCompiler.cpp:735
> +    unsigned size = tagNames.size();

size -> subsetSize?
largestPrefixSize?

> Source/WebCore/cssjit/SelectorCompiler.cpp:744
> +        unsigned amount = tagNames.size() - size;
> +        bool matched = true;
> +        for (unsigned i = 0; i < size; ++i) {
> +            if (!equalTagNamePatterns(tagNames[(tagNames.size() - 1 - i)], tagNames[(tagNames.size() - 1 - i) - amount].tagName)) {
> +                matched = false;
> +                break;
> +            }
> +        }

It would be nice to simplify this loop somehow.

Maybe rename amount to "offsetToLargestPrefix"?
Put "tagNames.size() - 1" in a temporary "lastIndex"?

It would be nice to put "tagNames.size() - 1 - i" and "(tagNames.size() - 1 - i) - amount" in named temporary too. Not sure what would be a good name.

> Source/WebCore/cssjit/SelectorCompiler.cpp:752
> +static inline void computeBacktrackingHeightFromDescendant(SelectorFragment& fragment, TagNameList& tagNames, bool hasDescendantRelationOnTheRight, const SelectorFragment*& previousChildFragment)
> +{

I think this function could start with

if (!hasDescendantRelationOnTheRight)
    return;

The descendant backtracking height is only relevant inside backtracking chains, and a chain can only start with a descendant.


Maybe rename previousChildFragment to previousChildFragmentInBacktrackingChain or previousChildFragmentInDescendantBacktrackingChain?

> Source/WebCore/cssjit/SelectorCompiler.cpp:753
> +    TagNamePattern pattern;

Let's make 2 local declaration in the block where it is used.

> Source/WebCore/cssjit/SelectorCompiler.cpp:765
> +            // tagName is not matched

WebKit comments should be sentences, you need the period at the end.

> Source/WebCore/cssjit/SelectorCompiler.cpp:770
> +        // tagName is matched

Ditto.

> Source/WebCore/cssjit/SelectorCompiler.cpp:838
> -            fragment.backtrackingFlags |= BacktrackingFlag::SaveDescendantBacktrackingStart;
> +            saveDescendantBacktrackingStartFragmentIndex = i;

Here we could have an ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max()).

> Source/WebCore/cssjit/SelectorCompiler.cpp:1008
>      Assembler::JumpList tagMatchingLocalFailureCases;
> -    generateElementMatching(tagMatchingLocalFailureCases, fragment);
> +    generateElementMatching(tagMatchingLocalFailureCases, tagMatchingLocalFailureCases, fragment);
>      tagMatchingLocalFailureCases.linkTo(loopStart, &m_assembler);

Let's rename tagMatchingLocalFailureCases to matchingFailureCases in this case.

[Yusuke Suzuki]

Comment on attachment 230071 [details]
Patch

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

Thank you for your review!
I'll upload a revised patch.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:114
>> +static const unsigned InvalidHeight = std::numeric_limits<unsigned>::max();
> 
> We do not capitalize the first letter of constant in WebKit.

I've fixed.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:120
>> +        , matchingOtherBacktrackingAction(BacktrackingAction::NoBacktracking)
> 
> maybe matchingOtherBacktrackingAction->matchingPostTagNameBacktrackingAction?
> To make it more explicit that tag name must go first.

Renaming to `matchingPostTagNameBacktrackingAction` looks nice.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:177
>> +    void generateWalkToParentElementWithoutElementCheck(Assembler::RegisterID targetRegister);
> 
> Without the element check, that would simply be generateWalkToParentNode().

You're right. To align with C++ code `ContainerNode* parent = parentNode()`, `generateWalkToParentNode` is better.
I've renamed.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:680
>> +enum TagNameEquality {
> 
> Let's use a typed enum with "enum class".

Wow! I don't know we can use C++11 enum class in WebKit.
I've changed to use "enum class".

>> Source/WebCore/cssjit/SelectorCompiler.cpp:702
>> +        // inverted lhs never matches on rhs.
> 
> This comment could be on a single line.
> 
> I believe this comment is useful but it should be in equalTagNamePatterns(). In equalTagNames(), we do not have the context of inverted/non-inverted.

Move this comment to `equalTagNamePatterns`.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:731
>> +static inline unsigned computeBacktrackingStartHeightFromDescendant(const TagNameList& tagNames)
> 
> This function could have a comment explaining it finds the largest matching prefix.

Right. Added comment.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:733
>> +    ASSERT(!tagNames.isEmpty());
> 
> You can use RELEASE_ASSERT here.
> 
> I try to be very aggressive with release assertion in this compiler to avoid any security issue. We can afford it because we compile very little compared to how many time the compiled code is executed.

Ah, I've got it. Changed to RELEASE_ASSERT.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:735
>> +    unsigned size = tagNames.size();
> 
> size -> subsetSize?
> largestPrefixSize?

Changed to largestPrefixSize.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:744
>> +        }
> 
> It would be nice to simplify this loop somehow.
> 
> Maybe rename amount to "offsetToLargestPrefix"?
> Put "tagNames.size() - 1" in a temporary "lastIndex"?
> 
> It would be nice to put "tagNames.size() - 1 - i" and "(tagNames.size() - 1 - i) - amount" in named temporary too. Not sure what would be a good name.

Changed. Introducing lastIndex, offsetToLargestPrefix and currentIndex.

In this loop, we check prefix matches to tagNames with the reverse order.

e.g.
TagNames [ p , div, div,  p ]
Index      3    2    1    0

And we create prefix from this, such as
Prefix   [ div, div, p ]
Index       2    1   0

And we need to check this prefix matches to TagNames with the reverse order (from index 3 to 1 in TagNames)
TagNames [ p , div, div,  p ]
T-Index    3    2    1    0
Prefix   [div, div,  p  ]
P-Index    2    1    0

In this code, currentIndex changes from 3 to 1, currentIndex - offsetToLargestPrefix changes from 2 to 0.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:752
>> +{
> 
> I think this function could start with
> 
> if (!hasDescendantRelationOnTheRight)
>     return;
> 
> The descendant backtracking height is only relevant inside backtracking chains, and a chain can only start with a descendant.
> 
> 
> Maybe rename previousChildFragment to previousChildFragmentInBacktrackingChain or previousChildFragmentInDescendantBacktrackingChain?

Right! I've fixed this.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:753
>> +    TagNamePattern pattern;
> 
> Let's make 2 local declaration in the block where it is used.

Yes. Moved it.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:765
>> +            // tagName is not matched
> 
> WebKit comments should be sentences, you need the period at the end.

Changed comment contents.

[Yusuke Suzuki]

Created attachment 230153 [details]
Patch

Revised patch

[Yusuke Suzuki]

Created attachment 230154 [details]
Patch

Revised patch 2, other => postTagName

[Yusuke Suzuki]

Comment on attachment 230071 [details]
Patch

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

>> Source/WebCore/cssjit/SelectorCompiler.cpp:838
>> +            saveDescendantBacktrackingStartFragmentIndex = i;
> 
> Here we could have an ASSERT(saveDescendantBacktrackingStartFragmentIndex == std::numeric_limits<unsigned>::max()).

Right! Inserted ASSERT here.

>> Source/WebCore/cssjit/SelectorCompiler.cpp:1008
>>      tagMatchingLocalFailureCases.linkTo(loopStart, &m_assembler);
> 
> Let's rename tagMatchingLocalFailureCases to matchingFailureCases in this case.

Renamed to matchingFailureCases.

[Yusuke Suzuki]

Created attachment 230156 [details]
Patch

Revised patch 3. fix failure cases variable's name

[Benjamin Poulain]

Comment on attachment 230156 [details]
Patch

Great change!

[Yusuke Suzuki]

Comment on attachment 230156 [details]
Patch

Thank you for your review and r+! Could you set cq+?

[WebKit Commit Bot]

Comment on attachment 230156 [details]
Patch

Clearing flags on attachment: 230156

Committed r167920: <http://trac.webkit.org/changeset/167920>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.