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