8171219: Missing checks in sparse array shift() implementation
Reviewed-by: jlaskey, attila, sundar
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ArrayData.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ArrayData.java Thu Dec 15 14:17:21 2016 +0100
@@ -107,14 +107,13 @@
@Override
public ArrayData ensure(final long safeIndex) {
- if (safeIndex > 0L) {
- if (safeIndex >= SparseArrayData.MAX_DENSE_LENGTH) {
- return new SparseArrayData(this, safeIndex + 1);
- }
- //known to fit in int
- return toRealArrayData((int)safeIndex);
- }
- return this;
+ assert safeIndex >= 0L;
+ if (safeIndex >= SparseArrayData.MAX_DENSE_LENGTH) {
+ return new SparseArrayData(this, safeIndex + 1);
+ }
+ //known to fit in int
+ return toRealArrayData((int)safeIndex);
+
}
@Override
@@ -133,8 +132,8 @@
}
@Override
- public void shiftLeft(final int by) {
- //nop, always empty or we wouldn't be of this class
+ public ArrayData shiftLeft(final int by) {
+ return this; //nop, always empty or we wouldn't be of this class
}
@Override
@@ -451,13 +450,13 @@
/**
* Shift the array data left
*
- * TODO: explore start at an index and not at zero, to make these operations
- * even faster. Offset everything from the index. Costs memory but is probably
- * worth it
+ * TODO: This is used for Array.prototype.shift() which only shifts by 1,
+ * so we might consider dropping the offset parameter.
*
* @param by offset to shift
+ * @return New arraydata (or same)
*/
- public abstract void shiftLeft(final int by);
+ public abstract ArrayData shiftLeft(final int by);
/**
* Shift the array right
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ArrayFilter.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ArrayFilter.java Thu Dec 15 14:17:21 2016 +0100
@@ -68,9 +68,10 @@
}
@Override
- public void shiftLeft(final int by) {
+ public ArrayData shiftLeft(final int by) {
underlying.shiftLeft(by);
setLength(underlying.length());
+ return this;
}
@Override
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ByteBufferArrayData.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ByteBufferArrayData.java Thu Dec 15 14:17:21 2016 +0100
@@ -82,7 +82,7 @@
}
@Override
- public void shiftLeft(final int by) {
+ public ArrayData shiftLeft(final int by) {
throw unsupported("shiftLeft");
}
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/DeletedArrayFilter.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/DeletedArrayFilter.java Thu Dec 15 14:17:21 2016 +0100
@@ -76,9 +76,10 @@
}
@Override
- public void shiftLeft(final int by) {
+ public ArrayData shiftLeft(final int by) {
super.shiftLeft(by);
deleted.shiftLeft(by, length());
+ return this;
}
@Override
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/DeletedRangeArrayFilter.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/DeletedRangeArrayFilter.java Thu Dec 15 14:17:21 2016 +0100
@@ -101,10 +101,12 @@
}
@Override
- public void shiftLeft(final int by) {
+ public ArrayData shiftLeft(final int by) {
super.shiftLeft(by);
lo = Math.max(0, lo - by);
hi = Math.max(-1, hi - by);
+
+ return isEmpty() ? getUnderlying() : this;
}
@Override
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/IntArrayData.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/IntArrayData.java Thu Dec 15 14:17:21 2016 +0100
@@ -176,8 +176,15 @@
}
@Override
- public void shiftLeft(final int by) {
- System.arraycopy(array, by, array, 0, array.length - by);
+ public ArrayData shiftLeft(final int by) {
+ if (by >= length()) {
+ shrink(0);
+ } else {
+ System.arraycopy(array, by, array, 0, array.length - by);
+ }
+ setLength(Math.max(0, length() - by));
+
+ return this;
}
@Override
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/NumberArrayData.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/NumberArrayData.java Thu Dec 15 14:17:21 2016 +0100
@@ -121,8 +121,14 @@
}
@Override
- public void shiftLeft(final int by) {
- System.arraycopy(array, by, array, 0, array.length - by);
+ public ArrayData shiftLeft(final int by) {
+ if (by >= length()) {
+ shrink(0);
+ } else {
+ System.arraycopy(array, by, array, 0, array.length - by);
+ }
+ setLength(Math.max(0, length() - by));
+ return this;
}
@Override
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ObjectArrayData.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ObjectArrayData.java Thu Dec 15 14:17:21 2016 +0100
@@ -98,8 +98,14 @@
}
@Override
- public void shiftLeft(final int by) {
- System.arraycopy(array, by, array, 0, array.length - by);
+ public ArrayData shiftLeft(final int by) {
+ if (by >= length()) {
+ shrink(0);
+ } else {
+ System.arraycopy(array, by, array, 0, array.length - by);
+ }
+ setLength(Math.max(0, length() - by));
+ return this;
}
@Override
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/SparseArrayData.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/SparseArrayData.java Thu Dec 15 14:17:21 2016 +0100
@@ -36,6 +36,7 @@
* 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. */
@@ -51,7 +52,7 @@
this(underlying, length, new TreeMap<>());
}
- SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
+ private SparseArrayData(final ArrayData underlying, final long length, final TreeMap<Long, Object> sparseMap) {
super(length);
assert underlying.length() <= length;
this.underlying = underlying;
@@ -89,38 +90,49 @@
}
@Override
- public void shiftLeft(final int by) {
- underlying.shiftLeft(by);
+ 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() - by;
- if (newIndex < maxDenseLength) {
- underlying = underlying.set((int) newIndex, entry.getValue(), false);
- } else if (newIndex >= 0) {
- newSparseMap.put(newIndex, entry.getValue());
+ 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(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) {
- for (long i = maxDenseLength - by; i < len; i++) {
+ // 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(i + by, underlying.getObject((int) i));
}
}
- underlying = underlying.shrink((int) (maxDenseLength - by));
+ underlying = underlying.shrink((int) tempLength);
+ underlying.setLength(tempLength);
}
- underlying.shiftRight(by);
+ underlying = underlying.shiftRight(by);
for (final Map.Entry<Long, Object> entry : sparseMap.entrySet()) {
final long newIndex = entry.getKey() + by;
@@ -135,14 +147,6 @@
@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);
}
@@ -167,8 +171,7 @@
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);
+ 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);
@@ -183,8 +186,7 @@
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);
+ 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);
@@ -198,8 +200,7 @@
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);
+ 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);
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/TypedArrayData.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/TypedArrayData.java Thu Dec 15 14:17:21 2016 +0100
@@ -98,7 +98,7 @@
}
@Override
- public void shiftLeft(final int by) {
+ public ArrayData shiftLeft(final int by) {
throw new UnsupportedOperationException();
}
--- a/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/UndefinedArrayFilter.java Wed Dec 14 20:34:11 2016 +0000
+++ b/nashorn/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/UndefinedArrayFilter.java Thu Dec 15 14:17:21 2016 +0100
@@ -77,9 +77,10 @@
}
@Override
- public void shiftLeft(final int by) {
+ public ArrayData shiftLeft(final int by) {
super.shiftLeft(by);
undefined.shiftLeft(by, length());
+ return this;
}
@Override
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/nashorn/test/script/basic/JDK-8171219.js Thu Dec 15 14:17:21 2016 +0100
@@ -0,0 +1,57 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * JDK-8171219: Missing checks in sparse array shift() implementation
+ *
+ * @test
+ * @run
+ */
+
+var a = [];
+a[1048577] = 1;
+a.shift();
+a[1] = 2;
+a.shift();
+var ka = Object.keys(a);
+Assert.assertTrue(ka.length === 2);
+Assert.assertTrue(ka[0] === '0');
+Assert.assertTrue(ka[1] === '1048575');
+Assert.assertTrue(a.length === 1048576);
+Assert.assertTrue(a[0] === 2);
+Assert.assertTrue(a[1048575] = 1);
+
+var b = [];
+b[1048577] = 1;
+b.unshift(2);
+b.shift();
+b[1] = 3;
+b.shift();
+var kb = Object.keys(b);
+Assert.assertTrue(kb.length === 2);
+Assert.assertTrue(kb[0] === '0');
+Assert.assertTrue(kb[1] === '1048576');
+Assert.assertTrue(b.length === 1048577);
+Assert.assertTrue(b[0] === 3);
+Assert.assertTrue(b[1048576] = 1);
+