This file is indexed.

/usr/include/thunderbird/js/UbiNode.h is in thunderbird-dev 1:52.8.0-1~deb8u1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

   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
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
/* -*- 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/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"

// 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 '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.

class JSAtom;

namespace JS {
namespace ubi {

class Edge;
class EdgeRange;
class StackFrame;

} // namespace ubi
} // namespace JS

namespace JS {
namespace ubi {

using mozilla::Forward;
using mozilla::Maybe;
using mozilla::Move;
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(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(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);
    }
    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();

    // 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 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,

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

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(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. You may take ownership of the name by `mozilla::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 |JSCompartment|s.
    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::UniquePtr<EdgeRange> edges(JSContext* cx, bool wantNames) const override;
    JS::Zone* zone() const override;

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

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

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

// Define specializations for some commonly-used public JSAPI types.
// These can use the generic templates above.
template<>
class JS_PUBLIC_API(Concrete<JS::Symbol>) : TracerConcrete<JS::Symbol> {
  protected:
    explicit Concrete(JS::Symbol* ptr) : TracerConcrete(ptr) { }

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

    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;

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

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

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

    CoarseType coarseType() const final { return CoarseType::Script; }
    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
    const char* scriptFilename() const final;

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

// The JSObject specialization.
template<>
class JS_PUBLIC_API(Concrete<JSObject>) : public TracerConcreteWithCompartment<JSObject> {
  protected:
    explicit Concrete(JSObject* ptr) : TracerConcreteWithCompartment(ptr) { }

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

    const char* jsObjectClassName() const override;
    MOZ_MUST_USE bool jsObjectConstructorName(JSContext* cx, UniqueTwoByteChars& 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; }

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

// For JSString, we extend the generic template with a 'size' implementation.
template<>
class JS_PUBLIC_API(Concrete<JSString>) : TracerConcrete<JSString> {
  protected:
    explicit Concrete(JSString *ptr) : TracerConcrete<JSString>(ptr) { }

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

    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;

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

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

// The ubi::Node null pointer. Any attempt to operate on a null ubi::Node asserts.
template<>
class JS_PUBLIC_API(Concrete<void>) : public Base {
    const char16_t* typeName() const override;
    Size size(mozilla::MallocSizeOf mallocSizeOf) const override;
    js::UniquePtr<EdgeRange> edges(JSContext* cx, 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); }
};


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