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

#define js_UbiNode_h

#include "mozilla/Alignment.h"

#include "mozilla/Assertions.h"

#include "mozilla/Attributes.h"

#include "mozilla/HashFunctions.h"

#include "mozilla/Maybe.h"

#include "mozilla/MemoryReporting.h"

#include "mozilla/Move.h"

#include "mozilla/RangedPtr.h"

#include "mozilla/TypeTraits.h"

#include "mozilla/Variant.h"

#include "jspubtd.h"

#include "js/GCAPI.h"

#include "js/HashTable.h"

#include "js/RootingAPI.h"

#include "js/TracingAPI.h"

#include "js/TypeDecls.h"

#include "js/UniquePtr.h"

#include "js/Value.h"

#include "js/Vector.h"

// [SMDOC] ubi::Node (Heap Analysis framework)

//

// JS::ubi::Node is a pointer-like type designed for internal use by heap

// analysis tools. A ubi::Node can refer to:

//

// - a JS value, like a string, object, or symbol;

// - an internal SpiderMonkey structure, like a shape or a scope chain object

// - an instance of some embedding-provided type: in Firefox, an XPCOM

//   object, or an internal DOM node class instance

//

// A ubi::Node instance provides metadata about its referent, and can

// enumerate its referent's outgoing edges, so you can implement heap analysis

// algorithms that walk the graph - finding paths between objects, or

// computing heap dominator trees, say - using ubi::Node, while remaining

// ignorant of the details of the types you're operating on.

//

// Of course, when it comes to presenting the results in a developer-facing

// tool, you'll need to stop being ignorant of those details, because you have

// to discuss the ubi::Nodes' referents with the developer. Here, ubi::Node

// can hand you dynamically checked, properly typed pointers to the original

// objects via the as<T> method, or generate descriptions of the referent

// itself.

//

// ubi::Node instances are lightweight (two-word) value types. Instances:

// - compare equal if and only if they refer to the same object;

// - have hash values that respect their equality relation; and

// - have serializations that are only equal if the ubi::Nodes are equal.

//

// A ubi::Node is only valid for as long as its referent is alive; if its

// referent goes away, the ubi::Node becomes a dangling pointer. A ubi::Node

// that refers to a GC-managed object is not automatically a GC root; if the

// GC frees or relocates its referent, the ubi::Node becomes invalid. A

// ubi::Node that refers to a reference-counted object does not bump the

// reference count.

//

// ubi::Node values require no supporting data structures, making them

// feasible for use in memory-constrained devices --- ideally, the memory

// requirements of the algorithm which uses them will be the limiting factor,

// not the demands of ubi::Node itself.

//

// One can construct a ubi::Node value given a pointer to a type that ubi::Node

// supports. In the other direction, one can convert a ubi::Node back to a

// pointer; these downcasts are checked dynamically. In particular, one can

// convert a 'JSContext*' to a ubi::Node, yielding a node with an outgoing edge

// for every root registered with the runtime; starting from this, one can walk

// the entire heap. (Of course, one could also start traversal at any other kind

// of type to which one has a pointer.)

//

//

// Extending ubi::Node To Handle Your Embedding's Types

//

// To add support for a new ubi::Node referent type R, you must define a

// specialization of the ubi::Concrete template, ubi::Concrete<R>, which

// inherits from ubi::Base. ubi::Node itself uses the specialization for

// compile-time information (i.e. the checked conversions between R * and

// ubi::Node), and the inheritance for run-time dispatching.

//

//

// ubi::Node Exposes Implementation Details

//

// In many cases, a JavaScript developer's view of their data differs

// substantially from its actual implementation. For example, while the

// ECMAScript specification describes objects as maps from property names to

// sets of attributes (like ECMAScript's [[Value]]), in practice many objects

// have only a pointer to a shape, shared with other similar objects, and

// indexed slots that contain the [[Value]] attributes. As another example, a

// string produced by concatenating two other strings may sometimes be

// represented by a "rope", a structure that points to the two original

// strings.

//

// We intend to use ubi::Node to write tools that report memory usage, so it's

// important that ubi::Node accurately portray how much memory nodes consume.

// Thus, for example, when data that apparently belongs to multiple nodes is

// in fact shared in a common structure, ubi::Node's graph uses a separate

// node for that shared structure, and presents edges to it from the data's

// apparent owners. For example, ubi::Node exposes SpiderMonkey objects'

// shapes and base shapes, and exposes rope string and substring structure,

// because these optimizations become visible when a tool reports how much

// memory a structure consumes.

//

// However, fine granularity is not a goal. When a particular object is the

// exclusive owner of a separate block of memory, ubi::Node may present the

// object and its block as a single node, and add their sizes together when

// reporting the node's size, as there is no meaningful loss of data in this

// case. Thus, for example, a ubi::Node referring to a JavaScript object, when

// asked for the object's size in bytes, includes the object's slot and

// element arrays' sizes in the total. There is no separate ubi::Node value

// representing the slot and element arrays, since they are owned exclusively

// by the object.

//

//

// Presenting Analysis Results To JavaScript Developers

//

// If an analysis provides its results in terms of ubi::Node values, a user

// interface presenting those results will generally need to clean them up

// before they can be understood by JavaScript developers. For example,

// JavaScript developers should not need to understand shapes, only JavaScript

// objects. Similarly, they should not need to understand the distinction

// between DOM nodes and the JavaScript shadow objects that represent them.

//

//

// Rooting Restrictions

//

// At present there is no way to root ubi::Node instances, so instances can't be

// live across any operation that might GC. Analyses using ubi::Node must either

// run to completion and convert their results to some other rootable type, or

// save their intermediate state in some rooted structure if they must GC before

// they complete. (For algorithms like path-finding and dominator tree

// computation, we implement the algorithm avoiding any operation that could

// cause a GC --- and use AutoCheckCannotGC to verify this.)

//

// If this restriction prevents us from implementing interesting tools, we may

// teach the GC how to root ubi::Nodes, fix up hash tables that use them as

// keys, etc.

//

//

// Hostile Graph Structure

//

// Analyses consuming ubi::Node graphs must be robust when presented with graphs

// that are deliberately constructed to exploit their weaknesses. When operating

// on live graphs, web content has control over the object graph, and less

// direct control over shape and string structure, and analyses should be

// prepared to handle extreme cases gracefully. For example, if an analysis were

// to use the C++ stack in a depth-first traversal, carefully constructed

// content could cause the analysis to overflow the stack.

//

// When ubi::Nodes refer to nodes deserialized from a heap snapshot, analyses

// must be even more careful: since snapshots often come from potentially

// compromised e10s content processes, even properties normally guaranteed by

// the platform (the proper linking of DOM nodes, for example) might be

// corrupted. While it is the deserializer's responsibility to check the basic

// structure of the snapshot file, the analyses should be prepared for ubi::Node

// graphs constructed from snapshots to be even more bizarre.

namespace JS {

namespace ubi {

class Edge;

class EdgeRange;

class StackFrame;

} // namespace ubi

} // namespace JS

namespace JS {

namespace ubi {

using mozilla::Maybe;

using mozilla::RangedPtr;

using mozilla::Variant;

template <typename T>

using Vector = mozilla::Vector<T, 0, js::SystemAllocPolicy>;

/*** ubi::StackFrame ******************************************************************************/

// Concrete JS::ubi::StackFrame instances backed by a live SavedFrame object

// store their strings as JSAtom*, while deserialized stack frames from offline

// heap snapshots store their strings as const char16_t*. In order to provide

// zero-cost accessors to these strings in a single interface that works with

// both cases, we use this variant type.

class JS_PUBLIC_API(AtomOrTwoByteChars) : public Variant<JSAtom*, const char16_t*> {

    using Base = Variant<JSAtom*, const char16_t*>;

  public:

    template<typename T>

    MOZ_IMPLICIT AtomOrTwoByteChars(T&& rhs) : Base(std::forward<T>(rhs)) { }

Unexecuted instantiation: JS::ubi::AtomOrTwoByteChars::AtomOrTwoByteChars<char16_t const*&>(char16_t const*&)

Unexecuted instantiation: JS::ubi::AtomOrTwoByteChars::AtomOrTwoByteChars<JSAtom*&>(JSAtom*&)

    template<typename T>

    AtomOrTwoByteChars& operator=(T&& rhs) {

        MOZ_ASSERT(this != &rhs, "self-move disallowed");

        this->~AtomOrTwoByteChars();

        new (this) AtomOrTwoByteChars(std::forward<T>(rhs));

        return *this;

    }

    // Return the length of the given AtomOrTwoByteChars string.

    size_t length();

    // Copy the given AtomOrTwoByteChars string into the destination buffer,

    // inflating if necessary. Does NOT null terminate. Returns the number of

    // characters written to destination.

    size_t copyToBuffer(RangedPtr<char16_t> destination, size_t length);

};

// The base class implemented by each ConcreteStackFrame<T> type. Subclasses

// must not add data members to this class.

class BaseStackFrame {

    friend class StackFrame;

    BaseStackFrame(const StackFrame&) = delete;

    BaseStackFrame& operator=(const StackFrame&) = delete;

  protected:

    void* ptr;

    explicit BaseStackFrame(void* ptr) : ptr(ptr) { }

  public:

    // This is a value type that should not have a virtual destructor. Don't add

    // destructors in subclasses!

    // Get a unique identifier for this StackFrame. The identifier is not valid

    // across garbage collections.

    virtual uint64_t identifier() const { return uint64_t(uintptr_t(ptr)); }

    // Get this frame's parent frame.

    virtual StackFrame parent() const = 0;

    // Get this frame's line number.

    virtual uint32_t line() const = 0;

    // Get this frame's column number.

    virtual uint32_t column() const = 0;

    // Get this frame's source name. Never null.

    virtual AtomOrTwoByteChars source() const = 0;

    // Return this frame's function name if named, otherwise the inferred

    // display name. Can be null.

    virtual AtomOrTwoByteChars functionDisplayName() const = 0;

    // Returns true if this frame's function is system JavaScript running with

    // trusted principals, false otherwise.

    virtual bool isSystem() const = 0;

    // Return true if this frame's function is a self-hosted JavaScript builtin,

    // false otherwise.

    virtual bool isSelfHosted(JSContext* cx) const = 0;

    // Construct a SavedFrame stack for the stack starting with this frame and

    // containing all of its parents. The SavedFrame objects will be placed into

    // cx's current compartment.

    //

    // Note that the process of

    //

    //     SavedFrame

    //         |

    //         V

    //     JS::ubi::StackFrame

    //         |

    //         V

    //     offline heap snapshot

    //         |

    //         V

    //     JS::ubi::StackFrame

    //         |

    //         V

    //     SavedFrame

    //

    // is lossy because we cannot serialize and deserialize the SavedFrame's

    // principals in the offline heap snapshot, so JS::ubi::StackFrame

    // simplifies the principals check into the boolean isSystem() state. This

    // is fine because we only expose JS::ubi::Stack to devtools and chrome

    // code, and not to the web platform.

    virtual MOZ_MUST_USE bool constructSavedFrameStack(JSContext* cx,

                                                       MutableHandleObject outSavedFrameStack)

        const = 0;

    // Trace the concrete implementation of JS::ubi::StackFrame.

    virtual void trace(JSTracer* trc) = 0;

};

// A traits template with a specialization for each backing type that implements

// the ubi::BaseStackFrame interface. Each specialization must be the a subclass

// of ubi::BaseStackFrame.

template<typename T> class ConcreteStackFrame;

// A JS::ubi::StackFrame represents a frame in a recorded stack. It can be

// backed either by a live SavedFrame object or by a structure deserialized from

// an offline heap snapshot.

//

// It is a value type that may be memcpy'd hither and thither without worrying

// about constructors or destructors, similar to POD types.

//

// Its lifetime is the same as the lifetime of the graph that is being analyzed

// by the JS::ubi::Node that the JS::ubi::StackFrame came from. That is, if the

// graph being analyzed is the live heap graph, the JS::ubi::StackFrame is only

// valid within the scope of an AutoCheckCannotGC; if the graph being analyzed

// is an offline heap snapshot, the JS::ubi::StackFrame is valid as long as the

// offline heap snapshot is alive.

class StackFrame {

    // Storage in which we allocate BaseStackFrame subclasses.

    mozilla::AlignedStorage2<BaseStackFrame> storage;

    BaseStackFrame* base() { return storage.addr(); }

    const BaseStackFrame* base() const { return storage.addr(); }

    template<typename T>

    void construct(T* ptr) {

        static_assert(mozilla::IsBaseOf<BaseStackFrame, ConcreteStackFrame<T>>::value,

                      "ConcreteStackFrame<T> must inherit from BaseStackFrame");

        static_assert(sizeof(ConcreteStackFrame<T>) == sizeof(*base()),

                      "ubi::ConcreteStackFrame<T> specializations must be the same size as "

                      "ubi::BaseStackFrame");

        ConcreteStackFrame<T>::construct(base(), ptr);

    }

Unexecuted instantiation: void JS::ubi::StackFrame::construct<void>(void*)

Unexecuted instantiation: void JS::ubi::StackFrame::construct<mozilla::devtools::DeserializedStackFrame>(mozilla::devtools::DeserializedStackFrame*)

Unexecuted instantiation: void JS::ubi::StackFrame::construct<js::SavedFrame>(js::SavedFrame*)

    struct ConstructFunctor;

  public:

    StackFrame() { construct<void>(nullptr); }

    template<typename T>

    MOZ_IMPLICIT StackFrame(T* ptr) {

        construct(ptr);

    }

Unexecuted instantiation: JS::ubi::StackFrame::StackFrame<mozilla::devtools::DeserializedStackFrame>(mozilla::devtools::DeserializedStackFrame*)

Unexecuted instantiation: JS::ubi::StackFrame::StackFrame<js::SavedFrame>(js::SavedFrame*)

    template<typename T>

    StackFrame& operator=(T* ptr) {

        construct(ptr);

        return *this;

    }

    // Constructors accepting SpiderMonkey's generic-pointer-ish types.

    template<typename T>

    explicit StackFrame(const JS::Handle<T*>& handle) {

        construct(handle.get());

    }

    template<typename T>

    StackFrame& operator=(const JS::Handle<T*>& handle) {

        construct(handle.get());

        return *this;

    }

    template<typename T>

    explicit StackFrame(const JS::Rooted<T*>& root) {

        construct(root.get());

    }

    template<typename T>

    StackFrame& operator=(const JS::Rooted<T*>& root) {

        construct(root.get());

        return *this;

    }

    // Because StackFrame is just a vtable pointer and an instance pointer, we

    // can memcpy everything around instead of making concrete classes define

    // virtual constructors. See the comment above Node's copy constructor for

    // more details; that comment applies here as well.

    StackFrame(const StackFrame& rhs) {

        memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));

    }

    StackFrame& operator=(const StackFrame& rhs) {

        memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));

        return *this;

    }

    bool operator==(const StackFrame& rhs) const { return base()->ptr == rhs.base()->ptr; }

    bool operator!=(const StackFrame& rhs) const { return !(*this == rhs); }

    explicit operator bool() const {

        return base()->ptr != nullptr;

    }

    // Copy this StackFrame's source name into the given |destination|

    // buffer. Copy no more than |length| characters. The result is *not* null

    // terminated. Returns how many characters were written into the buffer.

    size_t source(RangedPtr<char16_t> destination, size_t length) const;

    // Copy this StackFrame's function display name into the given |destination|

    // buffer. Copy no more than |length| characters. The result is *not* null

    // terminated. Returns how many characters were written into the buffer.

    size_t functionDisplayName(RangedPtr<char16_t> destination, size_t length) const;

    // Get the size of the respective strings. 0 is returned for null strings.

    size_t sourceLength();

    size_t functionDisplayNameLength();

    // Methods that forward to virtual calls through BaseStackFrame.

    void trace(JSTracer* trc) { base()->trace(trc); }

    uint64_t identifier() const {

        auto id = base()->identifier();

        MOZ_ASSERT(JS::Value::isNumberRepresentable(id));

        return id;

    }

    uint32_t line() const { return base()->line(); }

    uint32_t column() const { return base()->column(); }

    AtomOrTwoByteChars source() const { return base()->source(); }

    AtomOrTwoByteChars functionDisplayName() const { return base()->functionDisplayName(); }

    StackFrame parent() const { return base()->parent(); }

    bool isSystem() const { return base()->isSystem(); }

    bool isSelfHosted(JSContext* cx) const { return base()->isSelfHosted(cx); }

    MOZ_MUST_USE bool constructSavedFrameStack(JSContext* cx,

                                               MutableHandleObject outSavedFrameStack) const {

        return base()->constructSavedFrameStack(cx, outSavedFrameStack);

    }

    struct HashPolicy {

        using Lookup = JS::ubi::StackFrame;

        static js::HashNumber hash(const Lookup& lookup) {

            return mozilla::HashGeneric(lookup.identifier());

        }

        static bool match(const StackFrame& key, const Lookup& lookup) {

            return key == lookup;

        }

        static void rekey(StackFrame& k, const StackFrame& newKey) {

            k = newKey;

        }

    };

};

// The ubi::StackFrame null pointer. Any attempt to operate on a null

// ubi::StackFrame crashes.

template<>

class ConcreteStackFrame<void> : public BaseStackFrame {

    explicit ConcreteStackFrame(void* ptr) : BaseStackFrame(ptr) { }

  public:

    static void construct(void* storage, void*) { new (storage) ConcreteStackFrame(nullptr); }

    uint64_t identifier() const override { return 0; }

    void trace(JSTracer* trc) override { }

    MOZ_MUST_USE bool constructSavedFrameStack(JSContext* cx, MutableHandleObject out)

        const override

    {

        out.set(nullptr);

        return true;

    }

    uint32_t line() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }

    uint32_t column() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }

    AtomOrTwoByteChars source() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }

    AtomOrTwoByteChars functionDisplayName() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }

    StackFrame parent() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }

    bool isSystem() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }

    bool isSelfHosted(JSContext* cx) const override { MOZ_CRASH("null JS::ubi::StackFrame"); }

};

MOZ_MUST_USE JS_PUBLIC_API(bool)

ConstructSavedFrameStackSlow(JSContext* cx,

                             JS::ubi::StackFrame& frame,

                             MutableHandleObject outSavedFrameStack);

/*** ubi::Node ************************************************************************************/

// A concrete node specialization can claim its referent is a member of a

// particular "coarse type" which is less specific than the actual

// implementation type but generally more palatable for web developers. For

// example, JitCode can be considered to have a coarse type of "Script". This is

// used by some analyses for putting nodes into different buckets. The default,

// if a concrete specialization does not provide its own mapping to a CoarseType

// variant, is "Other".

//

// NB: the values associated with a particular enum variant must not change or

// be reused for new variants. Doing so will cause inspecting ubi::Nodes backed

// by an offline heap snapshot from an older SpiderMonkey/Firefox version to

// break. Consider this enum append only.

enum class CoarseType: uint32_t {

    Other   = 0,

    Object  = 1,

    Script  = 2,

    String  = 3,

    DOMNode = 4,

    FIRST   = Other,

    LAST    = DOMNode

};

inline uint32_t

CoarseTypeToUint32(CoarseType type)

{

    return static_cast<uint32_t>(type);

}

inline bool

Uint32IsValidCoarseType(uint32_t n)

{

    auto first = static_cast<uint32_t>(CoarseType::FIRST);

    auto last = static_cast<uint32_t>(CoarseType::LAST);

    MOZ_ASSERT(first < last);

    return first <= n && n <= last;

}

inline CoarseType

Uint32ToCoarseType(uint32_t n)

{

    MOZ_ASSERT(Uint32IsValidCoarseType(n));

    return static_cast<CoarseType>(n);

}

// The base class implemented by each ubi::Node referent type. Subclasses must

// not add data members to this class.

class JS_PUBLIC_API(Base) {

    friend class Node;

    // For performance's sake, we'd prefer to avoid a virtual destructor; and

    // an empty constructor seems consistent with the 'lightweight value type'

    // visible behavior we're trying to achieve. But if the destructor isn't

    // virtual, and a subclass overrides it, the subclass's destructor will be

    // ignored. Is there a way to make the compiler catch that error?

  protected:

    // Space for the actual pointer. Concrete subclasses should define a

    // properly typed 'get' member function to access this.

    void* ptr;

    explicit Base(void* ptr) : ptr(ptr) { }

  public:

    bool operator==(const Base& rhs) const {

        // Some compilers will indeed place objects of different types at

        // the same address, so technically, we should include the vtable

        // in this comparison. But it seems unlikely to cause problems in

        // practice.

        return ptr == rhs.ptr;

    }

    bool operator!=(const Base& rhs) const { return !(*this == rhs); }

    // An identifier for this node, guaranteed to be stable and unique for as

    // long as this ubi::Node's referent is alive and at the same address.

    //

    // This is probably suitable for use in serializations, as it is an integral

    // type. It may also help save memory when constructing HashSets of

    // ubi::Nodes: since a uint64_t will always be smaller-or-equal-to the size

    // of a ubi::Node, a HashSet<ubi::Node::Id> may use less space per element

    // than a HashSet<ubi::Node>.

    //

    // (Note that 'unique' only means 'up to equality on ubi::Node'; see the

    // caveats about multiple objects allocated at the same address for

    // 'ubi::Node::operator=='.)

    using Id = uint64_t;

    virtual Id identifier() const { return Id(uintptr_t(ptr)); }

    // Returns true if this node is pointing to something on the live heap, as

    // opposed to something from a deserialized core dump. Returns false,

    // otherwise.

    virtual bool isLive() const { return true; };

    // Return the coarse-grained type-of-thing that this node represents.

    virtual CoarseType coarseType() const { return CoarseType::Other; }

    // Return a human-readable name for the referent's type. The result should

    // be statically allocated. (You can use u"strings" for this.)

    //

    // This must always return Concrete<T>::concreteTypeName; we use that

    // pointer as a tag for this particular referent type.

    virtual const char16_t* typeName() const = 0;

    // Return the size of this node, in bytes. Include any structures that this

    // node owns exclusively that are not exposed as their own ubi::Nodes.

    // |mallocSizeOf| should be a malloc block sizing function; see

    // |mfbt/MemoryReporting.h|.

    //

    // Because we can use |JS::ubi::Node|s backed by a snapshot that was taken

    // on a 64-bit platform when we are currently on a 32-bit platform, we

    // cannot rely on |size_t| for node sizes. Instead, |Size| is uint64_t on

    // all platforms.

    using Size = uint64_t;

    virtual Size size(mozilla::MallocSizeOf mallocSizeof) const { return 1; }

    // Return an EdgeRange that initially contains all the referent's outgoing

    // edges. The caller takes ownership of the EdgeRange.

    //

    // If wantNames is true, compute names for edges. Doing so can be expensive

    // in time and memory.

    virtual js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const = 0;

    // Return the Zone to which this node's referent belongs, or nullptr if the

    // referent is not of a type allocated in SpiderMonkey Zones.

    virtual JS::Zone* zone() const { return nullptr; }

    // Return the compartment for this node. Some ubi::Node referents are not

    // associated with Compartments, such as JSStrings (which are associated

    // with Zones). When the referent is not associated with a compartment,

    // nullptr is returned.

    virtual JS::Compartment* compartment() const { return nullptr; }

    // Return the realm for this node. Some ubi::Node referents are not

    // associated with Realms, such as JSStrings (which are associated

    // with Zones) or cross-compartment wrappers (which are associated with

    // compartments). When the referent is not associated with a realm,

    // nullptr is returned.

    virtual JS::Realm* realm() const { return nullptr; }

    // Return whether this node's referent's allocation stack was captured.

    virtual bool hasAllocationStack() const { return false; }

    // Get the stack recorded at the time this node's referent was

    // allocated. This must only be called when hasAllocationStack() is true.

    virtual StackFrame allocationStack() const {

        MOZ_CRASH("Concrete classes that have an allocation stack must override both "

                  "hasAllocationStack and allocationStack.");

    }

    // In some cases, Concrete<T> can return a more descriptive

    // referent type name than simply `T`. This method returns an

    // identifier as specific as is efficiently available.

    // The string returned is borrowed from the ubi::Node's referent.

    // If nothing more specific than typeName() is available, return nullptr.

    virtual const char16_t* descriptiveTypeName() const { return nullptr; }

    // Methods for JSObject Referents

    //

    // These methods are only semantically valid if the referent is either a

    // JSObject in the live heap, or represents a previously existing JSObject

    // from some deserialized heap snapshot.

    // Return the object's [[Class]]'s name.

    virtual const char* jsObjectClassName() const { return nullptr; }

    // If this object was constructed with `new` and we have the data available,

    // place the contructor function's display name in the out parameter.

    // Otherwise, place nullptr in the out parameter. Caller maintains ownership

    // of the out parameter. True is returned on success, false is returned on

    // OOM.

    virtual MOZ_MUST_USE bool jsObjectConstructorName(JSContext* cx, UniqueTwoByteChars& outName)

        const

    {

        outName.reset(nullptr);

        return true;

    }

    // Methods for CoarseType::Script referents

    // Return the script's source's filename if available. If unavailable,

    // return nullptr.

    virtual const char* scriptFilename() const { return nullptr; }

  private:

    Base(const Base& rhs) = delete;

    Base& operator=(const Base& rhs) = delete;

};

// A traits template with a specialization for each referent type that

// ubi::Node supports. The specialization must be the concrete subclass of Base

// that represents a pointer to the referent type. It must include these

// members:

//

//    // The specific char16_t array returned by Concrete<T>::typeName().

//    static const char16_t concreteTypeName[];

//

//    // Construct an instance of this concrete class in |storage| referring

//    // to |referent|. Implementations typically use a placement 'new'.

//    //

//    // In some cases, |referent| will contain dynamic type information that

//    // identifies it a some more specific subclass of |Referent|. For

//    // example, when |Referent| is |JSObject|, then |referent->getClass()|

//    // could tell us that it's actually a JSFunction. Similarly, if

//    // |Referent| is |nsISupports|, we would like a ubi::Node that knows its

//    // final implementation type.

//    //

//    // So we delegate the actual construction to this specialization, which

//    // knows Referent's details.

//    static void construct(void* storage, Referent* referent);

template<typename Referent>

class Concrete;

// A container for a Base instance; all members simply forward to the contained

// instance.  This container allows us to pass ubi::Node instances by value.

class Node {

    // Storage in which we allocate Base subclasses.

    mozilla::AlignedStorage2<Base> storage;

    Base* base() { return storage.addr(); }

    const Base* base() const { return storage.addr(); }

    template<typename T>

    void construct(T* ptr) {

        static_assert(sizeof(Concrete<T>) == sizeof(*base()),

                      "ubi::Base specializations must be the same size as ubi::Base");

        static_assert(mozilla::IsBaseOf<Base, Concrete<T>>::value,

                      "ubi::Concrete<T> must inherit from ubi::Base");

        Concrete<T>::construct(base(), ptr);

    }

Unexecuted instantiation: void JS::ubi::Node::construct<nsINode>(nsINode*)

Unexecuted instantiation: void JS::ubi::Node::construct<void>(void*)

Unexecuted instantiation: void JS::ubi::Node::construct<nsIContent>(nsIContent*)

Unexecuted instantiation: void JS::ubi::Node::construct<mozilla::devtools::DeserializedNode>(mozilla::devtools::DeserializedNode*)

Unexecuted instantiation: void JS::ubi::Node::construct<JSObject>(JSObject*)

Unexecuted instantiation: void JS::ubi::Node::construct<JS::ubi::RootList>(JS::ubi::RootList*)

Unexecuted instantiation: void JS::ubi::Node::construct<FakeNode>(FakeNode*)

Unexecuted instantiation: void JS::ubi::Node::construct<JSScript>(JSScript*)

Unexecuted instantiation: void JS::ubi::Node::construct<js::BaseShape>(js::BaseShape*)

Unexecuted instantiation: void JS::ubi::Node::construct<js::jit::JitCode>(js::jit::JitCode*)

Unexecuted instantiation: void JS::ubi::Node::construct<js::LazyScript>(js::LazyScript*)

Unexecuted instantiation: void JS::ubi::Node::construct<js::Scope>(js::Scope*)

Unexecuted instantiation: void JS::ubi::Node::construct<js::ObjectGroup>(js::ObjectGroup*)

Unexecuted instantiation: void JS::ubi::Node::construct<js::Shape>(js::Shape*)

Unexecuted instantiation: void JS::ubi::Node::construct<JSString>(JSString*)

Unexecuted instantiation: void JS::ubi::Node::construct<JS::Symbol>(JS::Symbol*)

Unexecuted instantiation: void JS::ubi::Node::construct<js::RegExpShared>(js::RegExpShared*)

    struct ConstructFunctor;

  public:

    Node() { construct<void>(nullptr); }

    template<typename T>

    MOZ_IMPLICIT Node(T* ptr) {

        construct(ptr);

    }

Unexecuted instantiation: JS::ubi::Node::Node<nsINode>(nsINode*)

Unexecuted instantiation: JS::ubi::Node::Node<nsIContent>(nsIContent*)

Unexecuted instantiation: JS::ubi::Node::Node<mozilla::devtools::DeserializedNode>(mozilla::devtools::DeserializedNode*)

Unexecuted instantiation: JS::ubi::Node::Node<JSObject>(JSObject*)

Unexecuted instantiation: JS::ubi::Node::Node<JS::ubi::RootList>(JS::ubi::RootList*)

Unexecuted instantiation: JS::ubi::Node::Node<FakeNode>(FakeNode*)

    template<typename T>

    Node& operator=(T* ptr) {

        construct(ptr);

        return *this;

    }

    // We can construct and assign from rooted forms of pointers.

    template<typename T>

    MOZ_IMPLICIT Node(const Rooted<T*>& root) {

        construct(root.get());

    }

    template<typename T>

    Node& operator=(const Rooted<T*>& root) {

        construct(root.get());

        return *this;

    }

    // Constructors accepting SpiderMonkey's other generic-pointer-ish types.

    // Note that we *do* want an implicit constructor here: JS::Value and

    // JS::ubi::Node are both essentially tagged references to other sorts of

    // objects, so letting conversions happen automatically is appropriate.

    MOZ_IMPLICIT Node(JS::HandleValue value);

    explicit Node(const JS::GCCellPtr& thing);

    // copy construction and copy assignment just use memcpy, since we know

    // instances contain nothing but a vtable pointer and a data pointer.

    //

    // To be completely correct, concrete classes could provide a virtual

    // 'construct' member function, which we could invoke on rhs to construct an

    // instance in our storage. But this is good enough; there's no need to jump

    // through vtables for copying and assignment that are just going to move

    // two words around. The compiler knows how to optimize memcpy.

    Node(const Node& rhs) {

        memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));

    }

    Node& operator=(const Node& rhs) {

        memcpy(storage.u.mBytes, rhs.storage.u.mBytes, sizeof(storage.u));

        return *this;

    }

    bool operator==(const Node& rhs) const { return *base() == *rhs.base(); }

    bool operator!=(const Node& rhs) const { return *base() != *rhs.base(); }

    explicit operator bool() const {

        return base()->ptr != nullptr;

    }

    bool isLive() const { return base()->isLive(); }

    // Get the canonical type name for the given type T.

    template<typename T>

    static const char16_t* canonicalTypeName() { return Concrete<T>::concreteTypeName; }

Unexecuted instantiation: char16_t const* JS::ubi::Node::canonicalTypeName<JSObject>()

Unexecuted instantiation: char16_t const* JS::ubi::Node::canonicalTypeName<JSString>()

Unexecuted instantiation: char16_t const* JS::ubi::Node::canonicalTypeName<JS::Symbol>()

    template<typename T>

    bool is() const {

        return base()->typeName() == canonicalTypeName<T>();

    }

Unexecuted instantiation: bool JS::ubi::Node::is<JSObject>() const

Unexecuted instantiation: bool JS::ubi::Node::is<JSString>() const

Unexecuted instantiation: bool JS::ubi::Node::is<JS::Symbol>() const

    template<typename T>

    T* as() const {

        MOZ_ASSERT(isLive());

        MOZ_ASSERT(this->is<T>());

        return static_cast<T*>(base()->ptr);

    }

Unexecuted instantiation: JSObject* JS::ubi::Node::as<JSObject>() const

Unexecuted instantiation: JSString* JS::ubi::Node::as<JSString>() const

Unexecuted instantiation: JS::Symbol* JS::ubi::Node::as<JS::Symbol>() const

    template<typename T>

    T* asOrNull() const {

        MOZ_ASSERT(isLive());

        return this->is<T>() ? static_cast<T*>(base()->ptr) : nullptr;

    }

    // If this node refers to something that can be represented as a JavaScript

    // value that is safe to expose to JavaScript code, return that value.

    // Otherwise return UndefinedValue(). JSStrings, JS::Symbols, and some (but

    // not all!) JSObjects can be exposed.

    JS::Value exposeToJS() const;

    CoarseType coarseType()               const { return base()->coarseType(); }

    const char16_t* typeName()            const { return base()->typeName(); }

    JS::Zone* zone()                      const { return base()->zone(); }

    JS::Compartment* compartment()        const { return base()->compartment(); }

    JS::Realm* realm()                    const { return base()->realm(); }

    const char* jsObjectClassName()       const { return base()->jsObjectClassName(); }

    const char16_t* descriptiveTypeName() const { return base()->descriptiveTypeName(); }

    MOZ_MUST_USE bool jsObjectConstructorName(JSContext* cx, UniqueTwoByteChars& outName) const {

        return base()->jsObjectConstructorName(cx, outName);

    }

    const char* scriptFilename() const { return base()->scriptFilename(); }

    using Size = Base::Size;

    Size size(mozilla::MallocSizeOf mallocSizeof) const {

        auto size =  base()->size(mallocSizeof);

        MOZ_ASSERT(size > 0,

                   "C++ does not have zero-sized types! Choose 1 if you just need a "

                   "conservative default.");

        return size;

    }

    js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames = true) const {

        return base()->edges(cx, wantNames);

    }

    bool hasAllocationStack() const { return base()->hasAllocationStack(); }

    StackFrame allocationStack() const {

        return base()->allocationStack();

    }

    using Id = Base::Id;

    Id identifier() const {

        auto id = base()->identifier();

        MOZ_ASSERT(JS::Value::isNumberRepresentable(id));

        return id;

    }

    // A hash policy for ubi::Nodes.

    // This simply uses the stock PointerHasher on the ubi::Node's pointer.

    // We specialize DefaultHasher below to make this the default.

    class HashPolicy {

        typedef js::PointerHasher<void*> PtrHash;

      public:

        typedef Node Lookup;

        static js::HashNumber hash(const Lookup& l) { return PtrHash::hash(l.base()->ptr); }

        static bool match(const Node& k, const Lookup& l) { return k == l; }

        static void rekey(Node& k, const Node& newKey) { k = newKey; }

    };

};

using NodeSet = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>;

using NodeSetPtr = mozilla::UniquePtr<NodeSet, JS::DeletePolicy<NodeSet>>;

/*** Edge and EdgeRange ***************************************************************************/

using EdgeName = UniqueTwoByteChars;

// An outgoing edge to a referent node.

class Edge {

  public:

    Edge() : name(nullptr), referent() { }

    // Construct an initialized Edge, taking ownership of |name|.

    Edge(char16_t* name, const Node& referent)

        : name(name)

        , referent(referent)

    { }

    // Move construction and assignment.

    Edge(Edge&& rhs)

        : name(std::move(rhs.name))

        , referent(rhs.referent)

    { }

    Edge& operator=(Edge&& rhs) {

        MOZ_ASSERT(&rhs != this);

        this->~Edge();

        new (this) Edge(std::move(rhs));

        return *this;

    }

    Edge(const Edge&) = delete;

    Edge& operator=(const Edge&) = delete;

    // This edge's name. This may be nullptr, if Node::edges was called with

    // false as the wantNames parameter.

    //

    // The storage is owned by this Edge, and will be freed when this Edge is

    // destructed. You may take ownership of the name by `std::move`ing it

    // out of the edge; it is just a UniquePtr.

    //

    // (In real life we'll want a better representation for names, to avoid

    // creating tons of strings when the names follow a pattern; and we'll need

    // to think about lifetimes carefully to ensure traversal stays cheap.)

    EdgeName name;

    // This edge's referent.

    Node referent;

};

// EdgeRange is an abstract base class for iterating over a node's outgoing

// edges. (This is modeled after js::HashTable<K,V>::Range.)

//

// Concrete instances of this class need not be as lightweight as Node itself,

// since they're usually only instantiated while iterating over a particular

// object's edges. For example, a dumb implementation for JS Cells might use

// JS::TraceChildren to to get the outgoing edges, and then store them in an

// array internal to the EdgeRange.

class EdgeRange {

  protected:

    // The current front edge of this range, or nullptr if this range is empty.

    Edge* front_;

    EdgeRange() : front_(nullptr) { }

  public:

    virtual ~EdgeRange() { }

    // True if there are no more edges in this range.

    bool empty() const { return !front_; }

    // The front edge of this range. This is owned by the EdgeRange, and is

    // only guaranteed to live until the next call to popFront, or until

    // the EdgeRange is destructed.

    const Edge& front() const { return *front_; }

    Edge& front() { return *front_; }

    // Remove the front edge from this range. This should only be called if

    // !empty().

    virtual void popFront() = 0;

  private:

    EdgeRange(const EdgeRange&) = delete;

    EdgeRange& operator=(const EdgeRange&) = delete;

};

typedef mozilla::Vector<Edge, 8, js::SystemAllocPolicy> EdgeVector;

// An EdgeRange concrete class that holds a pre-existing vector of

// Edges. A PreComputedEdgeRange does not take ownership of its

// EdgeVector; it is up to the PreComputedEdgeRange's consumer to manage

// that lifetime.

class PreComputedEdgeRange : public EdgeRange {

    EdgeVector& edges;

    size_t      i;

    void settle() {

        front_ = i < edges.length() ? &edges[i] : nullptr;

    }

  public:

    explicit PreComputedEdgeRange(EdgeVector& edges)

      : edges(edges),

        i(0)

    {

        settle();

    }

    void popFront() override {

        MOZ_ASSERT(!empty());

        i++;

        settle();

    }

};

/*** RootList *************************************************************************************/

// RootList is a class that can be pointed to by a |ubi::Node|, creating a

// fictional root-of-roots which has edges to every GC root in the JS

// runtime. Having a single root |ubi::Node| is useful for algorithms written

// with the assumption that there aren't multiple roots (such as computing

// dominator trees) and you want a single point of entry. It also ensures that

// the roots themselves get visited by |ubi::BreadthFirst| (they would otherwise

// only be used as starting points).

//

// RootList::init itself causes a minor collection, but once the list of roots

// has been created, GC must not occur, as the referent ubi::Nodes are not

// stable across GC. The init calls emplace on |noGC|'s AutoCheckCannotGC, whose

// lifetime must extend at least as long as the RootList itself.

//

// Example usage:

//

//    {

//        mozilla::Maybe<JS::AutoCheckCannotGC> maybeNoGC;

//        JS::ubi::RootList rootList(cx, maybeNoGC);

//        if (!rootList.init())

//            return false;

//

//        // The AutoCheckCannotGC is guaranteed to exist if init returned true.

//        MOZ_ASSERT(maybeNoGC.isSome());

//

//        JS::ubi::Node root(&rootList);

//

//        ...

//    }

class MOZ_STACK_CLASS JS_PUBLIC_API(RootList) {

    Maybe<AutoCheckCannotGC>& noGC;

  public:

    JSContext* cx;

    EdgeVector edges;

    bool       wantNames;

    RootList(JSContext* cx, Maybe<AutoCheckCannotGC>& noGC, bool wantNames = false);

    // Find all GC roots.

    MOZ_MUST_USE bool init();

    // Find only GC roots in the provided set of |JS::Compartment|s. Note: it's

    // important to take a CompartmentSet and not a RealmSet: objects in

    // same-compartment realms can reference each other directly, without going

    // through CCWs, so if we used a RealmSet here we would miss edges.

    MOZ_MUST_USE bool init(CompartmentSet& debuggees);

    // Find only GC roots in the given Debugger object's set of debuggee

    // compartments.

    MOZ_MUST_USE bool init(HandleObject debuggees);

    // Returns true if the RootList has been initialized successfully, false

    // otherwise.

    bool initialized() { return noGC.isSome(); }

    // Explicitly add the given Node as a root in this RootList. If wantNames is

    // true, you must pass an edgeName. The RootList does not take ownership of

    // edgeName.

    MOZ_MUST_USE bool addRoot(Node node, const char16_t* edgeName = nullptr);

};

/*** Concrete classes for ubi::Node referent types ************************************************/

template<>

class JS_PUBLIC_API(Concrete<RootList>) : public Base {

  protected:

    explicit Concrete(RootList* ptr) : Base(ptr) { }

    RootList& get() const { return *static_cast<RootList*>(ptr); }

  public:

    static void construct(void* storage, RootList* ptr) { new (storage) Concrete(ptr); }

    js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override;

    const char16_t* typeName() const override { return concreteTypeName; }

    static const char16_t concreteTypeName[];

};

// A reusable ubi::Concrete specialization base class for types supported by

// JS::TraceChildren.

template<typename Referent>

class JS_PUBLIC_API(TracerConcrete) : public Base {

    JS::Zone* zone() const override;

  public:

    js::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override;

  protected:

    explicit TracerConcrete(Referent* ptr) : Base(ptr) { }

Unexecuted instantiation: JS::ubi::TracerConcrete<JSObject>::TracerConcrete(JSObject*)

Unexecuted instantiation: JS::ubi::TracerConcrete<JSScript>::TracerConcrete(JSScript*)

Unexecuted instantiation: JS::ubi::TracerConcrete<js::BaseShape>::TracerConcrete(js::BaseShape*)

Unexecuted instantiation: JS::ubi::TracerConcrete<js::jit::JitCode>::TracerConcrete(js::jit::JitCode*)

Unexecuted instantiation: JS::ubi::TracerConcrete<js::LazyScript>::TracerConcrete(js::LazyScript*)

Unexecuted instantiation: JS::ubi::TracerConcrete<js::Scope>::TracerConcrete(js::Scope*)

Unexecuted instantiation: JS::ubi::TracerConcrete<js::ObjectGroup>::TracerConcrete(js::ObjectGroup*)

Unexecuted instantiation: JS::ubi::TracerConcrete<js::Shape>::TracerConcrete(js::Shape*)

Unexecuted instantiation: JS::ubi::TracerConcrete<JSString>::TracerConcrete(JSString*)

Unexecuted instantiation: JS::ubi::TracerConcrete<JS::Symbol>::TracerConcrete(JS::Symbol*)

Unexecuted instantiation: JS::ubi::TracerConcrete<js::RegExpShared>::TracerConcrete(js::RegExpShared*)

    Referent& get() const { return *static_cast<Referent*>(ptr); }

Unexecuted instantiation: JS::ubi::TracerConcrete<JSObject>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<js::jit::JitCode>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<JSScript>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<js::LazyScript>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<js::RegExpShared>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<js::Scope>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<js::Shape>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<js::BaseShape>::get() const

Unexecuted instantiation: JS::ubi::TracerConcrete<JSString>::get() const