[builtins] implement Array.prototype.includes in TurboFan

src/elements.cc

Index: src/elements.cc
diff --git a/src/elements.cc b/src/elements.cc
index 7db641649f5ba204b17806f94144fb9e6dc59eaf..8226d375158760b6e8fb623443c9b6f833c9a914 100644
--- a/src/elements.cc
+++ b/src/elements.cc
@@ -468,6 +468,27 @@ static void SortIndices(
   }
 }
 
+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
@@ -1084,6 +1105,20 @@ class ElementsAccessorBase : public ElementsAccessor {
     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;
@@ -1420,6 +1455,84 @@ class DictionaryElementsAccessor
       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);
+  }
 };
 
 
@@ -1780,6 +1893,128 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
     }
   }
 
+  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,
@@ -2125,17 +2360,17 @@ class FastHoleyDoubleElementsAccessor
 
 
 // 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) {
@@ -2241,12 +2476,71 @@ class TypedElementsAccessor
     *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

+    }
 
-#define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size)       \
-  typedef TypedElementsAccessor<TYPE##_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, ctype>        \
       Fixed##Type##ElementsAccessor;
 
 TYPED_ARRAYS(FIXED_ELEMENTS_ACCESSOR)
@@ -2481,6 +2775,45 @@ class SloppyArgumentsElementsAccessor
         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);
+  }
 };