a5ec952d77b1699f8ffded014fb0b18f3452cc6d
[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 "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