1/*
2 * Copyright (C) 2014-2019 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 "JSCInlines.h"
31#include <wtf/text/CString.h>
32#include <wtf/text/WTFString.h>
33#include <wtf/text/StringBuilder.h>
34#include <wtf/Vector.h>
35
36namespace JSC {
37
38TypeSet::TypeSet()
39 : m_isOverflown(false)
40 , m_seenTypes(TypeNothing)
41{
42}
43
44void TypeSet::addTypeInformation(RuntimeType type, RefPtr<StructureShape>&& passedNewShape, Structure* structure, bool sawPolyProtoStructure)
45{
46 m_seenTypes = m_seenTypes | type;
47
48 if (structure && passedNewShape && !runtimeTypeIsPrimitive(type)) {
49 Ref<StructureShape> newShape = passedNewShape.releaseNonNull();
50 // FIXME: TypeSet should be able to cache poly proto chains
51 // just by caching the prototype chain:
52 // https://bugs.webkit.org/show_bug.cgi?id=177627
53 if (sawPolyProtoStructure || !m_structureSet.contains(structure)) {
54 if (!sawPolyProtoStructure) {
55 ConcurrentJSLocker locker(m_lock);
56 m_structureSet.add(structure);
57 }
58 // Make one more pass making sure that:
59 // - We don't have two instances of the same shape. (Same shapes may have different Structures).
60 // - We don't have two shapes that share the same prototype chain. If these shapes share the same
61 // prototype chain, they will be merged into one shape.
62 String hash = newShape->propertyHash();
63 for (auto& seenShape : m_structureHistory) {
64 if (seenShape->propertyHash() == hash)
65 return;
66 if (seenShape->hasSamePrototypeChain(newShape.get())) {
67 seenShape = StructureShape::merge(seenShape.copyRef(), WTFMove(newShape));
68 return;
69 }
70 }
71
72 if (m_structureHistory.size() < 100) {
73 m_structureHistory.append(WTFMove(newShape));
74 return;
75 }
76 if (!m_isOverflown)
77 m_isOverflown = true;
78 }
79 }
80}
81
82void TypeSet::invalidateCache(VM& vm)
83{
84 ConcurrentJSLocker locker(m_lock);
85 auto keepMarkedStructuresFilter = [&] (Structure* structure) -> bool {
86 return vm.heap.isMarked(structure);
87 };
88 m_structureSet.genericFilter(keepMarkedStructuresFilter);
89}
90
91String TypeSet::dumpTypes() const
92{
93 if (m_seenTypes == TypeNothing)
94 return "(Unreached Statement)"_s;
95
96 StringBuilder seen;
97
98 if (m_seenTypes & TypeFunction)
99 seen.appendLiteral("Function ");
100 if (m_seenTypes & TypeUndefined)
101 seen.appendLiteral("Undefined ");
102 if (m_seenTypes & TypeNull)
103 seen.appendLiteral("Null ");
104 if (m_seenTypes & TypeBoolean)
105 seen.appendLiteral("Boolean ");
106 if (m_seenTypes & TypeAnyInt)
107 seen.appendLiteral("AnyInt ");
108 if (m_seenTypes & TypeNumber)
109 seen.appendLiteral("Number ");
110 if (m_seenTypes & TypeString)
111 seen.appendLiteral("String ");
112 if (m_seenTypes & TypeObject)
113 seen.appendLiteral("Object ");
114 if (m_seenTypes & TypeSymbol)
115 seen.appendLiteral("Symbol ");
116
117 for (const auto& shape : m_structureHistory) {
118 seen.append(shape->m_constructorName);
119 seen.append(' ');
120 }
121
122 if (m_structureHistory.size())
123 seen.appendLiteral("\nStructures:[ ");
124 for (const auto& shape : m_structureHistory) {
125 seen.append(shape->stringRepresentation());
126 seen.append(' ');
127 }
128 if (m_structureHistory.size())
129 seen.append(']');
130
131 if (m_structureHistory.size()) {
132 seen.appendLiteral("\nLeast Common Ancestor: ");
133 seen.append(leastCommonAncestor());
134 }
135
136 return seen.toString();
137}
138
139bool TypeSet::doesTypeConformTo(RuntimeTypeMask test) const
140{
141 // 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).
142 // We are <= to those types if ANDing with the bitstring doesn't zero out any of our bits.
143
144 // For example:
145
146 // 0b0110 (seen)
147 // 0b1111 (test)
148 // ------ (AND)
149 // 0b0110 == seen
150
151 // 0b0110 (seen)
152 // 0b0010 (test)
153 // ------ (AND)
154 // 0b0010 != seen
155
156 return m_seenTypes != TypeNothing && (m_seenTypes & test) == m_seenTypes;
157}
158
159String TypeSet::displayName() const
160{
161 if (m_seenTypes == TypeNothing)
162 return emptyString();
163
164 if (m_structureHistory.size() && doesTypeConformTo(TypeObject | TypeNull | TypeUndefined)) {
165 String ctorName = leastCommonAncestor();
166
167 if (doesTypeConformTo(TypeObject))
168 return ctorName;
169 if (doesTypeConformTo(TypeObject | TypeNull | TypeUndefined))
170 return ctorName + '?';
171 }
172
173 // 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.
174 // Therefore, more specific types must be checked first.
175
176 if (doesTypeConformTo(TypeFunction))
177 return "Function"_s;
178 if (doesTypeConformTo(TypeUndefined))
179 return "Undefined"_s;
180 if (doesTypeConformTo(TypeNull))
181 return "Null"_s;
182 if (doesTypeConformTo(TypeBoolean))
183 return "Boolean"_s;
184 if (doesTypeConformTo(TypeAnyInt))
185 return "Integer"_s;
186 if (doesTypeConformTo(TypeNumber | TypeAnyInt))
187 return "Number"_s;
188 if (doesTypeConformTo(TypeString))
189 return "String"_s;
190 if (doesTypeConformTo(TypeSymbol))
191 return "Symbol"_s;
192
193 if (doesTypeConformTo(TypeNull | TypeUndefined))
194 return "(?)"_s;
195
196 if (doesTypeConformTo(TypeFunction | TypeNull | TypeUndefined))
197 return "Function?"_s;
198 if (doesTypeConformTo(TypeBoolean | TypeNull | TypeUndefined))
199 return "Boolean?"_s;
200 if (doesTypeConformTo(TypeAnyInt | TypeNull | TypeUndefined))
201 return "Integer?"_s;
202 if (doesTypeConformTo(TypeNumber | TypeAnyInt | TypeNull | TypeUndefined))
203 return "Number?"_s;
204 if (doesTypeConformTo(TypeString | TypeNull | TypeUndefined))
205 return "String?"_s;
206 if (doesTypeConformTo(TypeSymbol | TypeNull | TypeUndefined))
207 return "Symbol?"_s;
208
209 if (doesTypeConformTo(TypeObject | TypeFunction | TypeString))
210 return "Object"_s;
211 if (doesTypeConformTo(TypeObject | TypeFunction | TypeString | TypeNull | TypeUndefined))
212 return "Object?"_s;
213
214 return "(many)"_s;
215}
216
217String TypeSet::leastCommonAncestor() const
218{
219 return StructureShape::leastCommonAncestor(m_structureHistory);
220}
221
222Ref<JSON::ArrayOf<Inspector::Protocol::Runtime::StructureDescription>> TypeSet::allStructureRepresentations() const
223{
224 auto description = JSON::ArrayOf<Inspector::Protocol::Runtime::StructureDescription>::create();
225
226 for (auto& shape : m_structureHistory)
227 description->addItem(shape->inspectorRepresentation());
228
229 return description;
230}
231
232Ref<Inspector::Protocol::Runtime::TypeSet> TypeSet::inspectorTypeSet() const
233{
234 return Inspector::Protocol::Runtime::TypeSet::create()
235 .setIsFunction((m_seenTypes & TypeFunction) != TypeNothing)
236 .setIsUndefined((m_seenTypes & TypeUndefined) != TypeNothing)
237 .setIsNull((m_seenTypes & TypeNull) != TypeNothing)
238 .setIsBoolean((m_seenTypes & TypeBoolean) != TypeNothing)
239 .setIsInteger((m_seenTypes & TypeAnyInt) != TypeNothing)
240 .setIsNumber((m_seenTypes & TypeNumber) != TypeNothing)
241 .setIsString((m_seenTypes & TypeString) != TypeNothing)
242 .setIsObject((m_seenTypes & TypeObject) != TypeNothing)
243 .setIsSymbol((m_seenTypes & TypeSymbol) != TypeNothing)
244 .release();
245}
246
247String TypeSet::toJSONString() const
248{
249 // This returns a JSON string representing an Object with the following properties:
250 // displayTypeName: 'String'
251 // primitiveTypeNames: 'Array<String>'
252 // structures: 'Array<JSON<StructureShape>>'
253
254 StringBuilder json;
255 json.append('{');
256
257 json.appendLiteral("\"displayTypeName\":");
258 json.appendQuotedJSONString(displayName());
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 & TypeAnyInt) {
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
323StructureShape::StructureShape()
324 : m_final(false)
325 , m_isInDictionaryMode(false)
326 , m_proto(nullptr)
327 , m_propertyHash(nullptr)
328{
329}
330
331void StructureShape::markAsFinal()
332{
333 ASSERT(!m_final);
334 m_final = true;
335}
336
337void StructureShape::addProperty(UniquedStringImpl& uid)
338{
339 ASSERT(!m_final);
340 m_fields.add(&uid);
341}
342
343String 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
369String StructureShape::leastCommonAncestor(const Vector<Ref<StructureShape>>& shapes)
370{
371 if (shapes.isEmpty())
372 return emptyString();
373
374 StructureShape* origin = shapes[0].ptr();
375 for (size_t i = 1; i < shapes.size(); i++) {
376 bool foundLUB = false;
377 while (!foundLUB) {
378 StructureShape* check = shapes[i].ptr();
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.get();
386 }
387 if (!foundLUB) {
388 // This is unlikely to happen, because we usually bottom out at "Object", but there are some sets of Objects
389 // that may cause this behavior. We fall back to "Object" because it's our version of Top.
390 if (!origin->m_proto)
391 return "Object"_s;
392 origin = origin->m_proto.get();
393 }
394 }
395
396 if (origin->m_constructorName == "Object")
397 break;
398 }
399
400 return origin->m_constructorName;
401}
402
403String StructureShape::stringRepresentation()
404{
405 StringBuilder representation;
406 RefPtr<StructureShape> curShape = this;
407
408 representation.append('{');
409 while (curShape) {
410 for (auto it = curShape->m_fields.begin(), end = curShape->m_fields.end(); it != end; ++it) {
411 String prop((*it).get());
412 representation.append(prop);
413 representation.appendLiteral(", ");
414 }
415
416 if (curShape->m_proto) {
417 representation.appendLiteral("__proto__ [");
418 representation.append(curShape->m_proto->m_constructorName);
419 representation.appendLiteral("], ");
420 }
421
422 curShape = curShape->m_proto;
423 }
424
425 if (representation.length() >= 3)
426 representation.resize(representation.length() - 2);
427
428 representation.append('}');
429
430 return representation.toString();
431}
432
433String StructureShape::toJSONString() const
434{
435 // This returns a JSON string representing an Object with the following properties:
436 // constructorName: 'String'
437 // fields: 'Array<String>'
438 // optionalFields: 'Array<String>'
439 // proto: 'JSON<StructureShape> | null'
440
441 StringBuilder json;
442 json.append('{');
443
444 json.appendLiteral("\"constructorName\":");
445 json.appendQuotedJSONString(m_constructorName);
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.appendQuotedJSONString(fieldName);
465 }
466 json.append(']');
467 json.append(',');
468
469 json.appendLiteral("\"optionalFields\":");
470 json.append('[');
471 hasAnItem = false;
472 for (auto it = m_optionalFields.begin(), end = m_optionalFields.end(); it != end; ++it) {
473 if (hasAnItem)
474 json.append(',');
475 hasAnItem = true;
476
477 String fieldName((*it).get());
478 json.appendQuotedJSONString(fieldName);
479 }
480 json.append(']');
481 json.append(',');
482
483 json.appendLiteral("\"proto\":");
484 if (m_proto)
485 json.append(m_proto->toJSONString());
486 else
487 json.appendLiteral("null");
488
489 json.append('}');
490
491 return json.toString();
492}
493
494Ref<Inspector::Protocol::Runtime::StructureDescription> StructureShape::inspectorRepresentation()
495{
496 auto base = Inspector::Protocol::Runtime::StructureDescription::create().release();
497 Ref<Inspector::Protocol::Runtime::StructureDescription> currentObject = base.copyRef();
498 RefPtr<StructureShape> currentShape(this);
499
500 while (currentShape) {
501 auto fields = JSON::ArrayOf<String>::create();
502 auto optionalFields = JSON::ArrayOf<String>::create();
503 for (auto field : currentShape->m_fields)
504 fields->addItem(field.get());
505 for (auto field : currentShape->m_optionalFields)
506 optionalFields->addItem(field.get());
507
508 currentObject->setFields(&fields.get());
509 currentObject->setOptionalFields(&optionalFields.get());
510 currentObject->setConstructorName(currentShape->m_constructorName);
511 currentObject->setIsImprecise(currentShape->m_isInDictionaryMode);
512
513 if (currentShape->m_proto) {
514 auto nextObject = Inspector::Protocol::Runtime::StructureDescription::create().release();
515 currentObject->setPrototypeStructure(&nextObject.get());
516 currentObject = WTFMove(nextObject);
517 }
518
519 currentShape = currentShape->m_proto;
520 }
521
522 return base;
523}
524
525bool StructureShape::hasSamePrototypeChain(const StructureShape& otherRef)
526{
527 const StructureShape* self = this;
528 const StructureShape* other = &otherRef;
529 while (self && other) {
530 if (self->m_constructorName != other->m_constructorName)
531 return false;
532 self = self->m_proto.get();
533 other = other->m_proto.get();
534 }
535
536 return !self && !other;
537}
538
539Ref<StructureShape> StructureShape::merge(Ref<StructureShape>&& a, Ref<StructureShape>&& b)
540{
541 ASSERT(a->hasSamePrototypeChain(b.get()));
542
543 auto merged = StructureShape::create();
544 for (auto field : a->m_fields) {
545 if (b->m_fields.contains(field))
546 merged->m_fields.add(field);
547 else
548 merged->m_optionalFields.add(field);
549 }
550
551 for (auto field : b->m_fields) {
552 if (!merged->m_fields.contains(field)) {
553 auto addResult = merged->m_optionalFields.add(field);
554 ASSERT_UNUSED(addResult, addResult.isNewEntry);
555 }
556 }
557
558 for (auto field : a->m_optionalFields)
559 merged->m_optionalFields.add(field);
560 for (auto field : b->m_optionalFields)
561 merged->m_optionalFields.add(field);
562
563 ASSERT(a->m_constructorName == b->m_constructorName);
564 merged->setConstructorName(a->m_constructorName);
565
566 if (a->m_proto) {
567 RELEASE_ASSERT(b->m_proto);
568 merged->setProto(StructureShape::merge(*a->m_proto, *b->m_proto));
569 }
570
571 merged->markAsFinal();
572
573 return merged;
574}
575
576void StructureShape::enterDictionaryMode()
577{
578 m_isInDictionaryMode = true;
579}
580
581} // namespace JSC
582