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
26package jdk.nashorn.internal.parser;
27
28import java.util.ArrayList;
29import java.util.List;
30import jdk.nashorn.internal.codegen.ObjectClassGenerator;
31import jdk.nashorn.internal.objects.Global;
32import jdk.nashorn.internal.runtime.ECMAErrors;
33import jdk.nashorn.internal.runtime.ErrorManager;
34import jdk.nashorn.internal.runtime.JSErrorType;
35import jdk.nashorn.internal.runtime.JSType;
36import jdk.nashorn.internal.runtime.ParserException;
37import jdk.nashorn.internal.runtime.Property;
38import jdk.nashorn.internal.runtime.PropertyMap;
39import jdk.nashorn.internal.runtime.ScriptObject;
40import jdk.nashorn.internal.runtime.Source;
41import jdk.nashorn.internal.runtime.SpillProperty;
42import jdk.nashorn.internal.runtime.arrays.ArrayData;
43import jdk.nashorn.internal.runtime.arrays.ArrayIndex;
44import jdk.nashorn.internal.scripts.JD;
45import jdk.nashorn.internal.scripts.JO;
46
47import 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 */
55public 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}
549