[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-commits
Subject:    KDE/kdelibs/khtml
From:       Allan Sandfeld Jensen <kde () carewolf ! com>
Date:       2007-09-10 18:08:26
Message-ID: 1189447706.960459.923.nullmailer () svn ! kde ! org
[Download RAW message or body]

SVN commit 710723 by carewolf:

Fix an issue in the non-deterministic matching that had a O(h^2) worst
time behaviour, where h is the height of the tree.
This fixes a runtime issues with invalid XHTML, like that used in Trolltech Qt
documentation.
BUG: 148715



 M  +8 -0      ChangeLog  
 M  +24 -15    css/cssstyleselector.cpp  
 M  +2 -1      css/cssstyleselector.h  


--- trunk/KDE/kdelibs/khtml/ChangeLog #710722:710723
@@ -1,3 +1,11 @@
+2007-10-09  Allan Sandfeld Jensen <kde@carewolf.com>
+
+        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-01-21  Allan Sandfeld Jensen <kde@carewolf.com>
 
         Handle dynamic updates of default non-inherited properties that are \
                inherited explicitly
--- trunk/KDE/kdelibs/khtml/css/cssstyleselector.cpp #710722:710723
@@ -998,17 +998,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:
@@ -1016,9 +1020,11 @@
             while(true)
             {
                 DOM::NodeImpl* n = e->parentNode();
-                if(!n || !n->isElementNode()) return 0;
+                if(!n || !n->isElementNode()) return SelectorFails;
                 e = static_cast<ElementImpl *>(n);
-                if(checkSelector(sel, e, true)) return e;
+                SelectorMatch match = checkSelector(sel, e, true);
+                if (match != SelectorFailsLocal)
+                    return match;
             }
             break;
         }
@@ -1027,10 +1033,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<ElementImpl *>(n);
-            if(checkSelector(sel, e, true)) return e;
-            break;
+            return checkSelector(sel, e, true);
         }
         case CSSSelector::IndirectAdjacent:
         {
@@ -1043,9 +1048,11 @@
                 DOM::NodeImpl* n = e->previousSibling();
                 while( n && !n->isElementNode() )
                     n = n->previousSibling();
-                if( !n ) return 0;
+                if( !n ) return SelectorFailsLocal;
                 e = static_cast<ElementImpl *>(n);
-                if(checkSelector(sel, e, false)) return e;
+                SelectorMatch match = checkSelector(sel, e, false);
+                if (match != SelectorFailsLocal)
+                    return match;
             };
             break;
         }
@@ -1056,15 +1063,15 @@
             DOM::NodeImpl* n = e->previousSibling();
             while( n && !n->isElementNode() )
                 n = n->previousSibling();
-            if( !n ) return 0;
+            if( !n ) return SelectorFailsLocal;
             e = static_cast<ElementImpl *>(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)
@@ -1075,8 +1082,10 @@
 
     selectorCache[ selIndex ].state = Invalid;
     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;
--- trunk/KDE/kdelibs/khtml/css/cssstyleselector.h #710722:710723
@@ -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


[prev in list] [next in list] [prev in thread] [next in thread]