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.

Mercurial (7b5b4eed4707)

VCS Links

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
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * 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/. */

/* TypeSet classes and functions. */

#ifndef vm_TypeSet_h
#define vm_TypeSet_h

#include "mozilla/Assertions.h"  // MOZ_ASSERT
#include "mozilla/Attributes.h"  // MOZ_ALWAYS_INLINE
#include "mozilla/Likely.h"      // MOZ_UNLIKELY

#include <stdint.h>  // intptr_t, uintptr_t, uint8_t, uint32_t
#include <stdio.h>   // FILE

#include "jstypes.h"  // JS_BITS_PER_WORD
#include "jsutil.h"   // JS_CRASH_DIAGNOSTICS

#include "jit/IonTypes.h"      // jit::MIRType
#include "js/GCAnnotations.h"  // JS_HAZ_GC_POINTER
#include "js/Id.h"
#include "js/TracingAPI.h"   // JSTracer
#include "js/TypeDecls.h"    // IF_BIGINT
#include "js/Utility.h"      // UniqueChars
#include "js/Value.h"        // JSVAL_TYPE_*
#include "js/Vector.h"       // js::Vector
#include "vm/TaggedProto.h"  // js::TaggedProto

struct JSContext;
class JSObject;

namespace JS {

class Compartment;
class Realm;
class Zone;

}  // namespace JS

namespace js {

namespace jit {

struct IonScript;
class TempAllocator;

}  // namespace jit

class AutoClearTypeInferenceStateOnOOM;
class AutoSweepBase;
class AutoSweepObjectGroup;
class CompilerConstraintList;
class HeapTypeSetKey;
class LifoAlloc;
class ObjectGroup;
class SystemAllocPolicy;
class TypeConstraint;
class TypeNewScript;
class TypeZone;

/*
 * Type inference memory management overview.
 *
 * Type information about the values observed within scripts and about the
 * contents of the heap is accumulated as the program executes. Compilation
 * accumulates constraints relating type information on the heap with the
 * compilations that should be invalidated when those types change. Type
 * information and constraints are allocated in the zone's typeLifoAlloc,
 * and on GC all data referring to live things is copied into a new allocator.
 * Thus, type set and constraints only hold weak references.
 */

/* Flags and other state stored in TypeSet::flags */
enum : uint32_t {
  TYPE_FLAG_UNDEFINED = 0x1,
  TYPE_FLAG_NULL = 0x2,
  TYPE_FLAG_BOOLEAN = 0x4,
  TYPE_FLAG_INT32 = 0x8,
  TYPE_FLAG_DOUBLE = 0x10,
  TYPE_FLAG_STRING = 0x20,
  TYPE_FLAG_SYMBOL = 0x40,
  TYPE_FLAG_BIGINT = 0x80,
  TYPE_FLAG_LAZYARGS = 0x100,
  TYPE_FLAG_ANYOBJECT = 0x200,

  /* Mask containing all "immediate" primitives (not heap-allocated) */
  TYPE_FLAG_PRIMITIVE_IMMEDIATE = TYPE_FLAG_UNDEFINED | TYPE_FLAG_NULL |
                                  TYPE_FLAG_BOOLEAN | TYPE_FLAG_INT32 |
                                  TYPE_FLAG_DOUBLE,
  /* Mask containing all GCThing primitives (heap-allocated) */
  TYPE_FLAG_PRIMITIVE_GCTHING =
      TYPE_FLAG_STRING | TYPE_FLAG_SYMBOL | TYPE_FLAG_BIGINT,

  /* Mask containing all primitives */
  TYPE_FLAG_PRIMITIVE =
      TYPE_FLAG_PRIMITIVE_IMMEDIATE | TYPE_FLAG_PRIMITIVE_GCTHING,

  /* Mask/shift for the number of objects in objectSet */
  TYPE_FLAG_OBJECT_COUNT_MASK = 0x3c00,
  TYPE_FLAG_OBJECT_COUNT_SHIFT = 10,
  TYPE_FLAG_OBJECT_COUNT_LIMIT = 7,
  TYPE_FLAG_DOMOBJECT_COUNT_LIMIT =
      TYPE_FLAG_OBJECT_COUNT_MASK >> TYPE_FLAG_OBJECT_COUNT_SHIFT,

  /* Whether the contents of this type set are totally unknown. */
  TYPE_FLAG_UNKNOWN = 0x00004000,

  /* Mask of normal type flags on a type set. */
  TYPE_FLAG_BASE_MASK = TYPE_FLAG_PRIMITIVE | TYPE_FLAG_LAZYARGS |
                        TYPE_FLAG_ANYOBJECT | TYPE_FLAG_UNKNOWN,

  /* Additional flags for HeapTypeSet sets. */

  /*
   * Whether the property has ever been deleted or reconfigured to behave
   * differently from a plain data property, other than making the property
   * non-writable.
   */
  TYPE_FLAG_NON_DATA_PROPERTY = 0x00008000,

  /* Whether the property has ever been made non-writable. */
  TYPE_FLAG_NON_WRITABLE_PROPERTY = 0x00010000,

  /* Whether the property might not be constant. */
  TYPE_FLAG_NON_CONSTANT_PROPERTY = 0x00020000,

  /*
   * Whether the property is definitely in a particular slot on all objects
   * from which it has not been deleted or reconfigured. For singletons
   * this may be a fixed or dynamic slot, and for other objects this will be
   * a fixed slot.
   *
   * If the property is definite, mask and shift storing the slot + 1.
   * Otherwise these bits are clear.
   */
  TYPE_FLAG_DEFINITE_MASK = 0xfffc0000,
  TYPE_FLAG_DEFINITE_SHIFT = 18
};
using TypeFlags = uint32_t;

static_assert(
    TYPE_FLAG_PRIMITIVE < TYPE_FLAG_ANYOBJECT &&
        TYPE_FLAG_LAZYARGS < TYPE_FLAG_ANYOBJECT,
    "TYPE_FLAG_ANYOBJECT should be greater than primitive type flags");

/* Flags and other state stored in ObjectGroup::Flags */
enum : uint32_t {
  /* Whether this group is associated with some allocation site. */
  OBJECT_FLAG_FROM_ALLOCATION_SITE = 0x1,

  /* Whether this group is associated with a single object. */
  OBJECT_FLAG_SINGLETON = 0x2,

  /*
   * Whether this group is used by objects whose singleton groups have not
   * been created yet.
   */
  OBJECT_FLAG_LAZY_SINGLETON = 0x4,

  /* Mask/shift for the number of properties in propertySet */
  OBJECT_FLAG_PROPERTY_COUNT_MASK = 0xfff8,
  OBJECT_FLAG_PROPERTY_COUNT_SHIFT = 3,
  OBJECT_FLAG_PROPERTY_COUNT_LIMIT =
      OBJECT_FLAG_PROPERTY_COUNT_MASK >> OBJECT_FLAG_PROPERTY_COUNT_SHIFT,

  /* Whether any objects this represents may have sparse indexes. */
  OBJECT_FLAG_SPARSE_INDEXES = 0x00010000,

  /* Whether any objects this represents may not have packed dense elements. */
  OBJECT_FLAG_NON_PACKED = 0x00020000,

  /*
   * Whether any objects this represents may be arrays whose length does not
   * fit in an int32.
   */
  OBJECT_FLAG_LENGTH_OVERFLOW = 0x00040000,

  /* Whether any objects have been iterated over. */
  OBJECT_FLAG_ITERATED = 0x00080000,

  /* Whether any object this represents may have non-extensible elements. */
  OBJECT_FLAG_NON_EXTENSIBLE_ELEMENTS = 0x00100000,

  // (0x00200000 is unused)

  /*
   * For a global object, whether any array buffers in this compartment with
   * typed object views have ever been detached.
   */
  OBJECT_FLAG_TYPED_OBJECT_HAS_DETACHED_BUFFER = 0x00400000,

  /*
   * Whether objects with this type should be allocated directly in the
   * tenured heap.
   */
  OBJECT_FLAG_PRE_TENURE = 0x00800000,

  /* Whether objects with this type might have copy on write elements. */
  OBJECT_FLAG_COPY_ON_WRITE = 0x01000000,

  /* Whether this type has had its 'new' script cleared in the past. */
  OBJECT_FLAG_NEW_SCRIPT_CLEARED = 0x02000000,

  /*
   * Whether all properties of this object are considered unknown.
   * If set, all other flags in DYNAMIC_MASK will also be set.
   */
  OBJECT_FLAG_UNKNOWN_PROPERTIES = 0x04000000,

  /* Flags which indicate dynamic properties of represented objects. */
  OBJECT_FLAG_DYNAMIC_MASK = 0x07ff0000,

  // Mask/shift for the kind of addendum attached to this group.
  OBJECT_FLAG_ADDENDUM_MASK = 0x38000000,
  OBJECT_FLAG_ADDENDUM_SHIFT = 27,

  // Mask/shift for this group's generation. If out of sync with the
  // TypeZone's generation, this group hasn't been swept yet.
  OBJECT_FLAG_GENERATION_MASK = 0x40000000,
  OBJECT_FLAG_GENERATION_SHIFT = 30,
};
using ObjectGroupFlags = uint32_t;

class StackTypeSet;
class HeapTypeSet;
class TemporaryTypeSet;

/*
 * [SMDOC] Type-Inference TypeSet
 *
 * Information about the set of types associated with an lvalue. There are
 * three kinds of type sets:
 *
 * - StackTypeSet are associated with JitScripts, for arguments and values
 *   observed at property reads. These are implicitly frozen on compilation
 *   and only have constraints added to them which can trigger invalidation of
 *   TypeNewScript information.
 *
 * - HeapTypeSet are associated with the properties of ObjectGroups. These
 *   may have constraints added to them to trigger invalidation of either
 *   compiled code or TypeNewScript information.
 *
 * - TemporaryTypeSet are created during compilation and do not outlive
 *   that compilation.
 *
 * The contents of a type set completely describe the values that a particular
 * lvalue might have, except for the following cases:
 *
 * - If an object's prototype or class is dynamically mutated, its group will
 *   change. Type sets containing the old group will not necessarily contain
 *   the new group. When this occurs, the properties of the old and new group
 *   will both be marked as unknown, which will prevent Ion from optimizing
 *   based on the object's type information.
 */
class TypeSet {
 protected:
  /* Flags for this type set. */
  TypeFlags flags = 0;

 public:
  class ObjectKey;

 protected:
  /* Possible objects this type set can represent. */
  ObjectKey** objectSet = nullptr;

 public:
  TypeSet() = default;

  // Type set entry for either a JSObject with singleton type or a
  // non-singleton ObjectGroup.
  class ObjectKey {
   public:
    static intptr_t keyBits(ObjectKey* obj) { return (intptr_t)obj; }
    static ObjectKey* getKey(ObjectKey* obj) { return obj; }

    static inline ObjectKey* get(JSObject* obj);
    static inline ObjectKey* get(ObjectGroup* group);

    bool isGroup() { return (uintptr_t(this) & 1) == 0; }
    bool isSingleton() { return (uintptr_t(this) & 1) != 0; }
    static constexpr uintptr_t TypeHashSetMarkBit = 1 << 1;

    inline ObjectGroup* group();
    inline JSObject* singleton();

    inline ObjectGroup* groupNoBarrier();
    inline JSObject* singletonNoBarrier();

    const JSClass* clasp();
    TaggedProto proto();
    TypeNewScript* newScript();

    bool unknownProperties();
    bool hasFlags(CompilerConstraintList* constraints, ObjectGroupFlags flags);
    bool hasStableClassAndProto(CompilerConstraintList* constraints);
    void watchStateChangeForTypedArrayData(CompilerConstraintList* constraints);
    HeapTypeSetKey property(jsid id);
    void ensureTrackedProperty(JSContext* cx, jsid id);

    ObjectGroup* maybeGroup();

    JS::Compartment* maybeCompartment();
  } JS_HAZ_GC_POINTER;

  // Information about a single concrete type. We pack this into one word,
  // where small values are particular primitive or other singleton types and
  // larger values are either specific JS objects or object groups.
  class Type {
    friend class TypeSet;

    uintptr_t data;
    explicit Type(uintptr_t data) : data(data) {}

   public:
    uintptr_t raw() const { return data; }

    bool isPrimitive() const { return data < JSVAL_TYPE_OBJECT; }

    bool isPrimitive(ValueType type) const {
      MOZ_ASSERT(type != ValueType::Object);
      return uintptr_t(type) == data;
    }

    ValueType primitive() const {
      MOZ_ASSERT(isPrimitive());
      return ValueType(data);
    }

    bool isMagicArguments() const { return primitive() == ValueType::Magic; }

    bool isSomeObject() const {
      return data == JSVAL_TYPE_OBJECT || data > JSVAL_TYPE_UNKNOWN;
    }

    bool isAnyObject() const { return data == JSVAL_TYPE_OBJECT; }

    bool isUnknown() const { return data == JSVAL_TYPE_UNKNOWN; }

    /* Accessors for types that are either JSObject or ObjectGroup. */

    bool isObject() const {
      MOZ_ASSERT(!isAnyObject() && !isUnknown());
      return data > JSVAL_TYPE_UNKNOWN;
    }

    bool isObjectUnchecked() const { return data > JSVAL_TYPE_UNKNOWN; }

    inline ObjectKey* objectKey() const;

    /* Accessors for JSObject types */

    bool isSingleton() const { return isObject() && !!(data & 1); }
    bool isSingletonUnchecked() const {
      return isObjectUnchecked() && !!(data & 1);
    }

    inline JSObject* singleton() const;
    inline JSObject* singletonNoBarrier() const;

    /* Accessors for ObjectGroup types */

    bool isGroup() const { return isObject() && !(data & 1); }
    bool isGroupUnchecked() const { return isObjectUnchecked() && !(data & 1); }

    inline ObjectGroup* group() const;
    inline ObjectGroup* groupNoBarrier() const;

    inline void trace(JSTracer* trc);

    JS::Compartment* maybeCompartment();

    bool operator==(Type o) const { return data == o.data; }
    bool operator!=(Type o) const { return data != o.data; }
  } JS_HAZ_GC_POINTER;

  static inline Type UndefinedType() { return Type(JSVAL_TYPE_UNDEFINED); }
  static inline Type NullType() { return Type(JSVAL_TYPE_NULL); }
  static inline Type BooleanType() { return Type(JSVAL_TYPE_BOOLEAN); }
  static inline Type Int32Type() { return Type(JSVAL_TYPE_INT32); }
  static inline Type DoubleType() { return Type(JSVAL_TYPE_DOUBLE); }
  static inline Type StringType() { return Type(JSVAL_TYPE_STRING); }
  static inline Type SymbolType() { return Type(JSVAL_TYPE_SYMBOL); }
  static inline Type BigIntType() { return Type(JSVAL_TYPE_BIGINT); }
  static inline Type MagicArgType() { return Type(JSVAL_TYPE_MAGIC); }
  static inline Type AnyObjectType() { return Type(JSVAL_TYPE_OBJECT); }
  static inline Type UnknownType() { return Type(JSVAL_TYPE_UNKNOWN); }

  static inline Type PrimitiveType(JSValueType type) {
    MOZ_ASSERT(type < JSVAL_TYPE_UNKNOWN);
    return Type(type);
  }

  static inline Type ObjectType(const JSObject* obj);
  static inline Type ObjectType(const ObjectGroup* group);
  static inline Type ObjectType(const ObjectKey* key);

  static const char* NonObjectTypeString(Type type);

  static JS::UniqueChars TypeString(const Type type);
  static JS::UniqueChars ObjectGroupString(const ObjectGroup* group);

 public:
  void print(FILE* fp = stderr);

  /* Whether this set contains a specific type. */
  MOZ_ALWAYS_INLINE bool hasType(Type type) const;

  TypeFlags baseFlags() const { return flags & TYPE_FLAG_BASE_MASK; }
  bool unknown() const { return !!(flags & TYPE_FLAG_UNKNOWN); }
  bool unknownObject() const {
    return !!(flags & (TYPE_FLAG_UNKNOWN | TYPE_FLAG_ANYOBJECT));
  }
  bool empty() const { return !baseFlags() && !baseObjectCount(); }

  bool hasAnyFlag(TypeFlags flags) const {
    MOZ_ASSERT((flags & TYPE_FLAG_BASE_MASK) == flags);
    return !!(baseFlags() & flags);
  }

  bool nonDataProperty() const { return flags & TYPE_FLAG_NON_DATA_PROPERTY; }
  bool nonWritableProperty() const {
    return flags & TYPE_FLAG_NON_WRITABLE_PROPERTY;
  }
  bool nonConstantProperty() const {
    return flags & TYPE_FLAG_NON_CONSTANT_PROPERTY;
  }
  bool definiteProperty() const { return flags & TYPE_FLAG_DEFINITE_MASK; }
  unsigned definiteSlot() const {
    MOZ_ASSERT(definiteProperty());
    return (flags >> TYPE_FLAG_DEFINITE_SHIFT) - 1;
  }

  // Join two type sets into a new set. The result should not be modified
  // further.
  static TemporaryTypeSet* unionSets(TypeSet* a, TypeSet* b, LifoAlloc* alloc);

  // Return the intersection of the 2 TypeSets. The result should not be
  // modified further.
  static TemporaryTypeSet* intersectSets(TemporaryTypeSet* a,
                                         TemporaryTypeSet* b, LifoAlloc* alloc);

  /*
   * Returns a copy of TypeSet a excluding/removing the types in TypeSet b.
   * TypeSet b can only contain primitives or be any object. No support for
   * specific objects. The result should not be modified further.
   */
  static TemporaryTypeSet* removeSet(TemporaryTypeSet* a, TemporaryTypeSet* b,
                                     LifoAlloc* alloc);

  /* Add a type to this set using the specified allocator. */
  void addType(Type type, LifoAlloc* alloc);

  /* Get a list of all types in this set. */
  using TypeList = Vector<Type, 1, SystemAllocPolicy>;
  template <class TypeListT>
  bool enumerateTypes(TypeListT* list) const;

  /*
   * Iterate through the objects in this set. getObjectCount overapproximates
   * in the hash case (see SET_ARRAY_SIZE in TypeInference-inl.h), and
   * getObject may return nullptr.
   */
  inline unsigned getObjectCount() const;
  inline bool hasGroup(unsigned i) const;
  inline bool hasSingleton(unsigned i) const;
  inline ObjectKey* getObject(unsigned i) const;
  inline JSObject* getSingleton(unsigned i) const;
  inline ObjectGroup* getGroup(unsigned i) const;

  /*
   * Get the objects in the set without triggering barriers. This is
   * potentially unsafe and you should only call these methods if you know
   * what you're doing. For JIT compilation, use the following methods
   * instead:
   *  - MacroAssembler::getSingletonAndDelayBarrier()
   *  - MacroAssembler::getGroupAndDelayBarrier()
   */
  inline JSObject* getSingletonNoBarrier(unsigned i) const;
  inline ObjectGroup* getGroupNoBarrier(unsigned i) const;

  /* The Class of an object in this set. */
  inline const JSClass* getObjectClass(unsigned i) const;

  bool canSetDefinite(unsigned slot) {
    // Note: the cast is required to work around an MSVC issue.
    return (slot + 1) <=
           (unsigned(TYPE_FLAG_DEFINITE_MASK) >> TYPE_FLAG_DEFINITE_SHIFT);
  }
  void setDefinite(unsigned slot) {
    MOZ_ASSERT(canSetDefinite(slot));
    flags |= ((slot + 1) << TYPE_FLAG_DEFINITE_SHIFT);
    MOZ_ASSERT(definiteSlot() == slot);
  }

  /* Whether any values in this set might have the specified type. */
  bool mightBeMIRType(jit::MIRType type) const;

  /*
   * Get whether this type set is known to be a subset of other.
   * This variant doesn't freeze constraints. That variant is called knownSubset
   */
  bool isSubset(const TypeSet* other) const;

  /*
   * Get whether the objects in this TypeSet are a subset of the objects
   * in other.
   */
  bool objectsAreSubset(TypeSet* other);

  /* Whether this TypeSet contains exactly the same types as other. */
  bool equals(const TypeSet* other) const {
    return this->isSubset(other) && other->isSubset(this);
  }

  bool objectsIntersect(const TypeSet* other) const;

  /* Forward all types in this set to the specified constraint. */
  bool addTypesToConstraint(JSContext* cx, TypeConstraint* constraint);

  // Clone a type set into an arbitrary allocator.
  TemporaryTypeSet* clone(LifoAlloc* alloc) const;

  // |*result| is not even partly initialized when this function is called:
  // this function placement-new's its contents into existence.
  bool cloneIntoUninitialized(LifoAlloc* alloc, TemporaryTypeSet* result) const;

  // Create a new TemporaryTypeSet where undefined and/or null has been filtered
  // out.
  TemporaryTypeSet* filter(LifoAlloc* alloc, bool filterUndefined,
                           bool filterNull) const;
  // Create a new TemporaryTypeSet where the type has been set to object.
  TemporaryTypeSet* cloneObjectsOnly(LifoAlloc* alloc);
  TemporaryTypeSet* cloneWithoutObjects(LifoAlloc* alloc);

  JS::Compartment* maybeCompartment();

  // Trigger a read barrier on all the contents of a type set.
  static void readBarrier(const TypeSet* types);

 protected:
  uint32_t baseObjectCount() const {
    return (flags & TYPE_FLAG_OBJECT_COUNT_MASK) >>
           TYPE_FLAG_OBJECT_COUNT_SHIFT;
  }
  inline void setBaseObjectCount(uint32_t count);

  void clearObjects();

 public:
  static inline Type GetValueType(const JS::Value& val);

  static inline bool IsUntrackedValue(const JS::Value& val);

  // Get the type of a possibly optimized out or uninitialized let value.
  // This generally only happens on unconditional type monitors on bailing
  // out of Ion, such as for argument and local types.
  static inline Type GetMaybeUntrackedValueType(const JS::Value& val);

  static bool IsTypeMarked(JSRuntime* rt, Type* v);
  static bool IsTypeAboutToBeFinalized(Type* v);
} JS_HAZ_GC_POINTER;

#if JS_BITS_PER_WORD == 32
static const uintptr_t BaseTypeInferenceMagic = 0xa1a2b3b4;
#else
static const uintptr_t BaseTypeInferenceMagic = 0xa1a2b3b4c5c6d7d8;
#endif
static const uintptr_t TypeConstraintMagic = BaseTypeInferenceMagic + 1;
static const uintptr_t ConstraintTypeSetMagic = BaseTypeInferenceMagic + 2;

#ifdef JS_CRASH_DIAGNOSTICS
extern void ReportMagicWordFailure(uintptr_t actual, uintptr_t expected);
extern void ReportMagicWordFailure(uintptr_t actual, uintptr_t expected,
                                   uintptr_t flags, uintptr_t objectSet);
#endif

/*
 * A constraint which listens to additions to a type set and propagates those
 * changes to other type sets.
 */
class TypeConstraint {
 private:
#ifdef JS_CRASH_DIAGNOSTICS
  uintptr_t magic_ = TypeConstraintMagic;
#endif

  /* Next constraint listening to the same type set. */
  TypeConstraint* next_ = nullptr;

 public:
  TypeConstraint() = default;

  void checkMagic() const {
#ifdef JS_CRASH_DIAGNOSTICS
    if (MOZ_UNLIKELY(magic_ != TypeConstraintMagic)) {
      ReportMagicWordFailure(magic_, TypeConstraintMagic);
    }
#endif
  }

  TypeConstraint* next() const {
    checkMagic();
    if (next_) {
      next_->checkMagic();
    }
    return next_;
  }
  void setNext(TypeConstraint* next) {
    MOZ_ASSERT(!next_);
    checkMagic();
    if (next) {
      next->checkMagic();
    }
    next_ = next;
  }

  /* Debugging name for this kind of constraint. */
  virtual const char* kind() = 0;

  /* Register a new type for the set this constraint is listening to. */
  virtual void newType(JSContext* cx, TypeSet* source, TypeSet::Type type) = 0;

  /*
   * For constraints attached to an object property's type set, mark the
   * property as having changed somehow.
   */
  virtual void newPropertyState(JSContext* cx, TypeSet* source) {}

  /*
   * For constraints attached to the JSID_EMPTY type set on an object,
   * indicate a change in one of the object's dynamic property flags or other
   * state.
   */
  virtual void newObjectState(JSContext* cx, ObjectGroup* group) {}

  /*
   * If the data this constraint refers to is still live, copy it into the
   * zone's new allocator. Type constraints only hold weak references.
   */
  virtual bool sweep(TypeZone& zone, TypeConstraint** res) = 0;

  /* The associated compartment, if any. */
  virtual JS::Compartment* maybeCompartment() = 0;
};

/* Superclass common to stack and heap type sets. */
class ConstraintTypeSet : public TypeSet {
 private:
#ifdef JS_CRASH_DIAGNOSTICS
  uintptr_t magic_ = ConstraintTypeSetMagic;
#endif

 protected:
  /* Chain of constraints which propagate changes out from this type set. */
  TypeConstraint* constraintList_ = nullptr;

 public:
  ConstraintTypeSet() = default;

  void checkMagic() const {
#ifdef JS_CRASH_DIAGNOSTICS
    if (MOZ_UNLIKELY(magic_ != ConstraintTypeSetMagic)) {
      ReportMagicWordFailure(magic_, ConstraintTypeSetMagic, uintptr_t(flags),
                             uintptr_t(objectSet));
    }
#endif
  }

  // This takes a reference to AutoSweepBase to ensure we swept the owning
  // ObjectGroup or JitScript.
  TypeConstraint* constraintList(const AutoSweepBase& sweep) const {
    checkMagic();
    if (constraintList_) {
      constraintList_->checkMagic();
    }
    return constraintList_;
  }
  void setConstraintList(TypeConstraint* constraint) {
    MOZ_ASSERT(!constraintList_);
    checkMagic();
    if (constraint) {
      constraint->checkMagic();
    }
    constraintList_ = constraint;
  }

  /*
   * Add a type to this set, calling any constraint handlers if this is a new
   * possible type.
   */
  void addType(const AutoSweepBase& sweep, JSContext* cx, Type type);

  /* Generalize to any type. */
  void makeUnknown(const AutoSweepBase& sweep, JSContext* cx) {
    addType(sweep, cx, UnknownType());
  }

  // Trigger a post barrier when writing to this set, if necessary.
  // addType(cx, type) takes care of this automatically.
  void postWriteBarrier(JSContext* cx, Type type);

  /* Add a new constraint to this set. */
  bool addConstraint(JSContext* cx, TypeConstraint* constraint,
                     bool callExisting = true);

  inline void sweep(const AutoSweepBase& sweep, JS::Zone* zone);
  inline void trace(JS::Zone* zone, JSTracer* trc);
};

class StackTypeSet : public ConstraintTypeSet {
 public:
};

class HeapTypeSet : public ConstraintTypeSet {
  inline void newPropertyState(const AutoSweepObjectGroup& sweep,
                               JSContext* cx);

 public:
  /* Mark this type set as representing a non-data property. */
  inline void setNonDataProperty(const AutoSweepObjectGroup& sweep,
                                 JSContext* cx);

  /* Mark this type set as representing a non-writable property. */
  inline void setNonWritableProperty(const AutoSweepObjectGroup& sweep,
                                     JSContext* cx);

  // Mark this type set as being non-constant.
  inline void setNonConstantProperty(const AutoSweepObjectGroup& sweep,
                                     JSContext* cx);
};

enum class DOMObjectKind : uint8_t { Proxy, Native, Unknown };

class TemporaryTypeSet : public TypeSet {
 public:
  TemporaryTypeSet() {}
  TemporaryTypeSet(LifoAlloc* alloc, Type type);

  TemporaryTypeSet(uint32_t flags, ObjectKey** objectSet) {
    this->flags = flags;
    this->objectSet = objectSet;
  }

  TemporaryTypeSet(LifoAlloc* alloc, jit::MIRType type)
      : TemporaryTypeSet(alloc, PrimitiveType(ValueTypeFromMIRType(type))) {
    MOZ_ASSERT(type != jit::MIRType::Value);
  }

  /*
   * Constraints for JIT compilation.
   *
   * Methods for JIT compilation. These must be used when a script is
   * currently being compiled (see AutoEnterCompilation) and will add
   * constraints ensuring that if the return value change in the future due
   * to new type information, the script's jitcode will be discarded.
   */

  /* Get any type tag which all values in this set must have. */
  jit::MIRType getKnownMIRType();

  bool isMagicArguments() {
    return getKnownMIRType() == jit::MIRType::MagicOptimizedArguments;
  }

  /* Whether this value may be an object. */
  bool maybeObject() { return unknownObject() || baseObjectCount() > 0; }

  /*
   * Whether this typeset represents a potentially sentineled object value:
   * the value may be an object or null or undefined.
   * Returns false if the value cannot ever be an object.
   */
  bool objectOrSentinel() {
    TypeFlags flags =
        TYPE_FLAG_UNDEFINED | TYPE_FLAG_NULL | TYPE_FLAG_ANYOBJECT;
    if (baseFlags() & (~flags & TYPE_FLAG_BASE_MASK)) {
      return false;
    }

    return hasAnyFlag(TYPE_FLAG_ANYOBJECT) || baseObjectCount() > 0;
  }

  /* Whether the type set contains objects with any of a set of flags. */
  bool hasObjectFlags(CompilerConstraintList* constraints,
                      ObjectGroupFlags flags);

  /* Get the class shared by all objects in this set, or nullptr. */
  const JSClass* getKnownClass(CompilerConstraintList* constraints);

  /*
   * Get the realm shared by all objects in this set, or nullptr. Returns
   * nullptr if the set contains proxies (because cross-compartment wrappers
   * don't have a single realm associated with them).
   */
  JS::Realm* getKnownRealm(CompilerConstraintList* constraints);

  /* Result returned from forAllClasses */
  enum ForAllResult {
    EMPTY = 1,  // Set empty
    ALL_TRUE,   // Set not empty and predicate returned true for all classes
    ALL_FALSE,  // Set not empty and predicate returned false for all classes
    MIXED,      // Set not empty and predicate returned false for some classes
                // and true for others, or set contains an unknown or non-object
                // type
  };

  /* Apply func to the members of the set and return an appropriate result.
   * The iteration may end early if the result becomes known early.
   */
  ForAllResult forAllClasses(CompilerConstraintList* constraints,
                             bool (*func)(const JSClass* clasp));

  /*
   * Returns true if all objects in this set have the same prototype, and
   * assigns this object to *proto. The proto can be nullptr.
   */
  bool getCommonPrototype(CompilerConstraintList* constraints,
                          JSObject** proto);

  /* Whether the buffer mapped by a TypedArray is shared memory or not */
  enum TypedArraySharedness {
    UnknownSharedness = 1,  // We can't determine sharedness
    KnownShared,            // We know for sure the buffer is shared
    KnownUnshared           // We know for sure the buffer is unshared
  };

  /*
   * Get the typed array type of all objects in this set, or
   * Scalar::MaxTypedArrayViewType. If there is such a common type and
   * sharedness is not nullptr then *sharedness is set to what we know about the
   * sharedness of the memory.
   */
  Scalar::Type getTypedArrayType(CompilerConstraintList* constraints,
                                 TypedArraySharedness* sharedness = nullptr);

  // Whether all objects have JSCLASS_IS_DOMJSCLASS set.
  bool isDOMClass(CompilerConstraintList* constraints, DOMObjectKind* kind);

  // Whether clasp->isCallable() is true for one or more objects in this set.
  bool maybeCallable(CompilerConstraintList* constraints);

  // Whether clasp->emulatesUndefined() is true for one or more objects in
  // this set.
  bool maybeEmulatesUndefined(CompilerConstraintList* constraints);

  // Get the single value which can appear in this type set, otherwise
  // nullptr.
  JSObject* maybeSingleton();
  ObjectKey* maybeSingleObject();

  // Whether any objects in the type set needs a barrier on id.
  bool propertyNeedsBarrier(CompilerConstraintList* constraints, jsid id);

  // Whether this set contains all types in other, except (possibly) the
  // specified type.
  bool filtersType(const TemporaryTypeSet* other, Type type) const;

  enum DoubleConversion {
    /* All types in the set should use eager double conversion. */
    AlwaysConvertToDoubles,

    /* Some types in the set should use eager double conversion. */
    MaybeConvertToDoubles,

    /* No types should use eager double conversion. */
    DontConvertToDoubles,

    /* Some types should use eager double conversion, others cannot. */
    AmbiguousDoubleConversion
  };

  /*
   * Whether known double optimizations are possible for element accesses on
   * objects in this type set.
   */
  DoubleConversion convertDoubleElements(CompilerConstraintList* constraints);

 private:
  void getTypedArraySharedness(CompilerConstraintList* constraints,
                               TypedArraySharedness* sharedness);
};

// Representation of a heap type property which may or may not be instantiated.
// Heap properties for singleton types are instantiated lazily as they are used
// by the compiler, but this is only done on the main thread. If we are
// compiling off thread and use a property which has not yet been instantiated,
// it will be treated as empty and non-configured and will be instantiated when
// rejoining to the main thread. If it is in fact not empty, the compilation
// will fail; to avoid this, we try to instantiate singleton property types
// during generation of baseline caches.
class HeapTypeSetKey {
  friend class TypeSet::ObjectKey;

  // Object and property being accessed.
  TypeSet::ObjectKey* object_;
  jsid id_;

  // If instantiated, the underlying heap type set.
  HeapTypeSet* maybeTypes_;

 public:
  HeapTypeSetKey() : object_(nullptr), id_(JSID_EMPTY), maybeTypes_(nullptr) {}

  TypeSet::ObjectKey* object() const { return object_; }
  jsid id() const { return id_; }

  HeapTypeSet* maybeTypes() const {
    if (maybeTypes_) {
      maybeTypes_->checkMagic();
    }
    return maybeTypes_;
  }

  bool instantiate(JSContext* cx);

  void freeze(CompilerConstraintList* constraints);
  jit::MIRType knownMIRType(CompilerConstraintList* constraints);
  bool nonData(CompilerConstraintList* constraints);
  bool nonWritable(CompilerConstraintList* constraints);
  bool isOwnProperty(CompilerConstraintList* constraints,
                     bool allowEmptyTypesForGlobal = false);
  bool knownSubset(CompilerConstraintList* constraints,
                   const HeapTypeSetKey& other);
  JSObject* singleton(CompilerConstraintList* constraints);
  bool needsBarrier(CompilerConstraintList* constraints);
  bool constant(CompilerConstraintList* constraints, Value* valOut);
  bool couldBeConstant(CompilerConstraintList* constraints);
};

} /* namespace js */

#endif /* vm_TypeSet_h */