DXR will be turned off on Tuesday, December 29th. It will redirect to Searchfox.
See the announcement on Discourse.

DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127
/* -*- 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/Maybe.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/Move.h"
#include "mozilla/RangedPtr.h"
#include "mozilla/TypeTraits.h"
#include "mozilla/UniquePtr.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/Value.h"
#include "js/Vector.h"

// JS::ubi::Node
//
// 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 'JSRuntime*' 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.

class JSAtom;

namespace JS {
namespace ubi {

class Edge;
class EdgeRange;
class StackFrame;

} // namespace ubi
} // namespace JS

namespace mozilla {

template<>
class DefaultDelete<JS::ubi::EdgeRange> : public JS::DeletePolicy<JS::ubi::EdgeRange> { };

template<>
class DefaultDelete<JS::ubi::StackFrame> : public JS::DeletePolicy<JS::ubi::StackFrame> { };

} // namespace mozilla

namespace JS {
namespace ubi {

using mozilla::Forward;
using mozilla::Maybe;
using mozilla::Move;
using mozilla::RangedPtr;
using mozilla::UniquePtr;
using mozilla::Variant;

/*** 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 AtomOrTwoByteChars : public Variant<JSAtom*, const char16_t*> {
    using Base = Variant<JSAtom*, const char16_t*>;

  public:
    template<typename T>
    MOZ_IMPLICIT AtomOrTwoByteChars(T&& rhs) : Base(Forward<T>(rhs)) { }

    template<typename T>
    AtomOrTwoByteChars& operator=(T&& rhs) {
        MOZ_ASSERT(this != &rhs, "self-move disallowed");
        this->~AtomOrTwoByteChars();
        new (this) AtomOrTwoByteChars(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() 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 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 : public JS::Traceable {
    // 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);
    }
    struct ConstructFunctor;

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

    template<typename T>
    MOZ_IMPLICIT StackFrame(T* ptr) {
        construct(ptr);
    }

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

    // JS::Traceable implementation just forwards to our virtual trace method.
    static void trace(StackFrame* frame, JSTracer* trc) {
        if (frame)
            frame->trace(trc);
    }

    // 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() const { return base()->isSelfHosted(); }
    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 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 { }
    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() const override { MOZ_CRASH("null JS::ubi::StackFrame"); }
};

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,

    FIRST  = Other,
    LAST   = String
};

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 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 MOZ_UTF16("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|.
    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 UniquePtr<EdgeRange> edges(JSRuntime* rt, 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 JSCompartments, such as JSStrings (which are associated
    // with Zones). When the referent is not associated with a compartment,
    // nullptr is returned.
    virtual JSCompartment* compartment() 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.");
    }

    // 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 bool jsObjectConstructorName(JSContext* cx,
                                         UniquePtr<char16_t[], JS::FreePolicy>& outName) const {
        outName.reset(nullptr);
        return true;
    }

  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 also
// include the members described here.
template<typename Referent>
struct Concrete {
    // 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);
};

// 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");
        Concrete<T>::construct(base(), ptr);
    }
    struct ConstructFunctor;

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

    template<typename T>
    MOZ_IMPLICIT Node(T* ptr) {
        construct(ptr);
    }
    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; }

    template<typename T>
    bool is() const {
        return base()->typeName() == canonicalTypeName<T>();
    }

    template<typename T>
    T* as() const {
        MOZ_ASSERT(isLive());
        MOZ_ASSERT(is<T>());
        return static_cast<T*>(base()->ptr);
    }

    template<typename T>
    T* asOrNull() const {
        MOZ_ASSERT(isLive());
        return 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(); }
    JSCompartment* compartment()    const { return base()->compartment(); }
    const char* jsObjectClassName() const { return base()->jsObjectClassName(); }
    bool jsObjectConstructorName(JSContext* cx,
                                 UniquePtr<char16_t[], JS::FreePolicy>& outName) const {
        return base()->jsObjectConstructorName(cx, outName);
    }

    using Size = Base::Size;
    Size size(mozilla::MallocSizeOf mallocSizeof) const {
        return base()->size(mallocSizeof);
    }

    UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames = true) const {
        return base()->edges(rt, 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*, mozilla::tl::FloorLog2<sizeof(void*)>::value> 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; }
    };
};


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

using EdgeName = UniquePtr<const char16_t[], JS::FreePolicy>;

// 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(mozilla::Move(rhs.name))
        , referent(rhs.referent)
    { }

    Edge& operator=(Edge&& rhs) {
        MOZ_ASSERT(&rhs != this);
        this->~Edge();
        new (this) Edge(mozilla::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.
    //
    // (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(rt, 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 RootList {
    Maybe<AutoCheckCannotGC>& noGC;

  public:
    JSRuntime* rt;
    EdgeVector edges;
    bool       wantNames;

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

    // Find all GC roots.
    bool init();
    // Find only GC roots in the provided set of |Zone|s.
    bool init(ZoneSet& debuggees);
    // Find only GC roots in the given Debugger object's set of debuggee zones.
    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.
    bool addRoot(Node node, const char16_t* edgeName = nullptr);
};


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

template<>
struct Concrete<RootList> : public Base {
    UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const override;
    const char16_t* typeName() const override { return concreteTypeName; }

  protected:
    explicit Concrete(RootList* ptr) : Base(ptr) { }
    RootList& get() const { return *static_cast<RootList*>(ptr); }

  public:
    static const char16_t concreteTypeName[];
    static void construct(void* storage, RootList* ptr) { new (storage) Concrete(ptr); }
};

// A reusable ubi::Concrete specialization base class for types supported by
// JS::TraceChildren.
template<typename Referent>
class TracerConcrete : public Base {
    const char16_t* typeName() const override { return concreteTypeName; }
    UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const override;
    JS::Zone* zone() const override;

  protected:
    explicit TracerConcrete(Referent* ptr) : Base(ptr) { }
    Referent& get() const { return *static_cast<Referent*>(ptr); }

  public:
    static const char16_t concreteTypeName[];
    static void construct(void* storage, Referent* ptr) { new (storage) TracerConcrete(ptr); }
};

// For JS::TraceChildren-based types that have a 'compartment' method.
template<typename Referent>
class TracerConcreteWithCompartment : public TracerConcrete<Referent> {
    typedef TracerConcrete<Referent> TracerBase;
    JSCompartment* compartment() const override;

  protected:
    explicit TracerConcreteWithCompartment(Referent* ptr) : TracerBase(ptr) { }

  public:
    static void construct(void* storage, Referent* ptr) {
        new (storage) TracerConcreteWithCompartment(ptr);
    }
};

// Define specializations for some commonly-used public JSAPI types.
// These can use the generic templates above.
template<>
struct Concrete<JS::Symbol> : TracerConcrete<JS::Symbol> {
    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;

  protected:
    explicit Concrete(JS::Symbol* ptr) : TracerConcrete(ptr) { }

  public:
    static void construct(void* storage, JS::Symbol* ptr) {
        new (storage) Concrete(ptr);
    }
};

template<> struct Concrete<JSScript> : TracerConcreteWithCompartment<JSScript> {
    CoarseType coarseType() const final { return CoarseType::Script; }
    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;

  protected:
    explicit Concrete(JSScript *ptr) : TracerConcreteWithCompartment<JSScript>(ptr) { }

  public:
    static void construct(void *storage, JSScript *ptr) { new (storage) Concrete(ptr); }
};

// The JSObject specialization.
template<>
class Concrete<JSObject> : public TracerConcreteWithCompartment<JSObject> {
    const char* jsObjectClassName() const override;
    bool jsObjectConstructorName(JSContext* cx,
                                 UniquePtr<char16_t[], JS::FreePolicy>& outName) const override;
    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;

    bool hasAllocationStack() const override;
    StackFrame allocationStack() const override;

    CoarseType coarseType() const final { return CoarseType::Object; }

  protected:
    explicit Concrete(JSObject* ptr) : TracerConcreteWithCompartment(ptr) { }

  public:
    static void construct(void* storage, JSObject* ptr) {
        new (storage) Concrete(ptr);
    }
};

// For JSString, we extend the generic template with a 'size' implementation.
template<> struct Concrete<JSString> : TracerConcrete<JSString> {
    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;

    CoarseType coarseType() const final { return CoarseType::String; }

  protected:
    explicit Concrete(JSString *ptr) : TracerConcrete<JSString>(ptr) { }

  public:
    static void construct(void *storage, JSString *ptr) { new (storage) Concrete(ptr); }
};

// The ubi::Node null pointer. Any attempt to operate on a null ubi::Node asserts.
template<>
class Concrete<void> : public Base {
    const char16_t* typeName() const override;
    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
    UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const override;
    JS::Zone* zone() const override;
    JSCompartment* compartment() const override;
    CoarseType coarseType() const final;

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

  public:
    static void construct(void* storage, void* ptr) { new (storage) Concrete(ptr); }
    static const char16_t concreteTypeName[];
};


} // namespace ubi
} // namespace JS

namespace js {

// Make ubi::Node::HashPolicy the default hash policy for ubi::Node.
template<> struct DefaultHasher<JS::ubi::Node> : JS::ubi::Node::HashPolicy { };
template<> struct DefaultHasher<JS::ubi::StackFrame> : JS::ubi::StackFrame::HashPolicy { };

} // namespace js

#endif // js_UbiNode_h