--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/WebCore/html/HTMLElementStack.cpp	Fri Sep 17 09:02:29 2010 +0300
@@ -0,0 +1,494 @@
+/*
+ * Copyright (C) 2010 Google, Inc. All Rights Reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. 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.
+ *
+ * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL GOOGLE INC. 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 "HTMLElementStack.h"
+
+#include "Element.h"
+#include "HTMLNames.h"
+#include <wtf/PassOwnPtr.h>
+
+#if ENABLE(SVG)
+#include "SVGNames.h"
+#endif
+
+namespace WebCore {
+
+using namespace HTMLNames;
+
+namespace {
+
+inline bool isScopeMarker(Element* element)
+{
+    return element->hasTagName(appletTag)
+        || element->hasTagName(captionTag)
+#if ENABLE(SVG_FOREIGN_OBJECT)
+        || element->hasTagName(SVGNames::foreignObjectTag)
+#endif
+        || element->hasTagName(htmlTag)
+        || element->hasTagName(marqueeTag)
+        || element->hasTagName(objectTag)
+        || element->hasTagName(tableTag)
+        || element->hasTagName(tdTag)
+        || element->hasTagName(thTag);
+}
+
+inline bool isListItemScopeMarker(Element* element)
+{
+    return isScopeMarker(element)
+        || element->hasTagName(olTag)
+        || element->hasTagName(ulTag);
+}
+
+inline bool isTableScopeMarker(Element* element)
+{
+    return element->hasTagName(tableTag)
+        || element->hasTagName(htmlTag);
+}
+
+inline bool isTableBodyScopeMarker(Element* element)
+{
+    return element->hasTagName(tbodyTag)
+        || element->hasTagName(tfootTag)
+        || element->hasTagName(theadTag)
+        || element->hasTagName(htmlTag);
+}
+
+inline bool isTableRowScopeMarker(Element* element)
+{
+    return element->hasTagName(trTag)
+        || element->hasTagName(htmlTag);
+}
+
+inline bool isButtonScopeMarker(Element* element)
+{
+    return isScopeMarker(element)
+        || element->hasTagName(buttonTag);
+}
+
+}
+
+HTMLElementStack::ElementRecord::ElementRecord(PassRefPtr<Element> element, PassOwnPtr<ElementRecord> next)
+    : m_element(element)
+    , m_next(next)
+{
+    ASSERT(m_element);
+}
+
+HTMLElementStack::ElementRecord::~ElementRecord()
+{
+}
+
+void HTMLElementStack::ElementRecord::replaceElement(PassRefPtr<Element> element)
+{
+    ASSERT(element);
+    // FIXME: Should this call finishParsingChildren?
+    m_element = element;
+}
+
+bool HTMLElementStack::ElementRecord::isAbove(ElementRecord* other) const
+{
+    for (ElementRecord* below = next(); below; below = below->next()) {
+        if (below == other)
+            return true;
+    }
+    return false;
+}
+
+HTMLElementStack::HTMLElementStack()
+    : m_htmlElement(0)
+    , m_headElement(0)
+    , m_bodyElement(0)
+{
+}
+
+HTMLElementStack::~HTMLElementStack()
+{
+}
+
+void HTMLElementStack::popHTMLHeadElement()
+{
+    ASSERT(top() == m_headElement);
+    m_headElement = 0;
+    popCommon();
+}
+
+void HTMLElementStack::popHTMLBodyElement()
+{
+    ASSERT(top() == m_bodyElement);
+    m_bodyElement = 0;
+    popCommon();
+}
+
+void HTMLElementStack::popAll()
+{
+    m_htmlElement = 0;
+    m_headElement = 0;
+    m_bodyElement = 0;
+    while (m_top) {
+        top()->finishParsingChildren();
+        m_top = m_top->releaseNext();
+    }
+}
+
+void HTMLElementStack::pop()
+{
+    ASSERT(!top()->hasTagName(HTMLNames::headTag));
+    popCommon();
+}
+
+void HTMLElementStack::popUntilElementWithNamespace(const AtomicString& namespaceURI)
+{
+    while (top()->namespaceURI() != namespaceURI)
+        pop();
+}
+
+void HTMLElementStack::popUntil(const AtomicString& tagName)
+{
+    while (!top()->hasLocalName(tagName)) {
+        // pop() will ASSERT at <body> if callers fail to check that there is an
+        // element with localName |tagName| on the stack of open elements.
+        pop();
+    }
+}
+
+void HTMLElementStack::popUntilPopped(const AtomicString& tagName)
+{
+    popUntil(tagName);
+    pop();
+}
+
+void HTMLElementStack::popUntil(Element* element)
+{
+    while (top() != element)
+        pop();
+}
+
+void HTMLElementStack::popUntilPopped(Element* element)
+{
+    popUntil(element);
+    pop();
+}
+
+void HTMLElementStack::popUntilTableScopeMarker()
+{
+    // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-context
+    while (!isTableScopeMarker(top()))
+        pop();
+}
+
+void HTMLElementStack::popUntilTableBodyScopeMarker()
+{
+    // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-body-context
+    while (!isTableBodyScopeMarker(top()))
+        pop();
+}
+
+void HTMLElementStack::popUntilTableRowScopeMarker()
+{
+    // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#clear-the-stack-back-to-a-table-row-context
+    while (!isTableRowScopeMarker(top()))
+        pop();
+}
+
+void HTMLElementStack::pushHTMLHtmlElement(PassRefPtr<Element> element)
+{
+    ASSERT(!m_top); // <html> should always be the bottom of the stack.
+    ASSERT(element->hasTagName(HTMLNames::htmlTag));
+    ASSERT(!m_htmlElement);
+    m_htmlElement = element.get();
+    pushCommon(element);
+}
+
+void HTMLElementStack::pushHTMLHeadElement(PassRefPtr<Element> element)
+{
+    ASSERT(element->hasTagName(HTMLNames::headTag));
+    ASSERT(!m_headElement);
+    m_headElement = element.get();
+    pushCommon(element);
+}
+
+void HTMLElementStack::pushHTMLBodyElement(PassRefPtr<Element> element)
+{
+    ASSERT(element->hasTagName(HTMLNames::bodyTag));
+    ASSERT(!m_bodyElement);
+    m_bodyElement = element.get();
+    pushCommon(element);
+}
+
+void HTMLElementStack::push(PassRefPtr<Element> element)
+{
+    ASSERT(!element->hasTagName(HTMLNames::htmlTag));
+    ASSERT(!element->hasTagName(HTMLNames::headTag));
+    ASSERT(!element->hasTagName(HTMLNames::bodyTag));
+    ASSERT(m_htmlElement);
+    pushCommon(element);
+}
+
+void HTMLElementStack::insertAbove(PassRefPtr<Element> element, ElementRecord* recordBelow)
+{
+    ASSERT(element);
+    ASSERT(recordBelow);
+    ASSERT(m_top);
+    ASSERT(!element->hasTagName(HTMLNames::htmlTag));
+    ASSERT(!element->hasTagName(HTMLNames::headTag));
+    ASSERT(!element->hasTagName(HTMLNames::bodyTag));
+    ASSERT(m_htmlElement);
+    if (recordBelow == m_top) {
+        push(element);
+        return;
+    }
+
+    for (ElementRecord* recordAbove = m_top.get(); recordAbove; recordAbove = recordAbove->next()) {
+        if (recordAbove->next() != recordBelow)
+            continue;
+
+        recordAbove->setNext(new ElementRecord(element, recordAbove->releaseNext()));
+        recordAbove->next()->element()->beginParsingChildren();
+        return;
+    }
+    ASSERT_NOT_REACHED();
+}
+
+HTMLElementStack::ElementRecord* HTMLElementStack::topRecord() const
+{
+    ASSERT(m_top);
+    return m_top.get();
+}
+
+Element* HTMLElementStack::top() const
+{
+    ASSERT(m_top->element());
+    return m_top->element();
+}
+
+Element* HTMLElementStack::oneBelowTop() const
+{
+    // We should never be calling this if it could be 0.
+    ASSERT(m_top);
+    ASSERT(m_top->next());
+    return m_top->next()->element();
+}
+
+Element* HTMLElementStack::bottom() const
+{
+    return htmlElement();
+}
+
+void HTMLElementStack::removeHTMLHeadElement(Element* element)
+{
+    ASSERT(m_headElement == element);
+    if (m_top->element() == element) {
+        popHTMLHeadElement();
+        return;
+    }
+    m_headElement = 0;
+    removeNonTopCommon(element);
+}
+
+void HTMLElementStack::remove(Element* element)
+{
+    ASSERT(!element->hasTagName(HTMLNames::headTag));
+    if (m_top->element() == element) {
+        pop();
+        return;
+    }
+    removeNonTopCommon(element);
+}
+
+HTMLElementStack::ElementRecord* HTMLElementStack::find(Element* element) const
+{
+    for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
+        if (pos->element() == element)
+            return pos;
+    }
+    return 0;
+}
+
+HTMLElementStack::ElementRecord* HTMLElementStack::topmost(const AtomicString& tagName) const
+{
+    for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
+        if (pos->element()->hasLocalName(tagName))
+            return pos;
+    }
+    return 0;
+}
+
+bool HTMLElementStack::contains(Element* element) const
+{
+    return !!find(element);
+}
+
+bool HTMLElementStack::contains(const AtomicString& tagName) const
+{
+    return !!topmost(tagName);
+}
+
+template <bool isMarker(Element*)>
+bool inScopeCommon(HTMLElementStack::ElementRecord* top, const AtomicString& targetTag)
+{
+    for (HTMLElementStack::ElementRecord* pos = top; pos; pos = pos->next()) {
+        Element* element = pos->element();
+        if (element->hasLocalName(targetTag))
+            return true;
+        if (isMarker(element))
+            return false;
+    }
+    ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
+    return false;
+}
+
+bool HTMLElementStack::hasOnlyHTMLElementsInScope() const
+{
+    for (ElementRecord* record = m_top.get(); record; record = record->next()) {
+        Element* element = record->element();
+        if (element->namespaceURI() != xhtmlNamespaceURI)
+            return false;
+        if (isScopeMarker(element))
+            return true;
+    }
+    ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
+    return true;
+}
+
+bool HTMLElementStack::inScope(Element* targetElement) const
+{
+    for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
+        Element* element = pos->element();
+        if (element == targetElement)
+            return true;
+        if (isScopeMarker(element))
+            return false;
+    }
+    ASSERT_NOT_REACHED(); // <html> is always on the stack and is a scope marker.
+    return false;
+}
+
+bool HTMLElementStack::inScope(const AtomicString& targetTag) const
+{
+    return inScopeCommon<isScopeMarker>(m_top.get(), targetTag);
+}
+
+bool HTMLElementStack::inScope(const QualifiedName& tagName) const
+{
+    // FIXME: Is localName() right for non-html elements?
+    return inScope(tagName.localName());
+}
+
+bool HTMLElementStack::inListItemScope(const AtomicString& targetTag) const
+{
+    return inScopeCommon<isListItemScopeMarker>(m_top.get(), targetTag);
+}
+
+bool HTMLElementStack::inListItemScope(const QualifiedName& tagName) const
+{
+    // FIXME: Is localName() right for non-html elements?
+    return inListItemScope(tagName.localName());
+}
+
+bool HTMLElementStack::inTableScope(const AtomicString& targetTag) const
+{
+    return inScopeCommon<isTableScopeMarker>(m_top.get(), targetTag);
+}
+
+bool HTMLElementStack::inTableScope(const QualifiedName& tagName) const
+{
+    // FIXME: Is localName() right for non-html elements?
+    return inTableScope(tagName.localName());
+}
+
+bool HTMLElementStack::inButtonScope(const AtomicString& targetTag) const
+{
+    return inScopeCommon<isButtonScopeMarker>(m_top.get(), targetTag);
+}
+
+bool HTMLElementStack::inButtonScope(const QualifiedName& tagName) const
+{
+    // FIXME: Is localName() right for non-html elements?
+    return inButtonScope(tagName.localName());
+}
+
+Element* HTMLElementStack::htmlElement() const
+{
+    ASSERT(m_htmlElement);
+    return m_htmlElement;
+}
+
+Element* HTMLElementStack::headElement() const
+{
+    ASSERT(m_headElement);
+    return m_headElement;
+}
+
+Element* HTMLElementStack::bodyElement() const
+{
+    ASSERT(m_bodyElement);
+    return m_bodyElement;
+}
+
+void HTMLElementStack::pushCommon(PassRefPtr<Element> element)
+{
+    ASSERT(m_htmlElement);
+    m_top.set(new ElementRecord(element, m_top.release()));
+    top()->beginParsingChildren();
+}
+
+void HTMLElementStack::popCommon()
+{
+    ASSERT(!top()->hasTagName(HTMLNames::htmlTag));
+    ASSERT(!top()->hasTagName(HTMLNames::headTag) || !m_headElement);
+    ASSERT(!top()->hasTagName(HTMLNames::bodyTag) || !m_bodyElement);
+    top()->finishParsingChildren();
+    m_top = m_top->releaseNext();
+}
+
+void HTMLElementStack::removeNonTopCommon(Element* element)
+{
+    ASSERT(!element->hasTagName(HTMLNames::htmlTag));
+    ASSERT(!element->hasTagName(HTMLNames::bodyTag));
+    ASSERT(top() != element);
+    for (ElementRecord* pos = m_top.get(); pos; pos = pos->next()) {
+        if (pos->next()->element() == element) {
+            // FIXME: Is it OK to call finishParsingChildren()
+            // when the children aren't actually finished?
+            element->finishParsingChildren();
+            pos->setNext(pos->next()->releaseNext());
+            return;
+        }
+    }
+    ASSERT_NOT_REACHED();
+}
+
+#ifndef NDEBUG
+
+void HTMLElementStack::show()
+{
+    for (ElementRecord* record = m_top.get(); record; record = record->next())
+        record->element()->showNode();
+}
+
+#endif
+
+}