1 /*
2 * Copyright (c) 2010, 2015, 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 java.util.ArrayList;
29 import java.util.List;
30 import jdk.nashorn.internal.codegen.ObjectClassGenerator;
31 import jdk.nashorn.internal.objects.Global;
32 import jdk.nashorn.internal.runtime.ECMAErrors;
33 import jdk.nashorn.internal.runtime.ErrorManager;
34 import jdk.nashorn.internal.runtime.JSErrorType;
35 import jdk.nashorn.internal.runtime.JSType;
36 import jdk.nashorn.internal.runtime.ParserException;
37 import jdk.nashorn.internal.runtime.Property;
38 import jdk.nashorn.internal.runtime.PropertyMap;
39 import jdk.nashorn.internal.runtime.ScriptObject;
40 import jdk.nashorn.internal.runtime.Source;
41 import jdk.nashorn.internal.runtime.SpillProperty;
42 import jdk.nashorn.internal.runtime.arrays.ArrayData;
43 import jdk.nashorn.internal.runtime.arrays.ArrayIndex;
44 import jdk.nashorn.internal.scripts.JD;
45 import jdk.nashorn.internal.scripts.JO;
46
47 import static jdk.nashorn.internal.parser.TokenType.STRING;
48
49 /**
50 * Parses JSON text and returns the corresponding IR node. This is derived from
51 * the objectLiteral production of the main parser.
52 *
53 * See: 15.12.1.2 The JSON Syntactic Grammar
54 */
55 public class JSONParser {
56
57 final private String source;
58 final private Global global;
59 final private boolean dualFields;
60 final int length;
61 int pos = 0;
62
63 private static final int EOF = -1;
64
65 private static final String TRUE = "true";
66 private static final String FALSE = "false";
67 private static final String NULL = "null";
68
69 private static final int STATE_EMPTY = 0;
70 private static final int STATE_ELEMENT_PARSED = 1;
71 private static final int STATE_COMMA_PARSED = 2;
72
73 /**
74 * Constructor.
75 *
76 * @param source the source
77 * @param global the global object
78 * @param dualFields whether the parser should regard dual field representation
79 */
80 public JSONParser(final String source, final Global global, final boolean dualFields) {
81 this.source = source;
82 this.global = global;
83 this.length = source.length();
84 this.dualFields = dualFields;
85 }
86
87 /**
88 * Implementation of the Quote(value) operation as defined in the ECMAscript
89 * spec. It wraps a String value in double quotes and escapes characters
90 * within.
91 *
92 * @param value string to quote
93 *
94 * @return quoted and escaped string
95 */
96 public static String quote(final String value) {
97
98 final StringBuilder product = new StringBuilder();
99
100 product.append("\"");
101
102 for (final char ch : value.toCharArray()) {
103 // TODO: should use a table?
104 switch (ch) {
105 case '\\':
106 product.append("\\\\");
107 break;
108 case '"':
109 product.append("\\\"");
110 break;
111 case '\b':
112 product.append("\\b");
113 break;
114 case '\f':
115 product.append("\\f");
116 break;
117 case '\n':
118 product.append("\\n");
119 break;
120 case '\r':
121 product.append("\\r");
122 break;
123 case '\t':
124 product.append("\\t");
125 break;
126 default:
127 if (ch < ' ') {
128 product.append(Lexer.unicodeEscape(ch));
129 break;
130 }
131
132 product.append(ch);
133 break;
134 }
135 }
136
137 product.append("\"");
138
139 return product.toString();
140 }
141
142 /**
143 * Public parse method. Parse a string into a JSON object.
144 *
145 * @return the parsed JSON Object
146 */
147 public Object parse() {
148 final Object value = parseLiteral();
149 skipWhiteSpace();
150 if (pos < length) {
151 throw expectedError(pos, "eof", toString(peek()));
152 }
153 return value;
154 }
155
156 private Object parseLiteral() {
157 skipWhiteSpace();
158
159 final int c = peek();
160 if (c == EOF) {
161 throw expectedError(pos, "json literal", "eof");
162 }
163 switch (c) {
164 case '{':
165 return parseObject();
166 case '[':
167 return parseArray();
168 case '"':
169 return parseString();
170 case 'f':
171 return parseKeyword(FALSE, Boolean.FALSE);
172 case 't':
173 return parseKeyword(TRUE, Boolean.TRUE);
174 case 'n':
175 return parseKeyword(NULL, null);
176 default:
177 if (isDigit(c) || c == '-') {
178 return parseNumber();
179 } else if (c == '.') {
180 throw numberError(pos);
181 } else {
182 throw expectedError(pos, "json literal", toString(c));
183 }
184 }
185 }
186
187 private Object parseObject() {
188 PropertyMap propertyMap = dualFields ? JD.getInitialMap() : JO.getInitialMap();
189 ArrayData arrayData = ArrayData.EMPTY_ARRAY;
190 final ArrayList<Object> values = new ArrayList<>();
191 int state = STATE_EMPTY;
192
193 assert peek() == '{';
194 pos++;
195
196 while (pos < length) {
197 skipWhiteSpace();
198 final int c = peek();
199
200 switch (c) {
201 case '"':
202 if (state == STATE_ELEMENT_PARSED) {
203 throw expectedError(pos - 1, ", or }", toString(c));
204 }
205 final String id = parseString();
206 expectColon();
207 final Object value = parseLiteral();
208 final int index = ArrayIndex.getArrayIndex(id);
209 if (ArrayIndex.isValidArrayIndex(index)) {
210 arrayData = addArrayElement(arrayData, index, value);
211 } else {
212 propertyMap = addObjectProperty(propertyMap, values, id, value);
213 }
214 state = STATE_ELEMENT_PARSED;
215 break;
216 case ',':
217 if (state != STATE_ELEMENT_PARSED) {
218 throw error(AbstractParser.message("trailing.comma.in.json"), pos);
219 }
220 state = STATE_COMMA_PARSED;
221 pos++;
222 break;
223 case '}':
224 if (state == STATE_COMMA_PARSED) {
225 throw error(AbstractParser.message("trailing.comma.in.json"), pos);
226 }
227 pos++;
228 return createObject(propertyMap, values, arrayData);
229 default:
230 throw expectedError(pos, ", or }", toString(c));
231 }
232 }
233 throw expectedError(pos, ", or }", "eof");
234 }
235
236 private static ArrayData addArrayElement(final ArrayData arrayData, final int index, final Object value) {
237 final long oldLength = arrayData.length();
238 final long longIndex = ArrayIndex.toLongIndex(index);
239 ArrayData newArrayData = arrayData;
240 if (longIndex >= oldLength) {
241 newArrayData = newArrayData.ensure(longIndex);
242 if (longIndex > oldLength) {
243 newArrayData = newArrayData.delete(oldLength, longIndex - 1);
244 }
245 }
246 return newArrayData.set(index, value, false);
247 }
248
249 private PropertyMap addObjectProperty(final PropertyMap propertyMap, final List<Object> values,
250 final String id, final Object value) {
251 final Property oldProperty = propertyMap.findProperty(id);
252 final PropertyMap newMap;
253 final Class<?> type;
254 final int flags;
255 if (dualFields) {
256 type = getType(value);
257 flags = Property.DUAL_FIELDS;
258 } else {
259 type = Object.class;
260 flags = 0;
261 }
262
263 if (oldProperty != null) {
264 values.set(oldProperty.getSlot(), value);
265 newMap = propertyMap.replaceProperty(oldProperty, new SpillProperty(id, flags, oldProperty.getSlot(), type));;
266 } else {
267 values.add(value);
268 newMap = propertyMap.addProperty(new SpillProperty(id, flags, propertyMap.size(), type));
269 }
270
271 return newMap;
272 }
273
274 private Object createObject(final PropertyMap propertyMap, final List<Object> values, final ArrayData arrayData) {
275 final long[] primitiveSpill = dualFields ? new long[values.size()] : null;
276 final Object[] objectSpill = new Object[values.size()];
277
278 for (final Property property : propertyMap.getProperties()) {
279 if (!dualFields || property.getType() == Object.class) {
280 objectSpill[property.getSlot()] = values.get(property.getSlot());
281 } else {
282 primitiveSpill[property.getSlot()] = ObjectClassGenerator.pack((Number) values.get(property.getSlot()));
283 }
284 }
285
286 final ScriptObject object = dualFields ?
287 new JD(propertyMap, primitiveSpill, objectSpill) : new JO(propertyMap, null, objectSpill);
288 object.setInitialProto(global.getObjectPrototype());
289 object.setArray(arrayData);
290 return object;
291 }
292
293 private static Class<?> getType(final Object value) {
294 if (value instanceof Integer) {
295 return int.class;
296 } else if (value instanceof Double) {
297 return double.class;
298 } else {
299 return Object.class;
300 }
301 }
302
303 private void expectColon() {
304 skipWhiteSpace();
305 final int n = next();
306 if (n != ':') {
307 throw expectedError(pos - 1, ":", toString(n));
308 }
309 }
310
311 private Object parseArray() {
312 ArrayData arrayData = ArrayData.EMPTY_ARRAY;
313 int state = STATE_EMPTY;
314
315 assert peek() == '[';
316 pos++;
317
318 while (pos < length) {
319 skipWhiteSpace();
320 final int c = peek();
321
322 switch (c) {
323 case ',':
324 if (state != STATE_ELEMENT_PARSED) {
325 throw error(AbstractParser.message("trailing.comma.in.json"), pos);
326 }
327 state = STATE_COMMA_PARSED;
328 pos++;
329 break;
330 case ']':
331 if (state == STATE_COMMA_PARSED) {
332 throw error(AbstractParser.message("trailing.comma.in.json"), pos);
333 }
334 pos++;
335 return global.wrapAsObject(arrayData);
336 default:
337 if (state == STATE_ELEMENT_PARSED) {
338 throw expectedError(pos, ", or ]", toString(c));
339 }
340 final long index = arrayData.length();
341 arrayData = arrayData.ensure(index).set((int) index, parseLiteral(), true);
342 state = STATE_ELEMENT_PARSED;
343 break;
344 }
345 }
346
347 throw expectedError(pos, ", or ]", "eof");
348 }
349
350 private String parseString() {
351 // String buffer is only instantiated if string contains escape sequences.
352 int start = ++pos;
353 StringBuilder sb = null;
354
355 while (pos < length) {
356 final int c = next();
357 if (c <= 0x1f) {
358 // Characters < 0x1f are not allowed in JSON strings.
359 throw syntaxError(pos, "String contains control character");
360
361 } else if (c == '\\') {
362 if (sb == null) {
363 sb = new StringBuilder(pos - start + 16);
364 }
365 sb.append(source, start, pos - 1);
366 sb.append(parseEscapeSequence());
367 start = pos;
368
369 } else if (c == '"') {
370 if (sb != null) {
371 sb.append(source, start, pos - 1);
372 return sb.toString();
373 }
374 return source.substring(start, pos - 1);
375 }
376 }
377
378 throw error(Lexer.message("missing.close.quote"), pos, length);
379 }
380
381 private char parseEscapeSequence() {
382 final int c = next();
383 switch (c) {
384 case '"':
385 return '"';
386 case '\\':
387 return '\\';
388 case '/':
389 return '/';
390 case 'b':
391 return '\b';
392 case 'f':
393 return '\f';
394 case 'n':
395 return '\n';
396 case 'r':
397 return '\r';
398 case 't':
399 return '\t';
400 case 'u':
401 return parseUnicodeEscape();
402 default:
403 throw error(Lexer.message("invalid.escape.char"), pos - 1, length);
404 }
405 }
406
407 private char parseUnicodeEscape() {
408 return (char) (parseHexDigit() << 12 | parseHexDigit() << 8 | parseHexDigit() << 4 | parseHexDigit());
409 }
410
411 private int parseHexDigit() {
412 final int c = next();
413 if (c >= '0' && c <= '9') {
414 return c - '0';
415 } else if (c >= 'A' && c <= 'F') {
416 return c + 10 - 'A';
417 } else if (c >= 'a' && c <= 'f') {
418 return c + 10 - 'a';
419 }
420 throw error(Lexer.message("invalid.hex"), pos - 1, length);
421 }
422
423 private boolean isDigit(final int c) {
424 return c >= '0' && c <= '9';
425 }
426
427 private void skipDigits() {
428 while (pos < length) {
429 final int c = peek();
430 if (!isDigit(c)) {
431 break;
432 }
433 pos++;
434 }
435 }
436
437 private Number parseNumber() {
438 final int start = pos;
439 int c = next();
440
441 if (c == '-') {
442 c = next();
443 }
444 if (!isDigit(c)) {
445 throw numberError(start);
446 }
447 // no more digits allowed after 0
448 if (c != '0') {
449 skipDigits();
450 }
451
452 // fraction
453 if (peek() == '.') {
454 pos++;
455 if (!isDigit(next())) {
456 throw numberError(pos - 1);
457 }
458 skipDigits();
459 }
460
461 // exponent
462 c = peek();
463 if (c == 'e' || c == 'E') {
464 pos++;
465 c = next();
466 if (c == '-' || c == '+') {
467 c = next();
468 }
469 if (!isDigit(c)) {
470 throw numberError(pos - 1);
471 }
472 skipDigits();
473 }
474
475 final double d = Double.parseDouble(source.substring(start, pos));
476 if (JSType.isRepresentableAsInt(d)) {
477 return (int) d;
478 }
479 return d;
480 }
481
482 private Object parseKeyword(final String keyword, final Object value) {
483 if (!source.regionMatches(pos, keyword, 0, keyword.length())) {
484 throw expectedError(pos, "json literal", "ident");
485 }
486 pos += keyword.length();
487 return value;
488 }
489
490 private int peek() {
491 if (pos >= length) {
492 return -1;
493 }
494 return source.charAt(pos);
495 }
496
497 private int next() {
498 final int next = peek();
499 pos++;
500 return next;
501 }
502
503 private void skipWhiteSpace() {
504 while (pos < length) {
505 switch (peek()) {
506 case '\t':
507 case '\r':
508 case '\n':
509 case ' ':
510 pos++;
511 break;
512 default:
513 return;
514 }
515 }
516 }
517
518 private static String toString(final int c) {
519 return c == EOF ? "eof" : String.valueOf((char) c);
520 }
521
522 ParserException error(final String message, final int start, final int length) throws ParserException {
523 final long token = Token.toDesc(STRING, start, length);
524 final int pos = Token.descPosition(token);
525 final Source src = Source.sourceFor("<json>", source);
526 final int lineNum = src.getLine(pos);
527 final int columnNum = src.getColumn(pos);
528 final String formatted = ErrorManager.format(message, src, lineNum, columnNum, token);
529 return new ParserException(JSErrorType.SYNTAX_ERROR, formatted, src, lineNum, columnNum, token);
530 }
531
532 private ParserException error(final String message, final int start) {
533 return error(message, start, length);
534 }
535
536 private ParserException numberError(final int start) {
537 return error(Lexer.message("json.invalid.number"), start);
538 }
539
540 private ParserException expectedError(final int start, final String expected, final String found) {
541 return error(AbstractParser.message("expected", expected, found), start);
542 }
543
544 private ParserException syntaxError(final int start, final String reason) {
545 final String message = ECMAErrors.getMessage("syntax.error.invalid.json", reason);
546 return error(message, start);
547 }
548 }