Because compiler previously compute backtracking height for previous child fragment, by leveraging this, we can limit the `maxPrefixSize` for `computeBacktrackingHeightFromDescendant`. For example, consider selector "A>B>C>D>E>F G"'s descendant chain, "A>B>C>D>E>F". In the case of <B>, we calculate the backtracking height such as, pattern: [B, C, D, E, F] candidate0: [C, D, E, F] => not matched candidate1: [D, E, F] => not matched candidate2: [E, F] => matched At this time, first candidate (0)'s pattern size is `pattern.size() - 1`. And get backtracking height from descendant 3 `pattern.size() - candidate.size()`. And next, in the case of <A>, we re-calcucate the backtracking height such as, pattern: [A, B, C, D, E, F] candidate0: [B, C, D, E, F] => not matched candidate1: [C, D, E, F] => not matched candidate2: [D, E, F] => not matched candidate3: [E, F] => matched But we should known that candidate0 ~ candidate1 always fail because part of these patterns are already calculated in <B>'s case and we know that doesn't match. So in the case of <A>, we should start this computation from candidate2, such as, pattern: [A, B, C, D, E, F] candidate2: [D, E, F] => not matched candidate3: [E, F] => matched We can start computation with candidate size = `currentPattern.size() - previousChildFragmentBacktrackingHeightFromDescendant`. In this example, `currentPattern.size()` is 6 and `previousChildFragmentBacktrackingHeightFromDescendant` is 3, so candidate size is `3`.
Created attachment 230789 [details] Patch
Comment on attachment 230789 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=230789&action=review Sorry, I only had a quick look, I had two crazy days. I see what you are going for here, but I am a little puzzled by the change log. Can you explain from the comment bellow? One little thing that would be nice in the changelog is explaining that your reasoning also applies for tagNameNotMatchedBacktrackingStartHeightFromDescendant because the subset before the "not matched" must have matched. > Source/WebCore/ChangeLog:13 > + For example, consider selector "A>B>C>D>E>F G"'s descendant chain, > + "A>B>C>D>E>F". I am somewhat confused by the example... > Source/WebCore/ChangeLog:17 > + pattern: [B, C, D, E, F] Shouldn't the pattern be [F, E, D, C, B, A]? > Source/WebCore/ChangeLog:20 > + candidate2: [E, F] => matched You lost me here, why is [E, F] a matching "prefix"? > Source/WebCore/cssjit/SelectorCompiler.cpp:719 > + for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; largestPrefixSize--) { Traditionally, in Webkit we prefer the prefix increment/decrement instead of suffix operations (because of iterators). It really does not matter here, this is just for info. > Source/WebCore/cssjit/SelectorCompiler.cpp:757 > + RELEASE_ASSERT(tagNames.size() >= previousChildFragmentInDescendantBacktrackingChain->tagNameMatchedBacktrackingStartHeightFromDescendant); Ensuring there is no overflow here is a great use of RELEASE_ASSERT :)
Comment on attachment 230789 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=230789&action=review >> Source/WebCore/ChangeLog:17 >> + pattern: [B, C, D, E, F] > > Shouldn't the pattern be [F, E, D, C, B, A]? Since we now considers about <B>'s backtracking. <A> is not included in tagNames pattern vector. In the implementation detail, this vector is [F, E, D, C, B], but to follow the fragment's order in the selector, we describe it as [B, C, D, E, F] now. >> Source/WebCore/ChangeLog:20 >> + candidate2: [E, F] => matched > > You lost me here, why is [E, F] a matching "prefix"? In this example, "A" doesn't represent actual tag "A". "A" is an identifier for this fragment. Actually, "A" may be "div". In this time, we assume that prefix [E, F] matches to the [B, C] in this example to show the subsequent matching example. >> Source/WebCore/cssjit/SelectorCompiler.cpp:719 >> + for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; largestPrefixSize--) { > > Traditionally, in Webkit we prefer the prefix increment/decrement instead of suffix operations (because of iterators). > > It really does not matter here, this is just for info. Thank you! I also prefer the prefix inc/dec because of C++ iterators, I don't know WebKit also prefer it! I'll change it.
/I don't know/I didn't know/s Oops, mistyped. Sorry for my poor English.
Created attachment 231146 [details] Patch
Can we produce a performance test for this that shows the benefit?
Comment on attachment 231146 [details] Patch Looks good to me.
Comment on attachment 231146 [details] Patch Clearing flags on attachment: 231146 Committed r168606: <http://trac.webkit.org/changeset/168606>
All reviewed patches have been landed. Closing bug.