Replace PushIfAbsent by a Stack object

src/js/array.js

 // 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.
 
 (function(global, utils, extrasUtils) {
 
 "use strict";
 
 %CheckIsBootstrapping();
 
@@ skipping 56 matching lines @@
     var result = ObjectDefineProperty(array, i, {
       value: value, writable: true, configurable: true, enumerable: true
     });
     if (!result) throw MakeTypeError(kStrictCannotAssign, i);
   } else {
     AddIndexedProperty(array, i, value);
   }
 }
 
 
-// Global list of arrays visited during toString, toLocaleString and
-// join invocations.
-var visited_arrays = new InternalArray();
-
-
 // Gets a sorted array of array keys.  Useful for operations on sparse
 // arrays.  Dupes have not been removed.
 function GetSortedArrayKeys(array, indices) {
   var keys = new InternalArray();
   if (IS_NUMBER(indices)) {
     // It's an interval
     var limit = indices;
     for (var i = 0; i < limit; ++i) {
       var e = array[i];
       if (!IS_UNDEFINED(e) || i in array) {
@@ skipping 51 matching lines @@
       var e = array[key];
       if (!IS_STRING(e)) e = convert(e);
       elements[elements_length++] = e;
       last_key = key;
     }
   }
   return %StringBuilderConcat(elements, elements_length, '');
 }
 
 
+function StringBuilderJoin(elements, length, separator) {
+  length = MinSimple(elements.length, length);
+  if (length == 0) return "";
+  var result = elements[0];
+  for (var i = 1; i < length; i++) {
+    result = result + separator + elements[i];
+  }
+  return result;
+}
+
+
 function UseSparseVariant(array, length, is_array, touched) {
   // Only use the sparse variant on arrays that are likely to be sparse and the
   // number of elements touched in the operation is relatively small compared to
   // the overall size of the array.
   if (!is_array || length < 1000 || %IsObserved(array) ||
       %HasComplexElements(array)) {
     return false;
   }
   if (!%_IsSmi(length)) {
     return true;
   }
   var elements_threshold = length >> 2;  // No more than 75% holes
   var estimated_elements = %EstimateNumberOfElements(array);
   return (estimated_elements < elements_threshold) &&
     (touched > estimated_elements * 4);
 }
 
+function Stack() {
+  this.length = 0;
+  this.values = new InternalArray();
+}
+
+Stack.prototype.length = null;

[adamk, 2016/03/10 19:53:54]

Please add a comment noting that these are to mask any possible Object.prototype
properties, as well as a regression test showing that these two properties are
properly handled even if Object.prototype is mucked with. Otherwise I'd worry
that someone might remove them in a "cleanup"

+Stack.prototype.values = null;
+
+function StackPush(stack, value) {
+  stack.values[stack.length++] = value;
+}
+
+function StackPop(stack) {
+  stack.values[--stack.length] = null
+}
+
+function StackHas(stack, v) {
+  var length = stack.length;
+  var values = stack.values;
+  for (var i = 0; i < length; i++) {
+    if (values[i] === v) return true;
+  }
+  return false;
+}
+
+// Global list of arrays visited during toString, toLocaleString and
+// join invocations.
+var visited_arrays = new Stack();
 
 function Join(array, length, separator, convert) {
   if (length == 0) return '';
 
   var is_array = IS_ARRAY(array);
 
   if (is_array) {
     // If the array is cyclic, return the empty string for already
     // visited arrays.
-    if (!%PushIfAbsent(visited_arrays, array)) return '';
+    if (StackHas(visited_arrays, array)) return '';
+    StackPush(visited_arrays, array);
   }
 
   // Attempt to convert the elements.
   try {
     if (UseSparseVariant(array, length, is_array, length)) {
       %NormalizeElements(array);
       if (separator.length == 0) {
         return SparseJoin(array, length, convert);
       } else {
         return SparseJoinWithSeparatorJS(array, length, convert, separator);
@@ skipping 38 matching lines @@
       for (var i = 1; i < length; i++) {
         e = array[i];
         if (IS_NUMBER(e)) {
           e = %_NumberToString(e);
         } else if (!IS_STRING(e)) {
           e = convert(e);
         }
         elements[i] = e;
       }
     }
-    return %StringBuilderJoin(elements, length, separator);
+    return StringBuilderJoin(elements, length, separator);
   } finally {
     // Make sure to remove the last element of the visited array no
     // matter what happens.
-    if (is_array) visited_arrays.length = visited_arrays.length - 1;
+    if (is_array) StackPop(visited_arrays);
   }
 }
 
 
 function ConvertToString(x) {
   if (IS_NULL_OR_UNDEFINED(x)) {
     return '';
   } else {
     return TO_STRING(x);
   }
@@ skipping 1699 matching lines @@
   to.InnerArrayIncludes = InnerArrayIncludes;
   to.InnerArrayIndexOf = InnerArrayIndexOf;
   to.InnerArrayJoin = InnerArrayJoin;
   to.InnerArrayLastIndexOf = InnerArrayLastIndexOf;
   to.InnerArrayReduce = InnerArrayReduce;
   to.InnerArrayReduceRight = InnerArrayReduceRight;
   to.InnerArraySome = InnerArraySome;
   to.InnerArraySort = InnerArraySort;
   to.InnerArrayToLocaleString = InnerArrayToLocaleString;
   to.PackedArrayReverse = PackedArrayReverse;
+  to.Stack = Stack;
+  to.StackHas = StackHas;
+  to.StackPush = StackPush;
+  to.StackPop = StackPop;
 });
 
 %InstallToContext([
   "array_pop", ArrayPop,
   "array_push", ArrayPush,
   "array_shift", ArrayShift,
   "array_splice", ArraySplice,
   "array_slice", ArraySlice,
   "array_unshift", ArrayUnshift,
 ]);
 
 });