Reviewed by Darin.
authorap <ap@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 25 Mar 2007 08:39:27 +0000 (08:39 +0000)
committerap <ap@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sun, 25 Mar 2007 08:39:27 +0000 (08:39 +0000)
        A partial fix for http://bugs.webkit.org/show_bug.cgi?id=13021
        XPath can be very slow

        * xml/XPathExpression.cpp:
        (WebCore::XPathExpression::evaluate): Reset a reference to the context node, as this may prevent the whole document
        from being destroyed in time.

        * dom/Attr.cpp:
        (WebCore::Attr::createTextChild): Instead of calling appendChild(), just do the few operations it really needs to perform.
        * dom/ContainerNode.h:
        (WebCore::ContainerNode::fastSetFirstChild):
        (WebCore::ContainerNode::fastSetLastChild):
        Added operations that let Attr hack internal ContainerNode data (evil, but fast!).

        * xml/XPathStep.cpp:
        (WebCore::XPath::Step::evaluate):
        (WebCore::XPath::Step::nodesInAxis):
        (WebCore::XPath::Step::nodeMatches):
        * xml/XPathStep.h:
        Merged node testing into axis enumeration. This saves a lot of Vector resizing and passing, and is necessary for future
        optimizations (sometimes, we can just pick the single result node instead of enumerating and filtering the whole axis).

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@20487 268f45cc-cd09-0410-ab3c-d52691b4dbfc

WebCore/ChangeLog
WebCore/dom/Attr.cpp
WebCore/dom/ContainerNode.h
WebCore/xml/XPathExpression.cpp
WebCore/xml/XPathStep.cpp
WebCore/xml/XPathStep.h

index 939ef90..612a6bf 100644 (file)
@@ -1,3 +1,29 @@
+2007-03-25  Alexey Proskuryakov  <ap@webkit.org>
+
+        Reviewed by Darin.
+
+        A partial fix for http://bugs.webkit.org/show_bug.cgi?id=13021
+        XPath can be very slow
+
+        * xml/XPathExpression.cpp:
+        (WebCore::XPathExpression::evaluate): Reset a reference to the context node, as this may prevent the whole document
+        from being destroyed in time.
+
+        * dom/Attr.cpp:
+        (WebCore::Attr::createTextChild): Instead of calling appendChild(), just do the few operations it really needs to perform.
+        * dom/ContainerNode.h:
+        (WebCore::ContainerNode::fastSetFirstChild):
+        (WebCore::ContainerNode::fastSetLastChild):
+        Added operations that let Attr hack internal ContainerNode data (evil, but fast!).
+
+        * xml/XPathStep.cpp:
+        (WebCore::XPath::Step::evaluate):
+        (WebCore::XPath::Step::nodesInAxis):
+        (WebCore::XPath::Step::nodeMatches):
+        * xml/XPathStep.h:
+        Merged node testing into axis enumeration. This saves a lot of Vector resizing and passing, and is necessary for future 
+        optimizations (sometimes, we can just pick the single result node instead of enumerating and filtering the whole axis).
+
 2007-03-24  Mitz Pettel  <mitz@webkit.org>
 
         Reviewed by Darin.
index e44ad01..6cc83ce 100644 (file)
@@ -51,12 +51,15 @@ Attr::~Attr()
 
 void Attr::createTextChild()
 {
-    assert(refCount());
+    ASSERT(refCount());
     if (!m_attribute->value().isEmpty()) {
-        ExceptionCode ec = 0;
-        m_ignoreChildrenChanged++;
-        appendChild(document()->createTextNode(m_attribute->value().impl()), ec);
-        m_ignoreChildrenChanged--;
+        RefPtr<Text> textNode = document()->createTextNode(m_attribute->value().impl());
+
+        // This does everything appendChild() would do in this situation (assuming m_ignoreChildrenChanged was set),
+        // but much more efficiently.
+        textNode->setParent(this);
+        fastSetFirstChild(textNode.get());
+        fastSetLastChild(textNode.get());
     }
 }
 
index c781b1e..591eb9b 100644 (file)
@@ -65,7 +65,7 @@ public:
 
     Node* fastFirstChild() const { return m_firstChild; }
     Node* fastLastChild() const { return m_lastChild; }
-    
+
     void removeAllChildren();
     void removeChildren();
     void cloneChildNodes(Node* clone);
@@ -73,6 +73,9 @@ public:
 protected:
     static void queuePostAttachCallback(NodeCallback, Node*);
 
+    void fastSetFirstChild(Node* child) { m_firstChild = child; }
+    void fastSetLastChild(Node* child) { m_lastChild = child; }
+    
 private:
     Node* m_firstChild;
     Node* m_lastChild;
index e59a2c6..38369f8 100644 (file)
@@ -76,6 +76,7 @@ PassRefPtr<XPathResult> XPathExpression::evaluate(Node* contextNode, unsigned sh
     evaluationContext.size = 1;
     evaluationContext.position = 1;
     RefPtr<XPathResult> result = new XPathResult(eventTarget, m_topExpression->evaluate());
+    evaluationContext.node = 0; // Do not hold a reference to the context node, as this may prevent the whole document from being destroyed in time.
 
     if (type != XPathResult::ANY_TYPE) {
         ec = 0;
index 57f5335..11dbb8f 100644 (file)
@@ -62,7 +62,6 @@ Step::~Step()
 NodeSet Step::evaluate(Node* context) const
 {
     NodeSet nodes = nodesInAxis(context);
-    nodes = nodeTestMatches(nodes);
     
     EvaluationContext& evaluationContext = Expression::evaluationContext();
     
@@ -101,32 +100,38 @@ NodeSet Step::nodesInAxis(Node* context) const
                 return nodes;
 
             for (Node* n = context->firstChild(); n; n = n->nextSibling())
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
             return nodes;
         case DescendantAxis:
             if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
                 return nodes;
 
             for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
             return nodes;
         case ParentAxis:
-            if (context->isAttributeNode())
-                nodes.append(static_cast<Attr*>(context)->ownerElement());
-            else {
-                Node* parent = context->parentNode();
-                if (parent)
-                    nodes.append(parent);
+            if (context->isAttributeNode()) {
+                Node* n = static_cast<Attr*>(context)->ownerElement();
+                if (nodeMatches(n))
+                    nodes.append(n);
+            } else {
+                Node* n = context->parentNode();
+                if (n && nodeMatches(n))
+                    nodes.append(n);
             }
             return nodes;
         case AncestorAxis: {
             Node* n = context;
             if (context->isAttributeNode()) {
                 n = static_cast<Attr*>(context)->ownerElement();
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
             }
             for (n = n->parentNode(); n; n = n->parentNode())
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
             nodes.reverse();
             return nodes;
         }
@@ -136,7 +141,8 @@ NodeSet Step::nodesInAxis(Node* context) const
                 return nodes;
             
             for (Node* n = context->nextSibling(); n; n = n->nextSibling())
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
             return nodes;
         case PrecedingSiblingAxis:
             if (context->nodeType() == Node::ATTRIBUTE_NODE ||
@@ -144,7 +150,8 @@ NodeSet Step::nodesInAxis(Node* context) const
                 return nodes;
             
             for (Node* n = context->previousSibling(); n; n = n->previousSibling())
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
 
             nodes.reverse();
             return nodes;
@@ -152,13 +159,16 @@ NodeSet Step::nodesInAxis(Node* context) const
             if (context->isAttributeNode()) {
                 Node* p = static_cast<Attr*>(context)->ownerElement();
                 while ((p = p->traverseNextNode()))
-                    nodes.append(p);
+                    if (nodeMatches(p))
+                        nodes.append(p);
             } else {
                 for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
                     for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
-                        nodes.append(n);
+                        if (nodeMatches(n))
+                            nodes.append(n);
                         for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
-                            nodes.append(c);
+                            if (nodeMatches(c))
+                                nodes.append(c);
                     }
                 }
             }
@@ -169,9 +179,11 @@ NodeSet Step::nodesInAxis(Node* context) const
 
             for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
                 for (Node* n = p->previousSibling(); n ; n = n->previousSibling()) {
-                    nodes.append(n);
+                    if (nodeMatches(n))
+                        nodes.append(n);
                     for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
-                        nodes.append(c);
+                        if (nodeMatches(c))
+                            nodes.append(c);
                 }
             }
             nodes.markSorted(false);
@@ -184,33 +196,42 @@ NodeSet Step::nodesInAxis(Node* context) const
             if (!attrs)
                 return nodes;
 
-            for (unsigned long i = 0; i < attrs->length(); ++i) 
-                nodes.append(attrs->item(i));
+            for (unsigned long i = 0; i < attrs->length(); ++i) {
+                RefPtr<Node> n = attrs->item(i);
+                if (nodeMatches(n.get()))
+                    nodes.append(n.release());
+            }
             return nodes;
         }
         case NamespaceAxis:
             // XPath namespace nodes are not implemented yet.
             return nodes;
         case SelfAxis:
-            nodes.append(context);
+            if (nodeMatches(context))
+                nodes.append(context);
             return nodes;
         case DescendantOrSelfAxis:
-            nodes.append(context);
+            if (nodeMatches(context))
+                nodes.append(context);
             if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
                 return nodes;
 
             for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
+            if (nodeMatches(n))
                 nodes.append(n);
             return nodes;
         case AncestorOrSelfAxis: {
-            nodes.append(context);
+            if (nodeMatches(context))
+                nodes.append(context);
             Node* n = context;
             if (context->isAttributeNode()) {
                 n = static_cast<Attr*>(context)->ownerElement();
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
             }
             for (n = n->parentNode(); n; n = n->parentNode())
-                nodes.append(n);
+                if (nodeMatches(n))
+                    nodes.append(n);
 
             nodes.reverse();
             return nodes;
@@ -221,92 +242,47 @@ NodeSet Step::nodesInAxis(Node* context) const
 }
 
 
-NodeSet Step::nodeTestMatches(const NodeSet& nodes) const
+bool Step::nodeMatches(Node* node) const
 {
-    NodeSet matches;
-    if (!nodes.isSorted())
-        matches.markSorted(false);
-
     switch (m_nodeTest.kind()) {
         case NodeTest::TextNodeTest:
-            for (unsigned i = 0; i < nodes.size(); i++) {
-                Node* node = nodes[i];
-                if ((node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE))
-                    matches.append(node);
-            }
-            return matches;
+            return node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE;
         case NodeTest::CommentNodeTest:
-            for (unsigned i = 0; i < nodes.size(); i++) {
-                Node* node = nodes[i];
-                if (node->nodeType() == Node::COMMENT_NODE)
-                    matches.append(node);
-            }
-            return matches;
-        case NodeTest::ProcessingInstructionNodeTest:
-            for (unsigned i = 0; i < nodes.size(); i++) {
-                Node* node = nodes[i];
-                const String& name = m_nodeTest.data();
-                if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name))
-                        matches.append(node);
-            }    
-            return matches;
+            return node->nodeType() == Node::COMMENT_NODE;
+        case NodeTest::ProcessingInstructionNodeTest: {
+            const String& name = m_nodeTest.data();
+            return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name);
+        }
         case NodeTest::ElementNodeTest:
-            for (unsigned i = 0; i < nodes.size(); i++) {
-                Node* node = nodes[i];
-                if (node->isElementNode())
-                    matches.append(node);
-            }
-            return matches;
+            return node->isElementNode();
         case NodeTest::AnyNodeTest:
-            return nodes;
+            return true;
         case NodeTest::NameTest: {
             const String& name = m_nodeTest.data();
-            if (name == "*") {
-                for (unsigned i = 0; i < nodes.size(); i++) {
-                    Node* node = nodes[i];
-                    if (node->nodeType() == primaryNodeType(m_axis) &&
-                        (m_namespaceURI.isEmpty() || m_namespaceURI == node->namespaceURI()))
-                        matches.append(node);
-                }
-                return matches;
-            }
+            if (name == "*")
+                return node->nodeType() == primaryNodeType(m_axis) && (m_namespaceURI.isEmpty() || m_namespaceURI == node->namespaceURI());
+
             if (m_axis == AttributeAxis) {
-                // In XPath land, namespace nodes are not accessible
-                // on the attribute axis.
+                // In XPath land, namespace nodes are not accessible on the attribute axis.
                 if (name == "xmlns")
-                    return matches;
-
-                for (unsigned i = 0; i < nodes.size(); i++) {
-                    Node* node = nodes[i];
-                    
-                    if (node->nodeName() == name) {
-                        matches.append(node);
-                        break; // There can only be one.
-                    }
-                }
+                    return false;
 
-                return matches;
+                // FIXME: check the namespace!
+                return node->nodeName() == name;
             } else if (m_axis == NamespaceAxis) {
                 // Node test on the namespace axis is not implemented yet
             } else {
-                for (unsigned i = 0; i < nodes.size(); i++) {
-                    Node* node = nodes[i];
-
-                    // We use tagQName here because we don't want the element name in uppercase 
-                    // like we get with HTML elements.
-                    // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace.
-                    if (node->nodeType() == Node::ELEMENT_NODE
+                // We use tagQName here because we don't want the element name in uppercase 
+                // like we get with HTML elements.
+                // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace.
+                return node->nodeType() == Node::ELEMENT_NODE
                         && static_cast<Element*>(node)->tagQName().localName() == name
-                        && ((node->isHTMLElement() && node->document()->isHTMLDocument() && m_namespaceURI.isNull()) || m_namespaceURI == node->namespaceURI()))
-                        matches.append(node);
-                }
-
-                return matches;
+                        && ((node->isHTMLElement() && node->document()->isHTMLDocument() && m_namespaceURI.isNull()) || m_namespaceURI == node->namespaceURI());
             }
         }
     }
     ASSERT_NOT_REACHED();
-    return matches;
+    return false;
 }
 
 Node::NodeType Step::primaryNodeType(Axis axis) const
index 59b3b0d..4795347 100644 (file)
@@ -87,7 +87,7 @@ namespace WebCore {
         private:
             void parseNodeTest(const String&);
             NodeSet nodesInAxis(Node* context) const;
-            NodeSet nodeTestMatches(const NodeSet& nodes) const;
+            bool nodeMatches(Node*) const;
             String namespaceFromNodetest(const String& nodeTest) const;
             Node::NodeType primaryNodeType(Axis) const;