/*

    Copyright (C) 1997 Martin Jones (mjones@kde.org)

              (C) 1997 Torben Weis (weis@kde.org)

              (C) 1999,2001 Lars Knoll (knoll@kde.org)

              (C) 2000,2001 Dirk Mueller (mueller@kde.org)

    Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.

    Copyright (C) 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)

    This library is free software; you can redistribute it and/or

    modify it under the terms of the GNU Library General Public

    License as published by the Free Software Foundation; either

    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,

    but WITHOUT ANY WARRANTY; without even the implied warranty of

    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public License

    along with this library; see the file COPYING.LIB.  If not, write to

    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,

    Boston, MA 02110-1301, USA.

*/

#include "config.h"

#include "LegacyHTMLTreeBuilder.h"

#include "CharacterNames.h"

#include "CSSPropertyNames.h"

#include "CSSValueKeywords.h"

#include "Chrome.h"

#include "ChromeClient.h"

#include "Comment.h"

#include "Console.h"

#include "DOMWindow.h"

#include "DocumentFragment.h"

#include "DocumentType.h"

#include "Frame.h"

#include "HTMLBodyElement.h"

#include "HTMLDocument.h"

#include "HTMLDivElement.h"

#include "HTMLDListElement.h"

#include "HTMLElementFactory.h"

#include "HTMLFormElement.h"

#include "HTMLHeadElement.h"

#include "HTMLHRElement.h"

#include "HTMLHtmlElement.h"

#include "HTMLIsIndexElement.h"

#include "HTMLMapElement.h"

#include "HTMLNames.h"

#include "HTMLParserQuirks.h"

#include "HTMLTableCellElement.h"

#include "HTMLTableRowElement.h"

#include "HTMLTableSectionElement.h"

#include "LegacyHTMLDocumentParser.h"

#include "LocalizedStrings.h"

#include "Page.h"

#include "Settings.h"

#include "Text.h"

#include "TreeDepthLimit.h"

#include <wtf/StdLibExtras.h>

#include <wtf/dtoa.h>

namespace WebCore {

using namespace HTMLNames;

static const unsigned cMaxRedundantTagDepth = 20;

static const unsigned cResidualStyleMaxDepth = 200;

static const unsigned cResidualStyleIterationLimit = 10;

static const int minBlockLevelTagPriority = 3;

// A cap on the number of tags with priority minBlockLevelTagPriority or higher

// allowed in m_blockStack. The cap is enforced by adding such new elements as

// siblings instead of children once it is reached.

static const size_t cMaxBlockDepth = 4096;

typedef HashSet<AtomicStringImpl*> TagNameSet;

template< size_t ArraySize >

static void addTags(TagNameSet& set, QualifiedName (&names)[ArraySize])

{

    for (size_t x = 0; x < ArraySize; x++) {

        const QualifiedName& name = names[x];

        set.add(name.localName().impl());

    }

}

struct HTMLStackElem : Noncopyable {

    HTMLStackElem(const AtomicString& t, int lvl, Node* n, bool r, HTMLStackElem* nx)

        : tagName(t)

        , level(lvl)

        , strayTableContent(false)

        , node(n)

        , didRefNode(r)

        , next(nx)

    {

    }

    void derefNode()

    {

        if (didRefNode)

            node->deref();

    }

    AtomicString tagName;

    int level;

    bool strayTableContent;

    Node* node;

    bool didRefNode;

    HTMLStackElem* next;

};

/**

 * The parser parses tokenized input into the document, building up the

 * document tree. If the document is well-formed, parsing it is straightforward.

 *

 * Unfortunately, we have to handle many HTML documents that are not well-formed,

 * so the parser has to be tolerant about errors.

 *

 * We have to take care of at least the following error conditions:

 *

 * 1. The element being added is explicitly forbidden inside some outer tag.

 *    In this case we should close all tags up to the one, which forbids

 *    the element, and add it afterwards.

 *

 * 2. We are not allowed to add the element directly. It could be that

 *    the person writing the document forgot some tag in between (or that the

 *    tag in between is optional). This could be the case with the following

 *    tags: HTML HEAD BODY TBODY TR TD LI (did I forget any?).

 *

 * 3. We want to add a block element inside to an inline element. Close all

 *    inline elements up to the next higher block element.

 *

 * 4. If this doesn't help, close elements until we are allowed to add the

 *    element or ignore the tag.

 *

 */

LegacyHTMLTreeBuilder::LegacyHTMLTreeBuilder(HTMLDocument* doc, bool reportErrors)

    : m_document(doc)

    , m_current(doc)

    , m_didRefCurrent(false)

    , m_blockStack(0)

    , m_blocksInStack(0)

    , m_treeDepth(0)

    , m_hasPElementInScope(NotInScope)

    , m_inBody(false)

    , m_haveContent(false)

    , m_haveFrameSet(false)

    , m_isParsingFragment(false)

    , m_reportErrors(reportErrors)

    , m_handlingResidualStyleAcrossBlocks(false)

    , m_inStrayTableContent(0)

    , m_scriptingPermission(FragmentScriptingAllowed)

    , m_parserQuirks(m_document->page() ? m_document->page()->chrome()->client()->createHTMLParserQuirks() : 0)

{

}

LegacyHTMLTreeBuilder::LegacyHTMLTreeBuilder(DocumentFragment* frag, FragmentScriptingPermission scriptingPermission)

    : m_document(frag->document())

    , m_current(frag)

    , m_didRefCurrent(true)

    , m_blockStack(0)

    , m_blocksInStack(0)

    , m_treeDepth(0)

    , m_hasPElementInScope(NotInScope)

    , m_inBody(true)

    , m_haveContent(false)

    , m_haveFrameSet(false)

    , m_isParsingFragment(true)

    , m_reportErrors(false)

    , m_handlingResidualStyleAcrossBlocks(false)

    , m_inStrayTableContent(0)

    , m_scriptingPermission(scriptingPermission)

    , m_parserQuirks(m_document->page() ? m_document->page()->chrome()->client()->createHTMLParserQuirks() : 0)

{

    if (frag)

        frag->ref();

}

LegacyHTMLTreeBuilder::~LegacyHTMLTreeBuilder()

{

    freeBlock();

    if (m_didRefCurrent)

        m_current->deref();

}

void LegacyHTMLTreeBuilder::reset()

{

    ASSERT(!m_isParsingFragment);

    setCurrent(m_document);

    freeBlock();

    m_treeDepth = 0;

    m_inBody = false;

    m_haveFrameSet = false;

    m_haveContent = false;

    m_inStrayTableContent = 0;

    m_currentFormElement = 0;

    m_currentMapElement = 0;

    m_head = 0;

    m_isindexElement = 0;

    m_skipModeTag = nullAtom;

    if (m_parserQuirks)

        m_parserQuirks->reset();

}

void LegacyHTMLTreeBuilder::setCurrent(Node* newCurrent) 

{

    bool didRefNewCurrent = newCurrent && newCurrent != m_document;

    if (didRefNewCurrent) 

        newCurrent->ref(); 

    if (m_didRefCurrent) 

        m_current->deref();

    m_current = newCurrent;

    m_didRefCurrent = didRefNewCurrent;

}

inline static int tagPriorityOfNode(Node* n)

{

    return n->isHTMLElement() ? static_cast<HTMLElement*>(n)->tagPriority() : 0;

}

inline void LegacyHTMLTreeBuilder::limitDepth(int tagPriority)

{

    while (m_treeDepth >= maxDOMTreeDepth)

        popBlock(m_blockStack->tagName);

    if (tagPriority >= minBlockLevelTagPriority) {

        while (m_blocksInStack >= cMaxBlockDepth)

            popBlock(m_blockStack->tagName);

    }

}

inline bool LegacyHTMLTreeBuilder::insertNodeAfterLimitDepth(Node* n, bool flat)

{

    limitDepth(tagPriorityOfNode(n));

    return insertNode(n, flat);

}

PassRefPtr<Node> LegacyHTMLTreeBuilder::parseToken(Token* t)

{

    if (!m_skipModeTag.isNull()) {

        if (!t->beginTag && t->tagName == m_skipModeTag)

            // Found the end tag for the current skip mode, so we're done skipping.

            m_skipModeTag = nullAtom;

        else if (m_current->localName() == t->tagName)

            // Do not skip </iframe>.

            // FIXME: What does that comment mean? How can it be right to parse a token without clearing m_skipModeTag?

            ;

        else

            return 0;

    }

    // Apparently some sites use </br> instead of <br>. Be compatible with IE and Firefox and treat this like <br>.

    if (t->isCloseTag(brTag) && m_document->inCompatMode()) {

        reportError(MalformedBRError);

        t->beginTag = true;

    }

    if (!t->beginTag) {

        processCloseTag(t);

        return 0;

    }

    // Ignore spaces, if we're not inside a paragraph or other inline code.

    // Do not alter the text if it is part of a scriptTag.

    if (t->tagName == textAtom && t->text && m_current->localName() != scriptTag) {

        if (m_inBody && !skipMode() && m_current->localName() != styleTag &&

            m_current->localName() != titleTag && !t->text->containsOnlyWhitespace())

            m_haveContent = true;

        // HTML5 requires text node coalescing.

        // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#insert-a-character

        Node* previousChild = m_current->lastChild();

        if (previousChild && previousChild->isTextNode()) {

            // Only coalesce text nodes if the text node wouldn't be foster parented.

            if (!m_current->hasTagName(htmlTag)

                && !m_current->hasTagName(tableTag)

                && !m_current->hasTagName(trTag)

                && !m_current->hasTagName(theadTag)

                && !m_current->hasTagName(tbodyTag)

                && !m_current->hasTagName(tfootTag)

                && !m_current->hasTagName(titleTag)) {

                // Technically we're only supposed to merge into the previous

                // text node if it was the last node inserted by the parser.

                // (This was a spec modification made to make it easier for

                // mozilla to run their parser in a thread.)

                // In practice it does not seem to matter.

                CharacterData* textNode = static_cast<CharacterData*>(previousChild);

                textNode->parserAppendData(t->text);

                return textNode;

            }

        }

        RefPtr<Node> n;

        String text = t->text.get();

        unsigned charsLeft = text.length();

        while (charsLeft) {

            // split large blocks of text to nodes of manageable size

            n = Text::createWithLengthLimit(m_document, text, charsLeft);

            if (!insertNodeAfterLimitDepth(n.get(), t->selfClosingTag))

                return 0;

        }

        return n;

    }

    RefPtr<Node> n = getNode(t);

    // just to be sure, and to catch currently unimplemented stuff

    if (!n)

        return 0;

    // set attributes

    if (n->isHTMLElement()) {

        HTMLElement* e = static_cast<HTMLElement*>(n.get());

        if (m_scriptingPermission == FragmentScriptingAllowed || t->tagName != scriptTag)

            e->setAttributeMap(t->attrs.get(), m_scriptingPermission);

        // take care of optional close tags

        if (e->endTagRequirement() == TagStatusOptional)

            popBlock(t->tagName);

        // If the node does not have a forbidden end tag requirement, and if the broken XML self-closing

        // syntax was used, report an error.

        if (t->brokenXMLStyle && e->endTagRequirement() != TagStatusForbidden) {

            if (t->tagName == scriptTag)

                reportError(IncorrectXMLCloseScriptWarning);

            else

                reportError(IncorrectXMLSelfCloseError, &t->tagName);

        }

    }

    if (!insertNodeAfterLimitDepth(n.get(), t->selfClosingTag)) {

        // we couldn't insert the node

        if (n->isElementNode()) {

            Element* e = static_cast<Element*>(n.get());

            e->setAttributeMap(0);

        }

        if (m_currentMapElement == n)

            m_currentMapElement = 0;

        if (m_currentFormElement == n)

            m_currentFormElement = 0;

        if (m_head == n)

            m_head = 0;

        return 0;

    }

    return n;

}

void LegacyHTMLTreeBuilder::parseDoctypeToken(DoctypeToken* t)

{

    // Ignore any doctype after the first.  Ignore doctypes in fragments.

    if (m_document->doctype() || m_isParsingFragment || m_current != m_document)

        return;

    // Make a new doctype node and set it as our doctype.

    m_document->legacyParserAddChild(DocumentType::create(m_document, String::adopt(t->m_name), String::adopt(t->m_publicID), String::adopt(t->m_systemID)));

    if (t->m_forceQuirks)

        m_document->setParseMode(Document::Compat);

}

static bool isTableSection(const Node* n)

{

    return n->hasTagName(tbodyTag) || n->hasTagName(tfootTag) || n->hasTagName(theadTag);

}

static bool isTablePart(const Node* n)

{

    return n->hasTagName(trTag) || n->hasTagName(tdTag) || n->hasTagName(thTag)

        || isTableSection(n);

}

static bool isTableRelated(const Node* n)

{

    return n->hasTagName(tableTag) || isTablePart(n);

}

static bool isScopingTag(const AtomicString& tagName)

{

    return tagName == appletTag || tagName == captionTag || tagName == tdTag

        || tagName == thTag || tagName == buttonTag || tagName == marqueeTag

        || tagName == objectTag || tagName == tableTag || tagName == htmlTag;

}

bool LegacyHTMLTreeBuilder::insertNode(Node* n, bool flat)

{

    RefPtr<Node> protectNode(n);

    const AtomicString& localName = n->localName();

    // <table> is never allowed inside stray table content.  Always pop out of the stray table content

    // and close up the first table, and then start the second table as a sibling.

    if (m_inStrayTableContent && localName == tableTag)

        popBlock(tableTag);

    if (m_parserQuirks && !m_parserQuirks->shouldInsertNode(m_current, n))

        return false;

    int tagPriority = tagPriorityOfNode(n);

    // let's be stupid and just try to insert it.

    // this should work if the document is well-formed

    Node* newNode = m_current->legacyParserAddChild(n);

    if (!newNode)

        return handleError(n, flat, localName, tagPriority); // Try to handle the error.

    // don't push elements without end tags (e.g., <img>) on the stack

    bool parentAttached = m_current->attached();

    if (tagPriority > 0 && !flat) {

        if (newNode == m_current) {

            // This case should only be hit when a demoted <form> is placed inside a table.

            ASSERT(localName == formTag);

            reportError(FormInsideTablePartError, &m_current->localName());

            HTMLFormElement* form = static_cast<HTMLFormElement*>(n);

            form->setDemoted(true);

        } else {

            // The pushBlock function transfers ownership of current to the block stack

            // so we're guaranteed that m_didRefCurrent is false. The code below is an

            // optimized version of setCurrent that takes advantage of that fact and also

            // assumes that newNode is neither 0 nor a pointer to the document.

            pushBlock(localName, tagPriority);

            newNode->beginParsingChildren();

            ASSERT(!m_didRefCurrent);

            newNode->ref(); 

            m_current = newNode;

            m_didRefCurrent = true;

        }

        if (parentAttached && !n->attached() && !m_isParsingFragment)

            n->attach();

    } else {

        if (parentAttached && !n->attached() && !m_isParsingFragment)

            n->attach();

        n->finishParsingChildren();

    }

    if (localName == htmlTag && m_document->frame() && !m_isParsingFragment)

        m_document->frame()->loader()->dispatchDocumentElementAvailable();

    return true;

}

bool LegacyHTMLTreeBuilder::handleError(Node* n, bool flat, const AtomicString& localName, int tagPriority)

{

    // Error handling code.  This is just ad hoc handling of specific parent/child combinations.

    bool handled = false;

    // 1. Check out the element's tag name to decide how to deal with errors.

    if (n->isHTMLElement()) {

        HTMLElement* h = static_cast<HTMLElement*>(n);

        if (h->hasLocalName(trTag) || h->hasLocalName(thTag) || h->hasLocalName(tdTag)) {

            if (m_inStrayTableContent && !isTableRelated(m_current)) {

                reportError(MisplacedTablePartError, &localName, &m_current->localName());

                // pop out to the nearest enclosing table-related tag.

                while (m_blockStack && !isTableRelated(m_current))

                    popOneBlock();

                return insertNode(n);

            }

        } else if (h->hasLocalName(headTag)) {

            if (!m_current->isDocumentNode() && !m_current->hasTagName(htmlTag)) {

                reportError(MisplacedHeadError);

                return false;

            }

        } else if (h->hasLocalName(metaTag) || h->hasLocalName(linkTag) || h->hasLocalName(baseTag)) {

            bool createdHead = false;

            if (!m_head) {

                createHead();

                createdHead = true;

            }

            if (m_head) {

                if (!createdHead)

                    reportError(MisplacedHeadContentError, &localName, &m_current->localName());

                if (m_head->legacyParserAddChild(n)) {

                    if (!n->attached() && !m_isParsingFragment)

                        n->attach();

                    return true;

                }

                return false;

            }

        } else if (h->hasLocalName(htmlTag)) {

            if (!m_current->isDocumentNode() ) {

                if (m_document->documentElement() && m_document->documentElement()->hasTagName(htmlTag) && !m_isParsingFragment) {

                    reportError(RedundantHTMLBodyError, &localName);

                    // we have another <HTML> element.... apply attributes to existing one

                    // make sure we don't overwrite already existing attributes

                    NamedNodeMap* map = static_cast<Element*>(n)->attributes(true);

                    Element* existingHTML = static_cast<Element*>(m_document->documentElement());

                    NamedNodeMap* bmap = existingHTML->attributes(false);

                    for (unsigned l = 0; map && l < map->length(); ++l) {

                        Attribute* it = map->attributeItem(l);

                        if (!bmap->getAttributeItem(it->name()))

                            existingHTML->setAttribute(it->name(), it->value());

                    }

                }

                return false;

            }

        } else if (h->hasLocalName(titleTag) || h->hasLocalName(styleTag) || h->hasLocalName(scriptTag)) {

            bool createdHead = false;

            if (!m_head) {

                createHead();

                createdHead = true;

            }

            if (m_head) {

                Node* newNode = m_head->legacyParserAddChild(n);

                if (!newNode) {

                    setSkipMode(h->tagQName());

                    return false;

                }

                if (!createdHead)

                    reportError(MisplacedHeadContentError, &localName, &m_current->localName());

                pushBlock(localName, tagPriority);

                newNode->beginParsingChildren();

                setCurrent(newNode);

                if (!n->attached() && !m_isParsingFragment)