Mercurial > hg > openjdk > jdk9 > nashorn
changeset 1844:9c7526916609
8171219: Missing checks in sparse array shift() implementation
Reviewed-by: jlaskey, attila, sundar
line wrap: on
line diff
--- a/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ArrayData.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ArrayFilter.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ByteBufferArrayData.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/DeletedArrayFilter.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/DeletedRangeArrayFilter.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/IntArrayData.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/NumberArrayData.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/ObjectArrayData.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/SparseArrayData.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/TypedArrayData.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/src/jdk.scripting.nashorn/share/classes/jdk/nashorn/internal/runtime/arrays/UndefinedArrayFilter.java Wed Dec 14 20:34:11 2016 +0000 +++ b/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/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); +