[builtins] WIP: Array indexOf in TurboFan/Runtime

src/elements.cc

Index: src/elements.cc
diff --git a/src/elements.cc b/src/elements.cc
index 29fa4fb08c8bdaef6bda5d26794b4deab44a962c..50f77e90cef0d465ea9de847bab4d079c5db5c20 100644
--- a/src/elements.cc
+++ b/src/elements.cc
@@ -489,6 +489,26 @@ static Maybe<bool> IncludesValueSlowPath(Isolate* isolate,
   return Just(false);
 }
 
+static Maybe<int32_t> IndexOfValueSlowPath(Isolate* isolate,
+                                           Handle<JSObject> receiver,
+                                           Handle<Object> value,
+                                           uint32_t start_from,
+                                           uint32_t length) {
+  for (uint32_t k = start_from; k < length; ++k) {
+    LookupIterator it(isolate, receiver, k);
+    if (!it.IsFound()) {
+      continue;
+    }
+    Handle<Object> element_k;
+    ASSIGN_RETURN_ON_EXCEPTION_VALUE(
+        isolate, element_k, Object::GetProperty(&it), Nothing<int32_t>());
+
+    if (value->StrictEquals(*element_k)) return Just(static_cast<int32_t>(k));
+  }
+
+  return Just(-1);
+}
+
 // Base class for element handler implementations. Contains the
 // the common logic for objects with different ElementsKinds.
 // Subclasses must specialize method for which the element
@@ -1123,6 +1143,20 @@ class ElementsAccessorBase : public ElementsAccessor {
                                        length);
   }
 
+  static Maybe<int32_t> IndexOfValueImpl(Isolate* isolate,
+                                         Handle<JSObject> receiver,
+                                         Handle<Object> value,
+                                         uint32_t start_from, uint32_t length) {
+    return IndexOfValueSlowPath(isolate, receiver, value, start_from, length);
+  }
+
+  Maybe<int32_t> IndexOfValue(Isolate* isolate, Handle<JSObject> receiver,
+                              Handle<Object> value, uint32_t start_from,
+                              uint32_t length) final {
+    return Subclass::IndexOfValueImpl(isolate, receiver, value, start_from,
+                                      length);
+  }
+
   static uint32_t GetIndexForEntryImpl(FixedArrayBase* backing_store,
                                        uint32_t entry) {
     return entry;
@@ -1571,6 +1605,68 @@ class DictionaryElementsAccessor
     }
     return Just(false);
   }
+
+  static Maybe<int32_t> IndexOfValueImpl(Isolate* isolate,
+                                         Handle<JSObject> receiver,
+                                         Handle<Object> value,
+                                         uint32_t start_from, uint32_t length) {
+    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));
+
+    Handle<SeededNumberDictionary> dictionary(
+        SeededNumberDictionary::cast(receiver->elements()), isolate);
+    // Iterate through entire range, as accessing elements out of order is
+    // observable

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: trailing full stop.

[mattloring, 2016/08/17 23:27:21]

Done.

+    for (uint32_t k = start_from; k < length; ++k) {
+      int entry = dictionary->FindEntry(k);
+      if (entry == SeededNumberDictionary::kNotFound) {
+        continue;
+      }
+
+      PropertyDetails details = GetDetailsImpl(*dictionary, entry);
+      switch (details.kind()) {
+        case kData: {
+          Object* element_k = dictionary->ValueAt(entry);
+          if (value->StrictEquals(element_k))
+            return Just(static_cast<int32_t>(k));

[Jakob Kummerow, 2016/08/17 15:42:58]

Who guarantees that k is in int32_t range?

Also, nit:

if (it doesn't fit on one line) {
  then it requires braces;
}

[mattloring, 2016/08/18 19:03:10]

Done.

+          break;
+        }
+        case kAccessor: {
+          LookupIterator it(isolate, receiver, k,
+                            LookupIterator::OWN_SKIP_INTERCEPTOR);
+          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<int32_t>());
+
+          if (value->StrictEquals(*element_k))
+            return Just(static_cast<int32_t>(k));

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: braces

[mattloring, 2016/08/17 23:27:20]

Done.

+
+          // Bailout to slow path if elements on prototype changed

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: trailing full stop.

[mattloring, 2016/08/17 23:27:20]

Done.

+          if (!JSObject::PrototypeHasNoElements(isolate, *receiver)) {
+            return IndexOfValueSlowPath(isolate, receiver, value, k + 1,
+                                        length);
+          }
+
+          // Continue if elements unchanged

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: trailing full stop.

[mattloring, 2016/08/17 23:27:20]

Done.

+          if (*dictionary == receiver->elements()) continue;
+
+          // Otherwise, bailout or update elements

[Jakob Kummerow, 2016/08/17 15:42:59]

nit: trailing full stop.

[mattloring, 2016/08/17 23:27:20]

Done.

+          if (receiver->GetElementsKind() != DICTIONARY_ELEMENTS) {
+            // Otherwise, switch to slow path.
+            return IndexOfValueSlowPath(isolate, receiver, value, k + 1,
+                                        length);
+          }
+          dictionary = handle(
+              SeededNumberDictionary::cast(receiver->elements()), isolate);
+          break;
+        }
+      }
+    }
+    return Just(-1);
+  }
 };
 
 
@@ -2081,6 +2177,113 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
     }
   }
 
+  static Maybe<int32_t> IndexOfValueImpl(Isolate* isolate,
+                                         Handle<JSObject> receiver,
+                                         Handle<Object> search_value,
+                                         uint32_t start_from, uint32_t length) {
+    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));
+    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;
+
+    if (start_from >= length) return Just(-1);
+
+    length = std::min(static_cast<uint32_t>(elements_base->length()), length);
+
+    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.

[Jakob Kummerow, 2016/08/17 15:42:58]

The comment below contradicts this, saying that FAST_HOLEY_DOUBLE_ELEMENTS
cannot contain undefined (which I agree with; due to the HasProperty check the
hole does not count as undefined for the purposes of indexOf()). If they can't,
then neither can FAST_HOLEY_SMI_ELEMENTS, leaving only FAST_{,HOLEY_}ELEMENTS,
and the code below can be simplified a lot.

[mattloring, 2016/08/18 19:03:10]

Done.

+        if (!IsFastObjectElementsKind(Subclass::kind()) &&
+            !IsFastHoleyElementsKind(Subclass::kind())) {

[Jakob Kummerow, 2016/08/17 15:42:59]

This line can go.

[mattloring, 2016/08/18 19:03:10]

Shouldn't the check for FAST_ELEMENTS/FAST_HOLEY_ELEMENTS remain since these are
the cases where we can bail out without searching for undefined?

+          return Just(-1);
+        }
+
+        // Search for `undefined` in FAST_ELEMENTS,
+        // FAST_HOLEY_ELEMENTS or FAST_HOLEY_SMI_ELEMENTS
+        if (IsFastSmiOrObjectElementsKind(Subclass::kind())) {

[Jakob Kummerow, 2016/08/17 15:42:58]

This check (including its comment) can go.

[mattloring, 2016/08/18 19:03:10]

Done.

+          auto elements = FixedArray::cast(receiver->elements());

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: s/auto/FixedArray*/

[mattloring, 2016/08/17 23:27:21]

Done.

+
+          for (uint32_t k = start_from; k < length; ++k) {
+            Object* element_k = elements->get(k);

[Jakob Kummerow, 2016/08/17 15:42:59]

I'd inline this.

[mattloring, 2016/08/17 23:27:21]

Done.

+            if (IsFastObjectElementsKind(Subclass::kind()) &&

[Jakob Kummerow, 2016/08/17 15:42:58]

No elements kind check necessary here

[mattloring, 2016/08/18 19:03:10]

Done.

+                element_k == undefined) {
+              return Just(static_cast<int32_t>(k));
+            }
+          }
+          return Just(-1);
+        } else {

[Jakob Kummerow, 2016/08/17 15:42:58]

The entire else-block is unnecessary

[mattloring, 2016/08/18 19:03:10]

Done.

+          // FAST_HOLEY_DOUBLE_ELEMENTS cannot contain `undefined`
+          DCHECK_EQ(Subclass::kind(), FAST_HOLEY_DOUBLE_ELEMENTS);
+          return Just(-1);
+        }
+      } else if (!IsFastObjectElementsKind(Subclass::kind())) {

[Jakob Kummerow, 2016/08/17 15:42:58]

This entire block is subsumed by the above.

[mattloring, 2016/08/18 19:03:10]

Done.

+        // Search for non-number, non-Undefined value, with either
+        // FAST_SMI_ELEMENTS, FAST_DOUBLE_ELEMENTS, FAST_HOLEY_SMI_ELEMENTS or
+        // FAST_HOLEY_DOUBLE_ELEMENTS. Guaranteed to return false, since these
+        // elements kinds can only contain Number values or undefined.
+        return Just(-1);
+      } else {
+        // Search for non-number, non-Undefined value with either
+        // FAST_ELEMENTS or FAST_HOLEY_ELEMENTS.
+        DCHECK(IsFastObjectElementsKind(Subclass::kind()));
+        auto elements = FixedArray::cast(receiver->elements());

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: s/auto/FixedArray*/

[mattloring, 2016/08/17 23:27:21]

Done.

+
+        for (uint32_t k = start_from; k < length; ++k) {
+          Object* element_k = elements->get(k);
+          if (IsFastHoleyElementsKind(Subclass::kind()) &&
+              element_k == the_hole) {
+            continue;
+          }
+
+          if (value->StrictEquals(element_k)) {
+            return Just(static_cast<int32_t>(k));
+          }
+        }
+        return Just(-1);
+      }
+    } else {
+      if (!value->IsNaN()) {

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: reduce indentation by reversing order:

// NaN can never be found by strict equality.
if (value->IsNaN()) return Just(-1);

// <continue with non-NaN case>

[mattloring, 2016/08/18 19:03:10]

Done.

+        double search_value = value->Number();
+        if (IsFastDoubleElementsKind(Subclass::kind())) {
+          // Search for non-NaN Number in FAST_DOUBLE_ELEMENTS or

[Jakob Kummerow, 2016/08/17 15:42:58]

I don't understand what value this comment adds?

[mattloring, 2016/08/18 19:03:10]

Done.

+          // FAST_HOLEY_DOUBLE_ELEMENTS --- Skip TheHole, and trust UCOMISD or
+          // similar operation for result.
+          auto elements = FixedDoubleArray::cast(receiver->elements());

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: s/auto/FixedDoubleArray*/

[mattloring, 2016/08/17 23:27:20]

Done.

+
+          for (uint32_t k = start_from; k < length; ++k) {
+            if (IsFastHoleyElementsKind(Subclass::kind()) &&
+                elements->is_the_hole(k)) {
+              continue;
+            }
+            if (elements->get_scalar(k) == search_value) {
+              return Just(static_cast<int32_t>(k));
+            }
+          }
+          return Just(-1);
+        } else {
+          // Search for non-NaN Number in FAST_ELEMENTS, FAST_HOLEY_ELEMENTS,
+          // FAST_SMI_ELEMENTS or FAST_HOLEY_SMI_ELEMENTS --- Skip non-Numbers,
+          // and trust UCOMISD or similar operation for result

[Jakob Kummerow, 2016/08/17 15:42:59]

nit: if you think this comment is useful enough to stay, add a trailing full
stop.

[mattloring, 2016/08/18 19:03:10]

Done.

+          auto elements = FixedArray::cast(receiver->elements());

[Jakob Kummerow, 2016/08/17 15:42:59]

nit: s/auto/FixedArray*/

[mattloring, 2016/08/17 23:27:21]

Done.

+
+          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(static_cast<int32_t>(k));
+            }
+          }
+          return Just(-1);
+        }
+      } else {
+        // NaN can never be found by strict equality.
+        return Just(-1);
+      }
+    }
+  }
+
  private:
   // SpliceShrinkStep might modify the backing_store.
   static void SpliceShrinkStep(Isolate* isolate, Handle<JSArray> receiver,
@@ -2591,6 +2794,45 @@ class TypedElementsAccessor
       return Just(false);
     }
   }
+
+  static Maybe<int32_t> IndexOfValueImpl(Isolate* isolate,
+                                         Handle<JSObject> receiver,
+                                         Handle<Object> value,
+                                         uint32_t start_from, uint32_t length) {
+    DCHECK(JSObject::PrototypeHasNoElements(isolate, *receiver));
+    DisallowHeapAllocation no_gc;
+
+    BackingStore* elements = BackingStore::cast(receiver->elements());
+    if (!value->IsNumber()) return Just(-1);
+
+    double search_value = value->Number();
+
+    if (!std::isfinite(search_value)) {
+      // Integral types cannot represent +Inf or NaN

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: trailing full stop.

[mattloring, 2016/08/17 23:27:21]

Done.

+      if (AccessorClass::kind() < FLOAT32_ELEMENTS ||
+          AccessorClass::kind() > FLOAT64_ELEMENTS) {
+        return Just(-1);
+      }
+    } else if (search_value < std::numeric_limits<ctype>::lowest() ||
+               search_value > std::numeric_limits<ctype>::max()) {
+      // Return false if value can't be represented in this space

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: trailing full stop. s/space/ElementsKind/?

[mattloring, 2016/08/17 23:27:20]

Done.

+      return Just(-1);
+    }
+
+    // Prototype has no elements, and not searching for the hole --- limit
+    // search to backing store length.
+    if (static_cast<uint32_t>(elements->length()) < length) {
+      length = elements->length();
+    }
+
+    if (!std::isnan(search_value)) {

[Jakob Kummerow, 2016/08/17 15:42:58]

Again, reverse the order, just return -1 early in case of NaN.

[mattloring, 2016/08/18 19:03:10]

Done.

+      for (uint32_t k = start_from; k < length; ++k) {
+        double element_k = elements->get_scalar(k);

[Jakob Kummerow, 2016/08/17 15:42:58]

s/double/ctype/; search_value should be of type |ctype| at this point too

[mattloring, 2016/08/18 19:03:11]

Done.

+        if (element_k == search_value) return Just(static_cast<int32_t>(k));

[Jakob Kummerow, 2016/08/17 15:42:59]

Who guarantees that k is in int32_t range?

[mattloring, 2016/08/18 19:03:10]

Done.

+      }
+    }
+    return Just(-1);
+  }
 };
 
 #define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size) \
@@ -2869,6 +3111,45 @@ class SloppyArgumentsElementsAccessor
     }
     return Just(false);
   }
+
+  static Maybe<int32_t> IndexOfValueImpl(Isolate* isolate,
+                                         Handle<JSObject> object,
+                                         Handle<Object> value,
+                                         uint32_t start_from, uint32_t length) {
+    DCHECK(JSObject::PrototypeHasNoElements(isolate, *object));
+    Handle<Map> original_map = handle(object->map(), isolate);
+    FixedArray* parameter_map = FixedArray::cast(object->elements());
+
+    for (uint32_t k = start_from; k < length; ++k) {
+      uint32_t entry =
+          GetEntryForIndexImpl(*object, parameter_map, k, ALL_PROPERTIES);
+      if (entry == kMaxUInt32) {
+        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<int32_t>());
+
+        if (value->StrictEquals(*element_k))
+          return Just(static_cast<int32_t>(k));

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: braces

[mattloring, 2016/08/17 23:27:21]

Done.

+
+        if (object->map() != *original_map) {
+          // Some mutation occurred in accessor. Abort "fast" path

[Jakob Kummerow, 2016/08/17 15:42:58]

nit: trailing full stop.

[mattloring, 2016/08/17 23:27:21]

Done.

+          return IndexOfValueSlowPath(isolate, object, value, k + 1, length);
+        }
+      } else if (value->StrictEquals(*element_k)) {
+        return Just(static_cast<int32_t>(k));
+      }
+    }
+    return Just(-1);
+  }
 };