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 }