[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..48145df2943a34b74a48e56f6c25de19cae217fe 100644
--- a/src/elements.cc
+++ b/src/elements.cc
@@ -489,6 +489,26 @@ static Maybe<bool> IncludesValueSlowPath(Isolate* isolate,
   return Just(false);
 }
 
+static Maybe<int64_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<int64_t>());
+
+    if (value->StrictEquals(*element_k)) return Just<int64_t>(k);
+  }
+
+  return Just<int64_t>(-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<int64_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<int64_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<int64_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.
+    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<int64_t>(k);
+          }
+          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<int64_t>());
+
+          if (value->StrictEquals(*element_k)) return Just<int64_t>(k);
+
+          // Bailout to slow path if elements on prototype changed.
+          if (!JSObject::PrototypeHasNoElements(isolate, *receiver)) {
+            return IndexOfValueSlowPath(isolate, receiver, value, k + 1,
+                                        length);
+          }
+
+          // Continue if elements unchanged.
+          if (*dictionary == receiver->elements()) continue;
+
+          // Otherwise, bailout or update elements.
+          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<int64_t>(-1);
+  }
 };
 
 
@@ -2081,6 +2177,73 @@ class FastElementsAccessor : public ElementsAccessorBase<Subclass, KindTraits> {
     }
   }
 
+  static Maybe<int64_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<int64_t>(-1);
+
+    length = std::min(static_cast<uint32_t>(elements_base->length()), length);
+
+    if (!value->IsNumber()) {

[Jakob Kummerow, 2016/08/19 09:49:56]

Try this simplification:

    // Only FAST_{,HOLEY_}ELEMENTS can store non-numbers.
    if (!value->IsNumber() && 
        !IsFastObjectElementsKind(Subclass::kind())) {
      return Just<int64_t>(-1);
    }
    // NaN can never be found by strict equality.
    if (value->IsNaN()) return Just<int64_t>(-1);

    FixedArray* elements = FixedArray::cast(receiver->elements());
    for (uint32_t k = start_from; k < length; ++k) {
      if (value->StrictEquals(elements->get(k))) return Just<int64_t>(k);
    }
    return Just<int64_t>(-1);

I'd special-case numbers only if it makes a measurable performance difference.
Does it?

Also, now that this is not correct for FAST_DOUBLE_ELEMENTS any more, it should
move to the FastSmiOrObjectElementsAccessor class.

[mattloring, 2016/08/19 17:22:33]

I did not observe a performance difference so I've eliminated the number
specific path. In what way is this incorrect for FAST_DOUBLE_ELEMENTS?

[Jakob Kummerow, 2016/08/22 09:54:10]

FixedArray::cast(receiver->elements()) only works for smi/object elements; for
double elements it would have to be FixedDoubleArray::cast(...).

[mattloring, 2016/08/22 17:07:03]

Ah ok, that makes sense. Thanks!

+      if (value == undefined) {
+        // Only FAST_ELEMENTS and FAST_HOLEY_ELEMENTS can have
+        // `undefined` as a value.
+        if (!IsFastElementsKind(Subclass::kind()) &&

[Jakob Kummerow, 2016/08/19 09:49:56]

This is the FastElementsAccessor. All Subclass::kind()s are fast.
("IsFastElementsKind(kind)" is very different from "kind == FAST_ELEMENTS"!)

[mattloring, 2016/08/19 17:22:33]

Thank you for the clarification. This check is no longer needed in the updated
function.

+            !IsFastHoleyElementsKind(Subclass::kind())) {
+          return Just<int64_t>(-1);
+        }
+
+        FixedArray* elements = FixedArray::cast(receiver->elements());
+
+        for (uint32_t k = start_from; k < length; ++k) {
+          if (elements->get(k) == undefined) {
+            return Just<int64_t>(k);
+          }
+        }
+        return Just<int64_t>(-1);
+      } else {
+        // Search for non-number, non-Undefined value with either
+        // FAST_ELEMENTS or FAST_HOLEY_ELEMENTS.
+        DCHECK(IsFastObjectElementsKind(Subclass::kind()));
+        FixedArray* elements = FixedArray::cast(receiver->elements());
+
+        for (uint32_t k = start_from; k < length; ++k) {
+          Object* element_k = elements->get(k);
+          if (element_k == the_hole) {
+            continue;
+          }
+
+          if (value->StrictEquals(element_k)) {
+            return Just<int64_t>(k);
+          }
+        }
+        return Just<int64_t>(-1);
+      }
+    } else {
+      if (value->IsNaN()) {
+        return Just<int64_t>(-1);
+      }
+      double search_value = value->Number();
+      FixedArray* 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<int64_t>(k);
+        }
+      }
+      return Just<int64_t>(-1);
+    }
+  }
+
  private:
   // SpliceShrinkStep might modify the backing_store.
   static void SpliceShrinkStep(Isolate* isolate, Handle<JSArray> receiver,
@@ -2398,6 +2561,39 @@ class FastDoubleElementsAccessor
       break;
     }
   }
+
+  static Maybe<int64_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* value = *search_value;
+
+    if (start_from >= length) return Just<int64_t>(-1);
+
+    length = std::min(static_cast<uint32_t>(elements_base->length()), length);
+
+    if (!value->IsNumber()) {
+      return Just<int64_t>(-1);
+    }
+    if (value->IsNaN()) {
+      return Just<int64_t>(-1);
+    }
+    double numeric_search_value = value->Number();
+    FixedDoubleArray* elements = FixedDoubleArray::cast(receiver->elements());
+
+    for (uint32_t k = start_from; k < length; ++k) {
+      if (elements->is_the_hole(k)) {

[Jakob Kummerow, 2016/08/19 09:49:56]

(Just for the record: if everything does fit on one line, e.g. "if (foo) bar;",
then keeping it on one line without braces is fine. That said, splitting it into
two lines and adding braces like you've done here is fine too.)

[mattloring, 2016/08/19 17:22:33]

Ack. Thanks for clarifying.

+        continue;
+      }
+      if (elements->get_scalar(k) == numeric_search_value) {
+        return Just<int64_t>(k);
+      }
+    }
+    return Just<int64_t>(-1);
+  }
 };
 
 
@@ -2591,6 +2787,46 @@ class TypedElementsAccessor
       return Just(false);
     }
   }
+
+  static Maybe<int64_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<int64_t>(-1);
+
+    double search_value = value->Number();
+
+    if (!std::isfinite(search_value)) {
+      // Integral types cannot represent +Inf or NaN.
+      if (AccessorClass::kind() < FLOAT32_ELEMENTS ||
+          AccessorClass::kind() > FLOAT64_ELEMENTS) {
+        return Just<int64_t>(-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 ElementsKind.
+      return Just<int64_t>(-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)) {
+      return Just<int64_t>(-1);
+    }
+    for (uint32_t k = start_from; k < length; ++k) {
+      ctype element_k = elements->get_scalar(k);
+      if (element_k == search_value) return Just<int64_t>(k);

[Jakob Kummerow, 2016/08/19 09:49:56]

This still does an implicit cast to double, which is silly for int/uint typed
elements. I'd suggest:

    ctype typed_search_value = static_cast<ctype>(search_value);
    if (static_cast<double>(typed_search_value) != search_value) {
      return Just<int64_t>(-1);  // Loss of precision.
    }

outside the loop, and then comparing against typed_search_value.

[mattloring, 2016/08/19 17:22:33]

Done.

+    }
+    return Just<int64_t>(-1);
+  }
 };
 
 #define FIXED_ELEMENTS_ACCESSOR(Type, type, TYPE, ctype, size) \
@@ -2869,6 +3105,46 @@ class SloppyArgumentsElementsAccessor
     }
     return Just(false);
   }
+
+  static Maybe<int64_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<int64_t>());
+
+        if (value->StrictEquals(*element_k)) {
+          return Just<int64_t>(k);
+        }
+
+        if (object->map() != *original_map) {
+          // Some mutation occurred in accessor. Abort "fast" path.
+          return IndexOfValueSlowPath(isolate, object, value, k + 1, length);
+        }
+      } else if (value->StrictEquals(*element_k)) {
+        return Just<int64_t>(k);
+      }
+    }
+    return Just<int64_t>(-1);
+  }
 };