Changeset 77740 in webkit
- Timestamp:
- Feb 5, 2011 3:23:43 AM (13 years ago)
- Location:
- trunk/Source/WebCore
- Files:
-
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WebCore/ChangeLog
r77738 r77740 1 2011-02-05 Antti Koivisto <antti@apple.com> 2 3 Reviewed by Dave Hyatt. 4 5 Optimize matching of descendant selectors 6 https://bugs.webkit.org/show_bug.cgi?id=49876 7 <rdar://problem/8772822> 8 9 During style recalculation, maintain a filter of tags, ids and classes seen in ancestor elements. 10 Use the filter to quickly reject descendant and child selectors when doing style matching. 11 12 This speeds up style recalculations 3-6x on many major web sites. 13 14 * css/CSSStyleSelector.cpp: 15 (WebCore::RuleData::RuleData): 16 (WebCore::RuleData::descendantSelectorIdentifierHashes): 17 (WebCore::collectElementIdentifiers): 18 (WebCore::CSSStyleSelector::pushParent): 19 (WebCore::CSSStyleSelector::popParent): 20 (WebCore::CSSStyleSelector::fastRejectSelector): 21 (WebCore::CSSStyleSelector::matchRulesForList): 22 (WebCore::RuleData::collectDescendantSelectorIdentifierHashes): 23 * css/CSSStyleSelector.h: 24 (WebCore::CSSStyleSelector::ParentStackFrame::ParentStackFrame): 25 * dom/Element.cpp: 26 (WebCore::StyleSelectorParentPusher::StyleSelectorParentPusher): 27 (WebCore::StyleSelectorParentPusher::push): 28 (WebCore::StyleSelectorParentPusher::~StyleSelectorParentPusher): 29 (WebCore::Element::attach): 30 (WebCore::Element::recalcStyle): 31 1 32 2011-02-05 Nate Chapin <japhet@chromium.org> 2 33 -
trunk/Source/WebCore/css/CSSStyleSelector.cpp
r77664 r77740 360 360 , m_position(position) 361 361 { 362 } 362 collectDescendantSelectorIdentifierHashes(); 363 } 364 void collectDescendantSelectorIdentifierHashes(); 363 365 unsigned position() const { return m_position; } 364 366 CSSStyleRule* rule() const { return m_rule; } 365 367 CSSSelector* selector() const { return m_selector; } 368 369 // Try to balance between memory usage (there can be lots of RuleData objects) and good filtering performance. 370 static const unsigned maximumIdentifierCount = 4; 371 const unsigned* descendantSelectorIdentifierHashes() const { return m_descendantSelectorIdentifierHashes; } 366 372 367 373 private: … … 369 375 CSSSelector* m_selector; 370 376 unsigned m_position; 377 // Use plain array instead of a Vector to minimize memory overhead. 378 unsigned m_descendantSelectorIdentifierHashes[maximumIdentifierCount]; 371 379 }; 372 380 … … 643 651 defaultViewSourceStyle->addRulesFromSheet(parseUASheet(sourceUserAgentStyleSheet, sizeof(sourceUserAgentStyleSheet)), screenEval()); 644 652 } 653 654 static inline void collectElementIdentifierHashes(Element* element, Vector<unsigned, 4>& identifierHashes) 655 { 656 identifierHashes.append(element->localName().impl()->existingHash()); 657 if (element->hasID()) 658 identifierHashes.append(element->idForStyleResolution().impl()->existingHash()); 659 StyledElement* styledElement = element->isStyledElement() ? static_cast<StyledElement*>(element) : 0; 660 if (styledElement && styledElement->hasClass()) { 661 const SpaceSplitString& classNames = static_cast<StyledElement*>(element)->classNames(); 662 size_t count = classNames.size(); 663 for (size_t i = 0; i < count; ++i) 664 identifierHashes.append(classNames[i].impl()->existingHash()); 665 } 666 } 667 668 void CSSStyleSelector::pushParent(Element* parent) 669 { 670 // If we are not invoked consistently for each parent, just pause maintaining the stack. 671 // There are all kinds of wacky special cases where the style recalc may temporarily branch to some random elements. 672 // FIXME: Perhaps we should fix up the stack instead? There is some danger of getting into O(n^2) situations doing that. 673 if (m_parentStack.isEmpty()) { 674 ASSERT(m_ancestorIdentifierFilter.isEmpty()); 675 // We must start from the root. 676 if (parent->parentElement()) 677 return; 678 } else if (m_parentStack.last().element != parent->parentElement()) 679 return; 680 681 m_parentStack.append(ParentStackFrame(parent)); 682 ParentStackFrame& parentFrame = m_parentStack.last(); 683 // Mix tags, class names and ids into some sort of weird bouillabaisse. 684 // The filter is used for fast rejection of child and descendant selectors. 685 collectElementIdentifierHashes(parent, parentFrame.identifierHashes); 686 size_t count = parentFrame.identifierHashes.size(); 687 for (size_t i = 0; i < count; ++i) 688 m_ancestorIdentifierFilter.add(parentFrame.identifierHashes[i]); 689 } 690 691 void CSSStyleSelector::popParent(Element* parent) 692 { 693 if (m_parentStack.isEmpty() || m_parentStack.last().element != parent) 694 return; 695 696 const ParentStackFrame& parentFrame = m_parentStack.last(); 697 size_t count = parentFrame.identifierHashes.size(); 698 for (size_t i = 0; i < count; ++i) 699 m_ancestorIdentifierFilter.remove(parentFrame.identifierHashes[i]); 700 m_parentStack.removeLast(); 701 ASSERT(!m_parentStack.isEmpty() || m_ancestorIdentifierFilter.isEmpty()); 702 } 645 703 646 704 void CSSStyleSelector::addMatchedDeclaration(CSSMutableStyleDeclaration* decl) … … 694 752 } 695 753 754 inline bool CSSStyleSelector::fastRejectSelector(const RuleData& ruleData) const 755 { 756 const unsigned* descendantSelectorIdentifierHashes = ruleData.descendantSelectorIdentifierHashes(); 757 for (unsigned n = 0; n < RuleData::maximumIdentifierCount && descendantSelectorIdentifierHashes[n]; ++n) { 758 if (!m_ancestorIdentifierFilter.contains(descendantSelectorIdentifierHashes[n])) 759 return true; 760 } 761 return false; 762 } 763 696 764 void CSSStyleSelector::matchRulesForList(const Vector<RuleData>* rules, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules) 697 765 { 698 766 if (!rules) 699 767 return; 768 // In some cases we may end up looking up style for random elements in the middle of a recursive tree resolve. 769 // Ancestor identifier filter won't be up-to-date in that case and we can't use the fast path. 770 bool canUseFastReject = !m_parentStack.isEmpty() && m_parentStack.last().element == m_parentNode; 771 700 772 unsigned size = rules->size(); 701 773 for (unsigned i = 0; i < size; ++i) { 702 774 const RuleData& ruleData = rules->at(i); 703 775 CSSStyleRule* rule = ruleData.rule(); 704 if ( m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL()))705 continue; 776 if (canUseFastReject && fastRejectSelector(ruleData)) 777 continue; 706 778 if (checkSelector(ruleData.selector())) { 707 779 // If the rule has no properties to apply, then ignore it in the non-debug mode. … … 709 781 if (!decl || (!decl->length() && !includeEmptyRules)) 710 782 continue; 711 783 if (m_checker.m_sameOriginOnly && !m_checker.m_document->securityOrigin()->canRequest(rule->baseURL())) 784 continue; 712 785 // If we're matching normal rules, set a pseudo bit if 713 786 // we really just matched a pseudo-element. … … 2851 2924 2852 2925 // ----------------------------------------------------------------- 2926 2927 inline void RuleData::collectDescendantSelectorIdentifierHashes() 2928 { 2929 unsigned identifierCount = 0; 2930 CSSSelector::Relation relation = m_selector->relation(); 2931 CSSSelector* selector = m_selector->tagHistory(); 2932 // Skip the topmost selector. It is handled quickly by the rule hashes. 2933 for (; selector; selector = selector->tagHistory()) { 2934 if (relation != CSSSelector::SubSelector) 2935 break; 2936 relation = selector->relation(); 2937 } 2938 for (; selector; selector = selector->tagHistory()) { 2939 // Only collect identifiers that match direct ancestors. 2940 // FIXME: Intead of just stopping, this should skip over sibling selectors. 2941 if (relation != CSSSelector::Descendant && relation != CSSSelector::Child && relation != CSSSelector::SubSelector) 2942 break; 2943 if ((selector->m_match == CSSSelector::Id || selector->m_match == CSSSelector::Class) && !selector->value().isEmpty()) 2944 m_descendantSelectorIdentifierHashes[identifierCount++] = selector->value().impl()->existingHash(); 2945 if (identifierCount == maximumIdentifierCount) 2946 return; 2947 const AtomicString& localName = selector->tag().localName(); 2948 if (localName != starAtom) 2949 m_descendantSelectorIdentifierHashes[identifierCount++] = localName.impl()->existingHash(); 2950 if (identifierCount == maximumIdentifierCount) 2951 return; 2952 relation = selector->relation(); 2953 } 2954 m_descendantSelectorIdentifierHashes[identifierCount] = 0; 2955 } 2853 2956 2854 2957 RuleSet::RuleSet() -
trunk/Source/WebCore/css/CSSStyleSelector.h
r77376 r77740 28 28 #include "MediaQueryExp.h" 29 29 #include "RenderStyle.h" 30 #include <wtf/HashCountedSet.h> 30 31 #include <wtf/HashMap.h> 31 32 #include <wtf/HashSet.h> … … 90 91 bool strictParsing, bool matchAuthorAndUserStyles); 91 92 ~CSSStyleSelector(); 93 94 // Using these during tree walk will allow style selector to optimize child and descendant selector lookups. 95 void pushParent(Element* parent); 96 void popParent(Element* parent); 92 97 93 98 PassRefPtr<RenderStyle> styleForElement(Element* e, RenderStyle* parentStyle = 0, bool allowSharing = true, bool resolveForRootDefault = false, bool matchVisitedPseudoClass = false); … … 187 192 void matchRules(RuleSet*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules); 188 193 void matchRulesForList(const Vector<RuleData>*, int& firstRuleIndex, int& lastRuleIndex, bool includeEmptyRules); 194 bool fastRejectSelector(const RuleData&) const; 189 195 void sortMatchedRules(unsigned start, unsigned end); 190 196 … … 204 210 OwnPtr<RuleSet> m_siblingRules; 205 211 HashSet<AtomicStringImpl*> m_idsInRules; 212 213 struct ParentStackFrame { 214 ParentStackFrame(Element* element) : element(element) {} 215 Element* element; 216 Vector<unsigned, 4> identifierHashes; 217 }; 218 Vector<ParentStackFrame> m_parentStack; 219 // FIXME: Replace this with a bloom filter. 220 HashCountedSet<unsigned, AlreadyHashed> m_ancestorIdentifierFilter; 206 221 207 222 bool m_hasUAAppearance; -
trunk/Source/WebCore/dom/Element.cpp
r76183 r77740 69 69 using namespace XMLNames; 70 70 71 class StyleSelectorParentPusher { 72 public: 73 StyleSelectorParentPusher(CSSStyleSelector* styleSelector, Element* parent) 74 : m_styleSelector(styleSelector) 75 , m_parent(parent) 76 , m_didPush(false) 77 { 78 } 79 void push() 80 { 81 if (m_didPush) 82 return; 83 m_styleSelector->pushParent(m_parent); 84 m_didPush = true; 85 } 86 ~StyleSelectorParentPusher() 87 { 88 if (m_didPush) 89 m_styleSelector->popParent(m_parent); 90 } 91 92 private: 93 CSSStyleSelector* m_styleSelector; 94 Element* m_parent; 95 bool m_didPush; 96 }; 97 71 98 PassRefPtr<Element> Element::create(const QualifiedName& tagName, Document* document) 72 99 { … … 918 945 919 946 createRendererIfNeeded(); 947 948 StyleSelectorParentPusher parentPusher(document()->styleSelector(), this); 949 if (firstChild()) 950 parentPusher.push(); 920 951 ContainerNode::attach(); 921 if (Node* shadow = shadowRoot()) 952 if (Node* shadow = shadowRoot()) { 953 parentPusher.push(); 922 954 shadow->attach(); 955 } 923 956 if (hasRareData()) { 924 957 ElementRareData* data = rareData(); … … 1060 1093 } 1061 1094 } 1062 1095 StyleSelectorParentPusher parentPusher(document()->styleSelector(), this); 1063 1096 // FIXME: This check is good enough for :hover + foo, but it is not good enough for :hover + foo + bar. 1064 1097 // For now we will just worry about the common case, since it's a lot trickier to get the second case right … … 1069 1102 if (forceCheckOfNextElementSibling && n->isElementNode()) 1070 1103 n->setNeedsStyleRecalc(); 1071 if (change >= Inherit || n->isTextNode() || n->childNeedsStyleRecalc() || n->needsStyleRecalc()) 1104 if (change >= Inherit || n->isTextNode() || n->childNeedsStyleRecalc() || n->needsStyleRecalc()) { 1105 parentPusher.push(); 1072 1106 n->recalcStyle(change); 1107 } 1073 1108 if (n->isElementNode()) 1074 1109 forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules; … … 1076 1111 // FIXME: This does not care about sibling combinators. Will be necessary in XBL2 world. 1077 1112 if (Node* shadow = shadowRoot()) { 1078 if (change >= Inherit || shadow->isTextNode() || shadow->childNeedsStyleRecalc() || shadow->needsStyleRecalc()) 1113 if (change >= Inherit || shadow->isTextNode() || shadow->childNeedsStyleRecalc() || shadow->needsStyleRecalc()) { 1114 parentPusher.push(); 1079 1115 shadow->recalcStyle(change); 1116 } 1080 1117 } 1081 1118
Note: See TracChangeset
for help on using the changeset viewer.