Bug 132057 - CSS JIT: Backtracking with current matching element support for Child fragment.
Summary: CSS JIT: Backtracking with current matching element support for Child fragment.
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: CSS (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Nobody
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-04-23 04:32 PDT by Yusuke Suzuki
Modified: 2014-04-28 18:59 PDT (History)
7 users (show)

See Also:


Attachments
Patch (24.58 KB, patch)
2014-04-23 04:35 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (24.73 KB, patch)
2014-04-23 04:41 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (24.80 KB, patch)
2014-04-23 04:47 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (24.85 KB, patch)
2014-04-23 04:49 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Archive of layout-test-results from webkit-ews-05 for mac-mountainlion (540.65 KB, application/zip)
2014-04-23 05:32 PDT, Build Bot
no flags Details
Archive of layout-test-results from webkit-ews-13 for mac-mountainlion-wk2 (500.40 KB, application/zip)
2014-04-23 06:47 PDT, Build Bot
no flags Details
Patch (26.24 KB, patch)
2014-04-23 09:12 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (26.50 KB, patch)
2014-04-23 10:01 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (41.48 KB, patch)
2014-04-24 05:52 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (43.15 KB, patch)
2014-04-25 02:24 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (43.33 KB, patch)
2014-04-25 02:29 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (43.34 KB, patch)
2014-04-25 02:44 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2014-04-23 04:32:13 PDT
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.
Comment 1 Yusuke Suzuki 2014-04-23 04:35:59 PDT
Created attachment 229975 [details]
Patch
Comment 2 Yusuke Suzuki 2014-04-23 04:41:16 PDT
Created attachment 229976 [details]
Patch
Comment 3 Yusuke Suzuki 2014-04-23 04:43:59 PDT
Rebased patch.
Comment 4 Yusuke Suzuki 2014-04-23 04:47:25 PDT
Created attachment 229977 [details]
Patch
Comment 5 Yusuke Suzuki 2014-04-23 04:49:36 PDT
Created attachment 229978 [details]
Patch
Comment 6 Build Bot 2014-04-23 05:32:36 PDT
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
Comment 7 Build Bot 2014-04-23 05:32:38 PDT
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
Comment 8 Build Bot 2014-04-23 06:47:36 PDT
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
Comment 9 Build Bot 2014-04-23 06:47:38 PDT
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
Comment 10 Yusuke Suzuki 2014-04-23 09:12:47 PDT
Created attachment 229989 [details]
Patch
Comment 11 Yusuke Suzuki 2014-04-23 10:01:30 PDT
Created attachment 229991 [details]
Patch
Comment 12 Yusuke Suzuki 2014-04-23 10:25:31 PDT
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.
Comment 13 Yusuke Suzuki 2014-04-24 02:24:08 PDT
I'll add more LayoutTests related to this patch.
Comment 14 Yusuke Suzuki 2014-04-24 05:52:54 PDT
Created attachment 230071 [details]
Patch

Added LayoutTests, inserting saveDescendantBacktrackingStartFragment assertion
Comment 15 Benjamin Poulain 2014-04-24 16:39:01 PDT
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.
Comment 16 Yusuke Suzuki 2014-04-25 02:23:39 PDT
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.
Comment 17 Yusuke Suzuki 2014-04-25 02:24:50 PDT
Created attachment 230153 [details]
Patch

Revised patch
Comment 18 Yusuke Suzuki 2014-04-25 02:29:46 PDT
Created attachment 230154 [details]
Patch

Revised patch 2, other => postTagName
Comment 19 Yusuke Suzuki 2014-04-25 02:32:37 PDT
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.
Comment 20 Yusuke Suzuki 2014-04-25 02:44:23 PDT
Created attachment 230156 [details]
Patch

Revised patch 3. fix failure cases variable's name
Comment 21 Benjamin Poulain 2014-04-28 17:44:42 PDT
Comment on attachment 230156 [details]
Patch

Great change!
Comment 22 Yusuke Suzuki 2014-04-28 18:01:49 PDT
Comment on attachment 230156 [details]
Patch

Thank you for your review and r+! Could you set cq+?
Comment 23 WebKit Commit Bot 2014-04-28 18:59:07 PDT
Comment on attachment 230156 [details]
Patch

Clearing flags on attachment: 230156

Committed r167920: <http://trac.webkit.org/changeset/167920>
Comment 24 WebKit Commit Bot 2014-04-28 18:59:12 PDT
All reviewed patches have been landed.  Closing bug.