1/*
2 * Copyright (C) 2015-2018 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 return (numberOfConditionsWithKind(PropertyCondition::Presence) == 1) != (numberOfConditionsWithKind(PropertyCondition::Equivalence) == 1);
66}
67
68ObjectPropertyCondition ObjectPropertyConditionSet::slotBaseCondition() const
69{
70 ObjectPropertyCondition result;
71 unsigned numFound = 0;
72 for (const ObjectPropertyCondition& condition : *this) {
73 if (condition.kind() == PropertyCondition::Presence
74 || condition.kind() == PropertyCondition::Equivalence) {
75 result = condition;
76 numFound++;
77 }
78 }
79 RELEASE_ASSERT(numFound == 1);
80 return result;
81}
82
83ObjectPropertyConditionSet ObjectPropertyConditionSet::mergedWith(
84 const ObjectPropertyConditionSet& other) const
85{
86 if (!isValid() || !other.isValid())
87 return invalid();
88
89 Vector<ObjectPropertyCondition> result;
90
91 if (!isEmpty())
92 result.appendVector(m_data->vector);
93
94 for (const ObjectPropertyCondition& newCondition : other) {
95 bool foundMatch = false;
96 for (const ObjectPropertyCondition& existingCondition : *this) {
97 if (newCondition == existingCondition) {
98 foundMatch = true;
99 continue;
100 }
101 if (!newCondition.isCompatibleWith(existingCondition))
102 return invalid();
103 }
104 if (!foundMatch)
105 result.append(newCondition);
106 }
107
108 return create(result);
109}
110
111bool ObjectPropertyConditionSet::structuresEnsureValidity() const
112{
113 if (!isValid())
114 return false;
115
116 for (const ObjectPropertyCondition& condition : *this) {
117 if (!condition.structureEnsuresValidity())
118 return false;
119 }
120 return true;
121}
122
123bool ObjectPropertyConditionSet::structuresEnsureValidityAssumingImpurePropertyWatchpoint() const
124{
125 if (!isValid())
126 return false;
127
128 for (const ObjectPropertyCondition& condition : *this) {
129 if (!condition.structureEnsuresValidityAssumingImpurePropertyWatchpoint())
130 return false;
131 }
132 return true;
133}
134
135bool ObjectPropertyConditionSet::needImpurePropertyWatchpoint() const
136{
137 for (const ObjectPropertyCondition& condition : *this) {
138 if (condition.validityRequiresImpurePropertyWatchpoint())
139 return true;
140 }
141 return false;
142}
143
144bool ObjectPropertyConditionSet::areStillLive(VM& vm) const
145{
146 for (const ObjectPropertyCondition& condition : *this) {
147 if (!condition.isStillLive(vm))
148 return false;
149 }
150 return true;
151}
152
153void ObjectPropertyConditionSet::dumpInContext(PrintStream& out, DumpContext* context) const
154{
155 if (!isValid()) {
156 out.print("<invalid>");
157 return;
158 }
159
160 out.print("[");
161 if (m_data)
162 out.print(listDumpInContext(m_data->vector, context));
163 out.print("]");
164}
165
166void ObjectPropertyConditionSet::dump(PrintStream& out) const
167{
168 dumpInContext(out, nullptr);
169}
170
171bool ObjectPropertyConditionSet::isValidAndWatchable() const
172{
173 if (!isValid())
174 return false;
175
176 for (ObjectPropertyCondition condition : m_data->vector) {
177 if (!condition.isWatchable())
178 return false;
179 }
180 return true;
181}
182
183namespace {
184
185namespace ObjectPropertyConditionSetInternal {
186static const bool verbose = false;
187}
188
189ObjectPropertyCondition generateCondition(
190 VM& vm, JSCell* owner, JSObject* object, UniquedStringImpl* uid, PropertyCondition::Kind conditionKind)
191{
192 Structure* structure = object->structure(vm);
193 if (ObjectPropertyConditionSetInternal::verbose)
194 dataLog("Creating condition ", conditionKind, " for ", pointerDump(structure), "\n");
195
196 ObjectPropertyCondition result;
197 switch (conditionKind) {
198 case PropertyCondition::Presence: {
199 unsigned attributes;
200 PropertyOffset offset = structure->getConcurrently(uid, attributes);
201 if (offset == invalidOffset)
202 return ObjectPropertyCondition();
203 result = ObjectPropertyCondition::presence(vm, owner, object, uid, offset, attributes);
204 break;
205 }
206 case PropertyCondition::Absence: {
207 if (structure->hasPolyProto())
208 return ObjectPropertyCondition();
209 result = ObjectPropertyCondition::absence(
210 vm, owner, object, uid, object->structure(vm)->storedPrototypeObject());
211 break;
212 }
213 case PropertyCondition::AbsenceOfSetEffect: {
214 if (structure->hasPolyProto())
215 return ObjectPropertyCondition();
216 result = ObjectPropertyCondition::absenceOfSetEffect(
217 vm, owner, object, uid, object->structure(vm)->storedPrototypeObject());
218 break;
219 }
220 case PropertyCondition::Equivalence: {
221 unsigned attributes;
222 PropertyOffset offset = structure->getConcurrently(uid, attributes);
223 if (offset == invalidOffset)
224 return ObjectPropertyCondition();
225 JSValue value = object->getDirectConcurrently(structure, offset);
226 if (!value)
227 return ObjectPropertyCondition();
228 result = ObjectPropertyCondition::equivalence(vm, owner, object, uid, value);
229 break;
230 }
231 default:
232 RELEASE_ASSERT_NOT_REACHED();
233 return ObjectPropertyCondition();
234 }
235
236 if (!result.isStillValidAssumingImpurePropertyWatchpoint()) {
237 if (ObjectPropertyConditionSetInternal::verbose)
238 dataLog("Failed to create condition: ", result, "\n");
239 return ObjectPropertyCondition();
240 }
241
242 if (ObjectPropertyConditionSetInternal::verbose)
243 dataLog("New condition: ", result, "\n");
244 return result;
245}
246
247enum Concurrency {
248 MainThread,
249 Concurrent
250};
251template<typename Functor>
252ObjectPropertyConditionSet generateConditions(
253 VM& vm, JSGlobalObject* globalObject, Structure* structure, JSObject* prototype, const Functor& functor,
254 Concurrency concurrency = MainThread)
255{
256 Vector<ObjectPropertyCondition> conditions;
257
258 for (;;) {
259 if (ObjectPropertyConditionSetInternal::verbose)
260 dataLog("Considering structure: ", pointerDump(structure), "\n");
261
262 if (structure->isProxy()) {
263 if (ObjectPropertyConditionSetInternal::verbose)
264 dataLog("It's a proxy, so invalid.\n");
265 return ObjectPropertyConditionSet::invalid();
266 }
267
268 if (structure->hasPolyProto()) {
269 // FIXME: Integrate this with PolyProtoAccessChain:
270 // https://bugs.webkit.org/show_bug.cgi?id=177339
271 // Or at least allow OPC set generation when the
272 // base is not poly proto:
273 // https://bugs.webkit.org/show_bug.cgi?id=177721
274 return ObjectPropertyConditionSet::invalid();
275 }
276
277 JSValue value = structure->prototypeForLookup(globalObject);
278
279 if (value.isNull()) {
280 if (!prototype) {
281 if (ObjectPropertyConditionSetInternal::verbose)
282 dataLog("Reached end of prototype chain as expected, done.\n");
283 break;
284 }
285 if (ObjectPropertyConditionSetInternal::verbose)
286 dataLog("Unexpectedly reached end of prototype chain, so invalid.\n");
287 return ObjectPropertyConditionSet::invalid();
288 }
289
290 JSObject* object = jsCast<JSObject*>(value);
291 structure = object->structure(vm);
292
293 if (structure->isDictionary()) {
294 if (concurrency == MainThread) {
295 if (structure->hasBeenFlattenedBefore()) {
296 if (ObjectPropertyConditionSetInternal::verbose)
297 dataLog("Dictionary has been flattened before, so invalid.\n");
298 return ObjectPropertyConditionSet::invalid();
299 }
300
301 if (ObjectPropertyConditionSetInternal::verbose)
302 dataLog("Flattening ", pointerDump(structure));
303 structure->flattenDictionaryStructure(vm, object);
304 } else {
305 if (ObjectPropertyConditionSetInternal::verbose)
306 dataLog("Cannot flatten dictionary when not on main thread, so invalid.\n");
307 return ObjectPropertyConditionSet::invalid();
308 }
309 }
310
311 if (!functor(conditions, object)) {
312 if (ObjectPropertyConditionSetInternal::verbose)
313 dataLog("Functor failed, invalid.\n");
314 return ObjectPropertyConditionSet::invalid();
315 }
316
317 if (object == prototype) {
318 if (ObjectPropertyConditionSetInternal::verbose)
319 dataLog("Reached desired prototype, done.\n");
320 break;
321 }
322 }
323
324 if (ObjectPropertyConditionSetInternal::verbose)
325 dataLog("Returning conditions: ", listDump(conditions), "\n");
326 return ObjectPropertyConditionSet::create(conditions);
327}
328
329} // anonymous namespace
330
331ObjectPropertyConditionSet generateConditionsForPropertyMiss(
332 VM& vm, JSCell* owner, ExecState* exec, Structure* headStructure, UniquedStringImpl* uid)
333{
334 return generateConditions(
335 vm, exec->lexicalGlobalObject(), headStructure, nullptr,
336 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
337 ObjectPropertyCondition result =
338 generateCondition(vm, owner, object, uid, PropertyCondition::Absence);
339 if (!result)
340 return false;
341 conditions.append(result);
342 return true;
343 });
344}
345
346ObjectPropertyConditionSet generateConditionsForPropertySetterMiss(
347 VM& vm, JSCell* owner, ExecState* exec, Structure* headStructure, UniquedStringImpl* uid)
348{
349 return generateConditions(
350 vm, exec->lexicalGlobalObject(), headStructure, nullptr,
351 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
352 ObjectPropertyCondition result =
353 generateCondition(vm, owner, object, uid, PropertyCondition::AbsenceOfSetEffect);
354 if (!result)
355 return false;
356 conditions.append(result);
357 return true;
358 });
359}
360
361ObjectPropertyConditionSet generateConditionsForPrototypePropertyHit(
362 VM& vm, JSCell* owner, ExecState* exec, Structure* headStructure, JSObject* prototype,
363 UniquedStringImpl* uid)
364{
365 return generateConditions(
366 vm, exec->lexicalGlobalObject(), headStructure, prototype,
367 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
368 PropertyCondition::Kind kind =
369 object == prototype ? PropertyCondition::Presence : PropertyCondition::Absence;
370 ObjectPropertyCondition result =
371 generateCondition(vm, owner, object, uid, kind);
372 if (!result)
373 return false;
374 conditions.append(result);
375 return true;
376 });
377}
378
379ObjectPropertyConditionSet generateConditionsForPrototypePropertyHitCustom(
380 VM& vm, JSCell* owner, ExecState* exec, Structure* headStructure, JSObject* prototype,
381 UniquedStringImpl* uid)
382{
383 return generateConditions(
384 vm, exec->lexicalGlobalObject(), headStructure, prototype,
385 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
386 if (object == prototype)
387 return true;
388 ObjectPropertyCondition result =
389 generateCondition(vm, owner, object, uid, PropertyCondition::Absence);
390 if (!result)
391 return false;
392 conditions.append(result);
393 return true;
394 });
395}
396
397ObjectPropertyConditionSet generateConditionsForInstanceOf(
398 VM& vm, JSCell* owner, ExecState* exec, Structure* headStructure, JSObject* prototype,
399 bool shouldHit)
400{
401 bool didHit = false;
402 if (ObjectPropertyConditionSetInternal::verbose)
403 dataLog("Searching for prototype ", JSValue(prototype), " starting with structure ", RawPointer(headStructure), " with shouldHit = ", shouldHit, "\n");
404 ObjectPropertyConditionSet result = generateConditions(
405 vm, exec->lexicalGlobalObject(), headStructure, shouldHit ? prototype : nullptr,
406 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
407 if (ObjectPropertyConditionSetInternal::verbose)
408 dataLog("Encountered object: ", RawPointer(object), "\n");
409 if (object == prototype) {
410 RELEASE_ASSERT(shouldHit);
411 didHit = true;
412 return true;
413 }
414
415 Structure* structure = object->structure(vm);
416 if (structure->hasPolyProto())
417 return false;
418 conditions.append(
419 ObjectPropertyCondition::hasPrototype(
420 vm, owner, object, structure->storedPrototypeObject()));
421 return true;
422 });
423 if (result.isValid()) {
424 if (ObjectPropertyConditionSetInternal::verbose)
425 dataLog("didHit = ", didHit, ", shouldHit = ", shouldHit, "\n");
426 RELEASE_ASSERT(didHit == shouldHit);
427 }
428 return result;
429}
430
431ObjectPropertyConditionSet generateConditionsForPrototypeEquivalenceConcurrently(
432 VM& vm, JSGlobalObject* globalObject, Structure* headStructure, JSObject* prototype, UniquedStringImpl* uid)
433{
434 return generateConditions(vm, globalObject, headStructure, prototype,
435 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
436 PropertyCondition::Kind kind =
437 object == prototype ? PropertyCondition::Equivalence : PropertyCondition::Absence;
438 ObjectPropertyCondition result = generateCondition(vm, nullptr, object, uid, kind);
439 if (!result)
440 return false;
441 conditions.append(result);
442 return true;
443 }, Concurrent);
444}
445
446ObjectPropertyConditionSet generateConditionsForPropertyMissConcurrently(
447 VM& vm, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
448{
449 return generateConditions(
450 vm, globalObject, headStructure, nullptr,
451 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
452 ObjectPropertyCondition result = generateCondition(vm, nullptr, object, uid, PropertyCondition::Absence);
453 if (!result)
454 return false;
455 conditions.append(result);
456 return true;
457 }, Concurrent);
458}
459
460ObjectPropertyConditionSet generateConditionsForPropertySetterMissConcurrently(
461 VM& vm, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
462{
463 return generateConditions(
464 vm, globalObject, headStructure, nullptr,
465 [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
466 ObjectPropertyCondition result =
467 generateCondition(vm, nullptr, object, uid, PropertyCondition::AbsenceOfSetEffect);
468 if (!result)
469 return false;
470 conditions.append(result);
471 return true;
472 }, Concurrent);
473}
474
475ObjectPropertyCondition generateConditionForSelfEquivalence(
476 VM& vm, JSCell* owner, JSObject* object, UniquedStringImpl* uid)
477{
478 return generateCondition(vm, owner, object, uid, PropertyCondition::Equivalence);
479}
480
481} // namespace JSC
482
483