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 jdk.nashorn.internal.runtime.ConsString;
  29 import jdk.nashorn.internal.runtime.JSType;
  30 import jdk.nashorn.internal.runtime.ScriptObject;
  31 
  32 /**
  33  * Array index computation helpers. that both throw exceptions or return
  34  * invalid values.
  35  *
  36  */
  37 public final class ArrayIndex {
  38 
  39     private static final int  INVALID_ARRAY_INDEX = -1;
  40     private static final long MAX_ARRAY_INDEX = 0xfffffffeL;
  41 
  42     private ArrayIndex() {
  43     }
  44 
  45     /**
  46      * Fast conversion of non-negative integer string to long.
  47      * @param key Key as a string.
  48      * @return long value of string or {@code -1} if string does not represent a valid index.
  49      */
  50     private static long fromString(final String key) {
  51         long value = 0;
  52         final int length = key.length();
  53 
  54         // Check for empty string or leading 0
  55         if (length == 0 || (length > 1 && key.charAt(0) == '0')) {
  56             return INVALID_ARRAY_INDEX;
  57         }
  58 
  59         // Fast toNumber.
  60         for (int i = 0; i < length; i++) {
  61             final char digit = key.charAt(i);
  62 
  63             // If not a digit.
  64             if (digit < '0' || digit > '9') {
  65                 return INVALID_ARRAY_INDEX;
  66             }
  67 
  68             // Insert digit.
  69             value = value * 10 + digit - '0';
  70 
  71             // Check for overflow (need to catch before wrap around.)
  72             if (value > MAX_ARRAY_INDEX) {
  73                 return INVALID_ARRAY_INDEX;
  74             }
  75         }
  76 
  77         return value;
  78     }
  79 
  80     /**
  81      * Returns a valid array index in an int, if the object represents one. This
  82      * routine needs to perform quickly since all keys are tested with it.
  83      *
  84      * <p>The {@code key} parameter must be a JavaScript primitive type, i.e. one of
  85      * {@code String}, {@code Number}, {@code Boolean}, {@code null}, or {@code undefined}.
  86      * {@code ScriptObject} instances should be converted to primitive with
  87      * {@code String.class} hint before being passed to this method.</p>
  88      *
  89      * @param  key key to check for array index.
  90      * @return the array index, or {@code -1} if {@code key} does not represent a valid index.
  91      *         Note that negative return values other than {@code -1} are considered valid and can be converted to
  92      *         the actual index using {@link #toLongIndex(int)}.
  93      */
  94     public static int getArrayIndex(final Object key) {
  95         if (key instanceof Integer) {
  96             return getArrayIndex(((Integer) key).intValue());
  97         } else if (key instanceof Double) {
  98             return getArrayIndex(((Double) key).doubleValue());
  99         } else if (key instanceof String) {
 100             return (int)fromString((String) key);
 101         } else if (key instanceof Long) {
 102             return getArrayIndex(((Long) key).longValue());
 103         } else if (key instanceof ConsString) {
 104             return (int)fromString(key.toString());
 105         }
 106 
 107         assert !(key instanceof ScriptObject);
 108         return INVALID_ARRAY_INDEX;
 109     }
 110 
 111     /**
 112      * Returns a valid array index in an int, if {@code key} represents one.
 113      *
 114      * @param key key to check
 115      * @return the array index, or {@code -1} if {@code key} is not a valid array index.
 116      */
 117     public static int getArrayIndex(final int key) {
 118         return (key >= 0) ? key : INVALID_ARRAY_INDEX;
 119     }
 120 
 121     /**
 122      * Returns a valid array index in an int, if the long represents one.
 123      *
 124      * @param key key to check
 125      * @return the array index, or {@code -1} if long is not a valid array index.
 126      *         Note that negative return values other than {@code -1} are considered valid and can be converted to
 127      *         the actual index using {@link #toLongIndex(int)}.
 128      */
 129     public static int getArrayIndex(final long key) {
 130         if (key >= 0 && key <= MAX_ARRAY_INDEX) {
 131             return (int)key;
 132         }
 133 
 134         return INVALID_ARRAY_INDEX;
 135     }
 136 
 137 
 138     /**
 139      * Return a valid index for this double, if it represents one.
 140      *
 141      * Doubles that aren't representable exactly as longs/ints aren't working
 142      * array indexes, however, array[1.1] === array["1.1"] in JavaScript.
 143      *
 144      * @param key the key to check
 145      * @return the array index this double represents or {@code -1} if this isn't a valid index.
 146      *         Note that negative return values other than {@code -1} are considered valid and can be converted to
 147      *         the actual index using {@link #toLongIndex(int)}.
 148      */
 149     public static int getArrayIndex(final double key) {
 150         if (JSType.isRepresentableAsInt(key)) {
 151             return getArrayIndex((int) key);
 152         } else if (JSType.isRepresentableAsLong(key)) {
 153             return getArrayIndex((long) key);
 154         }
 155 
 156         return INVALID_ARRAY_INDEX;
 157     }
 158 
 159 
 160     /**
 161      * Return a valid array index for this string, if it represents one.
 162      *
 163      * @param key the key to check
 164      * @return the array index this string represents or {@code -1} if this isn't a valid index.
 165      *         Note that negative return values other than {@code -1} are considered valid and can be converted to
 166      *         the actual index using {@link #toLongIndex(int)}.
 167      */
 168     public static int getArrayIndex(final String key) {
 169         return (int)fromString(key);
 170     }
 171 
 172     /**
 173      * Check whether an index is valid as an array index. This check only tests if
 174      * it is the special "invalid array index" type, not if it is e.g. less than zero
 175      * or corrupt in some other way
 176      *
 177      * @param index index to test
 178      * @return true if {@code index} is not the special invalid array index type
 179      */
 180     public static boolean isValidArrayIndex(final int index) {
 181         return index != INVALID_ARRAY_INDEX;
 182     }
 183 
 184     /**
 185      * Convert an index to a long value. This basically amounts to converting it into a
 186      * {@link JSType#toUint32(int)} uint32} as the maximum array index in JavaScript
 187      * is 0xfffffffe
 188      *
 189      * @param index index to convert to long form
 190      * @return index as uint32 in a long
 191      */
 192     public static long toLongIndex(final int index) {
 193         return JSType.toUint32(index);
 194     }
 195 
 196     /**
 197      * Convert an index to a key string. This is the same as calling {@link #toLongIndex(int)}
 198      * and converting the result to String.
 199      *
 200      * @param index index to convert
 201      * @return index as string
 202      */
 203     public static String toKey(final int index) {
 204         return Long.toString(JSType.toUint32(index));
 205     }
 206 
 207 }
 208