/*

    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 "HTMLParser.h"

#include "CharacterNames.h"

#include "CSSPropertyNames.h"

#include "CSSValueKeywords.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 "HTMLTokenizer.h"

#include "LocalizedStrings.h"

#include "Page.h"

#include "Settings.h"

#include "Text.h"

#include <wtf/StdLibExtras.h>

namespace WebCore {

using namespace HTMLNames;

static const unsigned cMaxRedundantTagDepth = 20;

static const unsigned cResidualStyleMaxDepth = 200;

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;

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.

 *

 */

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

    : m_document(doc)

    , m_current(doc)

    , m_didRefCurrent(false)

    , m_blockStack(0)

    , m_blocksInStack(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_parserQuirks(m_document->page() ? m_document->page()->chrome()->client()->createHTMLParserQuirks() : 0)

{

}

HTMLParser::HTMLParser(DocumentFragment* frag)

    : m_document(frag->document())

    , m_current(frag)

    , m_didRefCurrent(true)

    , m_blockStack(0)

    , m_blocksInStack(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_parserQuirks(m_document->page() ? m_document->page()->chrome()->client()->createHTMLParserQuirks() : 0)

{

    if (frag)

        frag->ref();

}

HTMLParser::~HTMLParser()

{

    freeBlock();

    if (m_didRefCurrent)

        m_current->deref();

}

void HTMLParser::reset()

{

    ASSERT(!m_isParsingFragment);

    setCurrent(m_document);

    freeBlock();

    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 HTMLParser::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;

}

PassRefPtr<Node> HTMLParser::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;

        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 (!insertNode(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());

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

        // 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 (!insertNode(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 HTMLParser::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->addChild(DocumentType::create(m_document, String::adopt(t->m_name), String::adopt(t->m_publicID), String::adopt(t->m_systemID)));

}

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 HTMLParser::insertNode(Node* n, bool flat)

{

    RefPtr<Node> protectNode(n);

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

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

    // <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 (tagPriority >= minBlockLevelTagPriority) {

        while (m_blocksInStack >= cMaxBlockDepth)

            popBlock(m_blockStack->tagName);

    }

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

        return false;

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

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

    Node* newNode = m_current->addChild(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_document->frame()->loader()->dispatchDocumentElementAvailable();

    return true;

}

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

{

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

    HTMLElement* e;

    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->addChild(n)) {

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

                        n->attach();

                    return true;

                } else

                    return false;

            }

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

            if (!m_current->isDocumentNode() ) {

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

                    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->addChild(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)

                    n->attach();

                return true;

            }

            if (m_inBody) {

                setSkipMode(h->tagQName());

                return false;

            }

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

            if (m_inBody && m_document->body()) {

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

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

                // some sites use <body bgcolor=rightcolor>...<body bgcolor=wrongcolor>

                reportError(RedundantHTMLBodyError, &localName);

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

                Element* existingBody = m_document->body();

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

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

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

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

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

                }

                return false;

            }

            else if (!m_current->isDocumentNode())

                return false;

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

            if (m_currentMapElement) {

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

                m_currentMapElement->addChild(n);

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

                    n->attach();

                handled = true;

                return true;

            }

            return false;

        } else if (h->hasLocalName(colgroupTag) || h->hasLocalName(captionTag)) {

            if (isTableRelated(m_current)) {

                while (m_blockStack && isTablePart(m_current))

                    popOneBlock();

                return insertNode(n);

            }

        }

    } else if (n->isCommentNode() && !m_head)

        return false;

    // 2. Next we examine our currently active element to do some further error handling.

    if (m_current->isHTMLElement()) {

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

        const AtomicString& currentTagName = h->localName();

        if (h->hasLocalName(htmlTag)) {

            HTMLElement* elt = n->isHTMLElement() ? static_cast<HTMLElement*>(n) : 0;

            if (elt && (elt->hasLocalName(scriptTag) || elt->hasLocalName(styleTag) ||

                elt->hasLocalName(metaTag) || elt->hasLocalName(linkTag) ||

                elt->hasLocalName(objectTag) || elt->hasLocalName(embedTag) ||

                elt->hasLocalName(titleTag) || elt->hasLocalName(isindexTag) ||

                elt->hasLocalName(baseTag))) {

                if (!m_head) {

                    m_head = new HTMLHeadElement(headTag, m_document);

                    insertNode(m_head.get());

                    handled = true;

                }

            } else {

                if (n->isTextNode()) {

                    Text* t = static_cast<Text*>(n);

                    if (t->containsOnlyWhitespace())

                        return false;