/*

 * Copyright (C) 2008 Apple Inc. All Rights Reserved.

 * Copyright (C) 2009 Torch Mobile, Inc. http://www.torchmobile.com/

 * 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 APPLE 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 APPLE 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 "HTMLTokenizer.h"

#include "AtomicString.h"

#include "HTMLEntityParser.h"

#include "HTMLToken.h"

#include "HTMLNames.h"

#include "NotImplemented.h"

#include <wtf/ASCIICType.h>

#include <wtf/CurrentTime.h>

#include <wtf/UnusedParam.h>

#include <wtf/text/CString.h>

#include <wtf/unicode/Unicode.h>

using namespace WTF;

namespace WebCore {

using namespace HTMLNames;

const UChar HTMLTokenizer::InputStreamPreprocessor::endOfFileMarker = 0;

namespace {

inline UChar toLowerCase(UChar cc)

{

    ASSERT(isASCIIUpper(cc));

    const int lowerCaseOffset = 0x20;

    return cc + lowerCaseOffset;

}

inline bool isTokenizerWhitespace(UChar cc)

{

    return cc == '\x09' || cc == '\x0A' || cc == '\x0C' || cc == ' ';

}

inline void advanceStringAndASSERTIgnoringCase(SegmentedString& source, const char* expectedCharacters)

{

    while (*expectedCharacters)

        source.advanceAndASSERTIgnoringCase(*expectedCharacters++);

}

inline bool vectorEqualsString(const Vector<UChar, 32>& vector, const String& string)

{

    if (vector.size() != string.length())

        return false;

    const UChar* stringData = string.characters();

    const UChar* vectorData = vector.data();

    // FIXME: Is there a higher-level function we should be calling here?

    return !memcmp(stringData, vectorData, vector.size() * sizeof(UChar));

}

inline bool isEndTagBufferingState(HTMLTokenizer::State state)

{

    switch (state) {

    case HTMLTokenizer::RCDATAEndTagOpenState:

    case HTMLTokenizer::RCDATAEndTagNameState:

    case HTMLTokenizer::RAWTEXTEndTagOpenState:

    case HTMLTokenizer::RAWTEXTEndTagNameState:

    case HTMLTokenizer::ScriptDataEndTagOpenState:

    case HTMLTokenizer::ScriptDataEndTagNameState:

    case HTMLTokenizer::ScriptDataEscapedEndTagOpenState:

    case HTMLTokenizer::ScriptDataEscapedEndTagNameState:

        return true;

    default:

        return false;

    }

}

}

HTMLTokenizer::HTMLTokenizer()

{

    reset();

}

HTMLTokenizer::~HTMLTokenizer()

{

}

void HTMLTokenizer::reset()

{

    m_state = DataState;

    m_token = 0;

    m_lineNumber = 0;

    m_skipLeadingNewLineForListing = false;

    m_additionalAllowedCharacter = '\0';

}

inline bool HTMLTokenizer::processEntity(SegmentedString& source)

{

    bool notEnoughCharacters = false;

    unsigned value = consumeHTMLEntity(source, notEnoughCharacters);

    if (notEnoughCharacters)

        return false;

    if (!value)

        bufferCharacter('&');

    else

        bufferCodePoint(value);

    return true;

}

#if COMPILER(MSVC)

// We need to disable the "unreachable code" warning because we want to assert

// that some code points aren't reached in the state machine.

#pragma warning(disable: 4702)

#endif

#define BEGIN_STATE(stateName) case stateName: stateName:

#define END_STATE() ASSERT_NOT_REACHED(); break;

// We use this macro when the HTML5 spec says "reconsume the current input

// character in the <mumble> state."

#define RECONSUME_IN(stateName)                                            \

    do {                                                                   \

        m_state = stateName;                                               \

        goto stateName;                                                    \

    } while (false)

// We use this macro when the HTML5 spec says "consume the next input

// character ... and switch to the <mumble> state."

#define ADVANCE_TO(stateName)                                              \

    do {                                                                   \

        m_state = stateName;                                               \

        if (!m_inputStreamPreprocessor.advance(source, m_lineNumber))      \

            return shouldEmitBufferedCharacterToken(source);               \

        cc = m_inputStreamPreprocessor.nextInputCharacter();               \

        goto stateName;                                                    \

    } while (false)

// Sometimes there's more complicated logic in the spec that separates when

// we consume the next input character and when we switch to a particular

// state.  We handle those cases by advancing the source directly and using

// this macro to switch to the indicated state.

#define SWITCH_TO(stateName)                                               \

    do {                                                                   \

        m_state = stateName;                                               \

        if (source.isEmpty() || !m_inputStreamPreprocessor.peek(source, m_lineNumber)) \

            return shouldEmitBufferedCharacterToken(source);               \

        cc = m_inputStreamPreprocessor.nextInputCharacter();               \

        goto stateName;                                                    \

    } while (false)

inline void HTMLTokenizer::saveEndTagNameIfNeeded()

{

    ASSERT(m_token->type() != HTMLToken::Uninitialized);

    if (m_token->type() == HTMLToken::StartTag)

        m_appropriateEndTagName = m_token->name();

}

// We use this function when the HTML5 spec says "Emit the current <mumble>

// token. Switch to the <mumble> state."  We use the word "resume" instead of

// switch to indicate that this macro actually returns and that we'll end up

// in the state when we "resume" (i.e., are called again).

bool HTMLTokenizer::emitAndResumeIn(SegmentedString& source, State state)

{

    m_state = state;

    source.advance(m_lineNumber);

    saveEndTagNameIfNeeded();

    return true;

}

// Identical to emitAndResumeIn, except does not advance.

bool HTMLTokenizer::emitAndReconsumeIn(SegmentedString&, State state)

{

    m_state = state;

    saveEndTagNameIfNeeded();

    return true;

}

// Used to emit the EndOfFile token.

// Check if we have buffered characters to emit first before emitting the EOF.

bool HTMLTokenizer::emitEndOfFile(SegmentedString& source)

{

    if (shouldEmitBufferedCharacterToken(source))

        return true;

    m_state = DataState;

    source.advance(m_lineNumber);

    m_token->clear();

    m_token->makeEndOfFile();

    return true;

}

bool HTMLTokenizer::flushBufferedEndTag(SegmentedString& source)

{

    ASSERT(m_token->type() == HTMLToken::Character || m_token->type() == HTMLToken::Uninitialized);

    source.advance(m_lineNumber);

    if (m_token->type() == HTMLToken::Character)

        return true;

    m_token->beginEndTag(m_bufferedEndTagName);

    m_bufferedEndTagName.clear();

    return false;

}

#define FLUSH_AND_ADVANCE_TO(stateName)                                    \

    do {                                                                   \

        m_state = stateName;                                               \

        if (flushBufferedEndTag(source))                                   \

            return true;                                                   \

        if (source.isEmpty()                                               \

            || !m_inputStreamPreprocessor.peek(source, m_lineNumber))      \

            return shouldEmitBufferedCharacterToken(source);               \

        cc = m_inputStreamPreprocessor.nextInputCharacter();               \

        goto stateName;                                                    \

    } while (false)

bool HTMLTokenizer::flushEmitAndResumeIn(SegmentedString& source, State state)

{

    m_state = state;

    flushBufferedEndTag(source);

    return true;

}

bool HTMLTokenizer::nextToken(SegmentedString& source, HTMLToken& token)

{

    // If we have a token in progress, then we're supposed to be called back

    // with the same token so we can finish it.

    ASSERT(!m_token || m_token == &token || token.type() == HTMLToken::Uninitialized);

    m_token = &token;

    if (!m_bufferedEndTagName.isEmpty() && !isEndTagBufferingState(m_state)) {

        // FIXME: This should call flushBufferedEndTag().

        // We started an end tag during our last iteration.

        m_token->beginEndTag(m_bufferedEndTagName);

        m_bufferedEndTagName.clear();

        if (m_state == DataState) {

            // We're back in the data state, so we must be done with the tag.

            return true;

        }

    }

    if (source.isEmpty() || !m_inputStreamPreprocessor.peek(source, m_lineNumber))

        return shouldEmitBufferedCharacterToken(source);

    UChar cc = m_inputStreamPreprocessor.nextInputCharacter();

    // http://www.whatwg.org/specs/web-apps/current-work/multipage/tokenization.html#parsing-main-inbody

    // Note that this logic is different than the generic \r\n collapsing

    // handled in the input stream preprocessor.  This logic is here as an

    // "authoring convenience" so folks can write:

    //

    // <pre>

    // lorem ipsum

    // lorem ipsum

    // </pre>

    //

    // without getting an extra newline at the start of their <pre> element.

    if (m_skipLeadingNewLineForListing) {

        m_skipLeadingNewLineForListing = false;

        if (cc == '\n') {

            if (m_state == DataState)

                ADVANCE_TO(DataState);

            if (m_state == RCDATAState)

                ADVANCE_TO(RCDATAState);

            ASSERT_NOT_REACHED();

        }

    }

    // Source: http://www.whatwg.org/specs/web-apps/current-work/#tokenisation0

    switch (m_state) {

    BEGIN_STATE(DataState) {

        if (cc == '&')

            ADVANCE_TO(CharacterReferenceInDataState);

        else if (cc == '<') {

            if (m_token->type() == HTMLToken::Character) {

                // We have a bunch of character tokens queued up that we

                // are emitting lazily here.

                return true;

            }

            ADVANCE_TO(TagOpenState);

        } else if (cc == InputStreamPreprocessor::endOfFileMarker)

            return emitEndOfFile(source);

        else {

            bufferCharacter(cc);

            ADVANCE_TO(DataState);

        }

    }

    END_STATE()

    BEGIN_STATE(CharacterReferenceInDataState) {

        if (!processEntity(source))

            return shouldEmitBufferedCharacterToken(source);

        SWITCH_TO(DataState);

    }

    END_STATE()

    BEGIN_STATE(RCDATAState) {

        if (cc == '&')

            ADVANCE_TO(CharacterReferenceInRCDATAState);

        else if (cc == '<')

            ADVANCE_TO(RCDATALessThanSignState);

        else if (cc == InputStreamPreprocessor::endOfFileMarker)

            return emitEndOfFile(source);

        else {

            bufferCharacter(cc);

            ADVANCE_TO(RCDATAState);

        }

    }

    END_STATE()

    BEGIN_STATE(CharacterReferenceInRCDATAState) {

        if (!processEntity(source))

            return shouldEmitBufferedCharacterToken(source);

        SWITCH_TO(RCDATAState);

    }

    END_STATE()

    BEGIN_STATE(RAWTEXTState) {

        if (cc == '<')

            ADVANCE_TO(RAWTEXTLessThanSignState);

        else if (cc == InputStreamPreprocessor::endOfFileMarker)

            return emitEndOfFile(source);

        else {

            bufferCharacter(cc);

            ADVANCE_TO(RAWTEXTState);

        }

    }

    END_STATE()

    BEGIN_STATE(ScriptDataState) {

        if (cc == '<')

            ADVANCE_TO(ScriptDataLessThanSignState);

        else if (cc == InputStreamPreprocessor::endOfFileMarker)

            return emitEndOfFile(source);

        else {

            bufferCharacter(cc);

            ADVANCE_TO(ScriptDataState);

        }

    }

    END_STATE()

    BEGIN_STATE(PLAINTEXTState) {

        if (cc == InputStreamPreprocessor::endOfFileMarker)

            return emitEndOfFile(source);

        else

            bufferCharacter(cc);

        ADVANCE_TO(PLAINTEXTState);

    }

    END_STATE()

    BEGIN_STATE(TagOpenState) {

        if (cc == '!')

            ADVANCE_TO(MarkupDeclarationOpenState);

        else if (cc == '/')

            ADVANCE_TO(EndTagOpenState);

        else if (isASCIIUpper(cc)) {

            m_token->beginStartTag(toLowerCase(cc));

            ADVANCE_TO(TagNameState);

        } else if (isASCIILower(cc)) {

            m_token->beginStartTag(cc);

            ADVANCE_TO(TagNameState);

        } else if (cc == '?') {

            parseError();

            // The spec consumes the current character before switching

            // to the bogus comment state, but it's easier to implement

            // if we reconsume the current character.

            RECONSUME_IN(BogusCommentState);

        } else {

            parseError();

            bufferCharacter('<');

            RECONSUME_IN(DataState);

        }

    }

    END_STATE()

    BEGIN_STATE(EndTagOpenState) {

        if (isASCIIUpper(cc)) {

            m_token->beginEndTag(toLowerCase(cc));

            ADVANCE_TO(TagNameState);

        } else if (isASCIILower(cc)) {

            m_token->beginEndTag(cc);

            ADVANCE_TO(TagNameState);

        } else if (cc == '>') {

            parseError();

            ADVANCE_TO(DataState);

        } else if (cc == InputStreamPreprocessor::endOfFileMarker) {

            parseError();

            bufferCharacter('<');

            bufferCharacter('/');

            RECONSUME_IN(DataState);

        } else {

            parseError();

            RECONSUME_IN(BogusCommentState);

        }

    }

    END_STATE()

    BEGIN_STATE(TagNameState) {

        if (isTokenizerWhitespace(cc))

            ADVANCE_TO(BeforeAttributeNameState);

        else if (cc == '/')

            ADVANCE_TO(SelfClosingStartTagState);

        else if (cc == '>')

            return emitAndResumeIn(source, DataState);

        else if (isASCIIUpper(cc)) {

            m_token->appendToName(toLowerCase(cc));

            ADVANCE_TO(TagNameState);

        } if (cc == InputStreamPreprocessor::endOfFileMarker) {

            parseError();

            RECONSUME_IN(DataState);

        } else {

            m_token->appendToName(cc);

            ADVANCE_TO(TagNameState);

        }

    }

    END_STATE()

    BEGIN_STATE(RCDATALessThanSignState) {

        if (cc == '/') {

            m_temporaryBuffer.clear();

            ASSERT(m_bufferedEndTagName.isEmpty());

            ADVANCE_TO(RCDATAEndTagOpenState);

        } else {

            bufferCharacter('<');

            RECONSUME_IN(RCDATAState);

        }

    }

    END_STATE()

    BEGIN_STATE(RCDATAEndTagOpenState) {

        if (isASCIIUpper(cc)) {

            m_temporaryBuffer.append(cc);

            addToPossibleEndTag(toLowerCase(cc));

            ADVANCE_TO(RCDATAEndTagNameState);

        } else if (isASCIILower(cc)) {

            m_temporaryBuffer.append(cc);

            addToPossibleEndTag(cc);

            ADVANCE_TO(RCDATAEndTagNameState);

        } else {

            bufferCharacter('<');

            bufferCharacter('/');

            RECONSUME_IN(RCDATAState);

        }

    }

    END_STATE()

    BEGIN_STATE(RCDATAEndTagNameState) {

        if (isASCIIUpper(cc)) {

            m_temporaryBuffer.append(cc);

            addToPossibleEndTag(toLowerCase(cc));

            ADVANCE_TO(RCDATAEndTagNameState);

        } else if (isASCIILower(cc)) {

            m_temporaryBuffer.append(cc);

            addToPossibleEndTag(cc);

            ADVANCE_TO(RCDATAEndTagNameState);

        } else {

            if (isTokenizerWhitespace(cc)) {

                if (isAppropriateEndTag())

                    FLUSH_AND_ADVANCE_TO(BeforeAttributeNameState);

            } else if (cc == '/') {

                if (isAppropriateEndTag())

                    FLUSH_AND_ADVANCE_TO(SelfClosingStartTagState);

            } else if (cc == '>') {

                if (isAppropriateEndTag())

                    return flushEmitAndResumeIn(source, DataState);

            }

            bufferCharacter('<');

            bufferCharacter('/');

            m_token->appendToCharacter(m_temporaryBuffer);

            m_bufferedEndTagName.clear();

            RECONSUME_IN(RCDATAState);

        }

    }

    END_STATE()

    BEGIN_STATE(RAWTEXTLessThanSignState) {

        if (cc == '/') {

            m_temporaryBuffer.clear();

            ASSERT(m_bufferedEndTagName.isEmpty());

            ADVANCE_TO(RAWTEXTEndTagOpenState);

        } else {

            bufferCharacter('<');

            RECONSUME_IN(RAWTEXTState);

        }

    }

    END_STATE()

    BEGIN_STATE(RAWTEXTEndTagOpenState) {

        if (isASCIIUpper(cc)) {

            m_temporaryBuffer.append(cc);

            addToPossibleEndTag(toLowerCase(cc));

            ADVANCE_TO(RAWTEXTEndTagNameState);

        } else if (isASCIILower(cc)) {

            m_temporaryBuffer.append(cc);

            addToPossibleEndTag(cc);

            ADVANCE_TO(RAWTEXTEndTagNameState);

        } else {

            bufferCharacter('<');

            bufferCharacter('/');

            RECONSUME_IN(RAWTEXTState);

        }

    }

    END_STATE()

    BEGIN_STATE(RAWTEXTEndTagNameState) {

        if (isASCIIUpper(cc)) {

            m_temporaryBuffer.append(cc);

            addToPossibleEndTag(toLowerCase(cc));

            ADVANCE_TO(RAWTEXTEndTagNameState);

        } else if (isASCIILower(cc)) {

            m_temporaryBuffer.append(cc);