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.parser;
  27 
  28 import static jdk.nashorn.internal.parser.TokenKind.SPECIAL;
  29 import static jdk.nashorn.internal.parser.TokenType.IDENT;
  30 
  31 /**
  32  * Fast lookup of operators and keywords.
  33  *
  34  */
  35 public final class TokenLookup {
  36     /**
  37      * Lookup table for tokens.
  38      */
  39     private static final TokenType[] table;
  40 
  41     /**
  42      * Table base character.
  43      */
  44     private static final int tableBase = ' ';
  45 
  46     /**
  47      * Table base character.
  48      */
  49     private static final int tableLimit = '~';
  50 
  51     /**
  52      * Table size.
  53      */
  54     private static final int tableLength = tableLimit - tableBase + 1;
  55 
  56     static {
  57         // Construct the table.
  58         table = new TokenType[tableLength];
  59 
  60         // For each token type.
  61         for (final TokenType tokenType : TokenType.getValues()) {
  62             // Get the name.
  63             final String name = tokenType.getName();
  64 
  65             // Filter tokens.
  66             if (name == null) {
  67                 continue;
  68             }
  69 
  70             // Ignore null and special.
  71             if (tokenType.getKind() != SPECIAL) {
  72                 // Get the first character of the name.
  73                 final char first = name.charAt(0);
  74                 // Translate that character into a table index.
  75                 final int index = first - tableBase;
  76                 assert index < tableLength : "Token name does not fit lookup table";
  77 
  78                 // Get the length of the token so that the longest come first.
  79                 final int length = tokenType.getLength();
  80                 // Prepare for table insert.
  81                 TokenType prev = null;
  82                 TokenType next = table[index];
  83 
  84                 // Find the right spot in the table.
  85                 while(next != null && next.getLength() > length) {
  86                     prev = next;
  87                     next = next.getNext();
  88                 }
  89 
  90                 // Insert in table.
  91                 tokenType.setNext(next);
  92 
  93                 if (prev == null) {
  94                     table[index] = tokenType;
  95                 } else {
  96                     prev.setNext(tokenType);
  97                 }
  98             }
  99         }
 100     }
 101 
 102     private TokenLookup() {
 103     }
 104 
 105     /**
 106      * Lookup keyword.
 107      *
 108      * @param content parse content char array
 109      * @param position index of position to start looking
 110      * @param length   max length to scan
 111      *
 112      * @return token type for keyword
 113      */
 114     public static TokenType lookupKeyword(final char[] content, final int position, final int length) {
 115         assert table != null : "Token lookup table is not initialized";
 116 
 117         // First character of keyword.
 118         final char first = content[position];
 119 
 120         // Must be lower case character.
 121         if ('a' <= first && first <= 'z') {
 122             // Convert to table index.
 123             final int index = first - tableBase;
 124             // Get first bucket entry.
 125             TokenType tokenType = table[index];
 126 
 127             // Search bucket list.
 128             while (tokenType != null) {
 129                 final int tokenLength = tokenType.getLength();
 130 
 131                 // if we have a length match maybe a keyword.
 132                 if (tokenLength == length) {
 133                     // Do an exact compare of string.
 134                     final String name = tokenType.getName();
 135                     int i;
 136                     for (i = 0; i < length; i++) {
 137                         if (content[position + i] != name.charAt(i)) {
 138                             break;
 139                         }
 140                     }
 141 
 142                     if (i == length) {
 143                         // Found a match.
 144                         return tokenType;
 145                     }
 146                 } else if (tokenLength < length) {
 147                     // Rest of tokens are shorter.
 148                     break;
 149                 }
 150 
 151                 // Try next token.
 152                 tokenType = tokenType.getNext();
 153             }
 154         }
 155 
 156         // Not found.
 157         return IDENT;
 158     }
 159 
 160 
 161     /**
 162      * Lookup operator.
 163      *
 164      * @param ch0 0th char in stream
 165      * @param ch1 1st char in stream
 166      * @param ch2 2nd char in stream
 167      * @param ch3 3rd char in stream
 168      *
 169      * @return the token type for the operator
 170      */
 171     public static TokenType lookupOperator(final char ch0, final char ch1, final char ch2, final char ch3) {
 172         assert table != null : "Token lookup table is not initialized";
 173 
 174         // Ignore keyword entries.
 175         if (tableBase < ch0 && ch0 <= tableLimit && !('a' <= ch0 && ch0 <= 'z')) {
 176             // Convert to index.
 177             final int index = ch0 - tableBase;
 178             // Get first bucket entry.
 179             TokenType tokenType = table[index];
 180 
 181             // Search bucket list.
 182             while (tokenType != null) {
 183                 final String name = tokenType.getName();
 184 
 185                 switch (name.length()) {
 186                 case 1:
 187                     // One character entry.
 188                     return tokenType;
 189                 case 2:
 190                     // Two character entry.
 191                     if (name.charAt(1) == ch1) {
 192                         return tokenType;
 193                     }
 194                     break;
 195                 case 3:
 196                     // Three character entry.
 197                     if (name.charAt(1) == ch1 &&
 198                         name.charAt(2) == ch2) {
 199                         return tokenType;
 200                     }
 201                     break;
 202                 case 4:
 203                     // Four character entry.
 204                     if (name.charAt(1) == ch1 &&
 205                         name.charAt(2) == ch2 &&
 206                         name.charAt(3) == ch3) {
 207                         return tokenType;
 208                     }
 209                     break;
 210                 default:
 211                     break;
 212                 }
 213 
 214                 // Try next token.
 215                 tokenType = tokenType.getNext();
 216             }
 217         }
 218 
 219         // Not found.
 220         return null;
 221     }
 222 }