Changeset 20487 in webkit


Ignore:
Timestamp:
Mar 25, 2007 1:39:27 AM (17 years ago)
Author:
ap
Message:

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).
Location:
trunk/WebCore
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/WebCore/ChangeLog

    r20479 r20487  
     12007-03-25  Alexey Proskuryakov  <ap@webkit.org>
     2
     3        Reviewed by Darin.
     4
     5        A partial fix for http://bugs.webkit.org/show_bug.cgi?id=13021
     6        XPath can be very slow
     7
     8        * xml/XPathExpression.cpp:
     9        (WebCore::XPathExpression::evaluate): Reset a reference to the context node, as this may prevent the whole document
     10        from being destroyed in time.
     11
     12        * dom/Attr.cpp:
     13        (WebCore::Attr::createTextChild): Instead of calling appendChild(), just do the few operations it really needs to perform.
     14        * dom/ContainerNode.h:
     15        (WebCore::ContainerNode::fastSetFirstChild):
     16        (WebCore::ContainerNode::fastSetLastChild):
     17        Added operations that let Attr hack internal ContainerNode data (evil, but fast!).
     18
     19        * xml/XPathStep.cpp:
     20        (WebCore::XPath::Step::evaluate):
     21        (WebCore::XPath::Step::nodesInAxis):
     22        (WebCore::XPath::Step::nodeMatches):
     23        * xml/XPathStep.h:
     24        Merged node testing into axis enumeration. This saves a lot of Vector resizing and passing, and is necessary for future
     25        optimizations (sometimes, we can just pick the single result node instead of enumerating and filtering the whole axis).
     26
    1272007-03-24  Mitz Pettel  <mitz@webkit.org>
    228

  • trunk/WebCore/dom/Attr.cpp

    r13973 r20487  
    5252void Attr::createTextChild()
    5353{
    54     assert(refCount());
     54    ASSERT(refCount());
    5555    if (!m_attribute->value().isEmpty()) {
    56         ExceptionCode ec = 0;
    57         m_ignoreChildrenChanged++;
    58         appendChild(document()->createTextNode(m_attribute->value().impl()), ec);
    59         m_ignoreChildrenChanged--;
     56        RefPtr<Text> textNode = document()->createTextNode(m_attribute->value().impl());
     57
     58        // This does everything appendChild() would do in this situation (assuming m_ignoreChildrenChanged was set),
     59        // but much more efficiently.
     60        textNode->setParent(this);
     61        fastSetFirstChild(textNode.get());
     62        fastSetLastChild(textNode.get());
    6063    }
    6164}

  • trunk/WebCore/dom/ContainerNode.h

    r17040 r20487  
    6666    Node* fastFirstChild() const { return m_firstChild; }
    6767    Node* fastLastChild() const { return m_lastChild; }
    68    
     68
    6969    void removeAllChildren();
    7070    void removeChildren();
    … …  
    7474    static void queuePostAttachCallback(NodeCallback, Node*);
    7575
     76    void fastSetFirstChild(Node* child) { m_firstChild = child; }
     77    void fastSetLastChild(Node* child) { m_lastChild = child; }
     78   
    7679private:
    7780    Node* m_firstChild;

  • trunk/WebCore/xml/XPathExpression.cpp

    r20345 r20487  
    7777    evaluationContext.position = 1;
    7878    RefPtr<XPathResult> result = new XPathResult(eventTarget, m_topExpression->evaluate());
     79    evaluationContext.node = 0; // Do not hold a reference to the context node, as this may prevent the whole document from being destroyed in time.
    7980
    8081    if (type != XPathResult::ANY_TYPE) {

  • trunk/WebCore/xml/XPathStep.cpp

    r20345 r20487  
    6363{
    6464    NodeSet nodes = nodesInAxis(context);
    65     nodes = nodeTestMatches(nodes);
    6665   
    6766    EvaluationContext& evaluationContext = Expression::evaluationContext();
    … …  
    102101
    103102            for (Node* n = context->firstChild(); n; n = n->nextSibling())
    104                 nodes.append(n);
     103                if (nodeMatches(n))
     104                    nodes.append(n);
    105105            return nodes;
    106106        case DescendantAxis:
    … …  
    109109
    110110            for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
    111                 nodes.append(n);
     111                if (nodeMatches(n))
     112                    nodes.append(n);
    112113            return nodes;
    113114        case ParentAxis:
    114             if (context->isAttributeNode())
    115                 nodes.append(static_cast<Attr*>(context)->ownerElement());
    116             else {
    117                 Node* parent = context->parentNode();
    118                 if (parent)
    119                     nodes.append(parent);
     115            if (context->isAttributeNode()) {
     116                Node* n = static_cast<Attr*>(context)->ownerElement();
     117                if (nodeMatches(n))
     118                    nodes.append(n);
     119            } else {
     120                Node* n = context->parentNode();
     121                if (n && nodeMatches(n))
     122                    nodes.append(n);
    120123            }
    121124            return nodes;
    … …  
    124127            if (context->isAttributeNode()) {
    125128                n = static_cast<Attr*>(context)->ownerElement();
    126                 nodes.append(n);
     129                if (nodeMatches(n))
     130                    nodes.append(n);
    127131            }
    128132            for (n = n->parentNode(); n; n = n->parentNode())
    129                 nodes.append(n);
     133                if (nodeMatches(n))
     134                    nodes.append(n);
    130135            nodes.reverse();
    131136            return nodes;
    … …  
    137142           
    138143            for (Node* n = context->nextSibling(); n; n = n->nextSibling())
    139                 nodes.append(n);
     144                if (nodeMatches(n))
     145                    nodes.append(n);
    140146            return nodes;
    141147        case PrecedingSiblingAxis:
    … …  
    145151           
    146152            for (Node* n = context->previousSibling(); n; n = n->previousSibling())
    147                 nodes.append(n);
     153                if (nodeMatches(n))
     154                    nodes.append(n);
    148155
    149156            nodes.reverse();
    … …  
    153160                Node* p = static_cast<Attr*>(context)->ownerElement();
    154161                while ((p = p->traverseNextNode()))
    155                     nodes.append(p);
     162                    if (nodeMatches(p))
     163                        nodes.append(p);
    156164            } else {
    157165                for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
    158166                    for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
    159                         nodes.append(n);
     167                        if (nodeMatches(n))
     168                            nodes.append(n);
    160169                        for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
    161                             nodes.append(c);
     170                            if (nodeMatches(c))
     171                                nodes.append(c);
    162172                    }
    163173                }
    … …  
    170180            for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
    171181                for (Node* n = p->previousSibling(); n ; n = n->previousSibling()) {
    172                     nodes.append(n);
     182                    if (nodeMatches(n))
     183                        nodes.append(n);
    173184                    for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
    174                         nodes.append(c);
     185                        if (nodeMatches(c))
     186                            nodes.append(c);
    175187                }
    176188            }
    … …  
    185197                return nodes;
    186198
    187             for (unsigned long i = 0; i < attrs->length(); ++i)
    188                 nodes.append(attrs->item(i));
     199            for (unsigned long i = 0; i < attrs->length(); ++i) {
     200                RefPtr<Node> n = attrs->item(i);
     201                if (nodeMatches(n.get()))
     202                    nodes.append(n.release());
     203            }
    189204            return nodes;
    190205        }
    … …  
    193208            return nodes;
    194209        case SelfAxis:
    195             nodes.append(context);
     210            if (nodeMatches(context))
     211                nodes.append(context);
    196212            return nodes;
    197213        case DescendantOrSelfAxis:
    198             nodes.append(context);
     214            if (nodeMatches(context))
     215                nodes.append(context);
    199216            if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
    200217                return nodes;
    201218
    202219            for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
     220            if (nodeMatches(n))
    203221                nodes.append(n);
    204222            return nodes;
    205223        case AncestorOrSelfAxis: {
    206             nodes.append(context);
     224            if (nodeMatches(context))
     225                nodes.append(context);
    207226            Node* n = context;
    208227            if (context->isAttributeNode()) {
    209228                n = static_cast<Attr*>(context)->ownerElement();
    210                 nodes.append(n);
     229                if (nodeMatches(n))
     230                    nodes.append(n);
    211231            }
    212232            for (n = n->parentNode(); n; n = n->parentNode())
    213                 nodes.append(n);
     233                if (nodeMatches(n))
     234                    nodes.append(n);
    214235
    215236            nodes.reverse();
    … …  
    222243
    223244
    224 NodeSet Step::nodeTestMatches(const NodeSet& nodes) const
    225 {
    226     NodeSet matches;
    227     if (!nodes.isSorted())
    228         matches.markSorted(false);
    229 
     245bool Step::nodeMatches(Node* node) const
     246{
    230247    switch (m_nodeTest.kind()) {
    231248        case NodeTest::TextNodeTest:
    232             for (unsigned i = 0; i < nodes.size(); i++) {
    233                 Node* node = nodes[i];
    234                 if ((node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE))
    235                     matches.append(node);
    236             }
    237             return matches;
     249            return node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE;
    238250        case NodeTest::CommentNodeTest:
    239             for (unsigned i = 0; i < nodes.size(); i++) {
    240                 Node* node = nodes[i];
    241                 if (node->nodeType() == Node::COMMENT_NODE)
    242                     matches.append(node);
    243             }
    244             return matches;
    245         case NodeTest::ProcessingInstructionNodeTest:
    246             for (unsigned i = 0; i < nodes.size(); i++) {
    247                 Node* node = nodes[i];
    248                 const String& name = m_nodeTest.data();
    249                 if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name))
    250                         matches.append(node);
    251             }   
    252             return matches;
     251            return node->nodeType() == Node::COMMENT_NODE;
     252        case NodeTest::ProcessingInstructionNodeTest: {
     253            const String& name = m_nodeTest.data();
     254            return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name);
     255        }
    253256        case NodeTest::ElementNodeTest:
    254             for (unsigned i = 0; i < nodes.size(); i++) {
    255                 Node* node = nodes[i];
    256                 if (node->isElementNode())
    257                     matches.append(node);
    258             }
    259             return matches;
     257            return node->isElementNode();
    260258        case NodeTest::AnyNodeTest:
    261             return nodes;
     259            return true;
    262260        case NodeTest::NameTest: {
    263261            const String& name = m_nodeTest.data();
    264             if (name == "*") {
    265                 for (unsigned i = 0; i < nodes.size(); i++) {
    266                     Node* node = nodes[i];
    267                     if (node->nodeType() == primaryNodeType(m_axis) &&
    268                         (m_namespaceURI.isEmpty() || m_namespaceURI == node->namespaceURI()))
    269                         matches.append(node);
    270                 }
    271                 return matches;
    272             }
     262            if (name == "*")
     263                return node->nodeType() == primaryNodeType(m_axis) && (m_namespaceURI.isEmpty() || m_namespaceURI == node->namespaceURI());
     264
    273265            if (m_axis == AttributeAxis) {
    274                 // In XPath land, namespace nodes are not accessible
    275                 // on the attribute axis.
     266                // In XPath land, namespace nodes are not accessible on the attribute axis.
    276267                if (name == "xmlns")
    277                     return matches;
    278 
    279                 for (unsigned i = 0; i < nodes.size(); i++) {
    280                     Node* node = nodes[i];
    281                    
    282                     if (node->nodeName() == name) {
    283                         matches.append(node);
    284                         break; // There can only be one.
    285                     }
    286                 }
    287 
    288                 return matches;
     268                    return false;
     269
     270                // FIXME: check the namespace!
     271                return node->nodeName() == name;
    289272            } else if (m_axis == NamespaceAxis) {
    290273                // Node test on the namespace axis is not implemented yet
    291274            } else {
    292                 for (unsigned i = 0; i < nodes.size(); i++) {
    293                     Node* node = nodes[i];
    294 
    295                     // We use tagQName here because we don't want the element name in uppercase
    296                     // like we get with HTML elements.
    297                     // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace.
    298                     if (node->nodeType() == Node::ELEMENT_NODE
     275                // We use tagQName here because we don't want the element name in uppercase
     276                // like we get with HTML elements.
     277                // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace.
     278                return node->nodeType() == Node::ELEMENT_NODE
    299279                        && static_cast<Element*>(node)->tagQName().localName() == name
    300                         && ((node->isHTMLElement() && node->document()->isHTMLDocument() && m_namespaceURI.isNull()) || m_namespaceURI == node->namespaceURI()))
    301                         matches.append(node);
    302                 }
    303 
    304                 return matches;
     280                        && ((node->isHTMLElement() && node->document()->isHTMLDocument() && m_namespaceURI.isNull()) || m_namespaceURI == node->namespaceURI());
    305281            }
    306282        }
    307283    }
    308284    ASSERT_NOT_REACHED();
    309     return matches;
     285    return false;
    310286}
    311287

  • trunk/WebCore/xml/XPathStep.h

    r20345 r20487  
    8888            void parseNodeTest(const String&);
    8989            NodeSet nodesInAxis(Node* context) const;
    90             NodeSet nodeTestMatches(const NodeSet& nodes) const;
     90            bool nodeMatches(Node*) const;
    9191            String namespaceFromNodetest(const String& nodeTest) const;
    9292            Node::NodeType primaryNodeType(Axis) const;
Note: See TracChangeset for help on using the changeset viewer.