DOM Optimizations

DOM traversal optimizations
DOM Core optimizations
Prefetch optimization for DOM Tree Traversal

Conflicts:

	Source/WebKit/android/jni/WebViewCore.cpp

Change-Id: Icbb8a7229ee9cff1a5401b57c8181f18b9a6d6e0

20 files changed, 464 insertions, 159 deletions

diff --git a/Source/WebCore/dom/Attr.cpp b/Source/WebCore/dom/Attr.cpp
index e3ae348..346a819 100644
--- a/Source/WebCore/dom/Attr.cpp
+++ b/Source/WebCore/dom/Attr.cpp
@@ -69,6 +69,8 @@ void Attr::createTextChild()
         textNode->setParent(this);
         setFirstChild(textNode.get());
         setLastChild(textNode.get());
+        textNode->updateNextNode();
+        textNode->updatePreviousNode();
     }
 }
 
diff --git a/Source/WebCore/dom/CharacterData.cpp b/Source/WebCore/dom/CharacterData.cpp
index b4af02d..78f57d0 100644
--- a/Source/WebCore/dom/CharacterData.cpp
+++ b/Source/WebCore/dom/CharacterData.cpp
@@ -189,6 +189,7 @@ void CharacterData::updateRenderer(unsigned offsetOfReplacedData, unsigned lengt
 
 void CharacterData::dispatchModifiedEvent(StringImpl* oldData)
 {
+    updatePrevNextNodesInSubtree();
     if (parentNode())
         parentNode()->childrenChanged();
     if (document()->hasListenerType(Document::DOMCHARACTERDATAMODIFIED_LISTENER))
diff --git a/Source/WebCore/dom/ChildNodeList.cpp b/Source/WebCore/dom/ChildNodeList.cpp
index 3328c7c..253537c 100644
--- a/Source/WebCore/dom/ChildNodeList.cpp
+++ b/Source/WebCore/dom/ChildNodeList.cpp
@@ -27,19 +27,27 @@
 
 namespace WebCore {
 
-ChildNodeList::ChildNodeList(PassRefPtr<Node> rootNode, DynamicNodeList::Caches* info)
-    : DynamicNodeList(rootNode, info)
+ChildNodeList::ChildNodeList(PassRefPtr<Node> rootNode)
+    : DynamicNodeList(rootNode)
 {
 }
 
+ChildNodeList::~ChildNodeList()
+{
+    m_rootNode->removeCachedChildNodeList(this);
+}
+
 unsigned ChildNodeList::length() const
 {
     if (m_caches->isLengthCacheValid)
         return m_caches->cachedLength;
 
     unsigned len = 0;
-    for (Node* n = m_rootNode->firstChild(); n; n = n->nextSibling())
+    Vector<Node* >& cachedNodes = m_caches->cachedNodes;
+    for (Node* n = m_rootNode->firstChild(); n; n = n->nextSibling()) {
+        cachedNodes.append(n);
         len++;
+    }
 
     m_caches->cachedLength = len;
     m_caches->isLengthCacheValid = true;
@@ -49,6 +57,9 @@ unsigned ChildNodeList::length() const
 
 Node* ChildNodeList::item(unsigned index) const
 {
+    if (m_caches->isLengthCacheValid && index < m_caches->cachedLength)
+        return m_caches->cachedNodes[index];
+
     unsigned int pos = 0;
     Node* n = m_rootNode->firstChild();
 
diff --git a/Source/WebCore/dom/ChildNodeList.h b/Source/WebCore/dom/ChildNodeList.h
index f38106d..df3d67b 100644
--- a/Source/WebCore/dom/ChildNodeList.h
+++ b/Source/WebCore/dom/ChildNodeList.h
@@ -31,16 +31,18 @@ namespace WebCore {
 
     class ChildNodeList : public DynamicNodeList {
     public:
-        static PassRefPtr<ChildNodeList> create(PassRefPtr<Node> rootNode, Caches* caches)
+        static PassRefPtr<ChildNodeList> create(PassRefPtr<Node> rootNode)
         {
-            return adoptRef(new ChildNodeList(rootNode, caches));
+            return adoptRef(new ChildNodeList(rootNode));
         }
 
+        virtual ~ChildNodeList();
+
         virtual unsigned length() const;
         virtual Node* item(unsigned index) const;
 
     protected:
-        ChildNodeList(PassRefPtr<Node> rootNode, Caches*);
+        ChildNodeList(PassRefPtr<Node> rootNode);
 
         virtual bool nodeMatches(Element*) const;
     };
diff --git a/Source/WebCore/dom/ContainerNode.cpp b/Source/WebCore/dom/ContainerNode.cpp
index 2d22fa9..5574aa5 100644
--- a/Source/WebCore/dom/ContainerNode.cpp
+++ b/Source/WebCore/dom/ContainerNode.cpp
@@ -3,6 +3,7 @@
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.
+ * Copyright (C) 2012 The Linux Foundation All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -74,6 +75,7 @@ static void collectTargetNodes(Node* node, NodeVector& nodes)
 void ContainerNode::removeAllChildren()
 {
     removeAllChildrenInContainer<Node, ContainerNode>(this);
+    updateNextNode();
 }
 
 void ContainerNode::takeAllChildrenFrom(ContainerNode* oldParent)
@@ -208,6 +210,8 @@ void ContainerNode::insertBeforeCommon(Node* nextChild, Node* newChild)
     newChild->setParent(this);
     newChild->setPreviousSibling(prev);
     newChild->setNextSibling(nextChild);
+    newChild->updatePreviousNode();
+    newChild->lastDescendantNode(true)->updateNextNode();
     allowEventDispatch();
 }
 
@@ -335,6 +339,9 @@ bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, Exce
         child->setParent(this);
         child->setPreviousSibling(prev.get());
         child->setNextSibling(next);
+        child->updatePreviousNode();
+        child->lastDescendantNode(true)->updateNextNode();
+
         allowEventDispatch();
 
         childrenChanged(false, prev.get(), next, 1);
@@ -362,12 +369,13 @@ bool ContainerNode::replaceChild(PassRefPtr<Node> newChild, Node* oldChild, Exce
 
 void ContainerNode::willRemove()
 {
-    Vector<RefPtr<Node>, 10> nodes;
-    nodes.reserveInitialCapacity(childNodeCount());
-    for (Node* n = m_lastChild; n; n = n->previousSibling())
-        nodes.append(n);
-    for (; nodes.size(); nodes.removeLast())
-        nodes.last().get()->willRemove();
+    Node* next;
+    Node* child = m_firstChild;
+    while (child) {
+        next = child->nextSibling();
+        child->willRemove();
+        child = next;
+    }
     Node::willRemove();
 }
 
@@ -468,6 +476,8 @@ void ContainerNode::removeBetween(Node* previousChild, Node* nextChild, Node* ol
     if (oldChild->attached())
         oldChild->detach();
 
+    Node* previousNode = oldChild->traversePreviousNodeFastPath();
+
     if (nextChild)
         nextChild->setPreviousSibling(previousChild);
     if (previousChild)
@@ -480,6 +490,10 @@ void ContainerNode::removeBetween(Node* previousChild, Node* nextChild, Node* ol
     oldChild->setPreviousSibling(0);
     oldChild->setNextSibling(0);
     oldChild->setParent(0);
+    oldChild->setPreviousNode(0);
+    oldChild->lastDescendantNode(true)->setNextNode(0);
+    if (previousNode)
+        previousNode->updateNextNode();
 
     allowEventDispatch();
 }
@@ -530,6 +544,8 @@ void ContainerNode::removeChildren()
         n->setPreviousSibling(0);
         n->setNextSibling(0);
         n->setParent(0);
+        n->lastDescendantNode(true)->setNextNode(0);
+        n->setPreviousNode(0);
 
         m_firstChild = next;
         if (n == m_lastChild)
@@ -552,6 +568,7 @@ void ContainerNode::removeChildren()
             removedChild->detach();
     }
 
+    updateNextNode();
     allowEventDispatch();
 
     // Dispatch a single post-removal mutation event denoting a modified subtree.
@@ -621,6 +638,8 @@ bool ContainerNode::appendChild(PassRefPtr<Node> newChild, ExceptionCode& ec, bo
         } else
             m_firstChild = child;
         m_lastChild = child;
+        child->updatePreviousNode();
+        child->lastDescendantNode(true)->updateNextNode();
         allowEventDispatch();
 
         // Send notification about the children change.
@@ -658,6 +677,10 @@ void ContainerNode::parserAddChild(PassRefPtr<Node> newChild)
     Node* last = m_lastChild;
     // FIXME: This method should take a PassRefPtr.
     appendChildToContainer<Node, ContainerNode>(newChild.get(), this);
+    if (last)
+        last->updateNextNode();
+    newChild->updatePreviousNode();
+    newChild->lastDescendantNode(true)->updateNextNode();
     allowEventDispatch();
 
     // FIXME: Why doesn't this use notifyChildInserted(newChild) instead?
@@ -1070,8 +1093,12 @@ static void dispatchChildInsertionEvents(Node* child)
 
     // dispatch the DOMNodeInsertedIntoDocument event to all descendants
     if (c->inDocument() && document->hasListenerType(Document::DOMNODEINSERTEDINTODOCUMENT_LISTENER)) {
-        for (; c; c = c->traverseNextNode(child))
+        Node* last = child->lastDescendantNode(true);
+        for (; c; c = c->traverseNextNodeFastPath()) {
             c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeInsertedIntoDocumentEvent, false));
+            if (last == c)
+                break;
+        }
     }
 }
 
@@ -1092,8 +1119,12 @@ static void dispatchChildRemovalEvents(Node* child)
 
     // dispatch the DOMNodeRemovedFromDocument event to all descendants
     if (c->inDocument() && document->hasListenerType(Document::DOMNODEREMOVEDFROMDOCUMENT_LISTENER)) {
-        for (; c; c = c->traverseNextNode(child))
+        Node* last = c->lastDescendantNode(true);
+        for (; c; c = c->traverseNextNodeFastPath()) {
             c->dispatchScopedEvent(MutationEvent::create(eventNames().DOMNodeRemovedFromDocumentEvent, false));
+            if (last == c)
+                break;
+        }
     }
 }
 
diff --git a/Source/WebCore/dom/ContainerNode.h b/Source/WebCore/dom/ContainerNode.h
index 76eb1bd..ee8252e 100644
--- a/Source/WebCore/dom/ContainerNode.h
+++ b/Source/WebCore/dom/ContainerNode.h
@@ -170,6 +170,17 @@ inline Node* Node::lastChild() const
     return toContainerNode(this)->lastChild();
 }
 
+inline RenderObject* Node::previousRenderer()
+{
+    // FIXME: We should have the same O(N^2) avoidance as nextRenderer does
+    // however, when I tried adding it, several tests failed.
+    for (Node* n = previousSibling(); n; n = n->previousSibling()) {
+        if (n->renderer())
+            return n->renderer();
+    }
+    return 0;
+}
+
 } // namespace WebCore
 
 #endif // ContainerNode_h
diff --git a/Source/WebCore/dom/Document.cpp b/Source/WebCore/dom/Document.cpp
index e338c8e..60ecdb9 100644
--- a/Source/WebCore/dom/Document.cpp
+++ b/Source/WebCore/dom/Document.cpp
@@ -7,7 +7,7 @@
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (C) 2008, 2009 Google Inc. All rights reserved.
  * Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies)
- * Copyright (c) 2011, 2012 Code Aurora Forum. All rights reserved
+ * Copyright (c) 2011, 2012 The Linux Foundation All rights reserved
  * Copyright (C) 2011, 2012 Sony Ericsson Mobile Communications AB
  * Copyright (C) 2012 Sony Mobile Communcations AB
  *
@@ -1816,7 +1816,7 @@ void Document::removeAllEventListeners()
 
     if (DOMWindow* domWindow = this->domWindow())
         domWindow->removeAllEventListeners();
-    for (Node* node = firstChild(); node; node = node->traverseNextNode())
+    for (Node* node = firstChild(); node; node = node->traverseNextNodeFastPath())
         node->removeAllEventListeners();
 }
 
@@ -3848,11 +3848,12 @@ static inline bool isValidNameASCII(const UChar* characters, unsigned length)
 
 bool Document::isValidName(const String& name)
 {
-    unsigned length = name.length();
-    if (!length)
+    if (name.isEmpty())
         return false;
 
-    const UChar* characters = name.characters();
+    StringImpl* impl = name.impl();
+    const UChar* characters = impl->characters();
+    unsigned length = impl->length();
     return isValidNameASCII(characters, length) || isValidNameNonASCII(characters, length);
 }
 
diff --git a/Source/WebCore/dom/Document.h b/Source/WebCore/dom/Document.h
index 685e3b7..44f3f93 100644
--- a/Source/WebCore/dom/Document.h
+++ b/Source/WebCore/dom/Document.h
@@ -6,7 +6,7 @@
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
  * Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies)
- * Copyright (c) 2011, 2012 Code Aurora Forum. All rights reserved
+ * Copyright (c) 2011, 2012 The Linux Foundation All rights reserved
  * Copyright (C) 2011, 2012 Sony Ericsson Mobile Communications AB
  * Copyright (C) 2012 Sony Mobile Communcations AB
  *
@@ -1429,8 +1429,11 @@ inline Node::Node(Document* document, ConstructionType type)
     : m_document(document)
     , m_previous(0)
     , m_next(0)
+    , m_prefetch(0)
     , m_renderer(0)
     , m_nodeFlags(type)
+    , m_previousNode(0)
+    , m_nextNode(0)
 {
     if (m_document)
         m_document->guardRef();
diff --git a/Source/WebCore/dom/DocumentOrderedMap.cpp b/Source/WebCore/dom/DocumentOrderedMap.cpp
index 47268c4..73a0843 100644
--- a/Source/WebCore/dom/DocumentOrderedMap.cpp
+++ b/Source/WebCore/dom/DocumentOrderedMap.cpp
@@ -117,7 +117,7 @@ inline Element* DocumentOrderedMap::get(AtomicStringImpl* key, const TreeScope*
 
     if (m_duplicateCounts.contains(key)) {
         // We know there's at least one node that matches; iterate to find the first one.
-        for (Node* node = scope->firstChild(); node; node = node->traverseNextNode()) {
+        for (Node* node = scope->firstChild(); node; node = node->traverseNextNodeFastPath()) {
             if (!node->isElementNode())
                 continue;
             element = static_cast<Element*>(node);
diff --git a/Source/WebCore/dom/DynamicNodeList.cpp b/Source/WebCore/dom/DynamicNodeList.cpp
index 23664e8..bba1678 100644
--- a/Source/WebCore/dom/DynamicNodeList.cpp
+++ b/Source/WebCore/dom/DynamicNodeList.cpp
@@ -3,6 +3,7 @@
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2006, 2007, 2008, 2010 Apple Inc. All rights reserved.
+ * Copyright (C) 2012 The Linux Foundation All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -56,8 +57,18 @@ unsigned DynamicNodeList::length() const
 
     unsigned length = 0;
 
-    for (Node* n = m_rootNode->firstChild(); n; n = n->traverseNextNode(m_rootNode.get()))
-        length += n->isElementNode() && nodeMatches(static_cast<Element*>(n));
+    Node* lastNode = m_rootNode->lastDescendantNode();
+    Vector<Node* >& cachedNodes = m_caches->cachedNodes;
+    for (Node* n = m_rootNode->firstChild(); n; n = n->traverseNextNodeFastPath()) {
+        if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
+            if (length >= cachedNodes.size())
+                cachedNodes.resize(length + 1);
+            cachedNodes.data()[length] = n;
+            length ++;
+        }
+        if (n == lastNode)
+            break;
+    }
 
     m_caches->cachedLength = length;
     m_caches->isLengthCacheValid = true;
@@ -68,7 +79,9 @@ unsigned DynamicNodeList::length() const
 Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int remainingOffset) const
 {
     ASSERT(remainingOffset >= 0);
-    for (Node* n = start; n; n = n->traverseNextNode(m_rootNode.get())) {
+    if (!m_caches->lastDecendantOfRoot)
+        m_caches->lastDecendantOfRoot = m_rootNode->lastDescendantNode();
+    for (Node* n = start; n; n = n->traverseNextNodeFastPath()) {
         if (n->isElementNode() && nodeMatches(static_cast<Element*>(n))) {
             if (!remainingOffset) {
                 m_caches->lastItem = n;
@@ -78,6 +91,8 @@ Node* DynamicNodeList::itemForwardsFromCurrent(Node* start, unsigned offset, int
             }
             --remainingOffset;
         }
+        if (n == m_caches->lastDecendantOfRoot)
+            break;
     }
 
     return 0; // no matching node in this subtree
@@ -103,6 +118,14 @@ Node* DynamicNodeList::itemBackwardsFromCurrent(Node* start, unsigned offset, in
 
 Node* DynamicNodeList::item(unsigned offset) const
 {
+    Node* result;
+    Vector<Node* >& cachedNodes = m_caches->cachedNodes;
+    if (offset < cachedNodes.size()) {
+        result = cachedNodes[offset];
+        if (result)
+            return result;
+    }
+
     int remainingOffset = offset;
     Node* start = m_rootNode->firstChild();
     if (m_caches->isItemCacheValid) {
@@ -115,8 +138,16 @@ Node* DynamicNodeList::item(unsigned offset) const
     }
 
     if (remainingOffset < 0)
-        return itemBackwardsFromCurrent(start, offset, remainingOffset);
-    return itemForwardsFromCurrent(start, offset, remainingOffset);
+        result = itemBackwardsFromCurrent(start, offset, remainingOffset);
+    else
+        result = itemForwardsFromCurrent(start, offset, remainingOffset);
+
+    if (result) {
+        if (offset >= cachedNodes.size())
+            cachedNodes.resize(offset + 1);
+        cachedNodes.data()[offset] = result;
+    }
+    return result;
 }
 
 Node* DynamicNodeList::itemWithName(const AtomicString& elementId) const
@@ -159,6 +190,7 @@ void DynamicNodeList::invalidateCache()
 
 DynamicNodeList::Caches::Caches()
     : lastItem(0)
+    , lastDecendantOfRoot(0)
     , isLengthCacheValid(false)
     , isItemCacheValid(false)
 {
@@ -172,8 +204,10 @@ PassRefPtr<DynamicNodeList::Caches> DynamicNodeList::Caches::create()
 void DynamicNodeList::Caches::reset()
 {
     lastItem = 0;
+    lastDecendantOfRoot = 0;
     isLengthCacheValid = false;
-    isItemCacheValid = false;     
+    isItemCacheValid = false;
+    cachedNodes.clear();
 }
 
 } // namespace WebCore
diff --git a/Source/WebCore/dom/DynamicNodeList.h b/Source/WebCore/dom/DynamicNodeList.h
index 9c8f3cc..c8b6ca2 100644
--- a/Source/WebCore/dom/DynamicNodeList.h
+++ b/Source/WebCore/dom/DynamicNodeList.h
@@ -28,6 +28,12 @@
 #include <wtf/RefCounted.h>
 #include <wtf/Forward.h>
 #include <wtf/RefPtr.h>
+#include <wtf/Vector.h>
+
+namespace WTF {
+    // Properties in Vector can be initialized with memset and moved using memcpy.
+    template<> struct VectorTraits<WebCore::Node*> : SimpleClassVectorTraits { };
+}
 
 namespace WebCore {
 
@@ -42,9 +48,11 @@ namespace WebCore {
 
             unsigned cachedLength;
             Node* lastItem;
+            Node* lastDecendantOfRoot;
             unsigned lastItemOffset;
             bool isLengthCacheValid : 1;
             bool isItemCacheValid : 1;
+            Vector<Node* > cachedNodes;
         protected:
             Caches();
         };
diff --git a/Source/WebCore/dom/Node.cpp b/Source/WebCore/dom/Node.cpp
index da4312c..1e56278 100644
--- a/Source/WebCore/dom/Node.cpp
+++ b/Source/WebCore/dom/Node.cpp
@@ -5,6 +5,7 @@
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.
  * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies)
  * Copyright (C) 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
+ * Copyright (C) 2012 The Linux Foundation All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -130,6 +131,8 @@ namespace WebCore {
 
 using namespace HTMLNames;
 
+const int Node::cPrefetchTargetDepth = 7;
+
 bool Node::isSupported(const String& feature, const String& version)
 {
     return DOMImplementation::hasFeature(feature, version);
@@ -409,6 +412,8 @@ Node::~Node()
         m_previous->setNextSibling(0);
     if (m_next)
         m_next->setPreviousSibling(0);
+    m_nextNode = 0;
+    m_previousNode = 0;
 
     if (m_document)
         m_document->guardDeref();
@@ -517,9 +522,12 @@ void Node::setTreeScopeRecursively(TreeScope* newTreeScope)
     if (currentDocument && currentDocument != newDocument)
         currentDocument->incDOMTreeVersion();
 
-    for (Node* node = this; node; node = node->traverseNextNode(this)) {
+    Node* last = this->lastDescendantNode(true);
+    for (Node* node = this; node; node = node->traverseNextNodeFastPath()) {
         node->setTreeScope(newTreeScope);
         // FIXME: Once shadow scopes are landed, update parent scope, etc.
+        if (last == node)
+            break;
     }
 }
 
@@ -548,18 +556,22 @@ NodeRareData* Node::createRareData()
 
 Element* Node::shadowHost() const
 {
-    return toElement(getFlag(IsShadowRootFlag) ? parent() : 0);
+    return toElement(isShadowRoot() ? parent() : 0);
 }
 
 void Node::setShadowHost(Element* host)
 {
     ASSERT(!parentNode() && !isSVGShadowRoot());
     if (host)
-        setFlag(IsShadowRootFlag);
+        setFlag(IsShadowRootOrSVGShadowRootFlag);
     else
-        clearFlag(IsShadowRootFlag);
+        clearFlag(IsShadowRootOrSVGShadowRootFlag);
 
     setParent(host);
+    updatePreviousNode();
+    lastDescendantNode(true)->updateNextNode();
+    if (host)
+        host->updateNextNode();
 }
 
 InputElement* Node::toInputElement()
@@ -607,14 +619,13 @@ void Node::setNodeValue(const String& /*nodeValue*/, ExceptionCode& ec)
 
 PassRefPtr<NodeList> Node::childNodes()
 {
-    NodeRareData* data = ensureRareData();
-    if (!data->nodeLists()) {
-        data->setNodeLists(NodeListsNodeData::create());
-        if (document())
-            document()->addNodeListCache();
-    }
+    NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this);
+    if (data->m_childNodeListCache)
+        return PassRefPtr<ChildNodeList>(data->m_childNodeListCache);
 
-    return ChildNodeList::create(this, data->nodeLists()->m_childNodeListCaches.get());
+    RefPtr<ChildNodeList> childNodeList = ChildNodeList::create(this);
+    data->m_childNodeListCache = childNodeList.get();
+    return childNodeList.release();
 }
 
 Node *Node::lastDescendant() const
@@ -862,12 +873,15 @@ void Node::setDocumentRecursively(Document* newDocument)
 {
     ASSERT(document() != newDocument);
 
-    for (Node* node = this; node; node = node->traverseNextNode(this)) {
+    Node* last = this->lastDescendantNode(true);
+    for (Node* node = this; node; node = node->traverseNextNodeFastPath()) {
         node->setDocument(newDocument);
-        if (!node->isElementNode())
-            continue;
-        if (Node* shadow = shadowRoot(node))
-            shadow->setDocumentRecursively(newDocument);
+        if (node->isElementNode()) {
+            if (Node* shadow = shadowRoot(node))
+                shadow->setDocumentRecursively(newDocument);
+        }
+        if (node == last)
+            break;
     }
 }
 
@@ -911,12 +925,15 @@ void Node::setNeedsStyleRecalc(StyleChangeType changeType)
 
 void Node::lazyAttach(ShouldSetAttached shouldSetAttached)
 {
-    for (Node* n = this; n; n = n->traverseNextNode(this)) {
+    Node* last = this->lastDescendantNode(true);
+    for (Node* n = this; n; n = n->traverseNextNodeFastPath()) {
         if (n->firstChild())
             n->setChildNeedsStyleRecalc();
         n->setStyleChange(FullStyleChange);
         if (shouldSetAttached == SetAttached)
             n->setAttached();
+        if (n == last)
+            break;
     }
     markAncestorsWithChildNeedsStyleRecalc();
 }
@@ -1092,7 +1109,7 @@ void Node::removeCachedNameNodeList(NameNodeList* list, const String& nodeName)
     data->m_nameNodeListCache.remove(nodeName);
 }
 
-void Node::removeCachedTagNodeList(TagNodeList* list, const QualifiedName& name)
+void Node::removeCachedTagNodeList(TagNodeList* list, const AtomicString& name)
 {
     ASSERT(rareData());
     ASSERT(rareData()->nodeLists());
@@ -1103,6 +1120,17 @@ void Node::removeCachedTagNodeList(TagNodeList* list, const QualifiedName& name)
     data->m_tagNodeListCache.remove(name.impl());
 }
 
+void Node::removeCachedTagNodeListNS(TagNodeListNS* list, const QualifiedName& name)
+{
+    ASSERT(rareData());
+    ASSERT(rareData()->nodeLists());
+    ASSERT_UNUSED(list, list->hasOwnCaches());
+
+    NodeListsNodeData* data = rareData()->nodeLists();
+    ASSERT_UNUSED(list, list == data->m_tagNodeListCacheNS.get(name.impl()));
+    data->m_tagNodeListCacheNS.remove(name.impl());
+}
+
 void Node::removeCachedLabelsNodeList(DynamicNodeList* list)
 {
     ASSERT(rareData());
@@ -1113,14 +1141,27 @@ void Node::removeCachedLabelsNodeList(DynamicNodeList* list)
     data->m_labelsNodeListCache = 0;
 }
 
+void Node::removeCachedChildNodeList(DynamicNodeList* list)
+{
+    ASSERT(rareData());
+    ASSERT(rareData()->nodeLists());
+    ASSERT_UNUSED(list, list->hasOwnCaches());
+
+    NodeListsNodeData* data = rareData()->nodeLists();
+    data->m_childNodeListCache = 0;
+}
+
 Node* Node::traverseNextNode(const Node* stayWithin) const
 {
-    if (firstChild())
-        return firstChild();
+    prefetchTarget();
+    Node* fc = firstChild();
+    if (fc)
+        return fc;
     if (this == stayWithin)
         return 0;
-    if (nextSibling())
-        return nextSibling();
+    Node* ns = nextSibling();
+    if (ns)
+        return ns;
     const Node *n = this;
     while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
         n = n->parentNode();
@@ -1129,15 +1170,54 @@ Node* Node::traverseNextNode(const Node* stayWithin) const
     return 0;
 }
 
+Node* Node::lastDescendantNode(bool includeThis) const
+{
+    Node* n = lastChild();
+    if (!n && includeThis)
+        return const_cast<Node*>(this);
+
+    Node* p = n;
+    while(n) {
+        p = n;
+        n = n->lastChild();
+    }
+    return p;
+}
+
+void Node::updatePrevNextNodesInSubtree()
+{
+    Node* n = firstChild();
+    Node* next;
+    while(n) {
+        next = n->traverseNextNode(this);
+        if (next) {
+            n->setNextNode(next);
+            next->setPreviousNode(n);
+        } else {
+            next = n->traverseNextNode();
+            n->setNextNode(next);
+            if (next)
+                next->setPreviousNode(n);
+            break;
+        }
+        n = next;
+    }
+    updateNextNode();
+}
+
 Node* Node::traverseNextSibling(const Node* stayWithin) const
 {
     if (this == stayWithin)
         return 0;
-    if (nextSibling())
-        return nextSibling();
+    prefetchTarget();
+    Node* ns = nextSibling();
+    if (ns)
+        return ns;
     const Node *n = this;
-    while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin))
+    while (n && !n->nextSibling() && (!stayWithin || n->parentNode() != stayWithin)) {
+        n->prefetchTarget();
         n = n->parentNode();
+    }
     if (n)
         return n->nextSibling();
     return 0;
@@ -1157,10 +1237,11 @@ Node* Node::traversePreviousNode(const Node* stayWithin) const
 {
     if (this == stayWithin)
         return 0;
-    if (previousSibling()) {
-        Node *n = previousSibling();
-        while (n->lastChild())
-            n = n->lastChild();
+    Node *n = previousSibling();
+    if (n) {
+        Node* lastChild;
+        while ((lastChild = n->lastChild()))
+            n = lastChild;
         return n;
     }
     return parentNode();
@@ -1168,12 +1249,12 @@ Node* Node::traversePreviousNode(const Node* stayWithin) const
 
 Node* Node::traversePreviousNodePostOrder(const Node* stayWithin) const
 {
-    if (lastChild())
-        return lastChild();
+    if (Node* lc = lastChild())
+        return lc;
     if (this == stayWithin)
         return 0;
-    if (previousSibling())
-        return previousSibling();
+    if (Node* ps = previousSibling())
+        return ps;
     const Node *n = this;
     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
         n = n->parentNode();
@@ -1186,8 +1267,8 @@ Node* Node::traversePreviousSiblingPostOrder(const Node* stayWithin) const
 {
     if (this == stayWithin)
         return 0;
-    if (previousSibling())
-        return previousSibling();
+    if (Node* ps = previousSibling())
+        return ps;
     const Node *n = this;
     while (n && !n->previousSibling() && (!stayWithin || n->parentNode() != stayWithin))
         n = n->parentNode();
@@ -1333,14 +1414,20 @@ void Node::attach()
     // FIXME: This is O(N^2) for the innerHTML case, where all children are replaced at once (and not attached).
     // If this node got a renderer it may be the previousRenderer() of sibling text nodes and thus affect the
     // result of Text::rendererIsNeeded() for those nodes.
-    if (renderer()) {
+    RenderObject* renderer = this->renderer();
+    if (renderer) {
         for (Node* next = nextSibling(); next; next = next->nextSibling()) {
             if (next->renderer())
                 break;
             if (!next->attached())
                 break;  // Assume this means none of the following siblings are attached.
-            if (next->isTextNode())
+            if (next->isTextNode()) {
+                static_cast<Text*>(next)->setPreviousRenderer(renderer);
                 next->createRendererIfNeeded();
+                if (next->renderer())
+                    renderer = next->renderer();
+                static_cast<Text*>(next)->setPreviousRenderer(0);
+            }
         }
     }
 
@@ -1366,23 +1453,7 @@ void Node::detach()
     if (inActiveChain())
         doc->activeChainNodeDetached(this);
 
-    clearFlag(IsActiveFlag);
-    clearFlag(IsHoveredFlag);
-    clearFlag(InActiveChainFlag);
-    clearFlag(IsAttachedFlag);
-
-    clearFlag(InDetachFlag);
-}
-
-RenderObject* Node::previousRenderer()
-{
-    // FIXME: We should have the same O(N^2) avoidance as nextRenderer does
-    // however, when I tried adding it, several tests failed.
-    for (Node* n = previousSibling(); n; n = n->previousSibling()) {
-        if (n->renderer())
-            return n->renderer();
-    }
-    return 0;
+    clearFlag(NodeDetachClearFlags);
 }
 
 RenderObject* Node::nextRenderer()
@@ -1697,44 +1768,45 @@ bool Node::inSameContainingBlockFlowElement(Node *n)
 
 PassRefPtr<NodeList> Node::getElementsByTagName(const AtomicString& name)
 {
-    return getElementsByTagNameNS(starAtom, name);
+    if (name.isNull())
+        return 0;
+
+    NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this);
+
+    AtomicString localNameAtom = document()->isHTMLDocument() ? name.lower() : name;
+
+    pair<NodeListsNodeData::TagNodeListCache::iterator, bool> result = data->m_tagNodeListCache.add(localNameAtom.impl(), 0);
+    if (!result.second)
+        return PassRefPtr<TagNodeList>(result.first->second);
+
+    RefPtr<TagNodeList> list = TagNodeList::create(this, localNameAtom);
+    result.first->second = list.get();
+    return list.release();
 }
  
 PassRefPtr<NodeList> Node::getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName)
 {
     if (localName.isNull())
         return 0;
-    
-    NodeRareData* data = ensureRareData();
-    if (!data->nodeLists()) {
-        data->setNodeLists(NodeListsNodeData::create());
-        document()->addNodeListCache();
-    }
 
-    String name = localName;
-    if (document()->isHTMLDocument())
-        name = localName.lower();
-    
-    AtomicString localNameAtom = name;
-        
-    pair<NodeListsNodeData::TagNodeListCache::iterator, bool> result = data->nodeLists()->m_tagNodeListCache.add(QualifiedName(nullAtom, localNameAtom, namespaceURI).impl(), 0);
+    NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this);
+
+    AtomicString localNameAtom = document()->isHTMLDocument() ? localName.lower() : localName;
+
+    pair<NodeListsNodeData::TagNodeListCacheNS::iterator, bool> result = data->m_tagNodeListCacheNS.add(QualifiedName(nullAtom, localNameAtom, namespaceURI).impl(), 0);
     if (!result.second)
-        return PassRefPtr<TagNodeList>(result.first->second);
-    
-    RefPtr<TagNodeList> list = TagNodeList::create(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localNameAtom);
+        return PassRefPtr<TagNodeListNS>(result.first->second);
+
+    RefPtr<TagNodeListNS> list = TagNodeListNS::create(this, namespaceURI.isEmpty() ? nullAtom : namespaceURI, localNameAtom);
     result.first->second = list.get();
     return list.release();
 }
 
 PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
 {
-    NodeRareData* data = ensureRareData();
-    if (!data->nodeLists()) {
-        data->setNodeLists(NodeListsNodeData::create());
-        document()->addNodeListCache();
-    }
+    NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this);
 
-    pair<NodeListsNodeData::NameNodeListCache::iterator, bool> result = data->nodeLists()->m_nameNodeListCache.add(elementName, 0);
+    pair<NodeListsNodeData::NameNodeListCache::iterator, bool> result = data->m_nameNodeListCache.add(elementName, 0);
     if (!result.second)
         return PassRefPtr<NodeList>(result.first->second);
 
@@ -1745,13 +1817,9 @@ PassRefPtr<NodeList> Node::getElementsByName(const String& elementName)
 
 PassRefPtr<NodeList> Node::getElementsByClassName(const String& classNames)
 {
-    NodeRareData* data = ensureRareData();
-    if (!data->nodeLists()) {
-        data->setNodeLists(NodeListsNodeData::create());
-        document()->addNodeListCache();
-    }
+    NodeListsNodeData* data = ensureRareData()->ensureNodeLists(this);
 
-    pair<NodeListsNodeData::ClassNodeListCache::iterator, bool> result = data->nodeLists()->m_classNodeListCache.add(classNames, 0);
+    pair<NodeListsNodeData::ClassNodeListCache::iterator, bool> result = data->m_classNodeListCache.add(classNames, 0);
     if (!result.second)
         return PassRefPtr<NodeList>(result.first->second);
 
@@ -1794,7 +1862,8 @@ PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode&
     }
 
     // FIXME: We can speed this up by implementing caching similar to the one use by getElementById
-    for (Node* n = firstChild(); n; n = n->traverseNextNode(this)) {
+    Node* last = lastDescendantNode();
+    for (Node* n = firstChild(); n; n = n->traverseNextNodeFastPath()) {
         if (n->isElementNode()) {
             Element* element = static_cast<Element*>(n);
             for (CSSSelector* selector = querySelectorList.first(); selector; selector = CSSSelectorList::next(selector)) {
@@ -1802,6 +1871,8 @@ PassRefPtr<Element> Node::querySelector(const String& selectors, ExceptionCode&
                     return element;
             }
         }
+        if (n == last)
+            break;
     }
     
     return 0;
@@ -2425,10 +2496,14 @@ void Node::formatForDebugger(char* buffer, unsigned length) const
 
 void NodeListsNodeData::invalidateCaches()
 {
-    m_childNodeListCaches->reset();
+    if (m_childNodeListCache)
+        m_childNodeListCache->invalidateCache();
 
     if (m_labelsNodeListCache)
         m_labelsNodeListCache->invalidateCache();
+    TagNodeListCacheNS::const_iterator tagCacheEndNS = m_tagNodeListCacheNS.end();
+    for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEndNS; ++it)
+        it->second->invalidateCache();
     TagNodeListCache::const_iterator tagCacheEnd = m_tagNodeListCache.end();
     for (TagNodeListCache::const_iterator it = m_tagNodeListCache.begin(); it != tagCacheEnd; ++it)
         it->second->invalidateCache();
@@ -2453,9 +2528,15 @@ bool NodeListsNodeData::isEmpty() const
     if (!m_listsWithCaches.isEmpty())
         return false;
 
-    if (m_childNodeListCaches->refCount())
+    if (m_childNodeListCache)
         return false;
     
+    TagNodeListCacheNS::const_iterator tagCacheEndNS = m_tagNodeListCacheNS.end();
+    for (TagNodeListCacheNS::const_iterator it = m_tagNodeListCacheNS.begin(); it != tagCacheEndNS; ++it) {
+        if (it->second->refCount())
+            return false;
+    }
+
     TagNodeListCache::const_iterator tagCacheEnd = m_tagNodeListCache.end();
     for (TagNodeListCache::const_iterator it = m_tagNodeListCache.begin(); it != tagCacheEnd; ++it) {
         if (it->second->refCount())
diff --git a/Source/WebCore/dom/Node.h b/Source/WebCore/dom/Node.h
index 76355c3..886dd88 100644
--- a/Source/WebCore/dom/Node.h
+++ b/Source/WebCore/dom/Node.h
@@ -4,6 +4,7 @@
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
+ * Copyright (C) 2012 The Linux Foundation All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -75,6 +76,7 @@ class RenderStyle;
 class SVGUseElement;
 #endif
 class TagNodeList;
+class TagNodeListNS;
 class TreeScope;
 
 typedef int ExceptionCode;
@@ -121,6 +123,8 @@ public:
         DOCUMENT_POSITION_IMPLEMENTATION_SPECIFIC = 0x20,
     };
 
+    static const int cPrefetchTargetDepth;
+
     static bool isSupported(const String& feature, const String& version);
 
     static void startIgnoringLeaks();
@@ -143,8 +147,8 @@ public:
     virtual NodeType nodeType() const = 0;
     ContainerNode* parentNode() const;
     Element* parentElement() const;
-    Node* previousSibling() const { return m_previous; }
-    Node* nextSibling() const { return m_next; }
+    ALWAYS_INLINE Node* previousSibling() const { return m_previous; }
+    ALWAYS_INLINE Node* nextSibling() const { return m_next; }
     PassRefPtr<NodeList> childNodes();
     Node* firstChild() const;
     Node* lastChild() const;
@@ -187,14 +191,14 @@ public:
     
     // Other methods (not part of DOM)
 
-    bool isElementNode() const { return getFlag(IsElementFlag); }
-    bool isContainerNode() const { return getFlag(IsContainerFlag); }
+    ALWAYS_INLINE bool isElementNode() const { return getFlag(IsElementFlag); }
+    ALWAYS_INLINE bool isContainerNode() const { return getFlag(IsContainerFlag); }
     bool isTextNode() const { return getFlag(IsTextFlag); }
 
     bool isHTMLElement() const { return getFlag(IsHTMLFlag); }
 
-    bool isSVGElement() const { return getFlag(IsSVGFlag); }
-    virtual bool isSVGShadowRoot() const { return false; }
+    ALWAYS_INLINE bool isSVGElement() const { return getFlag(IsSVGFlag); }
+    ALWAYS_INLINE bool isSVGShadowRoot() const { return getFlag(IsShadowRootOrSVGShadowRootFlag) && isSVGElement(); }
 #if ENABLE(SVG)
     SVGUseElement* svgShadowHost() const;
 #endif
@@ -213,7 +217,7 @@ public:
     bool isCommentNode() const { return getFlag(IsCommentFlag); }
     virtual bool isCharacterDataNode() const { return false; }
     bool isDocumentNode() const;
-    bool isShadowRoot() const { return getFlag(IsShadowRootFlag); }
+    bool isShadowRoot() const { return getFlag(IsShadowRootOrSVGShadowRootFlag) && !isSVGElement(); }
     // FIXME: Remove this when all shadow roots are ShadowRoots.
     virtual bool isShadowBoundary() const { return false; }
     virtual bool canHaveLightChildRendererWithShadow() const { return false; }
@@ -240,7 +244,26 @@ public:
     
     // These low-level calls give the caller responsibility for maintaining the integrity of the tree.
     void setPreviousSibling(Node* previous) { m_previous = previous; }
-    void setNextSibling(Node* next) { m_next = next; }
+    ALWAYS_INLINE void updatePrefetchTarget() {
+        if (m_next) {
+            int skew;
+            Node* from = this;
+            Node* n = from->traversePreviousNodePostOrder();
+            for (skew = cPrefetchTargetDepth - 1; skew && n; skew--) {
+                from = n;
+                n = n->traversePreviousNodePostOrder();
+            }
+            from->setPrefetchTarget(m_next);
+        }
+    }
+    void setPrefetchTarget(Node *prefetch) { m_prefetch = prefetch; }
+    void setNextSibling(Node* next) { m_next = next; updatePrefetchTarget(); }
+    void updatePreviousNode() { m_previousNode = traversePreviousNode(); if (m_previousNode) m_previousNode->setNextNode(this); }
+    void updateNextNode() { m_nextNode = traverseNextNode(); if (m_nextNode) m_nextNode->setPreviousNode(this); }
+    void updatePrevNextNodesInSubtree();
+
+    void setPreviousNode(Node* previous) { m_previousNode = previous; }
+    void setNextNode(Node* next) { m_nextNode = next; }
 
     // FIXME: These two functions belong in editing -- "atomic node" is an editing concept.
     Node* previousNodeConsideringAtomicNodes() const;
@@ -314,6 +337,9 @@ public:
     void setIsLink() { setFlag(IsLinkFlag); }
     void clearIsLink() { clearFlag(IsLinkFlag); }
 
+    void setIeForbidsInsertHTML() { setFlag(IeForbidsInsertHTML); }
+    bool ieForbidsInsertHTML() const { return getFlag(IeForbidsInsertHTML); }
+
     enum ShouldSetAttached {
         SetAttached,
         DoNotSetAttached
@@ -392,12 +418,25 @@ public:
     // This can be used to restrict traversal to a particular sub-tree.
     Node* traverseNextNode(const Node* stayWithin = 0) const;
 
+    Node* traverseNextNodeFastPath() const { prefetchTarget(); return m_nextNode; }
+
+    ALWAYS_INLINE void prefetchTarget() const {
+        if (m_prefetch) {
+            __builtin_prefetch(((char *) m_prefetch));
+            __builtin_prefetch(((char *) m_prefetch) + 64);
+        }
+    }
+
+    Node* lastDescendantNode(bool includeThis = false) const;
+
     // Like traverseNextNode, but skips children and starts with the next sibling.
     Node* traverseNextSibling(const Node* stayWithin = 0) const;
 
     // Does a reverse pre-order traversal to find the node that comes before the current one in document order
     Node* traversePreviousNode(const Node* stayWithin = 0) const;
 
+    Node* traversePreviousNodeFastPath() const { return m_previousNode; }
+
     // Like traverseNextNode, but visits parents after their children.
     Node* traverseNextNodePostOrder() const;
 
@@ -515,9 +554,11 @@ public:
     void notifyLocalNodeListsLabelChanged();
     void removeCachedClassNodeList(ClassNodeList*, const String&);
     void removeCachedNameNodeList(NameNodeList*, const String&);
-    void removeCachedTagNodeList(TagNodeList*, const QualifiedName&);
+    void removeCachedTagNodeList(TagNodeList*, const AtomicString&);
+    void removeCachedTagNodeListNS(TagNodeListNS*, const QualifiedName&);
     void removeCachedLabelsNodeList(DynamicNodeList*);
-    
+    void removeCachedChildNodeList(DynamicNodeList*);
+
     PassRefPtr<NodeList> getElementsByTagName(const AtomicString&);
     PassRefPtr<NodeList> getElementsByTagNameNS(const AtomicString& namespaceURI, const AtomicString& localName);
     PassRefPtr<NodeList> getElementsByName(const String& elementName);
@@ -593,7 +634,7 @@ private:
         InActiveChainFlag = 1 << 15,
         InDetachFlag = 1 << 16,
         HasRareDataFlag = 1 << 17,
-        IsShadowRootFlag = 1 << 18,
+        IsShadowRootOrSVGShadowRootFlag = 1 << 18,
 
         // These bits are used by derived classes, pulled up here so they can
         // be stored in the same memory word as the Node bits above.
@@ -605,11 +646,14 @@ private:
         IsSynchronizingSVGAttributesFlag = 1 << 23, // SVGElement
         HasSVGRareDataFlag = 1 << 24, // SVGElement
 #endif
-
         StyleChangeMask = 1 << nodeStyleChangeShift | 1 << (nodeStyleChangeShift + 1),
 
         SelfOrAncestorHasDirAutoFlag = 1 << 27,
 
+        IeForbidsInsertHTML = 1 << 28,
+
+        NodeDetachClearFlags = IsActiveFlag | IsHoveredFlag | InActiveChainFlag | IsAttachedFlag | InDetachFlag,
+
 #if ENABLE(SVG)
         DefaultNodeFlags = IsParsingChildrenFinishedFlag | IsStyleAttributeValidFlag | AreSVGAttributesValidFlag
 #else
@@ -619,7 +663,7 @@ private:
 
     // 4 bits remaining
 
-    bool getFlag(NodeFlags mask) const { return m_nodeFlags & mask; }
+    ALWAYS_INLINE bool getFlag(NodeFlags mask) const { return m_nodeFlags & mask; }
     void setFlag(bool f, NodeFlags mask) const { m_nodeFlags = (m_nodeFlags & ~mask) | (-(int32_t)f & mask); } 
     void setFlag(NodeFlags mask) const { m_nodeFlags |= mask; } 
     void clearFlag(NodeFlags mask) const { m_nodeFlags &= ~mask; } 
@@ -631,9 +675,11 @@ protected:
         CreateComment = DefaultNodeFlags | IsCommentFlag,
         CreateContainer = DefaultNodeFlags | IsContainerFlag, 
         CreateElement = CreateContainer | IsElementFlag, 
+        CreateShadowRoot = CreateContainer | IsShadowRootOrSVGShadowRootFlag,
         CreateStyledElement = CreateElement | IsStyledElementFlag, 
         CreateHTMLElement = CreateStyledElement | IsHTMLFlag, 
         CreateSVGElement = CreateStyledElement | IsSVGFlag, 
+        CreateSVGShadowRoot = CreateSVGElement | IsShadowRootOrSVGShadowRootFlag,
     };
     Node(Document*, ConstructionType);
 
@@ -690,8 +736,11 @@ private:
     Document* m_document;
     Node* m_previous;
     Node* m_next;
+    Node* m_prefetch;
     RenderObject* m_renderer;
     mutable uint32_t m_nodeFlags;
+    Node* m_previousNode;
+    Node* m_nextNode;
 
 protected:
     bool isParsingChildrenFinished() const { return getFlag(IsParsingChildrenFinishedFlag); }
@@ -728,7 +777,7 @@ inline void addSubresourceURL(ListHashSet<KURL>& urls, const KURL& url)
 
 inline ContainerNode* Node::parentNode() const
 {
-    return getFlag(IsShadowRootFlag) || isSVGShadowRoot() ? 0 : parent();
+    return getFlag(IsShadowRootOrSVGShadowRootFlag) ? 0 : parent();
 }
 
 inline ContainerNode* Node::parentOrHostNode() const
@@ -738,7 +787,7 @@ inline ContainerNode* Node::parentOrHostNode() const
 
 inline ContainerNode* Node::parentNodeGuaranteedHostFree() const
 {
-    ASSERT(!getFlag(IsShadowRootFlag) && !isSVGShadowRoot());
+    ASSERT(!getFlag(IsShadowRootOrSVGShadowRootFlag));
     return parentOrHostNode();
 }
 
diff --git a/Source/WebCore/dom/NodeRareData.h b/Source/WebCore/dom/NodeRareData.h
index ac05d3e..b81dd3f 100644
--- a/Source/WebCore/dom/NodeRareData.h
+++ b/Source/WebCore/dom/NodeRareData.h
@@ -22,6 +22,7 @@
 #ifndef NodeRareData_h
 #define NodeRareData_h
 
+#include "ChildNodeList.h"
 #include "ClassNodeList.h"
 #include "DynamicNodeList.h"
 #include "NameNodeList.h"
@@ -42,17 +43,20 @@ public:
     typedef HashSet<DynamicNodeList*> NodeListSet;
     NodeListSet m_listsWithCaches;
     
-    RefPtr<DynamicNodeList::Caches> m_childNodeListCaches;
+    RefPtr<ChildNodeList> m_childNodeListCache;
     
     typedef HashMap<String, ClassNodeList*> ClassNodeListCache;
     ClassNodeListCache m_classNodeListCache;
 
     typedef HashMap<String, NameNodeList*> NameNodeListCache;
     NameNodeListCache m_nameNodeListCache;
-    
-    typedef HashMap<RefPtr<QualifiedName::QualifiedNameImpl>, TagNodeList*> TagNodeListCache;
+
+    typedef HashMap<AtomicStringImpl*, TagNodeList*> TagNodeListCache;
     TagNodeListCache m_tagNodeListCache;
 
+    typedef HashMap<RefPtr<QualifiedName::QualifiedNameImpl>, TagNodeListNS*> TagNodeListCacheNS;
+    TagNodeListCacheNS m_tagNodeListCacheNS;
+
     RefPtr<DynamicNodeList> m_labelsNodeListCache;
     
     static PassOwnPtr<NodeListsNodeData> create()
@@ -66,7 +70,8 @@ public:
 
 private:
     NodeListsNodeData()
-        : m_childNodeListCaches(DynamicNodeList::Caches::create()), m_labelsNodeListCache(0)
+        : m_childNodeListCache(0)
+        , m_labelsNodeListCache(0)
     {
     }
 };
@@ -106,6 +111,15 @@ public:
     void clearNodeLists() { m_nodeLists.clear(); }
     void setNodeLists(PassOwnPtr<NodeListsNodeData> lists) { m_nodeLists = lists; }
     NodeListsNodeData* nodeLists() const { return m_nodeLists.get(); }
+    NodeListsNodeData* ensureNodeLists(Node* n)
+    {
+        if (!m_nodeLists) {
+            m_nodeLists = NodeListsNodeData::create();
+            if (n->document())
+                n->document()->addNodeListCache();
+        }
+        return m_nodeLists.get();
+    }
 
     short tabIndex() const { return m_tabIndex; }
     void setTabIndexExplicitly(short index) { m_tabIndex = index; m_tabIndexWasSetExplicitly = true; }
diff --git a/Source/WebCore/dom/SelectorNodeList.cpp b/Source/WebCore/dom/SelectorNodeList.cpp
index 7611488..82f1103 100644
--- a/Source/WebCore/dom/SelectorNodeList.cpp
+++ b/Source/WebCore/dom/SelectorNodeList.cpp
@@ -1,5 +1,6 @@
 /*
  * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
+ * Copyright (C) 2012 The Linux Foundation All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -55,16 +56,25 @@ PassRefPtr<StaticNodeList> createSelectorNodeList(Node* rootNode, const CSSSelec
         if (element && (rootNode->isDocumentNode() || element->isDescendantOf(rootNode)) && selectorChecker.checkSelector(onlySelector, element))
             nodes.append(element);
     } else {
-        for (Node* n = rootNode->firstChild(); n; n = n->traverseNextNode(rootNode)) {
+        Vector<CSSSelector*> querySelectors;
+        querySelectors.reserveInitialCapacity(16);
+        for (CSSSelector* selector = querySelectorList.first(); selector; selector = CSSSelectorList::next(selector))
+            querySelectors.append(selector);
+        int querySelectorsCount = querySelectors.size();
+
+        Node* lastNode = rootNode->lastDescendantNode();
+        for (Node* n = rootNode->firstChild(); n; n = n->traverseNextNodeFastPath()) {
             if (n->isElementNode()) {
                 Element* element = static_cast<Element*>(n);
-                for (CSSSelector* selector = querySelectorList.first(); selector; selector = CSSSelectorList::next(selector)) {
-                    if (selectorChecker.checkSelector(selector, element)) {
+                for (int i = 0; i < querySelectorsCount; i++) {
+                    if (selectorChecker.checkSelector(querySelectors[i], element)) {
                         nodes.append(n);
                         break;
                     }
                 }
             }
+            if (n == lastNode)
+                break;
         }
     }
     
diff --git a/Source/WebCore/dom/TagNodeList.cpp b/Source/WebCore/dom/TagNodeList.cpp
index 4914e09..df51fe1 100644
--- a/Source/WebCore/dom/TagNodeList.cpp
+++ b/Source/WebCore/dom/TagNodeList.cpp
@@ -4,6 +4,7 @@
  *           (C) 2001 Dirk Mueller (mueller@kde.org)
  * Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
  * Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies)
+ * Copyright (C) 2012 The Linux Foundation All rights reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -29,25 +30,45 @@
 
 namespace WebCore {
 
-TagNodeList::TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
+TagNodeListNS::TagNodeListNS(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
     : DynamicNodeList(rootNode)
     , m_namespaceURI(namespaceURI)
     , m_localName(localName)
+    , m_isStarAtomNamespaceURI(m_namespaceURI == starAtom)
+    , m_isStarAtomlocalName(m_localName == starAtom)
 {
     ASSERT(m_namespaceURI.isNull() || !m_namespaceURI.isEmpty());
 }
 
-TagNodeList::~TagNodeList()
+TagNodeListNS::~TagNodeListNS()
 {
-    m_rootNode->removeCachedTagNodeList(this, QualifiedName(nullAtom, m_localName, m_namespaceURI));
-} 
+    m_rootNode->removeCachedTagNodeListNS(this, QualifiedName(nullAtom, m_localName, m_namespaceURI));
+}
 
-bool TagNodeList::nodeMatches(Element* testNode) const
+bool TagNodeListNS::nodeMatches(Element* testNode) const
 {
-    if (m_namespaceURI != starAtom && m_namespaceURI != testNode->namespaceURI())
+    if (!m_isStarAtomNamespaceURI && m_namespaceURI != testNode->namespaceURI())
         return false;
 
-    return m_localName == starAtom || m_localName == testNode->localName();
+    return m_isStarAtomlocalName || m_localName == testNode->localName();
 }
 
+TagNodeList::TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& localName)
+    : DynamicNodeList(rootNode)
+    , m_localName(localName)
+    , m_isStarAtomlocalName(m_localName == starAtom)
+{
+}
+
+TagNodeList::~TagNodeList()
+{
+    m_rootNode->removeCachedTagNodeList(this, m_localName);
+}
+
+bool TagNodeList::nodeMatches(Element* testNode) const
+{
+    return m_isStarAtomlocalName || m_localName == testNode->localName();
+}
+
+
 } // namespace WebCore
diff --git a/Source/WebCore/dom/TagNodeList.h b/Source/WebCore/dom/TagNodeList.h
index 9053b53..f255532 100644
--- a/Source/WebCore/dom/TagNodeList.h
+++ b/Source/WebCore/dom/TagNodeList.h
@@ -29,24 +29,45 @@
 
 namespace WebCore {
 
-    // NodeList that limits to a particular tag.
-    class TagNodeList : public DynamicNodeList {
-    public:
-        static PassRefPtr<TagNodeList> create(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
-        {
-            return adoptRef(new TagNodeList(rootNode, namespaceURI, localName));
-        }
+// NodeList with namespace that limits to a particular tag.
+class TagNodeListNS : public DynamicNodeList {
+public:
+    static PassRefPtr<TagNodeListNS> create(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName)
+    {
+        return adoptRef(new TagNodeListNS(rootNode, namespaceURI, localName));
+    }
 
-        virtual ~TagNodeList();
+    virtual ~TagNodeListNS();
 
-    private:
-        TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName);
+private:
+    TagNodeListNS(PassRefPtr<Node> rootNode, const AtomicString& namespaceURI, const AtomicString& localName);
 
-        virtual bool nodeMatches(Element*) const;
+    virtual bool nodeMatches(Element*) const;
 
-        AtomicString m_namespaceURI;
-        AtomicString m_localName;
-    };
+    AtomicString m_namespaceURI;
+    AtomicString m_localName;
+    bool m_isStarAtomNamespaceURI : 1;
+    bool m_isStarAtomlocalName : 1;
+};
+
+// NodeList that limits to a particular tag.
+class TagNodeList : public DynamicNodeList {
+public:
+    static PassRefPtr<TagNodeList> create(PassRefPtr<Node> rootNode, const AtomicString& localName)
+    {
+        return adoptRef(new TagNodeList(rootNode, localName));
+    }
+
+    virtual ~TagNodeList();
+
+private:
+    TagNodeList(PassRefPtr<Node> rootNode, const AtomicString& localName);
+
+    virtual bool nodeMatches(Element*) const;
+
+    AtomicString m_localName;
+    bool m_isStarAtomlocalName;
+};
 
 } // namespace WebCore
 
diff --git a/Source/WebCore/dom/Text.cpp b/Source/WebCore/dom/Text.cpp
index c4ea0a6..01a454d 100644
--- a/Source/WebCore/dom/Text.cpp
+++ b/Source/WebCore/dom/Text.cpp
@@ -213,7 +213,7 @@ bool Text::rendererIsNeeded(RenderStyle *style)
     if (style->preserveNewline()) // pre/pre-wrap/pre-line always make renderers.
         return true;
     
-    RenderObject *prev = previousRenderer();
+    RenderObject* prev = m_previousRenderer ? m_previousRenderer : previousRenderer();
     if (prev && prev->isBR()) // <span><br/> <br/></span>
         return false;
         
diff --git a/Source/WebCore/dom/Text.h b/Source/WebCore/dom/Text.h
index 5995f1f..4db3bb3 100644
--- a/Source/WebCore/dom/Text.h
+++ b/Source/WebCore/dom/Text.h
@@ -43,9 +43,12 @@ public:
 
     virtual void attach();
 
+    void setPreviousRenderer(RenderObject* renderer) { m_previousRenderer = renderer; }
+
 protected:
     Text(Document* document, const String& data)
         : CharacterData(document, data, CreateText)
+        , m_previousRenderer(0)
     {
     }
 
@@ -63,6 +66,8 @@ private:
 #ifndef NDEBUG
     virtual void formatForDebugger(char* buffer, unsigned length) const;
 #endif
+
+    RenderObject* m_previousRenderer;
 };
 
 } // namespace WebCore
diff --git a/Source/WebCore/dom/TreeScope.cpp b/Source/WebCore/dom/TreeScope.cpp
index a995a2d..45c7a8f 100644
--- a/Source/WebCore/dom/TreeScope.cpp
+++ b/Source/WebCore/dom/TreeScope.cpp
@@ -97,7 +97,7 @@ Element* TreeScope::getElementByAccessKey(const String& key) const
     if (key.isEmpty())
         return 0;
     if (!m_accessKeyMapValid) {
-        for (Node* n = firstChild(); n; n = n->traverseNextNode()) {
+        for (Node* n = firstChild(); n; n = n->traverseNextNodeFastPath()) {
             if (!n->isElementNode())
                 continue;
             Element* element = static_cast<Element*>(n);
@@ -149,7 +149,7 @@ Element* TreeScope::findAnchor(const String& name)
         return 0;
     if (Element* element = getElementById(name))
         return element;
-    for (Node* node = this; node; node = node->traverseNextNode()) {
+    for (Node* node = this; node; node = node->traverseNextNodeFastPath()) {
         if (node->hasTagName(aTag)) {
             HTMLAnchorElement* anchor = static_cast<HTMLAnchorElement*>(node);
             if (document()->inQuirksMode()) {