1 /*
   2  * Copyright (c) 2010, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package jdk.nashorn.internal.runtime.arrays;
  27 
  28 import java.lang.reflect.Array;
  29 import jdk.nashorn.internal.runtime.ScriptRuntime;
  30 
  31 /**
  32  * This filter handles the deletion of array elements.
  33  */
  34 final class DeletedRangeArrayFilter extends ArrayFilter {
  35     /** Range (inclusive) tracking deletions */
  36     private long lo, hi;
  37 
  38     DeletedRangeArrayFilter(final ArrayData underlying, final long lo, final long hi) {
  39         super(maybeSparse(underlying, hi));
  40         this.lo = lo;
  41         this.hi = hi;
  42     }
  43 
  44     private static ArrayData maybeSparse(final ArrayData underlying, final long hi) {
  45         if (hi < SparseArrayData.MAX_DENSE_LENGTH || underlying instanceof SparseArrayData) {
  46             return underlying;
  47         }
  48         return new SparseArrayData(underlying, underlying.length());
  49     }
  50 
  51     private boolean isEmpty() {
  52         return lo > hi;
  53     }
  54 
  55     private boolean isDeleted(final int index) {
  56         final long longIndex = ArrayIndex.toLongIndex(index);
  57         return lo <= longIndex && longIndex <= hi;
  58     }
  59 
  60     @Override
  61     public ArrayData copy() {
  62         return new DeletedRangeArrayFilter(underlying.copy(), lo, hi);
  63     }
  64 
  65     @Override
  66     public Object[] asObjectArray() {
  67         final Object[] value = super.asObjectArray();
  68 
  69         if (lo < Integer.MAX_VALUE) {
  70             final int end = (int)Math.min(hi + 1, Integer.MAX_VALUE);
  71             for (int i = (int)lo; i < end; i++) {
  72                 value[i] = ScriptRuntime.UNDEFINED;
  73             }
  74         }
  75 
  76         return value;
  77     }
  78 
  79     @Override
  80     public Object asArrayOfType(final Class<?> componentType) {
  81         final Object value = super.asArrayOfType(componentType);
  82         final Object undefValue = convertUndefinedValue(componentType);
  83 
  84         if (lo < Integer.MAX_VALUE) {
  85             final int end = (int)Math.min(hi + 1, Integer.MAX_VALUE);
  86             for (int i = (int)lo; i < end; i++) {
  87                 Array.set(value, i, undefValue);
  88             }
  89         }
  90 
  91         return value;
  92     }
  93 
  94     @Override
  95     public ArrayData ensure(final long safeIndex) {
  96         if (safeIndex >= SparseArrayData.MAX_DENSE_LENGTH && safeIndex >= length()) {
  97             return new SparseArrayData(this, safeIndex + 1);
  98         }
  99 
 100         return super.ensure(safeIndex);
 101     }
 102 
 103     @Override
 104     public void shiftLeft(final int by) {
 105         super.shiftLeft(by);
 106         lo = Math.max(0, lo - by);
 107         hi = Math.max(-1, hi - by);
 108     }
 109 
 110     @Override
 111     public ArrayData shiftRight(final int by) {
 112         super.shiftRight(by);
 113         final long len = length();
 114         lo = Math.min(len, lo + by);
 115         hi = Math.min(len - 1, hi + by);
 116 
 117         return isEmpty() ? getUnderlying() : this;
 118     }
 119 
 120     @Override
 121     public ArrayData shrink(final long newLength) {
 122         super.shrink(newLength);
 123         lo = Math.min(newLength, lo);
 124         hi = Math.min(newLength - 1, hi);
 125 
 126         return isEmpty() ? getUnderlying() : this;
 127     }
 128 
 129     @Override
 130     public ArrayData set(final int index, final Object value, final boolean strict) {
 131         final long longIndex = ArrayIndex.toLongIndex(index);
 132         if (longIndex < lo || longIndex > hi) {
 133             return super.set(index, value, strict);
 134         } else if (longIndex > lo && longIndex < hi) {
 135             return getDeletedArrayFilter().set(index, value, strict);
 136         }
 137         if (longIndex == lo) {
 138             lo++;
 139         } else {
 140             assert longIndex == hi;
 141             hi--;
 142         }
 143 
 144         return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
 145     }
 146 
 147     @Override
 148     public ArrayData set(final int index, final int value, final boolean strict) {
 149         final long longIndex = ArrayIndex.toLongIndex(index);
 150         if (longIndex < lo || longIndex > hi) {
 151             return super.set(index, value, strict);
 152         } else if (longIndex > lo && longIndex < hi) {
 153             return getDeletedArrayFilter().set(index, value, strict);
 154         }
 155         if (longIndex == lo) {
 156             lo++;
 157         } else {
 158             assert longIndex == hi;
 159             hi--;
 160         }
 161 
 162         return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
 163     }
 164 
 165     @Override
 166     public ArrayData set(final int index, final long value, final boolean strict) {
 167         final long longIndex = ArrayIndex.toLongIndex(index);
 168         if (longIndex < lo || longIndex > hi) {
 169             return super.set(index, value, strict);
 170         } else if (longIndex > lo && longIndex < hi) {
 171             return getDeletedArrayFilter().set(index, value, strict);
 172         }
 173         if (longIndex == lo) {
 174             lo++;
 175         } else {
 176             assert longIndex == hi;
 177             hi--;
 178         }
 179 
 180         return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
 181     }
 182 
 183     @Override
 184     public ArrayData set(final int index, final double value, final boolean strict) {
 185         final long longIndex = ArrayIndex.toLongIndex(index);
 186         if (longIndex < lo || longIndex > hi) {
 187             return super.set(index, value, strict);
 188         } else if (longIndex > lo && longIndex < hi) {
 189             return getDeletedArrayFilter().set(index, value, strict);
 190         }
 191         if (longIndex == lo) {
 192             lo++;
 193         } else {
 194             assert longIndex == hi;
 195             hi--;
 196         }
 197 
 198         return isEmpty() ? getUnderlying().set(index, value, strict) : super.set(index, value, strict);
 199     }
 200 
 201     @Override
 202     public boolean has(final int index) {
 203         return super.has(index) && !isDeleted(index);
 204     }
 205 
 206     private ArrayData getDeletedArrayFilter() {
 207         final ArrayData deleteFilter = new DeletedArrayFilter(getUnderlying());
 208         deleteFilter.delete(lo, hi);
 209         return deleteFilter;
 210     }
 211 
 212     @Override
 213     public ArrayData delete(final int index) {
 214         final long longIndex = ArrayIndex.toLongIndex(index);
 215         underlying.setEmpty(index);
 216 
 217         if (longIndex + 1 == lo) {
 218             lo = longIndex;
 219         } else if (longIndex - 1 == hi) {
 220             hi = longIndex;
 221         } else if (longIndex < lo || hi < longIndex) {
 222            return getDeletedArrayFilter().delete(index);
 223         }
 224 
 225         return this;
 226     }
 227 
 228     @Override
 229     public ArrayData delete(final long fromIndex, final long toIndex) {
 230         if (fromIndex > hi + 1  || toIndex < lo - 1) {
 231             return getDeletedArrayFilter().delete(fromIndex, toIndex);
 232         }
 233         lo = Math.min(fromIndex, lo);
 234         hi = Math.max(toIndex, hi);
 235         underlying.setEmpty(lo, hi);
 236         return this;
 237     }
 238 
 239     @Override
 240     public Object pop() {
 241         final int index = (int)length() - 1;
 242         if (super.has(index)) {
 243             final boolean isDeleted = isDeleted(index);
 244             final Object value      = super.pop();
 245 
 246             lo = Math.min(index + 1, lo);
 247             hi = Math.min(index, hi);
 248             return isDeleted ? ScriptRuntime.UNDEFINED : value;
 249         }
 250 
 251         return super.pop();
 252     }
 253 
 254     @Override
 255     public ArrayData slice(final long from, final long to) {
 256         return new DeletedRangeArrayFilter(underlying.slice(from, to), Math.max(0, lo - from), Math.max(0, hi - from));
 257     }
 258 }