/* -*- 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 "js/HashTable.h"
#include "js/Vector.h"

namespace js {
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(JSContext *cx, AtomIndexMap *indices, HeapPtr<JSAtom> *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) {
        JS_ASSERT(map);
#ifdef DEBUG
        bool ok = false;
        /* Make sure the map is in |all| but not already in |recyclable|. */
        for (void **it = all.begin(), **end = all.end(); it != end; ++it) {
            if (*it == map) {
                ok = true;
                break;
            }
        }
        JS_ASSERT(ok);
        for (void **it = recyclable.begin(), **end = recyclable.end(); it != end; ++it)
            JS_ASSERT(*it != map);
#endif
        JS_ASSERT(recyclable.length() < all.length());
        recyclable.infallibleAppend(map); /* Reserved in allocateFresh. */
    }

    void *allocateFresh();
    void *allocate();

    /* 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();

    /* 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(JSContext *cx);
    void releaseMap(JSContext *cx);

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

    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
{
    JSContext *cx;

  public:
    explicit OwnedAtomThingMapPtr(JSContext *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>
    JS_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 {
        JS_ASSERT(isMultiple());
        return (Node *) (u.bits & ~0x1);
    }

    static Node *
    allocNode(JSContext *cx, 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 = NULL;
                bits = list.u.bits;
            }
        }

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

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

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

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

    DefinitionList() {
        u.bits = 0;
    }

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

    explicit DefinitionList(Node *node) {
        u.head = node;
        u.bits |= 0x1;
        JS_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(JSContext *cx, typename ParseHandler::DefinitionNode defn) {
        Node *tail;
        if (isMultiple()) {
            tail = firstNode();
        } else {
            tail = allocNode(cx, u.bits, NULL);
            if (!tail)
                return false;
        }

        Node *node = allocNode(cx, 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
};

/*
 * 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;

    JSContext   *cx;
    AtomDefnListMap  *map;

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

  public:
    explicit AtomDecls(JSContext *cx) : cx(cx), map(NULL) {}

    ~AtomDecls();

    bool init();

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

    /* Return the definition at the head of the chain for |atom|. */
    inline DefinitionNode lookupFirst(JSAtom *atom) const;

    /* Perform a lookup that can iterate over the definitions associated with |atom|. */
    inline DefinitionList::Range lookupMulti(JSAtom *atom) const;

    /* Add-or-update a known-unique definition for |atom|. */
    inline bool addUnique(JSAtom *atom, DefinitionNode defn);
    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) {
        JS_ASSERT(map);
        AtomDefnListMap::Ptr p = map->lookup(atom);
        JS_ASSERT(p);
        p.value().setFront<ParseHandler>(defn);
    }

    /* Remove the node at the head of the chain for |atom|. */
    void remove(JSAtom *atom) {
        JS_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 {
        JS_ASSERT(map);
        return map->all();
    }

#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;

} /* 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 */