1/*
2 * Copyright (C) 2015-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 "ObjectPropertyConditionSet.h"
28
29#include "JSCInlines.h"
30#include <wtf/ListDump.h>
31
32namespace JSC {
33
34ObjectPropertyCondition ObjectPropertyConditionSet::forObject(JSObject* object) const
35{
36 for (const ObjectPropertyCondition& condition : *this) {
37 if (condition.object() == object)
38 return condition;
39 }
40 return ObjectPropertyCondition();
41}
42
43ObjectPropertyCondition ObjectPropertyConditionSet::forConditionKind(
44 PropertyCondition::Kind kind) const
45{
46 for (const ObjectPropertyCondition& condition : *this) {
47 if (condition.kind() == kind)
48 return condition;
49 }
50 return ObjectPropertyCondition();
51}
52
53unsigned ObjectPropertyConditionSet::numberOfConditionsWithKind(PropertyCondition::Kind kind) const
54{
55 unsigned result = 0;
56 for (const ObjectPropertyCondition& condition : *this) {
57 if (condition.kind() == kind)
58 result++;
59 }
60 return result;
61}
62
63bool ObjectPropertyConditionSet::hasOneSlotBaseCondition() const
64{
65 bool sawBase = false;
66 for (const ObjectPropertyCondition& condition : *this) {
67 switch (condition.kind()) {
68 case PropertyCondition::Presence:
69 case PropertyCondition::Equivalence:
70 case PropertyCondition::CustomFunctionEquivalence:
71 if (sawBase)
72 return false;
73 sawBase = true;
74 break;
75 default:
76 break;
77 }
78 }
79
80 return sawBase;
81}
82
83ObjectPropertyCondition ObjectPropertyConditionSet::slotBaseCondition() const
84{
85 ObjectPropertyCondition result;
86 unsigned numFound = 0;
87 for (const ObjectPropertyCondition& condition : *this) {
88 if (condition.kind() == PropertyCondition::Presence
89 || condition.kind() == PropertyCondition::Equivalence
90 || condition.kind() == PropertyCondition::CustomFunctionEquivalence) {
91 result = condition;
92 numFound++;
93 }
94 }
95 RELEASE_ASSERT(numFound == 1);
96 return result;
97}
98
99ObjectPropertyConditionSet ObjectPropertyConditionSet::mergedWith(
100 const ObjectPropertyConditionSet& other) const
101{
102 if (!isValid() || !other.isValid())
103 return invalid();
104
105 Vector<ObjectPropertyCondition> result;
106
107 if (!isEmpty())
108 result.appendVector(m_data->vector);
109
110 for (const ObjectPropertyCondition& newCondition : other) {
111 bool foundMatch = false;
112 for (const ObjectPropertyCondition& existingCondition : *this) {
113 if (newCondition == existingCondition) {
114 foundMatch = true;
115 continue;
116 }
117 if (!newCondition.isCompatibleWith(existingCondition))
118 return invalid();
119 }
120 if (!foundMatch)
121 result.append(newCondition);
122 }
123
124 return create(result);
125}
126
127bool ObjectPropertyConditionSet::structuresEnsureValidity() const
128{
129 if (!isValid())
130 return false;
131
132 for (const ObjectPropertyCondition& condition : *this) {
133 if (!condition.structureEnsuresValidity())
134 return false;
135 }
136 return true;
137}
138
139bool ObjectPropertyConditionSet::structuresEnsureValidityAssumingImpurePropertyWatchpoint() const
140{
141 if (!isValid())
142 return false;
143
144 for (const ObjectPropertyCondition& condition : *this) {
145 if (!condition.structureEnsuresValidityAssumingImpurePropertyWatchpoint())
146 return false;
147 }
148 return true;
149}
150
151bool ObjectPropertyConditionSet::needImpurePropertyWatchpoint() const
152{
153 for (const ObjectPropertyCondition& condition : *this) {
154 if (condition.validityRequiresImpurePropertyWatchpoint())
155 return true;
156 }
157 return false;
158}
159
160bool ObjectPropertyConditionSet::areStillLive(VM& vm) const
161{
162 bool stillLive = true;
163 forEachDependentCell([&](JSCell* cell) {
164 stillLive &= vm.heap.isMarked(cell);
165 });
166 return stillLive;
167}
168
169void ObjectPropertyConditionSet::dumpInContext(PrintStream& out, DumpContext* context) const
170{
171 if (!isValid()) {
172 out.print("<invalid>");
173 return;
174 }
175
176 out.print("[");
177 if (m_data)
178 out.print(listDumpInContext(m_data->vector, context));
179 out.print("]");
180}
181
182void ObjectPropertyConditionSet::dump(PrintStream& out) const
183{
184 dumpInContext(out, nullptr);
185}
186
187bool ObjectPropertyConditionSet::isValidAndWatchable() const
188{
189 if (!isValid())
190 return false;
191
192 for (ObjectPropertyCondition condition : m_data->vector) {
193 if (!condition.isWatchable())
194 return false;
195 }
196 return true;
197}
198
199namespace {
200
201namespace ObjectPropertyConditionSetInternal {
202static constexpr bool verbose = false;
203}
204
205ObjectPropertyCondition generateCondition(
206 VM& vm, JSCell* owner, JSObject* object, UniquedStringImpl* uid, PropertyCondition::Kind conditionKind)
207{
208 Structure* structure = object->structure(vm);
209 if (ObjectPropertyConditionSetInternal::verbose)
210 dataLog("Creating condition ", conditionKind, " for ", pointerDump(structure), "\n");
211
212 ObjectPropertyCondition result;
213 switch (conditionKind) {
214 case PropertyCondition::Presence: {
215 unsigned attributes;
216 PropertyOffset offset = structure->getConcurrently(uid, attributes);
217 if (offset == invalidOffset)
218 return ObjectPropertyCondition();
219 result = ObjectPropertyCondition::presence(vm, owner, object, uid, offset, attributes);
220 break;
221 }
222 case PropertyCondition::Absence: {
223 if (structure->hasPolyProto())
224 return ObjectPropertyCondition();
225 result = ObjectPropertyCondition::absence(
226 vm, owner, object, uid, object->structure(vm)->storedPrototypeObject());
227 break;
228 }
229 case PropertyCondition::AbsenceOfSetEffect: {
230 if (structure->hasPolyProto())
231 return ObjectPropertyCondition();
232 result = ObjectPropertyCondition::absenceOfSetEffect(
233 vm, owner, object, uid, object->structure(vm)->storedPrototypeObject());
234 break;
235 }
236 case PropertyCondition::Equivalence: {
237 unsigned attributes;
238 PropertyOffset offset = structure->getConcurrently(uid, attributes);
239 if (offset == invalidOffset)
240 return ObjectPropertyCondition();
241 JSValue value = object->getDirectConcurrently(structure, offset);
242 if (!value)
243 return ObjectPropertyCondition();
244 result = ObjectPropertyCondition::equivalence(vm, owner, object, uid, value);
245 break;
246 }
247 case PropertyCondition::CustomFunctionEquivalence: {
248 auto entry = object->findPropertyHashEntry(vm, uid);
249 if (!entry)
250 return ObjectPropertyCondition();
251 result = ObjectPropertyCondition::customFunctionEquivalence(vm, owner, object, uid);
252 break;
253 }
254 default:
255 RELEASE_ASSERT_NOT_REACHED();
256 return ObjectPropertyCondition();
257 }
258
259 if (!result.isStillValidAssumingImpurePropertyWatchpoint()) {
260 if (ObjectPropertyConditionSetInternal::verbose)
261 dataLog("Failed to create condition: ", result, "\n");
262 return ObjectPropertyCondition();
263 }
264
265 if (ObjectPropertyConditionSetInternal::verbose)
266 dataLog("New condition: ", result, "\n");
267 return result;
268}
269
270template<typename Functor>
271ObjectPropertyConditionSet generateConditions(
272 VM& vm, JSGlobalObject* globalObject, Structure* structure, JSObject* prototype, const Functor& functor)
273{
274 Vector<ObjectPropertyCondition> conditions;
275
276 for (;;) {
277 if (ObjectPropertyConditionSetInternal::verbose)
278 dataLog("Considering structure: ", pointerDump(structure), "\n");
279
280 if (structure->isProxy()) {
281 if (ObjectPropertyConditionSetInternal::verbose)
282 dataLog("It's a proxy, so invalid.\n");
283 return ObjectPropertyConditionSet::invalid();
284 }
285
286 if (structure->hasPolyProto()) {
287 // FIXME: Integrate this with PolyProtoAccessChain:
288 // https://bugs.webkit.org/show_bug.cgi?id=177339
289 // Or at least allow OPC set generation when the
290 // base is not poly proto:
291 // https://bugs.webkit.org/show_bug.cgi?id=177721
292 return ObjectPropertyConditionSet::invalid();
293 }
294
295 JSValue value = structure->prototypeForLookup(globalObject);
296
297 if (value.isNull()) {
298 if (!prototype) {
299 if (ObjectPropertyConditionSetInternal::verbose)
300 dataLog("Reached end of prototype chain as expected, done.\n");
301 break;
302 }
303 if (ObjectPropertyConditionSetInternal::verbose)
304 dataLog("Unexpectedly reached end of prototype chain, so invalid.\n");
305 return ObjectPropertyConditionSet::invalid();
306 }
307
308 JSObject* object = jsCast<JSObject*>(value);
309 structure = object->structure(vm);
310
311 if (structure->isDictionary()) {
312 if (ObjectPropertyConditionSetInternal::verbose)
313 dataLog("Cannot cache dictionary.\n");
314 return ObjectPropertyConditionSet::invalid();
315 }
316
317 if (!functor(conditions, object)) {
318 if (ObjectPropertyConditionSetInternal::verbose)
319 dataLog("Functor failed, invalid.\n");
320 return ObjectPropertyConditionSet::invalid();
321 }
322
323 if (object == prototype) {
324 if (ObjectPropertyConditionSetInternal::verbose)
325 dataLog("Reached desired prototype, done.\n");
326 break;
327 }
328 }
329
330 if (ObjectPropertyConditionSetInternal::verbose)
331 dataLog("Returning conditions: ", listDump(conditions), "\n");
332 return ObjectPropertyConditionSet::create(conditions);
333}
334
335} // anonymous namespace
336
337ObjectPropertyConditionSet generateConditionsForPropertyMiss(
338 VM& vm, JSCell* owner, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
339{
340 return generateConditions(
341 vm, globalObject, headStructure, nullptr,
342 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
343 ObjectPropertyCondition result =
344 generateCondition(vm, owner, object, uid, PropertyCondition::Absence);
345 if (!result)
346 return false;
347 conditions.append(result);
348 return true;
349 });
350}
351
352ObjectPropertyConditionSet generateConditionsForPropertySetterMiss(
353 VM& vm, JSCell* owner, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
354{
355 return generateConditions(
356 vm, globalObject, headStructure, nullptr,
357 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
358 ObjectPropertyCondition result =
359 generateCondition(vm, owner, object, uid, PropertyCondition::AbsenceOfSetEffect);
360 if (!result)
361 return false;
362 conditions.append(result);
363 return true;
364 });
365}
366
367ObjectPropertyConditionSet generateConditionsForPrototypePropertyHit(
368 VM& vm, JSCell* owner, JSGlobalObject* globalObject, Structure* headStructure, JSObject* prototype,
369 UniquedStringImpl* uid)
370{
371 return generateConditions(
372 vm, globalObject, headStructure, prototype,
373 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
374 PropertyCondition::Kind kind =
375 object == prototype ? PropertyCondition::Presence : PropertyCondition::Absence;
376 ObjectPropertyCondition result =
377 generateCondition(vm, owner, object, uid, kind);
378 if (!result)
379 return false;
380 conditions.append(result);
381 return true;
382 });
383}
384
385ObjectPropertyConditionSet generateConditionsForPrototypePropertyHitCustom(
386 VM& vm, JSCell* owner, JSGlobalObject* globalObject, Structure* headStructure, JSObject* prototype,
387 UniquedStringImpl* uid, unsigned attributes)
388{
389 return generateConditions(
390 vm, globalObject, headStructure, prototype,
391 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
392 auto kind = PropertyCondition::Absence;
393 if (object == prototype) {
394 Structure* structure = object->structure(vm);
395 PropertyOffset offset = structure->get(vm, uid);
396 if (isValidOffset(offset)) {
397 // When we reify custom accessors, we wrap them in a JSFunction that we shove
398 // inside a GetterSetter. So, once we've reified a custom accessor, we will
399 // no longer see it as a "custom" accessor/value. Hence, if our property access actually
400 // notices a custom, it must be a CustomGetterSetterType cell or something
401 // in the static property table. Custom values get reified into CustomGetterSetters.
402 JSValue value = object->getDirect(offset);
403 ASSERT_UNUSED(value, value.isCell() && value.asCell()->type() == CustomGetterSetterType);
404 kind = PropertyCondition::Equivalence;
405 } else if (structure->findPropertyHashEntry(uid))
406 kind = PropertyCondition::CustomFunctionEquivalence;
407 else if (attributes & PropertyAttribute::DontDelete) {
408 // This can't change, so we can blindly cache it.
409 return true;
410 } else {
411 // This means we materialized a custom out of thin air and it's not DontDelete (i.e, it can be
412 // redefined). This is curious. We don't actually need to crash here. We could blindly cache
413 // the function. Or we could blindly not cache it. However, we don't actually do this in WebKit
414 // right now, so it's reasonable to decide what to do later (or to warn people of forgetting DoneDelete.)
415 ASSERT_NOT_REACHED();
416 return false;
417 }
418 }
419 ObjectPropertyCondition result = generateCondition(vm, owner, object, uid, kind);
420 if (!result)
421 return false;
422 conditions.append(result);
423 return true;
424 });
425}
426
427ObjectPropertyConditionSet generateConditionsForInstanceOf(
428 VM& vm, JSCell* owner, JSGlobalObject* globalObject, Structure* headStructure, JSObject* prototype,
429 bool shouldHit)
430{
431 bool didHit = false;
432 if (ObjectPropertyConditionSetInternal::verbose)
433 dataLog("Searching for prototype ", JSValue(prototype), " starting with structure ", RawPointer(headStructure), " with shouldHit = ", shouldHit, "\n");
434 ObjectPropertyConditionSet result = generateConditions(
435 vm, globalObject, headStructure, shouldHit ? prototype : nullptr,
436 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
437 if (ObjectPropertyConditionSetInternal::verbose)
438 dataLog("Encountered object: ", RawPointer(object), "\n");
439 if (object == prototype) {
440 RELEASE_ASSERT(shouldHit);
441 didHit = true;
442 return true;
443 }
444
445 Structure* structure = object->structure(vm);
446 if (structure->hasPolyProto())
447 return false;
448 conditions.append(
449 ObjectPropertyCondition::hasPrototype(
450 vm, owner, object, structure->storedPrototypeObject()));
451 return true;
452 });
453 if (result.isValid()) {
454 if (ObjectPropertyConditionSetInternal::verbose)
455 dataLog("didHit = ", didHit, ", shouldHit = ", shouldHit, "\n");
456 RELEASE_ASSERT(didHit == shouldHit);
457 }
458 return result;
459}
460
461ObjectPropertyConditionSet generateConditionsForPrototypeEquivalenceConcurrently(
462 VM& vm, JSGlobalObject* globalObject, Structure* headStructure, JSObject* prototype, UniquedStringImpl* uid)
463{
464 return generateConditions(vm, globalObject, headStructure, prototype,
465 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
466 PropertyCondition::Kind kind =
467 object == prototype ? PropertyCondition::Equivalence : PropertyCondition::Absence;
468 ObjectPropertyCondition result = generateCondition(vm, nullptr, object, uid, kind);
469 if (!result)
470 return false;
471 conditions.append(result);
472 return true;
473 });
474}
475
476ObjectPropertyConditionSet generateConditionsForPropertyMissConcurrently(
477 VM& vm, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
478{
479 return generateConditions(
480 vm, globalObject, headStructure, nullptr,
481 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
482 ObjectPropertyCondition result = generateCondition(vm, nullptr, object, uid, PropertyCondition::Absence);
483 if (!result)
484 return false;
485 conditions.append(result);
486 return true;
487 });
488}
489
490ObjectPropertyConditionSet generateConditionsForPropertySetterMissConcurrently(
491 VM& vm, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
492{
493 return generateConditions(
494 vm, globalObject, headStructure, nullptr,
495 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
496 ObjectPropertyCondition result =
497 generateCondition(vm, nullptr, object, uid, PropertyCondition::AbsenceOfSetEffect);
498 if (!result)
499 return false;
500 conditions.append(result);
501 return true;
502 });
503}
504
505ObjectPropertyCondition generateConditionForSelfEquivalence(
506 VM& vm, JSCell* owner, JSObject* object, UniquedStringImpl* uid)
507{
508 return generateCondition(vm, owner, object, uid, PropertyCondition::Equivalence);
509}
510
511// Current might be null. Structure can't be null.
512static Optional<PrototypeChainCachingStatus> preparePrototypeChainForCaching(JSGlobalObject* globalObject, JSCell* current, Structure* structure, JSObject* target)
513{
514 ASSERT(structure);
515 VM& vm = globalObject->vm();
516
517 bool found = false;
518 bool usesPolyProto = false;
519 bool flattenedDictionary = false;
520
521 while (true) {
522 if (structure->isDictionary()) {
523 if (!current)
524 return WTF::nullopt;
525
526 ASSERT(structure->isObject());
527 if (structure->hasBeenFlattenedBefore())
528 return WTF::nullopt;
529
530 structure->flattenDictionaryStructure(vm, asObject(current));
531 flattenedDictionary = true;
532 }
533
534 if (!structure->propertyAccessesAreCacheable())
535 return WTF::nullopt;
536
537 if (structure->isProxy())
538 return WTF::nullopt;
539
540 if (current && current == target) {
541 found = true;
542 break;
543 }
544
545 // We only have poly proto if we need to access our prototype via
546 // the poly proto protocol. If the slot base is the only poly proto
547 // thing in the chain, and we have a cache hit on it, then we're not
548 // poly proto.
549 JSValue prototype;
550 if (structure->hasPolyProto()) {
551 if (!current)
552 return WTF::nullopt;
553 usesPolyProto = true;
554 prototype = structure->prototypeForLookup(globalObject, current);
555 } else
556 prototype = structure->prototypeForLookup(globalObject);
557
558 if (prototype.isNull())
559 break;
560 current = asObject(prototype);
561 structure = current->structure(vm);
562 }
563
564 if (!found && !!target)
565 return WTF::nullopt;
566
567 PrototypeChainCachingStatus result;
568 result.usesPolyProto = usesPolyProto;
569 result.flattenedDictionary = flattenedDictionary;
570
571 return result;
572}
573
574Optional<PrototypeChainCachingStatus> preparePrototypeChainForCaching(JSGlobalObject* globalObject, JSCell* base, JSObject* target)
575{
576 return preparePrototypeChainForCaching(globalObject, base, base->structure(globalObject->vm()), target);
577}
578
579Optional<PrototypeChainCachingStatus> preparePrototypeChainForCaching(JSGlobalObject* globalObject, JSCell* base, const PropertySlot& slot)
580{
581 JSObject* target = slot.isUnset() ? nullptr : slot.slotBase();
582 return preparePrototypeChainForCaching(globalObject, base, target);
583}
584
585Optional<PrototypeChainCachingStatus> preparePrototypeChainForCaching(JSGlobalObject* globalObject, Structure* baseStructure, JSObject* target)
586{
587 return preparePrototypeChainForCaching(globalObject, nullptr, baseStructure, target);
588}
589
590} // namespace JSC
591
592