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 | |
36 | namespace JSC { |
37 | |
38 | TypeSet::TypeSet() |
39 | : m_isOverflown(false) |
40 | , m_seenTypes(TypeNothing) |
41 | { |
42 | } |
43 | |
44 | void 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 | |
82 | void 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 | |
91 | String 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 | |
139 | bool 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 | |
159 | String 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 | |
217 | String TypeSet::leastCommonAncestor() const |
218 | { |
219 | return StructureShape::leastCommonAncestor(m_structureHistory); |
220 | } |
221 | |
222 | Ref<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 | |
232 | Ref<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 | |
247 | String 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 | |
323 | StructureShape::StructureShape() |
324 | : m_final(false) |
325 | , m_isInDictionaryMode(false) |
326 | , m_proto(nullptr) |
327 | , m_propertyHash(nullptr) |
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<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 | |
403 | String 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 | |
433 | String 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 | |
494 | Ref<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 | |
525 | bool 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 | |
539 | Ref<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 | |
576 | void StructureShape::enterDictionaryMode() |
577 | { |
578 | m_isInDictionaryMode = true; |
579 | } |
580 | |
581 | } // namespace JSC |
582 | |