src/jdk/nashorn/internal/runtime/arrays/SparseArrayData.java

*** 34,43 ****
--- 34,44 ----
  
  /**
   * Handle arrays where the index is very large.
   */
  class SparseArrayData extends ArrayData {
+     /** Maximum size for dense arrays */
      static final int MAX_DENSE_LENGTH = 1024 * 1024;
  
      /** Underlying array. */
      private ArrayData underlying;
  
*** 49,59 ****
  
      SparseArrayData(final ArrayData underlying, final long length) {
          this(underlying, length, new TreeMap<Long, Object>());
      }
  
!     SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
          super(length);
          assert underlying.length() <= length;
          this.underlying = underlying;
          this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length());
          this.sparseMap = sparseMap;
--- 50,60 ----
  
      SparseArrayData(final ArrayData underlying, final long length) {
          this(underlying, length, new TreeMap<Long, Object>());
      }
  
!     private SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
          super(length);
          assert underlying.length() <= length;
          this.underlying = underlying;
          this.maxDenseLength = Math.max(MAX_DENSE_LENGTH, underlying.length());
          this.sparseMap = sparseMap;
*** 87,128 ****
  
          return objArray;
      }
  
      @Override
!     public void shiftLeft(final int by) {
!         underlying.shiftLeft(by);
  
          final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
  
          for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
              final long newIndex = entry.getKey().longValue() - by;
              if (newIndex < maxDenseLength) {
!                 underlying = underlying.set((int) newIndex, entry.getValue(), false);
!             } else if (newIndex >= 0) {
                  newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
              }
          }
  
          sparseMap = newSparseMap;
          setLength(Math.max(length() - by, 0));
      }
  
      @Override
      public ArrayData shiftRight(final int by) {
          final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
          final long len = underlying.length();
          if (len + by > maxDenseLength) {
!             for (long i = maxDenseLength - by; i < len; i++) {
                  if (underlying.has((int) i)) {
                      newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i));
                  }
              }
!             underlying = underlying.shrink((int) (maxDenseLength - by));
          }
  
!         underlying.shiftRight(by);
  
          for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
              final long newIndex = entry.getKey().longValue() + by;
              newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
          }
--- 88,140 ----
  
          return objArray;
      }
  
      @Override
!     public ArrayData shiftLeft(final int by) {
!         underlying = underlying.shiftLeft(by);
  
          final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
  
          for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
              final long newIndex = entry.getKey().longValue() - by;
+             if (newIndex >= 0) {
                  if (newIndex < maxDenseLength) {
!                     final long oldLength = underlying.length();
!                     underlying = underlying.ensure(newIndex)
!                             .set((int) newIndex, entry.getValue(), false)
!                             .safeDelete(oldLength, newIndex - 1, false);
!                 } else {
                      newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
                  }
              }
+         }
  
          sparseMap = newSparseMap;
          setLength(Math.max(length() - by, 0));
+ 
+         return sparseMap.isEmpty() ? underlying : this;
      }
  
      @Override
      public ArrayData shiftRight(final int by) {
          final TreeMap<Long, Object> newSparseMap = new TreeMap<>();
+         // Move elements from underlying to sparse map if necessary
          final long len = underlying.length();
          if (len + by > maxDenseLength) {
!             // Length of underlying array after shrinking, before right-shifting
!             final long tempLength = Math.max(0, maxDenseLength - by);
!             for (long i = tempLength; i < len; i++) {
                  if (underlying.has((int) i)) {
                      newSparseMap.put(Long.valueOf(i + by), underlying.getObject((int) i));
                  }
              }
!             underlying = underlying.shrink((int) tempLength);
!             underlying.setLength(tempLength);
          }
  
!         underlying = underlying.shiftRight(by);
  
          for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
              final long newIndex = entry.getKey().longValue() + by;
              newSparseMap.put(Long.valueOf(newIndex), entry.getValue());
          }
*** 133,150 ****
          return this;
      }
  
      @Override
      public ArrayData ensure(final long safeIndex) {
-         // Usually #ensure only needs to be called if safeIndex is greater or equal current length.
-         // SparseArrayData is an exception as an index smaller than our current length may still
-         // exceed the underlying ArrayData's capacity. Because of this, SparseArrayData invokes
-         // its ensure method internally in various places where other ArrayData subclasses don't,
-         // making it safe for outside uses to only call ensure(safeIndex) if safeIndex >= length.
-         if (safeIndex < maxDenseLength && underlying.length() <= safeIndex) {
-             underlying = underlying.ensure(safeIndex);
-         }
          if (safeIndex >= length()) {
              setLength(safeIndex + 1);
          }
          return this;
      }
--- 145,154 ----
*** 165,176 ****
  
      @Override
      public ArrayData set(final int index, final Object value, final boolean strict) {
          if (index >= 0 && index < maxDenseLength) {
              final long oldLength = underlying.length();
!             ensure(index);
!             underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
              setLength(Math.max(underlying.length(), length()));
          } else {
              final Long longIndex = indexToKey(index);
              sparseMap.put(longIndex, value);
              setLength(Math.max(longIndex + 1, length()));
--- 169,179 ----
  
      @Override
      public ArrayData set(final int index, final Object value, final boolean strict) {
          if (index >= 0 && index < maxDenseLength) {
              final long oldLength = underlying.length();
!             underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);
              setLength(Math.max(underlying.length(), length()));
          } else {
              final Long longIndex = indexToKey(index);
              sparseMap.put(longIndex, value);
              setLength(Math.max(longIndex + 1, length()));
*** 181,192 ****
  
      @Override
      public ArrayData set(final int index, final int value, final boolean strict) {
          if (index >= 0 && index < maxDenseLength) {
              final long oldLength = underlying.length();
!             ensure(index);
!             underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
              setLength(Math.max(underlying.length(), length()));
          } else {
              final Long longIndex = indexToKey(index);
              sparseMap.put(longIndex, value);
              setLength(Math.max(longIndex + 1, length()));
--- 184,194 ----
  
      @Override
      public ArrayData set(final int index, final int value, final boolean strict) {
          if (index >= 0 && index < maxDenseLength) {
              final long oldLength = underlying.length();
!             underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);
              setLength(Math.max(underlying.length(), length()));
          } else {
              final Long longIndex = indexToKey(index);
              sparseMap.put(longIndex, value);
              setLength(Math.max(longIndex + 1, length()));
*** 196,207 ****
  
      @Override
      public ArrayData set(final int index, final double value, final boolean strict) {
          if (index >= 0 && index < maxDenseLength) {
              final long oldLength = underlying.length();
!             ensure(index);
!             underlying = underlying.set(index, value, strict).safeDelete(oldLength, index - 1, strict);
              setLength(Math.max(underlying.length(), length()));
          } else {
              final Long longIndex = indexToKey(index);
              sparseMap.put(longIndex, value);
              setLength(Math.max(longIndex + 1, length()));
--- 198,208 ----
  
      @Override
      public ArrayData set(final int index, final double value, final boolean strict) {
          if (index >= 0 && index < maxDenseLength) {
              final long oldLength = underlying.length();
!             underlying = underlying.ensure(index).set(index, value, strict).safeDelete(oldLength, index - 1, strict);
              setLength(Math.max(underlying.length(), length()));
          } else {
              final Long longIndex = indexToKey(index);
              sparseMap.put(longIndex, value);
              setLength(Math.max(longIndex + 1, length()));