From kde-commits Mon Sep 10 18:09:53 2007 From: Allan Sandfeld Jensen Date: Mon, 10 Sep 2007 18:09:53 +0000 To: kde-commits Subject: branches/KDE/3.5/kdelibs/khtml Message-Id: <1189447793.000554.1183.nullmailer () svn ! kde ! org> X-MARC-Message: https://marc.info/?l=kde-commits&m=118944780730368 SVN commit 710724 by carewolf: Backport of r710723 fix for Trolltech invalid XHTML M +9 -1 ChangeLog M +102 -23 css/cssstyleselector.cpp M +2 -1 css/cssstyleselector.h --- branches/KDE/3.5/kdelibs/khtml/ChangeLog #710723:710724 @@ -1,3 +1,11 @@ +2007-10-09 Allan Sandfeld Jensen + + Optimize the case of double descendant selectors "a b c", + to avoid O(n^2) run-time where n is the depth of the DOM tree. + + * css/cssstyleselector.h: Define new early termination value for checkSelector + * css/cssstyleselector.cpp: Bail-out when the selector-chain can't possibly match + 2007-04-22 Harri Porten * ecma/xmlhttprequest.cpp: allow Accept header overrides @@ -30,7 +38,7 @@ * html/html_formimpl.cpp (gatherWalletData): prevent crash occuring on double form submits (bug report #105899) - + 2006-11-14 Allan Sandfeld Jensen Implement overflow-x and overflow-y --- branches/KDE/3.5/kdelibs/khtml/css/cssstyleselector.cpp #710723:710724 @@ -419,7 +419,53 @@ } #undef MAXFONTSIZES +/* +bool CSSStyleSelector::canShareStyleWithElement(NodeImpl* n) +{ + if (n->isElementNode()) { + ElementImpl* s = static_cast(n); + RenderStyle* style = s->renderer()->style(); + if (style && + (s->id() == element->id()) && !s->hasID() && + (s->hasClass() == element->hasClass()) && !s->inlineStyleDecl() && + (s->hovered() == element->hovered()) && + (s->active() == element->active()) && + (s->focused() == element->focused()) + ) { +// (s->isEnabled() == element->isEnabled()) && +// (s->isIndeterminate() == element->isIndeterminate()) && +// (s->isChecked() == element->isChecked()) && + bool classesMatch = true; + if (s->hasClass()) { + const DOMString& class1 = element->getAttribute(ATTR_CLASS); + const DOMString& class2 = s->getAttribute(ATTR_CLASS); + classesMatch = (class1 == class2); + } + if (classesMatch) return true; + } + } + return false; +} + +RenderStyle* CSSStyleSelector::locateSharedStyle() +{ + if (element && !element->hasID()) { + // Check previous siblings. + unsigned count = 0; + NodeImpl* n; + for (n = element->previousSibling(); n && !n->isElementNode(); n = n->previousSibling()); + while (n) { + if (canShareStyleWithElement(n)) + return n->renderer()->style(); + if (++count > 10) + return 0; + for (n = n->previousSibling(); n && !n->isElementNode(); n = n->previousSibling()); + } + } + return 0; +}*/ + static inline void bubbleSort( CSSOrderedProperty **b, CSSOrderedProperty **e ) { while( b < e ) { @@ -466,6 +512,14 @@ // reset dynamic DOM dependencies e->getDocument()->dynamicDomRestyler().resetDependencies(e); +/* if (true) { + style = locateSharedStyle(); + if (style) { + style->ref(); + return style; + } + }*/ + style = new RenderStyle(); if( parentStyle ) style->inheritFrom( parentStyle ); @@ -614,6 +668,23 @@ pseudoStyle = pseudoStyle->pseudoStyle; } + // Try and share the style with our siblings + NodeImpl *n = element; + do { + for (n = n->previousSibling(); n && !n->isElementNode(); n = n->previousSibling()); + if (!n) break; + if (n->id() == element->id() && static_cast(n)->renderer() ) { + style->compactWith(static_cast(n)->renderer()->style()); + break; + } + } while(true); + if (!n) { + n=element->parentNode(); + if (n && n->renderer()) + style->compactWith(static_cast(n)->renderer()->style()); + } + + // Now return the style. return style; } @@ -934,11 +1005,11 @@ { // Sets up global dependencies of attributes if (isSubject) - doc->dynamicDomRestyler().addDependency(sel->attr, PersonalDependency); + doc->dynamicDomRestyler().addDependency(AttributeDependencies, sel->attr, PersonalDependency); else if (isAncestor) - doc->dynamicDomRestyler().addDependency(sel->attr, AncestorDependency); + doc->dynamicDomRestyler().addDependency(AttributeDependencies, sel->attr, AncestorDependency); else - doc->dynamicDomRestyler().addDependency(sel->attr, PredecessorDependency); + doc->dynamicDomRestyler().addDependency(AttributeDependencies, sel->attr, PredecessorDependency); } if(sel->match == CSSSelector::PseudoClass) { @@ -976,17 +1047,21 @@ } // Recursive check of selectors and combinators -DOM::ElementImpl* CSSStyleSelector::checkSelector(DOM::CSSSelector *sel, DOM::ElementImpl *e, bool isAncestor, bool isSubSelector) +// It can return 3 different values: +// * SelectorMatches - the selector is match for the node e +// * SelectorFailsLocal - the selector fails for the node e +// * SelectorFails - the selector fails for e and any sibling or ancestor of e +CSSStyleSelector::SelectorMatch CSSStyleSelector::checkSelector(DOM::CSSSelector *sel, DOM::ElementImpl *e, bool isAncestor, bool isSubSelector) { // The simple selector has to match - if(!checkSimpleSelector(sel, e, isAncestor, isSubSelector)) return 0; + if(!checkSimpleSelector(sel, e, isAncestor, isSubSelector)) return SelectorFailsLocal; // The rest of the selectors has to match CSSSelector::Relation relation = sel->relation; // Prepare next sel sel = sel->tagHistory; - if (!sel) return e; + if (!sel) return SelectorMatches; switch(relation) { case CSSSelector::Descendant: @@ -994,9 +1069,11 @@ while(true) { DOM::NodeImpl* n = e->parentNode(); - if(!n || !n->isElementNode()) return 0; + if(!n || !n->isElementNode()) return SelectorFails; e = static_cast(n); - if(checkSelector(sel, e, true)) return e; + SelectorMatch match = checkSelector(sel, e, true); + if (match != SelectorFailsLocal) + return match; } break; } @@ -1005,10 +1082,9 @@ DOM::NodeImpl* n = e->parentNode(); if (!strictParsing) while (n && n->implicitNode()) n = n->parentNode(); - if(!n || !n->isElementNode()) return 0; + if(!n || !n->isElementNode()) return SelectorFails; e = static_cast(n); - if(checkSelector(sel, e, true)) return e; - break; + return checkSelector(sel, e, true); } case CSSSelector::IndirectAdjacent: { @@ -1021,9 +1097,11 @@ DOM::NodeImpl* n = e->previousSibling(); while( n && !n->isElementNode() ) n = n->previousSibling(); - if( !n ) return 0; + if( !n ) return SelectorFailsLocal; e = static_cast(n); - if(checkSelector(sel, e, false)) return e; + SelectorMatch match = checkSelector(sel, e, false); + if (match != SelectorFailsLocal) + return match; }; break; } @@ -1034,15 +1112,15 @@ DOM::NodeImpl* n = e->previousSibling(); while( n && !n->isElementNode() ) n = n->previousSibling(); - if( !n ) return 0; + if( !n ) return SelectorFailsLocal; e = static_cast(n); - if(checkSelector(sel, e, false)) return e; - break; + return checkSelector(sel, e, false); } case CSSSelector::SubSelector: return checkSelector(sel, e, isAncestor, true); } - return 0; + assert(false); // never reached + return SelectorFails; } void CSSStyleSelector::checkSelector(int selIndex, DOM::ElementImpl * e) @@ -1055,7 +1133,8 @@ CSSSelector *sel = selectors[ selIndex ]; // Check the selector - if(!checkSelector(sel, e, true)) return; + SelectorMatch match = checkSelector(sel, e, true); + if(match != SelectorMatches) return; if ( dynamicPseudo != RenderStyle::NOPSEUDO ) { selectorCache[selIndex].state = AppliesPseudo; @@ -1456,13 +1535,13 @@ case CSSSelector::PseudoLang: { // Set dynamic attribute dependency if (e == element) { - e->getDocument()->dynamicDomRestyler().addDependency(ATTR_LANG, PersonalDependency); - e->getDocument()->dynamicDomRestyler().addDependency(ATTR_LANG, AncestorDependency); + e->getDocument()->dynamicDomRestyler().addDependency(AttributeDependencies, ATTR_LANG, PersonalDependency); + e->getDocument()->dynamicDomRestyler().addDependency(AttributeDependencies, ATTR_LANG, AncestorDependency); } else if (isAncestor) - e->getDocument()->dynamicDomRestyler().addDependency(ATTR_LANG, AncestorDependency); + e->getDocument()->dynamicDomRestyler().addDependency(AttributeDependencies, ATTR_LANG, AncestorDependency); else - e->getDocument()->dynamicDomRestyler().addDependency(ATTR_LANG, PredecessorDependency); + e->getDocument()->dynamicDomRestyler().addDependency(AttributeDependencies, ATTR_LANG, PredecessorDependency); // ### check xml:lang attribute in XML and XHTML documents DOMString value = e->getAttribute(ATTR_LANG); // The LANG attribute is inherited like a property @@ -3599,7 +3678,7 @@ case CSS_PROP_BORDER_COLOR: if(id == CSS_PROP_BORDER || id == CSS_PROP_BORDER_COLOR) { - if (isInherit) { + if (isInherit) { style->setBorderTopColor(parentStyle->borderTopColor()); style->setBorderBottomColor(parentStyle->borderBottomColor()); style->setBorderLeftColor(parentStyle->borderLeftColor()); --- branches/KDE/3.5/kdelibs/khtml/css/cssstyleselector.h #710723:710724 @@ -152,7 +152,8 @@ /* checks if the selector matches the given Element */ bool checkSimpleSelector(DOM::CSSSelector *selector, DOM::ElementImpl *e, bool isAncestor, bool isSubSelector = false); - DOM::ElementImpl* checkSelector(DOM::CSSSelector *sel, DOM::ElementImpl *e, bool isAncestor, bool isSubSelector = false); + enum SelectorMatch {SelectorMatches = 0, SelectorFailsLocal, SelectorFails}; + SelectorMatch checkSelector(DOM::CSSSelector *sel, DOM::ElementImpl *e, bool isAncestor, bool isSubSelector = false); void addDependency(StructuralDependencyType dependencyType, DOM::ElementImpl* dependency); #ifdef APPLE_CHANGES