1/*
2 * Copyright (C) 2010 Google Inc. All rights reserved.
3 * Copyright (C) 2014 University of Washington. All rights reserved.
4 * Copyright (C) 2017-2019 Apple Inc. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met:
9 *
10 * * Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above
13 * copyright notice, this list of conditions and the following disclaimer
14 * in the documentation and/or other materials provided with the
15 * distribution.
16 * * Neither the name of Google Inc. nor the names of its
17 * contributors may be used to endorse or promote products derived from
18 * this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33#include "config.h"
34#include <wtf/JSONValues.h>
35
36#include <wtf/text/StringBuilder.h>
37
38namespace WTF {
39namespace JSONImpl {
40
41namespace {
42
43static constexpr int stackLimit = 1000;
44
45enum class Token {
46 ObjectBegin,
47 ObjectEnd,
48 ArrayBegin,
49 ArrayEnd,
50 String,
51 Number,
52 BoolTrue,
53 BoolFalse,
54 Null,
55 ListSeparator,
56 ObjectPairSeparator,
57 Invalid,
58};
59
60const char* const nullString = "null";
61const char* const trueString = "true";
62const char* const falseString = "false";
63
64bool parseConstToken(const UChar* start, const UChar* end, const UChar** tokenEnd, const char* token)
65{
66 while (start < end && *token != '\0' && *start++ == *token++) { }
67
68 if (*token != '\0')
69 return false;
70
71 *tokenEnd = start;
72 return true;
73}
74
75bool readInt(const UChar* start, const UChar* end, const UChar** tokenEnd, bool canHaveLeadingZeros)
76{
77 if (start == end)
78 return false;
79
80 bool haveLeadingZero = '0' == *start;
81 int length = 0;
82 while (start < end && '0' <= *start && *start <= '9') {
83 ++start;
84 ++length;
85 }
86
87 if (!length)
88 return false;
89
90 if (!canHaveLeadingZeros && length > 1 && haveLeadingZero)
91 return false;
92
93 *tokenEnd = start;
94 return true;
95}
96
97bool parseNumberToken(const UChar* start, const UChar* end, const UChar** tokenEnd)
98{
99 // We just grab the number here. We validate the size in DecodeNumber.
100 // According to RFC 4627, a valid number is: [minus] int [frac] [exp]
101 if (start == end)
102 return false;
103
104 UChar c = *start;
105 if ('-' == c)
106 ++start;
107
108 if (!readInt(start, end, &start, false))
109 return false;
110
111 if (start == end) {
112 *tokenEnd = start;
113 return true;
114 }
115
116 // Optional fraction part.
117 c = *start;
118 if ('.' == c) {
119 ++start;
120 if (!readInt(start, end, &start, true))
121 return false;
122 if (start == end) {
123 *tokenEnd = start;
124 return true;
125 }
126 c = *start;
127 }
128
129 // Optional exponent part.
130 if ('e' == c || 'E' == c) {
131 ++start;
132 if (start == end)
133 return false;
134 c = *start;
135 if ('-' == c || '+' == c) {
136 ++start;
137 if (start == end)
138 return false;
139 }
140 if (!readInt(start, end, &start, true))
141 return false;
142 }
143
144 *tokenEnd = start;
145 return true;
146}
147
148bool readHexDigits(const UChar* start, const UChar* end, const UChar** tokenEnd, int digits)
149{
150 if (end - start < digits)
151 return false;
152
153 for (int i = 0; i < digits; ++i) {
154 if (!isASCIIHexDigit(*start++))
155 return false;
156 }
157
158 *tokenEnd = start;
159 return true;
160}
161
162bool parseStringToken(const UChar* start, const UChar* end, const UChar** tokenEnd)
163{
164 while (start < end) {
165 UChar c = *start++;
166 if ('\\' == c && start < end) {
167 c = *start++;
168 // Make sure the escaped char is valid.
169 switch (c) {
170 case 'x':
171 if (!readHexDigits(start, end, &start, 2))
172 return false;
173 break;
174 case 'u':
175 if (!readHexDigits(start, end, &start, 4))
176 return false;
177 break;
178 case '\\':
179 case '/':
180 case 'b':
181 case 'f':
182 case 'n':
183 case 'r':
184 case 't':
185 case 'v':
186 case '"':
187 break;
188 default:
189 return false;
190 }
191 } else if ('"' == c) {
192 *tokenEnd = start;
193 return true;
194 }
195 }
196
197 return false;
198}
199
200Token parseToken(const UChar* start, const UChar* end, const UChar** tokenStart, const UChar** tokenEnd)
201{
202 while (start < end && isSpaceOrNewline(*start))
203 ++start;
204
205 if (start == end)
206 return Token::Invalid;
207
208 *tokenStart = start;
209
210 switch (*start) {
211 case 'n':
212 if (parseConstToken(start, end, tokenEnd, nullString))
213 return Token::Null;
214 break;
215 case 't':
216 if (parseConstToken(start, end, tokenEnd, trueString))
217 return Token::BoolTrue;
218 break;
219 case 'f':
220 if (parseConstToken(start, end, tokenEnd, falseString))
221 return Token::BoolFalse;
222 break;
223 case '[':
224 *tokenEnd = start + 1;
225 return Token::ArrayBegin;
226 case ']':
227 *tokenEnd = start + 1;
228 return Token::ArrayEnd;
229 case ',':
230 *tokenEnd = start + 1;
231 return Token::ListSeparator;
232 case '{':
233 *tokenEnd = start + 1;
234 return Token::ObjectBegin;
235 case '}':
236 *tokenEnd = start + 1;
237 return Token::ObjectEnd;
238 case ':':
239 *tokenEnd = start + 1;
240 return Token::ObjectPairSeparator;
241 case '0':
242 case '1':
243 case '2':
244 case '3':
245 case '4':
246 case '5':
247 case '6':
248 case '7':
249 case '8':
250 case '9':
251 case '-':
252 if (parseNumberToken(start, end, tokenEnd))
253 return Token::Number;
254 break;
255 case '"':
256 if (parseStringToken(start + 1, end, tokenEnd))
257 return Token::String;
258 break;
259 }
260
261 return Token::Invalid;
262}
263
264bool decodeString(const UChar* start, const UChar* end, StringBuilder& output)
265{
266 while (start < end) {
267 UChar c = *start++;
268 if ('\\' != c) {
269 output.append(c);
270 continue;
271 }
272 if (UNLIKELY(start >= end))
273 return false;
274 c = *start++;
275 switch (c) {
276 case '"':
277 case '/':
278 case '\\':
279 break;
280 case 'b':
281 c = '\b';
282 break;
283 case 'f':
284 c = '\f';
285 break;
286 case 'n':
287 c = '\n';
288 break;
289 case 'r':
290 c = '\r';
291 break;
292 case 't':
293 c = '\t';
294 break;
295 case 'v':
296 c = '\v';
297 break;
298 case 'x':
299 if (UNLIKELY(start + 1 >= end))
300 return false;
301 c = toASCIIHexValue(start[0], start[1]);
302 start += 2;
303 break;
304 case 'u':
305 if (UNLIKELY(start + 3 >= end))
306 return false;
307 c = toASCIIHexValue(start[0], start[1]) << 8 | toASCIIHexValue(start[2], start[3]);
308 start += 4;
309 break;
310 default:
311 return false;
312 }
313 output.append(c);
314 }
315
316 return true;
317}
318
319bool decodeString(const UChar* start, const UChar* end, String& output)
320{
321 if (start == end) {
322 output = emptyString();
323 return true;
324 }
325
326 if (start > end)
327 return false;
328
329 StringBuilder buffer;
330 buffer.reserveCapacity(end - start);
331 if (!decodeString(start, end, buffer))
332 return false;
333
334 output = buffer.toString();
335 return true;
336}
337
338RefPtr<JSON::Value> buildValue(const UChar* start, const UChar* end, const UChar** valueTokenEnd, int depth)
339{
340 if (depth > stackLimit)
341 return nullptr;
342
343 RefPtr<JSON::Value> result;
344 const UChar* tokenStart;
345 const UChar* tokenEnd;
346 Token token = parseToken(start, end, &tokenStart, &tokenEnd);
347 switch (token) {
348 case Token::Invalid:
349 return nullptr;
350 case Token::Null:
351 result = JSON::Value::null();
352 break;
353 case Token::BoolTrue:
354 result = JSON::Value::create(true);
355 break;
356 case Token::BoolFalse:
357 result = JSON::Value::create(false);
358 break;
359 case Token::Number: {
360 bool ok;
361 double value = charactersToDouble(tokenStart, tokenEnd - tokenStart, &ok);
362 if (!ok)
363 return nullptr;
364 result = JSON::Value::create(value);
365 break;
366 }
367 case Token::String: {
368 String value;
369 bool ok = decodeString(tokenStart + 1, tokenEnd - 1, value);
370 if (!ok)
371 return nullptr;
372 result = JSON::Value::create(value);
373 break;
374 }
375 case Token::ArrayBegin: {
376 Ref<JSON::Array> array = JSON::Array::create();
377 start = tokenEnd;
378 token = parseToken(start, end, &tokenStart, &tokenEnd);
379 while (token != Token::ArrayEnd) {
380 RefPtr<JSON::Value> arrayNode = buildValue(start, end, &tokenEnd, depth + 1);
381 if (!arrayNode)
382 return nullptr;
383 array->pushValue(WTFMove(arrayNode));
384
385 // After a list value, we expect a comma or the end of the list.
386 start = tokenEnd;
387 token = parseToken(start, end, &tokenStart, &tokenEnd);
388 if (token == Token::ListSeparator) {
389 start = tokenEnd;
390 token = parseToken(start, end, &tokenStart, &tokenEnd);
391 if (token == Token::ArrayEnd)
392 return nullptr;
393 } else if (token != Token::ArrayEnd) {
394 // Unexpected value after list value. Bail out.
395 return nullptr;
396 }
397 }
398 if (token != Token::ArrayEnd)
399 return nullptr;
400 result = WTFMove(array);
401 break;
402 }
403 case Token::ObjectBegin: {
404 Ref<JSON::Object> object = JSON::Object::create();
405 start = tokenEnd;
406 token = parseToken(start, end, &tokenStart, &tokenEnd);
407 while (token != Token::ObjectEnd) {
408 if (token != Token::String)
409 return nullptr;
410 String key;
411 if (!decodeString(tokenStart + 1, tokenEnd - 1, key))
412 return nullptr;
413 start = tokenEnd;
414
415 token = parseToken(start, end, &tokenStart, &tokenEnd);
416 if (token != Token::ObjectPairSeparator)
417 return nullptr;
418 start = tokenEnd;
419
420 RefPtr<JSON::Value> value = buildValue(start, end, &tokenEnd, depth + 1);
421 if (!value)
422 return nullptr;
423 object->setValue(key, WTFMove(value));
424 start = tokenEnd;
425
426 // After a key/value pair, we expect a comma or the end of the
427 // object.
428 token = parseToken(start, end, &tokenStart, &tokenEnd);
429 if (token == Token::ListSeparator) {
430 start = tokenEnd;
431 token = parseToken(start, end, &tokenStart, &tokenEnd);
432 if (token == Token::ObjectEnd)
433 return nullptr;
434 } else if (token != Token::ObjectEnd) {
435 // Unexpected value after last object value. Bail out.
436 return nullptr;
437 }
438 }
439 if (token != Token::ObjectEnd)
440 return nullptr;
441 result = WTFMove(object);
442 break;
443 }
444
445 default:
446 // We got a token that's not a value.
447 return nullptr;
448 }
449 *valueTokenEnd = tokenEnd;
450 return result;
451}
452
453inline void appendDoubleQuotedString(StringBuilder& builder, StringView string)
454{
455 builder.append('"');
456 for (UChar codeUnit : string.codeUnits()) {
457 switch (codeUnit) {
458 case '\b':
459 builder.appendLiteral("\\b");
460 continue;
461 case '\f':
462 builder.appendLiteral("\\f");
463 continue;
464 case '\n':
465 builder.appendLiteral("\\n");
466 continue;
467 case '\r':
468 builder.appendLiteral("\\r");
469 continue;
470 case '\t':
471 builder.appendLiteral("\\t");
472 continue;
473 case '\\':
474 builder.appendLiteral("\\\\");
475 continue;
476 case '"':
477 builder.appendLiteral("\\\"");
478 continue;
479 }
480 // We escape < and > to prevent script execution.
481 if (codeUnit >= 32 && codeUnit < 127 && codeUnit != '<' && codeUnit != '>') {
482 builder.append(codeUnit);
483 continue;
484 }
485 // We could encode characters >= 127 as UTF-8 instead of \u escape sequences.
486 // We could handle surrogates here if callers wanted that; for now we just
487 // write them out as a \u sequence, so a surrogate pair appears as two of them.
488 builder.append("\\u",
489 upperNibbleToASCIIHexDigit(codeUnit >> 8), lowerNibbleToASCIIHexDigit(codeUnit >> 8),
490 upperNibbleToASCIIHexDigit(codeUnit), lowerNibbleToASCIIHexDigit(codeUnit));
491 }
492 builder.append('"');
493}
494
495} // anonymous namespace
496
497Ref<Value> Value::null()
498{
499 return adoptRef(*new Value);
500}
501
502Ref<Value> Value::create(bool value)
503{
504 return adoptRef(*new Value(value));
505}
506
507Ref<Value> Value::create(int value)
508{
509 return adoptRef(*new Value(value));
510}
511
512Ref<Value> Value::create(double value)
513{
514 return adoptRef(*new Value(value));
515}
516
517Ref<Value> Value::create(const String& value)
518{
519 return adoptRef(*new Value(value));
520}
521
522Ref<Value> Value::create(const char* value)
523{
524 return adoptRef(*new Value(value));
525}
526
527bool Value::asValue(RefPtr<Value>& value)
528{
529 value = this;
530 return true;
531}
532
533bool Value::asObject(RefPtr<Object>&)
534{
535 return false;
536}
537
538bool Value::asArray(RefPtr<Array>&)
539{
540 return false;
541}
542
543bool Value::parseJSON(const String& jsonInput, RefPtr<Value>& output)
544{
545 // FIXME: This whole file should just use StringView instead of UChar/length and avoid upconverting.
546 auto characters = StringView(jsonInput).upconvertedCharacters();
547 const UChar* start = characters;
548 const UChar* end = start + jsonInput.length();
549 const UChar* tokenEnd;
550 auto result = buildValue(start, end, &tokenEnd, 0);
551 if (!result)
552 return false;
553
554 for (const UChar* valueEnd = tokenEnd; valueEnd < end; ++valueEnd) {
555 if (!isSpaceOrNewline(*valueEnd))
556 return false;
557 }
558
559 output = WTFMove(result);
560 return true;
561}
562
563String Value::toJSONString() const
564{
565 StringBuilder result;
566 result.reserveCapacity(512);
567 writeJSON(result);
568 return result.toString();
569}
570
571bool Value::asBoolean(bool& output) const
572{
573 if (type() != Type::Boolean)
574 return false;
575
576 output = m_value.boolean;
577 return true;
578}
579
580bool Value::asDouble(double& output) const
581{
582 if (type() != Type::Double)
583 return false;
584
585 output = m_value.number;
586 return true;
587}
588
589bool Value::asDouble(float& output) const
590{
591 if (type() != Type::Double)
592 return false;
593
594 output = static_cast<float>(m_value.number);
595 return true;
596}
597
598bool Value::asInteger(int& output) const
599{
600 if (type() != Type::Integer && type() != Type::Double)
601 return false;
602
603 output = static_cast<int>(m_value.number);
604 return true;
605}
606
607bool Value::asInteger(unsigned& output) const
608{
609 if (type() != Type::Integer && type() != Type::Double)
610 return false;
611
612 output = static_cast<unsigned>(m_value.number);
613 return true;
614}
615
616bool Value::asInteger(long& output) const
617{
618 if (type() != Type::Integer && type() != Type::Double)
619 return false;
620
621 output = static_cast<long>(m_value.number);
622 return true;
623}
624
625bool Value::asInteger(long long& output) const
626{
627 if (type() != Type::Integer && type() != Type::Double)
628 return false;
629
630 output = static_cast<long long>(m_value.number);
631 return true;
632}
633
634bool Value::asInteger(unsigned long& output) const
635{
636 if (type() != Type::Integer && type() != Type::Double)
637 return false;
638
639 output = static_cast<unsigned long>(m_value.number);
640 return true;
641}
642
643bool Value::asInteger(unsigned long long& output) const
644{
645 if (type() != Type::Integer && type() != Type::Double)
646 return false;
647
648 output = static_cast<unsigned long long>(m_value.number);
649 return true;
650}
651
652bool Value::asString(String& output) const
653{
654 if (type() != Type::String)
655 return false;
656
657 output = m_value.string;
658 return true;
659}
660
661void Value::writeJSON(StringBuilder& output) const
662{
663 switch (m_type) {
664 case Type::Null:
665 output.appendLiteral("null");
666 break;
667 case Type::Boolean:
668 if (m_value.boolean)
669 output.appendLiteral("true");
670 else
671 output.appendLiteral("false");
672 break;
673 case Type::String:
674 appendDoubleQuotedString(output, m_value.string);
675 break;
676 case Type::Double:
677 case Type::Integer: {
678 if (!std::isfinite(m_value.number))
679 output.appendLiteral("null");
680 else
681 output.appendNumber(m_value.number);
682 break;
683 }
684 default:
685 ASSERT_NOT_REACHED();
686 }
687}
688
689size_t Value::memoryCost() const
690{
691 size_t memoryCost = sizeof(this);
692 if (m_type == Type::String && m_value.string)
693 memoryCost += m_value.string->sizeInBytes();
694 return memoryCost;
695}
696
697ObjectBase::~ObjectBase()
698{
699}
700
701bool ObjectBase::asObject(RefPtr<Object>& output)
702{
703 COMPILE_ASSERT(sizeof(Object) == sizeof(ObjectBase), cannot_cast);
704
705 output = static_cast<Object*>(this);
706 return true;
707}
708
709Object* ObjectBase::openAccessors()
710{
711 COMPILE_ASSERT(sizeof(Object) == sizeof(ObjectBase), cannot_cast);
712
713 return static_cast<Object*>(this);
714}
715
716size_t ObjectBase::memoryCost() const
717{
718 size_t memoryCost = Value::memoryCost();
719 for (const auto& entry : m_map) {
720 memoryCost += entry.key.sizeInBytes();
721 if (entry.value)
722 memoryCost += entry.value->memoryCost();
723 }
724 return memoryCost;
725}
726
727bool ObjectBase::getBoolean(const String& name, bool& output) const
728{
729 RefPtr<Value> value;
730 if (!getValue(name, value))
731 return false;
732
733 return value->asBoolean(output);
734}
735
736bool ObjectBase::getString(const String& name, String& output) const
737{
738 RefPtr<Value> value;
739 if (!getValue(name, value))
740 return false;
741
742 return value->asString(output);
743}
744
745bool ObjectBase::getObject(const String& name, RefPtr<Object>& output) const
746{
747 RefPtr<Value> value;
748 if (!getValue(name, value))
749 return false;
750
751 return value->asObject(output);
752}
753
754bool ObjectBase::getArray(const String& name, RefPtr<Array>& output) const
755{
756 RefPtr<Value> value;
757 if (!getValue(name, value))
758 return false;
759
760 return value->asArray(output);
761}
762
763bool ObjectBase::getValue(const String& name, RefPtr<Value>& output) const
764{
765 Dictionary::const_iterator findResult = m_map.find(name);
766 if (findResult == m_map.end())
767 return false;
768
769 output = findResult->value;
770 return true;
771}
772
773void ObjectBase::remove(const String& name)
774{
775 m_map.remove(name);
776 m_order.removeFirst(name);
777}
778
779void ObjectBase::writeJSON(StringBuilder& output) const
780{
781 output.append('{');
782 for (size_t i = 0; i < m_order.size(); ++i) {
783 auto findResult = m_map.find(m_order[i]);
784 ASSERT(findResult != m_map.end());
785 if (i)
786 output.append(',');
787 appendDoubleQuotedString(output, findResult->key);
788 output.append(':');
789 findResult->value->writeJSON(output);
790 }
791 output.append('}');
792}
793
794ObjectBase::ObjectBase()
795 : Value(Type::Object)
796 , m_map()
797 , m_order()
798{
799}
800
801ArrayBase::~ArrayBase()
802{
803}
804
805bool ArrayBase::asArray(RefPtr<Array>& output)
806{
807 COMPILE_ASSERT(sizeof(ArrayBase) == sizeof(Array), cannot_cast);
808 output = static_cast<Array*>(this);
809 return true;
810}
811
812void ArrayBase::writeJSON(StringBuilder& output) const
813{
814 output.append('[');
815 for (Vector<RefPtr<Value>>::const_iterator it = m_map.begin(); it != m_map.end(); ++it) {
816 if (it != m_map.begin())
817 output.append(',');
818 (*it)->writeJSON(output);
819 }
820 output.append(']');
821}
822
823ArrayBase::ArrayBase()
824 : Value(Type::Array)
825 , m_map()
826{
827}
828
829RefPtr<Value> ArrayBase::get(size_t index) const
830{
831 RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(index < m_map.size());
832 return m_map[index];
833}
834
835Ref<Object> Object::create()
836{
837 return adoptRef(*new Object);
838}
839
840Ref<Array> Array::create()
841{
842 return adoptRef(*new Array);
843}
844
845size_t ArrayBase::memoryCost() const
846{
847 size_t memoryCost = Value::memoryCost();
848 for (const auto& item : m_map) {
849 if (item)
850 memoryCost += item->memoryCost();
851 }
852 return memoryCost;
853}
854
855} // namespace JSONImpl
856} // namespace WTF
857