/*
 * Copyright (C) 2016-2019 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.
 */

#pragma once

#include "JSGlobalObjectInlines.h"
#include "JSString.h"
#include "KeyAtomStringCacheInlines.h"

namespace JSC {

ALWAYS_INLINE void JSString::destroy(JSCell* cell)
{
    auto* string = static_cast<JSString*>(cell);
    string->valueInternal().~String();
}

ALWAYS_INLINE void JSRopeString::destroy(JSCell* cell)
{
    auto* string = static_cast<JSRopeString*>(cell);
    if (string->isRope())
        return;
    string->valueInternal().~String();
}

bool JSString::equal(JSGlobalObject* globalObject, JSString* other) const
{
    if (isRope() || other->isRope())
        return equalSlowCase(globalObject, other);
    return WTF::equal(*valueInternal().impl(), *other->valueInternal().impl());
}

ALWAYS_INLINE bool JSString::equalInline(JSGlobalObject* globalObject, JSString* other) const
{
    VM& vm = globalObject->vm();
    auto scope = DECLARE_THROW_SCOPE(vm);

    unsigned length = this->length();
    if (length != other->length())
        return false;

    auto str1 = unsafeView(globalObject);
    RETURN_IF_EXCEPTION(scope, false);
    auto str2 = other->unsafeView(globalObject);
    RETURN_IF_EXCEPTION(scope, false);

    ensureStillAliveHere(this);
    ensureStillAliveHere(other);
    return WTF::equal(str1, str2, length);
}

template<typename StringType>
inline JSValue jsMakeNontrivialString(VM& vm, StringType&& string)
{
    return jsNontrivialString(vm, std::forward<StringType>(string));
}

template<typename StringType, typename... StringTypes>
inline JSValue jsMakeNontrivialString(JSGlobalObject* globalObject, StringType&& string, StringTypes&&... strings)
{
    VM& vm = getVM(globalObject);
    auto scope = DECLARE_THROW_SCOPE(vm);
    String result = tryMakeString(std::forward<StringType>(string), std::forward<StringTypes>(strings)...);
    if (UNLIKELY(!result))
        return throwOutOfMemoryError(globalObject, scope);
    ASSERT(result.length() <= JSString::MaxLength);
    return jsNontrivialString(vm, WTFMove(result));
}

template <typename CharacterType>
inline JSString* repeatCharacter(JSGlobalObject* globalObject, CharacterType character, unsigned repeatCount)
{
    VM& vm = globalObject->vm();
    auto scope = DECLARE_THROW_SCOPE(vm);

    CharacterType* buffer = nullptr;
    auto impl = StringImpl::tryCreateUninitialized(repeatCount, buffer);
    if (!impl) {
        throwOutOfMemoryError(globalObject, scope);
        return nullptr;
    }

    std::fill_n(buffer, repeatCount, character);

    RELEASE_AND_RETURN(scope, jsString(vm, impl.releaseNonNull()));
}

inline void JSRopeString::convertToNonRope(String&& string) const
{
    // Concurrent compiler threads can access String held by JSString. So we always emit
    // store-store barrier here to ensure concurrent compiler threads see initialized String.
    ASSERT(JSString::isRope());
    WTF::storeStoreFence();
    new (&uninitializedValueInternal()) String(WTFMove(string));
    static_assert(sizeof(String) == sizeof(RefPtr<StringImpl>), "JSString's String initialization must be done in one pointer move.");
    // We do not clear the trailing fibers and length information (fiber1 and fiber2) because we could be reading the length concurrently.
    ASSERT(!JSString::isRope());
}

// Overview: These functions convert a JSString from holding a string in rope form
// down to a simple String representation. It does so by building up the string
// backwards, since we want to avoid recursion, we expect that the tree structure
// representing the rope is likely imbalanced with more nodes down the left side
// (since appending to the string is likely more common) - and as such resolving
// in this fashion should minimize work queue size.  (If we built the queue forwards
// we would likely have to place all of the constituent StringImpls into the
// Vector before performing any concatenation, but by working backwards we likely
// only fill the queue with the number of substrings at any given level in a
// rope-of-ropes.)
template<typename CharacterType>
void JSRopeString::resolveToBufferSlow(JSString* fiber0, JSString* fiber1, JSString* fiber2, CharacterType* buffer, unsigned length, uint8_t*)
{
    // Keep in mind that resolveToBufferSlow signature must be the same to resolveToBuffer to encourage tail-calls by clang, that's the reason why
    // it takes the last stackLimit parameter still while it is not used here.

    CharacterType* position = buffer + length; // We will be working backwards over the rope.
    Vector<JSString*, 32, UnsafeVectorOverflow> workQueue; // These strings are kept alive by the parent rope, so using a Vector is OK.

    workQueue.append(fiber0);
    if (fiber1) {
        workQueue.append(fiber1);
        if (fiber2)
            workQueue.append(fiber2);
    }

    do {
        JSString* currentFiber = workQueue.takeLast();

        if (currentFiber->isRope()) {
            JSRopeString* currentFiberAsRope = static_cast<JSRopeString*>(currentFiber);
            if (currentFiberAsRope->isSubstring()) {
                ASSERT(!currentFiberAsRope->substringBase()->isRope());
                StringView view = *currentFiberAsRope->substringBase()->valueInternal().impl();
                unsigned offset = currentFiberAsRope->substringOffset();
                unsigned length = currentFiberAsRope->length();
                position -= length;
                view.substring(offset, length).getCharacters(position);
                continue;
            }
            for (size_t i = 0; i < JSRopeString::s_maxInternalRopeLength && currentFiberAsRope->fiber(i); ++i)
                workQueue.append(currentFiberAsRope->fiber(i));
            continue;
        }

        StringView view = *currentFiber->valueInternal().impl();
        position -= view.length();
        view.getCharacters(position);
    } while (!workQueue.isEmpty());

    ASSERT(buffer == position);
}

template<typename CharacterType>
inline void JSRopeString::resolveToBuffer(JSString* fiber0, JSString* fiber1, JSString* fiber2, CharacterType* buffer, unsigned length, uint8_t* stackLimit)
{
    ASSERT(fiber0);

    // We must ensure that all JSRopeString::resolveToBufferSlow and JSRopeString::resolveToBuffer calls must be done directly from this function, and it has
    // exact same signature to JSRopeString::resolveToBuffer, which will be esured by clang via MUST_TAIL_CALL attribute.
    // This allows clang to make these calls tail-calls, constructing significantly efficient rope resolution here.
    static_assert(3 == JSRopeString::s_maxInternalRopeLength);

    if (UNLIKELY(bitwise_cast<uint8_t*>(currentStackPointer()) < stackLimit))
        MUST_TAIL_CALL return JSRopeString::resolveToBufferSlow(fiber0, fiber1, fiber2, buffer, length, stackLimit);

    // 3 fibers.
    if (fiber2) {
        if (fiber0->isRope() || fiber1->isRope() || fiber2->isRope())
            MUST_TAIL_CALL return JSRopeString::resolveToBufferSlow(fiber0, fiber1, fiber2, buffer, length, stackLimit);

        StringView view0 = fiber0->valueInternal().impl();
        view0.getCharacters(buffer);
        StringView view1 = fiber1->valueInternal().impl();
        view1.getCharacters(buffer + view0.length());
        StringView view2 = fiber2->valueInternal().impl();
        view2.getCharacters(buffer + view0.length() + view1.length());
        return;
    }

    // 2 fibers.
    if (LIKELY(fiber1)) {
        if (fiber0->isRope()) {
            if (fiber1->isRope())
                MUST_TAIL_CALL return JSRopeString::resolveToBufferSlow(fiber0, fiber1, fiber2, buffer, length, stackLimit);

            auto* rope0 = static_cast<const JSRopeString*>(fiber0);
            {
                StringView view1 = fiber1->valueInternal().impl();
                view1.getCharacters(buffer + rope0->length());
            }
            if (rope0->isSubstring()) {
                StringView view0 = *rope0->substringBase()->valueInternal().impl();
                unsigned offset = rope0->substringOffset();
                unsigned length = rope0->length();
                view0.substring(offset, length).getCharacters(buffer);
                return;
            }
            MUST_TAIL_CALL return resolveToBuffer(rope0->fiber0(), rope0->fiber1(), rope0->fiber2(), buffer, rope0->length(), stackLimit);
        }

        if (fiber1->isRope()) {
            auto* rope1 = static_cast<const JSRopeString*>(fiber1);
            {
                StringView view0 = fiber0->valueInternal().impl();
                view0.getCharacters(buffer);
                buffer += view0.length();
            }
            if (rope1->isSubstring()) {
                StringView view1 = *rope1->substringBase()->valueInternal().impl();
                unsigned offset = rope1->substringOffset();
                unsigned length = rope1->length();
                view1.substring(offset, length).getCharacters(buffer);
                return;
            }
            MUST_TAIL_CALL return resolveToBuffer(rope1->fiber0(), rope1->fiber1(), rope1->fiber2(), buffer, rope1->length(), stackLimit);
        }

        StringView view0 = fiber0->valueInternal().impl();
        view0.getCharacters(buffer);
        StringView view1 = fiber1->valueInternal().impl();
        view1.getCharacters(buffer + view0.length());
        return;
    }

    // 1 fiber.
    if (!fiber0->isRope()) {
        StringView view0 = fiber0->valueInternal().impl();
        view0.getCharacters(buffer);
        return;
    }

    auto* rope0 = static_cast<const JSRopeString*>(fiber0);
    if (rope0->isSubstring()) {
        StringView view0 = *rope0->substringBase()->valueInternal().impl();
        unsigned offset = rope0->substringOffset();
        unsigned length = rope0->length();
        view0.substring(offset, length).getCharacters(buffer);
        return;
    }
    MUST_TAIL_CALL return resolveToBuffer(rope0->fiber0(), rope0->fiber1(), rope0->fiber2(), buffer, rope0->length(), stackLimit);
}

inline JSString* jsAtomString(JSGlobalObject* globalObject, VM& vm, JSString* string)
{
    auto scope = DECLARE_THROW_SCOPE(vm);

    unsigned length = string->length();
    if (length > KeyAtomStringCache::maxStringLengthForCache) {
        scope.release();
        string->toIdentifier(globalObject);
        return string;
    }

    if (!string->isRope()) {
        auto createFromNonRope = [&](VM& vm, auto&) {
            AtomString atom(string->valueInternal());
            if (!string->valueInternal().impl()->isAtom())
                string->swapToAtomString(vm, RefPtr { atom.impl() });
            return string;
        };

        if (string->valueInternal().is8Bit()) {
            WTF::HashTranslatorCharBuffer<LChar> buffer { string->valueInternal().characters8(), length, string->valueInternal().hash() };
            return vm.keyAtomStringCache.make(vm, buffer, createFromNonRope);
        }

        WTF::HashTranslatorCharBuffer<UChar> buffer { string->valueInternal().characters16(), length, string->valueInternal().hash() };
        return vm.keyAtomStringCache.make(vm, buffer, createFromNonRope);
    }

    JSRopeString* ropeString = jsCast<JSRopeString*>(string);

    auto createFromRope = [&](VM& vm, auto& buffer) {
        auto impl = AtomStringImpl::add(buffer);
        if (impl->hasOneRef())
            vm.heap.reportExtraMemoryAllocated(ropeString, impl->cost());
        ropeString->convertToNonRope(String { WTFMove(impl) });
        return ropeString;
    };

    AtomString atomString;
    if (!ropeString->isSubstring()) {
        uint8_t* stackLimit = bitwise_cast<uint8_t*>(vm.softStackLimit());
        JSString* fiber0 = ropeString->fiber0();
        JSString* fiber1 = ropeString->fiber1();
        JSString* fiber2 = ropeString->fiber2();
        if (ropeString->is8Bit()) {
            LChar characters[KeyAtomStringCache::maxStringLengthForCache];
            JSRopeString::resolveToBuffer(fiber0, fiber1, fiber2, characters, length, stackLimit);
            WTF::HashTranslatorCharBuffer<LChar> buffer { characters, length };
            return vm.keyAtomStringCache.make(vm, buffer, createFromRope);
        }
        UChar characters[KeyAtomStringCache::maxStringLengthForCache];
        JSRopeString::resolveToBuffer(fiber0, fiber1, fiber2, characters, length, stackLimit);
        WTF::HashTranslatorCharBuffer<UChar> buffer { characters, length };
        return vm.keyAtomStringCache.make(vm, buffer, createFromRope);
    }

    auto view = StringView { ropeString->substringBase()->valueInternal() }.substring(ropeString->substringOffset(), length);
    if (view.is8Bit()) {
        WTF::HashTranslatorCharBuffer<LChar> buffer { view.characters8(), length };
        return vm.keyAtomStringCache.make(vm, buffer, createFromRope);
    }
    WTF::HashTranslatorCharBuffer<UChar> buffer { view.characters16(), length };
    return vm.keyAtomStringCache.make(vm, buffer, createFromRope);
}

inline JSString* jsAtomString(JSGlobalObject* globalObject, VM& vm, JSString* s1, JSString* s2)
{
    auto scope = DECLARE_THROW_SCOPE(vm);

    unsigned length1 = s1->length();
    if (!length1)
        RELEASE_AND_RETURN(scope, jsAtomString(globalObject, vm, s2));
    unsigned length2 = s2->length();
    if (!length2)
        RELEASE_AND_RETURN(scope, jsAtomString(globalObject, vm, s1));
    static_assert(JSString::MaxLength == std::numeric_limits<int32_t>::max());
    if (sumOverflows<int32_t>(length1, length2)) {
        throwOutOfMemoryError(globalObject, scope);
        return nullptr;
    }

    unsigned length = length1 + length2;
    if (length > KeyAtomStringCache::maxStringLengthForCache) {
        auto* ropeString = jsString(globalObject, s1, s2);
        RETURN_IF_EXCEPTION(scope, nullptr);
        ropeString->toIdentifier(globalObject);
        RETURN_IF_EXCEPTION(scope, nullptr);
        return ropeString;
    }

    auto createFromFibers = [&](VM& vm, auto& buffer) {
        return jsString(vm, String { AtomStringImpl::add(buffer) });
    };

    // This is quite unfortunate, but duplicating this part here is the key of performance improvement in JetStream2/WSL,
    // which stress this jsAtomString significantly.
    auto resolveWith2Fibers = [&](JSString* fiber0, JSString* fiber1, auto* buffer, unsigned length) {
        uint8_t* stackLimit = bitwise_cast<uint8_t*>(vm.softStackLimit());
        if (fiber0->isRope()) {
            if (fiber1->isRope())
                return JSRopeString::resolveToBufferSlow(fiber0, fiber1, nullptr, buffer, length, stackLimit);

            auto* rope0 = static_cast<const JSRopeString*>(fiber0);
            StringView view1 = fiber1->valueInternal().impl();
            view1.getCharacters(buffer + rope0->length());
            if (rope0->isSubstring()) {
                StringView view0 = *rope0->substringBase()->valueInternal().impl();
                unsigned offset = rope0->substringOffset();
                unsigned length = rope0->length();
                view0.substring(offset, length).getCharacters(buffer);
                return;
            }
            return JSRopeString::resolveToBuffer(rope0->fiber0(), rope0->fiber1(), rope0->fiber2(), buffer, rope0->length(), stackLimit);
        }

        if (fiber1->isRope()) {
            StringView view0 = fiber0->valueInternal().impl();
            view0.getCharacters(buffer);
            auto* rope1 = static_cast<const JSRopeString*>(fiber1);
            if (rope1->isSubstring()) {
                StringView view1 = *rope1->substringBase()->valueInternal().impl();
                unsigned offset = rope1->substringOffset();
                unsigned length = rope1->length();
                view1.substring(offset, length).getCharacters(buffer + view0.length());
                return;
            }
            return JSRopeString::resolveToBuffer(rope1->fiber0(), rope1->fiber1(), rope1->fiber2(), buffer + view0.length(), rope1->length(), stackLimit);
        }

        StringView view0 = fiber0->valueInternal().impl();
        view0.getCharacters(buffer);
        StringView view1 = fiber1->valueInternal().impl();
        view1.getCharacters(buffer + view0.length());
    };

    if (s1->is8Bit() && s2->is8Bit()) {
        LChar characters[KeyAtomStringCache::maxStringLengthForCache];
        resolveWith2Fibers(s1, s2, characters, length);
        WTF::HashTranslatorCharBuffer<LChar> buffer { characters, length };
        return vm.keyAtomStringCache.make(vm, buffer, createFromFibers);
    }
    UChar characters[KeyAtomStringCache::maxStringLengthForCache];
    resolveWith2Fibers(s1, s2, characters, length);
    WTF::HashTranslatorCharBuffer<UChar> buffer { characters, length };
    return vm.keyAtomStringCache.make(vm, buffer, createFromFibers);
}

inline JSString* jsAtomString(JSGlobalObject* globalObject, VM& vm, JSString* s1, JSString* s2, JSString* s3)
{
    auto scope = DECLARE_THROW_SCOPE(vm);

    unsigned length1 = s1->length();
    if (!length1)
        RELEASE_AND_RETURN(scope, jsAtomString(globalObject, vm, s2, s3));

    unsigned length2 = s2->length();
    if (!length2)
        RELEASE_AND_RETURN(scope, jsAtomString(globalObject, vm, s1, s3));

    unsigned length3 = s3->length();
    if (!length3)
        RELEASE_AND_RETURN(scope, jsAtomString(globalObject, vm, s1, s2));

    static_assert(JSString::MaxLength == std::numeric_limits<int32_t>::max());
    if (sumOverflows<int32_t>(length1, length2, length3)) {
        throwOutOfMemoryError(globalObject, scope);
        return nullptr;
    }

    unsigned length = length1 + length2 + length3;
    if (length > KeyAtomStringCache::maxStringLengthForCache) {
        auto* ropeString = jsString(globalObject, s1, s2, s3);
        RETURN_IF_EXCEPTION(scope, nullptr);
        ropeString->toIdentifier(globalObject);
        RETURN_IF_EXCEPTION(scope, nullptr);
        return ropeString;
    }

    auto createFromFibers = [&](VM& vm, auto& buffer) {
        return jsString(vm, String { AtomStringImpl::add(buffer) });
    };

    auto resolveWith3Fibers = [&](JSString* fiber0, JSString* fiber1, JSString* fiber2, auto* buffer, unsigned length) {
        if (fiber0->isRope() || fiber1->isRope() || fiber2->isRope())
            return JSRopeString::resolveToBufferSlow(fiber0, fiber1, fiber2, buffer, length, bitwise_cast<uint8_t*>(vm.softStackLimit()));

        StringView view0 = fiber0->valueInternal().impl();
        view0.getCharacters(buffer);
        StringView view1 = fiber1->valueInternal().impl();
        view1.getCharacters(buffer + view0.length());
        StringView view2 = fiber2->valueInternal().impl();
        view2.getCharacters(buffer + view0.length() + view1.length());
    };

    if (s1->is8Bit() && s2->is8Bit() && s3->is8Bit()) {
        LChar characters[KeyAtomStringCache::maxStringLengthForCache];
        resolveWith3Fibers(s1, s2, s3, characters, length);
        WTF::HashTranslatorCharBuffer<LChar> buffer { characters, length };
        return vm.keyAtomStringCache.make(vm, buffer, createFromFibers);
    }
    UChar characters[KeyAtomStringCache::maxStringLengthForCache];
    resolveWith3Fibers(s1, s2, s3, characters, length);
    WTF::HashTranslatorCharBuffer<UChar> buffer { characters, length };
    return vm.keyAtomStringCache.make(vm, buffer, createFromFibers);
}

inline JSString* jsSubstringOfResolved(VM& vm, GCDeferralContext* deferralContext, JSString* s, unsigned offset, unsigned length)
{
    ASSERT(offset <= s->length());
    ASSERT(length <= s->length());
    ASSERT(offset + length <= s->length());
    ASSERT(!s->isRope());
    if (!length)
        return vm.smallStrings.emptyString();
    if (!offset && length == s->length())
        return s;
    if (length == 1) {
        auto& base = s->valueInternal();
        if (auto c = base.characterAt(offset); c <= maxSingleCharacterString)
            return vm.smallStrings.singleCharacterString(c);
    } else if (length == 2) {
        auto& base = s->valueInternal();
        UChar first = base.characterAt(offset);
        UChar second = base.characterAt(offset + 1);
        if ((first | second) < 0x80) {
            auto createFromSubstring = [&](VM& vm, auto& buffer) {
                auto impl = AtomStringImpl::add(buffer);
                return JSString::create(vm, deferralContext, impl.releaseNonNull());
            };
            LChar buf[] = { static_cast<LChar>(first), static_cast<LChar>(second) };
            WTF::HashTranslatorCharBuffer<LChar> buffer { buf, length };
            return vm.keyAtomStringCache.make(vm, buffer, createFromSubstring);
        }
    }
    return JSRopeString::createSubstringOfResolved(vm, deferralContext, s, offset, length);
}

} // namespace JSC
