SamplingProfiler::stackTracesAsJSON() should escape strings.
[WebKit-https.git] / Source / JavaScriptCore / runtime / TypeSet.cpp
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()
83 {
84     ConcurrentJSLocker locker(m_lock);
85     auto keepMarkedStructuresFilter = [] (Structure* structure) -> bool { return Heap::isMarked(structure); };
86     m_structureSet.genericFilter(keepMarkedStructuresFilter);
87 }
88
89 String TypeSet::dumpTypes() const
90 {
91     if (m_seenTypes == TypeNothing)
92         return "(Unreached Statement)"_s;
93
94     StringBuilder seen;
95
96     if (m_seenTypes & TypeFunction)
97         seen.appendLiteral("Function ");
98     if (m_seenTypes & TypeUndefined)
99         seen.appendLiteral("Undefined ");
100     if (m_seenTypes & TypeNull)
101         seen.appendLiteral("Null ");
102     if (m_seenTypes & TypeBoolean)
103         seen.appendLiteral("Boolean ");
104     if (m_seenTypes & TypeAnyInt)
105         seen.appendLiteral("AnyInt ");
106     if (m_seenTypes & TypeNumber)
107         seen.appendLiteral("Number ");
108     if (m_seenTypes & TypeString)
109         seen.appendLiteral("String ");
110     if (m_seenTypes & TypeObject)
111         seen.appendLiteral("Object ");
112     if (m_seenTypes & TypeSymbol)
113         seen.appendLiteral("Symbol ");
114
115     for (const auto& shape : m_structureHistory) {
116         seen.append(shape->m_constructorName);
117         seen.append(' ');
118     }
119
120     if (m_structureHistory.size()) 
121         seen.appendLiteral("\nStructures:[ ");
122     for (const auto& shape : m_structureHistory) {
123         seen.append(shape->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 "Function"_s;
176     if (doesTypeConformTo(TypeUndefined))
177         return "Undefined"_s;
178     if (doesTypeConformTo(TypeNull))
179         return "Null"_s;
180     if (doesTypeConformTo(TypeBoolean))
181         return "Boolean"_s;
182     if (doesTypeConformTo(TypeAnyInt))
183         return "Integer"_s;
184     if (doesTypeConformTo(TypeNumber | TypeAnyInt))
185         return "Number"_s;
186     if (doesTypeConformTo(TypeString))
187         return "String"_s;
188     if (doesTypeConformTo(TypeSymbol))
189         return "Symbol"_s;
190
191     if (doesTypeConformTo(TypeNull | TypeUndefined))
192         return "(?)"_s;
193
194     if (doesTypeConformTo(TypeFunction | TypeNull | TypeUndefined))
195         return "Function?"_s;
196     if (doesTypeConformTo(TypeBoolean | TypeNull | TypeUndefined))
197         return "Boolean?"_s;
198     if (doesTypeConformTo(TypeAnyInt | TypeNull | TypeUndefined))
199         return "Integer?"_s;
200     if (doesTypeConformTo(TypeNumber | TypeAnyInt | TypeNull | TypeUndefined))
201         return "Number?"_s;
202     if (doesTypeConformTo(TypeString | TypeNull | TypeUndefined))
203         return "String?"_s;
204     if (doesTypeConformTo(TypeSymbol | TypeNull | TypeUndefined))
205         return "Symbol?"_s;
206    
207     if (doesTypeConformTo(TypeObject | TypeFunction | TypeString))
208         return "Object"_s;
209     if (doesTypeConformTo(TypeObject | TypeFunction | TypeString | TypeNull | TypeUndefined))
210         return "Object?"_s;
211
212     return "(many)"_s;
213 }
214
215 String TypeSet::leastCommonAncestor() const
216 {
217     return StructureShape::leastCommonAncestor(m_structureHistory);
218 }
219
220 Ref<JSON::ArrayOf<Inspector::Protocol::Runtime::StructureDescription>> TypeSet::allStructureRepresentations() const
221 {
222     auto description = JSON::ArrayOf<Inspector::Protocol::Runtime::StructureDescription>::create();
223
224     for (auto& shape : m_structureHistory)
225         description->addItem(shape->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 & TypeAnyInt) != 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.appendQuotedJSONString(displayName());
257     json.append(',');
258
259     json.appendLiteral("\"primitiveTypeNames\":");
260     json.append('[');
261     bool hasAnItem = false;
262     if (m_seenTypes & TypeUndefined) {
263         hasAnItem = true;
264         json.appendLiteral("\"Undefined\"");
265     }
266     if (m_seenTypes & TypeNull) {
267         if (hasAnItem)
268             json.append(',');
269         hasAnItem = true;
270         json.appendLiteral("\"Null\"");
271     }
272     if (m_seenTypes & TypeBoolean) {
273         if (hasAnItem)
274             json.append(',');
275         hasAnItem = true;
276         json.appendLiteral("\"Boolean\"");
277     }
278     if (m_seenTypes & TypeAnyInt) {
279         if (hasAnItem)
280             json.append(',');
281         hasAnItem = true;
282         json.appendLiteral("\"Integer\"");
283     }
284     if (m_seenTypes & TypeNumber) {
285         if (hasAnItem)
286             json.append(',');
287         hasAnItem = true;
288         json.appendLiteral("\"Number\"");
289     }
290     if (m_seenTypes & TypeString) {
291         if (hasAnItem)
292             json.append(',');
293         hasAnItem = true;
294         json.appendLiteral("\"String\"");
295     }
296     if (m_seenTypes & TypeSymbol) {
297         if (hasAnItem)
298             json.append(',');
299         hasAnItem = true;
300         json.appendLiteral("\"Symbol\"");
301     }
302     json.append(']');
303
304     json.append(',');
305
306     json.appendLiteral("\"structures\":");
307     json.append('[');
308     hasAnItem = false;
309     for (size_t i = 0; i < m_structureHistory.size(); i++) {
310         if (hasAnItem)
311             json.append(',');
312         hasAnItem = true;
313         json.append(m_structureHistory[i]->toJSONString());
314     }
315     json.append(']');
316
317     json.append('}');
318     return json.toString();
319 }
320
321 StructureShape::StructureShape()
322     : m_proto(nullptr)
323     , m_propertyHash(nullptr)
324     , m_final(false)
325     , m_isInDictionaryMode(false)
326 {
327 }
328
329 void StructureShape::markAsFinal()
330 {
331     ASSERT(!m_final);
332     m_final = true;
333 }
334
335 void StructureShape::addProperty(UniquedStringImpl& uid)
336 {
337     ASSERT(!m_final);
338     m_fields.add(&uid);
339 }
340
341 String StructureShape::propertyHash()
342 {
343     ASSERT(m_final);
344     if (m_propertyHash)
345         return *m_propertyHash;
346
347     StringBuilder builder;
348     builder.append(':');
349     builder.append(m_constructorName);
350     builder.append(':');
351     for (auto& key : m_fields) {
352         String property = key.get();
353         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.
354         builder.append(property);
355     }
356
357     if (m_proto) {
358         builder.append(':');
359         builder.appendLiteral("__proto__");
360         builder.append(m_proto->propertyHash());
361     }
362
363     m_propertyHash = std::make_unique<String>(builder.toString());
364     return *m_propertyHash;
365 }
366
367 String StructureShape::leastCommonAncestor(const Vector<Ref<StructureShape>>& shapes)
368 {
369     if (shapes.isEmpty())
370         return emptyString();
371
372     StructureShape* origin = shapes[0].ptr();
373     for (size_t i = 1; i < shapes.size(); i++) {
374         bool foundLUB = false;
375         while (!foundLUB) {
376             StructureShape* check = shapes[i].ptr();
377             String curCtorName = origin->m_constructorName;
378             while (check) {
379                 if (check->m_constructorName == curCtorName) {
380                     foundLUB = true;
381                     break;
382                 }
383                 check = check->m_proto.get();
384             }
385             if (!foundLUB) {
386                 // This is unlikely to happen, because we usually bottom out at "Object", but there are some sets of Objects
387                 // that may cause this behavior. We fall back to "Object" because it's our version of Top.
388                 if (!origin->m_proto)
389                     return "Object"_s;
390                 origin = origin->m_proto.get();
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.appendQuotedJSONString(m_constructorName);
444     json.append(',');
445
446     json.appendLiteral("\"isInDictionaryMode\":");
447     if (m_isInDictionaryMode)
448         json.appendLiteral("true");
449     else
450         json.appendLiteral("false");
451     json.append(',');
452
453     json.appendLiteral("\"fields\":");
454     json.append('[');
455     bool hasAnItem = false;
456     for (auto it = m_fields.begin(), end = m_fields.end(); it != end; ++it) {
457         if (hasAnItem)
458             json.append(',');
459         hasAnItem = true;
460
461         String fieldName((*it).get());
462         json.appendQuotedJSONString(fieldName);
463     }
464     json.append(']');
465     json.append(',');
466
467     json.appendLiteral("\"optionalFields\":");
468     json.append('[');
469     hasAnItem = false;
470     for (auto it = m_optionalFields.begin(), end = m_optionalFields.end(); it != end; ++it) {
471         if (hasAnItem)
472             json.append(',');
473         hasAnItem = true;
474
475         String fieldName((*it).get());
476         json.appendQuotedJSONString(fieldName);
477     }
478     json.append(']');
479     json.append(',');
480
481     json.appendLiteral("\"proto\":");
482     if (m_proto)
483         json.append(m_proto->toJSONString());
484     else
485         json.appendLiteral("null");
486
487     json.append('}');
488
489     return json.toString();
490 }
491
492 Ref<Inspector::Protocol::Runtime::StructureDescription> StructureShape::inspectorRepresentation()
493 {
494     auto base = Inspector::Protocol::Runtime::StructureDescription::create().release();
495     Ref<Inspector::Protocol::Runtime::StructureDescription> currentObject = base.copyRef();
496     RefPtr<StructureShape> currentShape(this);
497
498     while (currentShape) {
499         auto fields = JSON::ArrayOf<String>::create();
500         auto optionalFields = JSON::ArrayOf<String>::create();
501         for (auto field : currentShape->m_fields)
502             fields->addItem(field.get());
503         for (auto field : currentShape->m_optionalFields)
504             optionalFields->addItem(field.get());
505
506         currentObject->setFields(&fields.get());
507         currentObject->setOptionalFields(&optionalFields.get());
508         currentObject->setConstructorName(currentShape->m_constructorName);
509         currentObject->setIsImprecise(currentShape->m_isInDictionaryMode);
510
511         if (currentShape->m_proto) {
512             auto nextObject = Inspector::Protocol::Runtime::StructureDescription::create().release();
513             currentObject->setPrototypeStructure(&nextObject.get());
514             currentObject = WTFMove(nextObject);
515         }
516
517         currentShape = currentShape->m_proto;
518     }
519
520     return base;
521 }
522
523 bool StructureShape::hasSamePrototypeChain(const StructureShape& otherRef)
524 {
525     const StructureShape* self = this;
526     const StructureShape* other = &otherRef;
527     while (self && other) {
528         if (self->m_constructorName != other->m_constructorName)
529             return false;
530         self = self->m_proto.get();
531         other = other->m_proto.get();
532     }
533
534     return !self && !other;
535 }
536
537 Ref<StructureShape> StructureShape::merge(Ref<StructureShape>&& a, Ref<StructureShape>&& b)
538 {
539     ASSERT(a->hasSamePrototypeChain(b.get()));
540
541     auto merged = StructureShape::create();
542     for (auto field : a->m_fields) {
543         if (b->m_fields.contains(field))
544             merged->m_fields.add(field);
545         else
546             merged->m_optionalFields.add(field);
547     }
548
549     for (auto field : b->m_fields) {
550         if (!merged->m_fields.contains(field)) {
551             auto addResult = merged->m_optionalFields.add(field);
552             ASSERT_UNUSED(addResult, addResult.isNewEntry);
553         }
554     }
555
556     for (auto field : a->m_optionalFields)
557         merged->m_optionalFields.add(field);
558     for (auto field : b->m_optionalFields)
559         merged->m_optionalFields.add(field);
560
561     ASSERT(a->m_constructorName == b->m_constructorName);
562     merged->setConstructorName(a->m_constructorName);
563
564     if (a->m_proto) {
565         RELEASE_ASSERT(b->m_proto);
566         merged->setProto(StructureShape::merge(*a->m_proto, *b->m_proto));
567     }
568
569     merged->markAsFinal();
570
571     return merged;
572 }
573
574 void StructureShape::enterDictionaryMode()
575 {
576     m_isInDictionaryMode = true;
577 }
578
579 } // namespace JSC