Modified: trunk/Source/WebCore/ChangeLog (168605 => 168606)
--- trunk/Source/WebCore/ChangeLog 2014-05-12 00:08:02 UTC (rev 168605)
+++ trunk/Source/WebCore/ChangeLog 2014-05-12 04:23:12 UTC (rev 168606)
@@ -1,3 +1,64 @@
+2014-05-11 Yusuke Suzuki <utatane....@gmail.com>
+
+ CSS JIT: reduce cost of computing backtracking height
+ https://bugs.webkit.org/show_bug.cgi?id=132546
+
+ Reviewed by Benjamin Poulain.
+
+ Because compiler previously compute backtracking height for
+ previous child fragment, by leveraging this, we can limit the
+ `maxPrefixSize` for `computeBacktrackingHeightFromDescendant`.
+
+ For example, consider selector "c>a>b>d>a>b e"'s descendant chain,
+ "c>a>b>d>a>b".
+
+ At the <a> position, we have matching pattern [b, a, d, b, a] and
+ calculate the backtracking height by following method.
+
+ pattern: [b, a, d, b, a]
+ candidate0: [b, a, d, b] => Not matched.
+ candidate1: [b, a, d] => Not matched.
+ candidate2: [b, a] => Matched against the pattern.
+
+ At this time, first candidate0's pattern size is `pattern.size() - 1`.
+ And get backtracking height from descendant 3, that is
+ `pattern.size() - candidate.size()`, `5 - 2`.
+
+ And next, at the <c> position, we calcucate the backtracking height
+ for this pattern.
+
+ pattern: [b, a, d, b, a, c]
+ candidate0: [b, a, d, b, a] => Not matched.
+ candidate1: [b, a, d, b] => Not matched.
+ candidate2: [b, a, d] => Not matched.
+ candidate3: [b, a] => Not matched.
+ candidate4: [b] => Not matched.
+ candidate5: [] => Matched against the pattern.
+
+ Then, we get the backtracking height, which is 6 (6 - 0).
+ However, in the above case, we already know that attempts from candidate0
+ to candidate1 always fail, since parts of these are already tested at
+ the <b> position trial and we know they don't match.
+
+ So in this case, we should start this computation from candidate2,
+ such as,
+
+ pattern: [b, a, d, b, a, c]
+ candidate2: [b, a, d] => Not matched.
+ candidate3: [b, a] => Not matched.
+ candidate4: [b] => Not matched.
+ candidate5: [] => Matched against the pattern.
+
+ We can start computation with candidate size
+ `pattern.size() - previousChildFragmentBacktrackingHeight`.
+ In this example, `pattern.size()` is 6 and
+ `previousChildFragmentBacktrackingHeight` is 3, so candidate size is
+ 3, that is candidate2.
+
+ * cssjit/SelectorCompiler.cpp:
+ (WebCore::SelectorCompiler::computeBacktrackingStartHeightFromDescendant):
+ (WebCore::SelectorCompiler::computeBacktrackingHeightFromDescendant):
+
2014-05-11 Beth Dakin <bda...@apple.com>
Headers and footers are not positioned correctly with topContentInset
Modified: trunk/Source/WebCore/cssjit/SelectorCompiler.cpp (168605 => 168606)
--- trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-05-12 00:08:02 UTC (rev 168605)
+++ trunk/Source/WebCore/cssjit/SelectorCompiler.cpp 2014-05-12 04:23:12 UTC (rev 168606)
@@ -711,12 +711,12 @@
// Find the largest matching prefix from already known tagNames.
// And by using this, compute an appropriate height of backtracking start element from the closest descendant.
-static inline unsigned computeBacktrackingStartHeightFromDescendant(const TagNameList& tagNames)
+static inline unsigned computeBacktrackingStartHeightFromDescendant(const TagNameList& tagNames, unsigned maxPrefixSize)
{
RELEASE_ASSERT(!tagNames.isEmpty());
+ RELEASE_ASSERT(maxPrefixSize < tagNames.size());
- unsigned largestPrefixSize = tagNames.size();
- while (--largestPrefixSize) {
+ for (unsigned largestPrefixSize = maxPrefixSize; largestPrefixSize > 0; --largestPrefixSize) {
unsigned offsetToLargestPrefix = tagNames.size() - largestPrefixSize;
bool matched = true;
// Since TagNamePatterns are pushed to a tagNames, check tagNames with reverse order.
@@ -752,15 +752,21 @@
pattern.tagName = fragment.tagName;
tagNames.append(pattern);
+ unsigned maxPrefixSize = tagNames.size() - 1;
+ if (previousChildFragmentInDescendantBacktrackingChain) {
+ RELEASE_ASSERT(tagNames.size() >= previousChildFragmentInDescendantBacktrackingChain->tagNameMatchedBacktrackingStartHeightFromDescendant);
+ maxPrefixSize = tagNames.size() - previousChildFragmentInDescendantBacktrackingChain->tagNameMatchedBacktrackingStartHeightFromDescendant;
+ }
+
if (pattern.tagName) {
// Compute height from descendant in the case that tagName is not matched.
tagNames.last().inverted = true;
- fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames);
+ fragment.tagNameNotMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames, maxPrefixSize);
}
// Compute height from descendant in the case that tagName is matched.
tagNames.last().inverted = false;
- fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames);
+ fragment.tagNameMatchedBacktrackingStartHeightFromDescendant = computeBacktrackingStartHeightFromDescendant(tagNames, maxPrefixSize);
fragment.heightFromDescendant = tagNames.size() - 1;
previousChildFragmentInDescendantBacktrackingChain = &fragment;
} else {
