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
26package jdk.nashorn.internal.parser;
27
28import static jdk.nashorn.internal.parser.TokenKind.SPECIAL;
29import static jdk.nashorn.internal.parser.TokenType.IDENT;
30
31/**
32 * Fast lookup of operators and keywords.
33 *
34 */
35public 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}
223