/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef frontend_ParseMaps_h
#define frontend_ParseMaps_h

#include "mozilla/Attributes.h"
#include "mozilla/TypeTraits.h"

#include "ds/InlineMap.h"
#include "gc/Barrier.h"
#include "js/Vector.h"

class JSAtom;

typedef uintptr_t jsatomid;

namespace js {

class LifoAlloc;

namespace frontend {

class DefinitionSingle;
class DefinitionList;

typedef InlineMap<JSAtom*, jsatomid, 24> AtomIndexMap;
typedef InlineMap<JSAtom*, DefinitionSingle, 24> AtomDefnMap;
typedef InlineMap<JSAtom*, DefinitionList, 24> AtomDefnListMap;

/*
 * For all unmapped atoms recorded in al, add a mapping from the atom's index
 * to its address. map->length must already be set to the number of atoms in
 * the list and map->vector must point to pre-allocated memory.
 */
void
InitAtomMap(AtomIndexMap* indices, HeapPtrAtom* atoms);

/*
 * A pool that permits the reuse of the backing storage for the defn, index, or
 * defn-or-header (multi) maps.
 *
 * The pool owns all the maps that are given out, and is responsible for
 * relinquishing all resources when |purgeAll| is triggered.
 */
class ParseMapPool
{
    typedef Vector<void*, 32, SystemAllocPolicy> RecyclableMaps;

    RecyclableMaps      all;
    RecyclableMaps      recyclable;

    void checkInvariants();

    void recycle(void* map) {
        MOZ_ASSERT(map);
#ifdef DEBUG
        bool ok = false;
        /* Make sure the map is in |all| but not already in |recyclable|. */
        for (void** it = all.begin(); it != all.end(); ++it) {
            if (*it == map) {
                ok = true;
                break;
            }
        }
        MOZ_ASSERT(ok);
        for (void** it = recyclable.begin(); it != recyclable.end(); ++it)
            MOZ_ASSERT(*it != map);
#endif
        MOZ_ASSERT(recyclable.length() < all.length());
        recyclable.infallibleAppend(map); /* Reserved in allocateFresh. */
    }

    void* allocateFresh();
    void* allocate() {
        if (recyclable.empty())
            return allocateFresh();

        void* map = recyclable.popCopy();
        asAtomMap(map)->clear();
        return map;
    }

    /* Arbitrary atom map type, that has keys and values of the same kind. */
    typedef AtomIndexMap AtomMapT;

    static AtomMapT* asAtomMap(void* ptr) {
        return reinterpret_cast<AtomMapT*>(ptr);
    }

  public:
    ~ParseMapPool() {
        purgeAll();
    }

    void purgeAll();

    bool empty() const {
        return all.empty();
    }

    /* Fallibly aquire one of the supported map types from the pool. */
    template <typename T>
    T* acquire() {
        return reinterpret_cast<T*>(allocate());
    }

    /* Release one of the supported map types back to the pool. */

    void release(AtomIndexMap* map) {
        recycle((void*) map);
    }

    void release(AtomDefnMap* map) {
        recycle((void*) map);
    }

    void release(AtomDefnListMap* map) {
        recycle((void*) map);
    }
}; /* ParseMapPool */

/*
 * N.B. This is a POD-type so that it can be included in the ParseNode union.
 * If possible, use the corresponding |OwnedAtomThingMapPtr| variant.
 */
template <class Map>
struct AtomThingMapPtr
{
    Map* map_;

    void init() { clearMap(); }

    bool ensureMap(ExclusiveContext* cx);
    void releaseMap(ExclusiveContext* cx);

    bool hasMap() const { return map_; }
    Map* getMap() { return map_; }
    void setMap(Map* newMap) { MOZ_ASSERT(!map_); map_ = newMap; }
    void clearMap() { map_ = nullptr; }

    Map* operator->() { return map_; }
    const Map* operator->() const { return map_; }
    Map& operator*() const { return *map_; }
};

typedef AtomThingMapPtr<AtomIndexMap> AtomIndexMapPtr;

/*
 * Wrapper around an AtomThingMapPtr (or its derivatives) that automatically
 * releases a map on destruction, if one has been acquired.
 */
template <typename AtomThingMapPtrT>
class OwnedAtomThingMapPtr : public AtomThingMapPtrT
{
    ExclusiveContext* cx;

  public:
    explicit OwnedAtomThingMapPtr(ExclusiveContext* cx) : cx(cx) {
        AtomThingMapPtrT::init();
    }

    ~OwnedAtomThingMapPtr() {
        AtomThingMapPtrT::releaseMap(cx);
    }
};

typedef OwnedAtomThingMapPtr<AtomIndexMapPtr> OwnedAtomIndexMapPtr;

/*
 * DefinitionSingle and DefinitionList represent either a single definition
 * or a list of them. The representation of definitions varies between
 * parse handlers, being either a Definition* (FullParseHandler) or a
 * Definition::Kind (SyntaxParseHandler). Methods on the below classes are
 * templated to distinguish the kind of value wrapped by the class.
 */

/* Wrapper for a single definition. */
class DefinitionSingle
{
    uintptr_t bits;

  public:

    template <typename ParseHandler>
    static DefinitionSingle new_(typename ParseHandler::DefinitionNode defn)
    {
        DefinitionSingle res;
        res.bits = ParseHandler::definitionToBits(defn);
        return res;
    }

    template <typename ParseHandler>
    typename ParseHandler::DefinitionNode get() {
        return ParseHandler::definitionFromBits(bits);
    }
};

struct AtomDefnMapPtr : public AtomThingMapPtr<AtomDefnMap>
{
    template <typename ParseHandler>
    MOZ_ALWAYS_INLINE
    typename ParseHandler::DefinitionNode lookupDefn(JSAtom* atom) {
        AtomDefnMap::Ptr p = map_->lookup(atom);
        return p ? p.value().get<ParseHandler>() : ParseHandler::nullDefinition();
    }
};

typedef OwnedAtomThingMapPtr<AtomDefnMapPtr> OwnedAtomDefnMapPtr;

/*
 * A nonempty list containing one or more pointers to Definitions.
 *
 * By far the most common case is that the list contains exactly one
 * Definition, so the implementation is optimized for that case.
 *
 * Nodes for the linked list (if any) are allocated from the tempPool of a
 * context the caller passes into pushFront and pushBack. This means the
 * DefinitionList does not own the memory for the nodes: the JSContext does.
 * As a result, DefinitionList is a POD type; it can be safely and cheaply
 * copied.
 */
class DefinitionList
{
  public:
    class Range;

  private:
    friend class Range;

    /* A node in a linked list of Definitions. */
    struct Node
    {
        uintptr_t bits;
        Node* next;

        Node(uintptr_t bits, Node* next) : bits(bits), next(next) {}
    };

    union {
        uintptr_t bits;
        Node* head;
    } u;

    Node* firstNode() const {
        MOZ_ASSERT(isMultiple());
        return (Node*) (u.bits & ~0x1);
    }

    static Node*
    allocNode(ExclusiveContext* cx, LifoAlloc& alloc, uintptr_t bits, Node* tail);

  public:
    class Range
    {
        friend class DefinitionList;

        Node* node;
        uintptr_t bits;

        explicit Range(const DefinitionList& list) {
            if (list.isMultiple()) {
                node = list.firstNode();
                bits = node->bits;
            } else {
                node = nullptr;
                bits = list.u.bits;
            }
        }

      public:
        /* An empty Range. */
        Range() : node(nullptr), bits(0) {}

        void popFront() {
            MOZ_ASSERT(!empty());
            if (!node) {
                bits = 0;
                return;
            }
            node = node->next;
            bits = node ? node->bits : 0;
        }

        template <typename ParseHandler>
        typename ParseHandler::DefinitionNode front() {
            MOZ_ASSERT(!empty());
            return ParseHandler::definitionFromBits(bits);
        }

        bool empty() const {
            MOZ_ASSERT_IF(!bits, !node);
            return !bits;
        }
    };

    DefinitionList() {
        u.bits = 0;
    }

    explicit DefinitionList(uintptr_t bits) {
        u.bits = bits;
        MOZ_ASSERT(!isMultiple());
    }

    explicit DefinitionList(Node* node) {
        u.head = node;
        u.bits |= 0x1;
        MOZ_ASSERT(isMultiple());
    }

    bool isMultiple() const { return (u.bits & 0x1) != 0; }

    template <typename ParseHandler>
    typename ParseHandler::DefinitionNode front() {
        return ParseHandler::definitionFromBits(isMultiple() ? firstNode()->bits : u.bits);
    }

    /*
     * If there are multiple Definitions in this list, remove the first and
     * return true. Otherwise there is exactly one Definition in the list; do
     * nothing and return false.
     */
    bool popFront() {
        if (!isMultiple())
            return false;

        Node* node = firstNode();
        Node* next = node->next;
        if (next->next)
            *this = DefinitionList(next);
        else
            *this = DefinitionList(next->bits);
        return true;
    }

    /*
     * Add a definition to the front of this list.
     *
     * Return true on success. On OOM, report on cx and return false.
     */
    template <typename ParseHandler>
    bool pushFront(ExclusiveContext* cx, LifoAlloc& alloc,
                   typename ParseHandler::DefinitionNode defn) {
        Node* tail;
        if (isMultiple()) {
            tail = firstNode();
        } else {
            tail = allocNode(cx, alloc, u.bits, nullptr);
            if (!tail)
                return false;
        }

        Node* node = allocNode(cx, alloc, ParseHandler::definitionToBits(defn), tail);
        if (!node)
            return false;
        *this = DefinitionList(node);
        return true;
    }

    /* Overwrite the first Definition in the list. */
    template <typename ParseHandler>
        void setFront(typename ParseHandler::DefinitionNode defn) {
        if (isMultiple())
            firstNode()->bits = ParseHandler::definitionToBits(defn);
        else
            *this = DefinitionList(ParseHandler::definitionToBits(defn));
    }

    Range all() const { return Range(*this); }

#ifdef DEBUG
    void dump();
#endif
};

typedef AtomDefnMap::Range      AtomDefnRange;
typedef AtomDefnMap::AddPtr     AtomDefnAddPtr;
typedef AtomDefnMap::Ptr        AtomDefnPtr;
typedef AtomIndexMap::AddPtr    AtomIndexAddPtr;
typedef AtomIndexMap::Ptr       AtomIndexPtr;
typedef AtomDefnListMap::Ptr    AtomDefnListPtr;
typedef AtomDefnListMap::AddPtr AtomDefnListAddPtr;
typedef AtomDefnListMap::Range  AtomDefnListRange;

/*
 * AtomDecls is a map of atoms to (sequences of) Definitions. It is used by
 * ParseContext to store declarations. A declaration associates a name with a
 * Definition.
 *
 * Declarations with function scope (such as const, var, and function) are
 * unique in the sense that they override any previous declarations with the
 * same name. For such declarations, we only need to store a single Definition,
 * using the method addUnique.
 *
 * Declarations with block scope (such as let) are slightly more complex. They
 * override any previous declarations with the same name, but only do so for
 * the block they are associated with. This is known as shadowing. For such
 * definitions, we need to store a sequence of Definitions, including those
 * introduced by previous declarations (and which are now shadowed), using the
 * method addShadow. When we leave the block associated with the let, the method
 * remove is used to unshadow the declaration immediately preceding it.
 */
template <typename ParseHandler>
class AtomDecls
{
    typedef typename ParseHandler::DefinitionNode DefinitionNode;

    /* AtomDeclsIter needs to get at the DefnListMap directly. */
    friend class AtomDeclsIter;

    ExclusiveContext* cx;
    LifoAlloc& alloc;
    AtomDefnListMap* map;

    AtomDecls(const AtomDecls& other) = delete;
    void operator=(const AtomDecls& other) = delete;

  public:
    explicit AtomDecls(ExclusiveContext* cx, LifoAlloc& alloc) : cx(cx),
                                                                 alloc(alloc),
                                                                 map(nullptr) {}

    ~AtomDecls();

    bool init();

    void clear() {
        map->clear();
    }

    /* Return the definition at the head of the chain for |atom|. */
    DefinitionNode lookupFirst(JSAtom* atom) const {
        MOZ_ASSERT(map);
        AtomDefnListPtr p = map->lookup(atom);
        if (!p)
            return ParseHandler::nullDefinition();
        return p.value().front<ParseHandler>();
    }

    /* Return the definition at the tail of the chain for |atom|. */
    DefinitionNode lookupLast(JSAtom* atom) const {
        MOZ_ASSERT(map);
        DefinitionList::Range range = lookupMulti(atom);
        DefinitionNode dn = ParseHandler::nullDefinition();
        while (!range.empty()) {
            dn = range.front<ParseHandler>();
            range.popFront();
        }
        return dn;
    }

    /* Perform a lookup that can iterate over the definitions associated with |atom|. */
    DefinitionList::Range lookupMulti(JSAtom* atom) const {
        MOZ_ASSERT(map);
        if (AtomDefnListPtr p = map->lookup(atom))
            return p.value().all();
        return DefinitionList::Range();
    }

    /* Add-or-update a known-unique definition for |atom|. */
    bool addUnique(JSAtom* atom, DefinitionNode defn) {
        MOZ_ASSERT(map);
        AtomDefnListAddPtr p = map->lookupForAdd(atom);
        if (!p)
            return map->add(p, atom, DefinitionList(ParseHandler::definitionToBits(defn)));
        MOZ_ASSERT(!p.value().isMultiple());
        p.value() = DefinitionList(ParseHandler::definitionToBits(defn));
        return true;
    }

    bool addShadow(JSAtom* atom, DefinitionNode defn);

    /* Updating the definition for an entry that is known to exist is infallible. */
    void updateFirst(JSAtom* atom, DefinitionNode defn) {
        MOZ_ASSERT(map);
        AtomDefnListMap::Ptr p = map->lookup(atom);
        MOZ_ASSERT(p);
        p.value().setFront<ParseHandler>(defn);
    }

    /* Remove the node at the head of the chain for |atom|. */
    void remove(JSAtom* atom) {
        MOZ_ASSERT(map);
        AtomDefnListMap::Ptr p = map->lookup(atom);
        if (!p)
            return;

        DefinitionList& list = p.value();
        if (!list.popFront()) {
            map->remove(p);
            return;
        }
    }

    AtomDefnListMap::Range all() const {
        MOZ_ASSERT(map);
        return map->all();
    }

#ifdef DEBUG
    void dump();
#endif
};

} /* namespace frontend */

} /* namespace js */

namespace mozilla {

template <>
struct IsPod<js::frontend::DefinitionSingle> : TrueType {};

template <>
struct IsPod<js::frontend::DefinitionList> : TrueType {};

} /* namespace mozilla */

#endif /* frontend_ParseMaps_h */