/*

 * Copyright (C) 2009 Apple 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 "JSONObject.h"

#include "BooleanObject.h"

#include "Error.h"

#include "ExceptionHelpers.h"

#include "JSArray.h"

#include "LiteralParser.h"

#include "PropertyNameArray.h"

#include <wtf/MathExtras.h>

namespace JSC {

ASSERT_CLASS_FITS_IN_CELL(JSONObject);

static JSValue JSC_HOST_CALL JSONProtoFuncParse(ExecState*, JSObject*, JSValue, const ArgList&);

static JSValue JSC_HOST_CALL JSONProtoFuncStringify(ExecState*, JSObject*, JSValue, const ArgList&);

}

#include "JSONObject.lut.h"

namespace JSC {

// PropertyNameForFunctionCall objects must be on the stack, since the JSValue that they create is not marked.

class PropertyNameForFunctionCall {

public:

    PropertyNameForFunctionCall(const Identifier&);

    PropertyNameForFunctionCall(unsigned);

    JSValue value(ExecState*) const;

private:

    const Identifier* m_identifier;

    unsigned m_number;

    mutable JSValue m_value;

};

class Stringifier : public Noncopyable {

public:

    Stringifier(ExecState*, JSValue replacer, JSValue space);

    ~Stringifier();

    JSValue stringify(JSValue);

    void markAggregate(MarkStack&);

private:

    typedef UString StringBuilder;

    class Holder {

    public:

        Holder(JSObject*);

        JSObject* object() const { return m_object; }

        bool appendNextProperty(Stringifier&, StringBuilder&);

    private:

        JSObject* const m_object;

        const bool m_isArray;

        bool m_isJSArray;

        unsigned m_index;

        unsigned m_size;

        RefPtr<PropertyNameArrayData> m_propertyNames;

    };

    friend class Holder;

    static void appendQuotedString(StringBuilder&, const UString&);

    JSValue toJSON(JSValue, const PropertyNameForFunctionCall&);

    enum StringifyResult { StringifyFailed, StringifySucceeded, StringifyFailedDueToUndefinedValue };

    StringifyResult appendStringifiedValue(StringBuilder&, JSValue, JSObject* holder, const PropertyNameForFunctionCall&);

    bool willIndent() const;

    void indent();

    void unindent();

    void startNewLine(StringBuilder&) const;

    Stringifier* const m_nextStringifierToMark;

    ExecState* const m_exec;

    const JSValue m_replacer;

    bool m_usingArrayReplacer;

    PropertyNameArray m_arrayReplacerPropertyNames;

    CallType m_replacerCallType;

    CallData m_replacerCallData;

    const UString m_gap;

    HashSet<JSObject*> m_holderCycleDetector;

    Vector<Holder, 16> m_holderStack;

    UString m_repeatedGap;

    UString m_indent;

};

// ------------------------------ helper functions --------------------------------

static inline JSValue unwrapBoxedPrimitive(ExecState* exec, JSValue value)

{

    if (!value.isObject())

        return value;

    JSObject* object = asObject(value);

    if (object->inherits(&NumberObject::info))

        return jsNumber(exec, object->toNumber(exec));

    if (object->inherits(&StringObject::info))

        return jsString(exec, object->toString(exec));

    if (object->inherits(&BooleanObject::info))

        return object->toPrimitive(exec);

    return value;

}

static inline UString gap(ExecState* exec, JSValue space)

{

    const int maxGapLength = 10;

    space = unwrapBoxedPrimitive(exec, space);

    // If the space value is a number, create a gap string with that number of spaces.

    double spaceCount;

    if (space.getNumber(spaceCount)) {

        int count;

        if (spaceCount > maxGapLength)

            count = maxGapLength;

        else if (!(spaceCount > 0))

            count = 0;

        else

            count = static_cast<int>(spaceCount);

        UChar spaces[maxGapLength];

        for (int i = 0; i < count; ++i)

            spaces[i] = ' ';

        return UString(spaces, count);

    }

    // If the space value is a string, use it as the gap string, otherwise use no gap string.

    UString spaces = space.getString();

    if (spaces.size() > maxGapLength) {

        spaces = spaces.substr(0, maxGapLength);

    }

    return spaces;

}

// ------------------------------ PropertyNameForFunctionCall --------------------------------

inline PropertyNameForFunctionCall::PropertyNameForFunctionCall(const Identifier& identifier)

    : m_identifier(&identifier)

{

}

inline PropertyNameForFunctionCall::PropertyNameForFunctionCall(unsigned number)

    : m_identifier(0)

    , m_number(number)

{

}

JSValue PropertyNameForFunctionCall::value(ExecState* exec) const

{

    if (!m_value) {

        if (m_identifier)

            m_value = jsString(exec, m_identifier->ustring());

        else

            m_value = jsNumber(exec, m_number);

    }

    return m_value;

}

// ------------------------------ Stringifier --------------------------------

Stringifier::Stringifier(ExecState* exec, JSValue replacer, JSValue space)

    : m_nextStringifierToMark(exec->globalData().firstStringifierToMark)

    , m_exec(exec)

    , m_replacer(replacer)

    , m_usingArrayReplacer(false)

    , m_arrayReplacerPropertyNames(exec)

    , m_replacerCallType(CallTypeNone)

    , m_gap(gap(exec, space))

{

    exec->globalData().firstStringifierToMark = this;

    if (!m_replacer.isObject())

        return;

    if (asObject(m_replacer)->inherits(&JSArray::info)) {

        m_usingArrayReplacer = true;

        JSObject* array = asObject(m_replacer);

        unsigned length = array->get(exec, exec->globalData().propertyNames->length).toUInt32(exec);

        for (unsigned i = 0; i < length; ++i) {

            JSValue name = array->get(exec, i);

            if (exec->hadException())

                break;

            UString propertyName;

            if (name.getString(propertyName)) {

                m_arrayReplacerPropertyNames.add(Identifier(exec, propertyName));

                continue;

            }

            double value = 0;

            if (name.getNumber(value)) {

                m_arrayReplacerPropertyNames.add(Identifier::from(exec, value));

                continue;

            }

            if (name.isObject()) {

                if (!asObject(name)->inherits(&NumberObject::info) && !asObject(name)->inherits(&StringObject::info))

                    continue;

                propertyName = name.toString(exec);

                if (exec->hadException())

                    break;

                m_arrayReplacerPropertyNames.add(Identifier(exec, propertyName));

            }

        }

        return;

    }

    m_replacerCallType = asObject(m_replacer)->getCallData(m_replacerCallData);

}

Stringifier::~Stringifier()

{

    ASSERT(m_exec->globalData().firstStringifierToMark == this);

    m_exec->globalData().firstStringifierToMark = m_nextStringifierToMark;

}

void Stringifier::markAggregate(MarkStack& markStack)

{

    for (Stringifier* stringifier = this; stringifier; stringifier = stringifier->m_nextStringifierToMark) {

        size_t size = m_holderStack.size();

        for (size_t i = 0; i < size; ++i)

            markStack.append(m_holderStack[i].object());

    }

}

JSValue Stringifier::stringify(JSValue value)

{

    JSObject* object = constructEmptyObject(m_exec);

    if (m_exec->hadException())

        return jsNull();

    PropertyNameForFunctionCall emptyPropertyName(m_exec->globalData().propertyNames->emptyIdentifier);

    object->putDirect(m_exec->globalData().propertyNames->emptyIdentifier, value);

    StringBuilder result;

    if (appendStringifiedValue(result, value, object, emptyPropertyName) != StringifySucceeded)

        return jsUndefined();

    if (m_exec->hadException())

        return jsNull();

    return jsString(m_exec, result);

}

void Stringifier::appendQuotedString(StringBuilder& builder, const UString& value)

{

    int length = value.size();

    // String length plus 2 for quote marks plus 8 so we can accomodate a few escaped characters.

    builder.reserveCapacity(builder.size() + length + 2 + 8);

    builder.append('"');

    const UChar* data = value.data();

    for (int i = 0; i < length; ++i) {

        int start = i;

        while (i < length && (data[i] > 0x1F && data[i] != '"' && data[i] != '\\'))

            ++i;

        builder.append(data + start, i - start);

        if (i >= length)

            break;

        switch (data[i]) {

            case '\t':

                builder.append('\\');

                builder.append('t');

                break;

            case '\r':

                builder.append('\\');

                builder.append('r');

                break;

            case '\n':

                builder.append('\\');

                builder.append('n');

                break;

            case '\f':

                builder.append('\\');

                builder.append('f');

                break;

            case '\b':

                builder.append('\\');

                builder.append('b');

                break;

            case '"':

                builder.append('\\');

                builder.append('"');

                break;

            case '\\':

                builder.append('\\');

                builder.append('\\');

                break;

            default:

                static const char hexDigits[] = "0123456789abcdef";

                UChar ch = data[i];

                UChar hex[] = { '\\', 'u', hexDigits[(ch >> 12) & 0xF], hexDigits[(ch >> 8) & 0xF], hexDigits[(ch >> 4) & 0xF], hexDigits[ch & 0xF] };

                builder.append(hex, sizeof(hex) / sizeof(UChar));

                break;

        }

    }

    builder.append('"');

}

inline JSValue Stringifier::toJSON(JSValue value, const PropertyNameForFunctionCall& propertyName)

{

    ASSERT(!m_exec->hadException());

    if (!value.isObject() || !asObject(value)->hasProperty(m_exec, m_exec->globalData().propertyNames->toJSON))

        return value;

    JSValue toJSONFunction = asObject(value)->get(m_exec, m_exec->globalData().propertyNames->toJSON);

    if (m_exec->hadException())

        return jsNull();

    if (!toJSONFunction.isObject())

        return value;

    JSObject* object = asObject(toJSONFunction);

    CallData callData;

    CallType callType = object->getCallData(callData);

    if (callType == CallTypeNone)

        return value;

    JSValue list[] = { propertyName.value(m_exec) };

    ArgList args(list, sizeof(list) / sizeof(JSValue));

    return call(m_exec, object, callType, callData, value, args);

}

Stringifier::StringifyResult Stringifier::appendStringifiedValue(StringBuilder& builder, JSValue value, JSObject* holder, const PropertyNameForFunctionCall& propertyName)

{

    // Call the toJSON function.

    value = toJSON(value, propertyName);

    if (m_exec->hadException())

        return StringifyFailed;

    // Call the replacer function.

    if (m_replacerCallType != CallTypeNone) {

        JSValue list[] = { propertyName.value(m_exec), value };

        ArgList args(list, sizeof(list) / sizeof(JSValue));

        value = call(m_exec, m_replacer, m_replacerCallType, m_replacerCallData, holder, args);

        if (m_exec->hadException())

            return StringifyFailed;

    }

    if (value.isUndefined() && !holder->inherits(&JSArray::info))

        return StringifyFailedDueToUndefinedValue;

    if (value.isNull()) {

        builder.append("null");

        return StringifySucceeded;

    }

    value = unwrapBoxedPrimitive(m_exec, value);

    if (m_exec->hadException())

        return StringifyFailed;

    if (value.isBoolean()) {

        builder.append(value.getBoolean() ? "true" : "false");

        return StringifySucceeded;

    }

    UString stringValue;

    if (value.getString(stringValue)) {

        appendQuotedString(builder, stringValue);

        return StringifySucceeded;

    }

    double numericValue;

    if (value.getNumber(numericValue)) {

        if (!isfinite(numericValue))

            builder.append("null");

        else

            builder.append(UString::from(numericValue));

        return StringifySucceeded;

    }

    if (!value.isObject())

        return StringifyFailed;

    JSObject* object = asObject(value);

    CallData callData;

    if (object->getCallData(callData) != CallTypeNone) {

        if (holder->inherits(&JSArray::info)) {

            builder.append("null");

            return StringifySucceeded;

        }

        return StringifyFailedDueToUndefinedValue;

    }

    // Handle cycle detection, and put the holder on the stack.

    if (!m_holderCycleDetector.add(object).second) {

        throwError(m_exec, TypeError, "JSON.stringify cannot serialize cyclic structures.");

        return StringifyFailed;

    }

    bool holderStackWasEmpty = m_holderStack.isEmpty();

    m_holderStack.append(object);

    if (!holderStackWasEmpty)

        return StringifySucceeded;

    // If this is the outermost call, then loop to handle everything on the holder stack.

    TimeoutChecker localTimeoutChecker(m_exec->globalData().timeoutChecker);

    localTimeoutChecker.reset();

    unsigned tickCount = localTimeoutChecker.ticksUntilNextCheck();

    do {

        while (m_holderStack.last().appendNextProperty(*this, builder)) {

            if (m_exec->hadException())

                return StringifyFailed;

            if (!--tickCount) {

                if (localTimeoutChecker.didTimeOut(m_exec)) {

                    m_exec->setException(createInterruptedExecutionException(&m_exec->globalData()));

                    return StringifyFailed;

                }

                tickCount = localTimeoutChecker.ticksUntilNextCheck();

            }

        }

        m_holderCycleDetector.remove(m_holderStack.last().object());

        m_holderStack.removeLast();

    } while (!m_holderStack.isEmpty());

    return StringifySucceeded;

}

inline bool Stringifier::willIndent() const

{

    return !m_gap.isEmpty();

}

inline void Stringifier::indent()

{

    // Use a single shared string, m_repeatedGap, so we don't keep allocating new ones as we indent and unindent.

    int newSize = m_indent.size() + m_gap.size();

    if (newSize > m_repeatedGap.size())

        m_repeatedGap.append(m_gap);

    ASSERT(newSize <= m_repeatedGap.size());

    m_indent = m_repeatedGap.substr(0, newSize);

}

inline void Stringifier::unindent()

{

    ASSERT(m_indent.size() >= m_gap.size());

    m_indent = m_repeatedGap.substr(0, m_indent.size() - m_gap.size());

}

inline void Stringifier::startNewLine(StringBuilder& builder) const

{

    if (m_gap.isEmpty())

        return;

    builder.append('\n');

    builder.append(m_indent);

}

inline Stringifier::Holder::Holder(JSObject* object)

    : m_object(object)

    , m_isArray(object->inherits(&JSArray::info))

    , m_index(0)

{

}

bool Stringifier::Holder::appendNextProperty(Stringifier& stringifier, StringBuilder& builder)

{

    ASSERT(m_index <= m_size);

    ExecState* exec = stringifier.m_exec;

    // First time through, initialize.

    if (!m_index) {

        if (m_isArray) {

            m_isJSArray = isJSArray(&exec->globalData(), m_object);

            m_size = m_object->get(exec, exec->globalData().propertyNames->length).toUInt32(exec);

            builder.append('[');

        } else {

            if (stringifier.m_usingArrayReplacer)

                m_propertyNames = stringifier.m_arrayReplacerPropertyNames.data();

            else {

                PropertyNameArray objectPropertyNames(exec);

                m_object->getPropertyNames(exec, objectPropertyNames);

                m_propertyNames = objectPropertyNames.releaseData();

            }

            m_size = m_propertyNames->propertyNameVector().size();

            builder.append('{');

        }

        stringifier.indent();

    }

    // Last time through, finish up and return false.

    if (m_index == m_size) {

        stringifier.unindent();

        if (m_size && builder[builder.size() - 1] != '{')

            stringifier.startNewLine(builder);

        builder.append(m_isArray ? ']' : '}');

        return false;

    }

    // Handle a single element of the array or object.

    unsigned index = m_index++;

    unsigned rollBackPoint = 0;

    StringifyResult stringifyResult;

    if (m_isArray) {

        // Get the value.