js/src/jsinfer.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set ts=8 sts=4 et sw=4 tw=99:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "jsinferinlines.h"
   8
   9 #include "mozilla/DebugOnly.h"
  10 #include "mozilla/MemoryReporting.h"
  11 #include "mozilla/PodOperations.h"
  12
  13 #include "jsapi.h"
  14 #include "jscntxt.h"
  15 #include "jsgc.h"
  16 #include "jshashutil.h"
  17 #include "jsobj.h"
  18 #include "jsprf.h"
  19 #include "jsscript.h"
  20 #include "jsstr.h"
  21 #include "prmjtime.h"
  22
  23 #include "gc/Marking.h"
  24 #include "jit/BaselineJIT.h"
  25 #include "jit/Ion.h"
  26 #include "jit/IonAnalysis.h"
  27 #include "jit/JitCompartment.h"
  28 #include "js/MemoryMetrics.h"
  29 #include "vm/HelperThreads.h"
  30 #include "vm/Opcodes.h"
  31 #include "vm/Shape.h"
  32
  33 #include "jsatominlines.h"
  34 #include "jsgcinlines.h"
  35 #include "jsobjinlines.h"
  36 #include "jsscriptinlines.h"
  37
  38 #include "jit/ExecutionMode-inl.h"
  39
  40 using namespace js;
  41 using namespace js::gc;
  42 using namespace js::types;
  43
  44 using mozilla::DebugOnly;
  45 using mozilla::Maybe;
  46 using mozilla::PodArrayZero;
  47 using mozilla::PodCopy;
  48 using mozilla::PodZero;
  49
  50 static inline jsid
  51 id_prototype(JSContext* cx) {
  52     return NameToId(cx->names().prototype);
  53 }
  54
  55 static inline jsid
  56 id___proto__(JSContext* cx) {
  57     return NameToId(cx->names().proto);
  58 }
  59
  60 static inline jsid
  61 id_constructor(JSContext* cx) {
  62     return NameToId(cx->names().constructor);
  63 }
  64
  65 static inline jsid
  66 id_caller(JSContext* cx) {
  67     return NameToId(cx->names().caller);
  68 }
  69
  70 #ifdef DEBUG
  71 const char*
  72 types::TypeIdStringImpl(jsid id)
  73 {
  74     if (JSID_IS_VOID(id))
  75         return "(index)";
  76     if (JSID_IS_EMPTY(id))
  77         return "(new)";
  78     if (JSID_IS_SYMBOL(id))
  79         return "(symbol)";
  80     static char bufs[4][100];
  81     static unsigned which = 0;
  82     which = (which + 1) & 3;
  83     PutEscapedString(bufs[which], 100, JSID_TO_FLAT_STRING(id), 0);
  84     return bufs[which];
  85 }
  86 #endif
  87
  88 /////////////////////////////////////////////////////////////////////
  89 // Logging
  90 /////////////////////////////////////////////////////////////////////
  91
  92 #ifdef DEBUG
  93
  94 static bool InferSpewActive(SpewChannel channel)
  95 {
  96     static bool active[SPEW_COUNT];
  97     static bool checked = false;
  98     if (!checked) {
  99         checked = true;
 100         PodArrayZero(active);
 101         const char* env = getenv("INFERFLAGS");
 102         if (!env)
 103             return false;
 104         if (strstr(env, "ops"))
 105             active[ISpewOps] = true;
 106         if (strstr(env, "result"))
 107             active[ISpewResult] = true;
 108         if (strstr(env, "full")) {
 109             for (unsigned i = 0; i < SPEW_COUNT; i++)
 110                 active[i] = true;
 111         }
 112     }
 113     return active[channel];
 114 }
 115
 116 static bool InferSpewColorable()
 117 {
 118     /* Only spew colors on xterm-color to not screw up emacs. */
 119     static bool colorable = false;
 120     static bool checked = false;
 121     if (!checked) {
 122         checked = true;
 123         const char* env = getenv("TERM");
 124         if (!env)
 125             return false;
 126         if (strcmp(env, "xterm-color") == 0 || strcmp(env, "xterm-256color") == 0)
 127             colorable = true;
 128     }
 129     return colorable;
 130 }
 131
 132 const char*
 133 types::InferSpewColorReset()
 134 {
 135     if (!InferSpewColorable())
 136         return "";
 137     return "\x1b[0m";
 138 }
 139
 140 const char*
 141 types::InferSpewColor(TypeConstraint* constraint)
 142 {
 143     /* Type constraints are printed out using foreground colors. */
 144     static const char * const colors[] = { "\x1b[31m", "\x1b[32m", "\x1b[33m",
 145                                            "\x1b[34m", "\x1b[35m", "\x1b[36m",
 146                                            "\x1b[37m" };
 147     if (!InferSpewColorable())
 148         return "";
 149     return colors[DefaultHasher<TypeConstraint*>::hash(constraint) % 7];
 150 }
 151
 152 const char*
 153 types::InferSpewColor(TypeSet* types)
 154 {
 155     /* Type sets are printed out using bold colors. */
 156     static const char * const colors[] = { "\x1b[1;31m", "\x1b[1;32m", "\x1b[1;33m",
 157                                            "\x1b[1;34m", "\x1b[1;35m", "\x1b[1;36m",
 158                                            "\x1b[1;37m" };
 159     if (!InferSpewColorable())
 160         return "";
 161     return colors[DefaultHasher<TypeSet*>::hash(types) % 7];
 162 }
 163
 164 const char*
 165 types::TypeString(Type type)
 166 {
 167     if (type.isPrimitive()) {
 168         switch (type.primitive()) {
 169           case JSVAL_TYPE_UNDEFINED:
 170             return "void";
 171           case JSVAL_TYPE_NULL:
 172             return "null";
 173           case JSVAL_TYPE_BOOLEAN:
 174             return "bool";
 175           case JSVAL_TYPE_INT32:
 176             return "int";
 177           case JSVAL_TYPE_DOUBLE:
 178             return "float";
 179           case JSVAL_TYPE_STRING:
 180             return "string";
 181           case JSVAL_TYPE_SYMBOL:
 182             return "symbol";
 183           case JSVAL_TYPE_MAGIC:
 184             return "lazyargs";
 185           default:
 186             MOZ_ASSUME_UNREACHABLE("Bad type");
 187         }
 188     }
 189     if (type.isUnknown())
 190         return "unknown";
 191     if (type.isAnyObject())
 192         return " object";
 193
 194     static char bufs[4][40];
 195     static unsigned which = 0;
 196     which = (which + 1) & 3;
 197
 198     if (type.isSingleObject())
 199         JS_snprintf(bufs[which], 40, "<0x%p>", (void*) type.singleObject());
 200     else
 201         JS_snprintf(bufs[which], 40, "[0x%p]", (void*) type.typeObject());
 202
 203     return bufs[which];
 204 }
 205
 206 const char*
 207 types::TypeObjectString(TypeObject* type)
 208 {
 209     return TypeString(Type::ObjectType(type));
 210 }
 211
 212 unsigned JSScript::id() {
 213     if (!id_) {
 214         id_ = ++compartment()->types.scriptCount;
 215         InferSpew(ISpewOps, "script #%u: %p %s:%d",
 216                   id_, this, filename() ? filename() : "<null>", lineno());
 217     }
 218     return id_;
 219 }
 220
 221 void
 222 types::InferSpew(SpewChannel channel, const char* fmt, ...)
 223 {
 224     if (!InferSpewActive(channel))
 225         return;
 226
 227     va_list ap;
 228     va_start(ap, fmt);
 229     fprintf(stderr, "[infer] ");
 230     vfprintf(stderr, fmt, ap);
 231     fprintf(stderr, "\n");
 232     va_end(ap);
 233 }
 234
 235 bool
 236 types::TypeHasProperty(JSContext* cx, TypeObject* obj, jsid id, const Value& value)
 237 {
 238     /*
 239      * Check the correctness of the type information in the object's property
 240      * against an actual value.
 241      */
 242     if (!obj->unknownProperties() && !value.isUndefined()) {
 243         id = IdToTypeId(id);
 244
 245         /* Watch for properties which inference does not monitor. */
 246         if (id == id___proto__(cx) || id == id_constructor(cx) || id == id_caller(cx))
 247             return true;
 248
 249         Type type = GetValueType(value);
 250
 251         AutoEnterAnalysis enter(cx);
 252
 253         /*
 254          * We don't track types for properties inherited from prototypes which
 255          * haven't yet been accessed during analysis of the inheriting object.
 256          * Don't do the property instantiation now.
 257          */
 258         TypeSet* types = obj->maybeGetProperty(id);
 259         if (!types)
 260             return true;
 261
 262         if (!types->hasType(type)) {
 263             TypeFailure(cx, "Missing type in object %s %s: %s",
 264                         TypeObjectString(obj), TypeIdString(id), TypeString(type));
 265         }
 266     }
 267     return true;
 268 }
 269
 270 #endif
 271
 272 void
 273 types::TypeFailure(JSContext* cx, const char* fmt, ...)
 274 {
 275     char msgbuf[1024]; /* Larger error messages will be truncated */
 276     char errbuf[1024];
 277
 278     va_list ap;
 279     va_start(ap, fmt);
 280     JS_vsnprintf(errbuf, sizeof(errbuf), fmt, ap);
 281     va_end(ap);
 282
 283     JS_snprintf(msgbuf, sizeof(msgbuf), "[infer failure] %s", errbuf);
 284
 285     /* Dump type state, even if INFERFLAGS is unset. */
 286     cx->compartment()->types.print(cx, true);
 287
 288     MOZ_ReportAssertionFailure(msgbuf, __FILE__, __LINE__);
 289     MOZ_CRASH();
 290 }
 291
 292 /////////////////////////////////////////////////////////////////////
 293 // TypeSet
 294 /////////////////////////////////////////////////////////////////////
 295
 296 TemporaryTypeSet::TemporaryTypeSet(Type type)
 297 {
 298     if (type.isUnknown()) {
 299         flags |= TYPE_FLAG_BASE_MASK;
 300     } else if (type.isPrimitive()) {
 301         flags = PrimitiveTypeFlag(type.primitive());
 302         if (flags == TYPE_FLAG_DOUBLE)
 303             flags |= TYPE_FLAG_INT32;
 304     } else if (type.isAnyObject()) {
 305         flags |= TYPE_FLAG_ANYOBJECT;
 306     } else  if (type.isTypeObject() && type.typeObject()->unknownProperties()) {
 307         flags |= TYPE_FLAG_ANYOBJECT;
 308     } else {
 309         setBaseObjectCount(1);
 310         objectSet = reinterpret_cast<TypeObjectKey**>(type.objectKey());
 311     }
 312 }
 313
 314 bool
 315 TypeSet::mightBeMIRType(jit::MIRType type)
 316 {
 317     if (unknown())
 318         return true;
 319
 320     if (type == jit::MIRType_Object)
 321         return unknownObject() || baseObjectCount() != 0;
 322
 323     switch (type) {
 324       case jit::MIRType_Undefined:
 325         return baseFlags() & TYPE_FLAG_UNDEFINED;
 326       case jit::MIRType_Null:
 327         return baseFlags() & TYPE_FLAG_NULL;
 328       case jit::MIRType_Boolean:
 329         return baseFlags() & TYPE_FLAG_BOOLEAN;
 330       case jit::MIRType_Int32:
 331         return baseFlags() & TYPE_FLAG_INT32;
 332       case jit::MIRType_Float32: // Fall through, there's no JSVAL for Float32.
 333       case jit::MIRType_Double:
 334         return baseFlags() & TYPE_FLAG_DOUBLE;
 335       case jit::MIRType_String:
 336         return baseFlags() & TYPE_FLAG_STRING;
 337       case jit::MIRType_Symbol:
 338         return baseFlags() & TYPE_FLAG_SYMBOL;
 339       case jit::MIRType_MagicOptimizedArguments:
 340         return baseFlags() & TYPE_FLAG_LAZYARGS;
 341       case jit::MIRType_MagicHole:
 342       case jit::MIRType_MagicIsConstructing:
 343         // These magic constants do not escape to script and are not observed
 344         // in the type sets.
 345         //
 346         // The reason we can return false here is subtle: if Ion is asking the
 347         // type set if it has seen such a magic constant, then the MIR in
 348         // question is the most generic type, MIRType_Value. A magic constant
 349         // could only be emitted by a MIR of MIRType_Value if that MIR is a
 350         // phi, and we check that different magic constants do not flow to the
 351         // same join point in GuessPhiType.
 352         return false;
 353       default:
 354         MOZ_ASSUME_UNREACHABLE("Bad MIR type");
 355     }
 356 }
 357
 358 bool
 359 TypeSet::objectsAreSubset(TypeSet* other)
 360 {
 361     if (other->unknownObject())
 362         return true;
 363
 364     if (unknownObject())
 365         return false;
 366
 367     for (unsigned i = 0; i < getObjectCount(); i++) {
 368         TypeObjectKey* obj = getObject(i);
 369         if (!obj)
 370             continue;
 371         if (!other->hasType(Type::ObjectType(obj)))
 372             return false;
 373     }
 374
 375     return true;
 376 }
 377
 378 bool
 379 TypeSet::isSubset(TypeSet* other)
 380 {
 381     if ((baseFlags() & other->baseFlags()) != baseFlags())
 382         return false;
 383
 384     if (unknownObject()) {
 385         JS_ASSERT(other->unknownObject());
 386     } else {
 387         for (unsigned i = 0; i < getObjectCount(); i++) {
 388             TypeObjectKey* obj = getObject(i);
 389             if (!obj)
 390                 continue;
 391             if (!other->hasType(Type::ObjectType(obj)))
 392                 return false;
 393         }
 394     }
 395
 396     return true;
 397 }
 398
 399 bool
 400 TypeSet::enumerateTypes(TypeList* list)
 401 {
 402     /* If any type is possible, there's no need to worry about specifics. */
 403     if (flags & TYPE_FLAG_UNKNOWN)
 404         return list->append(Type::UnknownType());
 405
 406     /* Enqueue type set members stored as bits. */
 407     for (TypeFlags flag = 1; flag < TYPE_FLAG_ANYOBJECT; flag <<= 1) {
 408         if (flags & flag) {
 409             Type type = Type::PrimitiveType(TypeFlagPrimitive(flag));
 410             if (!list->append(type))
 411                 return false;
 412         }
 413     }
 414
 415     /* If any object is possible, skip specifics. */
 416     if (flags & TYPE_FLAG_ANYOBJECT)
 417         return list->append(Type::AnyObjectType());
 418
 419     /* Enqueue specific object types. */
 420     unsigned count = getObjectCount();
 421     for (unsigned i = 0; i < count; i++) {
 422         TypeObjectKey* object = getObject(i);
 423         if (object) {
 424             if (!list->append(Type::ObjectType(object)))
 425                 return false;
 426         }
 427     }
 428
 429     return true;
 430 }
 431
 432 inline bool
 433 TypeSet::addTypesToConstraint(JSContext* cx, TypeConstraint* constraint)
 434 {
 435     /*
 436      * Build all types in the set into a vector before triggering the
 437      * constraint, as doing so may modify this type set.
 438      */
 439     TypeList types;
 440     if (!enumerateTypes(&types))
 441         return false;
 442
 443     for (unsigned i = 0; i < types.length(); i++)
 444         constraint->newType(cx, this, types[i]);
 445
 446     return true;
 447 }
 448
 449 bool
 450 ConstraintTypeSet::addConstraint(JSContext* cx, TypeConstraint* constraint, bool callExisting)
 451 {
 452     if (!constraint) {
 453         /* OOM failure while constructing the constraint. */
 454         return false;
 455     }
 456
 457     JS_ASSERT(cx->compartment()->activeAnalysis);
 458
 459     InferSpew(ISpewOps, "addConstraint: %sT%p%s %sC%p%s %s",
 460               InferSpewColor(this), this, InferSpewColorReset(),
 461               InferSpewColor(constraint), constraint, InferSpewColorReset(),
 462               constraint->kind());
 463
 464     JS_ASSERT(constraint->next == nullptr);
 465     constraint->next = constraintList;
 466     constraintList = constraint;
 467
 468     if (callExisting)
 469         return addTypesToConstraint(cx, constraint);
 470     return true;
 471 }
 472
 473 void
 474 TypeSet::clearObjects()
 475 {
 476     setBaseObjectCount(0);
 477     objectSet = nullptr;
 478 }
 479
 480 void
 481 TypeSet::addType(Type type, LifoAlloc* alloc)
 482 {
 483     if (unknown())
 484         return;
 485
 486     if (type.isUnknown()) {
 487         flags |= TYPE_FLAG_BASE_MASK;
 488         clearObjects();
 489         JS_ASSERT(unknown());
 490         return;
 491     }
 492
 493     if (type.isPrimitive()) {
 494         TypeFlags flag = PrimitiveTypeFlag(type.primitive());
 495         if (flags & flag)
 496             return;
 497
 498         /* If we add float to a type set it is also considered to contain int. */
 499         if (flag == TYPE_FLAG_DOUBLE)
 500             flag |= TYPE_FLAG_INT32;
 501
 502         flags |= flag;
 503         return;
 504     }
 505
 506     if (flags & TYPE_FLAG_ANYOBJECT)
 507         return;
 508     if (type.isAnyObject())
 509         goto unknownObject;
 510
 511     {
 512         uint32_t objectCount = baseObjectCount();
 513         TypeObjectKey* object = type.objectKey();
 514         TypeObjectKey** pentry = HashSetInsert<TypeObjectKey*,TypeObjectKey,TypeObjectKey>
 515                                      (*alloc, objectSet, objectCount, object);
 516         if (!pentry)
 517             goto unknownObject;
 518         if (*pentry)
 519             return;
 520         *pentry = object;
 521
 522         setBaseObjectCount(objectCount);
 523
 524         if (objectCount == TYPE_FLAG_OBJECT_COUNT_LIMIT)
 525             goto unknownObject;
 526     }
 527
 528     if (type.isTypeObject()) {
 529         TypeObject* nobject = type.typeObject();
 530         JS_ASSERT(!nobject->singleton());
 531         if (nobject->unknownProperties())
 532             goto unknownObject;
 533     }
 534
 535     if (false) {
 536     unknownObject:
 537         flags |= TYPE_FLAG_ANYOBJECT;
 538         clearObjects();
 539     }
 540 }
 541
 542 void
 543 ConstraintTypeSet::addType(ExclusiveContext* cxArg, Type type)
 544 {
 545     JS_ASSERT(cxArg->compartment()->activeAnalysis);
 546
 547     if (hasType(type))
 548         return;
 549
 550     TypeSet::addType(type, &cxArg->typeLifoAlloc());
 551
 552     if (type.isObjectUnchecked() && unknownObject())
 553         type = Type::AnyObjectType();
 554
 555     InferSpew(ISpewOps, "addType: %sT%p%s %s",
 556               InferSpewColor(this), this, InferSpewColorReset(),
 557               TypeString(type));
 558
 559     /* Propagate the type to all constraints. */
 560     if (JSContext* cx = cxArg->maybeJSContext()) {
 561         TypeConstraint* constraint = constraintList;
 562         while (constraint) {
 563             constraint->newType(cx, this, type);
 564             constraint = constraint->next;
 565         }
 566     } else {
 567         JS_ASSERT(!constraintList);
 568     }
 569 }
 570
 571 void
 572 TypeSet::print()
 573 {
 574     if (flags & TYPE_FLAG_NON_DATA_PROPERTY)
 575         fprintf(stderr, " [non-data]");
 576
 577     if (flags & TYPE_FLAG_NON_WRITABLE_PROPERTY)
 578         fprintf(stderr, " [non-writable]");
 579
 580     if (definiteProperty())
 581         fprintf(stderr, " [definite:%d]", definiteSlot());
 582
 583     if (baseFlags() == 0 && !baseObjectCount()) {
 584         fprintf(stderr, " missing");
 585         return;
 586     }
 587
 588     if (flags & TYPE_FLAG_UNKNOWN)
 589         fprintf(stderr, " unknown");
 590     if (flags & TYPE_FLAG_ANYOBJECT)
 591         fprintf(stderr, " object");
 592
 593     if (flags & TYPE_FLAG_UNDEFINED)
 594         fprintf(stderr, " void");
 595     if (flags & TYPE_FLAG_NULL)
 596         fprintf(stderr, " null");
 597     if (flags & TYPE_FLAG_BOOLEAN)
 598         fprintf(stderr, " bool");
 599     if (flags & TYPE_FLAG_INT32)
 600         fprintf(stderr, " int");
 601     if (flags & TYPE_FLAG_DOUBLE)
 602         fprintf(stderr, " float");
 603     if (flags & TYPE_FLAG_STRING)
 604         fprintf(stderr, " string");
 605     if (flags & TYPE_FLAG_LAZYARGS)
 606         fprintf(stderr, " lazyargs");
 607
 608     uint32_t objectCount = baseObjectCount();
 609     if (objectCount) {
 610         fprintf(stderr, " object[%u]", objectCount);
 611
 612         unsigned count = getObjectCount();
 613         for (unsigned i = 0; i < count; i++) {
 614             TypeObjectKey* object = getObject(i);
 615             if (object)
 616                 fprintf(stderr, " %s", TypeString(Type::ObjectType(object)));
 617         }
 618     }
 619 }
 620
 621 /* static */ void
 622 TypeSet::readBarrier(const TypeSet* types)
 623 {
 624     if (types->unknownObject())
 625         return;
 626
 627     for (unsigned i = 0; i < types->getObjectCount(); i++) {
 628         if (TypeObjectKey* object = types->getObject(i)) {
 629             if (object->isSingleObject())
 630                 (void) object->asSingleObject();
 631             else
 632                 (void) object->asTypeObject();
 633         }
 634     }
 635 }
 636
 637 bool
 638 TypeSet::clone(LifoAlloc* alloc, TemporaryTypeSet* result) const
 639 {
 640     JS_ASSERT(result->empty());
 641
 642     unsigned objectCount = baseObjectCount();
 643     unsigned capacity = (objectCount >= 2) ? HashSetCapacity(objectCount) : 0;
 644
 645     TypeObjectKey** newSet;
 646     if (capacity) {
 647         newSet = alloc->newArray<TypeObjectKey*>(capacity);
 648         if (!newSet)
 649             return false;
 650         PodCopy(newSet, objectSet, capacity);
 651     }
 652
 653     new(result) TemporaryTypeSet(flags, capacity ? newSet : objectSet);
 654     return true;
 655 }
 656
 657 TemporaryTypeSet*
 658 TypeSet::clone(LifoAlloc* alloc) const
 659 {
 660     TemporaryTypeSet* res = alloc->new_<TemporaryTypeSet>();
 661     if (!res || !clone(alloc, res))
 662         return nullptr;
 663     return res;
 664 }
 665
 666 TemporaryTypeSet*
 667 TypeSet::filter(LifoAlloc* alloc, bool filterUndefined, bool filterNull) const
 668 {
 669     TemporaryTypeSet* res = clone(alloc);
 670     if (!res)
 671         return nullptr;
 672
 673     if (filterUndefined)
 674         res->flags = res->flags & ~TYPE_FLAG_UNDEFINED;
 675
 676     if (filterNull)
 677         res->flags = res->flags & ~TYPE_FLAG_NULL;
 678
 679     return res;
 680 }
 681
 682 TemporaryTypeSet*
 683 TypeSet::cloneObjectsOnly(LifoAlloc* alloc)
 684 {
 685     TemporaryTypeSet* res = clone(alloc);
 686     if (!res)
 687         return nullptr;
 688
 689     res->flags &= TYPE_FLAG_ANYOBJECT;
 690
 691     return res;
 692 }
 693
 694 /* static */ TemporaryTypeSet*
 695 TypeSet::unionSets(TypeSet* a, TypeSet* b, LifoAlloc* alloc)
 696 {
 697     TemporaryTypeSet* res = alloc->new_<TemporaryTypeSet>(a->baseFlags() | b->baseFlags(),
 698                                                           static_cast<TypeObjectKey**>(nullptr));
 699     if (!res)
 700         return nullptr;
 701
 702     if (!res->unknownObject()) {
 703         for (size_t i = 0; i < a->getObjectCount() && !res->unknownObject(); i++) {
 704             if (TypeObjectKey* key = a->getObject(i))
 705                 res->addType(Type::ObjectType(key), alloc);
 706         }
 707         for (size_t i = 0; i < b->getObjectCount() && !res->unknownObject(); i++) {
 708             if (TypeObjectKey* key = b->getObject(i))
 709                 res->addType(Type::ObjectType(key), alloc);
 710         }
 711     }
 712
 713     return res;
 714 }
 715
 716 /////////////////////////////////////////////////////////////////////
 717 // Compiler constraints
 718 /////////////////////////////////////////////////////////////////////
 719
 720 // Compiler constraints overview
 721 //
 722 // Constraints generated during Ion compilation capture assumptions made about
 723 // heap properties that will trigger invalidation of the resulting Ion code if
 724 // the constraint is violated. Constraints can only be attached to type sets on
 725 // the main thread, so to allow compilation to occur almost entirely off thread
 726 // the generation is split into two phases.
 727 //
 728 // During compilation, CompilerConstraint values are constructed in a list,
 729 // recording the heap property type set which was read from and its expected
 730 // contents, along with the assumption made about those contents.
 731 //
 732 // At the end of compilation, when linking the result on the main thread, the
 733 // list of compiler constraints are read and converted to type constraints and
 734 // attached to the type sets. If the property type sets have changed so that the
 735 // assumptions no longer hold then the compilation is aborted and its result
 736 // discarded.
 737
 738 // Superclass of all constraints generated during Ion compilation. These may
 739 // be allocated off the main thread, using the current Ion context's allocator.
 740 class CompilerConstraint
 741 {
 742   public:
 743     // Property being queried by the compiler.
 744     HeapTypeSetKey property;
 745
 746     // Contents of the property at the point when the query was performed. This
 747     // may differ from the actual property types later in compilation as the
 748     // main thread performs side effects.
 749     TemporaryTypeSet* expected;
 750
 751     CompilerConstraint(LifoAlloc* alloc, const HeapTypeSetKey& property)
 752       : property(property),
 753         expected(property.maybeTypes() ? property.maybeTypes()->clone(alloc) : nullptr)
 754     {}
 755
 756     // Generate the type constraint recording the assumption made by this
 757     // compilation. Returns true if the assumption originally made still holds.
 758     virtual bool generateTypeConstraint(JSContext* cx, RecompileInfo recompileInfo) = 0;
 759 };
 760
 761 class types::CompilerConstraintList
 762 {
 763   public:
 764     struct FrozenScript
 765     {
 766         JSScript* script;
 767         TemporaryTypeSet* thisTypes;
 768         TemporaryTypeSet* argTypes;
 769         TemporaryTypeSet* bytecodeTypes;
 770     };
 771
 772   private:
 773
 774     // OOM during generation of some constraint.
 775     bool failed_;
 776
 777     // Allocator used for constraints.
 778     LifoAlloc* alloc_;
 779
 780     // Constraints generated on heap properties.
 781     Vector<CompilerConstraint*, 0, jit::IonAllocPolicy> constraints;
 782
 783     // Scripts whose stack type sets were frozen for the compilation.
 784     Vector<FrozenScript, 1, jit::IonAllocPolicy> frozenScripts;
 785
 786   public:
 787     explicit CompilerConstraintList(jit::TempAllocator& alloc)
 788       : failed_(false),
 789         alloc_(alloc.lifoAlloc()),
 790         constraints(alloc),
 791         frozenScripts(alloc)
 792     {}
 793
 794     void add(CompilerConstraint* constraint) {
 795         if (!constraint || !constraints.append(constraint))
 796             setFailed();
 797     }
 798
 799     void freezeScript(JSScript* script,
 800                       TemporaryTypeSet* thisTypes,
 801                       TemporaryTypeSet* argTypes,
 802                       TemporaryTypeSet* bytecodeTypes)
 803     {
 804         FrozenScript entry;
 805         entry.script = script;
 806         entry.thisTypes = thisTypes;
 807         entry.argTypes = argTypes;
 808         entry.bytecodeTypes = bytecodeTypes;
 809         if (!frozenScripts.append(entry))
 810             setFailed();
 811     }
 812
 813     size_t length() {
 814         return constraints.length();
 815     }
 816
 817     CompilerConstraint* get(size_t i) {
 818         return constraints[i];
 819     }
 820
 821     size_t numFrozenScripts() {
 822         return frozenScripts.length();
 823     }
 824
 825     const FrozenScript& frozenScript(size_t i) {
 826         return frozenScripts[i];
 827     }
 828
 829     bool failed() {
 830         return failed_;
 831     }
 832     void setFailed() {
 833         failed_ = true;
 834     }
 835     LifoAlloc* alloc() const {
 836         return alloc_;
 837     }
 838 };
 839
 840 CompilerConstraintList*
 841 types::NewCompilerConstraintList(jit::TempAllocator& alloc)
 842 {
 843     return alloc.lifoAlloc()->new_<CompilerConstraintList>(alloc);
 844 }
 845
 846 /* static */ bool
 847 TypeScript::FreezeTypeSets(CompilerConstraintList* constraints, JSScript* script,
 848                            TemporaryTypeSet** pThisTypes,
 849                            TemporaryTypeSet** pArgTypes,
 850                            TemporaryTypeSet** pBytecodeTypes)
 851 {
 852     LifoAlloc* alloc = constraints->alloc();
 853     StackTypeSet* existing = script->types->typeArray();
 854
 855     size_t count = NumTypeSets(script);
 856     TemporaryTypeSet* types = alloc->newArrayUninitialized<TemporaryTypeSet>(count);
 857     if (!types)
 858         return false;
 859     PodZero(types, count);
 860
 861     for (size_t i = 0; i < count; i++) {
 862         if (!existing[i].clone(alloc, &types[i]))
 863             return false;
 864     }
 865
 866     *pThisTypes = types + (ThisTypes(script) - existing);
 867     *pArgTypes = (script->functionNonDelazifying() && script->functionNonDelazifying()->nargs())
 868                  ? (types + (ArgTypes(script, 0) - existing))
 869                  : nullptr;
 870     *pBytecodeTypes = types;
 871
 872     constraints->freezeScript(script, *pThisTypes, *pArgTypes, *pBytecodeTypes);
 873     return true;
 874 }
 875
 876 namespace {
 877
 878 template <typename T>
 879 class CompilerConstraintInstance : public CompilerConstraint
 880 {
 881     T data;
 882
 883   public:
 884     CompilerConstraintInstance<T>(LifoAlloc* alloc, const HeapTypeSetKey& property, const T& data)
 885       : CompilerConstraint(alloc, property), data(data)
 886     {}
 887
 888     bool generateTypeConstraint(JSContext* cx, RecompileInfo recompileInfo);
 889 };
 890
 891 // Constraint generated from a CompilerConstraint when linking the compilation.
 892 template <typename T>
 893 class TypeCompilerConstraint : public TypeConstraint
 894 {
 895     // Compilation which this constraint may invalidate.
 896     RecompileInfo compilation;
 897
 898     T data;
 899
 900   public:
 901     TypeCompilerConstraint<T>(RecompileInfo compilation, const T& data)
 902       : compilation(compilation), data(data)
 903     {}
 904
 905     const char* kind() { return data.kind(); }
 906
 907     void newType(JSContext* cx, TypeSet* source, Type type) {
 908         if (data.invalidateOnNewType(type))
 909             cx->zone()->types.addPendingRecompile(cx, compilation);
 910     }
 911
 912     void newPropertyState(JSContext* cx, TypeSet* source) {
 913         if (data.invalidateOnNewPropertyState(source))
 914             cx->zone()->types.addPendingRecompile(cx, compilation);
 915     }
 916
 917     void newObjectState(JSContext* cx, TypeObject* object) {
 918         // Note: Once the object has unknown properties, no more notifications
 919         // will be sent on changes to its state, so always invalidate any
 920         // associated compilations.
 921         if (object->unknownProperties() || data.invalidateOnNewObjectState(object))
 922             cx->zone()->types.addPendingRecompile(cx, compilation);
 923     }
 924
 925     bool sweep(TypeZone& zone, TypeConstraint** res) {
 926         if (data.shouldSweep() || compilation.shouldSweep(zone))
 927             return false;
 928         *res = zone.typeLifoAlloc.new_<TypeCompilerConstraint<T> >(compilation, data);
 929         return true;
 930     }
 931 };
 932
 933 template <typename T>
 934 bool
 935 CompilerConstraintInstance<T>::generateTypeConstraint(JSContext* cx, RecompileInfo recompileInfo)
 936 {
 937     if (property.object()->unknownProperties())
 938         return false;
 939
 940     if (!property.instantiate(cx))
 941         return false;
 942
 943     if (!data.constraintHolds(cx, property, expected))
 944         return false;
 945
 946     return property.maybeTypes()->addConstraint(cx, cx->typeLifoAlloc().new_<TypeCompilerConstraint<T> >(recompileInfo, data),
 947                                                 /* callExisting = */ false);
 948 }
 949
 950 } /* anonymous namespace */
 951
 952 const Class*
 953 TypeObjectKey::clasp()
 954 {
 955     return isTypeObject() ? asTypeObject()->clasp() : asSingleObject()->getClass();
 956 }
 957
 958 TaggedProto
 959 TypeObjectKey::proto()
 960 {
 961     JS_ASSERT(hasTenuredProto());
 962     return isTypeObject() ? asTypeObject()->proto() : asSingleObject()->getTaggedProto();
 963 }
 964
 965 bool
 966 ObjectImpl::hasTenuredProto() const
 967 {
 968     return type_->hasTenuredProto();
 969 }
 970
 971 bool
 972 TypeObjectKey::hasTenuredProto()
 973 {
 974     return isTypeObject() ? asTypeObject()->hasTenuredProto() : asSingleObject()->hasTenuredProto();
 975 }
 976
 977 JSObject*
 978 TypeObjectKey::singleton()
 979 {
 980     return isTypeObject() ? asTypeObject()->singleton() : asSingleObject();
 981 }
 982
 983 TypeNewScript*
 984 TypeObjectKey::newScript()
 985 {
 986     if (isTypeObject() && asTypeObject()->newScript())
 987         return asTypeObject()->newScript();
 988     return nullptr;
 989 }
 990
 991 TypeObject*
 992 TypeObjectKey::maybeType()
 993 {
 994     if (isTypeObject())
 995         return asTypeObject();
 996     if (asSingleObject()->hasLazyType())
 997         return nullptr;
 998     return asSingleObject()->type();
 999 }
1000
1001 bool
1002 TypeObjectKey::unknownProperties()
1003 {
1004     if (TypeObject* type = maybeType())
1005         return type->unknownProperties();
1006     return false;
1007 }
1008
1009 HeapTypeSetKey
1010 TypeObjectKey::property(jsid id)
1011 {
1012     JS_ASSERT(!unknownProperties());
1013
1014     HeapTypeSetKey property;
1015     property.object_ = this;
1016     property.id_ = id;
1017     if (TypeObject* type = maybeType())
1018         property.maybeTypes_ = type->maybeGetProperty(id);
1019
1020     return property;
1021 }
1022
1023 void
1024 TypeObjectKey::ensureTrackedProperty(JSContext* cx, jsid id)
1025 {
1026     // If we are accessing a lazily defined property which actually exists in
1027     // the VM and has not been instantiated yet, instantiate it now if we are
1028     // on the main thread and able to do so.
1029     if (!JSID_IS_VOID(id) && !JSID_IS_EMPTY(id)) {
1030         JS_ASSERT(CurrentThreadCanAccessRuntime(cx->runtime()));
1031         if (JSObject* obj = singleton()) {
1032             if (obj->isNative() && obj->nativeLookupPure(id))
1033                 EnsureTrackPropertyTypes(cx, obj, id);
1034         }
1035     }
1036 }
1037
1038 bool
1039 HeapTypeSetKey::instantiate(JSContext* cx)
1040 {
1041     if (maybeTypes())
1042         return true;
1043     if (object()->isSingleObject() && !object()->asSingleObject()->getType(cx)) {
1044         cx->clearPendingException();
1045         return false;
1046     }
1047     maybeTypes_ = object()->maybeType()->getProperty(cx, id());
1048     return maybeTypes_ != nullptr;
1049 }
1050
1051 static bool
1052 CheckFrozenTypeSet(JSContext* cx, TemporaryTypeSet* frozen, StackTypeSet* actual)
1053 {
1054     // Return whether the types frozen for a script during compilation are
1055     // still valid. Also check for any new types added to the frozen set during
1056     // compilation, and add them to the actual stack type sets. These new types
1057     // indicate places where the compiler relaxed its possible inputs to be
1058     // more tolerant of potential new types.
1059
1060     if (!actual->isSubset(frozen))
1061         return false;
1062
1063     if (!frozen->isSubset(actual)) {
1064         TypeSet::TypeList list;
1065         frozen->enumerateTypes(&list);
1066
1067         for (size_t i = 0; i < list.length(); i++)
1068             actual->addType(cx, list[i]);
1069     }
1070
1071     return true;
1072 }
1073
1074 namespace {
1075
1076 /*
1077  * As for TypeConstraintFreeze, but describes an implicit freeze constraint
1078  * added for stack types within a script. Applies to all compilations of the
1079  * script, not just a single one.
1080  */
1081 class TypeConstraintFreezeStack : public TypeConstraint
1082 {
1083     JSScript* script_;
1084
1085   public:
1086     explicit TypeConstraintFreezeStack(JSScript* script)
1087         : script_(script)
1088     {}
1089
1090     const char* kind() { return "freezeStack"; }
1091
1092     void newType(JSContext* cx, TypeSet* source, Type type) {
1093         /*
1094          * Unlike TypeConstraintFreeze, triggering this constraint once does
1095          * not disable it on future changes to the type set.
1096          */
1097         cx->zone()->types.addPendingRecompile(cx, script_);
1098     }
1099
1100     bool sweep(TypeZone& zone, TypeConstraint** res) {
1101         if (IsScriptAboutToBeFinalized(&script_))
1102             return false;
1103         *res = zone.typeLifoAlloc.new_<TypeConstraintFreezeStack>(script_);
1104         return true;
1105     }
1106 };
1107
1108 } /* anonymous namespace */
1109
1110 bool
1111 types::FinishCompilation(JSContext* cx, HandleScript script, ExecutionMode executionMode,
1112                          CompilerConstraintList* constraints, RecompileInfo* precompileInfo)
1113 {
1114     if (constraints->failed())
1115         return false;
1116
1117     CompilerOutput co(script, executionMode);
1118
1119     TypeZone& types = cx->zone()->types;
1120     if (!types.compilerOutputs) {
1121         types.compilerOutputs = cx->new_< Vector<CompilerOutput> >(cx);
1122         if (!types.compilerOutputs)
1123             return false;
1124     }
1125
1126 #ifdef DEBUG
1127     for (size_t i = 0; i < types.compilerOutputs->length(); i++) {
1128         const CompilerOutput& co = (*types.compilerOutputs)[i];
1129         JS_ASSERT_IF(co.isValid(), co.script() != script || co.mode() != executionMode);
1130     }
1131 #endif
1132
1133     uint32_t index = types.compilerOutputs->length();
1134     if (!types.compilerOutputs->append(co))
1135         return false;
1136
1137     *precompileInfo = RecompileInfo(index);
1138
1139     bool succeeded = true;
1140
1141     for (size_t i = 0; i < constraints->length(); i++) {
1142         CompilerConstraint* constraint = constraints->get(i);
1143         if (!constraint->generateTypeConstraint(cx, *precompileInfo))
1144             succeeded = false;
1145     }
1146
1147     for (size_t i = 0; i < constraints->numFrozenScripts(); i++) {
1148         const CompilerConstraintList::FrozenScript& entry = constraints->frozenScript(i);
1149         JS_ASSERT(entry.script->types);
1150
1151         if (!CheckFrozenTypeSet(cx, entry.thisTypes, types::TypeScript::ThisTypes(entry.script)))
1152             succeeded = false;
1153         unsigned nargs = entry.script->functionNonDelazifying()
1154                          ? entry.script->functionNonDelazifying()->nargs()
1155                          : 0;
1156         for (size_t i = 0; i < nargs; i++) {
1157             if (!CheckFrozenTypeSet(cx, &entry.argTypes[i], types::TypeScript::ArgTypes(entry.script, i)))
1158                 succeeded = false;
1159         }
1160         for (size_t i = 0; i < entry.script->nTypeSets(); i++) {
1161             if (!CheckFrozenTypeSet(cx, &entry.bytecodeTypes[i], &entry.script->types->typeArray()[i]))
1162                 succeeded = false;
1163         }
1164
1165         // If necessary, add constraints to trigger invalidation on the script
1166         // after any future changes to the stack type sets.
1167         if (entry.script->hasFreezeConstraints())
1168             continue;
1169         entry.script->setHasFreezeConstraints();
1170
1171         size_t count = TypeScript::NumTypeSets(entry.script);
1172
1173         StackTypeSet* array = entry.script->types->typeArray();
1174         for (size_t i = 0; i < count; i++) {
1175             if (!array[i].addConstraint(cx, cx->typeLifoAlloc().new_<TypeConstraintFreezeStack>(entry.script), false))
1176                 succeeded = false;
1177         }
1178     }
1179
1180     if (!succeeded || types.compilerOutputs->back().pendingInvalidation()) {
1181         types.compilerOutputs->back().invalidate();
1182         script->resetUseCount();
1183         return false;
1184     }
1185
1186     return true;
1187 }
1188
1189 static void
1190 CheckDefinitePropertiesTypeSet(JSContext* cx, TemporaryTypeSet* frozen, StackTypeSet* actual)
1191 {
1192     // The definite properties analysis happens on the main thread, so no new
1193     // types can have been added to actual. The analysis may have updated the
1194     // contents of |frozen| though with new speculative types, and these need
1195     // to be reflected in |actual| for AddClearDefiniteFunctionUsesInScript
1196     // to work.
1197     if (!frozen->isSubset(actual)) {
1198         TypeSet::TypeList list;
1199         frozen->enumerateTypes(&list);
1200
1201         for (size_t i = 0; i < list.length(); i++)
1202             actual->addType(cx, list[i]);
1203     }
1204 }
1205
1206 void
1207 types::FinishDefinitePropertiesAnalysis(JSContext* cx, CompilerConstraintList* constraints)
1208 {
1209 #ifdef DEBUG
1210     // Assert no new types have been added to the StackTypeSets. Do this before
1211     // calling CheckDefinitePropertiesTypeSet, as it may add new types to the
1212     // StackTypeSets and break these invariants if a script is inlined more
1213     // than once. See also CheckDefinitePropertiesTypeSet.
1214     for (size_t i = 0; i < constraints->numFrozenScripts(); i++) {
1215         const CompilerConstraintList::FrozenScript& entry = constraints->frozenScript(i);
1216         JSScript* script = entry.script;
1217         JS_ASSERT(script->types);
1218
1219         JS_ASSERT(TypeScript::ThisTypes(script)->isSubset(entry.thisTypes));
1220
1221         unsigned nargs = entry.script->functionNonDelazifying()
1222                          ? entry.script->functionNonDelazifying()->nargs()
1223                          : 0;
1224         for (size_t j = 0; j < nargs; j++)
1225             JS_ASSERT(TypeScript::ArgTypes(script, j)->isSubset(&entry.argTypes[j]));
1226
1227         for (size_t j = 0; j < script->nTypeSets(); j++)
1228             JS_ASSERT(script->types->typeArray()[j].isSubset(&entry.bytecodeTypes[j]));
1229     }
1230 #endif
1231
1232     for (size_t i = 0; i < constraints->numFrozenScripts(); i++) {
1233         const CompilerConstraintList::FrozenScript& entry = constraints->frozenScript(i);
1234         JSScript* script = entry.script;
1235         JS_ASSERT(script->types);
1236
1237         if (!script->types)
1238             MOZ_CRASH();
1239
1240         CheckDefinitePropertiesTypeSet(cx, entry.thisTypes, TypeScript::ThisTypes(script));
1241
1242         unsigned nargs = script->functionNonDelazifying()
1243                          ? script->functionNonDelazifying()->nargs()
1244                          : 0;
1245         for (size_t j = 0; j < nargs; j++)
1246             CheckDefinitePropertiesTypeSet(cx, &entry.argTypes[j], TypeScript::ArgTypes(script, j));
1247
1248         for (size_t j = 0; j < script->nTypeSets(); j++)
1249             CheckDefinitePropertiesTypeSet(cx, &entry.bytecodeTypes[j], &script->types->typeArray()[j]);
1250     }
1251 }
1252
1253 namespace {
1254
1255 // Constraint which triggers recompilation of a script if any type is added to a type set. */
1256 class ConstraintDataFreeze
1257 {
1258   public:
1259     ConstraintDataFreeze() {}
1260
1261     const char* kind() { return "freeze"; }
1262
1263     bool invalidateOnNewType(Type type) { return true; }
1264     bool invalidateOnNewPropertyState(TypeSet* property) { return true; }
1265     bool invalidateOnNewObjectState(TypeObject* object) { return false; }
1266
1267     bool constraintHolds(JSContext* cx,
1268                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1269     {
1270         return expected
1271                ? property.maybeTypes()->isSubset(expected)
1272                : property.maybeTypes()->empty();
1273     }
1274
1275     bool shouldSweep() { return false; }
1276 };
1277
1278 } /* anonymous namespace */
1279
1280 void
1281 HeapTypeSetKey::freeze(CompilerConstraintList* constraints)
1282 {
1283     LifoAlloc* alloc = constraints->alloc();
1284
1285     typedef CompilerConstraintInstance<ConstraintDataFreeze> T;
1286     constraints->add(alloc->new_<T>(alloc, *this, ConstraintDataFreeze()));
1287 }
1288
1289 static inline jit::MIRType
1290 GetMIRTypeFromTypeFlags(TypeFlags flags)
1291 {
1292     switch (flags) {
1293       case TYPE_FLAG_UNDEFINED:
1294         return jit::MIRType_Undefined;
1295       case TYPE_FLAG_NULL:
1296         return jit::MIRType_Null;
1297       case TYPE_FLAG_BOOLEAN:
1298         return jit::MIRType_Boolean;
1299       case TYPE_FLAG_INT32:
1300         return jit::MIRType_Int32;
1301       case (TYPE_FLAG_INT32 | TYPE_FLAG_DOUBLE):
1302         return jit::MIRType_Double;
1303       case TYPE_FLAG_STRING:
1304         return jit::MIRType_String;
1305       case TYPE_FLAG_SYMBOL:
1306         return jit::MIRType_Symbol;
1307       case TYPE_FLAG_LAZYARGS:
1308         return jit::MIRType_MagicOptimizedArguments;
1309       case TYPE_FLAG_ANYOBJECT:
1310         return jit::MIRType_Object;
1311       default:
1312         return jit::MIRType_Value;
1313     }
1314 }
1315
1316 jit::MIRType
1317 TemporaryTypeSet::getKnownMIRType()
1318 {
1319     TypeFlags flags = baseFlags();
1320     jit::MIRType type;
1321
1322     if (baseObjectCount())
1323         type = flags ? jit::MIRType_Value : jit::MIRType_Object;
1324     else
1325         type = GetMIRTypeFromTypeFlags(flags);
1326
1327     /*
1328      * If the type set is totally empty then it will be treated as unknown,
1329      * but we still need to record the dependency as adding a new type can give
1330      * it a definite type tag. This is not needed if there are enough types
1331      * that the exact tag is unknown, as it will stay unknown as more types are
1332      * added to the set.
1333      */
1334     DebugOnly<bool> empty = flags == 0 && baseObjectCount() == 0;
1335     JS_ASSERT_IF(empty, type == jit::MIRType_Value);
1336
1337     return type;
1338 }
1339
1340 jit::MIRType
1341 HeapTypeSetKey::knownMIRType(CompilerConstraintList* constraints)
1342 {
1343     TypeSet* types = maybeTypes();
1344
1345     if (!types || types->unknown())
1346         return jit::MIRType_Value;
1347
1348     TypeFlags flags = types->baseFlags() & ~TYPE_FLAG_ANYOBJECT;
1349     jit::MIRType type;
1350
1351     if (types->unknownObject() || types->getObjectCount())
1352         type = flags ? jit::MIRType_Value : jit::MIRType_Object;
1353     else
1354         type = GetMIRTypeFromTypeFlags(flags);
1355
1356     if (type != jit::MIRType_Value)
1357         freeze(constraints);
1358
1359     /*
1360      * If the type set is totally empty then it will be treated as unknown,
1361      * but we still need to record the dependency as adding a new type can give
1362      * it a definite type tag. This is not needed if there are enough types
1363      * that the exact tag is unknown, as it will stay unknown as more types are
1364      * added to the set.
1365      */
1366     JS_ASSERT_IF(types->empty(), type == jit::MIRType_Value);
1367
1368     return type;
1369 }
1370
1371 bool
1372 HeapTypeSetKey::isOwnProperty(CompilerConstraintList* constraints)
1373 {
1374     if (maybeTypes() && (!maybeTypes()->empty() || maybeTypes()->nonDataProperty()))
1375         return true;
1376     if (JSObject* obj = object()->singleton()) {
1377         if (CanHaveEmptyPropertyTypesForOwnProperty(obj))
1378             return true;
1379     }
1380     freeze(constraints);
1381     return false;
1382 }
1383
1384 bool
1385 HeapTypeSetKey::knownSubset(CompilerConstraintList* constraints, const HeapTypeSetKey& other)
1386 {
1387     if (!maybeTypes() || maybeTypes()->empty()) {
1388         freeze(constraints);
1389         return true;
1390     }
1391     if (!other.maybeTypes() || !maybeTypes()->isSubset(other.maybeTypes()))
1392         return false;
1393     freeze(constraints);
1394     return true;
1395 }
1396
1397 JSObject*
1398 TemporaryTypeSet::getSingleton()
1399 {
1400     if (baseFlags() != 0 || baseObjectCount() != 1)
1401         return nullptr;
1402
1403     return getSingleObject(0);
1404 }
1405
1406 JSObject*
1407 HeapTypeSetKey::singleton(CompilerConstraintList* constraints)
1408 {
1409     HeapTypeSet* types = maybeTypes();
1410
1411     if (!types || types->nonDataProperty() || types->baseFlags() != 0 || types->getObjectCount() != 1)
1412         return nullptr;
1413
1414     JSObject* obj = types->getSingleObject(0);
1415
1416     if (obj)
1417         freeze(constraints);
1418
1419     return obj;
1420 }
1421
1422 bool
1423 HeapTypeSetKey::needsBarrier(CompilerConstraintList* constraints)
1424 {
1425     TypeSet* types = maybeTypes();
1426     if (!types)
1427         return false;
1428     bool result = types->unknownObject()
1429                || types->getObjectCount() > 0
1430                || types->hasAnyFlag(TYPE_FLAG_STRING);
1431     if (!result)
1432         freeze(constraints);
1433     return result;
1434 }
1435
1436 namespace {
1437
1438 // Constraint which triggers recompilation if an object acquires particular flags.
1439 class ConstraintDataFreezeObjectFlags
1440 {
1441   public:
1442     // Flags we are watching for on this object.
1443     TypeObjectFlags flags;
1444
1445     explicit ConstraintDataFreezeObjectFlags(TypeObjectFlags flags)
1446       : flags(flags)
1447     {
1448         JS_ASSERT(flags);
1449     }
1450
1451     const char* kind() { return "freezeObjectFlags"; }
1452
1453     bool invalidateOnNewType(Type type) { return false; }
1454     bool invalidateOnNewPropertyState(TypeSet* property) { return false; }
1455     bool invalidateOnNewObjectState(TypeObject* object) {
1456         return object->hasAnyFlags(flags);
1457     }
1458
1459     bool constraintHolds(JSContext* cx,
1460                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1461     {
1462         return !invalidateOnNewObjectState(property.object()->maybeType());
1463     }
1464
1465     bool shouldSweep() { return false; }
1466 };
1467
1468 } /* anonymous namespace */
1469
1470 bool
1471 TypeObjectKey::hasFlags(CompilerConstraintList* constraints, TypeObjectFlags flags)
1472 {
1473     JS_ASSERT(flags);
1474
1475     if (TypeObject* type = maybeType()) {
1476         if (type->hasAnyFlags(flags))
1477             return true;
1478     }
1479
1480     HeapTypeSetKey objectProperty = property(JSID_EMPTY);
1481     LifoAlloc* alloc = constraints->alloc();
1482
1483     typedef CompilerConstraintInstance<ConstraintDataFreezeObjectFlags> T;
1484     constraints->add(alloc->new_<T>(alloc, objectProperty, ConstraintDataFreezeObjectFlags(flags)));
1485     return false;
1486 }
1487
1488 bool
1489 TemporaryTypeSet::hasObjectFlags(CompilerConstraintList* constraints, TypeObjectFlags flags)
1490 {
1491     if (unknownObject())
1492         return true;
1493
1494     /*
1495      * Treat type sets containing no objects as having all object flags,
1496      * to spare callers from having to check this.
1497      */
1498     if (baseObjectCount() == 0)
1499         return true;
1500
1501     unsigned count = getObjectCount();
1502     for (unsigned i = 0; i < count; i++) {
1503         TypeObjectKey* object = getObject(i);
1504         if (object && object->hasFlags(constraints, flags))
1505             return true;
1506     }
1507
1508     return false;
1509 }
1510
1511 gc::InitialHeap
1512 TypeObject::initialHeap(CompilerConstraintList* constraints)
1513 {
1514     // If this object is not required to be pretenured but could be in the
1515     // future, add a constraint to trigger recompilation if the requirement
1516     // changes.
1517
1518     if (shouldPreTenure())
1519         return gc::TenuredHeap;
1520
1521     if (!canPreTenure())
1522         return gc::DefaultHeap;
1523
1524     HeapTypeSetKey objectProperty = TypeObjectKey::get(this)->property(JSID_EMPTY);
1525     LifoAlloc* alloc = constraints->alloc();
1526
1527     typedef CompilerConstraintInstance<ConstraintDataFreezeObjectFlags> T;
1528     constraints->add(alloc->new_<T>(alloc, objectProperty, ConstraintDataFreezeObjectFlags(OBJECT_FLAG_PRE_TENURE)));
1529
1530     return gc::DefaultHeap;
1531 }
1532
1533 namespace {
1534
1535 // Constraint which triggers recompilation on any type change in an inlined
1536 // script. The freeze constraints added to stack type sets will only directly
1537 // invalidate the script containing those stack type sets. To invalidate code
1538 // for scripts into which the base script was inlined, ObjectStateChange is used.
1539 class ConstraintDataFreezeObjectForInlinedCall
1540 {
1541   public:
1542     ConstraintDataFreezeObjectForInlinedCall()
1543     {}
1544
1545     const char* kind() { return "freezeObjectForInlinedCall"; }
1546
1547     bool invalidateOnNewType(Type type) { return false; }
1548     bool invalidateOnNewPropertyState(TypeSet* property) { return false; }
1549     bool invalidateOnNewObjectState(TypeObject* object) {
1550         // We don't keep track of the exact dependencies the caller has on its
1551         // inlined scripts' type sets, so always invalidate the caller.
1552         return true;
1553     }
1554
1555     bool constraintHolds(JSContext* cx,
1556                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1557     {
1558         return true;
1559     }
1560
1561     bool shouldSweep() { return false; }
1562 };
1563
1564 // Constraint which triggers recompilation when the template object for a
1565 // type's new script changes.
1566 class ConstraintDataFreezeObjectForNewScriptTemplate
1567 {
1568     JSObject* templateObject;
1569
1570   public:
1571     explicit ConstraintDataFreezeObjectForNewScriptTemplate(JSObject* templateObject)
1572       : templateObject(templateObject)
1573     {}
1574
1575     const char* kind() { return "freezeObjectForNewScriptTemplate"; }
1576
1577     bool invalidateOnNewType(Type type) { return false; }
1578     bool invalidateOnNewPropertyState(TypeSet* property) { return false; }
1579     bool invalidateOnNewObjectState(TypeObject* object) {
1580         return !object->newScript() || object->newScript()->templateObject != templateObject;
1581     }
1582
1583     bool constraintHolds(JSContext* cx,
1584                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1585     {
1586         return !invalidateOnNewObjectState(property.object()->maybeType());
1587     }
1588
1589     bool shouldSweep() {
1590         // Note: |templateObject| is only used for equality testing.
1591         return false;
1592     }
1593 };
1594
1595 // Constraint which triggers recompilation when a typed array's data becomes
1596 // invalid.
1597 class ConstraintDataFreezeObjectForTypedArrayData
1598 {
1599     void* viewData;
1600     uint32_t length;
1601
1602   public:
1603     explicit ConstraintDataFreezeObjectForTypedArrayData(TypedArrayObject& tarray)
1604       : viewData(tarray.viewData()),
1605         length(tarray.length())
1606     {}
1607
1608     const char* kind() { return "freezeObjectForTypedArrayData"; }
1609
1610     bool invalidateOnNewType(Type type) { return false; }
1611     bool invalidateOnNewPropertyState(TypeSet* property) { return false; }
1612     bool invalidateOnNewObjectState(TypeObject* object) {
1613         TypedArrayObject& tarray = object->singleton()->as<TypedArrayObject>();
1614         return tarray.viewData() != viewData || tarray.length() != length;
1615     }
1616
1617     bool constraintHolds(JSContext* cx,
1618                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1619     {
1620         return !invalidateOnNewObjectState(property.object()->maybeType());
1621     }
1622
1623     bool shouldSweep() {
1624         // Note: |viewData| is only used for equality testing.
1625         return false;
1626     }
1627 };
1628
1629 } /* anonymous namespace */
1630
1631 void
1632 TypeObjectKey::watchStateChangeForInlinedCall(CompilerConstraintList* constraints)
1633 {
1634     HeapTypeSetKey objectProperty = property(JSID_EMPTY);
1635     LifoAlloc* alloc = constraints->alloc();
1636
1637     typedef CompilerConstraintInstance<ConstraintDataFreezeObjectForInlinedCall> T;
1638     constraints->add(alloc->new_<T>(alloc, objectProperty, ConstraintDataFreezeObjectForInlinedCall()));
1639 }
1640
1641 void
1642 TypeObjectKey::watchStateChangeForNewScriptTemplate(CompilerConstraintList* constraints)
1643 {
1644     JSObject* templateObject = asTypeObject()->newScript()->templateObject;
1645     HeapTypeSetKey objectProperty = property(JSID_EMPTY);
1646     LifoAlloc* alloc = constraints->alloc();
1647
1648     typedef CompilerConstraintInstance<ConstraintDataFreezeObjectForNewScriptTemplate> T;
1649     constraints->add(alloc->new_<T>(alloc, objectProperty,
1650                                     ConstraintDataFreezeObjectForNewScriptTemplate(templateObject)));
1651 }
1652
1653 void
1654 TypeObjectKey::watchStateChangeForTypedArrayData(CompilerConstraintList* constraints)
1655 {
1656     TypedArrayObject& tarray = asSingleObject()->as<TypedArrayObject>();
1657     HeapTypeSetKey objectProperty = property(JSID_EMPTY);
1658     LifoAlloc* alloc = constraints->alloc();
1659
1660     typedef CompilerConstraintInstance<ConstraintDataFreezeObjectForTypedArrayData> T;
1661     constraints->add(alloc->new_<T>(alloc, objectProperty,
1662                                     ConstraintDataFreezeObjectForTypedArrayData(tarray)));
1663 }
1664
1665 static void
1666 ObjectStateChange(ExclusiveContext* cxArg, TypeObject* object, bool markingUnknown)
1667 {
1668     if (object->unknownProperties())
1669         return;
1670
1671     /* All constraints listening to state changes are on the empty id. */
1672     HeapTypeSet* types = object->maybeGetProperty(JSID_EMPTY);
1673
1674     /* Mark as unknown after getting the types, to avoid assertion. */
1675     if (markingUnknown)
1676         object->addFlags(OBJECT_FLAG_DYNAMIC_MASK | OBJECT_FLAG_UNKNOWN_PROPERTIES);
1677
1678     if (types) {
1679         if (JSContext* cx = cxArg->maybeJSContext()) {
1680             TypeConstraint* constraint = types->constraintList;
1681             while (constraint) {
1682                 constraint->newObjectState(cx, object);
1683                 constraint = constraint->next;
1684             }
1685         } else {
1686             JS_ASSERT(!types->constraintList);
1687         }
1688     }
1689 }
1690
1691 static void
1692 CheckNewScriptProperties(JSContext* cx, TypeObject* type, JSFunction* fun);
1693
1694 namespace {
1695
1696 class ConstraintDataFreezePropertyState
1697 {
1698   public:
1699     enum Which {
1700         NON_DATA,
1701         NON_WRITABLE
1702     } which;
1703
1704     explicit ConstraintDataFreezePropertyState(Which which)
1705       : which(which)
1706     {}
1707
1708     const char* kind() { return (which == NON_DATA) ? "freezeNonDataProperty" : "freezeNonWritableProperty"; }
1709
1710     bool invalidateOnNewType(Type type) { return false; }
1711     bool invalidateOnNewPropertyState(TypeSet* property) {
1712         return (which == NON_DATA)
1713                ? property->nonDataProperty()
1714                : property->nonWritableProperty();
1715     }
1716     bool invalidateOnNewObjectState(TypeObject* object) { return false; }
1717
1718     bool constraintHolds(JSContext* cx,
1719                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1720     {
1721         return !invalidateOnNewPropertyState(property.maybeTypes());
1722     }
1723
1724     bool shouldSweep() { return false; }
1725 };
1726
1727 } /* anonymous namespace */
1728
1729 bool
1730 HeapTypeSetKey::nonData(CompilerConstraintList* constraints)
1731 {
1732     if (maybeTypes() && maybeTypes()->nonDataProperty())
1733         return true;
1734
1735     LifoAlloc* alloc = constraints->alloc();
1736
1737     typedef CompilerConstraintInstance<ConstraintDataFreezePropertyState> T;
1738     constraints->add(alloc->new_<T>(alloc, *this,
1739                                     ConstraintDataFreezePropertyState(ConstraintDataFreezePropertyState::NON_DATA)));
1740     return false;
1741 }
1742
1743 bool
1744 HeapTypeSetKey::nonWritable(CompilerConstraintList* constraints)
1745 {
1746     if (maybeTypes() && maybeTypes()->nonWritableProperty())
1747         return true;
1748
1749     LifoAlloc* alloc = constraints->alloc();
1750
1751     typedef CompilerConstraintInstance<ConstraintDataFreezePropertyState> T;
1752     constraints->add(alloc->new_<T>(alloc, *this,
1753                                     ConstraintDataFreezePropertyState(ConstraintDataFreezePropertyState::NON_WRITABLE)));
1754     return false;
1755 }
1756
1757 namespace {
1758
1759 class ConstraintDataConstantProperty
1760 {
1761   public:
1762     explicit ConstraintDataConstantProperty() {}
1763
1764     const char* kind() { return "constantProperty"; }
1765
1766     bool invalidateOnNewType(Type type) { return false; }
1767     bool invalidateOnNewPropertyState(TypeSet* property) {
1768         return property->nonConstantProperty();
1769     }
1770     bool invalidateOnNewObjectState(TypeObject* object) { return false; }
1771
1772     bool constraintHolds(JSContext* cx,
1773                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1774     {
1775         return !invalidateOnNewPropertyState(property.maybeTypes());
1776     }
1777
1778     bool shouldSweep() { return false; }
1779 };
1780
1781 } /* anonymous namespace */
1782
1783 bool
1784 HeapTypeSetKey::constant(CompilerConstraintList* constraints, Value* valOut)
1785 {
1786     if (nonData(constraints))
1787         return false;
1788
1789     // Only singleton object properties can be marked as constants.
1790     JSObject* obj = object()->singleton();
1791     if (!obj || !obj->isNative())
1792         return false;
1793
1794     if (maybeTypes() && maybeTypes()->nonConstantProperty())
1795         return false;
1796
1797     // Get the current value of the property.
1798     Shape* shape = obj->nativeLookupPure(id());
1799     if (!shape || !shape->hasDefaultGetter() || !shape->hasSlot() || shape->hadOverwrite())
1800         return false;
1801
1802     Value val = obj->nativeGetSlot(shape->slot());
1803
1804     // If the value is a pointer to an object in the nursery, don't optimize.
1805     if (val.isGCThing() && IsInsideNursery(val.toGCThing()))
1806         return false;
1807
1808     // If the value is a string that's not atomic, don't optimize.
1809     if (val.isString() && !val.toString()->isAtom())
1810         return false;
1811
1812     *valOut = val;
1813
1814     LifoAlloc* alloc = constraints->alloc();
1815     typedef CompilerConstraintInstance<ConstraintDataConstantProperty> T;
1816     constraints->add(alloc->new_<T>(alloc, *this, ConstraintDataConstantProperty()));
1817     return true;
1818 }
1819
1820 bool
1821 TemporaryTypeSet::filtersType(const TemporaryTypeSet* other, Type filteredType) const
1822 {
1823     if (other->unknown())
1824         return unknown();
1825
1826     for (TypeFlags flag = 1; flag < TYPE_FLAG_ANYOBJECT; flag <<= 1) {
1827         Type type = Type::PrimitiveType(TypeFlagPrimitive(flag));
1828         if (type != filteredType && other->hasType(type) && !hasType(type))
1829             return false;
1830     }
1831
1832     if (other->unknownObject())
1833         return unknownObject();
1834
1835     for (size_t i = 0; i < other->getObjectCount(); i++) {
1836         TypeObjectKey* key = other->getObject(i);
1837         if (key) {
1838             Type type = Type::ObjectType(key);
1839             if (type != filteredType && !hasType(type))
1840                 return false;
1841         }
1842     }
1843
1844     return true;
1845 }
1846
1847 namespace {
1848
1849 // A constraint that never triggers recompilation.
1850 class ConstraintDataInert
1851 {
1852   public:
1853     explicit ConstraintDataInert() {}
1854
1855     const char* kind() { return "inert"; }
1856
1857     bool invalidateOnNewType(Type type) { return false; }
1858     bool invalidateOnNewPropertyState(TypeSet* property) { return false; }
1859     bool invalidateOnNewObjectState(TypeObject* object) { return false; }
1860
1861     bool constraintHolds(JSContext* cx,
1862                          const HeapTypeSetKey& property, TemporaryTypeSet* expected)
1863     {
1864         return true;
1865     }
1866
1867     bool shouldSweep() { return false; }
1868 };
1869
1870 } /* anonymous namespace */
1871
1872 bool
1873 TemporaryTypeSet::propertyMightBeConstant(CompilerConstraintList* constraints, jsid id)
1874 {
1875     if (unknownObject())
1876         return true;
1877
1878     for (size_t i = 0; i < getObjectCount(); i++) {
1879         TypeObjectKey* type = getObject(i);
1880
1881         // Type sets are only marked as constants when they are lazily
1882         // constructed from the properties of singleton typed objects. So watch
1883         // for the cases when a property either already is or might be marked
1884         // as constant in the future.
1885
1886         if (!type || !type->isSingleObject())
1887             continue;
1888
1889         if (type->unknownProperties())
1890             return true;
1891
1892         HeapTypeSetKey property = type->property(id);
1893         if (!property.maybeTypes() || !property.maybeTypes()->nonConstantProperty())
1894             return true;
1895     }
1896
1897     // It is possible for a property that was not marked as constant to
1898     // 'become' one, if we throw away the type property during a GC and
1899     // regenerate it with the constant flag set. TypeObject::sweep only removes
1900     // type properties if they have no constraints attached to them, so add
1901     // inert constraints to pin these properties in place.
1902
1903     LifoAlloc* alloc = constraints->alloc();
1904     for (size_t i = 0; i < getObjectCount(); i++) {
1905         TypeObjectKey* type = getObject(i);
1906
1907         if (!type || !type->isSingleObject())
1908             continue;
1909
1910         HeapTypeSetKey property = type->property(id);
1911
1912         typedef CompilerConstraintInstance<ConstraintDataInert> T;
1913         constraints->add(alloc->new_<T>(alloc, property, ConstraintDataInert()));
1914     }
1915
1916     return false;
1917 }
1918
1919 bool
1920 TemporaryTypeSet::propertyIsConstant(CompilerConstraintList* constraints, jsid id, Value* valOut)
1921 {
1922     JS_ASSERT(valOut);
1923
1924     JSObject* singleton = getSingleton();
1925     if (!singleton)
1926         return false;
1927
1928     TypeObjectKey* type = TypeObjectKey::get(singleton);
1929     if (type->unknownProperties())
1930         return false;
1931
1932     HeapTypeSetKey property = type->property(id);
1933     return property.constant(constraints, valOut);
1934 }
1935
1936 TemporaryTypeSet::DoubleConversion
1937 TemporaryTypeSet::convertDoubleElements(CompilerConstraintList* constraints)
1938 {
1939     if (unknownObject() || !getObjectCount())
1940         return AmbiguousDoubleConversion;
1941
1942     bool alwaysConvert = true;
1943     bool maybeConvert = false;
1944     bool dontConvert = false;
1945
1946     for (unsigned i = 0; i < getObjectCount(); i++) {
1947         TypeObjectKey* type = getObject(i);
1948         if (!type)
1949             continue;
1950
1951         if (type->unknownProperties()) {
1952             alwaysConvert = false;
1953             continue;
1954         }
1955
1956         HeapTypeSetKey property = type->property(JSID_VOID);
1957         property.freeze(constraints);
1958
1959         // We can't convert to double elements for objects which do not have
1960         // double in their element types (as the conversion may render the type
1961         // information incorrect), nor for non-array objects (as their elements
1962         // may point to emptyObjectElements, which cannot be converted).
1963         if (!property.maybeTypes() ||
1964             !property.maybeTypes()->hasType(Type::DoubleType()) ||
1965             type->clasp() != &ArrayObject::class_)
1966         {
1967             dontConvert = true;
1968             alwaysConvert = false;
1969             continue;
1970         }
1971
1972         // Only bother with converting known packed arrays whose possible
1973         // element types are int or double. Other arrays require type tests
1974         // when elements are accessed regardless of the conversion.
1975         if (property.knownMIRType(constraints) == jit::MIRType_Double &&
1976             !type->hasFlags(constraints, OBJECT_FLAG_NON_PACKED))
1977         {
1978             maybeConvert = true;
1979         } else {
1980             alwaysConvert = false;
1981         }
1982     }
1983
1984     JS_ASSERT_IF(alwaysConvert, maybeConvert);
1985
1986     if (maybeConvert && dontConvert)
1987         return AmbiguousDoubleConversion;
1988     if (alwaysConvert)
1989         return AlwaysConvertToDoubles;
1990     if (maybeConvert)
1991         return MaybeConvertToDoubles;
1992     return DontConvertToDoubles;
1993 }
1994
1995 const Class*
1996 TemporaryTypeSet::getKnownClass()
1997 {
1998     if (unknownObject())
1999         return nullptr;
2000
2001     const Class* clasp = nullptr;
2002     unsigned count = getObjectCount();
2003
2004     for (unsigned i = 0; i < count; i++) {
2005         const Class* nclasp = getObjectClass(i);
2006         if (!nclasp)
2007             continue;
2008
2009         if (clasp && clasp != nclasp)
2010             return nullptr;
2011         clasp = nclasp;
2012     }
2013
2014     return clasp;
2015 }
2016
2017 TemporaryTypeSet::ForAllResult
2018 TemporaryTypeSet::forAllClasses(bool (*func)(const Class* clasp))
2019 {
2020     if (unknownObject())
2021         return ForAllResult::MIXED;
2022
2023     unsigned count = getObjectCount();
2024     if (count == 0)
2025         return ForAllResult::EMPTY;
2026
2027     bool true_results = false;
2028     bool false_results = false;
2029     for (unsigned i = 0; i < count; i++) {
2030         const Class* clasp = getObjectClass(i);
2031         if (!clasp)
2032             return ForAllResult::MIXED;
2033         if (func(clasp)) {
2034             true_results = true;
2035             if (false_results) return ForAllResult::MIXED;
2036         }
2037         else {
2038             false_results = true;
2039             if (true_results) return ForAllResult::MIXED;
2040         }
2041     }
2042
2043     JS_ASSERT(true_results != false_results);
2044
2045     return true_results ? ForAllResult::ALL_TRUE : ForAllResult::ALL_FALSE;
2046 }
2047
2048 Scalar::Type
2049 TemporaryTypeSet::getTypedArrayType()
2050 {
2051     const Class* clasp = getKnownClass();
2052
2053     if (clasp && IsTypedArrayClass(clasp))
2054         return (Scalar::Type) (clasp - &TypedArrayObject::classes[0]);
2055     return Scalar::TypeMax;
2056 }
2057
2058 bool
2059 TemporaryTypeSet::isDOMClass()
2060 {
2061     if (unknownObject())
2062         return false;
2063
2064     unsigned count = getObjectCount();
2065     for (unsigned i = 0; i < count; i++) {
2066         const Class* clasp = getObjectClass(i);
2067         if (clasp && !clasp->isDOMClass())
2068             return false;
2069     }
2070
2071     return count > 0;
2072 }
2073
2074 bool
2075 TemporaryTypeSet::maybeCallable()
2076 {
2077     if (!maybeObject())
2078         return false;
2079
2080     if (unknownObject())
2081         return true;
2082
2083     unsigned count = getObjectCount();
2084     for (unsigned i = 0; i < count; i++) {
2085         const Class* clasp = getObjectClass(i);
2086         if (clasp && clasp->isCallable())
2087             return true;
2088     }
2089
2090     return false;
2091 }
2092
2093 bool
2094 TemporaryTypeSet::maybeEmulatesUndefined()
2095 {
2096     if (!maybeObject())
2097         return false;
2098
2099     if (unknownObject())
2100         return true;
2101
2102     unsigned count = getObjectCount();
2103     for (unsigned i = 0; i < count; i++) {
2104         // The object emulates undefined if clasp->emulatesUndefined() or if
2105         // it's a WrapperObject, see EmulatesUndefined. Since all wrappers are
2106         // proxies, we can just check for that.
2107         const Class* clasp = getObjectClass(i);
2108         if (clasp && (clasp->emulatesUndefined() || clasp->isProxy()))
2109             return true;
2110     }
2111
2112     return false;
2113 }
2114
2115 JSObject*
2116 TemporaryTypeSet::getCommonPrototype()
2117 {
2118     if (unknownObject())
2119         return nullptr;
2120
2121     JSObject* proto = nullptr;
2122     unsigned count = getObjectCount();
2123
2124     for (unsigned i = 0; i < count; i++) {
2125         TypeObjectKey* object = getObject(i);
2126         if (!object)
2127             continue;
2128
2129         if (!object->hasTenuredProto())
2130             return nullptr;
2131
2132         TaggedProto nproto = object->proto();
2133         if (proto) {
2134             if (nproto != TaggedProto(proto))
2135                 return nullptr;
2136         } else {
2137             if (!nproto.isObject())
2138                 return nullptr;
2139             proto = nproto.toObject();
2140         }
2141     }
2142
2143     return proto;
2144 }
2145
2146 bool
2147 TemporaryTypeSet::propertyNeedsBarrier(CompilerConstraintList* constraints, jsid id)
2148 {
2149     if (unknownObject())
2150         return true;
2151
2152     for (unsigned i = 0; i < getObjectCount(); i++) {
2153         TypeObjectKey* type = getObject(i);
2154         if (!type)
2155             continue;
2156
2157         if (type->unknownProperties())
2158             return true;
2159
2160         HeapTypeSetKey property = type->property(id);
2161         if (property.needsBarrier(constraints))
2162             return true;
2163     }
2164
2165     return false;
2166 }
2167
2168 /////////////////////////////////////////////////////////////////////
2169 // TypeCompartment
2170 /////////////////////////////////////////////////////////////////////
2171
2172 TypeCompartment::TypeCompartment()
2173 {
2174     PodZero(this);
2175 }
2176
2177 TypeObject*
2178 TypeCompartment::newTypeObject(ExclusiveContext* cx, const Class* clasp, Handle<TaggedProto> proto,
2179                                TypeObjectFlags initialFlags)
2180 {
2181     JS_ASSERT_IF(proto.isObject(), cx->isInsideCurrentCompartment(proto.toObject()));
2182
2183     if (cx->isJSContext()) {
2184         if (proto.isObject() && IsInsideNursery(proto.toObject()))
2185             initialFlags |= OBJECT_FLAG_NURSERY_PROTO;
2186     }
2187
2188     TypeObject* object = js::NewTypeObject(cx);
2189     if (!object)
2190         return nullptr;
2191     new(object) TypeObject(clasp, proto, initialFlags);
2192
2193     return object;
2194 }
2195
2196 TypeObject*
2197 TypeCompartment::addAllocationSiteTypeObject(JSContext* cx, AllocationSiteKey key)
2198 {
2199     AutoEnterAnalysis enter(cx);
2200
2201     if (!allocationSiteTable) {
2202         allocationSiteTable = cx->new_<AllocationSiteTable>();
2203         if (!allocationSiteTable || !allocationSiteTable->init()) {
2204             js_delete(allocationSiteTable);
2205             allocationSiteTable = nullptr;
2206             return nullptr;
2207         }
2208     }
2209
2210     AllocationSiteTable::AddPtr p = allocationSiteTable->lookupForAdd(key);
2211     JS_ASSERT(!p);
2212
2213     TypeObject* res = nullptr;
2214
2215     jsbytecode* pc = key.script->offsetToPC(key.offset);
2216     RootedScript keyScript(cx, key.script);
2217
2218     if (!res) {
2219         RootedObject proto(cx);
2220         if (!GetBuiltinPrototype(cx, key.kind, &proto))
2221             return nullptr;
2222
2223         Rooted<TaggedProto> tagged(cx, TaggedProto(proto));
2224         res = newTypeObject(cx, GetClassForProtoKey(key.kind), tagged, OBJECT_FLAG_FROM_ALLOCATION_SITE);
2225         if (!res)
2226             return nullptr;
2227         key.script = keyScript;
2228     }
2229
2230     if (JSOp(*pc) == JSOP_NEWOBJECT) {
2231         /*
2232          * This object is always constructed the same way and will not be
2233          * observed by other code before all properties have been added. Mark
2234          * all the properties as definite properties of the object.
2235          */
2236         RootedObject baseobj(cx, key.script->getObject(GET_UINT32_INDEX(pc)));
2237
2238         if (!res->addDefiniteProperties(cx, baseobj))
2239             return nullptr;
2240     }
2241
2242     if (!allocationSiteTable->add(p, key, res))
2243         return nullptr;
2244
2245     return res;
2246 }
2247
2248 static inline jsid
2249 GetAtomId(JSContext* cx, JSScript* script, const jsbytecode* pc, unsigned offset)
2250 {
2251     PropertyName* name = script->getName(GET_UINT32_INDEX(pc + offset));
2252     return IdToTypeId(NameToId(name));
2253 }
2254
2255 bool
2256 types::UseNewType(JSContext* cx, JSScript* script, jsbytecode* pc)
2257 {
2258     /*
2259      * Make a heuristic guess at a use of JSOP_NEW that the constructed object
2260      * should have a fresh type object. We do this when the NEW is immediately
2261      * followed by a simple assignment to an object's .prototype field.
2262      * This is designed to catch common patterns for subclassing in JS:
2263      *
2264      * function Super() { ... }
2265      * function Sub1() { ... }
2266      * function Sub2() { ... }
2267      *
2268      * Sub1.prototype = new Super();
2269      * Sub2.prototype = new Super();
2270      *
2271      * Using distinct type objects for the particular prototypes of Sub1 and
2272      * Sub2 lets us continue to distinguish the two subclasses and any extra
2273      * properties added to those prototype objects.
2274      */
2275     if (JSOp(*pc) != JSOP_NEW)
2276         return false;
2277     pc += JSOP_NEW_LENGTH;
2278     if (JSOp(*pc) == JSOP_SETPROP) {
2279         jsid id = GetAtomId(cx, script, pc, 0);
2280         if (id == id_prototype(cx))
2281             return true;
2282     }
2283
2284     return false;
2285 }
2286
2287 NewObjectKind
2288 types::UseNewTypeForInitializer(JSScript* script, jsbytecode* pc, JSProtoKey key)
2289 {
2290     /*
2291      * Objects created outside loops in global and eval scripts should have
2292      * singleton types. For now this is only done for plain objects and typed
2293      * arrays, but not normal arrays.
2294      */
2295
2296     if (script->functionNonDelazifying() && !script->treatAsRunOnce())
2297         return GenericObject;
2298
2299     if (key != JSProto_Object && !(key >= JSProto_Int8Array && key <= JSProto_Uint8ClampedArray))
2300         return GenericObject;
2301
2302     /*
2303      * All loops in the script will have a JSTRY_ITER or JSTRY_LOOP try note
2304      * indicating their boundary.
2305      */
2306
2307     if (!script->hasTrynotes())
2308         return SingletonObject;
2309
2310     unsigned offset = script->pcToOffset(pc);
2311
2312     JSTryNote* tn = script->trynotes()->vector;
2313     JSTryNote* tnlimit = tn + script->trynotes()->length;
2314     for (; tn < tnlimit; tn++) {
2315         if (tn->kind != JSTRY_ITER && tn->kind != JSTRY_LOOP)
2316             continue;
2317
2318         unsigned startOffset = script->mainOffset() + tn->start;
2319         unsigned endOffset = startOffset + tn->length;
2320
2321         if (offset >= startOffset && offset < endOffset)
2322             return GenericObject;
2323     }
2324
2325     return SingletonObject;
2326 }
2327
2328 NewObjectKind
2329 types::UseNewTypeForInitializer(JSScript* script, jsbytecode* pc, const Class* clasp)
2330 {
2331     return UseNewTypeForInitializer(script, pc, JSCLASS_CACHED_PROTO_KEY(clasp));
2332 }
2333
2334 static inline bool
2335 ClassCanHaveExtraProperties(const Class* clasp)
2336 {
2337     JS_ASSERT(clasp->resolve);
2338     return clasp->resolve != JS_ResolveStub
2339         || clasp->ops.lookupGeneric
2340         || clasp->ops.getGeneric
2341         || IsTypedArrayClass(clasp);
2342 }
2343
2344 static inline bool
2345 PrototypeHasIndexedProperty(CompilerConstraintList* constraints, JSObject* obj)
2346 {
2347     do {
2348         TypeObjectKey* type = TypeObjectKey::get(obj);
2349         if (ClassCanHaveExtraProperties(type->clasp()))
2350             return true;
2351         if (type->unknownProperties())
2352             return true;
2353         HeapTypeSetKey index = type->property(JSID_VOID);
2354         if (index.nonData(constraints) || index.isOwnProperty(constraints))
2355             return true;
2356         if (!obj->hasTenuredProto())
2357             return true;
2358         obj = obj->getProto();
2359     } while (obj);
2360
2361     return false;
2362 }
2363
2364 bool
2365 types::ArrayPrototypeHasIndexedProperty(CompilerConstraintList* constraints, JSScript* script)
2366 {
2367     if (JSObject* proto = script->global().maybeGetArrayPrototype())
2368         return PrototypeHasIndexedProperty(constraints, proto);
2369     return true;
2370 }
2371
2372 bool
2373 types::TypeCanHaveExtraIndexedProperties(CompilerConstraintList* constraints,
2374                                          TemporaryTypeSet* types)
2375 {
2376     const Class* clasp = types->getKnownClass();
2377
2378     // Note: typed arrays have indexed properties not accounted for by type
2379     // information, though these are all in bounds and will be accounted for
2380     // by JIT paths.
2381     if (!clasp || (ClassCanHaveExtraProperties(clasp) && !IsTypedArrayClass(clasp)))
2382         return true;
2383
2384     if (types->hasObjectFlags(constraints, types::OBJECT_FLAG_SPARSE_INDEXES))
2385         return true;
2386
2387     JSObject* proto = types->getCommonPrototype();
2388     if (!proto)
2389         return true;
2390
2391     return PrototypeHasIndexedProperty(constraints, proto);
2392 }
2393
2394 void
2395 TypeZone::processPendingRecompiles(FreeOp* fop)
2396 {
2397     if (!pendingRecompiles)
2398         return;
2399
2400     /* Steal the list of scripts to recompile, else we will try to recursively recompile them. */
2401     Vector<RecompileInfo>* pending = pendingRecompiles;
2402     pendingRecompiles = nullptr;
2403
2404     JS_ASSERT(!pending->empty());
2405
2406     jit::Invalidate(*this, fop, *pending);
2407
2408     fop->delete_(pending);
2409 }
2410
2411 void
2412 TypeZone::addPendingRecompile(JSContext* cx, const RecompileInfo& info)
2413 {
2414     CompilerOutput* co = info.compilerOutput(cx);
2415     if (!co || !co->isValid() || co->pendingInvalidation())
2416         return;
2417
2418     InferSpew(ISpewOps, "addPendingRecompile: %p:%s:%d",
2419               co->script(), co->script()->filename(), co->script()->lineno());
2420
2421     co->setPendingInvalidation();
2422
2423     if (!pendingRecompiles) {
2424         pendingRecompiles = cx->new_< Vector<RecompileInfo> >(cx);
2425         if (!pendingRecompiles)
2426             CrashAtUnhandlableOOM("Could not update pendingRecompiles");
2427     }
2428
2429     if (!pendingRecompiles->append(info))
2430         CrashAtUnhandlableOOM("Could not update pendingRecompiles");
2431 }
2432
2433 void
2434 TypeZone::addPendingRecompile(JSContext* cx, JSScript* script)
2435 {
2436     JS_ASSERT(script);
2437
2438     CancelOffThreadIonCompile(cx->compartment(), script);
2439
2440     // Let the script warm up again before attempting another compile.
2441     if (jit::IsBaselineEnabled(cx))
2442         script->resetUseCount();
2443
2444     if (script->hasIonScript())
2445         addPendingRecompile(cx, script->ionScript()->recompileInfo());
2446
2447     if (script->hasParallelIonScript())
2448         addPendingRecompile(cx, script->parallelIonScript()->recompileInfo());
2449
2450     // When one script is inlined into another the caller listens to state
2451     // changes on the callee's script, so trigger these to force recompilation
2452     // of any such callers.
2453     if (script->functionNonDelazifying() && !script->functionNonDelazifying()->hasLazyType())
2454         ObjectStateChange(cx, script->functionNonDelazifying()->type(), false);
2455 }
2456
2457 void
2458 TypeCompartment::markSetsUnknown(JSContext* cx, TypeObject* target)
2459 {
2460     JS_ASSERT(this == &cx->compartment()->types);
2461     JS_ASSERT(!(target->flags() & OBJECT_FLAG_SETS_MARKED_UNKNOWN));
2462     JS_ASSERT(!target->singleton());
2463     JS_ASSERT(target->unknownProperties());
2464
2465     AutoEnterAnalysis enter(cx);
2466
2467     /* Mark type sets which contain obj as having a generic object types. */
2468
2469     for (gc::ZoneCellIter i(cx->zone(), gc::FINALIZE_TYPE_OBJECT); !i.done(); i.next()) {
2470         TypeObject* object = i.get<TypeObject>();
2471         unsigned count = object->getPropertyCount();
2472         for (unsigned i = 0; i < count; i++) {
2473             Property* prop = object->getProperty(i);
2474             if (prop && prop->types.hasType(Type::ObjectType(target)))
2475                 prop->types.addType(cx, Type::AnyObjectType());
2476         }
2477     }
2478
2479     for (gc::ZoneCellIter i(cx->zone(), gc::FINALIZE_SCRIPT); !i.done(); i.next()) {
2480         JSScript* script = i.get<JSScript>();
2481         if (script->types) {
2482             unsigned count = TypeScript::NumTypeSets(script);
2483             StackTypeSet* typeArray = script->types->typeArray();
2484             for (unsigned i = 0; i < count; i++) {
2485                 if (typeArray[i].hasType(Type::ObjectType(target)))
2486                     typeArray[i].addType(cx, Type::AnyObjectType());
2487             }
2488         }
2489     }
2490
2491     target->addFlags(OBJECT_FLAG_SETS_MARKED_UNKNOWN);
2492 }
2493
2494 void
2495 TypeCompartment::print(JSContext* cx, bool force)
2496 {
2497 #ifdef DEBUG
2498     gc::AutoSuppressGC suppressGC(cx);
2499     JSAutoRequest request(cx);
2500
2501     JSCompartment* compartment = this->compartment();
2502     AutoEnterAnalysis enter(nullptr, compartment);
2503
2504     if (!force && !InferSpewActive(ISpewResult))
2505         return;
2506
2507     for (gc::ZoneCellIter i(compartment->zone(), gc::FINALIZE_SCRIPT); !i.done(); i.next()) {
2508         // Note: use cx->runtime() instead of cx to work around IsInRequest(cx)
2509         // assertion failures when we're called from DestroyContext.
2510         RootedScript script(cx->runtime(), i.get<JSScript>());
2511         if (script->types)
2512             script->types->printTypes(cx, script);
2513     }
2514
2515     for (gc::ZoneCellIter i(compartment->zone(), gc::FINALIZE_TYPE_OBJECT); !i.done(); i.next()) {
2516         TypeObject* object = i.get<TypeObject>();
2517         object->print();
2518     }
2519 #endif
2520 }
2521
2522 /////////////////////////////////////////////////////////////////////
2523 // TypeCompartment tables
2524 /////////////////////////////////////////////////////////////////////
2525
2526 /*
2527  * The arrayTypeTable and objectTypeTable are per-compartment tables for making
2528  * common type objects to model the contents of large script singletons and
2529  * JSON objects. These are vanilla Arrays and native Objects, so we distinguish
2530  * the types of different ones by looking at the types of their properties.
2531  *
2532  * All singleton/JSON arrays which have the same prototype, are homogenous and
2533  * of the same element type will share a type object. All singleton/JSON
2534  * objects which have the same shape and property types will also share a type
2535  * object. We don't try to collate arrays or objects that have type mismatches.
2536  */
2537
2538 static inline bool
2539 NumberTypes(Type a, Type b)
2540 {
2541     return (a.isPrimitive(JSVAL_TYPE_INT32) || a.isPrimitive(JSVAL_TYPE_DOUBLE))
2542         && (b.isPrimitive(JSVAL_TYPE_INT32) || b.isPrimitive(JSVAL_TYPE_DOUBLE));
2543 }
2544
2545 /*
2546  * As for GetValueType, but requires object types to be non-singletons with
2547  * their default prototype. These are the only values that should appear in
2548  * arrays and objects whose type can be fixed.
2549  */
2550 static inline Type
2551 GetValueTypeForTable(const Value& v)
2552 {
2553     Type type = GetValueType(v);
2554     JS_ASSERT(!type.isSingleObject());
2555     return type;
2556 }
2557
2558 struct types::ArrayTableKey : public DefaultHasher<types::ArrayTableKey>
2559 {
2560     Type type;
2561     JSObject* proto;
2562
2563     ArrayTableKey()
2564       : type(Type::UndefinedType()), proto(nullptr)
2565     {}
2566
2567     ArrayTableKey(Type type, JSObject* proto)
2568       : type(type), proto(proto)
2569     {}
2570
2571     static inline uint32_t hash(const ArrayTableKey& v) {
2572         return (uint32_t) (v.type.raw() ^ ((uint32_t)(size_t)v.proto >> 2));
2573     }
2574
2575     static inline bool match(const ArrayTableKey& v1, const ArrayTableKey& v2) {
2576         return v1.type == v2.type && v1.proto == v2.proto;
2577     }
2578 };
2579
2580 void
2581 TypeCompartment::setTypeToHomogenousArray(ExclusiveContext* cx,
2582                                           JSObject* obj, Type elementType)
2583 {
2584     JS_ASSERT(cx->compartment()->activeAnalysis);
2585
2586     if (!arrayTypeTable) {
2587         arrayTypeTable = cx->new_<ArrayTypeTable>();
2588         if (!arrayTypeTable || !arrayTypeTable->init()) {
2589             arrayTypeTable = nullptr;
2590             return;
2591         }
2592     }
2593
2594     ArrayTableKey key(elementType, obj->getProto());
2595     DependentAddPtr<ArrayTypeTable> p(cx, *arrayTypeTable, key);
2596     if (p) {
2597         obj->setType(p->value());
2598     } else {
2599         /* Make a new type to use for future arrays with the same elements. */
2600         RootedObject objProto(cx, obj->getProto());
2601         Rooted<TaggedProto> taggedProto(cx, TaggedProto(objProto));
2602         TypeObject* objType = newTypeObject(cx, &ArrayObject::class_, taggedProto);
2603         if (!objType)
2604             return;
2605         obj->setType(objType);
2606
2607         if (!objType->unknownProperties())
2608             objType->addPropertyType(cx, JSID_VOID, elementType);
2609
2610         key.proto = objProto;
2611         (void) p.add(cx, *arrayTypeTable, key, objType);
2612     }
2613 }
2614
2615 void
2616 TypeCompartment::fixArrayType(ExclusiveContext* cx, JSObject* obj)
2617 {
2618     AutoEnterAnalysis enter(cx);
2619
2620     /*
2621      * If the array is of homogenous type, pick a type object which will be
2622      * shared with all other singleton/JSON arrays of the same type.
2623      * If the array is heterogenous, keep the existing type object, which has
2624      * unknown properties.
2625      */
2626     JS_ASSERT(obj->is<ArrayObject>());
2627
2628     unsigned len = obj->getDenseInitializedLength();
2629     if (len == 0)
2630         return;
2631
2632     Type type = GetValueTypeForTable(obj->getDenseElement(0));
2633
2634     for (unsigned i = 1; i < len; i++) {
2635         Type ntype = GetValueTypeForTable(obj->getDenseElement(i));
2636         if (ntype != type) {
2637             if (NumberTypes(type, ntype))
2638                 type = Type::DoubleType();
2639             else
2640                 return;
2641         }
2642     }
2643
2644     setTypeToHomogenousArray(cx, obj, type);
2645 }
2646
2647 void
2648 types::FixRestArgumentsType(ExclusiveContext* cx, JSObject* obj)
2649 {
2650     cx->compartment()->types.fixRestArgumentsType(cx, obj);
2651 }
2652
2653 void
2654 TypeCompartment::fixRestArgumentsType(ExclusiveContext* cx, JSObject* obj)
2655 {
2656     AutoEnterAnalysis enter(cx);
2657
2658     /*
2659      * Tracking element types for rest argument arrays is not worth it, but we
2660      * still want it to be known that it's a dense array.
2661      */
2662     JS_ASSERT(obj->is<ArrayObject>());
2663
2664     setTypeToHomogenousArray(cx, obj, Type::UnknownType());
2665 }
2666
2667 /*
2668  * N.B. We could also use the initial shape of the object (before its type is
2669  * fixed) as the key in the object table, but since all references in the table
2670  * are weak the hash entries would usually be collected on GC even if objects
2671  * with the new type/shape are still live.
2672  */
2673 struct types::ObjectTableKey
2674 {
2675     jsid* properties;
2676     uint32_t nproperties;
2677     uint32_t nfixed;
2678
2679     struct Lookup {
2680         IdValuePair* properties;
2681         uint32_t nproperties;
2682         uint32_t nfixed;
2683
2684         Lookup(IdValuePair* properties, uint32_t nproperties, uint32_t nfixed)
2685           : properties(properties), nproperties(nproperties), nfixed(nfixed)
2686         {}
2687     };
2688
2689     static inline HashNumber hash(const Lookup& lookup) {
2690         return (HashNumber) (JSID_BITS(lookup.properties[lookup.nproperties - 1].id) ^
2691                              lookup.nproperties ^
2692                              lookup.nfixed);
2693     }
2694
2695     static inline bool match(const ObjectTableKey& v, const Lookup& lookup) {
2696         if (lookup.nproperties != v.nproperties || lookup.nfixed != v.nfixed)
2697             return false;
2698         for (size_t i = 0; i < lookup.nproperties; i++) {
2699             if (lookup.properties[i].id != v.properties[i])
2700                 return false;
2701         }
2702         return true;
2703     }
2704 };
2705
2706 struct types::ObjectTableEntry
2707 {
2708     ReadBarrieredTypeObject object;
2709     ReadBarrieredShape shape;
2710     Type* types;
2711 };
2712
2713 static inline void
2714 UpdateObjectTableEntryTypes(ExclusiveContext* cx, ObjectTableEntry& entry,
2715                             IdValuePair* properties, size_t nproperties)
2716 {
2717     if (entry.object->unknownProperties())
2718         return;
2719     for (size_t i = 0; i < nproperties; i++) {
2720         Type type = entry.types[i];
2721         Type ntype = GetValueTypeForTable(properties[i].value);
2722         if (ntype == type)
2723             continue;
2724         if (ntype.isPrimitive(JSVAL_TYPE_INT32) &&
2725             type.isPrimitive(JSVAL_TYPE_DOUBLE))
2726         {
2727             /* The property types already reflect 'int32'. */
2728         } else {
2729             if (ntype.isPrimitive(JSVAL_TYPE_DOUBLE) &&
2730                 type.isPrimitive(JSVAL_TYPE_INT32))
2731             {
2732                 /* Include 'double' in the property types to avoid the update below later. */
2733                 entry.types[i] = Type::DoubleType();
2734             }
2735             entry.object->addPropertyType(cx, IdToTypeId(properties[i].id), ntype);
2736         }
2737     }
2738 }
2739
2740 void
2741 TypeCompartment::fixObjectType(ExclusiveContext* cx, JSObject* obj)
2742 {
2743     AutoEnterAnalysis enter(cx);
2744
2745     if (!objectTypeTable) {
2746         objectTypeTable = cx->new_<ObjectTypeTable>();
2747         if (!objectTypeTable || !objectTypeTable->init()) {
2748             js_delete(objectTypeTable);
2749             objectTypeTable = nullptr;
2750             return;
2751         }
2752     }
2753
2754     /*
2755      * Use the same type object for all singleton/JSON objects with the same
2756      * base shape, i.e. the same fields written in the same order.
2757      */
2758     JS_ASSERT(obj->is<JSObject>());
2759
2760     /*
2761      * Exclude some objects we can't readily associate common types for based on their
2762      * shape. Objects with metadata are excluded so that the metadata does not need to
2763      * be included in the table lookup (the metadata object might be in the nursery).
2764      */
2765     if (obj->slotSpan() == 0 || obj->inDictionaryMode() || !obj->hasEmptyElements() || obj->getMetadata())
2766         return;
2767
2768     Vector<IdValuePair> properties(cx);
2769     if (!properties.resize(obj->slotSpan()))
2770         return;
2771
2772     Shape* shape = obj->lastProperty();
2773     while (!shape->isEmptyShape()) {
2774         IdValuePair& entry = properties[shape->slot()];
2775         entry.id = shape->propid();
2776         entry.value = obj->getSlot(shape->slot());
2777         shape = shape->previous();
2778     }
2779
2780     ObjectTableKey::Lookup lookup(properties.begin(), properties.length(), obj->numFixedSlots());
2781     ObjectTypeTable::AddPtr p = objectTypeTable->lookupForAdd(lookup);
2782
2783     if (p) {
2784         JS_ASSERT(obj->getProto() == p->value().object->proto().toObject());
2785         JS_ASSERT(obj->lastProperty() == p->value().shape);
2786
2787         UpdateObjectTableEntryTypes(cx, p->value(), properties.begin(), properties.length());
2788         obj->setType(p->value().object);
2789         return;
2790     }
2791
2792     /* Make a new type to use for the object and similar future ones. */
2793     Rooted<TaggedProto> objProto(cx, obj->getTaggedProto());
2794     TypeObject* objType = newTypeObject(cx, &JSObject::class_, objProto);
2795     if (!objType || !objType->addDefiniteProperties(cx, obj))
2796         return;
2797
2798     if (obj->isIndexed())
2799         objType->setFlags(cx, OBJECT_FLAG_SPARSE_INDEXES);
2800
2801     ScopedJSFreePtr<jsid> ids(objType->pod_calloc<jsid>(properties.length()));
2802     if (!ids)
2803         return;
2804
2805     ScopedJSFreePtr<Type> types(objType->pod_calloc<Type>(properties.length()));
2806     if (!types)
2807         return;
2808
2809     for (size_t i = 0; i < properties.length(); i++) {
2810         ids[i] = properties[i].id;
2811         types[i] = GetValueTypeForTable(obj->getSlot(i));
2812         if (!objType->unknownProperties())
2813             objType->addPropertyType(cx, IdToTypeId(ids[i]), types[i]);
2814     }
2815
2816     ObjectTableKey key;
2817     key.properties = ids;
2818     key.nproperties = properties.length();
2819     key.nfixed = obj->numFixedSlots();
2820     JS_ASSERT(ObjectTableKey::match(key, lookup));
2821
2822     ObjectTableEntry entry;
2823     entry.object.set(objType);
2824     entry.shape.set(obj->lastProperty());
2825     entry.types = types;
2826
2827     obj->setType(objType);
2828
2829     p = objectTypeTable->lookupForAdd(lookup);
2830     if (objectTypeTable->add(p, key, entry)) {
2831         ids.forget();
2832         types.forget();
2833     }
2834 }
2835
2836 JSObject*
2837 TypeCompartment::newTypedObject(JSContext* cx, IdValuePair* properties, size_t nproperties)
2838 {
2839     AutoEnterAnalysis enter(cx);
2840
2841     if (!objectTypeTable) {
2842         objectTypeTable = cx->new_<ObjectTypeTable>();
2843         if (!objectTypeTable || !objectTypeTable->init()) {
2844             js_delete(objectTypeTable);
2845             objectTypeTable = nullptr;
2846             return nullptr;
2847         }
2848     }
2849
2850     /*
2851      * Use the object type table to allocate an object with the specified
2852      * properties, filling in its final type and shape and failing if no cache
2853      * entry could be found for the properties.
2854      */
2855
2856     /*
2857      * Filter out a few cases where we don't want to use the object type table.
2858      * Note that if the properties contain any duplicates or dense indexes,
2859      * the lookup below will fail as such arrays of properties cannot be stored
2860      * in the object type table --- fixObjectType populates the table with
2861      * properties read off its input object, which cannot be duplicates, and
2862      * ignores objects with dense indexes.
2863      */
2864     if (!nproperties || nproperties >= PropertyTree::MAX_HEIGHT)
2865         return nullptr;
2866
2867     gc::AllocKind allocKind = gc::GetGCObjectKind(nproperties);
2868     size_t nfixed = gc::GetGCKindSlots(allocKind, &JSObject::class_);
2869
2870     ObjectTableKey::Lookup lookup(properties, nproperties, nfixed);
2871     ObjectTypeTable::AddPtr p = objectTypeTable->lookupForAdd(lookup);
2872
2873     if (!p)
2874         return nullptr;
2875
2876     RootedObject obj(cx, NewBuiltinClassInstance(cx, &JSObject::class_, allocKind));
2877     if (!obj) {
2878         cx->clearPendingException();
2879         return nullptr;
2880     }
2881     JS_ASSERT(obj->getProto() == p->value().object->proto().toObject());
2882
2883     RootedShape shape(cx, p->value().shape);
2884     if (!JSObject::setLastProperty(cx, obj, shape)) {
2885         cx->clearPendingException();
2886         return nullptr;
2887     }
2888
2889     UpdateObjectTableEntryTypes(cx, p->value(), properties, nproperties);
2890
2891     for (size_t i = 0; i < nproperties; i++)
2892         obj->setSlot(i, properties[i].value);
2893
2894     obj->setType(p->value().object);
2895     return obj;
2896 }
2897
2898 /////////////////////////////////////////////////////////////////////
2899 // TypeObject
2900 /////////////////////////////////////////////////////////////////////
2901
2902 void
2903 TypeObject::setProto(JSContext* cx, TaggedProto proto)
2904 {
2905     JS_ASSERT(singleton());
2906
2907     if (proto.isObject() && IsInsideNursery(proto.toObject()))
2908         addFlags(OBJECT_FLAG_NURSERY_PROTO);
2909
2910     setProtoUnchecked(proto);
2911 }
2912
2913 static inline void
2914 UpdatePropertyType(ExclusiveContext* cx, HeapTypeSet* types, JSObject* obj, Shape* shape,
2915                    bool indexed)
2916 {
2917     JS_ASSERT(obj->hasSingletonType() && !obj->hasLazyType());
2918
2919     if (!shape->writable())
2920         types->setNonWritableProperty(cx);
2921
2922     if (shape->hasGetterValue() || shape->hasSetterValue()) {
2923         types->setNonDataProperty(cx);
2924         types->TypeSet::addType(Type::UnknownType(), &cx->typeLifoAlloc());
2925     } else if (shape->hasDefaultGetter() && shape->hasSlot()) {
2926         if (!indexed && types->canSetDefinite(shape->slot()))
2927             types->setDefinite(shape->slot());
2928
2929         const Value& value = obj->nativeGetSlot(shape->slot());
2930
2931         /*
2932          * Don't add initial undefined types for properties of global objects
2933          * that are not collated into the JSID_VOID property (see propertySet
2934          * comment).
2935          */
2936         if (indexed || !value.isUndefined() || !CanHaveEmptyPropertyTypesForOwnProperty(obj)) {
2937             Type type = GetValueType(value);
2938             types->TypeSet::addType(type, &cx->typeLifoAlloc());
2939         }
2940
2941         if (indexed || shape->hadOverwrite()) {
2942             types->setNonConstantProperty(cx);
2943         } else {
2944             InferSpew(ISpewOps, "typeSet: %sT%p%s property %s %s - setConstant",
2945                       InferSpewColor(types), types, InferSpewColorReset(),
2946                       TypeObjectString(obj->type()), TypeIdString(shape->propid()));
2947         }
2948     }
2949 }
2950
2951 void
2952 TypeObject::updateNewPropertyTypes(ExclusiveContext* cx, jsid id, HeapTypeSet* types)
2953 {
2954     InferSpew(ISpewOps, "typeSet: %sT%p%s property %s %s",
2955               InferSpewColor(types), types, InferSpewColorReset(),
2956               TypeObjectString(this), TypeIdString(id));
2957
2958     if (!singleton() || !singleton()->isNative()) {
2959         types->setNonConstantProperty(cx);
2960         return;
2961     }
2962
2963     /*
2964      * Fill the property in with any type the object already has in an own
2965      * property. We are only interested in plain native properties and
2966      * dense elements which don't go through a barrier when read by the VM
2967      * or jitcode.
2968      */
2969
2970     if (JSID_IS_VOID(id)) {
2971         /* Go through all shapes on the object to get integer-valued properties. */
2972         RootedShape shape(cx, singleton()->lastProperty());
2973         while (!shape->isEmptyShape()) {
2974             if (JSID_IS_VOID(IdToTypeId(shape->propid())))
2975                 UpdatePropertyType(cx, types, singleton(), shape, true);
2976             shape = shape->previous();
2977         }
2978
2979         /* Also get values of any dense elements in the object. */
2980         for (size_t i = 0; i < singleton()->getDenseInitializedLength(); i++) {
2981             const Value& value = singleton()->getDenseElement(i);
2982             if (!value.isMagic(JS_ELEMENTS_HOLE)) {
2983                 Type type = GetValueType(value);
2984                 types->TypeSet::addType(type, &cx->typeLifoAlloc());
2985             }
2986         }
2987     } else if (!JSID_IS_EMPTY(id)) {
2988         RootedId rootedId(cx, id);
2989         Shape* shape = singleton()->nativeLookup(cx, rootedId);
2990         if (shape)
2991             UpdatePropertyType(cx, types, singleton(), shape, false);
2992     }
2993
2994     if (singleton()->watched()) {
2995         /*
2996          * Mark the property as non-data, to inhibit optimizations on it
2997          * and avoid bypassing the watchpoint handler.
2998          */
2999         types->setNonDataProperty(cx);
3000     }
3001 }
3002
3003 bool
3004 TypeObject::addDefiniteProperties(ExclusiveContext* cx, JSObject* obj)
3005 {
3006     if (unknownProperties())
3007         return true;
3008
3009     /* Mark all properties of obj as definite properties of this type. */
3010     AutoEnterAnalysis enter(cx);
3011
3012     RootedShape shape(cx, obj->lastProperty());
3013     while (!shape->isEmptyShape()) {
3014         jsid id = IdToTypeId(shape->propid());
3015         if (!JSID_IS_VOID(id) && obj->isFixedSlot(shape->slot())) {
3016             TypeSet* types = getProperty(cx, id);
3017             if (!types)
3018                 return false;
3019             types->setDefinite(shape->slot());
3020         }
3021         shape = shape->previous();
3022     }
3023
3024     return true;
3025 }
3026
3027 bool
3028 TypeObject::matchDefiniteProperties(HandleObject obj)
3029 {
3030     unsigned count = getPropertyCount();
3031     for (unsigned i = 0; i < count; i++) {
3032         Property* prop = getProperty(i);
3033         if (!prop)
3034             continue;
3035         if (prop->types.definiteProperty()) {
3036             unsigned slot = prop->types.definiteSlot();
3037
3038             bool found = false;
3039             Shape* shape = obj->lastProperty();
3040             while (!shape->isEmptyShape()) {
3041                 if (shape->slot() == slot && shape->propid() == prop->id) {
3042                     found = true;
3043                     break;
3044                 }
3045                 shape = shape->previous();
3046             }
3047             if (!found)
3048                 return false;
3049         }
3050     }
3051
3052     return true;
3053 }
3054
3055 static inline void
3056 InlineAddTypeProperty(ExclusiveContext* cx, TypeObject* obj, jsid id, Type type)
3057 {
3058     JS_ASSERT(id == IdToTypeId(id));
3059
3060     AutoEnterAnalysis enter(cx);
3061
3062     HeapTypeSet* types = obj->getProperty(cx, id);
3063     if (!types)
3064         return;
3065
3066     // Clear any constant flag if it exists.
3067     if (!types->nonConstantProperty()) {
3068         InferSpew(ISpewOps, "constantMutated: %sT%p%s %s",
3069                   InferSpewColor(types), types, InferSpewColorReset(), TypeString(type));
3070         types->setNonConstantProperty(cx);
3071     }
3072
3073     if (types->hasType(type))
3074         return;
3075
3076     InferSpew(ISpewOps, "externalType: property %s %s: %s",
3077               TypeObjectString(obj), TypeIdString(id), TypeString(type));
3078     types->addType(cx, type);
3079 }
3080
3081 void
3082 TypeObject::addPropertyType(ExclusiveContext* cx, jsid id, Type type)
3083 {
3084     InlineAddTypeProperty(cx, this, id, type);
3085 }
3086
3087 void
3088 TypeObject::addPropertyType(ExclusiveContext* cx, jsid id, const Value& value)
3089 {
3090     InlineAddTypeProperty(cx, this, id, GetValueType(value));
3091 }
3092
3093 void
3094 TypeObject::markPropertyNonData(ExclusiveContext* cx, jsid id)
3095 {
3096     AutoEnterAnalysis enter(cx);
3097
3098     id = IdToTypeId(id);
3099
3100     HeapTypeSet* types = getProperty(cx, id);
3101     if (types)
3102         types->setNonDataProperty(cx);
3103 }
3104
3105 void
3106 TypeObject::markPropertyNonWritable(ExclusiveContext* cx, jsid id)
3107 {
3108     AutoEnterAnalysis enter(cx);
3109
3110     id = IdToTypeId(id);
3111
3112     HeapTypeSet* types = getProperty(cx, id);
3113     if (types)
3114         types->setNonWritableProperty(cx);
3115 }
3116
3117 bool
3118 TypeObject::isPropertyNonData(jsid id)
3119 {
3120     TypeSet* types = maybeGetProperty(id);
3121     if (types)
3122         return types->nonDataProperty();
3123     return false;
3124 }
3125
3126 bool
3127 TypeObject::isPropertyNonWritable(jsid id)
3128 {
3129     TypeSet* types = maybeGetProperty(id);
3130     if (types)
3131         return types->nonWritableProperty();
3132     return false;
3133 }
3134
3135 void
3136 TypeObject::markStateChange(ExclusiveContext* cxArg)
3137 {
3138     if (unknownProperties())
3139         return;
3140
3141     AutoEnterAnalysis enter(cxArg);
3142     HeapTypeSet* types = maybeGetProperty(JSID_EMPTY);
3143     if (types) {
3144         if (JSContext* cx = cxArg->maybeJSContext()) {
3145             TypeConstraint* constraint = types->constraintList;
3146             while (constraint) {
3147                 constraint->newObjectState(cx, this);
3148                 constraint = constraint->next;
3149             }
3150         } else {
3151             JS_ASSERT(!types->constraintList);
3152         }
3153     }
3154 }
3155
3156 void
3157 TypeObject::setFlags(ExclusiveContext* cx, TypeObjectFlags flags)
3158 {
3159     if (hasAllFlags(flags))
3160         return;
3161
3162     AutoEnterAnalysis enter(cx);
3163
3164     if (singleton()) {
3165         /* Make sure flags are consistent with persistent object state. */
3166         JS_ASSERT_IF(flags & OBJECT_FLAG_ITERATED,
3167                      singleton()->lastProperty()->hasObjectFlag(BaseShape::ITERATED_SINGLETON));
3168     }
3169
3170     addFlags(flags);
3171
3172     InferSpew(ISpewOps, "%s: setFlags 0x%x", TypeObjectString(this), flags);
3173
3174     ObjectStateChange(cx, this, false);
3175 }
3176
3177 void
3178 TypeObject::markUnknown(ExclusiveContext* cx)
3179 {
3180     AutoEnterAnalysis enter(cx);
3181
3182     JS_ASSERT(cx->compartment()->activeAnalysis);
3183     JS_ASSERT(!unknownProperties());
3184
3185     InferSpew(ISpewOps, "UnknownProperties: %s", TypeObjectString(this));
3186
3187     clearNewScript(cx);
3188     ObjectStateChange(cx, this, true);
3189
3190     /*
3191      * Existing constraints may have already been added to this object, which we need
3192      * to do the right thing for. We can't ensure that we will mark all unknown
3193      * objects before they have been accessed, as the __proto__ of a known object
3194      * could be dynamically set to an unknown object, and we can decide to ignore
3195      * properties of an object during analysis (i.e. hashmaps). Adding unknown for
3196      * any properties accessed already accounts for possible values read from them.
3197      */
3198
3199     unsigned count = getPropertyCount();
3200     for (unsigned i = 0; i < count; i++) {
3201         Property* prop = getProperty(i);
3202         if (prop) {
3203             prop->types.addType(cx, Type::UnknownType());
3204             prop->types.setNonDataProperty(cx);
3205         }
3206     }
3207 }
3208
3209 void
3210 TypeObject::maybeClearNewScriptOnOOM()
3211 {
3212     if (!isMarked())
3213         return;
3214
3215     if (!newScript_)
3216         return;
3217
3218     for (unsigned i = 0; i < getPropertyCount(); i++) {
3219         Property* prop = getProperty(i);
3220         if (!prop)
3221             continue;
3222         if (prop->types.definiteProperty())
3223             prop->types.setNonDataPropertyIgnoringConstraints();
3224     }
3225
3226     // This method is called during GC sweeping, so there is no write barrier
3227     // that needs to be triggered.
3228     js_free(newScript_);
3229     newScript_.unsafeSet(nullptr);
3230 }
3231
3232 void
3233 TypeObject::clearNewScript(ExclusiveContext* cx)
3234 {
3235     if (!newScript_)
3236         return;
3237
3238     TypeNewScript* newScript = newScript_;
3239     newScript_ = nullptr;
3240
3241     AutoEnterAnalysis enter(cx);
3242
3243     /*
3244      * Any definite properties we added due to analysis of the new script when
3245      * the type object was created are now invalid: objects with the same type
3246      * can be created by using 'new' on a different script or through some
3247      * other mechanism (e.g. Object.create). Rather than clear out the definite
3248      * bits on the object's properties, just mark such properties as having
3249      * been deleted/reconfigured, which will have the same effect on JITs
3250      * wanting to use the definite bits to optimize property accesses.
3251      */
3252     for (unsigned i = 0; i < getPropertyCount(); i++) {
3253         Property* prop = getProperty(i);
3254         if (!prop)
3255             continue;
3256         if (prop->types.definiteProperty())
3257             prop->types.setNonDataProperty(cx);
3258     }
3259
3260     /*
3261      * If we cleared the new script while in the middle of initializing an
3262      * object, it will still have the new script's shape and reflect the no
3263      * longer correct state of the object once its initialization is completed.
3264      * We can't detect the possibility of this statically while remaining
3265      * robust, but the new script keeps track of where each property is
3266      * initialized so we can walk the stack and fix up any such objects.
3267      */
3268     if (cx->isJSContext()) {
3269         Vector<uint32_t, 32> pcOffsets(cx);
3270         for (ScriptFrameIter iter(cx->asJSContext()); !iter.done(); ++iter) {
3271             pcOffsets.append(iter.script()->pcToOffset(iter.pc()));
3272             if (!iter.isConstructing() ||
3273                 iter.callee() != newScript->fun ||
3274                 !iter.thisv().isObject() ||
3275                 iter.thisv().toObject().hasLazyType() ||
3276                 iter.thisv().toObject().type() != this)
3277             {
3278                 continue;
3279             }
3280
3281             // Found a matching frame.
3282             RootedObject obj(cx, &iter.thisv().toObject());
3283
3284             // Whether all identified 'new' properties have been initialized.
3285             bool finished = false;
3286
3287             // If not finished, number of properties that have been added.
3288             uint32_t numProperties = 0;
3289
3290             // Whether the current SETPROP is within an inner frame which has
3291             // finished entirely.
3292             bool pastProperty = false;
3293
3294             // Index in pcOffsets of the outermost frame.
3295             int callDepth = pcOffsets.length() - 1;
3296
3297             // Index in pcOffsets of the frame currently being checked for a SETPROP.
3298             int setpropDepth = callDepth;
3299
3300             for (TypeNewScript::Initializer* init = newScript->initializerList;; init++) {
3301                 if (init->kind == TypeNewScript::Initializer::SETPROP) {
3302                     if (!pastProperty && pcOffsets[setpropDepth] < init->offset) {
3303                         // Have not yet reached this setprop.
3304                         break;
3305                     }
3306                     // This setprop has executed, reset state for the next one.
3307                     numProperties++;
3308                     pastProperty = false;
3309                     setpropDepth = callDepth;
3310                 } else if (init->kind == TypeNewScript::Initializer::SETPROP_FRAME) {
3311                     if (!pastProperty) {
3312                         if (pcOffsets[setpropDepth] < init->offset) {
3313                             // Have not yet reached this inner call.
3314                             break;
3315                         } else if (pcOffsets[setpropDepth] > init->offset) {
3316                             // Have advanced past this inner call.
3317                             pastProperty = true;
3318                         } else if (setpropDepth == 0) {
3319                             // Have reached this call but not yet in it.
3320                             break;
3321                         } else {
3322                             // Somewhere inside this inner call.
3323                             setpropDepth--;
3324                         }
3325                     }
3326                 } else {
3327                     JS_ASSERT(init->kind == TypeNewScript::Initializer::DONE);
3328                     finished = true;
3329                     break;
3330                 }
3331             }
3332
3333             if (!finished)
3334                 (void) JSObject::rollbackProperties(cx, obj, numProperties);
3335         }
3336     } else {
3337         // Threads with an ExclusiveContext are not allowed to run scripts.
3338         JS_ASSERT(!cx->perThreadData->activation());
3339     }
3340
3341     js_free(newScript);
3342     markStateChange(cx);
3343 }
3344
3345 void
3346 TypeObject::print()
3347 {
3348     TaggedProto tagged(proto());
3349     fprintf(stderr, "%s : %s",
3350             TypeObjectString(this),
3351             tagged.isObject() ? TypeString(Type::ObjectType(tagged.toObject()))
3352                               : (tagged.isLazy() ? "(lazy)" : "(null)"));
3353
3354     if (unknownProperties()) {
3355         fprintf(stderr, " unknown");
3356     } else {
3357         if (!hasAnyFlags(OBJECT_FLAG_SPARSE_INDEXES))
3358             fprintf(stderr, " dense");
3359         if (!hasAnyFlags(OBJECT_FLAG_NON_PACKED))
3360             fprintf(stderr, " packed");
3361         if (!hasAnyFlags(OBJECT_FLAG_LENGTH_OVERFLOW))
3362             fprintf(stderr, " noLengthOverflow");
3363         if (hasAnyFlags(OBJECT_FLAG_ITERATED))
3364             fprintf(stderr, " iterated");
3365         if (interpretedFunction)
3366             fprintf(stderr, " ifun");
3367     }
3368
3369     unsigned count = getPropertyCount();
3370
3371     if (count == 0) {
3372         fprintf(stderr, " {}\n");
3373         return;
3374     }
3375
3376     fprintf(stderr, " {");
3377
3378     for (unsigned i = 0; i < count; i++) {
3379         Property* prop = getProperty(i);
3380         if (prop) {
3381             fprintf(stderr, "\n    %s:", TypeIdString(prop->id));
3382             prop->types.print();
3383         }
3384     }
3385
3386     fprintf(stderr, "\n}\n");
3387 }
3388
3389 /////////////////////////////////////////////////////////////////////
3390 // Type Analysis
3391 /////////////////////////////////////////////////////////////////////
3392
3393 /*
3394  * Persistent constraint clearing out newScript and definite properties from
3395  * an object should a property on another object get a getter or setter.
3396  */
3397 class TypeConstraintClearDefiniteGetterSetter : public TypeConstraint
3398 {
3399   public:
3400     TypeObject* object;
3401
3402     explicit TypeConstraintClearDefiniteGetterSetter(TypeObject* object)
3403         : object(object)
3404     {}
3405
3406     const char* kind() { return "clearDefiniteGetterSetter"; }
3407
3408     void newPropertyState(JSContext* cx, TypeSet* source) {
3409         /*
3410          * Clear out the newScript shape and definite property information from
3411          * an object if the source type set could be a setter or could be
3412          * non-writable.
3413          */
3414         if (source->nonDataProperty() || source->nonWritableProperty())
3415             object->clearNewScript(cx);
3416     }
3417
3418     void newType(JSContext* cx, TypeSet* source, Type type) {}
3419
3420     bool sweep(TypeZone& zone, TypeConstraint** res) {
3421         if (IsTypeObjectAboutToBeFinalized(&object))
3422             return false;
3423         *res = zone.typeLifoAlloc.new_<TypeConstraintClearDefiniteGetterSetter>(object);
3424         return true;
3425     }
3426 };
3427
3428 bool
3429 types::AddClearDefiniteGetterSetterForPrototypeChain(JSContext* cx, TypeObject* type, HandleId id)
3430 {
3431     /*
3432      * Ensure that if the properties named here could have a getter, setter or
3433      * a permanent property in any transitive prototype, the definite
3434      * properties get cleared from the type.
3435      */
3436     RootedObject parent(cx, type->proto().toObjectOrNull());
3437     while (parent) {
3438         TypeObject* parentObject = parent->getType(cx);
3439         if (!parentObject || parentObject->unknownProperties())
3440             return false;
3441         HeapTypeSet* parentTypes = parentObject->getProperty(cx, id);
3442         if (!parentTypes || parentTypes->nonDataProperty() || parentTypes->nonWritableProperty())
3443             return false;
3444         if (!parentTypes->addConstraint(cx, cx->typeLifoAlloc().new_<TypeConstraintClearDefiniteGetterSetter>(type)))
3445             return false;
3446         parent = parent->getProto();
3447     }
3448     return true;
3449 }
3450
3451 /*
3452  * Constraint which clears definite properties on an object should a type set
3453  * contain any types other than a single object.
3454  */
3455 class TypeConstraintClearDefiniteSingle : public TypeConstraint
3456 {
3457   public:
3458     TypeObject* object;
3459
3460     explicit TypeConstraintClearDefiniteSingle(TypeObject* object)
3461         : object(object)
3462     {}
3463
3464     const char* kind() { return "clearDefiniteSingle"; }
3465
3466     void newType(JSContext* cx, TypeSet* source, Type type) {
3467         if (source->baseFlags() || source->getObjectCount() > 1)
3468             object->clearNewScript(cx);
3469     }
3470
3471     bool sweep(TypeZone& zone, TypeConstraint** res) {
3472         if (IsTypeObjectAboutToBeFinalized(&object))
3473             return false;
3474         *res = zone.typeLifoAlloc.new_<TypeConstraintClearDefiniteSingle>(object);
3475         return true;
3476     }
3477 };
3478
3479 bool
3480 types::AddClearDefiniteFunctionUsesInScript(JSContext* cx, TypeObject* type,
3481                                             JSScript* script, JSScript* calleeScript)
3482 {
3483     // Look for any uses of the specified calleeScript in type sets for
3484     // |script|, and add constraints to ensure that if the type sets' contents
3485     // change then the definite properties are cleared from the type.
3486     // This ensures that the inlining performed when the definite properties
3487     // analysis was done is stable. We only need to look at type sets which
3488     // contain a single object, as IonBuilder does not inline polymorphic sites
3489     // during the definite properties analysis.
3490
3491     TypeObjectKey* calleeKey = Type::ObjectType(calleeScript->functionNonDelazifying()).objectKey();
3492
3493     unsigned count = TypeScript::NumTypeSets(script);
3494     StackTypeSet* typeArray = script->types->typeArray();
3495
3496     for (unsigned i = 0; i < count; i++) {
3497         StackTypeSet* types = &typeArray[i];
3498         if (!types->unknownObject() && types->getObjectCount() == 1) {
3499             if (calleeKey != types->getObject(0)) {
3500                 // Also check if the object is the Function.call or
3501                 // Function.apply native. IonBuilder uses the presence of these
3502                 // functions during inlining.
3503                 JSObject* singleton = types->getSingleObject(0);
3504                 if (!singleton || !singleton->is<JSFunction>())
3505                     continue;
3506                 JSFunction* fun = &singleton->as<JSFunction>();
3507                 if (!fun->isNative())
3508                     continue;
3509                 if (fun->native() != js_fun_call && fun->native() != js_fun_apply)
3510                     continue;
3511             }
3512             // This is a type set that might have been used when inlining
3513             // |calleeScript| into |script|.
3514             if (!types->addConstraint(cx, cx->typeLifoAlloc().new_<TypeConstraintClearDefiniteSingle>(type)))
3515                 return false;
3516         }
3517     }
3518
3519     return true;
3520 }
3521
3522 /*
3523  * Either make the newScript information for type when it is constructed
3524  * by the specified script, or regenerate the constraints for an existing
3525  * newScript on the type after they were cleared by a GC.
3526  */
3527 static void
3528 CheckNewScriptProperties(JSContext* cx, TypeObject* type, JSFunction* fun)
3529 {
3530     JS_ASSERT(cx->compartment()->activeAnalysis);
3531     JS_ASSERT(!type->newScript());
3532
3533     /* Strawman object to add properties to and watch for duplicates. */
3534     RootedObject baseobj(cx, NewBuiltinClassInstance(cx, &JSObject::class_, gc::FINALIZE_OBJECT16));
3535     if (!baseobj)
3536         return;
3537
3538     Vector<TypeNewScript::Initializer> initializerList(cx);
3539
3540     if (!jit::AnalyzeNewScriptProperties(cx, fun, type, baseobj, &initializerList))
3541         return;
3542
3543     if (baseobj->slotSpan() == 0 || type->unknownProperties())
3544         return;
3545
3546     gc::AllocKind kind = gc::GetGCObjectKind(baseobj->slotSpan());
3547
3548     /* We should not have overflowed the maximum number of fixed slots for an object. */
3549     JS_ASSERT(gc::GetGCKindSlots(kind) >= baseobj->slotSpan());
3550
3551     TypeNewScript::Initializer done(TypeNewScript::Initializer::DONE, 0);
3552
3553     /*
3554      * The base object may have been created with a different finalize kind
3555      * than we will use for subsequent new objects. Generate an object with the
3556      * appropriate final shape.
3557      */
3558     Rooted<TypeObject*> rootedType(cx, type);
3559     RootedShape shape(cx, baseobj->lastProperty());
3560     baseobj = NewReshapedObject(cx, rootedType, baseobj->getParent(), kind, shape, MaybeSingletonObject);
3561     if (!baseobj ||
3562         !type->addDefiniteProperties(cx, baseobj) ||
3563         !initializerList.append(done))
3564     {
3565         return;
3566     }
3567
3568     TypeNewScript* newScript = type->pod_calloc_with_extra<TypeNewScript, TypeNewScript::Initializer>(
3569                                    initializerList.length());
3570     if (!newScript)
3571         return;
3572
3573     new (newScript) TypeNewScript();
3574
3575     type->setNewScript(newScript);
3576
3577     newScript->fun = fun;
3578     newScript->templateObject = baseobj;
3579
3580     newScript->initializerList = reinterpret_cast<TypeNewScript::Initializer*>(newScript + 1);
3581     PodCopy(newScript->initializerList,
3582             initializerList.begin(),
3583             initializerList.length());
3584
3585     js::gc::TraceTypeNewScript(type);
3586 }
3587
3588 /////////////////////////////////////////////////////////////////////
3589 // Interface functions
3590 /////////////////////////////////////////////////////////////////////
3591
3592 void
3593 types::TypeMonitorCallSlow(JSContext* cx, JSObject* callee, const CallArgs& args,
3594                            bool constructing)
3595 {
3596     unsigned nargs = callee->as<JSFunction>().nargs();
3597     JSScript* script = callee->as<JSFunction>().nonLazyScript();
3598
3599     if (!constructing)
3600         TypeScript::SetThis(cx, script, args.thisv());
3601
3602     /*
3603      * Add constraints going up to the minimum of the actual and formal count.
3604      * If there are more actuals than formals the later values can only be
3605      * accessed through the arguments object, which is monitored.
3606      */
3607     unsigned arg = 0;
3608     for (; arg < args.length() && arg < nargs; arg++)
3609         TypeScript::SetArgument(cx, script, arg, args[arg]);
3610
3611     /* Watch for fewer actuals than formals to the call. */
3612     for (; arg < nargs; arg++)
3613         TypeScript::SetArgument(cx, script, arg, UndefinedValue());
3614 }
3615
3616 static inline bool
3617 IsAboutToBeFinalized(TypeObjectKey** keyp)
3618 {
3619     /* Mask out the low bit indicating whether this is a type or JS object. */
3620     uintptr_t flagBit = uintptr_t(*keyp) & 1;
3621     gc::Cell* tmp = reinterpret_cast<gc::Cell*>(uintptr_t(*keyp) & ~1);
3622     bool isAboutToBeFinalized = IsCellAboutToBeFinalized(&tmp);
3623     *keyp = reinterpret_cast<TypeObjectKey*>(uintptr_t(tmp) | flagBit);
3624     return isAboutToBeFinalized;
3625 }
3626
3627 void
3628 types::FillBytecodeTypeMap(JSScript* script, uint32_t* bytecodeMap)
3629 {
3630     uint32_t added = 0;
3631     for (jsbytecode* pc = script->code(); pc < script->codeEnd(); pc += GetBytecodeLength(pc)) {
3632         JSOp op = JSOp(*pc);
3633         if (js_CodeSpec[op].format & JOF_TYPESET) {
3634             bytecodeMap[added++] = script->pcToOffset(pc);
3635             if (added == script->nTypeSets())
3636                 break;
3637         }
3638     }
3639     JS_ASSERT(added == script->nTypeSets());
3640 }
3641
3642 JSObject*
3643 types::GetOrFixupCopyOnWriteObject(JSContext* cx, HandleScript script, jsbytecode* pc)
3644 {
3645     // Make sure that the template object for script/pc has a type indicating
3646     // that the object and its copies have copy on write elements.
3647     RootedObject obj(cx, script->getObject(GET_UINT32_INDEX(pc)));
3648     JS_ASSERT(obj->is<ArrayObject>());
3649     JS_ASSERT(obj->denseElementsAreCopyOnWrite());
3650
3651     if (obj->type()->hasAnyFlags(OBJECT_FLAG_COPY_ON_WRITE))
3652         return obj;
3653
3654     RootedTypeObject type(cx, TypeScript::InitObject(cx, script, pc, JSProto_Array));
3655     if (!type)
3656         return nullptr;
3657
3658     type->addFlags(OBJECT_FLAG_COPY_ON_WRITE);
3659
3660     // Update type information in the initializer object type.
3661     JS_ASSERT(obj->slotSpan() == 0);
3662     for (size_t i = 0; i < obj->getDenseInitializedLength(); i++) {
3663         const Value& v = obj->getDenseElement(i);
3664         AddTypePropertyId(cx, type, JSID_VOID, v);
3665     }
3666
3667     obj->setType(type);
3668     return obj;
3669 }
3670
3671 JSObject*
3672 types::GetCopyOnWriteObject(JSScript* script, jsbytecode* pc)
3673 {
3674     // GetOrFixupCopyOnWriteObject should already have been called for
3675     // script/pc, ensuring that the template object has a type with the
3676     // COPY_ON_WRITE flag. We don't assert this here, due to a corner case
3677     // where this property doesn't hold. See jsop_newarray_copyonwrite in
3678     // IonBuilder.
3679     JSObject* obj = script->getObject(GET_UINT32_INDEX(pc));
3680     JS_ASSERT(obj->is<ArrayObject>());
3681     JS_ASSERT(obj->denseElementsAreCopyOnWrite());
3682
3683     return obj;
3684 }
3685
3686 void
3687 types::TypeMonitorResult(JSContext* cx, JSScript* script, jsbytecode* pc, const js::Value& rval)
3688 {
3689     /* Allow the non-TYPESET scenario to simplify stubs used in compound opcodes. */
3690     if (!(js_CodeSpec[*pc].format & JOF_TYPESET))
3691         return;
3692
3693     if (!script->hasBaselineScript())
3694         return;
3695
3696     AutoEnterAnalysis enter(cx);
3697
3698     Type type = GetValueType(rval);
3699     StackTypeSet* types = TypeScript::BytecodeTypes(script, pc);
3700     if (types->hasType(type))
3701         return;
3702
3703     InferSpew(ISpewOps, "bytecodeType: #%u:%05u: %s",
3704               script->id(), script->pcToOffset(pc), TypeString(type));
3705     types->addType(cx, type);
3706 }
3707
3708 bool
3709 types::UseNewTypeForClone(JSFunction* fun)
3710 {
3711     if (!fun->isInterpreted())
3712         return false;
3713
3714     if (fun->hasScript() && fun->nonLazyScript()->shouldCloneAtCallsite())
3715         return true;
3716
3717     if (fun->isArrow())
3718         return false;
3719
3720     if (fun->hasSingletonType())
3721         return false;
3722
3723     /*
3724      * When a function is being used as a wrapper for another function, it
3725      * improves precision greatly to distinguish between different instances of
3726      * the wrapper; otherwise we will conflate much of the information about
3727      * the wrapped functions.
3728      *
3729      * An important example is the Class.create function at the core of the
3730      * Prototype.js library, which looks like:
3731      *
3732      * var Class = {
3733      *   create: function() {
3734      *     return function() {
3735      *       this.initialize.apply(this, arguments);
3736      *     }
3737      *   }
3738      * };
3739      *
3740      * Each instance of the innermost function will have a different wrapped
3741      * initialize method. We capture this, along with similar cases, by looking
3742      * for short scripts which use both .apply and arguments. For such scripts,
3743      * whenever creating a new instance of the function we both give that
3744      * instance a singleton type and clone the underlying script.
3745      */
3746
3747     uint32_t begin, end;
3748     if (fun->hasScript()) {
3749         if (!fun->nonLazyScript()->usesArgumentsAndApply())
3750             return false;
3751         begin = fun->nonLazyScript()->sourceStart();
3752         end = fun->nonLazyScript()->sourceEnd();
3753     } else {
3754         if (!fun->lazyScript()->usesArgumentsAndApply())
3755             return false;
3756         begin = fun->lazyScript()->begin();
3757         end = fun->lazyScript()->end();
3758     }
3759
3760     return end - begin <= 100;
3761 }
3762 /////////////////////////////////////////////////////////////////////
3763 // TypeScript
3764 /////////////////////////////////////////////////////////////////////
3765
3766 bool
3767 JSScript::makeTypes(JSContext* cx)
3768 {
3769     JS_ASSERT(!types);
3770
3771     AutoEnterAnalysis enter(cx);
3772
3773     unsigned count = TypeScript::NumTypeSets(this);
3774
3775     TypeScript* typeScript = (TypeScript*)
3776         pod_calloc<uint8_t>(TypeScript::SizeIncludingTypeArray(count));
3777     if (!typeScript)
3778         return false;
3779
3780     types = typeScript;
3781
3782 #ifdef DEBUG
3783     StackTypeSet* typeArray = typeScript->typeArray();
3784     for (unsigned i = 0; i < nTypeSets(); i++) {
3785         InferSpew(ISpewOps, "typeSet: %sT%p%s bytecode%u #%u",
3786                   InferSpewColor(&typeArray[i]), &typeArray[i], InferSpewColorReset(),
3787                   i, id());
3788     }
3789     TypeSet* thisTypes = TypeScript::ThisTypes(this);
3790     InferSpew(ISpewOps, "typeSet: %sT%p%s this #%u",
3791               InferSpewColor(thisTypes), thisTypes, InferSpewColorReset(),
3792               id());
3793     unsigned nargs = functionNonDelazifying() ? functionNonDelazifying()->nargs() : 0;
3794     for (unsigned i = 0; i < nargs; i++) {
3795         TypeSet* types = TypeScript::ArgTypes(this, i);
3796         InferSpew(ISpewOps, "typeSet: %sT%p%s arg%u #%u",
3797                   InferSpewColor(types), types, InferSpewColorReset(),
3798                   i, id());
3799     }
3800 #endif
3801
3802     return true;
3803 }
3804
3805 /* static */ bool
3806 JSFunction::setTypeForScriptedFunction(ExclusiveContext* cx, HandleFunction fun,
3807                                        bool singleton /* = false */)
3808 {
3809     if (singleton) {
3810         if (!setSingletonType(cx, fun))
3811             return false;
3812     } else {
3813         RootedObject funProto(cx, fun->getProto());
3814         Rooted<TaggedProto> taggedProto(cx, TaggedProto(funProto));
3815         TypeObject* type =
3816             cx->compartment()->types.newTypeObject(cx, &JSFunction::class_, taggedProto);
3817         if (!type)
3818             return false;
3819
3820         fun->setType(type);
3821         type->interpretedFunction = fun;
3822     }
3823
3824     return true;
3825 }
3826
3827 /////////////////////////////////////////////////////////////////////
3828 // JSObject
3829 /////////////////////////////////////////////////////////////////////
3830
3831 bool
3832 JSObject::shouldSplicePrototype(JSContext* cx)
3833 {
3834     /*
3835      * During bootstrapping, if inference is enabled we need to make sure not
3836      * to splice a new prototype in for Function.prototype or the global
3837      * object if their __proto__ had previously been set to null, as this
3838      * will change the prototype for all other objects with the same type.
3839      */
3840     if (getProto() != nullptr)
3841         return false;
3842     return hasSingletonType();
3843 }
3844
3845 bool
3846 JSObject::splicePrototype(JSContext* cx, const Class* clasp, Handle<TaggedProto> proto)
3847 {
3848     JS_ASSERT(cx->compartment() == compartment());
3849
3850     RootedObject self(cx, this);
3851
3852     /*
3853      * For singleton types representing only a single JSObject, the proto
3854      * can be rearranged as needed without destroying type information for
3855      * the old or new types.
3856      */
3857     JS_ASSERT(self->hasSingletonType());
3858
3859     /* Inner objects may not appear on prototype chains. */
3860     JS_ASSERT_IF(proto.isObject(), !proto.toObject()->getClass()->ext.outerObject);
3861
3862     /*
3863      * Force type instantiation when splicing lazy types. This may fail,
3864      * in which case inference will be disabled for the compartment.
3865      */
3866     Rooted<TypeObject*> type(cx, self->getType(cx));
3867     if (!type)
3868         return false;
3869     Rooted<TypeObject*> protoType(cx, nullptr);
3870     if (proto.isObject()) {
3871         protoType = proto.toObject()->getType(cx);
3872         if (!protoType)
3873             return false;
3874     }
3875
3876     type->setClasp(clasp);
3877     type->setProto(cx, proto);
3878     return true;
3879 }
3880
3881 /* static */ TypeObject*
3882 JSObject::makeLazyType(JSContext* cx, HandleObject obj)
3883 {
3884     JS_ASSERT(obj->hasLazyType());
3885     JS_ASSERT(cx->compartment() == obj->compartment());
3886
3887     /* De-lazification of functions can GC, so we need to do it up here. */
3888     if (obj->is<JSFunction>() && obj->as<JSFunction>().isInterpretedLazy()) {
3889         RootedFunction fun(cx, &obj->as<JSFunction>());
3890         if (!fun->getOrCreateScript(cx))
3891             return nullptr;
3892     }
3893
3894     // Find flags which need to be specified immediately on the object.
3895     // Don't track whether singletons are packed.
3896     TypeObjectFlags initialFlags = OBJECT_FLAG_NON_PACKED;
3897
3898     if (obj->lastProperty()->hasObjectFlag(BaseShape::ITERATED_SINGLETON))
3899         initialFlags |= OBJECT_FLAG_ITERATED;
3900
3901     if (obj->isIndexed())
3902         initialFlags |= OBJECT_FLAG_SPARSE_INDEXES;
3903
3904     if (obj->is<ArrayObject>() && obj->as<ArrayObject>().length() > INT32_MAX)
3905         initialFlags |= OBJECT_FLAG_LENGTH_OVERFLOW;
3906
3907     Rooted<TaggedProto> proto(cx, obj->getTaggedProto());
3908     TypeObject* type = cx->compartment()->types.newTypeObject(cx, obj->getClass(), proto, initialFlags);
3909     if (!type)
3910         return nullptr;
3911
3912     AutoEnterAnalysis enter(cx);
3913
3914     /* Fill in the type according to the state of this object. */
3915
3916     type->initSingleton(obj);
3917
3918     if (obj->is<JSFunction>() && obj->as<JSFunction>().isInterpreted())
3919         type->interpretedFunction = &obj->as<JSFunction>();
3920
3921     obj->type_ = type;
3922
3923     return type;
3924 }
3925
3926 /* static */ inline HashNumber
3927 TypeObjectWithNewScriptEntry::hash(const Lookup& lookup)
3928 {
3929     return PointerHasher<JSObject*, 3>::hash(lookup.hashProto.raw()) ^
3930            PointerHasher<const Class*, 3>::hash(lookup.clasp) ^
3931            PointerHasher<JSFunction*, 3>::hash(lookup.newFunction);
3932 }
3933
3934 /* static */ inline bool
3935 TypeObjectWithNewScriptEntry::match(const TypeObjectWithNewScriptEntry& key, const Lookup& lookup)
3936 {
3937     return key.object->proto() == lookup.matchProto &&
3938            key.object->clasp() == lookup.clasp &&
3939            key.newFunction == lookup.newFunction;
3940 }
3941
3942 #ifdef DEBUG
3943 bool
3944 JSObject::hasNewType(const Class* clasp, TypeObject* type)
3945 {
3946     TypeObjectWithNewScriptSet& table = compartment()->newTypeObjects;
3947
3948     if (!table.initialized())
3949         return false;
3950
3951     TypeObjectWithNewScriptSet::Ptr p = table.lookup(TypeObjectWithNewScriptSet::Lookup(clasp, TaggedProto(this), nullptr));
3952     return p && p->object == type;
3953 }
3954 #endif /* DEBUG */
3955
3956 /* static */ bool
3957 JSObject::setNewTypeUnknown(JSContext* cx, const Class* clasp, HandleObject obj)
3958 {
3959     if (!obj->setFlag(cx, js::BaseShape::NEW_TYPE_UNKNOWN))
3960         return false;
3961
3962     /*
3963      * If the object already has a new type, mark that type as unknown. It will
3964      * not have the SETS_MARKED_UNKNOWN bit set, so may require a type set
3965      * crawl if prototypes of the object change dynamically in the future.
3966      */
3967     TypeObjectWithNewScriptSet& table = cx->compartment()->newTypeObjects;
3968     if (table.initialized()) {
3969         Rooted<TaggedProto> taggedProto(cx, TaggedProto(obj));
3970         if (TypeObjectWithNewScriptSet::Ptr p = table.lookup(TypeObjectWithNewScriptSet::Lookup(clasp, taggedProto, nullptr)))
3971             MarkTypeObjectUnknownProperties(cx, p->object);
3972     }
3973
3974     return true;
3975 }
3976
3977 #ifdef JSGC_GENERATIONAL
3978 /*
3979  * This class is used to add a post barrier on the newTypeObjects set, as the
3980  * key is calculated from a prototype object which may be moved by generational
3981  * GC.
3982  */
3983 class NewTypeObjectsSetRef : public BufferableRef
3984 {
3985     TypeObjectWithNewScriptSet* set;
3986     const Class* clasp;
3987     JSObject* proto;
3988     JSFunction* newFunction;
3989
3990   public:
3991     NewTypeObjectsSetRef(TypeObjectWithNewScriptSet* s, const Class* clasp, JSObject* proto, JSFunction* newFunction)
3992         : set(s), clasp(clasp), proto(proto), newFunction(newFunction)
3993     {}
3994
3995     void mark(JSTracer* trc) {
3996         JSObject* prior = proto;
3997         trc->setTracingLocation(&*prior);
3998         Mark(trc, &proto, "newTypeObjects set prototype");
3999         if (prior == proto)
4000             return;
4001
4002         TypeObjectWithNewScriptSet::Ptr p = set->lookup(TypeObjectWithNewScriptSet::Lookup(clasp, TaggedProto(prior), TaggedProto(proto), newFunction));
4003         JS_ASSERT(p);  // newTypeObjects set must still contain original entry.
4004
4005         set->rekeyAs(TypeObjectWithNewScriptSet::Lookup(clasp, TaggedProto(prior), TaggedProto(proto), newFunction),
4006                      TypeObjectWithNewScriptSet::Lookup(clasp, TaggedProto(proto), newFunction), *p);
4007     }
4008 };
4009
4010 static void
4011 TypeObjectTablePostBarrier(ExclusiveContext* cx, TypeObjectWithNewScriptSet* table,
4012                            const Class* clasp, TaggedProto proto, JSFunction* fun)
4013 {
4014     JS_ASSERT_IF(fun, !IsInsideNursery(fun));
4015
4016     if (!proto.isObject())
4017         return;
4018
4019     if (!cx->isJSContext()) {
4020         JS_ASSERT(!IsInsideNursery(proto.toObject()));
4021         return;
4022     }
4023
4024     if (IsInsideNursery(proto.toObject())) {
4025         StoreBuffer& sb = cx->asJSContext()->runtime()->gc.storeBuffer;
4026         sb.putGeneric(NewTypeObjectsSetRef(table, clasp, proto.toObject(), fun));
4027     }
4028 }
4029 #endif
4030
4031 TypeObject*
4032 ExclusiveContext::getNewType(const Class* clasp, TaggedProto proto, JSFunction* fun)
4033 {
4034     JS_ASSERT_IF(fun, proto.isObject());
4035     JS_ASSERT_IF(proto.isObject(), isInsideCurrentCompartment(proto.toObject()));
4036
4037     TypeObjectWithNewScriptSet& newTypeObjects = compartment()->newTypeObjects;
4038
4039     if (!newTypeObjects.initialized() && !newTypeObjects.init())
4040         return nullptr;
4041
4042     // Canonicalize new functions to use the original one associated with its script.
4043     if (fun) {
4044         if (fun->hasScript())
4045             fun = fun->nonLazyScript()->functionNonDelazifying();
4046         else if (fun->isInterpretedLazy() && !fun->isSelfHostedBuiltin())
4047             fun = fun->lazyScript()->functionNonDelazifying();
4048         else
4049             fun = nullptr;
4050     }
4051
4052     TypeObjectWithNewScriptSet::AddPtr p =
4053         newTypeObjects.lookupForAdd(TypeObjectWithNewScriptSet::Lookup(clasp, proto, fun));
4054     if (p) {
4055         TypeObject* type = p->object;
4056         JS_ASSERT(type->clasp() == clasp);
4057         JS_ASSERT(type->proto() == proto);
4058         JS_ASSERT_IF(type->newScript(), type->newScript()->fun == fun);
4059         return type;
4060     }
4061
4062     AutoEnterAnalysis enter(this);
4063
4064     if (proto.isObject() && !proto.toObject()->setDelegate(this))
4065         return nullptr;
4066
4067     TypeObjectFlags initialFlags = 0;
4068     if (!proto.isObject() || proto.toObject()->lastProperty()->hasObjectFlag(BaseShape::NEW_TYPE_UNKNOWN)) {
4069         // The new type is not present in any type sets, so mark the object as
4070         // unknown in all type sets it appears in. This allows the prototype of
4071         // such objects to mutate freely without triggering an expensive walk of
4072         // the compartment's type sets. (While scripts normally don't mutate
4073         // __proto__, the browser will for proxies and such, and we need to
4074         // accommodate this behavior).
4075         initialFlags = OBJECT_FLAG_UNKNOWN_MASK | OBJECT_FLAG_SETS_MARKED_UNKNOWN;
4076     }
4077
4078     Rooted<TaggedProto> protoRoot(this, proto);
4079     TypeObject* type = compartment()->types.newTypeObject(this, clasp, protoRoot, initialFlags);
4080     if (!type)
4081         return nullptr;
4082
4083     if (!newTypeObjects.add(p, TypeObjectWithNewScriptEntry(type, fun)))
4084         return nullptr;
4085
4086 #ifdef JSGC_GENERATIONAL
4087     TypeObjectTablePostBarrier(this, &newTypeObjects, clasp, proto, fun);
4088 #endif
4089
4090     if (proto.isObject()) {
4091         RootedObject obj(this, proto.toObject());
4092
4093         if (fun)
4094             CheckNewScriptProperties(asJSContext(), type, fun);
4095
4096         /*
4097          * Some builtin objects have slotful native properties baked in at
4098          * creation via the Shape::{insert,get}initialShape mechanism. Since
4099          * these properties are never explicitly defined on new objects, update
4100          * the type information for them here.
4101          */
4102
4103         if (obj->is<RegExpObject>()) {
4104             AddTypePropertyId(this, type, NameToId(names().source), Type::StringType());
4105             AddTypePropertyId(this, type, NameToId(names().global), Type::BooleanType());
4106             AddTypePropertyId(this, type, NameToId(names().ignoreCase), Type::BooleanType());
4107             AddTypePropertyId(this, type, NameToId(names().multiline), Type::BooleanType());
4108             AddTypePropertyId(this, type, NameToId(names().sticky), Type::BooleanType());
4109             AddTypePropertyId(this, type, NameToId(names().lastIndex), Type::Int32Type());
4110         }
4111
4112         if (obj->is<StringObject>())
4113             AddTypePropertyId(this, type, NameToId(names().length), Type::Int32Type());
4114
4115         if (obj->is<ErrorObject>()) {
4116             AddTypePropertyId(this, type, NameToId(names().fileName), Type::StringType());
4117             AddTypePropertyId(this, type, NameToId(names().lineNumber), Type::Int32Type());
4118             AddTypePropertyId(this, type, NameToId(names().columnNumber), Type::Int32Type());
4119             AddTypePropertyId(this, type, NameToId(names().stack), Type::StringType());
4120         }
4121     }
4122
4123     return type;
4124 }
4125
4126 TypeObject*
4127 ExclusiveContext::getSingletonType(const Class* clasp, TaggedProto proto)
4128 {
4129     JS_ASSERT_IF(proto.isObject(), compartment() == proto.toObject()->compartment());
4130
4131     AutoEnterAnalysis enter(this);
4132
4133     TypeObjectWithNewScriptSet& table = compartment()->lazyTypeObjects;
4134
4135     if (!table.initialized() && !table.init())
4136         return nullptr;
4137
4138     TypeObjectWithNewScriptSet::AddPtr p = table.lookupForAdd(TypeObjectWithNewScriptSet::Lookup(clasp, proto, nullptr));
4139     if (p) {
4140         TypeObject* type = p->object;
4141         JS_ASSERT(type->lazy());
4142
4143         return type;
4144     }
4145
4146     Rooted<TaggedProto> protoRoot(this, proto);
4147     TypeObject* type = compartment()->types.newTypeObject(this, clasp, protoRoot);
4148     if (!type)
4149         return nullptr;
4150
4151     if (!table.add(p, TypeObjectWithNewScriptEntry(type, nullptr)))
4152         return nullptr;
4153
4154 #ifdef JSGC_GENERATIONAL
4155     TypeObjectTablePostBarrier(this, &table, clasp, proto, nullptr);
4156 #endif
4157
4158     type->initSingleton((JSObject*) TypeObject::LAZY_SINGLETON);
4159     MOZ_ASSERT(type->singleton(), "created type must be a proper singleton");
4160
4161     return type;
4162 }
4163
4164 /////////////////////////////////////////////////////////////////////
4165 // Tracing
4166 /////////////////////////////////////////////////////////////////////
4167
4168 void
4169 ConstraintTypeSet::sweep(Zone* zone, bool* oom)
4170 {
4171     /*
4172      * Purge references to type objects that are no longer live. Type sets hold
4173      * only weak references. For type sets containing more than one object,
4174      * live entries in the object hash need to be copied to the zone's
4175      * new arena.
4176      */
4177     unsigned objectCount = baseObjectCount();
4178     if (objectCount >= 2) {
4179         unsigned oldCapacity = HashSetCapacity(objectCount);
4180         TypeObjectKey** oldArray = objectSet;
4181
4182         clearObjects();
4183         objectCount = 0;
4184         for (unsigned i = 0; i < oldCapacity; i++) {
4185             TypeObjectKey* object = oldArray[i];
4186             if (object && !IsAboutToBeFinalized(&object)) {
4187                 TypeObjectKey** pentry =
4188                     HashSetInsert<TypeObjectKey*,TypeObjectKey,TypeObjectKey>
4189                         (zone->types.typeLifoAlloc, objectSet, objectCount, object);
4190                 if (pentry) {
4191                     *pentry = object;
4192                 } else {
4193                     *oom = true;
4194                     flags |= TYPE_FLAG_ANYOBJECT;
4195                     clearObjects();
4196                     objectCount = 0;
4197                     break;
4198                 }
4199             }
4200         }
4201         setBaseObjectCount(objectCount);
4202     } else if (objectCount == 1) {
4203         TypeObjectKey* object = (TypeObjectKey*) objectSet;
4204         if (IsAboutToBeFinalized(&object)) {
4205             objectSet = nullptr;
4206             setBaseObjectCount(0);
4207         } else {
4208             objectSet = reinterpret_cast<TypeObjectKey**>(object);
4209         }
4210     }
4211
4212     /*
4213      * Type constraints only hold weak references. Copy constraints referring
4214      * to data that is still live into the zone's new arena.
4215      */
4216     TypeConstraint* constraint = constraintList;
4217     constraintList = nullptr;
4218     while (constraint) {
4219         TypeConstraint* copy;
4220         if (constraint->sweep(zone->types, &copy)) {
4221             if (copy) {
4222                 copy->next = constraintList;
4223                 constraintList = copy;
4224             } else {
4225                 *oom = true;
4226             }
4227         }
4228         constraint = constraint->next;
4229     }
4230 }
4231
4232 inline void
4233 TypeObject::clearProperties()
4234 {
4235     setBasePropertyCount(0);
4236     propertySet = nullptr;
4237 }
4238
4239 /*
4240  * Before sweeping the arenas themselves, scan all type objects in a
4241  * compartment to fixup weak references: property type sets referencing dead
4242  * JS and type objects, and singleton JS objects whose type is not referenced
4243  * elsewhere. This also releases memory associated with dead type objects,
4244  * so that type objects do not need later finalization.
4245  */
4246 inline void
4247 TypeObject::sweep(FreeOp* fop, bool* oom)
4248 {
4249     if (!isMarked()) {
4250         if (newScript_)
4251             fop->free_(newScript_);
4252         return;
4253     }
4254
4255     LifoAlloc& typeLifoAlloc = zone()->types.typeLifoAlloc;
4256
4257     /*
4258      * Properties were allocated from the old arena, and need to be copied over
4259      * to the new one.
4260      */
4261     unsigned propertyCount = basePropertyCount();
4262     if (propertyCount >= 2) {
4263         unsigned oldCapacity = HashSetCapacity(propertyCount);
4264         Property** oldArray = propertySet;
4265
4266         clearProperties();
4267         propertyCount = 0;
4268         for (unsigned i = 0; i < oldCapacity; i++) {
4269             Property* prop = oldArray[i];
4270             if (prop) {
4271                 if (singleton() && !prop->types.constraintList && !zone()->isPreservingCode()) {
4272                     /*
4273                      * Don't copy over properties of singleton objects when their
4274                      * presence will not be required by jitcode or type constraints
4275                      * (i.e. for the definite properties analysis). The contents of
4276                      * these type sets will be regenerated as necessary.
4277                      */
4278                     continue;
4279                 }
4280
4281                 Property* newProp = typeLifoAlloc.new_<Property>(*prop);
4282                 if (newProp) {
4283                     Property** pentry =
4284                         HashSetInsert<jsid,Property,Property>
4285                             (typeLifoAlloc, propertySet, propertyCount, prop->id);
4286                     if (pentry) {
4287                         *pentry = newProp;
4288                         newProp->types.sweep(zone(), oom);
4289                         continue;
4290                     }
4291                 }
4292
4293                 *oom = true;
4294                 addFlags(OBJECT_FLAG_DYNAMIC_MASK | OBJECT_FLAG_UNKNOWN_PROPERTIES);
4295                 clearProperties();
4296                 return;
4297             }
4298         }
4299         setBasePropertyCount(propertyCount);
4300     } else if (propertyCount == 1) {
4301         Property* prop = (Property*) propertySet;
4302         if (singleton() && !prop->types.constraintList && !zone()->isPreservingCode()) {
4303             // Skip, as above.
4304             clearProperties();
4305         } else {
4306             Property* newProp = typeLifoAlloc.new_<Property>(*prop);
4307             if (newProp) {
4308                 propertySet = (Property**) newProp;
4309                 newProp->types.sweep(zone(), oom);
4310             } else {
4311                 *oom = true;
4312                 addFlags(OBJECT_FLAG_DYNAMIC_MASK | OBJECT_FLAG_UNKNOWN_PROPERTIES);
4313                 clearProperties();
4314                 return;
4315             }
4316         }
4317     }
4318 }
4319
4320 void
4321 TypeCompartment::clearTables()
4322 {
4323     if (allocationSiteTable && allocationSiteTable->initialized())
4324         allocationSiteTable->clear();
4325     if (arrayTypeTable && arrayTypeTable->initialized())
4326         arrayTypeTable->clear();
4327     if (objectTypeTable && objectTypeTable->initialized())
4328         objectTypeTable->clear();
4329 }
4330
4331 void
4332 TypeCompartment::sweep(FreeOp* fop)
4333 {
4334     /*
4335      * Iterate through the array/object type tables and remove all entries
4336      * referencing collected data. These tables only hold weak references.
4337      */
4338
4339     if (arrayTypeTable) {
4340         for (ArrayTypeTable::Enum e(*arrayTypeTable); !e.empty(); e.popFront()) {
4341             const ArrayTableKey& key = e.front().key();
4342             JS_ASSERT(key.type.isUnknown() || !key.type.isSingleObject());
4343
4344             bool remove = false;
4345             TypeObject* typeObject = nullptr;
4346             if (!key.type.isUnknown() && key.type.isTypeObject()) {
4347                 typeObject = key.type.typeObjectNoBarrier();
4348                 if (IsTypeObjectAboutToBeFinalized(&typeObject))
4349                     remove = true;
4350             }
4351             if (IsTypeObjectAboutToBeFinalized(e.front().value().unsafeGet()))
4352                 remove = true;
4353
4354             if (remove) {
4355                 e.removeFront();
4356             } else if (typeObject && typeObject != key.type.typeObjectNoBarrier()) {
4357                 ArrayTableKey newKey;
4358                 newKey.type = Type::ObjectType(typeObject);
4359                 newKey.proto = key.proto;
4360                 e.rekeyFront(newKey);
4361             }
4362         }
4363     }
4364
4365     if (objectTypeTable) {
4366         for (ObjectTypeTable::Enum e(*objectTypeTable); !e.empty(); e.popFront()) {
4367             const ObjectTableKey& key = e.front().key();
4368             ObjectTableEntry& entry = e.front().value();
4369
4370             bool remove = false;
4371             if (IsTypeObjectAboutToBeFinalized(entry.object.unsafeGet()))
4372                 remove = true;
4373             if (IsShapeAboutToBeFinalized(entry.shape.unsafeGet()))
4374                 remove = true;
4375             for (unsigned i = 0; !remove && i < key.nproperties; i++) {
4376                 if (JSID_IS_STRING(key.properties[i])) {
4377                     JSString* str = JSID_TO_STRING(key.properties[i]);
4378                     if (IsStringAboutToBeFinalized(&str))
4379                         remove = true;
4380                     JS_ASSERT(AtomToId((JSAtom*)str) == key.properties[i]);
4381                 } else if (JSID_IS_SYMBOL(key.properties[i])) {
4382                     JS::Symbol* sym = JSID_TO_SYMBOL(key.properties[i]);
4383                     if (IsSymbolAboutToBeFinalized(&sym))
4384                         remove = true;
4385                 }
4386
4387                 JS_ASSERT(!entry.types[i].isSingleObject());
4388                 TypeObject* typeObject = nullptr;
4389                 if (entry.types[i].isTypeObject()) {
4390                     typeObject = entry.types[i].typeObjectNoBarrier();
4391                     if (IsTypeObjectAboutToBeFinalized(&typeObject))
4392                         remove = true;
4393                     else if (typeObject != entry.types[i].typeObjectNoBarrier())
4394                         entry.types[i] = Type::ObjectType(typeObject);
4395                 }
4396             }
4397
4398             if (remove) {
4399                 js_free(key.properties);
4400                 js_free(entry.types);
4401                 e.removeFront();
4402             }
4403         }
4404     }
4405
4406     if (allocationSiteTable) {
4407         for (AllocationSiteTable::Enum e(*allocationSiteTable); !e.empty(); e.popFront()) {
4408             AllocationSiteKey key = e.front().key();
4409             bool keyDying = IsScriptAboutToBeFinalized(&key.script);
4410             bool valDying = IsTypeObjectAboutToBeFinalized(e.front().value().unsafeGet());
4411             if (keyDying || valDying)
4412                 e.removeFront();
4413             else if (key.script != e.front().key().script)
4414                 e.rekeyFront(key);
4415         }
4416     }
4417 }
4418
4419 void
4420 JSCompartment::sweepNewTypeObjectTable(TypeObjectWithNewScriptSet& table)
4421 {
4422     JS_ASSERT(zone()->isCollecting());
4423     if (table.initialized()) {
4424         for (TypeObjectWithNewScriptSet::Enum e(table); !e.empty(); e.popFront()) {
4425             TypeObjectWithNewScriptEntry entry = e.front();
4426             if (IsTypeObjectAboutToBeFinalized(entry.object.unsafeGet()) ||
4427                 (entry.newFunction && IsObjectAboutToBeFinalized(&entry.newFunction)))
4428             {
4429                 e.removeFront();
4430             } else {
4431                 /* Any rekeying necessary is handled by fixupNewTypeObjectTable() below. */
4432                 JS_ASSERT(entry.object == e.front().object);
4433                 JS_ASSERT(entry.newFunction == e.front().newFunction);
4434             }
4435         }
4436     }
4437 }
4438
4439 #ifdef JSGC_COMPACTING
4440 void
4441 JSCompartment::fixupNewTypeObjectTable(TypeObjectWithNewScriptSet& table)
4442 {
4443     /*
4444      * Each entry's hash depends on the object's prototype and we can't tell
4445      * whether that has been moved or not in sweepNewTypeObjectTable().
4446      */
4447     JS_ASSERT(zone()->isCollecting());
4448     if (table.initialized()) {
4449         for (TypeObjectWithNewScriptSet::Enum e(table); !e.empty(); e.popFront()) {
4450             TypeObjectWithNewScriptEntry entry = e.front();
4451             bool needRekey = false;
4452             if (IsForwarded(entry.object.get())) {
4453                 entry.object.set(Forwarded(entry.object.get()));
4454                 needRekey = true;
4455             }
4456             TaggedProto proto = entry.object->proto();
4457             if (proto.isObject() && IsForwarded(proto.toObject())) {
4458                 proto = TaggedProto(Forwarded(proto.toObject()));
4459                 needRekey = true;
4460             }
4461             if (entry.newFunction && IsForwarded(entry.newFunction)) {
4462                 entry.newFunction = Forwarded(entry.newFunction);
4463                 needRekey = true;
4464             }
4465             if (needRekey) {
4466                 TypeObjectWithNewScriptSet::Lookup lookup(entry.object->clasp(),
4467                                                           proto,
4468                                                           entry.newFunction);
4469                 e.rekeyFront(lookup, entry);
4470             }
4471         }
4472     }
4473 }
4474 #endif
4475
4476 #ifdef JSGC_HASH_TABLE_CHECKS
4477
4478 void
4479 JSCompartment::checkTypeObjectTablesAfterMovingGC()
4480 {
4481     checkTypeObjectTableAfterMovingGC(newTypeObjects);
4482     checkTypeObjectTableAfterMovingGC(lazyTypeObjects);
4483 }
4484
4485 void
4486 JSCompartment::checkTypeObjectTableAfterMovingGC(TypeObjectWithNewScriptSet& table)
4487 {
4488     /*
4489      * Assert that nothing points into the nursery or needs to be relocated, and
4490      * that the hash table entries are discoverable.
4491      */
4492     if (!table.initialized())
4493         return;
4494
4495     for (TypeObjectWithNewScriptSet::Enum e(table); !e.empty(); e.popFront()) {
4496         TypeObjectWithNewScriptEntry entry = e.front();
4497         CheckGCThingAfterMovingGC(entry.object.get());
4498         TaggedProto proto = entry.object->proto();
4499         if (proto.isObject())
4500             CheckGCThingAfterMovingGC(proto.toObject());
4501         CheckGCThingAfterMovingGC(entry.newFunction);
4502
4503         TypeObjectWithNewScriptEntry::Lookup
4504             lookup(entry.object->clasp(), proto, entry.newFunction);
4505         TypeObjectWithNewScriptSet::Ptr ptr = table.lookup(lookup);
4506         JS_ASSERT(ptr.found() && &*ptr == &e.front());
4507     }
4508 }
4509
4510 #endif // JSGC_HASH_TABLE_CHECKS
4511
4512 TypeCompartment::~TypeCompartment()
4513 {
4514     js_delete(arrayTypeTable);
4515     js_delete(objectTypeTable);
4516     js_delete(allocationSiteTable);
4517 }
4518
4519 /* static */ void
4520 TypeScript::Sweep(FreeOp* fop, JSScript* script, bool* oom)
4521 {
4522     JSCompartment* compartment = script->compartment();
4523     JS_ASSERT(compartment->zone()->isGCSweepingOrCompacting());
4524
4525     unsigned num = NumTypeSets(script);
4526     StackTypeSet* typeArray = script->types->typeArray();
4527
4528     /* Remove constraints and references to dead objects from the persistent type sets. */
4529     for (unsigned i = 0; i < num; i++)
4530         typeArray[i].sweep(compartment->zone(), oom);
4531 }
4532
4533 void
4534 TypeScript::destroy()
4535 {
4536     js_free(this);
4537 }
4538
4539 void
4540 Zone::addSizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf,
4541                              size_t* typePool,
4542                              size_t* baselineStubsOptimized)
4543 {
4544     *typePool += types.typeLifoAlloc.sizeOfExcludingThis(mallocSizeOf);
4545     if (jitZone()) {
4546         *baselineStubsOptimized +=
4547             jitZone()->optimizedStubSpace()->sizeOfExcludingThis(mallocSizeOf);
4548     }
4549 }
4550
4551 void
4552 TypeCompartment::addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
4553                                         size_t* allocationSiteTables,
4554                                         size_t* arrayTypeTables,
4555                                         size_t* objectTypeTables)
4556 {
4557     if (allocationSiteTable)
4558         *allocationSiteTables += allocationSiteTable->sizeOfIncludingThis(mallocSizeOf);
4559
4560     if (arrayTypeTable)
4561         *arrayTypeTables += arrayTypeTable->sizeOfIncludingThis(mallocSizeOf);
4562
4563     if (objectTypeTable) {
4564         *objectTypeTables += objectTypeTable->sizeOfIncludingThis(mallocSizeOf);
4565
4566         for (ObjectTypeTable::Enum e(*objectTypeTable);
4567              !e.empty();
4568              e.popFront())
4569         {
4570             const ObjectTableKey& key = e.front().key();
4571             const ObjectTableEntry& value = e.front().value();
4572
4573             /* key.ids and values.types have the same length. */
4574             *objectTypeTables += mallocSizeOf(key.properties) + mallocSizeOf(value.types);
4575         }
4576     }
4577 }
4578
4579 size_t
4580 TypeObject::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const
4581 {
4582     return mallocSizeOf(newScript_);
4583 }
4584
4585 TypeZone::TypeZone(Zone* zone)
4586   : zone_(zone),
4587     typeLifoAlloc(TYPE_LIFO_ALLOC_PRIMARY_CHUNK_SIZE),
4588     compilerOutputs(nullptr),
4589     pendingRecompiles(nullptr)
4590 {
4591 }
4592
4593 TypeZone::~TypeZone()
4594 {
4595     js_delete(compilerOutputs);
4596     js_delete(pendingRecompiles);
4597 }
4598
4599 void
4600 TypeZone::sweep(FreeOp* fop, bool releaseTypes, bool* oom)
4601 {
4602     JS_ASSERT(zone()->isGCSweepingOrCompacting());
4603
4604     JSRuntime* rt = fop->runtime();
4605
4606     /*
4607      * Clear the analysis pool, but don't release its data yet. While
4608      * sweeping types any live data will be allocated into the pool.
4609      */
4610     LifoAlloc oldAlloc(typeLifoAlloc.defaultChunkSize());
4611     oldAlloc.steal(&typeLifoAlloc);
4612
4613     /* Sweep and find compressed indexes for each compiler output. */
4614     size_t newCompilerOutputCount = 0;
4615
4616     if (compilerOutputs) {
4617         for (size_t i = 0; i < compilerOutputs->length(); i++) {
4618             CompilerOutput& output = (*compilerOutputs)[i];
4619             if (output.isValid()) {
4620                 JSScript* script = output.script();
4621                 if (IsScriptAboutToBeFinalized(&script)) {
4622                     jit::GetIonScript(script, output.mode())->recompileInfoRef() = RecompileInfo(uint32_t(-1));
4623                     output.invalidate();
4624                 } else {
4625                     output.setSweepIndex(newCompilerOutputCount++);
4626                 }
4627             }
4628         }
4629     }
4630
4631     {
4632         gcstats::MaybeAutoPhase ap2(rt->gc.stats, !rt->isHeapCompacting(),
4633                                     gcstats::PHASE_DISCARD_TI);
4634
4635         for (ZoneCellIterUnderGC i(zone(), FINALIZE_SCRIPT); !i.done(); i.next()) {
4636             JSScript* script = i.get<JSScript>();
4637             if (script->types) {
4638                 types::TypeScript::Sweep(fop, script, oom);
4639
4640                 if (releaseTypes) {
4641                     script->types->destroy();
4642                     script->types = nullptr;
4643
4644                     /*
4645                      * Freeze constraints on stack type sets need to be
4646                      * regenerated the next time the script is analyzed.
4647                      */
4648                     script->clearHasFreezeConstraints();
4649
4650                     JS_ASSERT(!script->hasIonScript());
4651                     JS_ASSERT(!script->hasParallelIonScript());
4652                 } else {
4653                     /* Update the recompile indexes in any IonScripts still on the script. */
4654                     if (script->hasIonScript())
4655                         script->ionScript()->recompileInfoRef().shouldSweep(*this);
4656                     if (script->hasParallelIonScript())
4657                         script->parallelIonScript()->recompileInfoRef().shouldSweep(*this);
4658                 }
4659             }
4660         }
4661     }
4662
4663     {
4664         gcstats::MaybeAutoPhase ap2(rt->gc.stats, !rt->isHeapCompacting(),
4665                                     gcstats::PHASE_SWEEP_TYPES);
4666
4667         for (gc::ZoneCellIterUnderGC iter(zone(), gc::FINALIZE_TYPE_OBJECT);
4668              !iter.done(); iter.next())
4669         {
4670             TypeObject* object = iter.get<TypeObject>();
4671             object->sweep(fop, oom);
4672         }
4673
4674         for (CompartmentsInZoneIter comp(zone()); !comp.done(); comp.next())
4675             comp->types.sweep(fop);
4676     }
4677
4678     if (compilerOutputs) {
4679         size_t sweepIndex = 0;
4680         for (size_t i = 0; i < compilerOutputs->length(); i++) {
4681             CompilerOutput output = (*compilerOutputs)[i];
4682             if (output.isValid()) {
4683                 JS_ASSERT(sweepIndex == output.sweepIndex());
4684                 output.invalidateSweepIndex();
4685                 (*compilerOutputs)[sweepIndex++] = output;
4686             }
4687         }
4688         JS_ASSERT(sweepIndex == newCompilerOutputCount);
4689         JS_ALWAYS_TRUE(compilerOutputs->resize(newCompilerOutputCount));
4690     }
4691
4692     {
4693         gcstats::MaybeAutoPhase ap2(rt->gc.stats, !rt->isHeapCompacting(),
4694                                     gcstats::PHASE_FREE_TI_ARENA);
4695         rt->freeLifoAlloc.transferFrom(&oldAlloc);
4696     }
4697 }
4698
4699 void
4700 TypeZone::clearAllNewScriptsOnOOM()
4701 {
4702     for (gc::ZoneCellIterUnderGC iter(zone(), gc::FINALIZE_TYPE_OBJECT);
4703          !iter.done(); iter.next())
4704     {
4705         TypeObject* object = iter.get<TypeObject>();
4706         object->maybeClearNewScriptOnOOM();
4707     }
4708 }
4709
4710 #ifdef DEBUG
4711 void
4712 TypeScript::printTypes(JSContext* cx, HandleScript script) const
4713 {
4714     JS_ASSERT(script->types == this);
4715
4716     if (!script->hasBaselineScript())
4717         return;
4718
4719     AutoEnterAnalysis enter(nullptr, script->compartment());
4720
4721     if (script->functionNonDelazifying())
4722         fprintf(stderr, "Function");
4723     else if (script->isForEval())
4724         fprintf(stderr, "Eval");
4725     else
4726         fprintf(stderr, "Main");
4727     fprintf(stderr, " #%u %s:%d ", script->id(), script->filename(), (int) script->lineno());
4728
4729     if (script->functionNonDelazifying()) {
4730         if (js::PropertyName* name = script->functionNonDelazifying()->name())
4731             name->dumpCharsNoNewline();
4732     }
4733
4734     fprintf(stderr, "\n    this:");
4735     TypeScript::ThisTypes(script)->print();
4736
4737     for (unsigned i = 0;
4738          script->functionNonDelazifying() && i < script->functionNonDelazifying()->nargs();
4739          i++)
4740     {
4741         fprintf(stderr, "\n    arg%u:", i);
4742         TypeScript::ArgTypes(script, i)->print();
4743     }
4744     fprintf(stderr, "\n");
4745
4746     for (jsbytecode* pc = script->code(); pc < script->codeEnd(); pc += GetBytecodeLength(pc)) {
4747         {
4748             fprintf(stderr, "#%u:", script->id());
4749             Sprinter sprinter(cx);
4750             if (!sprinter.init())
4751                 return;
4752             js_Disassemble1(cx, script, pc, script->pcToOffset(pc), true, &sprinter);
4753             fprintf(stderr, "%s", sprinter.string());
4754         }
4755
4756         if (js_CodeSpec[*pc].format & JOF_TYPESET) {
4757             StackTypeSet* types = TypeScript::BytecodeTypes(script, pc);
4758             fprintf(stderr, "  typeset %u:", unsigned(types - typeArray()));
4759             types->print();
4760             fprintf(stderr, "\n");
4761         }
4762     }
4763
4764     fprintf(stderr, "\n");
4765 }
4766 #endif /* DEBUG */
4767
4768 void
4769 TypeObject::setNewScript(TypeNewScript* newScript)
4770 {
4771     JS_ASSERT(!newScript_);
4772     newScript_ = newScript;
4773 }