[builtins] implement Array.prototype.includes in TurboFan

src/elements.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/elements.h"
 
 #include "src/arguments.h"
 #include "src/conversions.h"
 #include "src/factory.h"
 #include "src/isolate-inl.h"
@@ skipping 450 matching lines @@
   } cmp;
   Object** start =
       reinterpret_cast<Object**>(indices->GetFirstElementAddress());
   std::sort(start, start + sort_size, cmp);
   if (write_barrier_mode != SKIP_WRITE_BARRIER) {
     FIXED_ARRAY_ELEMENTS_WRITE_BARRIER(indices->GetIsolate()->heap(), *indices,
                                        0, sort_size);
   }
 }
 
+static Maybe<bool> IncludesValueSlowPath(Isolate* isolate,
+                                         Handle<JSObject> receiver,
+                                         Handle<Object> value,
+                                         uint32_t start_from, uint32_t length) {

[Camillo Bruni, 2016/07/28 12:57:29]

nit: expose this globally and use the common implementation from the builtin,
this way we can reduce some duplication.

[caitp, 2016/07/29 20:27:47]

The builtin has to deal with non-JSObject receivers and lengths up to 2^53-1,
whereas this one does not. While it is possible to make it support both, it
results in messier code :(

+  bool search_for_hole = value->IsUndefined(isolate);
+  for (uint32_t k = start_from; k < length; ++k) {
+    LookupIterator it(isolate, receiver, k);
+    if (!it.IsFound()) {
+      if (search_for_hole) return Just(true);
+      continue;
+    }
+    Handle<Object> element_k;
+    ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
+                                     Object::GetProperty(&it), Nothing<bool>());
+
+    if (value->SameValueZero(*element_k)) return Just(true);
+  }
+
+  return Just(false);
+}
+
 // Base class for element handler implementations. Contains the
 // the common logic for objects with different ElementsKinds.
 // Subclasses must specialize method for which the element
 // implementation differs from the base class implementation.
 //
 // This class is intended to be used in the following way:
 //
 //   class SomeElementsAccessor :
 //       public ElementsAccessorBase<SomeElementsAccessor,
 //                                   BackingStoreClass> {
@@ skipping 596 matching lines @@
 
   static uint32_t GetCapacityImpl(JSObject* holder,
                                   FixedArrayBase* backing_store) {
     return backing_store->length();
   }
 
   uint32_t GetCapacity(JSObject* holder, FixedArrayBase* backing_store) final {
     return Subclass::GetCapacityImpl(holder, backing_store);
   }
 
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> receiver,
+                                       Handle<Object> value,
+                                       uint32_t start_from, uint32_t length) {
+    return IncludesValueSlowPath(isolate, receiver, value, start_from, length);
+  }
+
+  Maybe<bool> IncludesValue(Isolate* isolate, Handle<JSObject> receiver,
+                            Handle<Object> value, uint32_t start_from,
+                            uint32_t length) final {
+    return Subclass::IncludesValueImpl(isolate, receiver, value, start_from,
+                                       length);
+  }
+
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
                                        uint32_t entry) {
     return entry;
   }
 
   static uint32_t GetEntryForIndexImpl(JSObject* holder,
                                        FixedArrayBase* backing_store,
                                        uint32_t index, PropertyFilter filter) {
     if (IsHoleyElementsKind(kind())) {
       return index < Subclass::GetCapacityImpl(holder, backing_store) &&
@@ skipping 316 matching lines @@
       if (k == *undefined) continue;
       if (k == *the_hole) continue;
       if (dictionary->IsDeleted(i)) continue;
       Object* value = dictionary->ValueAt(i);
       DCHECK(!value->IsTheHole(isolate));
       DCHECK(!value->IsAccessorPair());
       DCHECK(!value->IsAccessorInfo());
       accumulator->AddKey(value, convert);
     }
   }
+
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> receiver,
+                                       Handle<Object> value,
+                                       uint32_t start_from, uint32_t length) {
+    Handle<SeededNumberDictionary> dictionary(
+        SeededNumberDictionary::cast(receiver->elements()), isolate);
+
+    bool search_for_hole = value->IsUndefined(isolate);
+    if (search_for_hole) goto slow_path;

[Camillo Bruni, 2016/07/28 12:57:29]

shush, I didn't see this goto :D. 
For the sake of consistency you may resort to a fast helper that returns true on
completing the fast-path plus a bool pointer for the result.

[caitp, 2016/07/29 20:27:46]

Done.

+    goto slow_path;
+    {
+      DisallowHeapAllocation no_gc;
+      int capacity = dictionary->Capacity();
+      Object* the_hole = isolate->heap()->the_hole_value();
+      for (int i = 0; i < capacity; ++i) {
+        Object* k = dictionary->KeyAt(i);
+        if (!dictionary->IsKey(k)) continue;
+
+        Object* element_k = dictionary->ValueAt(i);
+        if (element_k == the_hole) continue;
+
+        switch (dictionary->DetailsAt(i).kind()) {
+          case kData: {
+            if (value->SameValueZero(element_k)) return Just(true);
+            break;
+          }
+          case kAccessor: {
+            // Restart from beginning in slow path, otherwise we may observably
+            // access getters out of order
+            goto slow_path;
+          }
+        }
+      }
+      return Just(false);
+    }
+
+  slow_path:
+    // Iterate through entire range, as accessing elements out of order is
+    // observable
+    for (uint32_t k = start_from; k < length; ++k) {
+      int entry = dictionary->FindEntry(k);
+      if (entry == SeededNumberDictionary::kNotFound) {
+        if (search_for_hole) return Just(true);
+        continue;
+      }
+
+      PropertyDetails details = GetDetailsImpl(receiver->elements(), entry);
+      switch (details.kind()) {
+        case kData: {
+          Object* element_k = dictionary->ValueAt(entry);
+          if (value->SameValueZero(element_k)) return Just(true);
+          break;
+        }
+        case kAccessor: {
+          LookupIterator it(isolate, receiver, k, LookupIterator::OWN);

[Camillo Bruni, 2016/07/28 12:57:29]

nit: You can minimally speed up the lookup iterator by passing in
OWN_SKIP_INTERCEPTOR.
In elements.cc we are sure that there are no elements on the prototype and we
have not interceptors.

[caitp, 2016/07/29 20:27:47]

Done.

+          DCHECK(it.IsFound());
+          DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
+          Handle<Object> element_k;
+
+          ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+              isolate, element_k, JSObject::GetPropertyWithAccessor(&it),
+              Nothing<bool>());
+
+          if (value->SameValueZero(*element_k)) return Just(true);
+
+          // Some mutation to the prototype elements may have occurred in
+          // accessor.
+          if (!JSObject::PrototypeHasNoElements(isolate, *receiver)) {
+            return IncludesValueSlowPath(isolate, receiver, value, k + 1,
+                                         length);
+          }
+          break;
+        }
+      }
+    }
+    return Just(false);
+  }
 };
 
 
 // Super class for all fast element arrays.
 template <typename Subclass, typename KindTraits>
 class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
  public:
   explicit FastElementsAccessor(const char* name)
       : ElementsAccessorBase<Subclass, KindTraits>(name) {}
 
@@ skipping 340 matching lines @@
         DisallowHeapAllocation no_gc;
         heap->MoveElements(FixedArray::cast(*dst_elms), dst_index, src_index,
                            len);
       }
     }
     if (hole_start != hole_end) {
       dst_elms->FillWithHoles(hole_start, hole_end);
     }
   }
 
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> receiver,
+                                       Handle<Object> search_value,
+                                       uint32_t start_from, uint32_t length) {
+    DisallowHeapAllocation no_gc;
+    FixedArrayBase* elements_base = receiver->elements();
+    Object* the_hole = isolate->heap()->the_hole_value();
+    Object* undefined = isolate->heap()->undefined_value();
+    Object* value = *search_value;
+
+    // Elements beyond the capacity of the backing store treated as undefined.
+    if (value == undefined && elements_base->length() < length) {
+      return Just(true);
+    }
+
+    if (start_from >= length) return Just(false);
+
+    if (!value->IsNumber()) {
+      if (value == undefined) {
+        // Only FAST_ELEMENTS, FAST_HOLEY_ELEMENTS, FAST_HOLEY_SMI_ELEMENTS, and
+        // FAST_HOLEY_DOUBLE_ELEMENTS can have `undefined` as a value.
+        if (!IsFastObjectElementsKind(KindTraits::Kind) &&
+            !IsFastHoleyElementsKind(KindTraits::Kind)) {
+          return Just(false);
+        }
+        if (IsFastSmiOrObjectElementsKind(KindTraits::Kind)) {

[Camillo Bruni, 2016/07/28 12:57:29]

nit: please add comments to each branch on what you are checking (it's easy to
get confused with negated vs. non-negated checks)

[caitp, 2016/07/29 20:27:47]

Done.

+          auto elements = FixedArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            Object* element_k = elements->get(k);
+
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                element_k == the_hole) {
+              return Just(true);
+            }
+            if (IsFastObjectElementsKind(KindTraits::Kind) &&
+                element_k == undefined) {
+              return Just(true);
+            }
+          }
+          return Just(false);
+        } else {
+          // Loop searching for non-Number, non-Undefined elements
+          auto elements = FixedDoubleArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                elements->is_the_hole(k)) {
+              return Just(true);
+            }
+          }
+          return Just(false);
+        }
+      } else if (!IsFastObjectElementsKind(KindTraits::Kind)) {
+        // Only Numbers can be represented as packed Smi or Double elements
+        return Just(false);
+      } else {
+        auto elements = FixedArray::cast(receiver->elements());
+
+        for (uint32_t k = start_from; k < length; ++k) {
+          Object* element_k = elements->get(k);
+          if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+              element_k == the_hole) {
+            continue;
+          }
+
+          if (value->SameValueZero(element_k)) return Just(true);
+        }
+        return Just(false);
+      }
+    } else {
+      if (!value->IsNaN()) {
+        double search_value = value->Number();
+        if (IsFastDoubleElementsKind(KindTraits::Kind)) {
+          auto elements = FixedDoubleArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                elements->is_the_hole(k)) {
+              continue;
+            }
+            if (elements->get_scalar(k) == search_value) return Just(true);
+          }
+          return Just(false);
+        } else {
+          auto elements = FixedArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            Object* element_k = elements->get(k);
+            if (element_k->IsNumber() && element_k->Number() == search_value) {
+              return Just(true);
+            }
+          }
+          return Just(false);
+        }
+      } else {
+        // NaN cannot be represented with Smi elements
+        if (IsFastSmiElementsKind(KindTraits::Kind)) return Just(false);
+
+        if (IsFastDoubleElementsKind(KindTraits::Kind)) {
+          auto elements = FixedDoubleArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (IsFastHoleyElementsKind(KindTraits::Kind) &&
+                elements->is_the_hole(k)) {
+              continue;
+            }
+            if (std::isnan(elements->get_scalar(k))) return Just(true);
+          }
+          return Just(false);
+        } else {
+          auto elements = FixedArray::cast(receiver->elements());
+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (elements->get(k)->IsNaN()) return Just(true);
+          }
+          return Just(false);
+        }
+      }
+    }
+  }
+
  private:
   // SpliceShrinkStep might modify the backing_store.
   static void SpliceShrinkStep(Isolate* isolate, Handle<JSArray> receiver,
                                Handle<FixedArrayBase> backing_store,
                                uint32_t start, uint32_t delete_count,
                                uint32_t add_count, uint32_t len,
                                uint32_t new_length) {
     const int move_left_count = len - delete_count - start;
     const int move_left_dst_index = start + add_count;
     Subclass::MoveElements(isolate, receiver, backing_store,
@@ skipping 325 matching lines @@
         ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> > {
  public:
   explicit FastHoleyDoubleElementsAccessor(const char* name)
       : FastDoubleElementsAccessor<
           FastHoleyDoubleElementsAccessor,
           ElementsKindTraits<FAST_HOLEY_DOUBLE_ELEMENTS> >(name) {}
 };
 
 
 // Super class for all external element arrays.
-template<ElementsKind Kind>
+template <ElementsKind Kind, typename ctype>

[Camillo Bruni, 2016/07/28 12:57:29]

nice :)

 class TypedElementsAccessor
-    : public ElementsAccessorBase<TypedElementsAccessor<Kind>,
-                                  ElementsKindTraits<Kind> > {
+    : public ElementsAccessorBase<TypedElementsAccessor<Kind, ctype>,
+                                  ElementsKindTraits<Kind>> {
  public:
   explicit TypedElementsAccessor(const char* name)
       : ElementsAccessorBase<AccessorClass,
                              ElementsKindTraits<Kind> >(name) {}
 
   typedef typename ElementsKindTraits<Kind>::BackingStore BackingStore;
-  typedef TypedElementsAccessor<Kind> AccessorClass;
+  typedef TypedElementsAccessor<Kind, ctype> AccessorClass;
 
   static inline void SetImpl(Handle<JSObject> holder, uint32_t entry,
                              Object* value) {
     SetImpl(holder->elements(), entry, value);
   }
 
   static inline void SetImpl(FixedArrayBase* backing_store, uint32_t entry,
                              Object* value) {
     BackingStore::cast(backing_store)->SetValue(entry, value);
   }
@@ skipping 85 matching lines @@
         Handle<Object> value = AccessorClass::GetImpl(*elements, index);
         if (get_entries) {
           value = MakeEntryPair(isolate, index, value);
         }
         values_or_entries->set(count++, *value);
       }
     }
     *nof_items = count;
     return Just(true);
   }
+
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> receiver,
+                                       Handle<Object> value,
+                                       uint32_t start_from, uint32_t length) {
+    DisallowHeapAllocation no_gc;
+    auto HasNeuteredArrayBuffer = [](JSObject* object) -> bool {

[Camillo Bruni, 2016/07/28 12:57:29]

can you just put this in a helper on this elements accessor?
I'd like to keep the code style roughly the same, makes navigation and error
spotting more efficient.

[caitp, 2016/07/29 20:27:46]

Done (moved to `static inline JSObject::HasNeuteredArrayBuffer(JSObject*
object)`) --- and then subsequently deleted after realizing it's not needed

+      switch (object->map()->instance_type()) {
+        case JS_ARRAY_BUFFER_TYPE:
+          return JSArrayBuffer::cast(object)->was_neutered();
+        case JS_DATA_VIEW_TYPE:
+        case JS_TYPED_ARRAY_TYPE: {
+          Object* buffer = static_cast<JSArrayBufferView*>(object)->buffer();
+          if (!buffer->IsJSArrayBuffer()) return false;
+          return JSArrayBuffer::cast(buffer)->was_neutered();
+        }
+        default:
+          return false;
+      }
+    };
+
+    // Don't exit early if buffers are neutred, because this is observable
+    // via a thrown exception (but should still throw early).
+    if (HasNeuteredArrayBuffer(*receiver)) {
+      return IncludesValueSlowPath(isolate, receiver, value, start_from,
+                                   length);

[Camillo Bruni, 2016/07/28 12:57:29]

nit: If we have nothing on the prototype chain we can just do an early return
here.

[caitp, 2016/07/29 20:27:46]

Actually, I think this whole thing can be removed, since the only caller never
reaches this point if the buffer is detached (because neutering the buffer sets
its length to 0, which causes the algorithm to abort early).

Removed it, and added lots of new tests for TypedArray elements

+    }
+
+    BackingStore* elements = BackingStore::cast(receiver->elements());
+    if (value->IsUndefined(isolate) && length > elements->length()) {
+      return Just(true);
+    }
+    if (!value->IsNumber()) return Just(false);
+
+    double search_value = value->Number();
+
+    if (!std::isfinite(search_value)) {
+      // Integral types cannot represent +Inf or NaN
+      if (Kind < FLOAT32_ELEMENTS || Kind > FLOAT64_ELEMENTS) {

[Camillo Bruni, 2016/07/28 12:57:29]

I think you can use kind() which is consistent across all elements accessors

[caitp, 2016/07/29 20:27:47]

Done

+        return Just(false);
+      }
+    } else if (search_value < std::numeric_limits<ctype>::min() ||

[caitp, 2016/07/29 20:27:47]

switched to numeric_limits<ctype>::lowest() rather than min()... TIL
numeric_limits<T>::min() refers to the lowest positive value (which ends up
being the same as epsilon, greater than 0). Luckily new tests caught that.

[Camillo Bruni, 2016/07/30 06:56:56]

argh, good catch!

+               search_value > std::numeric_limits<ctype>::max()) {
+      // Return false if value can't be represented in this space
+      return Just(false);
+    }
+
+    if (!std::isnan(search_value)) {
+      for (uint32_t k = start_from; k < length; ++k) {
+        double element_k = elements->get_scalar(k);
+        if (element_k == search_value) return Just(true);
+      }
+      return Just(false);
+    } else {
+      for (uint32_t k = start_from; k < length; ++k) {
+        double element_k = elements->get_scalar(k);
+        if (std::isnan(element_k)) return Just(true);
+      }
+      return Just(false);
+    }
+  }
 };
 
-
-
-#define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size)       \
-  typedef TypedElementsAccessor<TYPE##_ELEMENTS >                    \
+#define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size) \
+  typedef TypedElementsAccessor<TYPE##_ELEMENTS, ctype>        \
       Fixed##Type##ElementsAccessor;
 
 TYPED_ARRAYS(FIXED_ELEMENTS_ACCESSOR)
 #undef FIXED_ELEMENTS_ACCESSOR
 
 template <typename Subclass, typename ArgumentsAccessor, typename KindTraits>
 class SloppyArgumentsElementsAccessor
     : public ElementsAccessorBase<Subclass, KindTraits> {
  public:
   explicit SloppyArgumentsElementsAccessor(const char* name)
@@ skipping 214 matching lines @@
         list->set(insertion_index, Smi::FromInt(i), SKIP_WRITE_BARRIER);
       }
       insertion_index++;
     }
 
     Handle<FixedArrayBase> store(FixedArrayBase::cast(parameter_map->get(1)));
     return ArgumentsAccessor::DirectCollectElementIndicesImpl(
         isolate, object, store, convert, filter, list, nof_indices,
         insertion_index);
   }
+
+  static Maybe<bool> IncludesValueImpl(Isolate* isolate,
+                                       Handle<JSObject> object,
+                                       Handle<Object> value,
+                                       uint32_t start_from, uint32_t length) {
+    Handle<Map> original_map = handle(object->map(), isolate);
+    FixedArray* parameter_map = FixedArray::cast(object->elements());
+    bool search_for_hole = value->IsUndefined(isolate);
+
+    for (uint32_t k = start_from; k < length; ++k) {
+      uint32_t entry =
+          GetEntryForIndexImpl(*object, parameter_map, k, ALL_PROPERTIES);
+      if (entry == kMaxUInt32) {
+        if (search_for_hole) return Just(true);
+        continue;
+      }
+
+      Handle<Object> element_k = GetImpl(parameter_map, entry);
+
+      if (element_k->IsAccessorPair()) {
+        LookupIterator it(isolate, object, k, LookupIterator::OWN);
+        DCHECK(it.IsFound());
+        DCHECK_EQ(it.state(), LookupIterator::ACCESSOR);
+        ASSIGN_RETURN_ON_EXCEPTION_VALUE(isolate, element_k,
+                                         Object::GetPropertyWithAccessor(&it),
+                                         Nothing<bool>());
+
+        if (value->SameValueZero(*element_k)) return Just(true);
+
+        if (object->map() != *original_map) {
+          // Some mutation occurred in accessor. Abort "fast" path
+          return IncludesValueSlowPath(isolate, object, value, k + 1, length);
+        }
+      } else if (value->SameValueZero(*element_k)) {
+        return Just(true);
+      }
+    }
+    return Just(false);
+  }
 };
 
 
 class SlowSloppyArgumentsElementsAccessor
     : public SloppyArgumentsElementsAccessor<
           SlowSloppyArgumentsElementsAccessor, DictionaryElementsAccessor,
           ElementsKindTraits<SLOW_SLOPPY_ARGUMENTS_ELEMENTS> > {
  public:
   explicit SlowSloppyArgumentsElementsAccessor(const char* name)
       : SloppyArgumentsElementsAccessor<
@@ skipping 587 matching lines @@
     insertion_index += len;
   }
 
   DCHECK_EQ(insertion_index, result_len);
   return result_array;
 }
 
 ElementsAccessor** ElementsAccessor::elements_accessors_ = NULL;
 }  // namespace internal
 }  // namespace v8