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  
 32  namespace JSC {
 33  
 34  ObjectPropertyCondition 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  
 43  ObjectPropertyCondition 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  
 53  unsigned 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  
 63  bool 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::HasStaticProperty:
 71              if (sawBase)
 72                  return false;
 73              sawBase = true;
 74              break;
 75          default:
 76              break;
 77          }
 78      }
 79  
 80      return sawBase;
 81  }
 82  
 83  ObjectPropertyCondition 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::HasStaticProperty) {
 91              result = condition;
 92              numFound++;
 93          }
 94      }
 95      RELEASE_ASSERT(numFound == 1);
 96      return result;
 97  }
 98  
 99  ObjectPropertyConditionSet 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  
127  bool 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  
139  bool 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  
151  bool ObjectPropertyConditionSet::needImpurePropertyWatchpoint() const
152  {
153      for (const ObjectPropertyCondition& condition : *this) {
154          if (condition.validityRequiresImpurePropertyWatchpoint())
155              return true;
156      }
157      return false;
158  }
159  
160  bool 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  
169  void 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  
182  void ObjectPropertyConditionSet::dump(PrintStream& out) const
183  {
184      dumpInContext(out, nullptr);
185  }
186  
187  bool 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  
199  namespace {
200  
201  namespace ObjectPropertyConditionSetInternal {
202  static constexpr bool verbose = false;
203  }
204  
205  ObjectPropertyCondition 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::HasStaticProperty: {
248          auto entry = object->findPropertyHashEntry(vm, uid);
249          if (!entry)
250              return ObjectPropertyCondition();
251          result = ObjectPropertyCondition::hasStaticProperty(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  
270  template<typename Functor>
271  ObjectPropertyConditionSet 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  
337  ObjectPropertyConditionSet 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  
352  ObjectPropertyConditionSet 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  
367  ObjectPropertyConditionSet 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  
385  ObjectPropertyConditionSet 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  
404                      if (!value.isCell() || value.asCell()->type() != CustomGetterSetterType) {
405                          // The value could have just got changed to some other type, so check if it's still
406                          // a custom getter setter.
407                          return false;
408                      }
409  
410                      kind = PropertyCondition::Equivalence;
411                  } else if (structure->findPropertyHashEntry(uid))
412                      kind = PropertyCondition::HasStaticProperty;
413                  else if (attributes & PropertyAttribute::DontDelete) {
414                      // This can't change, so we can blindly cache it.
415                      return true;
416                  } else {
417                      // This means we materialized a custom out of thin air and it's not DontDelete (i.e, it can be
418                      // redefined). This is curious. We don't actually need to crash here. We could blindly cache
419                      // the function. Or we could blindly not cache it. However, we don't actually do this in WebKit
420                      // right now, so it's reasonable to decide what to do later (or to warn people of forgetting DoneDelete.)
421                      ASSERT_NOT_REACHED();
422                      return false;
423                  }
424              }
425              ObjectPropertyCondition result = generateCondition(vm, owner, object, uid, kind);
426              if (!result)
427                  return false;
428              conditions.append(result);
429              return true;
430          });
431  }
432  
433  ObjectPropertyConditionSet generateConditionsForInstanceOf(
434      VM& vm, JSCell* owner, JSGlobalObject* globalObject, Structure* headStructure, JSObject* prototype,
435      bool shouldHit)
436  {
437      bool didHit = false;
438      if (ObjectPropertyConditionSetInternal::verbose)
439          dataLog("Searching for prototype ", JSValue(prototype), " starting with structure ", RawPointer(headStructure), " with shouldHit = ", shouldHit, "\n");
440      ObjectPropertyConditionSet result = generateConditions(
441          vm, globalObject, headStructure, shouldHit ? prototype : nullptr,
442          [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
443              if (ObjectPropertyConditionSetInternal::verbose)
444                  dataLog("Encountered object: ", RawPointer(object), "\n");
445              if (object == prototype) {
446                  RELEASE_ASSERT(shouldHit);
447                  didHit = true;
448                  return true;
449              }
450  
451              Structure* structure = object->structure(vm);
452              if (structure->hasPolyProto())
453                  return false;
454              conditions.append(
455                  ObjectPropertyCondition::hasPrototype(
456                      vm, owner, object, structure->storedPrototypeObject()));
457              return true;
458          });
459      if (result.isValid()) {
460          if (ObjectPropertyConditionSetInternal::verbose)
461              dataLog("didHit = ", didHit, ", shouldHit = ", shouldHit, "\n");
462          RELEASE_ASSERT(didHit == shouldHit);
463      }
464      return result;
465  }
466  
467  ObjectPropertyConditionSet generateConditionsForPrototypeEquivalenceConcurrently(
468      VM& vm, JSGlobalObject* globalObject, Structure* headStructure, JSObject* prototype, UniquedStringImpl* uid)
469  {
470      return generateConditions(vm, globalObject, headStructure, prototype,
471          [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
472              PropertyCondition::Kind kind =
473                  object == prototype ? PropertyCondition::Equivalence : PropertyCondition::Absence;
474              ObjectPropertyCondition result = generateCondition(vm, nullptr, object, uid, kind);
475              if (!result)
476                  return false;
477              conditions.append(result);
478              return true;
479          });
480  }
481  
482  ObjectPropertyConditionSet generateConditionsForPropertyMissConcurrently(
483      VM& vm, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
484  {
485      return generateConditions(
486          vm, globalObject, headStructure, nullptr,
487          [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
488              ObjectPropertyCondition result = generateCondition(vm, nullptr, object, uid, PropertyCondition::Absence);
489              if (!result)
490                  return false;
491              conditions.append(result);
492              return true;
493          });
494  }
495  
496  ObjectPropertyConditionSet generateConditionsForPropertySetterMissConcurrently(
497      VM& vm, JSGlobalObject* globalObject, Structure* headStructure, UniquedStringImpl* uid)
498  {
499      return generateConditions(
500          vm, globalObject, headStructure, nullptr,
501          [&] (Vector<ObjectPropertyCondition>& conditions, JSObject* object) -> bool {
502              ObjectPropertyCondition result =
503                  generateCondition(vm, nullptr, object, uid, PropertyCondition::AbsenceOfSetEffect);
504              if (!result)
505                  return false;
506              conditions.append(result);
507              return true;
508          });
509  }
510  
511  ObjectPropertyCondition generateConditionForSelfEquivalence(
512      VM& vm, JSCell* owner, JSObject* object, UniquedStringImpl* uid)
513  {
514      return generateCondition(vm, owner, object, uid, PropertyCondition::Equivalence);
515  }
516  
517  // Current might be null. Structure can't be null.
518  static Optional<PrototypeChainCachingStatus> prepareChainForCaching(JSGlobalObject* globalObject, JSCell* current, Structure* structure, JSObject* target)
519  {
520      ASSERT(structure);
521      VM& vm = globalObject->vm();
522  
523      bool found = false;
524      bool usesPolyProto = false;
525      bool flattenedDictionary = false;
526  
527      while (true) {
528          if (structure->isDictionary()) {
529              if (!current)
530                  return WTF::nullopt;
531  
532              ASSERT(structure->isObject());
533              if (structure->hasBeenFlattenedBefore())
534                  return WTF::nullopt;
535  
536              structure->flattenDictionaryStructure(vm, asObject(current));
537              flattenedDictionary = true;
538          }
539  
540          if (!structure->propertyAccessesAreCacheable())
541              return WTF::nullopt;
542  
543          if (structure->isProxy())
544              return WTF::nullopt;
545  
546          if (current && current == target) {
547              found = true;
548              break;
549          }
550  
551          // We only have poly proto if we need to access our prototype via
552          // the poly proto protocol. If the slot base is the only poly proto
553          // thing in the chain, and we have a cache hit on it, then we're not
554          // poly proto.
555          JSValue prototype;
556          if (structure->hasPolyProto()) {
557              if (!current)
558                  return WTF::nullopt;
559              usesPolyProto = true;
560              prototype = structure->prototypeForLookup(globalObject, current);
561          } else
562              prototype = structure->prototypeForLookup(globalObject);
563  
564          if (prototype.isNull())
565              break;
566          current = asObject(prototype);
567          structure = current->structure(vm);
568      }
569  
570      if (!found && !!target)
571          return WTF::nullopt;
572  
573      PrototypeChainCachingStatus result;
574      result.usesPolyProto = usesPolyProto;
575      result.flattenedDictionary = flattenedDictionary;
576  
577      return result;
578  }
579  
580  Optional<PrototypeChainCachingStatus> prepareChainForCaching(JSGlobalObject* globalObject, JSCell* base, JSObject* target)
581  {
582      return prepareChainForCaching(globalObject, base, base->structure(globalObject->vm()), target);
583  }
584  
585  Optional<PrototypeChainCachingStatus> prepareChainForCaching(JSGlobalObject* globalObject, JSCell* base, const PropertySlot& slot)
586  {
587      JSObject* target = slot.isUnset() ? nullptr : slot.slotBase();
588      return prepareChainForCaching(globalObject, base, target);
589  }
590  
591  Optional<PrototypeChainCachingStatus> prepareChainForCaching(JSGlobalObject* globalObject, Structure* baseStructure, JSObject* target)
592  {
593      return prepareChainForCaching(globalObject, nullptr, baseStructure, target);
594  }
595  
596  } // namespace JSC
597