DOM Optimizations

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

Conflicts:

	Source/WebKit/android/jni/WebViewCore.cpp

Change-Id: Icbb8a7229ee9cff1a5401b57c8181f18b9a6d6e0

70 files changed, 881 insertions, 384 deletions

diff --git a/Source/JavaScriptCore/runtime/RopeImpl.h b/Source/JavaScriptCore/runtime/RopeImpl.h
index dfacbf5..5bfbde5 100644
--- a/Source/JavaScriptCore/runtime/RopeImpl.h
+++ b/Source/JavaScriptCore/runtime/RopeImpl.h
@@ -71,8 +71,8 @@ public:
 
     ALWAYS_INLINE void deref()
     {
-        m_refCountAndFlags -= s_refCountIncrement;
-        if (!(m_refCountAndFlags & s_refCountMask))
+        --m_refCount;
+        if (!m_refCount)
             destructNonRecursive();
     }
 
@@ -86,7 +86,7 @@ private:
     void destructNonRecursive();
     void derefFibersNonRecursive(Vector<RopeImpl*, 32>& workQueue);
 
-    bool hasOneRef() { return (m_refCountAndFlags & s_refCountMask) == s_refCountIncrement; }
+    bool hasOneRef() { return m_refCount == 1; }
 
     unsigned m_size;
     Fiber m_fibers[1];
diff --git a/Source/JavaScriptCore/wtf/RefPtr.h b/Source/JavaScriptCore/wtf/RefPtr.h
index 353bd35..aaa4a8e 100644
--- a/Source/JavaScriptCore/wtf/RefPtr.h
+++ b/Source/JavaScriptCore/wtf/RefPtr.h
@@ -57,7 +57,7 @@ namespace WTF {
 
         ALWAYS_INLINE ~RefPtr() { derefIfNotNull(m_ptr); }
 
-        T* get() const { return m_ptr; }
+        ALWAYS_INLINE T* get() const { return m_ptr; }
         
         void clear();
         PassRefPtr<T> release() { PassRefPtr<T> tmp = adoptRef(m_ptr); m_ptr = 0; return tmp; }
diff --git a/Source/JavaScriptCore/wtf/text/AtomicString.cpp b/Source/JavaScriptCore/wtf/text/AtomicString.cpp
index 9dd655e..3c02607 100644
--- a/Source/JavaScriptCore/wtf/text/AtomicString.cpp
+++ b/Source/JavaScriptCore/wtf/text/AtomicString.cpp
@@ -343,7 +343,7 @@ AtomicString AtomicString::lower() const
 {
     // Note: This is a hot function in the Dromaeo benchmark.
     StringImpl* impl = this->impl();
-    if (UNLIKELY(!impl))
+    if (UNLIKELY(!impl) || impl->isLower())
         return *this;
     RefPtr<StringImpl> newImpl = impl->lower();
     if (LIKELY(newImpl == impl))
diff --git a/Source/JavaScriptCore/wtf/text/AtomicString.h b/Source/JavaScriptCore/wtf/text/AtomicString.h
index 440700c..5ee9e5d 100644
--- a/Source/JavaScriptCore/wtf/text/AtomicString.h
+++ b/Source/JavaScriptCore/wtf/text/AtomicString.h
@@ -58,7 +58,7 @@ public:
     operator const String&() const { return m_string; }
     const String& string() const { return m_string; };
 
-    AtomicStringImpl* impl() const { return static_cast<AtomicStringImpl *>(m_string.impl()); }
+    ALWAYS_INLINE AtomicStringImpl* impl() const { return static_cast<AtomicStringImpl *>(m_string.impl()); }
     
     const UChar* characters() const { return m_string.characters(); }
     unsigned length() const { return m_string.length(); }
diff --git a/Source/JavaScriptCore/wtf/text/StringImpl.cpp b/Source/JavaScriptCore/wtf/text/StringImpl.cpp
index 9afd1d2..826e749 100644
--- a/Source/JavaScriptCore/wtf/text/StringImpl.cpp
+++ b/Source/JavaScriptCore/wtf/text/StringImpl.cpp
@@ -148,7 +148,7 @@ SharedUChar* StringImpl::sharedBuffer()
     if (ownership == BufferOwned) {
         ASSERT(!m_sharedBuffer);
         m_sharedBuffer = SharedUChar::create(new SharableUChar(m_data)).leakRef();
-        m_refCountAndFlags = (m_refCountAndFlags & ~s_refCountMaskBufferOwnership) | BufferShared;
+        m_bufferOwnership = BufferShared;
     }
 
     ASSERT(bufferOwnership() == BufferShared);
@@ -193,6 +193,8 @@ PassRefPtr<StringImpl> StringImpl::lower()
 {
     // Note: This is a hot function in the Dromaeo benchmark, specifically the
     // no-op code path up through the first 'return' statement.
+    if (isLower())
+        return this;
     
     // First scan the string for uppercase and non-ASCII characters:
     UChar ored = 0;
@@ -205,8 +207,10 @@ PassRefPtr<StringImpl> StringImpl::lower()
     }
     
     // Nothing to do if the string is all ASCII with no uppercase.
-    if (noUpper && !(ored & ~0x7F))
+    if (noUpper && !(ored & ~0x7F)) {
+        setIsLower(true);
         return this;
+    }
 
     if (m_length > static_cast<unsigned>(numeric_limits<int32_t>::max()))
         CRASH();
@@ -1060,7 +1064,7 @@ PassRefPtr<StringImpl> StringImpl::createWithTerminatingNullCharacter(const Stri
     data[length] = 0;
     terminatedString->m_length--;
     terminatedString->m_hash = string.m_hash;
-    terminatedString->m_refCountAndFlags |= s_refCountFlagHasTerminatingNullCharacter;
+    terminatedString->m_hasTerminatingNullCharacter = true;
     return terminatedString.release();
 }
 
diff --git a/Source/JavaScriptCore/wtf/text/StringImpl.h b/Source/JavaScriptCore/wtf/text/StringImpl.h
index 81911b3..bd51f78 100644
--- a/Source/JavaScriptCore/wtf/text/StringImpl.h
+++ b/Source/JavaScriptCore/wtf/text/StringImpl.h
@@ -206,40 +206,29 @@ public:
         if (bufferOwnership() == BufferSubstring)
             return m_substringBuffer->cost();
 
-        if (m_refCountAndFlags & s_refCountFlagShouldReportedCost) {
-            m_refCountAndFlags &= ~s_refCountFlagShouldReportedCost;
+        if (m_shouldReportCost) {
+            m_shouldReportCost = false;
             return m_length;
         }
         return 0;
     }
 
-    bool isIdentifier() const { return m_refCountAndFlags & s_refCountFlagIsIdentifier; }
-    void setIsIdentifier(bool isIdentifier)
-    {
-        ASSERT(!isStatic());
-        if (isIdentifier)
-            m_refCountAndFlags |= s_refCountFlagIsIdentifier;
-        else
-            m_refCountAndFlags &= ~s_refCountFlagIsIdentifier;
-    }
+    bool isIdentifier() const { return m_identifier; }
+    void setIsIdentifier(bool isIdentifier) { ASSERT(!isStatic()); m_identifier = isIdentifier; }
 
-    bool hasTerminatingNullCharacter() const { return m_refCountAndFlags & s_refCountFlagHasTerminatingNullCharacter; }
+    bool hasTerminatingNullCharacter() const { return m_hasTerminatingNullCharacter; }
 
-    bool isAtomic() const { return m_refCountAndFlags & s_refCountFlagIsAtomic; }
-    void setIsAtomic(bool isIdentifier)
-    {
-        ASSERT(!isStatic());
-        if (isIdentifier)
-            m_refCountAndFlags |= s_refCountFlagIsAtomic;
-        else
-            m_refCountAndFlags &= ~s_refCountFlagIsAtomic;
-    }
+    bool isAtomic() const { return m_atomic; }
+    void setIsAtomic(bool isAtomic) { ASSERT(!isStatic()); m_atomic = isAtomic; }
+
+    bool isLower() const { return m_lower; }
+    void setIsLower(bool isLower) { m_lower = isLower; }
 
     unsigned hash() const { if (!m_hash) m_hash = StringHasher::computeHash(m_data, m_length); return m_hash; }
     unsigned existingHash() const { ASSERT(m_hash); return m_hash; }
 
-    ALWAYS_INLINE void deref() { m_refCountAndFlags -= s_refCountIncrement; if (!(m_refCountAndFlags & (s_refCountMask | s_refCountFlagStatic))) delete this; }
-    ALWAYS_INLINE bool hasOneRef() const { return (m_refCountAndFlags & (s_refCountMask | s_refCountFlagStatic)) == s_refCountIncrement; }
+    ALWAYS_INLINE void deref() { --m_refCount; if (!m_refCount && !m_static) delete this; }
+    ALWAYS_INLINE bool hasOneRef() const { return (m_refCount == 1 && !m_static); }
 
     static StringImpl* empty();
 
@@ -328,8 +317,8 @@ private:
 
     static PassRefPtr<StringImpl> createStrippingNullCharactersSlowCase(const UChar*, unsigned length);
     
-    BufferOwnership bufferOwnership() const { return static_cast<BufferOwnership>(m_refCountAndFlags & s_refCountMaskBufferOwnership); }
-    bool isStatic() const { return m_refCountAndFlags & s_refCountFlagStatic; }
+    BufferOwnership bufferOwnership() const { return static_cast<BufferOwnership>(m_bufferOwnership); }
+    bool isStatic() const { return m_static; }
     const UChar* m_data;
     union {
         void* m_buffer;
diff --git a/Source/JavaScriptCore/wtf/text/StringImplBase.h b/Source/JavaScriptCore/wtf/text/StringImplBase.h
index 26bc1d9..b6a7210 100644
--- a/Source/JavaScriptCore/wtf/text/StringImplBase.h
+++ b/Source/JavaScriptCore/wtf/text/StringImplBase.h
@@ -33,9 +33,9 @@ namespace WTF {
 class StringImplBase {
     WTF_MAKE_NONCOPYABLE(StringImplBase); WTF_MAKE_FAST_ALLOCATED;
 public:
-    bool isStringImpl() { return (m_refCountAndFlags & s_refCountInvalidForStringImpl) != s_refCountInvalidForStringImpl; }
+    bool isStringImpl() { return !(m_static && m_shouldReportCost); }
     unsigned length() const { return m_length; }
-    void ref() { m_refCountAndFlags += s_refCountIncrement; }
+    void ref() { ++m_refCount; }
 
 protected:
     enum BufferOwnership {
@@ -49,7 +49,14 @@ protected:
     StringImplBase() { }
 
     StringImplBase(unsigned length, BufferOwnership ownership)
-        : m_refCountAndFlags(s_refCountIncrement | s_refCountFlagShouldReportedCost | ownership)
+        : m_lower(false)
+        , m_hasTerminatingNullCharacter(false)
+        , m_atomic(false)
+        , m_static(false)
+        , m_shouldReportCost(true)
+        , m_identifier(false)
+        , m_bufferOwnership(ownership)
+        , m_refCount(1)
         , m_length(length)
     {
         ASSERT(isStringImpl());
@@ -57,7 +64,14 @@ protected:
 
     enum StaticStringConstructType { ConstructStaticString };
     StringImplBase(unsigned length, StaticStringConstructType)
-        : m_refCountAndFlags(s_refCountFlagStatic | s_refCountFlagIsIdentifier | BufferOwned)
+        : m_lower(false)
+        , m_hasTerminatingNullCharacter(false)
+        , m_atomic(false)
+        , m_static(true)
+        , m_shouldReportCost(false)
+        , m_identifier(true)
+        , m_bufferOwnership(BufferOwned)
+        , m_refCount(0)
         , m_length(length)
     {
         ASSERT(isStringImpl());
@@ -67,29 +81,28 @@ protected:
     // and sets the flags into a state marking the object as such.
     enum NonStringImplConstructType { ConstructNonStringImpl };
     StringImplBase(NonStringImplConstructType)
-        : m_refCountAndFlags(s_refCountIncrement | s_refCountInvalidForStringImpl)
+        : m_lower(false)
+        , m_hasTerminatingNullCharacter(false)
+        , m_atomic(false)
+        , m_static(true)
+        , m_shouldReportCost(true)
+        , m_identifier(false)
+        , m_bufferOwnership(0)
+        , m_refCount(1)
         , m_length(0)
     {
         ASSERT(!isStringImpl());
     }
 
-    // The bottom 7 bits hold flags, the top 25 bits hold the ref count.
-    // When dereferencing StringImpls we check for the ref count AND the
-    // static bit both being zero - static strings are never deleted.
-    static const unsigned s_refCountMask = 0xFFFFFF80;
-    static const unsigned s_refCountIncrement = 0x80;
-    static const unsigned s_refCountFlagStatic = 0x40;
-    static const unsigned s_refCountFlagHasTerminatingNullCharacter = 0x20;
-    static const unsigned s_refCountFlagIsAtomic = 0x10;
-    static const unsigned s_refCountFlagShouldReportedCost = 0x8;
-    static const unsigned s_refCountFlagIsIdentifier = 0x4;
-    static const unsigned s_refCountMaskBufferOwnership = 0x3;
-    // An invalid permutation of flags (static & shouldReportedCost - static strings do not
-    // set shouldReportedCost in the constructor, and this bit is only ever cleared, not set).
-    // Used by "ConstructNonStringImpl" constructor, above.
-    static const unsigned s_refCountInvalidForStringImpl = s_refCountFlagStatic | s_refCountFlagShouldReportedCost;
+    bool m_lower : 1;
+    bool m_hasTerminatingNullCharacter : 1;
+    bool m_atomic : 1;
+    bool m_static : 1;
+    bool m_shouldReportCost  : 1;
+    bool m_identifier : 1;
+    unsigned m_bufferOwnership : 2;
+    unsigned m_refCount : 24;
 
-    unsigned m_refCountAndFlags;
     unsigned m_length;
 };
 
diff --git a/Source/JavaScriptCore/wtf/text/WTFString.h b/Source/JavaScriptCore/wtf/text/WTFString.h
index b593d20..6b1bbfb 100644
--- a/Source/JavaScriptCore/wtf/text/WTFString.h
+++ b/Source/JavaScriptCore/wtf/text/WTFString.h
@@ -123,7 +123,7 @@ public:
     bool isNull() const { return !m_impl; }
     bool isEmpty() const { return !m_impl || !m_impl->length(); }
 
-    StringImpl* impl() const { return m_impl.get(); }
+    ALWAYS_INLINE StringImpl* impl() const { return m_impl.get(); }
 
     unsigned length() const
     {
diff --git a/Source/WebCore/Android.mk b/Source/WebCore/Android.mk
index 1f6b838..b1b430c 100644
--- a/Source/WebCore/Android.mk
+++ b/Source/WebCore/Android.mk
@@ -341,6 +341,7 @@ LOCAL_SRC_FILES := $(LOCAL_SRC_FILES) \
 	html/HTMLParserErrorCodes.cpp \
 	html/HTMLTableRowsCollection.cpp \
 	html/HTMLViewSourceDocument.cpp \
+	html/HTMLWbrElement.cpp \
 	html/HiddenInputType.cpp \
 	html/ImageData.cpp \
 	html/ImageDocument.cpp \
diff --git a/Source/WebCore/css/CSSStyleSelector.cpp b/Source/WebCore/css/CSSStyleSelector.cpp
index d81cc9d..f1a7a44 100644
--- a/Source/WebCore/css/CSSStyleSelector.cpp
+++ b/Source/WebCore/css/CSSStyleSelector.cpp
@@ -6,7 +6,7 @@
  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
- * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
+ * Copyright (c) 2011, 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
@@ -7037,7 +7037,7 @@ void CSSStyleSelector::SelectorChecker::allVisitedStateChanged()
 {
     if (m_linksCheckedForVisitedState.isEmpty())
         return;
-    for (Node* node = m_document; node; node = node->traverseNextNode()) {
+    for (Node* node = m_document; node; node = node->traverseNextNodeFastPath()) {
         if (node->isLink())
             node->setNeedsStyleRecalc();
     }
@@ -7047,7 +7047,7 @@ void CSSStyleSelector::SelectorChecker::visitedStateChanged(LinkHash visitedHash
 {
     if (!m_linksCheckedForVisitedState.contains(visitedHash))
         return;
-    for (Node* node = m_document; node; node = node->traverseNextNode()) {
+    for (Node* node = m_document; node; node = node->traverseNextNodeFastPath()) {
         const AtomicString* attr = linkAttribute(node);
         if (attr && visitedLinkHash(m_document->baseURL(), *attr) == visitedHash)
             node->setNeedsStyleRecalc();
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()) {
diff --git a/Source/WebCore/html/CollectionCache.cpp b/Source/WebCore/html/CollectionCache.cpp
index 745cf6e..d831ad1 100644
--- a/Source/WebCore/html/CollectionCache.cpp
+++ b/Source/WebCore/html/CollectionCache.cpp
@@ -83,6 +83,7 @@ void CollectionCache::reset()
     deleteAllValues(nameCache);
     nameCache.clear();
     hasNameCache = false;
+    lastDecendantOfBase = 0;
 }
 
 #if !ASSERT_DISABLED
diff --git a/Source/WebCore/html/CollectionCache.h b/Source/WebCore/html/CollectionCache.h
index d160db2..799263c 100644
--- a/Source/WebCore/html/CollectionCache.h
+++ b/Source/WebCore/html/CollectionCache.h
@@ -28,6 +28,7 @@
 namespace WebCore {
 
 class Element;
+class Node;
 
 struct CollectionCache {
     WTF_MAKE_FAST_ALLOCATED;
@@ -58,6 +59,7 @@ public:
     NodeCacheMap nameCache;
     bool hasLength;
     bool hasNameCache;
+    Node* lastDecendantOfBase;
 
 private:
     static void copyCacheMap(NodeCacheMap&, const NodeCacheMap&);
diff --git a/Source/WebCore/html/HTMLAllCollection.cpp b/Source/WebCore/html/HTMLAllCollection.cpp
index dbfed28..8c92a00 100644
--- a/Source/WebCore/html/HTMLAllCollection.cpp
+++ b/Source/WebCore/html/HTMLAllCollection.cpp
@@ -26,17 +26,18 @@
 #include "config.h"
 #include "HTMLAllCollection.h"
 
+#include "Element.h"
 #include "Node.h"
 
 namespace WebCore {
 
-PassRefPtr<HTMLAllCollection> HTMLAllCollection::create(PassRefPtr<Node> base)
+PassRefPtr<HTMLAllCollection> HTMLAllCollection::create(PassRefPtr<Node> base, CollectionType type)
 {
-    return adoptRef(new HTMLAllCollection(base));
+    return adoptRef(new HTMLAllCollection(base, type));
 }
 
-HTMLAllCollection::HTMLAllCollection(PassRefPtr<Node> base)
-    : HTMLCollection(base, DocAll)
+HTMLAllCollection::HTMLAllCollection(PassRefPtr<Node> base, CollectionType type)
+    : HTMLCollection(base, type)
 {
 }
 
@@ -44,4 +45,38 @@ HTMLAllCollection::~HTMLAllCollection()
 {
 }
 
+Element* HTMLAllCollection::itemAfter(Element* previous) const
+{
+    bool includeChildren = (type() == DocAll);
+    Node* current;
+    Node* root = base();
+    if (!previous)
+        current = root->firstChild();
+    else
+        current = includeChildren ? previous->traverseNextNode(root) : previous->traverseNextSibling(root);
+
+    if (includeChildren) {
+        Node * lastDecendant = info()->lastDecendantOfBase;
+        if (!lastDecendant) {
+            info()->lastDecendantOfBase = root->lastDescendantNode();
+            lastDecendant = info()->lastDecendantOfBase;
+        }
+
+        for (; current; current = current->traverseNextNodeFastPath()) {
+            if (current->isElementNode())
+                return static_cast<Element*>(current);
+            if (current == lastDecendant)
+                break;
+        }
+    } else {
+        for (; current; current = current->traverseNextSibling(root)) {
+            if (current->isElementNode())
+                return static_cast<Element*>(current);
+        }
+    }
+
+    return 0;
+}
+
+
 } // namespace WebCore
diff --git a/Source/WebCore/html/HTMLAllCollection.h b/Source/WebCore/html/HTMLAllCollection.h
index 1dd3ede..443e855 100644
--- a/Source/WebCore/html/HTMLAllCollection.h
+++ b/Source/WebCore/html/HTMLAllCollection.h
@@ -32,11 +32,13 @@ namespace WebCore {
 
 class HTMLAllCollection : public HTMLCollection {
 public:
-    static PassRefPtr<HTMLAllCollection> create(PassRefPtr<Node>);
+    static PassRefPtr<HTMLAllCollection> create(PassRefPtr<Node>, CollectionType = DocAll);
     virtual ~HTMLAllCollection();
 
 private:
-    HTMLAllCollection(PassRefPtr<Node>);
+    HTMLAllCollection(PassRefPtr<Node>, CollectionType = DocAll);
+
+    virtual Element* itemAfter(Element*) const;
 };
 
 } // namespace WebCore
diff --git a/Source/WebCore/html/HTMLAreaElement.cpp b/Source/WebCore/html/HTMLAreaElement.cpp
index 4cb2748..cf37ff2 100644
--- a/Source/WebCore/html/HTMLAreaElement.cpp
+++ b/Source/WebCore/html/HTMLAreaElement.cpp
@@ -45,6 +45,7 @@ inline HTMLAreaElement::HTMLAreaElement(const QualifiedName& tagName, Document*
     , m_shape(Unknown)
 {
     ASSERT(hasTagName(areaTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLAreaElement> HTMLAreaElement::create(const QualifiedName& tagName, Document* document)
diff --git a/Source/WebCore/html/HTMLBRElement.cpp b/Source/WebCore/html/HTMLBRElement.cpp
index e8f4520..da20fbf 100644
--- a/Source/WebCore/html/HTMLBRElement.cpp
+++ b/Source/WebCore/html/HTMLBRElement.cpp
@@ -36,6 +36,7 @@ HTMLBRElement::HTMLBRElement(const QualifiedName& tagName, Document* document)
     : HTMLElement(tagName, document)
 {
     ASSERT(hasTagName(brTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLBRElement> HTMLBRElement::create(Document* document)
diff --git a/Source/WebCore/html/HTMLBaseElement.cpp b/Source/WebCore/html/HTMLBaseElement.cpp
index 0dd16fa..961cc49 100644
--- a/Source/WebCore/html/HTMLBaseElement.cpp
+++ b/Source/WebCore/html/HTMLBaseElement.cpp
@@ -35,6 +35,7 @@ inline HTMLBaseElement::HTMLBaseElement(const QualifiedName& tagName, Document*
     : HTMLElement(tagName, document)
 {
     ASSERT(hasTagName(baseTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLBaseElement> HTMLBaseElement::create(const QualifiedName& tagName, Document* document)
diff --git a/Source/WebCore/html/HTMLCanvasElement.cpp b/Source/WebCore/html/HTMLCanvasElement.cpp
index 81aa1cf..35ce549 100644
--- a/Source/WebCore/html/HTMLCanvasElement.cpp
+++ b/Source/WebCore/html/HTMLCanvasElement.cpp
@@ -2,7 +2,7 @@
  * Copyright (C) 2004, 2006, 2007 Apple Inc. All rights reserved.
  * Copyright (C) 2007 Alp Toker <alp@atoker.com>
  * Copyright (C) 2010 Torch Mobile (Beijing) Co. Ltd. All rights reserved.
- * Copyright (c) 2012, Code Aurora Forum. All rights reserved.
+ * Copyright (c) 2012, The Linux Foundation All rights reserved.
  * Copyright (C) 2011, 2012 Sony Ericsson Mobile Communications AB
  * Copyright (C) 2012 Sony Mobile Communications AB
  *
@@ -321,6 +321,11 @@ void HTMLCanvasElement::paint(GraphicsContext* context, const IntRect& r)
     if (is3D())
         static_cast<WebGLRenderingContext*>(m_context.get())->markLayerComposited();
 #endif
+#if ENABLE(DASHBOARD_SUPPORT)
+    Settings* settings = document()->settings();
+    if (settings && settings->usesDashboardBackwardCompatibilityMode())
+        setIeForbidsInsertHTML();
+#endif
 }
 
 #if ENABLE(WEBGL)
diff --git a/Source/WebCore/html/HTMLCollection.cpp b/Source/WebCore/html/HTMLCollection.cpp
index 2782e50..2c6b135 100644
--- a/Source/WebCore/html/HTMLCollection.cpp
+++ b/Source/WebCore/html/HTMLCollection.cpp
@@ -2,6 +2,7 @@
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 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
@@ -22,6 +23,7 @@
 
 #include "config.h"
 #include "HTMLCollection.h"
+#include "HTMLAllCollection.h"
 
 #include "HTMLDocument.h"
 #include "HTMLElement.h"
@@ -38,24 +40,30 @@ using namespace HTMLNames;
 
 HTMLCollection::HTMLCollection(PassRefPtr<Node> base, CollectionType type)
     : m_idsDone(false)
+    , m_matchTag(htmlTag)
     , m_base(base)
     , m_type(type)
     , m_info(m_base->isDocumentNode() ? static_cast<Document*>(m_base.get())->collectionInfo(type) : 0)
     , m_ownsInfo(false)
 {
+    init();
 }
 
 HTMLCollection::HTMLCollection(PassRefPtr<Node> base, CollectionType type, CollectionCache* info)
     : m_idsDone(false)
+    , m_matchTag(htmlTag)
     , m_base(base)
     , m_type(type)
     , m_info(info)
     , m_ownsInfo(false)
 {
+    init();
 }
 
 PassRefPtr<HTMLCollection> HTMLCollection::create(PassRefPtr<Node> base, CollectionType type)
 {
+    if (type == DocAll || type == NodeChildren)
+        return HTMLAllCollection::create(base, type);
     return adoptRef(new HTMLCollection(base, type));
 }
 
@@ -65,32 +73,9 @@ HTMLCollection::~HTMLCollection()
         delete m_info;
 }
 
-void HTMLCollection::resetCollectionInfo() const
-{
-    uint64_t docversion = static_cast<HTMLDocument*>(m_base->document())->domTreeVersion();
-
-    if (!m_info) {
-        m_info = new CollectionCache;
-        m_ownsInfo = true;
-        m_info->version = docversion;
-        return;
-    }
-
-    if (m_info->version != docversion) {
-        m_info->reset();
-        m_info->version = docversion;
-    }
-}
-
-static Node* nextNodeOrSibling(Node* base, Node* node, bool includeChildren)
-{
-    return includeChildren ? node->traverseNextNode(base) : node->traverseNextSibling(base);
-}
-
-Element* HTMLCollection::itemAfter(Element* previous) const
+void HTMLCollection::init()
 {
-    bool deep = true;
-
+    m_includeChildren = true;
     switch (m_type) {
         case DocAll:
         case DocAnchors:
@@ -112,91 +97,158 @@ Element* HTMLCollection::itemAfter(Element* previous) const
         case TRCells:
         case TSectionRows:
         case TableTBodies:
-            deep = false;
+            m_includeChildren = false;
             break;
     }
 
-    Node* current;
-    if (!previous)
-        current = m_base->firstChild();
-    else
-        current = nextNodeOrSibling(m_base.get(), previous, deep);
+    m_matchType = MatchNone;
+    switch (m_type) {
+        case DocImages:
+            m_matchTag = imgTag;
+            m_matchType = MatchTag;
+            break;
+        case DocScripts:
+            m_matchTag = scriptTag;
+            m_matchType = MatchTag;
+            break;
+        case DocForms:
+            m_matchTag = formTag;
+            m_matchType = MatchTag;
+            break;
+        case TableTBodies:
+            m_matchTag = tbodyTag;
+            m_matchType = MatchTag;
+            break;
+        case TSectionRows:
+            m_matchTag = trTag;
+            m_matchType = MatchTag;
+            break;
+        case SelectOptions:
+            m_matchTag = optionTag;
+            m_matchType = MatchTag;
+            break;
+        case MapAreas:
+            m_matchTag = areaTag;
+            m_matchType = MatchTag;
+            break;
+        case DocEmbeds:
+            m_matchTag = embedTag;
+            m_matchType = MatchTag;
+            break;
+        case DocObjects:
+            m_matchTag = objectTag;
+            m_matchType = MatchTag;
+            break;
+        case TRCells:
+        case DataListOptions:
+        case DocApplets: // all <applet> elements and <object> elements that contain Java Applets
+        case DocLinks: // all <a> and <area> elements with a value for href
+        case DocAnchors: // all <a> elements with a value for name
+            m_matchType = MatchCustom;
+            break;
+        case DocAll:
+        case NodeChildren:
+            m_matchType = MatchAll;
+            break;
+        case DocumentNamedItems:
+        case OtherCollection:
+        case WindowNamedItems:
+            m_matchType = MatchNone;
+            break;
+    }
+}
 
-    for (; current; current = nextNodeOrSibling(m_base.get(), current, deep)) {
-        if (!current->isElementNode())
-            continue;
-        Element* e = static_cast<Element*>(current);
+void HTMLCollection::resetCollectionInfo() const
+{
+    uint64_t docversion = static_cast<HTMLDocument*>(m_base->document())->domTreeVersion();
+
+    if (!m_info) {
+        m_info = new CollectionCache;
+        m_ownsInfo = true;
+        m_info->version = docversion;
+        return;
+    }
+
+    if (m_info->version != docversion) {
+        m_info->reset();
+        m_info->version = docversion;
+    }
+}
+
+static Node* nextNodeOrSibling(Node* base, Node* node, bool includeChildren)
+{
+    return includeChildren ? node->traverseNextNode(base) : node->traverseNextSibling(base);
+}
+
+inline bool HTMLCollection::nodeMatchesShallow(Element* e) const
+{
+    if (m_matchType == MatchTag && e->hasLocalName(m_matchTag))
+        return true;
+    if (m_type == TRCells && (e->hasLocalName(tdTag) || e->hasLocalName(thTag)))
+        return true;
+
+    return false;
+}
+
+inline bool HTMLCollection::nodeMatchesDeep(Element* e) const
+{
+    if (m_matchType == MatchTag && e->hasLocalName(m_matchTag))
+        return true;
+    if (m_matchType == MatchCustom) {
         switch (m_type) {
-            case DocImages:
-                if (e->hasLocalName(imgTag))
-                    return e;
-                break;
-            case DocScripts:
-                if (e->hasLocalName(scriptTag))
-                    return e;
-                break;
-            case DocForms:
-                if (e->hasLocalName(formTag))
-                    return e;
-                break;
-            case TableTBodies:
-                if (e->hasLocalName(tbodyTag))
-                    return e;
-                break;
-            case TRCells:
-                if (e->hasLocalName(tdTag) || e->hasLocalName(thTag))
-                    return e;
-                break;
-            case TSectionRows:
-                if (e->hasLocalName(trTag))
-                    return e;
-                break;
-            case SelectOptions:
-                if (e->hasLocalName(optionTag))
-                    return e;
-                break;
             case DataListOptions:
                 if (e->hasLocalName(optionTag)) {
                     HTMLOptionElement* option = static_cast<HTMLOptionElement*>(e);
                     if (!option->disabled() && !option->value().isEmpty())
-                        return e;
+                        return true;
                 }
                 break;
-            case MapAreas:
-                if (e->hasLocalName(areaTag))
-                    return e;
-                break;
             case DocApplets: // all <applet> elements and <object> elements that contain Java Applets
                 if (e->hasLocalName(appletTag))
-                    return e;
+                    return true;
                 if (e->hasLocalName(objectTag) && static_cast<HTMLObjectElement*>(e)->containsJavaApplet())
-                    return e;
-                break;
-            case DocEmbeds:
-                if (e->hasLocalName(embedTag))
-                    return e;
-                break;
-            case DocObjects:
-                if (e->hasLocalName(objectTag))
-                    return e;
+                    return true;
                 break;
             case DocLinks: // all <a> and <area> elements with a value for href
                 if ((e->hasLocalName(aTag) || e->hasLocalName(areaTag)) && e->fastHasAttribute(hrefAttr))
-                    return e;
+                    return true;
                 break;
             case DocAnchors: // all <a> elements with a value for name
                 if (e->hasLocalName(aTag) && e->fastHasAttribute(nameAttr))
-                    return e;
+                    return true;
                 break;
-            case DocAll:
-            case NodeChildren:
-                return e;
-            case DocumentNamedItems:
-            case OtherCollection:
-            case WindowNamedItems:
-                ASSERT_NOT_REACHED();
+        }
+    }
+
+    return false;
+}
+
+Element* HTMLCollection::itemAfter(Element* previous) const
+{
+    Node* current;
+    Node* base = m_base.get();
+    if (!previous)
+        current = base->firstChild();
+    else
+        current = nextNodeOrSibling(base, previous, m_includeChildren);
+
+    if (m_includeChildren) {
+        if (!m_info->lastDecendantOfBase)
+            m_info->lastDecendantOfBase = base->lastDescendantNode();
+
+        for (; current; current = current->traverseNextNodeFastPath()) {
+            if (current->isElementNode() && HTMLCollection::nodeMatchesDeep(static_cast<Element*>(current)))
+                return static_cast<Element*>(current);
+            if (current == m_info->lastDecendantOfBase)
                 break;
         }
+    } else {
+        for (; current; current = current->traverseNextSibling(base)) {
+            if (!current->isElementNode())
+                continue;
+            if (HTMLCollection::nodeMatchesShallow(static_cast<Element*>(current)))
+                return static_cast<Element*>(current);
+        }
     }
 
     return 0;
diff --git a/Source/WebCore/html/HTMLCollection.h b/Source/WebCore/html/HTMLCollection.h
index 4359724..47449da 100644
--- a/Source/WebCore/html/HTMLCollection.h
+++ b/Source/WebCore/html/HTMLCollection.h
@@ -2,6 +2,7 @@
  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
  *           (C) 1999 Antti Koivisto (koivisto@kde.org)
  * Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 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
@@ -24,6 +25,7 @@
 #define HTMLCollection_h
 
 #include "CollectionType.h"
+#include "QualifiedName.h"
 #include <wtf/RefCounted.h>
 #include <wtf/Forward.h>
 #include <wtf/HashMap.h>
@@ -72,11 +74,19 @@ private:
     virtual Element* itemAfter(Element*) const;
     virtual unsigned calcLength() const;
     virtual void updateNameCache() const;
+    void init();
+    bool nodeMatchesDeep(Element*) const;
+    bool nodeMatchesShallow(Element*) const;
 
     bool checkForNameMatch(Element*, bool checkName, const AtomicString& name) const;
 
+    enum MatchType { MatchNone, MatchTag, MatchCustom, MatchAll };
+    MatchType m_matchType;
+    QualifiedName m_matchTag;
+
     RefPtr<Node> m_base;
     CollectionType m_type;
+    bool m_includeChildren;
 
     mutable CollectionCache* m_info;
     mutable bool m_ownsInfo;
diff --git a/Source/WebCore/html/HTMLDataGridCellElement.cpp b/Source/WebCore/html/HTMLDataGridCellElement.cpp
index 9596d63..a0a5e13 100644
--- a/Source/WebCore/html/HTMLDataGridCellElement.cpp
+++ b/Source/WebCore/html/HTMLDataGridCellElement.cpp
@@ -38,6 +38,7 @@ using namespace HTMLNames;
 inline HTMLDataGridCellElement::HTMLDataGridCellElement(const QualifiedName& name, Document* document)
     : HTMLElement(name, document)
 {
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLDataGridCellElement> HTMLDataGridCellElement::create(const QualifiedName& name, Document* document)
diff --git a/Source/WebCore/html/HTMLDataGridColElement.cpp b/Source/WebCore/html/HTMLDataGridColElement.cpp
index 196c7b6..c546ce9 100644
--- a/Source/WebCore/html/HTMLDataGridColElement.cpp
+++ b/Source/WebCore/html/HTMLDataGridColElement.cpp
@@ -42,6 +42,7 @@ inline HTMLDataGridColElement::HTMLDataGridColElement(const QualifiedName& name,
     : HTMLElement(name, document)
     , m_dataGrid(0)
 {
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLDataGridColElement> HTMLDataGridColElement::create(const QualifiedName& name, Document* document)
diff --git a/Source/WebCore/html/HTMLElement.cpp b/Source/WebCore/html/HTMLElement.cpp
index 0aa9664..f8f2113 100644
--- a/Source/WebCore/html/HTMLElement.cpp
+++ b/Source/WebCore/html/HTMLElement.cpp
@@ -71,49 +71,6 @@ String HTMLElement::nodeName() const
     return Element::nodeName();
 }
 
-bool HTMLElement::ieForbidsInsertHTML() const
-{
-    // FIXME: Supposedly IE disallows settting innerHTML, outerHTML
-    // and createContextualFragment on these tags.  We have no tests to
-    // verify this however, so this list could be totally wrong.
-    // This list was moved from the previous endTagRequirement() implementation.
-    // This is also called from editing and assumed to be the list of tags
-    // for which no end tag should be serialized. It's unclear if the list for
-    // IE compat and the list for serialization sanity are the same.
-    if (hasLocalName(areaTag)
-        || hasLocalName(baseTag)
-        || hasLocalName(basefontTag)
-        || hasLocalName(brTag)
-        || hasLocalName(colTag)
-#if ENABLE(DATAGRID)
-        || hasLocalName(dcellTag)
-        || hasLocalName(dcolTag)
-#endif
-        || hasLocalName(embedTag)
-        || hasLocalName(frameTag)
-        || hasLocalName(hrTag)
-        || hasLocalName(imageTag)
-        || hasLocalName(imgTag)
-        || hasLocalName(inputTag)
-        || hasLocalName(isindexTag)
-        || hasLocalName(linkTag)
-        || hasLocalName(metaTag)
-        || hasLocalName(paramTag)
-        || hasLocalName(sourceTag)
-        || hasLocalName(wbrTag))
-        return true;
-    // FIXME: I'm not sure why dashboard mode would want to change the
-    // serialization of <canvas>, that seems like a bad idea.
-#if ENABLE(DASHBOARD_SUPPORT)
-    if (hasLocalName(canvasTag)) {
-        Settings* settings = document()->settings();
-        if (settings && settings->usesDashboardBackwardCompatibilityMode())
-            return true;
-    }
-#endif
-    return false;
-}
-
 bool HTMLElement::mapToEntry(const QualifiedName& attrName, MappedAttributeEntry& result) const
 {
     if (attrName == alignAttr
@@ -786,8 +743,6 @@ bool HTMLElement::rendererIsNeeded(RenderStyle *style)
 
 RenderObject* HTMLElement::createRenderer(RenderArena* arena, RenderStyle* style)
 {
-    if (hasLocalName(wbrTag))
-        return new (arena) RenderWordBreak(this);
     return RenderObject::createObject(this, style);
 }
 
diff --git a/Source/WebCore/html/HTMLElement.h b/Source/WebCore/html/HTMLElement.h
index 5a5fdfb..6e0b8c5 100644
--- a/Source/WebCore/html/HTMLElement.h
+++ b/Source/WebCore/html/HTMLElement.h
@@ -70,8 +70,6 @@ public:
 
     virtual void accessKeyAction(bool sendToAnyElement);
 
-    bool ieForbidsInsertHTML() const;
-
     virtual bool rendererIsNeeded(RenderStyle*);
     virtual RenderObject* createRenderer(RenderArena*, RenderStyle*);
 
diff --git a/Source/WebCore/html/HTMLEmbedElement.cpp b/Source/WebCore/html/HTMLEmbedElement.cpp
index 851deb8..b6ad707 100644
--- a/Source/WebCore/html/HTMLEmbedElement.cpp
+++ b/Source/WebCore/html/HTMLEmbedElement.cpp
@@ -49,6 +49,7 @@ inline HTMLEmbedElement::HTMLEmbedElement(const QualifiedName& tagName, Document
     : HTMLPlugInImageElement(tagName, document, createdByParser, ShouldPreferPlugInsForImages)
 {
     ASSERT(hasTagName(embedTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLEmbedElement> HTMLEmbedElement::create(const QualifiedName& tagName, Document* document, bool createdByParser)
diff --git a/Source/WebCore/html/HTMLFrameElement.cpp b/Source/WebCore/html/HTMLFrameElement.cpp
index 71c8f3f..f5297da 100644
--- a/Source/WebCore/html/HTMLFrameElement.cpp
+++ b/Source/WebCore/html/HTMLFrameElement.cpp
@@ -41,6 +41,7 @@ inline HTMLFrameElement::HTMLFrameElement(const QualifiedName& tagName, Document
     , m_noResize(false)
 {
     ASSERT(hasTagName(frameTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLFrameElement> HTMLFrameElement::create(const QualifiedName& tagName, Document* document)
diff --git a/Source/WebCore/html/HTMLHRElement.cpp b/Source/WebCore/html/HTMLHRElement.cpp
index 44aa052..4de829c 100644
--- a/Source/WebCore/html/HTMLHRElement.cpp
+++ b/Source/WebCore/html/HTMLHRElement.cpp
@@ -36,6 +36,7 @@ HTMLHRElement::HTMLHRElement(const QualifiedName& tagName, Document* document)
     : HTMLElement(tagName, document)
 {
     ASSERT(hasTagName(hrTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLHRElement> HTMLHRElement::create(Document* document)
diff --git a/Source/WebCore/html/HTMLImageElement.cpp b/Source/WebCore/html/HTMLImageElement.cpp
index d66075e..836388f 100644
--- a/Source/WebCore/html/HTMLImageElement.cpp
+++ b/Source/WebCore/html/HTMLImageElement.cpp
@@ -51,6 +51,7 @@ HTMLImageElement::HTMLImageElement(const QualifiedName& tagName, Document* docum
     ASSERT(hasTagName(imgTag));
     if (form)
         form->registerImgElement(this);
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLImageElement> HTMLImageElement::create(Document* document)
diff --git a/Source/WebCore/html/HTMLInputElement.cpp b/Source/WebCore/html/HTMLInputElement.cpp
index 27b29a8..626fdc0 100644
--- a/Source/WebCore/html/HTMLInputElement.cpp
+++ b/Source/WebCore/html/HTMLInputElement.cpp
@@ -85,6 +85,7 @@ HTMLInputElement::HTMLInputElement(const QualifiedName& tagName, Document* docum
     , m_inputType(InputType::createText(this))
 {
     ASSERT(hasTagName(inputTag) || hasTagName(isindexTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLInputElement> HTMLInputElement::create(const QualifiedName& tagName, Document* document, HTMLFormElement* form, bool createdByParser)
diff --git a/Source/WebCore/html/HTMLLinkElement.cpp b/Source/WebCore/html/HTMLLinkElement.cpp
index 4e1e843..223fcf6 100644
--- a/Source/WebCore/html/HTMLLinkElement.cpp
+++ b/Source/WebCore/html/HTMLLinkElement.cpp
@@ -61,6 +61,7 @@ inline HTMLLinkElement::HTMLLinkElement(const QualifiedName& tagName, Document*
     , m_pendingSheetType(None)
 {
     ASSERT(hasTagName(linkTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLLinkElement> HTMLLinkElement::create(const QualifiedName& tagName, Document* document, bool createdByParser)
diff --git a/Source/WebCore/html/HTMLMetaElement.cpp b/Source/WebCore/html/HTMLMetaElement.cpp
index 4f65065..3c3db44 100644
--- a/Source/WebCore/html/HTMLMetaElement.cpp
+++ b/Source/WebCore/html/HTMLMetaElement.cpp
@@ -40,6 +40,7 @@ inline HTMLMetaElement::HTMLMetaElement(const QualifiedName& tagName, Document*
     : HTMLElement(tagName, document)
 {
     ASSERT(hasTagName(metaTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLMetaElement> HTMLMetaElement::create(const QualifiedName& tagName, Document* document)
diff --git a/Source/WebCore/html/HTMLParamElement.cpp b/Source/WebCore/html/HTMLParamElement.cpp
index 45a74b2..830c1ad 100644
--- a/Source/WebCore/html/HTMLParamElement.cpp
+++ b/Source/WebCore/html/HTMLParamElement.cpp
@@ -35,6 +35,7 @@ inline HTMLParamElement::HTMLParamElement(const QualifiedName& tagName, Document
     : HTMLElement(tagName, document)
 {
     ASSERT(hasTagName(paramTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLParamElement> HTMLParamElement::create(const QualifiedName& tagName, Document* document)
diff --git a/Source/WebCore/html/HTMLSourceElement.cpp b/Source/WebCore/html/HTMLSourceElement.cpp
index 59b3882..ca683c2 100644
--- a/Source/WebCore/html/HTMLSourceElement.cpp
+++ b/Source/WebCore/html/HTMLSourceElement.cpp
@@ -47,6 +47,7 @@ inline HTMLSourceElement::HTMLSourceElement(const QualifiedName& tagName, Docume
 {
     LOG(Media, "HTMLSourceElement::HTMLSourceElement - %p", this);
     ASSERT(hasTagName(sourceTag));
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLSourceElement> HTMLSourceElement::create(const QualifiedName& tagName, Document* document)
diff --git a/Source/WebCore/html/HTMLTableColElement.cpp b/Source/WebCore/html/HTMLTableColElement.cpp
index 96af708..f7b8f2b 100644
--- a/Source/WebCore/html/HTMLTableColElement.cpp
+++ b/Source/WebCore/html/HTMLTableColElement.cpp
@@ -40,6 +40,7 @@ inline HTMLTableColElement::HTMLTableColElement(const QualifiedName& tagName, Do
     : HTMLTablePartElement(tagName, document)
     , m_span(1)
 {
+    setIeForbidsInsertHTML();
 }
 
 PassRefPtr<HTMLTableColElement> HTMLTableColElement::create(const QualifiedName& tagName, Document* document)
diff --git a/Source/WebCore/html/HTMLTagNames.in b/Source/WebCore/html/HTMLTagNames.in
index 0bf4ff9..0de0632 100644
--- a/Source/WebCore/html/HTMLTagNames.in
+++ b/Source/WebCore/html/HTMLTagNames.in
@@ -132,7 +132,7 @@ u interfaceName=HTMLElement
 ul interfaceName=HTMLUListElement
 var interfaceName=HTMLElement
 video wrapperOnlyIfMediaIsAvailable, conditional=VIDEO
-wbr interfaceName=HTMLElement
+wbr interfaceName=HTMLWbrElement, JSInterfaceName=HTMLElement
 xmp interfaceName=HTMLPreElement
 
 #if ENABLE_XHTMLMP
diff --git a/Source/WebCore/html/HTMLWbrElement.cpp b/Source/WebCore/html/HTMLWbrElement.cpp
new file mode 100644
index 0000000..4de25ac
--- /dev/null
+++ b/Source/WebCore/html/HTMLWbrElement.cpp
@@ -0,0 +1,62 @@
+/*
+* 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 are
+* met:
+*     * Redistributions of source code must retain the above copyright
+*       notice, this list of conditions and the following disclaimer.
+*     * Redistributions in binary form must reproduce the above
+*       copyright notice, this list of conditions and the following
+*       disclaimer in the documentation and/or other materials provided
+*       with the distribution.
+*     * Neither the name of The Linux Foundation nor the names of its
+*       contributors may be used to endorse or promote products derived
+*       from this software without specific prior written permission.
+*
+* THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
+* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
+* ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
+* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+* IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include "config.h"
+#include "HTMLWbrElement.h"
+
+#include "HTMLNames.h"
+#include "RenderWordBreak.h"
+
+namespace WebCore {
+
+using namespace HTMLNames;
+
+HTMLWbrElement::HTMLWbrElement(const QualifiedName& tagName, Document* document)
+    : HTMLElement(tagName, document)
+{
+    ASSERT(hasTagName(wbrTag));
+    setIeForbidsInsertHTML();
+}
+
+PassRefPtr<HTMLWbrElement> HTMLWbrElement::create(Document* document)
+{
+    return adoptRef(new HTMLWbrElement(wbrTag, document));
+}
+
+PassRefPtr<HTMLWbrElement> HTMLWbrElement::create(const QualifiedName& tagName, Document* document)
+{
+    return adoptRef(new HTMLWbrElement(tagName, document));
+}
+
+RenderObject* HTMLWbrElement::createRenderer(RenderArena* arena, RenderStyle* style)
+{
+    return new (arena) RenderWordBreak(this);
+}
+
+}
diff --git a/Source/WebCore/html/HTMLWbrElement.h b/Source/WebCore/html/HTMLWbrElement.h
new file mode 100644
index 0000000..fa6856e
--- /dev/null
+++ b/Source/WebCore/html/HTMLWbrElement.h
@@ -0,0 +1,50 @@
+/*
+* 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 are
+* met:
+*     * Redistributions of source code must retain the above copyright
+*       notice, this list of conditions and the following disclaimer.
+*     * Redistributions in binary form must reproduce the above
+*       copyright notice, this list of conditions and the following
+*       disclaimer in the documentation and/or other materials provided
+*       with the distribution.
+*     * Neither the name of The Linux Foundation nor the names of its
+*       contributors may be used to endorse or promote products derived
+*       from this software without specific prior written permission.
+*
+* THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
+* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
+* ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
+* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
+* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
+* IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef HTMLWbrElement_h
+#define HTMLWbrElement_h
+
+#include "HTMLElement.h"
+
+namespace WebCore {
+
+class HTMLWbrElement : public HTMLElement {
+public:
+    static PassRefPtr<HTMLWbrElement> create(Document*);
+    static PassRefPtr<HTMLWbrElement> create(const QualifiedName&, Document*);
+
+private:
+    HTMLWbrElement(const QualifiedName&, Document*);
+
+    virtual RenderObject* createRenderer(RenderArena*, RenderStyle*);
+};
+
+} // namespace
+
+#endif
diff --git a/Source/WebCore/rendering/svg/SVGShadowTreeElements.cpp b/Source/WebCore/rendering/svg/SVGShadowTreeElements.cpp
index ac4a63e..a5cf4ca 100644
--- a/Source/WebCore/rendering/svg/SVGShadowTreeElements.cpp
+++ b/Source/WebCore/rendering/svg/SVGShadowTreeElements.cpp
@@ -32,8 +32,8 @@ namespace WebCore {
 
 // SVGShadowTreeContainerElement
 
-SVGShadowTreeContainerElement::SVGShadowTreeContainerElement(Document* document)
-    : SVGGElement(SVGNames::gTag, document)
+SVGShadowTreeContainerElement::SVGShadowTreeContainerElement(Document* document, ConstructionType constructionType)
+    : SVGGElement(SVGNames::gTag, document, constructionType)
 {
 }
 
@@ -54,7 +54,7 @@ PassRefPtr<Element> SVGShadowTreeContainerElement::cloneElementWithoutAttributes
 // SVGShadowTreeRootElement
 
 inline SVGShadowTreeRootElement::SVGShadowTreeRootElement(Document* document, SVGUseElement* host)
-    : SVGShadowTreeContainerElement(document)
+    : SVGShadowTreeContainerElement(document, CreateSVGShadowRoot)
 {
     setParent(host);
     setInDocument();
diff --git a/Source/WebCore/rendering/svg/SVGShadowTreeElements.h b/Source/WebCore/rendering/svg/SVGShadowTreeElements.h
index 8cbd4b7..9ccda36 100644
--- a/Source/WebCore/rendering/svg/SVGShadowTreeElements.h
+++ b/Source/WebCore/rendering/svg/SVGShadowTreeElements.h
@@ -41,7 +41,7 @@ public:
     }
 
 protected:
-    SVGShadowTreeContainerElement(Document*);
+    SVGShadowTreeContainerElement(Document*, ConstructionType = CreateSVGElement);
 
 private:
     virtual PassRefPtr<Element> cloneElementWithoutAttributesAndChildren() const;
@@ -58,8 +58,6 @@ public:
     void attachElement(PassRefPtr<RenderStyle>, RenderArena*);
     void clearSVGShadowHost();
 
-    virtual bool isSVGShadowRoot() const { return true; }
-
 private:
     SVGShadowTreeRootElement(Document*, SVGUseElement* host);
 };
diff --git a/Source/WebCore/svg/SVGElement.cpp b/Source/WebCore/svg/SVGElement.cpp
index 044f439..9ddc383 100644
--- a/Source/WebCore/svg/SVGElement.cpp
+++ b/Source/WebCore/svg/SVGElement.cpp
@@ -54,8 +54,8 @@ namespace WebCore {
 
 using namespace HTMLNames;
 
-SVGElement::SVGElement(const QualifiedName& tagName, Document* document)
-    : StyledElement(tagName, document, CreateSVGElement)
+SVGElement::SVGElement(const QualifiedName& tagName, Document* document, ConstructionType constructionType)
+    : StyledElement(tagName, document, constructionType)
 {
 }
 
diff --git a/Source/WebCore/svg/SVGElement.h b/Source/WebCore/svg/SVGElement.h
index 380fa0e..1bb10d9 100644
--- a/Source/WebCore/svg/SVGElement.h
+++ b/Source/WebCore/svg/SVGElement.h
@@ -110,7 +110,7 @@ public:
     virtual void updateAnimatedSVGAttribute(const QualifiedName&) const;
 
 protected:
-    SVGElement(const QualifiedName&, Document*);
+    SVGElement(const QualifiedName&, Document*, ConstructionType = CreateSVGElement);
 
     virtual void parseMappedAttribute(Attribute*);
 
diff --git a/Source/WebCore/svg/SVGGElement.cpp b/Source/WebCore/svg/SVGGElement.cpp
index f7a48ec..1be08bf 100644
--- a/Source/WebCore/svg/SVGGElement.cpp
+++ b/Source/WebCore/svg/SVGGElement.cpp
@@ -33,8 +33,8 @@ namespace WebCore {
 // Animated property declarations
 DEFINE_ANIMATED_BOOLEAN(SVGGElement, SVGNames::externalResourcesRequiredAttr, ExternalResourcesRequired, externalResourcesRequired)
 
-SVGGElement::SVGGElement(const QualifiedName& tagName, Document* document)
-    : SVGStyledTransformableElement(tagName, document)
+SVGGElement::SVGGElement(const QualifiedName& tagName, Document* document, ConstructionType constructionType)
+    : SVGStyledTransformableElement(tagName, document, constructionType)
 {
 }
 
diff --git a/Source/WebCore/svg/SVGGElement.h b/Source/WebCore/svg/SVGGElement.h
index c306f4a..8126957 100644
--- a/Source/WebCore/svg/SVGGElement.h
+++ b/Source/WebCore/svg/SVGGElement.h
@@ -40,7 +40,7 @@ public:
     virtual bool isShadowTreeContainerElement() const { return false; }
 
 protected:
-    SVGGElement(const QualifiedName&, Document*);
+    SVGGElement(const QualifiedName&, Document*, ConstructionType = CreateSVGElement);
 
     virtual RenderObject* createRenderer(RenderArena*, RenderStyle*);
 
diff --git a/Source/WebCore/svg/SVGStyledElement.cpp b/Source/WebCore/svg/SVGStyledElement.cpp
index 79e1633..5a2fe5d 100644
--- a/Source/WebCore/svg/SVGStyledElement.cpp
+++ b/Source/WebCore/svg/SVGStyledElement.cpp
@@ -59,8 +59,8 @@ void mapAttributeToCSSProperty(HashMap<AtomicStringImpl*, int>* propertyNameToId
     propertyNameToIdMap->set(attrName.localName().impl(), propertyId);
 }
 
-SVGStyledElement::SVGStyledElement(const QualifiedName& tagName, Document* document)
-    : SVGElement(tagName, document)
+SVGStyledElement::SVGStyledElement(const QualifiedName& tagName, Document* document, ConstructionType constructionType)
+    : SVGElement(tagName, document, constructionType)
 {
 }
 
diff --git a/Source/WebCore/svg/SVGStyledElement.h b/Source/WebCore/svg/SVGStyledElement.h
index b6c0b96..1de3ac6 100644
--- a/Source/WebCore/svg/SVGStyledElement.h
+++ b/Source/WebCore/svg/SVGStyledElement.h
@@ -60,7 +60,7 @@ public:
     virtual CSSStyleDeclaration* style() { return StyledElement::style(); }
 
 protected: 
-    SVGStyledElement(const QualifiedName&, Document*);
+    SVGStyledElement(const QualifiedName&, Document*, ConstructionType = CreateSVGElement);
 
     virtual bool rendererIsNeeded(RenderStyle*);
 
diff --git a/Source/WebCore/svg/SVGStyledLocatableElement.cpp b/Source/WebCore/svg/SVGStyledLocatableElement.cpp
index f29121b..5ccfb4b 100644
--- a/Source/WebCore/svg/SVGStyledLocatableElement.cpp
+++ b/Source/WebCore/svg/SVGStyledLocatableElement.cpp
@@ -29,8 +29,8 @@
 
 namespace WebCore {
 
-SVGStyledLocatableElement::SVGStyledLocatableElement(const QualifiedName& tagName, Document* document)
-    : SVGStyledElement(tagName, document)
+SVGStyledLocatableElement::SVGStyledLocatableElement(const QualifiedName& tagName, Document* document, ConstructionType constructionType)
+    : SVGStyledElement(tagName, document, constructionType)
 {
 }
 
diff --git a/Source/WebCore/svg/SVGStyledLocatableElement.h b/Source/WebCore/svg/SVGStyledLocatableElement.h
index 114ae83..3a9baf7 100644
--- a/Source/WebCore/svg/SVGStyledLocatableElement.h
+++ b/Source/WebCore/svg/SVGStyledLocatableElement.h
@@ -42,7 +42,7 @@ public:
     virtual AffineTransform localCoordinateSpaceTransform(SVGLocatable::CTMScope mode) const { return SVGLocatable::localCoordinateSpaceTransform(mode); }
 
 protected:
-    SVGStyledLocatableElement(const QualifiedName&, Document*);
+    SVGStyledLocatableElement(const QualifiedName&, Document*, ConstructionType = CreateSVGElement);
 
 private:
     virtual bool isStyledLocatable() const { return true; }
diff --git a/Source/WebCore/svg/SVGStyledTransformableElement.cpp b/Source/WebCore/svg/SVGStyledTransformableElement.cpp
index 1e32f9a..bdb3fab 100644
--- a/Source/WebCore/svg/SVGStyledTransformableElement.cpp
+++ b/Source/WebCore/svg/SVGStyledTransformableElement.cpp
@@ -34,8 +34,8 @@ namespace WebCore {
 // Animated property definitions
 DEFINE_ANIMATED_TRANSFORM_LIST(SVGStyledTransformableElement, SVGNames::transformAttr, Transform, transform)
 
-SVGStyledTransformableElement::SVGStyledTransformableElement(const QualifiedName& tagName, Document* document)
-    : SVGStyledLocatableElement(tagName, document)
+SVGStyledTransformableElement::SVGStyledTransformableElement(const QualifiedName& tagName, Document* document, ConstructionType constructionType)
+    : SVGStyledLocatableElement(tagName, document, constructionType)
 {
 }
 
diff --git a/Source/WebCore/svg/SVGStyledTransformableElement.h b/Source/WebCore/svg/SVGStyledTransformableElement.h
index 9d6834a..e16dbc6 100644
--- a/Source/WebCore/svg/SVGStyledTransformableElement.h
+++ b/Source/WebCore/svg/SVGStyledTransformableElement.h
@@ -55,7 +55,7 @@ public:
     virtual RenderObject* createRenderer(RenderArena*, RenderStyle*);
 
 protected:
-    SVGStyledTransformableElement(const QualifiedName&, Document*);
+    SVGStyledTransformableElement(const QualifiedName&, Document*, ConstructionType = CreateSVGElement);
 
     virtual void parseMappedAttribute(Attribute*);
     virtual void svgAttributeChanged(const QualifiedName&);
diff --git a/Source/WebKit/android/jni/WebViewCore.cpp b/Source/WebKit/android/jni/WebViewCore.cpp
index 5f3390b..23bd873 100644
--- a/Source/WebKit/android/jni/WebViewCore.cpp
+++ b/Source/WebKit/android/jni/WebViewCore.cpp
@@ -1,6 +1,6 @@
 /*
  * Copyright 2006, The Android Open Source Project
- * Copyright (C) 2011, 2012 Code Aurora Forum. All rights reserved.
+ * Copyright (C) 2011, 2012 The Linux Foundation All rights reserved.
  * Copyright (C) 2012 Sony Ericsson Mobile Communications AB.
  * Copyright (C) 2012 Sony Mobile Communications AB
  *
@@ -2576,7 +2576,7 @@ Node* WebViewCore::getNextAnchorNode(Node* anchorNode, bool ignoreFirstNode, int
                 || isContentInputElement(currentNode))
             return currentNode;
         if (direction == DIRECTION_FORWARD)
-            currentNode = currentNode->traverseNextNode();
+            currentNode = currentNode->traverseNextNodeFastPath();
         else
             currentNode = currentNode->traversePreviousNodePostOrder(body);
     }
@@ -2698,7 +2698,7 @@ Node* WebViewCore::getIntermediaryInputElement(Node* fromNode, Node* toNode, int
         while (currentNode && currentNode != toNode) {
             if (isContentInputElement(currentNode))
                 return currentNode;
-            currentNode = currentNode->traverseNextNode();
+            currentNode = currentNode->traverseNextNodeFastPath();
         }
     } else {
         Node* currentNode = fromNode->traversePreviousNode();