ChakraCore/lib/Parser/Hash.h

//-------------------------------------------------------------------------------------------------------
// Copyright (C) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.
//-------------------------------------------------------------------------------------------------------
#pragma once

// StaticSym contains a string literal at the end (flexible array) and is
// meant to be initialized statically. However, flexible array initialization
// is not allowed in standard C++. We declare each StaticSym with length
// instead and cast to common StaticSymLen<0>* (StaticSym*) to access.
template <uint32 N>
struct StaticSymLen
{
    uint32 luHash;
    uint32 cch;
    OLECHAR sz[N];
};

typedef StaticSymLen<0> StaticSym;

/***************************************************************************
Hashing functions. Definitions in core\hashfunc.cpp.
***************************************************************************/
ULONG CaseSensitiveComputeHash(LPCOLESTR prgch, LPCOLESTR end);
ULONG CaseSensitiveComputeHash(LPCUTF8 prgch, LPCUTF8 end);
ULONG CaseInsensitiveComputeHash(LPCOLESTR posz);

enum
{
    fidNil          = 0x0000,
    fidKwdRsvd      = 0x0001,     // the keyword is a reserved word
    fidKwdFutRsvd   = 0x0002,     // a future reserved word, but only in strict mode

    fidModuleExport = 0x8000    // name is module export
};

struct BlockIdsStack
{
    int id;
    BlockIdsStack *prev;
};

class Span
{
    charcount_t m_ichMin;
    charcount_t m_ichLim;

public:
    Span(): m_ichMin((charcount_t)-1), m_ichLim((charcount_t)-1) { }
    Span(charcount_t ichMin, charcount_t ichLim): m_ichMin(ichMin), m_ichLim(ichLim) { }

    charcount_t GetIchMin() { return m_ichMin; }
    charcount_t GetIchLim() { Assert(m_ichMin != (charcount_t)-1); return m_ichLim; }
    void Set(charcount_t ichMin, charcount_t ichLim)
    {
        m_ichMin = ichMin;
        m_ichLim = ichLim;
    }

    operator bool() { return m_ichMin != -1; }
};

struct PidRefStack
{
    PidRefStack() : isAsg(false), isDynamic(false), id(0), funcId(0), sym(nullptr), prev(nullptr), isEscape(false), isModuleExport(false), isFuncAssignment(false), isUsedInLdElem(false) {}
    PidRefStack(int id, Js::LocalFunctionId funcId) : isAsg(false), isDynamic(false), id(id), funcId(funcId), sym(nullptr), prev(nullptr), isEscape(false), isModuleExport(false), isFuncAssignment(false), isUsedInLdElem(false) {}

    int GetScopeId() const    { return id; }
    Js::LocalFunctionId GetFuncScopeId() const { return funcId; }
    Symbol *GetSym() const    { return sym; }
    void SetSym(Symbol *sym)  { this->sym = sym; }
    bool IsAssignment() const { return isAsg; }
    bool IsFuncAssignment() const { return isFuncAssignment; }
    bool IsEscape() const { return isEscape; }
    void SetIsEscape(bool is) { isEscape = is; }
    bool IsDynamicBinding() const { return isDynamic; }
    void SetDynamicBinding()  { isDynamic = true; }
    bool IsUsedInLdElem() const { return isUsedInLdElem; }
    void SetIsUsedInLdElem(bool is) { isUsedInLdElem = is; }

    Symbol **GetSymRef()
    {
        return &sym;
    }

    bool           isAsg;
    bool           isDynamic;
    bool           isModuleExport;
    bool           isEscape;
    bool           isFuncAssignment;
    bool           isUsedInLdElem;
    int            id;
    Js::LocalFunctionId funcId;
    Symbol        *sym;
    PidRefStack   *prev;
};

enum AssignmentState : byte {
    NotAssigned,
    AssignedOnce,
    AssignedMultipleTimes
};

struct Ident
{
    friend class HashTbl;

private:
    Ident * m_pidNext;   // next identifier in this hash bucket
    PidRefStack *m_pidRefStack;
    ushort m_tk;         // token# if identifier is a keyword
    ushort m_grfid;      // see fidXXX above
    uint32 m_luHash;      // hash value

    uint32 m_cch;                   // length of the identifier spelling
    Js::PropertyId m_propertyId;

    AssignmentState assignmentState;
    bool isUsedInLdElem;

    OLECHAR m_sz[]; // the spelling follows (null terminated)

    void SetTk(tokens tk, ushort grfid);
public:
    LPCOLESTR Psz(void)
    { return m_sz; }
    uint32 Cch(void)
    { return m_cch; }
    tokens Tk(bool isStrictMode);
    uint32 Hash(void)
    { return m_luHash; }

    PidRefStack *GetTopRef() const
    {
        return m_pidRefStack;
    }

    PidRefStack *GetTopRef(uint maxBlockId) const
    {
        PidRefStack *ref;
        for (ref = m_pidRefStack; ref && (uint)ref->id > maxBlockId; ref = ref->prev)
        {
            ; // nothing
        }
        return ref;
    }

    void SetTopRef(PidRefStack *ref)
    {
        m_pidRefStack = ref;
    }

    void PromoteAssignmentState()
    {
        if (assignmentState == NotAssigned)
        {
            assignmentState = AssignedOnce;
        }
        else if (assignmentState == AssignedOnce)
        {
            assignmentState = AssignedMultipleTimes;
        }
    }

    bool IsUsedInLdElem() const
    {
        return this->isUsedInLdElem;
    }

    void SetIsUsedInLdElem(bool is)
    {
        this->isUsedInLdElem = is;
    }

    static void TrySetIsUsedInLdElem(ParseNode * pnode);

    bool IsSingleAssignment()
    {
        return assignmentState == AssignedOnce;
    }

    PidRefStack *GetPidRefForScopeId(int scopeId)
    {
        PidRefStack *ref;
        for (ref = m_pidRefStack; ref; ref = ref->prev)
        {
            int refId = ref->GetScopeId();
            if (refId == scopeId)
            {
                return ref;
            }
            if (refId < scopeId)
            {
                break;
            }
        }
        return nullptr;
    }

    void PushPidRef(int blockId, Js::LocalFunctionId funcId, PidRefStack *newRef)
    {
        AssertMsg(blockId >= 0, "Block Id's should be greater than 0");
        newRef->id = blockId;
        newRef->funcId = funcId;
        newRef->prev = m_pidRefStack;
        m_pidRefStack = newRef;
    }

    PidRefStack * RemovePrevPidRef(PidRefStack *ref)
    {
        PidRefStack *prevRef;
        if (ref == nullptr)
        {
            prevRef = m_pidRefStack;
            Assert(prevRef);
            m_pidRefStack = prevRef->prev;
        }
        else
        {
            prevRef = ref->prev;
            Assert(prevRef);
            ref->prev = prevRef->prev;
        }
        return prevRef;
    }

    PidRefStack * FindOrAddPidRef(ArenaAllocator *alloc, int scopeId, Js::LocalFunctionId funcId)
    {
        // If the stack is empty, or we are pushing to the innermost scope already,
        // we can go ahead and push a new PidRef on the stack.
        if (m_pidRefStack == nullptr)
        {
            PidRefStack *newRef = Anew(alloc, PidRefStack, scopeId, funcId);
            if (newRef == nullptr)
            {
                return nullptr;
            }
            newRef->prev = m_pidRefStack;
            m_pidRefStack = newRef;
            return newRef;
        }

        // Search for the corresponding PidRef, or the position to insert the new PidRef.
        PidRefStack *ref = m_pidRefStack;
        PidRefStack *prevRef = nullptr;
        while (1)
        {
            // We may already have a ref for this scopeId.
            if (ref->id == scopeId)
            {
                return ref;
            }

            if (ref->prev == nullptr || ref->id  < scopeId)
            {
                // No existing PidRef for this scopeId, so create and insert one at this position.
                PidRefStack *newRef = Anew(alloc, PidRefStack, scopeId, funcId);
                if (newRef == nullptr)
                {
                    return nullptr;
                }

                if (ref->id < scopeId)
                {
                    if (prevRef != nullptr)
                    {
                        // Param scope has a reference to the same pid as the one we are inserting into the body.
                        // There is a another reference (prevRef), probably from an inner block in the body.
                        // So we should insert the new reference between them.
                        newRef->prev = prevRef->prev;
                        prevRef->prev = newRef;
                    }
                    else
                    {
                        // When we have code like below, prevRef will be null,
                        // function (a = x) { var x = 1; }
                        newRef->prev = m_pidRefStack;
                        m_pidRefStack = newRef;
                    }
                }
                else
                {
                    newRef->prev = ref->prev;
                    ref->prev = newRef;
                }
                return newRef;
            }

            prevRef = ref;
            ref = ref->prev;
        }
    }

    Js::PropertyId GetPropertyId() const { return m_propertyId; }
    void SetPropertyId(Js::PropertyId id) { m_propertyId = id; }

    void SetIsModuleExport() { m_grfid |= fidModuleExport; }
    BOOL GetIsModuleExport() const { return m_grfid & fidModuleExport; }

    static tokens TkFromNameLen(uint32 luHash, _In_reads_(cch) LPCOLESTR prgch, uint32 cch, bool isStrictMode, ushort * pgrfid, ushort * ptk);

#if DBG
    static tokens TkFromNameLen(_In_reads_(cch) LPCOLESTR prgch, uint32 cch, bool isStrictMode);
#endif
};


/*****************************************************************************/

class HashTbl
{
public:
    HashTbl(uint cidHash = DEFAULT_HASH_TABLE_SIZE)
    {
        AssertCanHandleOutOfMemory();
        m_prgpidName = nullptr;
        memset(&m_rpid, 0, sizeof(m_rpid));
        if (!Init(cidHash))
        {
            Js::Throw::OutOfMemory();
        }
    }
    ~HashTbl(void) {}

    BOOL TokIsBinop(tokens tk, int *popl, OpCode *pnop)
    {
        const KWD *pkwd = KwdOfTok(tk);

        if (nullptr == pkwd)
            return FALSE;
        *popl = pkwd->prec2;
        *pnop = pkwd->nop2;
        return TRUE;
    }

    BOOL TokIsUnop(tokens tk, int *popl, OpCode *pnop)
    {
        const KWD *pkwd = KwdOfTok(tk);

        if (nullptr == pkwd)
            return FALSE;
        *popl = pkwd->prec1;
        *pnop = pkwd->nop1;
        return TRUE;
    }

    IdentPtr PidFromTk(tokens tk);
    IdentPtr PidHashName(LPCOLESTR psz)
    {
        size_t csz = wcslen(psz);
        Assert(csz <= ULONG_MAX);
        return PidHashNameLen(psz, static_cast<uint32>(csz));
    }

    template <typename CharType>
    IdentPtr PidHashNameLen(CharType const * psz, CharType const * end, uint32 cch);
    template <typename CharType>
    IdentPtr PidHashNameLen(CharType const * psz, uint32 cch);
    template <typename CharType>
    IdentPtr PidHashNameLenWithHash(_In_reads_(cch) CharType const * psz, CharType const * end, int32 cch, uint32 luHash);


    template <typename CharType>
    inline IdentPtr FindExistingPid(
        CharType const * prgch,
        CharType const * end,
        int32 cch,
        uint32 luHash,
        IdentPtr **pppInsert,
        int32 *pBucketCount
#if PROFILE_DICTIONARY
        , int& depth
#endif
        );

    NoReleaseAllocator* GetAllocator() {return &m_noReleaseAllocator;}

    bool Contains(_In_reads_(cch) LPCOLESTR prgch, int32 cch);

    template<typename Fn>
    void VisitPids(Fn fn)
    {
        for (uint i = 0; i <= m_luMask; i++)
        {
            for (IdentPtr pid = m_prgpidName[i]; pid; pid = pid->m_pidNext)
            {
                fn(pid);
            }
        }
    }

private:
    static const uint DEFAULT_HASH_TABLE_SIZE = 256;

    NoReleaseAllocator m_noReleaseAllocator;            // to allocate identifiers
    Ident ** m_prgpidName;        // hash table for names

    uint32 m_luMask;                // hash mask
    uint32 m_luCount;              // count of the number of entires in the hash table    
    IdentPtr m_rpid[tkLimKwd];

    // Called to grow the number of buckets in the table to reduce the table density.
    void Grow();

    // Automatically grow the table if a bucket's length grows beyond BucketLengthLimit and the table is densely populated.
    static const uint BucketLengthLimit = 5;

    // When growing the bucket size we'll grow by GrowFactor. GrowFactor MUST be a power of 2.
    static const uint GrowFactor = 4;

#if DEBUG
    uint CountAndVerifyItems(IdentPtr *buckets, uint bucketCount, uint mask);
#endif

    static bool CharsAreEqual(__in_z LPCOLESTR psz1, __in_ecount(psz2end - psz2) LPCOLESTR psz2, LPCOLESTR psz2end)
    {
        return memcmp(psz1, psz2, (psz2end - psz2) * sizeof(OLECHAR)) == 0;
    }
    static bool CharsAreEqual(__in_z LPCOLESTR psz1, LPCUTF8 psz2, LPCUTF8 psz2end)
    {
        return utf8::CharsAreEqual(psz1, psz2, psz2end, utf8::doAllowThreeByteSurrogates);
    }
    static bool CharsAreEqual(__in_z LPCOLESTR psz1, __in_ecount(psz2end - psz2) char const * psz2, char const * psz2end)
    {
        while (psz2 < psz2end)
        {
            if (*psz1++ != *psz2++)
            {
                return false;
            }
        }
        return true;
    }
    static void CopyString(__in_ecount((psz2end - psz2) + 1) LPOLESTR psz1, __in_ecount(psz2end - psz2) LPCOLESTR psz2, LPCOLESTR psz2end)
    {
        size_t cch = psz2end - psz2;
        js_memcpy_s(psz1, cch * sizeof(OLECHAR), psz2, cch * sizeof(OLECHAR));
        psz1[cch] = 0;
    }
    static void CopyString(LPOLESTR psz1, LPCUTF8 psz2, LPCUTF8 psz2end)
    {
        utf8::DecodeUnitsIntoAndNullTerminate(psz1, psz2, psz2end);
    }
    static void CopyString(LPOLESTR psz1, char const * psz2, char const * psz2end)
    {
        while (psz2 < psz2end)
        {
            *(psz1++) = *psz2++;
        }
        *psz1 = 0;
    }

    // note: on failure this may throw or return FALSE, depending on
    // where the failure occurred.
    BOOL Init(uint cidHash);

    /*************************************************************************/
    /* The following members are related to the keyword descriptor tables    */
    /*************************************************************************/
    struct KWD
    {
        OpCode nop2;
        byte prec2;
        OpCode nop1;
        byte prec1;
    };
    struct ReservedWordInfo
    {
        StaticSym const * sym;
        ushort grfid;
    };
    static const ReservedWordInfo s_reservedWordInfo[tkID];
    static const KWD g_mptkkwd[tkLimKwd];
    static const KWD * KwdOfTok(tokens tk)
    { return (unsigned int)tk < tkLimKwd ? g_mptkkwd + tk : nullptr; }

    static __declspec(noreturn) void OutOfMemory();
#if PROFILE_DICTIONARY
    DictionaryStats *stats;
#endif
};