Remove excessive headers from JavaScriptCore
[WebKit-https.git] / 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 "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)
45 {
46     m_seenTypes = m_seenTypes | type;
47
48     if (structure && passedNewShape && !runtimeTypeIsPrimitive(type)) {
49         Ref<StructureShape> newShape = passedNewShape.releaseNonNull();
50         if (!m_structureSet.contains(structure)) {
51             {
52                 ConcurrentJSLocker locker(m_lock);
53                 m_structureSet.add(structure);
54             }
55             // Make one more pass making sure that: 
56             // - We don't have two instances of the same shape. (Same shapes may have different Structures).
57             // - We don't have two shapes that share the same prototype chain. If these shapes share the same 
58             //   prototype chain, they will be merged into one shape.
59             String hash = newShape->propertyHash();
60             for (auto& seenShape : m_structureHistory) {
61                 if (seenShape->propertyHash() == hash)
62                     return;
63                 if (seenShape->hasSamePrototypeChain(newShape.get())) {
64                     seenShape = StructureShape::merge(seenShape.copyRef(), WTFMove(newShape));
65                     return;
66                 }
67             }
68
69             if (m_structureHistory.size() < 100) {
70                 m_structureHistory.append(WTFMove(newShape));
71                 return;
72             }
73             if (!m_isOverflown)
74                 m_isOverflown = true;
75         }
76     }
77 }
78
79 void TypeSet::invalidateCache()
80 {
81     ConcurrentJSLocker locker(m_lock);
82     auto keepMarkedStructuresFilter = [] (Structure* structure) -> bool { return Heap::isMarked(structure); };
83     m_structureSet.genericFilter(keepMarkedStructuresFilter);
84 }
85
86 String TypeSet::dumpTypes() const
87 {
88     if (m_seenTypes == TypeNothing)
89         return ASCIILiteral("(Unreached Statement)");
90
91     StringBuilder seen;
92
93     if (m_seenTypes & TypeFunction)
94         seen.appendLiteral("Function ");
95     if (m_seenTypes & TypeUndefined)
96         seen.appendLiteral("Undefined ");
97     if (m_seenTypes & TypeNull)
98         seen.appendLiteral("Null ");
99     if (m_seenTypes & TypeBoolean)
100         seen.appendLiteral("Boolean ");
101     if (m_seenTypes & TypeAnyInt)
102         seen.appendLiteral("AnyInt ");
103     if (m_seenTypes & TypeNumber)
104         seen.appendLiteral("Number ");
105     if (m_seenTypes & TypeString)
106         seen.appendLiteral("String ");
107     if (m_seenTypes & TypeObject)
108         seen.appendLiteral("Object ");
109     if (m_seenTypes & TypeSymbol)
110         seen.appendLiteral("Symbol ");
111
112     for (const auto& shape : m_structureHistory) {
113         seen.append(shape->m_constructorName);
114         seen.append(' ');
115     }
116
117     if (m_structureHistory.size()) 
118         seen.appendLiteral("\nStructures:[ ");
119     for (const auto& shape : m_structureHistory) {
120         seen.append(shape->stringRepresentation());
121         seen.append(' ');
122     }
123     if (m_structureHistory.size())
124         seen.append(']');
125
126     if (m_structureHistory.size()) {
127         seen.appendLiteral("\nLeast Common Ancestor: ");
128         seen.append(leastCommonAncestor());
129     }
130
131     return seen.toString();
132 }
133
134 bool TypeSet::doesTypeConformTo(RuntimeTypeMask test) const
135 {
136     // 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).
137     // We are <= to those types if ANDing with the bitstring doesn't zero out any of our bits.
138
139     // For example:
140
141     // 0b0110 (seen)
142     // 0b1111 (test)
143     // ------ (AND)
144     // 0b0110 == seen
145
146     // 0b0110 (seen)
147     // 0b0010 (test)
148     // ------ (AND)
149     // 0b0010 != seen
150
151     return m_seenTypes != TypeNothing && (m_seenTypes & test) == m_seenTypes;
152 }
153
154 String TypeSet::displayName() const
155 {
156     if (m_seenTypes == TypeNothing)
157         return emptyString();
158
159     if (m_structureHistory.size() && doesTypeConformTo(TypeObject | TypeNull | TypeUndefined)) {
160         String ctorName = leastCommonAncestor(); 
161
162         if (doesTypeConformTo(TypeObject))
163             return ctorName;
164         if (doesTypeConformTo(TypeObject | TypeNull | TypeUndefined))
165             return ctorName + '?';
166     }
167
168     // 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.
169     // Therefore, more specific types must be checked first.
170
171     if (doesTypeConformTo(TypeFunction))
172         return ASCIILiteral("Function");
173     if (doesTypeConformTo(TypeUndefined))
174         return ASCIILiteral("Undefined");
175     if (doesTypeConformTo(TypeNull))
176         return ASCIILiteral("Null");
177     if (doesTypeConformTo(TypeBoolean))
178         return ASCIILiteral("Boolean");
179     if (doesTypeConformTo(TypeAnyInt))
180         return ASCIILiteral("Integer");
181     if (doesTypeConformTo(TypeNumber | TypeAnyInt))
182         return ASCIILiteral("Number");
183     if (doesTypeConformTo(TypeString))
184         return ASCIILiteral("String");
185     if (doesTypeConformTo(TypeSymbol))
186         return ASCIILiteral("Symbol");
187
188     if (doesTypeConformTo(TypeNull | TypeUndefined))
189         return ASCIILiteral("(?)");
190
191     if (doesTypeConformTo(TypeFunction | TypeNull | TypeUndefined))
192         return ASCIILiteral("Function?");
193     if (doesTypeConformTo(TypeBoolean | TypeNull | TypeUndefined))
194         return ASCIILiteral("Boolean?");
195     if (doesTypeConformTo(TypeAnyInt | TypeNull | TypeUndefined))
196         return ASCIILiteral("Integer?");
197     if (doesTypeConformTo(TypeNumber | TypeAnyInt | TypeNull | TypeUndefined))
198         return ASCIILiteral("Number?");
199     if (doesTypeConformTo(TypeString | TypeNull | TypeUndefined))
200         return ASCIILiteral("String?");
201     if (doesTypeConformTo(TypeSymbol | TypeNull | TypeUndefined))
202         return ASCIILiteral("Symbol?");
203    
204     if (doesTypeConformTo(TypeObject | TypeFunction | TypeString))
205         return ASCIILiteral("Object");
206     if (doesTypeConformTo(TypeObject | TypeFunction | TypeString | TypeNull | TypeUndefined))
207         return ASCIILiteral("Object?");
208
209     return ASCIILiteral("(many)");
210 }
211
212 String TypeSet::leastCommonAncestor() const
213 {
214     return StructureShape::leastCommonAncestor(m_structureHistory);
215 }
216
217 Ref<Inspector::Protocol::Array<Inspector::Protocol::Runtime::StructureDescription>> TypeSet::allStructureRepresentations() const
218 {
219     auto description = Inspector::Protocol::Array<Inspector::Protocol::Runtime::StructureDescription>::create();
220
221     for (auto& shape : m_structureHistory)
222         description->addItem(shape->inspectorRepresentation());
223
224     return description;
225 }
226
227 Ref<Inspector::Protocol::Runtime::TypeSet> TypeSet::inspectorTypeSet() const
228 {
229     return Inspector::Protocol::Runtime::TypeSet::create()
230         .setIsFunction((m_seenTypes & TypeFunction) != TypeNothing)
231         .setIsUndefined((m_seenTypes & TypeUndefined) != TypeNothing)
232         .setIsNull((m_seenTypes & TypeNull) != TypeNothing)
233         .setIsBoolean((m_seenTypes & TypeBoolean) != TypeNothing)
234         .setIsInteger((m_seenTypes & TypeAnyInt) != TypeNothing)
235         .setIsNumber((m_seenTypes & TypeNumber) != TypeNothing)
236         .setIsString((m_seenTypes & TypeString) != TypeNothing)
237         .setIsObject((m_seenTypes & TypeObject) != TypeNothing)
238         .setIsSymbol((m_seenTypes & TypeSymbol) != TypeNothing)
239         .release();
240 }
241
242 String TypeSet::toJSONString() const
243 {
244     // This returns a JSON string representing an Object with the following properties:
245     //     displayTypeName: 'String'
246     //     primitiveTypeNames: 'Array<String>'
247     //     structures: 'Array<JSON<StructureShape>>'
248
249     StringBuilder json;
250     json.append('{');
251
252     json.appendLiteral("\"displayTypeName\":");
253     json.append('"');
254     json.append(displayName());
255     json.append('"');
256     json.append(',');
257
258     json.appendLiteral("\"primitiveTypeNames\":");
259     json.append('[');
260     bool hasAnItem = false;
261     if (m_seenTypes & TypeUndefined) {
262         hasAnItem = true;
263         json.appendLiteral("\"Undefined\"");
264     }
265     if (m_seenTypes & TypeNull) {
266         if (hasAnItem)
267             json.append(',');
268         hasAnItem = true;
269         json.appendLiteral("\"Null\"");
270     }
271     if (m_seenTypes & TypeBoolean) {
272         if (hasAnItem)
273             json.append(',');
274         hasAnItem = true;
275         json.appendLiteral("\"Boolean\"");
276     }
277     if (m_seenTypes & TypeAnyInt) {
278         if (hasAnItem)
279             json.append(',');
280         hasAnItem = true;
281         json.appendLiteral("\"Integer\"");
282     }
283     if (m_seenTypes & TypeNumber) {
284         if (hasAnItem)
285             json.append(',');
286         hasAnItem = true;
287         json.appendLiteral("\"Number\"");
288     }
289     if (m_seenTypes & TypeString) {
290         if (hasAnItem)
291             json.append(',');
292         hasAnItem = true;
293         json.appendLiteral("\"String\"");
294     }
295     if (m_seenTypes & TypeSymbol) {
296         if (hasAnItem)
297             json.append(',');
298         hasAnItem = true;
299         json.appendLiteral("\"Symbol\"");
300     }
301     json.append(']');
302
303     json.append(',');
304
305     json.appendLiteral("\"structures\":");
306     json.append('[');
307     hasAnItem = false;
308     for (size_t i = 0; i < m_structureHistory.size(); i++) {
309         if (hasAnItem)
310             json.append(',');
311         hasAnItem = true;
312         json.append(m_structureHistory[i]->toJSONString());
313     }
314     json.append(']');
315
316     json.append('}');
317     return json.toString();
318 }
319
320 StructureShape::StructureShape()
321     : m_proto(nullptr)
322     , m_propertyHash(nullptr)
323     , m_final(false)
324     , m_isInDictionaryMode(false)
325 {
326 }
327
328 void StructureShape::markAsFinal()
329 {
330     ASSERT(!m_final);
331     m_final = true;
332 }
333
334 void StructureShape::addProperty(UniquedStringImpl& uid)
335 {
336     ASSERT(!m_final);
337     m_fields.add(&uid);
338 }
339
340 String StructureShape::propertyHash()
341 {
342     ASSERT(m_final);
343     if (m_propertyHash)
344         return *m_propertyHash;
345
346     StringBuilder builder;
347     builder.append(':');
348     builder.append(m_constructorName);
349     builder.append(':');
350     for (auto& key : m_fields) {
351         String property = key.get();
352         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.
353         builder.append(property);
354     }
355
356     if (m_proto) {
357         builder.append(':');
358         builder.appendLiteral("__proto__");
359         builder.append(m_proto->propertyHash());
360     }
361
362     m_propertyHash = std::make_unique<String>(builder.toString());
363     return *m_propertyHash;
364 }
365
366 String StructureShape::leastCommonAncestor(const Vector<Ref<StructureShape>>& shapes)
367 {
368     if (shapes.isEmpty())
369         return emptyString();
370
371     StructureShape* origin = shapes[0].ptr();
372     for (size_t i = 1; i < shapes.size(); i++) {
373         bool foundLUB = false;
374         while (!foundLUB) {
375             StructureShape* check = shapes[i].ptr();
376             String curCtorName = origin->m_constructorName;
377             while (check) {
378                 if (check->m_constructorName == curCtorName) {
379                     foundLUB = true;
380                     break;
381                 }
382                 check = check->m_proto.get();
383             }
384             if (!foundLUB) {
385                 // This is unlikely to happen, because we usually bottom out at "Object", but there are some sets of Objects
386                 // that may cause this behavior. We fall back to "Object" because it's our version of Top.
387                 if (!origin->m_proto)
388                     return ASCIILiteral("Object");
389                 origin = origin->m_proto.get();
390             }
391         }
392
393         if (origin->m_constructorName == "Object")
394             break;
395     }
396
397     return origin->m_constructorName;
398 }
399
400 String StructureShape::stringRepresentation()
401 {
402     StringBuilder representation;
403     RefPtr<StructureShape> curShape = this;
404
405     representation.append('{');
406     while (curShape) {
407         for (auto it = curShape->m_fields.begin(), end = curShape->m_fields.end(); it != end; ++it) {
408             String prop((*it).get());
409             representation.append(prop);
410             representation.appendLiteral(", ");
411         }
412
413         if (curShape->m_proto) {
414             representation.appendLiteral("__proto__ [");
415             representation.append(curShape->m_proto->m_constructorName);
416             representation.appendLiteral("], ");
417         }
418
419         curShape = curShape->m_proto;
420     }
421
422     if (representation.length() >= 3)
423         representation.resize(representation.length() - 2);
424
425     representation.append('}');
426
427     return representation.toString();
428 }
429
430 String StructureShape::toJSONString() const
431 {
432     // This returns a JSON string representing an Object with the following properties:
433     //     constructorName: 'String'
434     //     fields: 'Array<String>'
435     //     optionalFields: 'Array<String>'
436     //     proto: 'JSON<StructureShape> | null'
437
438     StringBuilder json;
439     json.append('{');
440
441     json.appendLiteral("\"constructorName\":");
442     json.append('"');
443     json.append(m_constructorName);
444     json.append('"');
445     json.append(',');
446
447     json.appendLiteral("\"isInDictionaryMode\":");
448     if (m_isInDictionaryMode)
449         json.appendLiteral("true");
450     else
451         json.appendLiteral("false");
452     json.append(',');
453
454     json.appendLiteral("\"fields\":");
455     json.append('[');
456     bool hasAnItem = false;
457     for (auto it = m_fields.begin(), end = m_fields.end(); it != end; ++it) {
458         if (hasAnItem)
459             json.append(',');
460         hasAnItem = true;
461
462         String fieldName((*it).get());
463         json.append('"');
464         json.append(fieldName);
465         json.append('"');
466     }
467     json.append(']');
468     json.append(',');
469
470     json.appendLiteral("\"optionalFields\":");
471     json.append('[');
472     hasAnItem = false;
473     for (auto it = m_optionalFields.begin(), end = m_optionalFields.end(); it != end; ++it) {
474         if (hasAnItem)
475             json.append(',');
476         hasAnItem = true;
477
478         String fieldName((*it).get());
479         json.append('"');
480         json.append(fieldName);
481         json.append('"');
482     }
483     json.append(']');
484     json.append(',');
485
486     json.appendLiteral("\"proto\":");
487     if (m_proto)
488         json.append(m_proto->toJSONString());
489     else
490         json.appendLiteral("null");
491
492     json.append('}');
493
494     return json.toString();
495 }
496
497 Ref<Inspector::Protocol::Runtime::StructureDescription> StructureShape::inspectorRepresentation()
498 {
499     auto base = Inspector::Protocol::Runtime::StructureDescription::create().release();
500     Ref<Inspector::Protocol::Runtime::StructureDescription> currentObject = base.copyRef();
501     RefPtr<StructureShape> currentShape(this);
502
503     while (currentShape) {
504         auto fields = Inspector::Protocol::Array<String>::create();
505         auto optionalFields = Inspector::Protocol::Array<String>::create();
506         for (auto field : currentShape->m_fields)
507             fields->addItem(field.get());
508         for (auto field : currentShape->m_optionalFields)
509             optionalFields->addItem(field.get());
510
511         currentObject->setFields(&fields.get());
512         currentObject->setOptionalFields(&optionalFields.get());
513         currentObject->setConstructorName(currentShape->m_constructorName);
514         currentObject->setIsImprecise(currentShape->m_isInDictionaryMode);
515
516         if (currentShape->m_proto) {
517             auto nextObject = Inspector::Protocol::Runtime::StructureDescription::create().release();
518             currentObject->setPrototypeStructure(&nextObject.get());
519             currentObject = WTFMove(nextObject);
520         }
521
522         currentShape = currentShape->m_proto;
523     }
524
525     return base;
526 }
527
528 bool StructureShape::hasSamePrototypeChain(const StructureShape& otherRef)
529 {
530     const StructureShape* self = this;
531     const StructureShape* other = &otherRef;
532     while (self && other) {
533         if (self->m_constructorName != other->m_constructorName)
534             return false;
535         self = self->m_proto.get();
536         other = other->m_proto.get();
537     }
538
539     return !self && !other;
540 }
541
542 Ref<StructureShape> StructureShape::merge(Ref<StructureShape>&& a, Ref<StructureShape>&& b)
543 {
544     ASSERT(a->hasSamePrototypeChain(b.get()));
545
546     auto merged = StructureShape::create();
547     for (auto field : a->m_fields) {
548         if (b->m_fields.contains(field))
549             merged->m_fields.add(field);
550         else
551             merged->m_optionalFields.add(field);
552     }
553
554     for (auto field : b->m_fields) {
555         if (!merged->m_fields.contains(field)) {
556             auto addResult = merged->m_optionalFields.add(field);
557             ASSERT_UNUSED(addResult, addResult.isNewEntry);
558         }
559     }
560
561     for (auto field : a->m_optionalFields)
562         merged->m_optionalFields.add(field);
563     for (auto field : b->m_optionalFields)
564         merged->m_optionalFields.add(field);
565
566     ASSERT(a->m_constructorName == b->m_constructorName);
567     merged->setConstructorName(a->m_constructorName);
568
569     if (a->m_proto) {
570         RELEASE_ASSERT(b->m_proto);
571         merged->setProto(StructureShape::merge(*a->m_proto, *b->m_proto));
572     }
573
574     merged->markAsFinal();
575
576     return merged;
577 }
578
579 void StructureShape::enterDictionaryMode()
580 {
581     m_isInDictionaryMode = true;
582 }
583
584 } // namespace JSC