Source/JavaScriptCore/runtime/TypeSet.cpp

   1 /*
   2  * Copyright (C) 2014, 2015 Apple Inc. All Rights Reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "TypeSet.h"
  28
  29 #include "InspectorProtocolObjects.h"
  30 #include "JSCJSValue.h"
  31 #include "JSCJSValueInlines.h"
  32 #include <wtf/text/CString.h>
  33 #include <wtf/text/WTFString.h>
  34 #include <wtf/text/StringBuilder.h>
  35 #include <wtf/Vector.h>
  36
  37 namespace JSC {
  38
  39 TypeSet::TypeSet()
  40     : m_seenTypes(TypeNothing)
  41     , m_isOverflown(false)
  42 {
  43 }
  44
  45 void TypeSet::addTypeInformation(RuntimeType type, PassRefPtr<StructureShape> prpNewShape, Structure* structure)
  46 {
  47     RefPtr<StructureShape> newShape = prpNewShape;
  48     m_seenTypes = m_seenTypes | type;
  49
  50     if (structure && newShape && !runtimeTypeIsPrimitive(type)) {
  51         if (!m_structureSet.contains(structure)) {
  52             m_structureSet.add(structure);
  53             // Make one more pass making sure that:
  54             // - We don't have two instances of the same shape. (Same shapes may have different Structures).
  55             // - We don't have two shapes that share the same prototype chain. If these shapes share the same
  56             //   prototype chain, they will be merged into one shape.
  57             bool found = false;
  58             String hash = newShape->propertyHash();
  59             for (size_t i = 0; i < m_structureHistory.size(); i++) {
  60                 RefPtr<StructureShape>& seenShape = m_structureHistory.at(i);
  61                 if (seenShape->propertyHash() == hash) {
  62                     found = true;
  63                     break;
  64                 }
  65                 if (seenShape->hasSamePrototypeChain(newShape)) {
  66                     seenShape = StructureShape::merge(seenShape, newShape);
  67                     found = true;
  68                     break;
  69                 }
  70             }
  71
  72             if (!found) {
  73                 if (m_structureHistory.size() < 100)
  74                     m_structureHistory.append(newShape);
  75                 else if (!m_isOverflown)
  76                     m_isOverflown = true;
  77             }
  78         }
  79     }
  80 }
  81
  82 void TypeSet::invalidateCache()
  83 {
  84     auto keepMarkedStructuresFilter = [] (Structure* structure) -> bool { return Heap::isMarked(structure); };
  85     m_structureSet.genericFilter(keepMarkedStructuresFilter);
  86 }
  87
  88 String TypeSet::dumpTypes() const
  89 {
  90     if (m_seenTypes == TypeNothing)
  91         return ASCIILiteral("(Unreached Statement)");
  92
  93     StringBuilder seen;
  94
  95     if (m_seenTypes & TypeFunction)
  96         seen.appendLiteral("Function ");
  97     if (m_seenTypes & TypeUndefined)
  98         seen.appendLiteral("Undefined ");
  99     if (m_seenTypes & TypeNull)
 100         seen.appendLiteral("Null ");
 101     if (m_seenTypes & TypeBoolean)
 102         seen.appendLiteral("Boolean ");
 103     if (m_seenTypes & TypeMachineInt)
 104         seen.appendLiteral("MachineInt ");
 105     if (m_seenTypes & TypeNumber)
 106         seen.appendLiteral("Number ");
 107     if (m_seenTypes & TypeString)
 108         seen.appendLiteral("String ");
 109     if (m_seenTypes & TypeObject)
 110         seen.appendLiteral("Object ");
 111     if (m_seenTypes & TypeSymbol)
 112         seen.appendLiteral("Symbol ");
 113
 114     for (size_t i = 0; i < m_structureHistory.size(); i++) {
 115         RefPtr<StructureShape> shape = m_structureHistory.at(i);
 116         seen.append(shape->m_constructorName);
 117         seen.append(' ');
 118     }
 119
 120     if (m_structureHistory.size())
 121         seen.appendLiteral("\nStructures:[ ");
 122     for (size_t i = 0; i < m_structureHistory.size(); i++) {
 123         seen.append(m_structureHistory.at(i)->stringRepresentation());
 124         seen.append(' ');
 125     }
 126     if (m_structureHistory.size())
 127         seen.append(']');
 128
 129     if (m_structureHistory.size()) {
 130         seen.appendLiteral("\nLeast Common Ancestor: ");
 131         seen.append(leastCommonAncestor());
 132     }
 133
 134     return seen.toString();
 135 }
 136
 137 bool TypeSet::doesTypeConformTo(RuntimeTypeMask test) const
 138 {
 139     // This function checks if our seen types conform  to the types described by the test bitstring. (i.e we haven't seen more types than test).
 140     // We are <= to those types if ANDing with the bitstring doesn't zero out any of our bits.
 141
 142     // For example:
 143
 144     // 0b0110 (seen)
 145     // 0b1111 (test)
 146     // ------ (AND)
 147     // 0b0110 == seen
 148
 149     // 0b0110 (seen)
 150     // 0b0010 (test)
 151     // ------ (AND)
 152     // 0b0010 != seen
 153
 154     return m_seenTypes != TypeNothing && (m_seenTypes & test) == m_seenTypes;
 155 }
 156
 157 String TypeSet::displayName() const
 158 {
 159     if (m_seenTypes == TypeNothing)
 160         return emptyString();
 161
 162     if (m_structureHistory.size() && doesTypeConformTo(TypeObject | TypeNull | TypeUndefined)) {
 163         String ctorName = leastCommonAncestor();
 164
 165         if (doesTypeConformTo(TypeObject))
 166             return ctorName;
 167         if (doesTypeConformTo(TypeObject | TypeNull | TypeUndefined))
 168             return ctorName + '?';
 169     }
 170
 171     // The order of these checks are important. For example, if a value is only a function, it conforms to TypeFunction, but it also conforms to TypeFunction | TypeNull.
 172     // Therefore, more specific types must be checked first.
 173
 174     if (doesTypeConformTo(TypeFunction))
 175         return ASCIILiteral("Function");
 176     if (doesTypeConformTo(TypeUndefined))
 177         return ASCIILiteral("Undefined");
 178     if (doesTypeConformTo(TypeNull))
 179         return ASCIILiteral("Null");
 180     if (doesTypeConformTo(TypeBoolean))
 181         return ASCIILiteral("Boolean");
 182     if (doesTypeConformTo(TypeMachineInt))
 183         return ASCIILiteral("Integer");
 184     if (doesTypeConformTo(TypeNumber | TypeMachineInt))
 185         return ASCIILiteral("Number");
 186     if (doesTypeConformTo(TypeString))
 187         return ASCIILiteral("String");
 188     if (doesTypeConformTo(TypeSymbol))
 189         return ASCIILiteral("Symbol");
 190
 191     if (doesTypeConformTo(TypeNull | TypeUndefined))
 192         return ASCIILiteral("(?)");
 193
 194     if (doesTypeConformTo(TypeFunction | TypeNull | TypeUndefined))
 195         return ASCIILiteral("Function?");
 196     if (doesTypeConformTo(TypeBoolean | TypeNull | TypeUndefined))
 197         return ASCIILiteral("Boolean?");
 198     if (doesTypeConformTo(TypeMachineInt | TypeNull | TypeUndefined))
 199         return ASCIILiteral("Integer?");
 200     if (doesTypeConformTo(TypeNumber | TypeMachineInt | TypeNull | TypeUndefined))
 201         return ASCIILiteral("Number?");
 202     if (doesTypeConformTo(TypeString | TypeNull | TypeUndefined))
 203         return ASCIILiteral("String?");
 204     if (doesTypeConformTo(TypeSymbol | TypeNull | TypeUndefined))
 205         return ASCIILiteral("Symbol?");
 206
 207     if (doesTypeConformTo(TypeObject | TypeFunction | TypeString))
 208         return ASCIILiteral("Object");
 209     if (doesTypeConformTo(TypeObject | TypeFunction | TypeString | TypeNull | TypeUndefined))
 210         return ASCIILiteral("Object?");
 211
 212     return ASCIILiteral("(many)");
 213 }
 214
 215 String TypeSet::leastCommonAncestor() const
 216 {
 217     return StructureShape::leastCommonAncestor(m_structureHistory);
 218 }
 219
 220 Ref<Inspector::Protocol::Array<Inspector::Protocol::Runtime::StructureDescription>> TypeSet::allStructureRepresentations() const
 221 {
 222     auto description = Inspector::Protocol::Array<Inspector::Protocol::Runtime::StructureDescription>::create();
 223
 224     for (size_t i = 0; i < m_structureHistory.size(); i++)
 225         description->addItem(m_structureHistory.at(i)->inspectorRepresentation());
 226
 227     return description;
 228 }
 229
 230 Ref<Inspector::Protocol::Runtime::TypeSet> TypeSet::inspectorTypeSet() const
 231 {
 232     return Inspector::Protocol::Runtime::TypeSet::create()
 233         .setIsFunction((m_seenTypes & TypeFunction) != TypeNothing)
 234         .setIsUndefined((m_seenTypes & TypeUndefined) != TypeNothing)
 235         .setIsNull((m_seenTypes & TypeNull) != TypeNothing)
 236         .setIsBoolean((m_seenTypes & TypeBoolean) != TypeNothing)
 237         .setIsInteger((m_seenTypes & TypeMachineInt) != TypeNothing)
 238         .setIsNumber((m_seenTypes & TypeNumber) != TypeNothing)
 239         .setIsString((m_seenTypes & TypeString) != TypeNothing)
 240         .setIsObject((m_seenTypes & TypeObject) != TypeNothing)
 241         .setIsSymbol((m_seenTypes & TypeSymbol) != TypeNothing)
 242         .release();
 243 }
 244
 245 String TypeSet::toJSONString() const
 246 {
 247     // This returns a JSON string representing an Object with the following properties:
 248     //     displayTypeName: 'String'
 249     //     primitiveTypeNames: 'Array<String>'
 250     //     structures: 'Array<JSON<StructureShape>>'
 251
 252     StringBuilder json;
 253     json.append('{');
 254
 255     json.appendLiteral("\"displayTypeName\":");
 256     json.append('"');
 257     json.append(displayName());
 258     json.append('"');
 259     json.append(',');
 260
 261     json.appendLiteral("\"primitiveTypeNames\":");
 262     json.append('[');
 263     bool hasAnItem = false;
 264     if (m_seenTypes & TypeUndefined) {
 265         hasAnItem = true;
 266         json.appendLiteral("\"Undefined\"");
 267     }
 268     if (m_seenTypes & TypeNull) {
 269         if (hasAnItem)
 270             json.append(',');
 271         hasAnItem = true;
 272         json.appendLiteral("\"Null\"");
 273     }
 274     if (m_seenTypes & TypeBoolean) {
 275         if (hasAnItem)
 276             json.append(',');
 277         hasAnItem = true;
 278         json.appendLiteral("\"Boolean\"");
 279     }
 280     if (m_seenTypes & TypeMachineInt) {
 281         if (hasAnItem)
 282             json.append(',');
 283         hasAnItem = true;
 284         json.appendLiteral("\"Integer\"");
 285     }
 286     if (m_seenTypes & TypeNumber) {
 287         if (hasAnItem)
 288             json.append(',');
 289         hasAnItem = true;
 290         json.appendLiteral("\"Number\"");
 291     }
 292     if (m_seenTypes & TypeString) {
 293         if (hasAnItem)
 294             json.append(',');
 295         hasAnItem = true;
 296         json.appendLiteral("\"String\"");
 297     }
 298     if (m_seenTypes & TypeSymbol) {
 299         if (hasAnItem)
 300             json.append(',');
 301         hasAnItem = true;
 302         json.appendLiteral("\"Symbol\"");
 303     }
 304     json.append(']');
 305
 306     json.append(',');
 307
 308     json.appendLiteral("\"structures\":");
 309     json.append('[');
 310     hasAnItem = false;
 311     for (size_t i = 0; i < m_structureHistory.size(); i++) {
 312         if (hasAnItem)
 313             json.append(',');
 314         hasAnItem = true;
 315         json.append(m_structureHistory[i]->toJSONString());
 316     }
 317     json.append(']');
 318
 319     json.append('}');
 320     return json.toString();
 321 }
 322
 323 StructureShape::StructureShape()
 324     : m_proto(nullptr)
 325     , m_propertyHash(nullptr)
 326     , m_final(false)
 327     , m_isInDictionaryMode(false)
 328 {
 329 }
 330
 331 void StructureShape::markAsFinal()
 332 {
 333     ASSERT(!m_final);
 334     m_final = true;
 335 }
 336
 337 void StructureShape::addProperty(UniquedStringImpl& uid)
 338 {
 339     ASSERT(!m_final);
 340     m_fields.add(&uid);
 341 }
 342
 343 String StructureShape::propertyHash()
 344 {
 345     ASSERT(m_final);
 346     if (m_propertyHash)
 347         return *m_propertyHash;
 348
 349     StringBuilder builder;
 350     builder.append(':');
 351     builder.append(m_constructorName);
 352     builder.append(':');
 353     for (auto& key : m_fields) {
 354         String property = key.get();
 355         property.replace(":", "\\:"); // Ensure that hash({"foo:", "bar"}) != hash({"foo", ":bar"}) because we're using colons as a separator and colons are legal characters in field names in JS.
 356         builder.append(property);
 357     }
 358
 359     if (m_proto) {
 360         builder.append(':');
 361         builder.appendLiteral("__proto__");
 362         builder.append(m_proto->propertyHash());
 363     }
 364
 365     m_propertyHash = std::make_unique<String>(builder.toString());
 366     return *m_propertyHash;
 367 }
 368
 369 String StructureShape::leastCommonAncestor(const Vector<RefPtr<StructureShape>> shapes)
 370 {
 371     if (!shapes.size())
 372         return emptyString();
 373
 374     RefPtr<StructureShape> origin = shapes.at(0);
 375     for (size_t i = 1; i < shapes.size(); i++) {
 376         bool foundLUB = false;
 377         while (!foundLUB) {
 378             RefPtr<StructureShape> check = shapes.at(i);
 379             String curCtorName = origin->m_constructorName;
 380             while (check) {
 381                 if (check->m_constructorName == curCtorName) {
 382                     foundLUB = true;
 383                     break;
 384                 }
 385                 check = check->m_proto;
 386             }
 387             if (!foundLUB) {
 388                 origin = origin->m_proto;
 389                 // All Objects must share the 'Object' Prototype. Therefore, at the very least, we should always converge on 'Object' before reaching a null prototype.
 390                 RELEASE_ASSERT(origin);
 391             }
 392         }
 393
 394         if (origin->m_constructorName == "Object")
 395             break;
 396     }
 397
 398     return origin->m_constructorName;
 399 }
 400
 401 String StructureShape::stringRepresentation()
 402 {
 403     StringBuilder representation;
 404     RefPtr<StructureShape> curShape = this;
 405
 406     representation.append('{');
 407     while (curShape) {
 408         for (auto it = curShape->m_fields.begin(), end = curShape->m_fields.end(); it != end; ++it) {
 409             String prop((*it).get());
 410             representation.append(prop);
 411             representation.appendLiteral(", ");
 412         }
 413
 414         if (curShape->m_proto) {
 415             representation.appendLiteral("__proto__ [");
 416             representation.append(curShape->m_proto->m_constructorName);
 417             representation.appendLiteral("], ");
 418         }
 419
 420         curShape = curShape->m_proto;
 421     }
 422
 423     if (representation.length() >= 3)
 424         representation.resize(representation.length() - 2);
 425
 426     representation.append('}');
 427
 428     return representation.toString();
 429 }
 430
 431 String StructureShape::toJSONString() const
 432 {
 433     // This returns a JSON string representing an Object with the following properties:
 434     //     constructorName: 'String'
 435     //     fields: 'Array<String>'
 436     //     optionalFields: 'Array<String>'
 437     //     proto: 'JSON<StructureShape> | null'
 438
 439     StringBuilder json;
 440     json.append('{');
 441
 442     json.appendLiteral("\"constructorName\":");
 443     json.append('"');
 444     json.append(m_constructorName);
 445     json.append('"');
 446     json.append(',');
 447
 448     json.appendLiteral("\"isInDictionaryMode\":");
 449     if (m_isInDictionaryMode)
 450         json.appendLiteral("true");
 451     else
 452         json.appendLiteral("false");
 453     json.append(',');
 454
 455     json.appendLiteral("\"fields\":");
 456     json.append('[');
 457     bool hasAnItem = false;
 458     for (auto it = m_fields.begin(), end = m_fields.end(); it != end; ++it) {
 459         if (hasAnItem)
 460             json.append(',');
 461         hasAnItem = true;
 462
 463         String fieldName((*it).get());
 464         json.append('"');
 465         json.append(fieldName);
 466         json.append('"');
 467     }
 468     json.append(']');
 469     json.append(',');
 470
 471     json.appendLiteral("\"optionalFields\":");
 472     json.append('[');
 473     hasAnItem = false;
 474     for (auto it = m_optionalFields.begin(), end = m_optionalFields.end(); it != end; ++it) {
 475         if (hasAnItem)
 476             json.append(',');
 477         hasAnItem = true;
 478
 479         String fieldName((*it).get());
 480         json.append('"');
 481         json.append(fieldName);
 482         json.append('"');
 483     }
 484     json.append(']');
 485     json.append(',');
 486
 487     json.appendLiteral("\"proto\":");
 488     if (m_proto)
 489         json.append(m_proto->toJSONString());
 490     else
 491         json.appendLiteral("null");
 492
 493     json.append('}');
 494
 495     return json.toString();
 496 }
 497
 498 Ref<Inspector::Protocol::Runtime::StructureDescription> StructureShape::inspectorRepresentation()
 499 {
 500     auto base = Inspector::Protocol::Runtime::StructureDescription::create().release();
 501     Ref<Inspector::Protocol::Runtime::StructureDescription> currentObject = base.copyRef();
 502     RefPtr<StructureShape> currentShape(this);
 503
 504     while (currentShape) {
 505         auto fields = Inspector::Protocol::Array<String>::create();
 506         auto optionalFields = Inspector::Protocol::Array<String>::create();
 507         for (auto field : currentShape->m_fields)
 508             fields->addItem(field.get());
 509         for (auto field : currentShape->m_optionalFields)
 510             optionalFields->addItem(field.get());
 511
 512         currentObject->setFields(&fields.get());
 513         currentObject->setOptionalFields(&optionalFields.get());
 514         currentObject->setConstructorName(currentShape->m_constructorName);
 515         currentObject->setIsImprecise(currentShape->m_isInDictionaryMode);
 516
 517         if (currentShape->m_proto) {
 518             auto nextObject = Inspector::Protocol::Runtime::StructureDescription::create().release();
 519             currentObject->setPrototypeStructure(&nextObject.get());
 520             currentObject = WTFMove(nextObject);
 521         }
 522
 523         currentShape = currentShape->m_proto;
 524     }
 525
 526     return base;
 527 }
 528
 529 bool StructureShape::hasSamePrototypeChain(PassRefPtr<StructureShape> prpOther)
 530 {
 531     RefPtr<StructureShape> self = this;
 532     RefPtr<StructureShape> other = prpOther;
 533     while (self && other) {
 534         if (self->m_constructorName != other->m_constructorName)
 535             return false;
 536         self = self->m_proto;
 537         other = other->m_proto;
 538     }
 539
 540     return !self && !other;
 541 }
 542
 543 PassRefPtr<StructureShape> StructureShape::merge(const PassRefPtr<StructureShape> prpA, const PassRefPtr<StructureShape> prpB)
 544 {
 545     RefPtr<StructureShape> a = prpA;
 546     RefPtr<StructureShape> b = prpB;
 547     ASSERT(a->hasSamePrototypeChain(b));
 548
 549     RefPtr<StructureShape> merged = StructureShape::create();
 550     for (auto field : a->m_fields) {
 551         if (b->m_fields.contains(field))
 552             merged->m_fields.add(field);
 553         else
 554             merged->m_optionalFields.add(field);
 555     }
 556
 557     for (auto field : b->m_fields) {
 558         if (!merged->m_fields.contains(field)) {
 559             auto addResult = merged->m_optionalFields.add(field);
 560             ASSERT_UNUSED(addResult, addResult.isNewEntry);
 561         }
 562     }
 563
 564     for (auto field : a->m_optionalFields)
 565         merged->m_optionalFields.add(field);
 566     for (auto field : b->m_optionalFields)
 567         merged->m_optionalFields.add(field);
 568
 569     ASSERT(a->m_constructorName == b->m_constructorName);
 570     merged->setConstructorName(a->m_constructorName);
 571
 572     if (a->m_proto) {
 573         RELEASE_ASSERT(b->m_proto);
 574         merged->setProto(StructureShape::merge(a->m_proto, b->m_proto));
 575     }
 576
 577     merged->markAsFinal();
 578
 579     return merged.release();
 580 }
 581
 582 void StructureShape::enterDictionaryMode()
 583 {
 584     m_isInDictionaryMode = true;
 585 }
 586
 587 } //namespace JSC