Wow, that page is ridicolously slow. I am surprised I haven't noticed myself I use the Qt docs a lot, but most of them works perfectly.

Parsing issue. This is mock-xhtml, and as usual this depends on funny quirks to be parsed correctly.

<li><div class="fn"/>enum <a href="qabstractitemview.html#CursorAction-enum">CursorAction</a></li>
<li><div class="fn"/>enum <a href="qabstractitemview.html#DragDropMode-enum">DragDropMode</a></li>

No browser will parse <div class="fn"/> as a flat XHTML tag in this context, but somehow they survive the layered <li> elements better than we do.

Someone should tell Trolltech however that XHTML doesn't work and their documents are just quirky HTML.

Created attachment 21586 [details]
Test-case

And the funny quirk is:
</li> closes unclosed <div> elements!

Created attachment 21587 [details]
Patch

A different fix. 

Speed-up deeply nested descent selectors.

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

SVN commit 724766 by carewolf:

 Update HTML-Parser to parse more HTML5 like, and allow custom HTML tags. This
 makes us more compatible with IceWeasel and Opera
 BUG: 109557
 BUG: 102209
 CCBUG: 148715
 CCBUG: 150694



 M  +8 -0      ChangeLog  
 M  +39 -40    html/dtd.cpp  
 M  +19 -2     html/dtd.h  
 M  +3 -3      html/html_elementimpl.cpp  
 M  +73 -34    html/htmlparser.cpp  
 M  +2 -0      html/htmlparser.h  
 M  +8 -6      html/htmltokenizer.cpp  


WebSVN link: http://websvn.kde.org/?view=rev&revision=724766