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