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 Long) { 297 return long.class; 298 } else if (value instanceof Double) { 299 return double.class; 300 } else { 301 return Object.class; 302 } 303 } 304 305 private void expectColon() { 306 skipWhiteSpace(); 307 final int n = next(); 308 if (n != ':') { 309 throw expectedError(pos - 1, ":", toString(n)); 310 } 311 } 312 313 private Object parseArray() { 314 ArrayData arrayData = ArrayData.EMPTY_ARRAY; 315 int state = STATE_EMPTY; 316 317 assert peek() == '['; 318 pos++; 319 320 while (pos < length) { 321 skipWhiteSpace(); 322 final int c = peek(); 323 324 switch (c) { 325 case ',': 326 if (state != STATE_ELEMENT_PARSED) { 327 throw error(AbstractParser.message("trailing.comma.in.json"), pos); 328 } 329 state = STATE_COMMA_PARSED; 330 pos++; 331 break; 332 case ']': 333 if (state == STATE_COMMA_PARSED) { 334 throw error(AbstractParser.message("trailing.comma.in.json"), pos); 335 } 336 pos++; 337 return global.wrapAsObject(arrayData); 338 default: 339 if (state == STATE_ELEMENT_PARSED) { 340 throw expectedError(pos, ", or ]", toString(c)); 341 } 342 final long index = arrayData.length(); 343 arrayData = arrayData.ensure(index).set((int) index, parseLiteral(), true); 344 state = STATE_ELEMENT_PARSED; 345 break; 346 } 347 } 348 349 throw expectedError(pos, ", or ]", "eof"); 350 } 351 352 private String parseString() { 353 // String buffer is only instantiated if string contains escape sequences. 354 int start = ++pos; 355 StringBuilder sb = null; 356 357 while (pos < length) { 358 final int c = next(); 359 if (c <= 0x1f) { 360 // Characters < 0x1f are not allowed in JSON strings. 361 throw syntaxError(pos, "String contains control character"); 362 363 } else if (c == '\\') { 364 if (sb == null) { 365 sb = new StringBuilder(pos - start + 16); 366 } 367 sb.append(source, start, pos - 1); 368 sb.append(parseEscapeSequence()); 369 start = pos; 370 371 } else if (c == '"') { 372 if (sb != null) { 373 sb.append(source, start, pos - 1); 374 return sb.toString(); 375 } 376 return source.substring(start, pos - 1); 377 } 378 } 379 380 throw error(Lexer.message("missing.close.quote"), pos, length); 381 } 382 383 private char parseEscapeSequence() { 384 final int c = next(); 385 switch (c) { 386 case '"': 387 return '"'; 388 case '\\': 389 return '\\'; 390 case '/': 391 return '/'; 392 case 'b': 393 return '\b'; 394 case 'f': 395 return '\f'; 396 case 'n': 397 return '\n'; 398 case 'r': 399 return '\r'; 400 case 't': 401 return '\t'; 402 case 'u': 403 return parseUnicodeEscape(); 404 default: 405 throw error(Lexer.message("invalid.escape.char"), pos - 1, length); 406 } 407 } 408 409 private char parseUnicodeEscape() { 410 return (char) (parseHexDigit() << 12 | parseHexDigit() << 8 | parseHexDigit() << 4 | parseHexDigit()); 411 } 412 413 private int parseHexDigit() { 414 final int c = next(); 415 if (c >= '0' && c <= '9') { 416 return c - '0'; 417 } else if (c >= 'A' && c <= 'F') { 418 return c + 10 - 'A'; 419 } else if (c >= 'a' && c <= 'f') { 420 return c + 10 - 'a'; 421 } 422 throw error(Lexer.message("invalid.hex"), pos - 1, length); 423 } 424 425 private boolean isDigit(final int c) { 426 return c >= '0' && c <= '9'; 427 } 428 429 private void skipDigits() { 430 while (pos < length) { 431 final int c = peek(); 432 if (!isDigit(c)) { 433 break; 434 } 435 pos++; 436 } 437 } 438 439 private Number parseNumber() { 440 final int start = pos; 441 int c = next(); 442 443 if (c == '-') { 444 c = next(); 445 } 446 if (!isDigit(c)) { 447 throw numberError(start); 448 } 449 // no more digits allowed after 0 450 if (c != '0') { 451 skipDigits(); 452 } 453 454 // fraction 455 if (peek() == '.') { 456 pos++; 457 if (!isDigit(next())) { 458 throw numberError(pos - 1); 459 } 460 skipDigits(); 461 } 462 463 // exponent 464 c = peek(); 465 if (c == 'e' || c == 'E') { 466 pos++; 467 c = next(); 468 if (c == '-' || c == '+') { 469 c = next(); 470 } 471 if (!isDigit(c)) { 472 throw numberError(pos - 1); 473 } 474 skipDigits(); 475 } 476 477 final double d = Double.parseDouble(source.substring(start, pos)); 478 if (JSType.isRepresentableAsInt(d)) { 479 return (int) d; 480 } else if (JSType.isRepresentableAsLong(d)) { 481 return (long) d; 482 } 483 return d; 484 } 485 486 private Object parseKeyword(final String keyword, final Object value) { 487 if (!source.regionMatches(pos, keyword, 0, keyword.length())) { 488 throw expectedError(pos, "json literal", "ident"); 489 } 490 pos += keyword.length(); 491 return value; 492 } 493 494 private int peek() { 495 if (pos >= length) { 496 return -1; 497 } 498 return source.charAt(pos); 499 } 500 501 private int next() { 502 final int next = peek(); 503 pos++; 504 return next; 505 } 506 507 private void skipWhiteSpace() { 508 while (pos < length) { 509 switch (peek()) { 510 case '\t': 511 case '\r': 512 case '\n': 513 case ' ': 514 pos++; 515 break; 516 default: 517 return; 518 } 519 } 520 } 521 522 private static String toString(final int c) { 523 return c == EOF ? "eof" : String.valueOf((char) c); 524 } 525 526 ParserException error(final String message, final int start, final int length) throws ParserException { 527 final long token = Token.toDesc(STRING, start, length); 528 final int pos = Token.descPosition(token); 529 final Source src = Source.sourceFor("<json>", source); 530 final int lineNum = src.getLine(pos); 531 final int columnNum = src.getColumn(pos); 532 final String formatted = ErrorManager.format(message, src, lineNum, columnNum, token); 533 return new ParserException(JSErrorType.SYNTAX_ERROR, formatted, src, lineNum, columnNum, token); 534 } 535 536 private ParserException error(final String message, final int start) { 537 return error(message, start, length); 538 } 539 540 private ParserException numberError(final int start) { 541 return error(Lexer.message("json.invalid.number"), start); 542 } 543 544 private ParserException expectedError(final int start, final String expected, final String found) { 545 return error(AbstractParser.message("expected", expected, found), start); 546 } 547 548 private ParserException syntaxError(final int start, final String reason) { 549 final String message = ECMAErrors.getMessage("syntax.error.invalid.json", reason); 550 return error(message, start); 551 } 552 }