1 // Copyright 2016 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/json/json-parser.h"
6
7 #include "src/base/strings.h"
8 #include "src/common/globals.h"
9 #include "src/common/message-template.h"
10 #include "src/debug/debug.h"
11 #include "src/execution/frames-inl.h"
12 #include "src/numbers/conversions.h"
13 #include "src/numbers/hash-seed-inl.h"
14 #include "src/objects/field-type.h"
15 #include "src/objects/hash-table-inl.h"
16 #include "src/objects/map-updater.h"
17 #include "src/objects/objects-inl.h"
18 #include "src/objects/property-descriptor.h"
19 #include "src/strings/char-predicates-inl.h"
20 #include "src/strings/string-hasher.h"
21
22 namespace v8 {
23 namespace internal {
24
25 namespace {
26
GetOneCharJsonToken(uint8_t c)27 constexpr JsonToken GetOneCharJsonToken(uint8_t c) {
28 // clang-format off
29 return
30 c == '"' ? JsonToken::STRING :
31 IsDecimalDigit(c) ? JsonToken::NUMBER :
32 c == '-' ? JsonToken::NUMBER :
33 c == '[' ? JsonToken::LBRACK :
34 c == '{' ? JsonToken::LBRACE :
35 c == ']' ? JsonToken::RBRACK :
36 c == '}' ? JsonToken::RBRACE :
37 c == 't' ? JsonToken::TRUE_LITERAL :
38 c == 'f' ? JsonToken::FALSE_LITERAL :
39 c == 'n' ? JsonToken::NULL_LITERAL :
40 c == ' ' ? JsonToken::WHITESPACE :
41 c == '\t' ? JsonToken::WHITESPACE :
42 c == '\r' ? JsonToken::WHITESPACE :
43 c == '\n' ? JsonToken::WHITESPACE :
44 c == ':' ? JsonToken::COLON :
45 c == ',' ? JsonToken::COMMA :
46 JsonToken::ILLEGAL;
47 // clang-format on
48 }
49
50 // Table of one-character tokens, by character (0x00..0xFF only).
51 static const constexpr JsonToken one_char_json_tokens[256] = {
52 #define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(N),
53 INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
54 #undef CALL_GET_SCAN_FLAGS
55 #define CALL_GET_SCAN_FLAGS(N) GetOneCharJsonToken(128 + N),
56 INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
57 #undef CALL_GET_SCAN_FLAGS
58 };
59
60 enum class EscapeKind : uint8_t {
61 kIllegal,
62 kSelf,
63 kBackspace,
64 kTab,
65 kNewLine,
66 kFormFeed,
67 kCarriageReturn,
68 kUnicode
69 };
70
71 using EscapeKindField = base::BitField8<EscapeKind, 0, 3>;
72 using MayTerminateStringField = EscapeKindField::Next<bool, 1>;
73 using NumberPartField = MayTerminateStringField::Next<bool, 1>;
74
MayTerminateJsonString(uint8_t flags)75 constexpr bool MayTerminateJsonString(uint8_t flags) {
76 return MayTerminateStringField::decode(flags);
77 }
78
GetEscapeKind(uint8_t flags)79 constexpr EscapeKind GetEscapeKind(uint8_t flags) {
80 return EscapeKindField::decode(flags);
81 }
82
IsNumberPart(uint8_t flags)83 constexpr bool IsNumberPart(uint8_t flags) {
84 return NumberPartField::decode(flags);
85 }
86
GetJsonScanFlags(uint8_t c)87 constexpr uint8_t GetJsonScanFlags(uint8_t c) {
88 // clang-format off
89 return (c == 'b' ? EscapeKindField::encode(EscapeKind::kBackspace)
90 : c == 't' ? EscapeKindField::encode(EscapeKind::kTab)
91 : c == 'n' ? EscapeKindField::encode(EscapeKind::kNewLine)
92 : c == 'f' ? EscapeKindField::encode(EscapeKind::kFormFeed)
93 : c == 'r' ? EscapeKindField::encode(EscapeKind::kCarriageReturn)
94 : c == 'u' ? EscapeKindField::encode(EscapeKind::kUnicode)
95 : c == '"' ? EscapeKindField::encode(EscapeKind::kSelf)
96 : c == '\\' ? EscapeKindField::encode(EscapeKind::kSelf)
97 : c == '/' ? EscapeKindField::encode(EscapeKind::kSelf)
98 : EscapeKindField::encode(EscapeKind::kIllegal)) |
99 (c < 0x20 ? MayTerminateStringField::encode(true)
100 : c == '"' ? MayTerminateStringField::encode(true)
101 : c == '\\' ? MayTerminateStringField::encode(true)
102 : MayTerminateStringField::encode(false)) |
103 NumberPartField::encode(c == '.' ||
104 c == 'e' ||
105 c == 'E' ||
106 IsDecimalDigit(c) ||
107 c == '-' ||
108 c == '+');
109 // clang-format on
110 }
111
112 // Table of one-character scan flags, by character (0x00..0xFF only).
113 static const constexpr uint8_t character_json_scan_flags[256] = {
114 #define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(N),
115 INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
116 #undef CALL_GET_SCAN_FLAGS
117 #define CALL_GET_SCAN_FLAGS(N) GetJsonScanFlags(128 + N),
118 INT_0_TO_127_LIST(CALL_GET_SCAN_FLAGS)
119 #undef CALL_GET_SCAN_FLAGS
120 };
121
122 } // namespace
123
Internalize(Isolate * isolate,Handle<Object> object,Handle<Object> reviver)124 MaybeHandle<Object> JsonParseInternalizer::Internalize(Isolate* isolate,
125 Handle<Object> object,
126 Handle<Object> reviver) {
127 DCHECK(reviver->IsCallable());
128 JsonParseInternalizer internalizer(isolate,
129 Handle<JSReceiver>::cast(reviver));
130 Handle<JSObject> holder =
131 isolate->factory()->NewJSObject(isolate->object_function());
132 Handle<String> name = isolate->factory()->empty_string();
133 JSObject::AddProperty(isolate, holder, name, object, NONE);
134 return internalizer.InternalizeJsonProperty(holder, name);
135 }
136
InternalizeJsonProperty(Handle<JSReceiver> holder,Handle<String> name)137 MaybeHandle<Object> JsonParseInternalizer::InternalizeJsonProperty(
138 Handle<JSReceiver> holder, Handle<String> name) {
139 HandleScope outer_scope(isolate_);
140 Handle<Object> value;
141 ASSIGN_RETURN_ON_EXCEPTION(
142 isolate_, value, Object::GetPropertyOrElement(isolate_, holder, name),
143 Object);
144 if (value->IsJSReceiver()) {
145 Handle<JSReceiver> object = Handle<JSReceiver>::cast(value);
146 Maybe<bool> is_array = Object::IsArray(object);
147 if (is_array.IsNothing()) return MaybeHandle<Object>();
148 if (is_array.FromJust()) {
149 Handle<Object> length_object;
150 ASSIGN_RETURN_ON_EXCEPTION(
151 isolate_, length_object,
152 Object::GetLengthFromArrayLike(isolate_, object), Object);
153 double length = length_object->Number();
154 for (double i = 0; i < length; i++) {
155 HandleScope inner_scope(isolate_);
156 Handle<Object> index = isolate_->factory()->NewNumber(i);
157 Handle<String> index_name = isolate_->factory()->NumberToString(index);
158 if (!RecurseAndApply(object, index_name)) return MaybeHandle<Object>();
159 }
160 } else {
161 Handle<FixedArray> contents;
162 ASSIGN_RETURN_ON_EXCEPTION(
163 isolate_, contents,
164 KeyAccumulator::GetKeys(object, KeyCollectionMode::kOwnOnly,
165 ENUMERABLE_STRINGS,
166 GetKeysConversion::kConvertToString),
167 Object);
168 for (int i = 0; i < contents->length(); i++) {
169 HandleScope inner_scope(isolate_);
170 Handle<String> key_name(String::cast(contents->get(i)), isolate_);
171 if (!RecurseAndApply(object, key_name)) return MaybeHandle<Object>();
172 }
173 }
174 }
175 Handle<Object> argv[] = {name, value};
176 Handle<Object> result;
177 ASSIGN_RETURN_ON_EXCEPTION(
178 isolate_, result, Execution::Call(isolate_, reviver_, holder, 2, argv),
179 Object);
180 return outer_scope.CloseAndEscape(result);
181 }
182
RecurseAndApply(Handle<JSReceiver> holder,Handle<String> name)183 bool JsonParseInternalizer::RecurseAndApply(Handle<JSReceiver> holder,
184 Handle<String> name) {
185 STACK_CHECK(isolate_, false);
186
187 Handle<Object> result;
188 ASSIGN_RETURN_ON_EXCEPTION_VALUE(
189 isolate_, result, InternalizeJsonProperty(holder, name), false);
190 Maybe<bool> change_result = Nothing<bool>();
191 if (result->IsUndefined(isolate_)) {
192 change_result = JSReceiver::DeletePropertyOrElement(holder, name,
193 LanguageMode::kSloppy);
194 } else {
195 PropertyDescriptor desc;
196 desc.set_value(result);
197 desc.set_configurable(true);
198 desc.set_enumerable(true);
199 desc.set_writable(true);
200 change_result = JSReceiver::DefineOwnProperty(isolate_, holder, name, &desc,
201 Just(kDontThrow));
202 }
203 MAYBE_RETURN(change_result, false);
204 return true;
205 }
206
207 template <typename Char>
JsonParser(Isolate * isolate,Handle<String> source)208 JsonParser<Char>::JsonParser(Isolate* isolate, Handle<String> source)
209 : isolate_(isolate),
210 hash_seed_(HashSeed(isolate)),
211 object_constructor_(isolate_->object_function()),
212 original_source_(source) {
213 size_t start = 0;
214 size_t length = source->length();
215 PtrComprCageBase cage_base(isolate);
216 if (source->IsSlicedString(cage_base)) {
217 SlicedString string = SlicedString::cast(*source);
218 start = string.offset();
219 String parent = string.parent(cage_base);
220 if (parent.IsThinString(cage_base))
221 parent = ThinString::cast(parent).actual(cage_base);
222 source_ = handle(parent, isolate);
223 } else {
224 source_ = String::Flatten(isolate, source);
225 }
226
227 if (StringShape(*source_, cage_base).IsExternal()) {
228 chars_ = static_cast<const Char*>(
229 SeqExternalString::cast(*source_).GetChars(cage_base));
230 chars_may_relocate_ = false;
231 } else {
232 DisallowGarbageCollection no_gc;
233 isolate->main_thread_local_heap()->AddGCEpilogueCallback(
234 UpdatePointersCallback, this);
235 chars_ = SeqString::cast(*source_).GetChars(no_gc);
236 chars_may_relocate_ = true;
237 }
238 cursor_ = chars_ + start;
239 end_ = cursor_ + length;
240 }
241
242 template <typename Char>
ReportUnexpectedToken(JsonToken token)243 void JsonParser<Char>::ReportUnexpectedToken(JsonToken token) {
244 // Some exception (for example stack overflow) is already pending.
245 if (isolate_->has_pending_exception()) return;
246
247 // Parse failed. Current character is the unexpected token.
248 Factory* factory = this->factory();
249 MessageTemplate message;
250 int offset = original_source_->IsSlicedString()
251 ? SlicedString::cast(*original_source_).offset()
252 : 0;
253 int pos = position() - offset;
254 Handle<Object> arg1 = Handle<Smi>(Smi::FromInt(pos), isolate());
255 Handle<Object> arg2;
256
257 switch (token) {
258 case JsonToken::EOS:
259 message = MessageTemplate::kJsonParseUnexpectedEOS;
260 break;
261 case JsonToken::NUMBER:
262 message = MessageTemplate::kJsonParseUnexpectedTokenNumber;
263 break;
264 case JsonToken::STRING:
265 message = MessageTemplate::kJsonParseUnexpectedTokenString;
266 break;
267 default:
268 message = MessageTemplate::kJsonParseUnexpectedToken;
269 arg2 = arg1;
270 arg1 = factory->LookupSingleCharacterStringFromCode(*cursor_);
271 break;
272 }
273
274 Handle<Script> script(factory->NewScript(original_source_));
275 if (isolate()->NeedsSourcePositionsForProfiling()) {
276 Script::InitLineEnds(isolate(), script);
277 }
278
279 StackTraceFrameIterator it(isolate_);
280 if (!it.done() && it.is_javascript()) {
281 FrameSummary summary = it.GetTopValidFrame();
282 script->set_eval_from_shared(summary.AsJavaScript().function()->shared());
283 if (summary.script()->IsScript()) {
284 script->set_origin_options(
285 Script::cast(*summary.script()).origin_options());
286 }
287 }
288
289 // We should sent compile error event because we compile JSON object in
290 // separated source file.
291 isolate()->debug()->OnCompileError(script);
292 MessageLocation location(script, pos, pos + 1);
293 isolate()->ThrowAt(factory->NewSyntaxError(message, arg1, arg2), &location);
294
295 // Move the cursor to the end so we won't be able to proceed parsing.
296 cursor_ = end_;
297 }
298
299 template <typename Char>
ReportUnexpectedCharacter(base::uc32 c)300 void JsonParser<Char>::ReportUnexpectedCharacter(base::uc32 c) {
301 JsonToken token = JsonToken::ILLEGAL;
302 if (c == kEndOfString) {
303 token = JsonToken::EOS;
304 } else if (c <= unibrow::Latin1::kMaxChar) {
305 token = one_char_json_tokens[c];
306 }
307 return ReportUnexpectedToken(token);
308 }
309
310 template <typename Char>
~JsonParser()311 JsonParser<Char>::~JsonParser() {
312 if (StringShape(*source_).IsExternal()) {
313 // Check that the string shape hasn't changed. Otherwise our GC hooks are
314 // broken.
315 SeqExternalString::cast(*source_);
316 } else {
317 // Check that the string shape hasn't changed. Otherwise our GC hooks are
318 // broken.
319 SeqString::cast(*source_);
320 isolate()->main_thread_local_heap()->RemoveGCEpilogueCallback(
321 UpdatePointersCallback, this);
322 }
323 }
324
325 template <typename Char>
ParseJson()326 MaybeHandle<Object> JsonParser<Char>::ParseJson() {
327 MaybeHandle<Object> result = ParseJsonValue();
328 if (!Check(JsonToken::EOS)) ReportUnexpectedToken(peek());
329 if (isolate_->has_pending_exception()) return MaybeHandle<Object>();
330 return result;
331 }
332
333 MaybeHandle<Object> InternalizeJsonProperty(Handle<JSObject> holder,
334 Handle<String> key);
335
336 template <typename Char>
SkipWhitespace()337 void JsonParser<Char>::SkipWhitespace() {
338 next_ = JsonToken::EOS;
339
340 cursor_ = std::find_if(cursor_, end_, [this](Char c) {
341 JsonToken current = V8_LIKELY(c <= unibrow::Latin1::kMaxChar)
342 ? one_char_json_tokens[c]
343 : JsonToken::ILLEGAL;
344 bool result = current != JsonToken::WHITESPACE;
345 if (result) next_ = current;
346 return result;
347 });
348 }
349
350 template <typename Char>
ScanUnicodeCharacter()351 base::uc32 JsonParser<Char>::ScanUnicodeCharacter() {
352 base::uc32 value = 0;
353 for (int i = 0; i < 4; i++) {
354 int digit = base::HexValue(NextCharacter());
355 if (V8_UNLIKELY(digit < 0)) return kInvalidUnicodeCharacter;
356 value = value * 16 + digit;
357 }
358 return value;
359 }
360
361 // Parse any JSON value.
362 template <typename Char>
ScanJsonPropertyKey(JsonContinuation * cont)363 JsonString JsonParser<Char>::ScanJsonPropertyKey(JsonContinuation* cont) {
364 {
365 DisallowGarbageCollection no_gc;
366 const Char* start = cursor_;
367 base::uc32 first = CurrentCharacter();
368 if (first == '\\' && NextCharacter() == 'u') first = ScanUnicodeCharacter();
369 if (IsDecimalDigit(first)) {
370 if (first == '0') {
371 if (NextCharacter() == '"') {
372 advance();
373 // Record element information.
374 cont->elements++;
375 DCHECK_LE(0, cont->max_index);
376 return JsonString(0);
377 }
378 } else {
379 uint32_t index = first - '0';
380 while (true) {
381 cursor_ = std::find_if(cursor_ + 1, end_, [&index](Char c) {
382 return !TryAddArrayIndexChar(&index, c);
383 });
384
385 if (CurrentCharacter() == '"') {
386 advance();
387 // Record element information.
388 cont->elements++;
389 cont->max_index = std::max(cont->max_index, index);
390 return JsonString(index);
391 }
392
393 if (CurrentCharacter() == '\\' && NextCharacter() == 'u') {
394 if (TryAddArrayIndexChar(&index, ScanUnicodeCharacter())) continue;
395 }
396
397 break;
398 }
399 }
400 }
401 // Reset cursor_ to start if the key is not an index.
402 cursor_ = start;
403 }
404 return ScanJsonString(true);
405 }
406
407 namespace {
ParentOfDescriptorOwner(Isolate * isolate,Handle<Map> maybe_root,Handle<Map> source,int descriptor)408 Handle<Map> ParentOfDescriptorOwner(Isolate* isolate, Handle<Map> maybe_root,
409 Handle<Map> source, int descriptor) {
410 if (descriptor == 0) {
411 DCHECK_EQ(0, maybe_root->NumberOfOwnDescriptors());
412 return maybe_root;
413 }
414 return handle(source->FindFieldOwner(isolate, InternalIndex(descriptor - 1)),
415 isolate);
416 }
417 } // namespace
418
419 template <typename Char>
BuildJsonObject(const JsonContinuation & cont,const SmallVector<JsonProperty> & property_stack,Handle<Map> feedback)420 Handle<Object> JsonParser<Char>::BuildJsonObject(
421 const JsonContinuation& cont,
422 const SmallVector<JsonProperty>& property_stack, Handle<Map> feedback) {
423 size_t start = cont.index;
424 int length = static_cast<int>(property_stack.size() - start);
425 int named_length = length - cont.elements;
426
427 Handle<Map> initial_map = factory()->ObjectLiteralMapFromCache(
428 isolate_->native_context(), named_length);
429
430 Handle<Map> map = initial_map;
431
432 Handle<FixedArrayBase> elements = factory()->empty_fixed_array();
433
434 // First store the elements.
435 if (cont.elements > 0) {
436 // Store as dictionary elements if that would use less memory.
437 if (ShouldConvertToSlowElements(cont.elements, cont.max_index + 1)) {
438 Handle<NumberDictionary> elms =
439 NumberDictionary::New(isolate_, cont.elements);
440 for (int i = 0; i < length; i++) {
441 const JsonProperty& property = property_stack[start + i];
442 if (!property.string.is_index()) continue;
443 uint32_t index = property.string.index();
444 Handle<Object> value = property.value;
445 elms = NumberDictionary::Set(isolate_, elms, index, value);
446 }
447 map = Map::AsElementsKind(isolate_, map, DICTIONARY_ELEMENTS);
448 elements = elms;
449 } else {
450 Handle<FixedArray> elms =
451 factory()->NewFixedArrayWithHoles(cont.max_index + 1);
452 DisallowGarbageCollection no_gc;
453 WriteBarrierMode mode = elms->GetWriteBarrierMode(no_gc);
454 DCHECK_EQ(HOLEY_ELEMENTS, map->elements_kind());
455
456 for (int i = 0; i < length; i++) {
457 const JsonProperty& property = property_stack[start + i];
458 if (!property.string.is_index()) continue;
459 uint32_t index = property.string.index();
460 Handle<Object> value = property.value;
461 elms->set(static_cast<int>(index), *value, mode);
462 }
463 elements = elms;
464 }
465 }
466
467 int feedback_descriptors =
468 (feedback.is_null() ||
469 feedback->elements_kind() != map->elements_kind() ||
470 feedback->instance_size() != map->instance_size())
471 ? 0
472 : feedback->NumberOfOwnDescriptors();
473
474 int i;
475 int descriptor = 0;
476 int new_mutable_double = 0;
477 for (i = 0; i < length; i++) {
478 const JsonProperty& property = property_stack[start + i];
479 if (property.string.is_index()) continue;
480 Handle<String> expected;
481 Handle<Map> target;
482 InternalIndex descriptor_index(descriptor);
483 if (descriptor < feedback_descriptors) {
484 expected =
485 handle(String::cast(feedback->instance_descriptors(isolate_).GetKey(
486 descriptor_index)),
487 isolate_);
488 } else {
489 TransitionsAccessor transitions(isolate(), *map);
490 expected = transitions.ExpectedTransitionKey();
491 if (!expected.is_null()) {
492 // Directly read out the target while reading out the key, otherwise it
493 // might die while building the string below.
494 target =
495 TransitionsAccessor(isolate(), *map).ExpectedTransitionTarget();
496 }
497 }
498
499 Handle<String> key = MakeString(property.string, expected);
500 if (key.is_identical_to(expected)) {
501 if (descriptor < feedback_descriptors) target = feedback;
502 } else {
503 if (descriptor < feedback_descriptors) {
504 map = ParentOfDescriptorOwner(isolate_, map, feedback, descriptor);
505 feedback_descriptors = 0;
506 }
507 if (!TransitionsAccessor(isolate(), *map)
508 .FindTransitionToField(key)
509 .ToHandle(&target)) {
510 break;
511 }
512 }
513
514 Handle<Object> value = property.value;
515
516 PropertyDetails details =
517 target->instance_descriptors(isolate_).GetDetails(descriptor_index);
518 Representation expected_representation = details.representation();
519
520 if (!value->FitsRepresentation(expected_representation)) {
521 Representation representation = value->OptimalRepresentation(isolate());
522 representation = representation.generalize(expected_representation);
523 if (!expected_representation.CanBeInPlaceChangedTo(representation)) {
524 map = ParentOfDescriptorOwner(isolate_, map, target, descriptor);
525 break;
526 }
527 Handle<FieldType> value_type =
528 value->OptimalType(isolate(), representation);
529 MapUpdater::GeneralizeField(isolate(), target, descriptor_index,
530 details.constness(), representation,
531 value_type);
532 } else if (expected_representation.IsHeapObject() &&
533 !target->instance_descriptors(isolate())
534 .GetFieldType(descriptor_index)
535 .NowContains(value)) {
536 Handle<FieldType> value_type =
537 value->OptimalType(isolate(), expected_representation);
538 MapUpdater::GeneralizeField(isolate(), target, descriptor_index,
539 details.constness(), expected_representation,
540 value_type);
541 } else if (expected_representation.IsDouble() && value->IsSmi()) {
542 new_mutable_double++;
543 }
544
545 DCHECK(target->instance_descriptors(isolate())
546 .GetFieldType(descriptor_index)
547 .NowContains(value));
548 map = target;
549 descriptor++;
550 }
551
552 // Fast path: Write all transitioned named properties.
553 if (i == length && descriptor < feedback_descriptors) {
554 map = ParentOfDescriptorOwner(isolate_, map, map, descriptor);
555 }
556
557 // Preallocate all mutable heap numbers so we don't need to allocate while
558 // setting up the object. Otherwise verification of that object may fail.
559 Handle<ByteArray> mutable_double_buffer;
560 // Allocate enough space so we can double-align the payload.
561 const int kMutableDoubleSize = sizeof(double) * 2;
562 STATIC_ASSERT(HeapNumber::kSize <= kMutableDoubleSize);
563 if (new_mutable_double > 0) {
564 mutable_double_buffer =
565 factory()->NewByteArray(kMutableDoubleSize * new_mutable_double);
566 }
567
568 Handle<JSObject> object = initial_map->is_dictionary_map()
569 ? factory()->NewSlowJSObjectFromMap(map)
570 : factory()->NewJSObjectFromMap(map);
571 object->set_elements(*elements);
572
573 {
574 descriptor = 0;
575 DisallowGarbageCollection no_gc;
576 WriteBarrierMode mode = object->GetWriteBarrierMode(no_gc);
577 Address mutable_double_address =
578 mutable_double_buffer.is_null()
579 ? 0
580 : reinterpret_cast<Address>(
581 mutable_double_buffer->GetDataStartAddress());
582 Address filler_address = mutable_double_address;
583 if (kTaggedSize != kDoubleSize) {
584 if (IsAligned(mutable_double_address, kDoubleAlignment)) {
585 mutable_double_address += kTaggedSize;
586 } else {
587 filler_address += HeapNumber::kSize;
588 }
589 }
590 for (int j = 0; j < i; j++) {
591 const JsonProperty& property = property_stack[start + j];
592 if (property.string.is_index()) continue;
593 InternalIndex descriptor_index(descriptor);
594 PropertyDetails details =
595 map->instance_descriptors(isolate()).GetDetails(descriptor_index);
596 Object value = *property.value;
597 FieldIndex index = FieldIndex::ForDescriptor(*map, descriptor_index);
598 descriptor++;
599
600 if (details.representation().IsDouble()) {
601 if (value.IsSmi()) {
602 if (kTaggedSize != kDoubleSize) {
603 // Write alignment filler.
604 HeapObject filler = HeapObject::FromAddress(filler_address);
605 filler.set_map_after_allocation(
606 *factory()->one_pointer_filler_map());
607 filler_address += kMutableDoubleSize;
608 }
609
610 uint64_t bits =
611 bit_cast<uint64_t>(static_cast<double>(Smi::ToInt(value)));
612 // Allocate simple heapnumber with immortal map, with non-pointer
613 // payload, so we can skip notifying object layout change.
614
615 HeapObject hn = HeapObject::FromAddress(mutable_double_address);
616 hn.set_map_after_allocation(*factory()->heap_number_map());
617 HeapNumber::cast(hn).set_value_as_bits(bits, kRelaxedStore);
618 value = hn;
619 mutable_double_address += kMutableDoubleSize;
620 } else {
621 DCHECK(value.IsHeapNumber());
622 HeapObject::cast(value).set_map(*factory()->heap_number_map(),
623 kReleaseStore);
624 }
625 }
626 object->RawFastInobjectPropertyAtPut(index, value, mode);
627 }
628 // Make all mutable HeapNumbers alive.
629 if (!mutable_double_buffer.is_null()) {
630 #ifdef DEBUG
631 Address end =
632 reinterpret_cast<Address>(mutable_double_buffer->GetDataEndAddress());
633 if (kTaggedSize != kDoubleSize) {
634 DCHECK_EQ(std::min(filler_address, mutable_double_address), end);
635 DCHECK_GE(filler_address, end);
636 DCHECK_GE(mutable_double_address, end);
637 } else {
638 DCHECK_EQ(mutable_double_address, end);
639 }
640 #endif
641 // Before setting the length of mutable_double_buffer back to zero, we
642 // must ensure that the sweeper is not running or has already swept the
643 // object's page. Otherwise the GC can add the contents of
644 // mutable_double_buffer to the free list.
645 isolate()->heap()->EnsureSweepingCompleted(*mutable_double_buffer);
646 mutable_double_buffer->set_length(0);
647 }
648 }
649
650 // Slow path: define remaining named properties.
651 for (; i < length; i++) {
652 HandleScope scope(isolate_);
653 const JsonProperty& property = property_stack[start + i];
654 if (property.string.is_index()) continue;
655 Handle<String> key = MakeString(property.string);
656 #ifdef DEBUG
657 uint32_t index;
658 DCHECK(!key->AsArrayIndex(&index));
659 #endif
660 Handle<Object> value = property.value;
661 LookupIterator it(isolate_, object, key, object, LookupIterator::OWN);
662 JSObject::DefineOwnPropertyIgnoreAttributes(&it, value, NONE).Check();
663 }
664
665 return object;
666 }
667
668 template <typename Char>
BuildJsonArray(const JsonContinuation & cont,const SmallVector<Handle<Object>> & element_stack)669 Handle<Object> JsonParser<Char>::BuildJsonArray(
670 const JsonContinuation& cont,
671 const SmallVector<Handle<Object>>& element_stack) {
672 size_t start = cont.index;
673 int length = static_cast<int>(element_stack.size() - start);
674
675 ElementsKind kind = PACKED_SMI_ELEMENTS;
676 for (size_t i = start; i < element_stack.size(); i++) {
677 Object value = *element_stack[i];
678 if (value.IsHeapObject()) {
679 if (HeapObject::cast(value).IsHeapNumber()) {
680 kind = PACKED_DOUBLE_ELEMENTS;
681 } else {
682 kind = PACKED_ELEMENTS;
683 break;
684 }
685 }
686 }
687
688 Handle<JSArray> array = factory()->NewJSArray(kind, length, length);
689 if (kind == PACKED_DOUBLE_ELEMENTS) {
690 DisallowGarbageCollection no_gc;
691 FixedDoubleArray elements = FixedDoubleArray::cast(array->elements());
692 for (int i = 0; i < length; i++) {
693 elements.set(i, element_stack[start + i]->Number());
694 }
695 } else {
696 DisallowGarbageCollection no_gc;
697 FixedArray elements = FixedArray::cast(array->elements());
698 WriteBarrierMode mode = kind == PACKED_SMI_ELEMENTS
699 ? SKIP_WRITE_BARRIER
700 : elements.GetWriteBarrierMode(no_gc);
701 for (int i = 0; i < length; i++) {
702 elements.set(i, *element_stack[start + i], mode);
703 }
704 }
705 return array;
706 }
707
708 // Parse any JSON value.
709 template <typename Char>
ParseJsonValue()710 MaybeHandle<Object> JsonParser<Char>::ParseJsonValue() {
711 std::vector<JsonContinuation> cont_stack;
712 SmallVector<JsonProperty> property_stack;
713 SmallVector<Handle<Object>> element_stack;
714
715 cont_stack.reserve(16);
716
717 JsonContinuation cont(isolate_, JsonContinuation::kReturn, 0);
718
719 Handle<Object> value;
720 while (true) {
721 // Produce a json value.
722 //
723 // Iterate until a value is produced. Starting but not immediately finishing
724 // objects and arrays will cause the loop to continue until a first member
725 // is completed.
726 while (true) {
727 SkipWhitespace();
728 // The switch is immediately followed by 'break' so we can use 'break' to
729 // break out of the loop, and 'continue' to continue the loop.
730 switch (peek()) {
731 case JsonToken::STRING:
732 Consume(JsonToken::STRING);
733 value = MakeString(ScanJsonString(false));
734 break;
735
736 case JsonToken::NUMBER:
737 value = ParseJsonNumber();
738 break;
739
740 case JsonToken::LBRACE: {
741 Consume(JsonToken::LBRACE);
742 if (Check(JsonToken::RBRACE)) {
743 // TODO(verwaest): Directly use the map instead.
744 value = factory()->NewJSObject(object_constructor_);
745 break;
746 }
747
748 // Start parsing an object with properties.
749 cont_stack.emplace_back(std::move(cont));
750 cont = JsonContinuation(isolate_, JsonContinuation::kObjectProperty,
751 property_stack.size());
752
753 // Parse the property key.
754 ExpectNext(JsonToken::STRING);
755 property_stack.emplace_back(ScanJsonPropertyKey(&cont));
756
757 ExpectNext(JsonToken::COLON);
758
759 // Continue to start producing the first property value.
760 continue;
761 }
762
763 case JsonToken::LBRACK:
764 Consume(JsonToken::LBRACK);
765 if (Check(JsonToken::RBRACK)) {
766 value = factory()->NewJSArray(0, PACKED_SMI_ELEMENTS);
767 break;
768 }
769
770 // Start parsing an array with elements.
771 cont_stack.emplace_back(std::move(cont));
772 cont = JsonContinuation(isolate_, JsonContinuation::kArrayElement,
773 element_stack.size());
774
775 // Continue to start producing the first array element.
776 continue;
777
778 case JsonToken::TRUE_LITERAL:
779 ScanLiteral("true");
780 value = factory()->true_value();
781 break;
782
783 case JsonToken::FALSE_LITERAL:
784 ScanLiteral("false");
785 value = factory()->false_value();
786 break;
787
788 case JsonToken::NULL_LITERAL:
789 ScanLiteral("null");
790 value = factory()->null_value();
791 break;
792
793 case JsonToken::COLON:
794 case JsonToken::COMMA:
795 case JsonToken::ILLEGAL:
796 case JsonToken::RBRACE:
797 case JsonToken::RBRACK:
798 case JsonToken::EOS:
799 ReportUnexpectedCharacter(CurrentCharacter());
800 // Pop the continuation stack to correctly tear down handle scopes.
801 while (!cont_stack.empty()) {
802 cont = std::move(cont_stack.back());
803 cont_stack.pop_back();
804 }
805 return MaybeHandle<Object>();
806
807 case JsonToken::WHITESPACE:
808 UNREACHABLE();
809 }
810
811 // Done producing a value, consume it.
812 break;
813 }
814
815 // Consume a produced json value.
816 //
817 // Iterate as long as values are produced (arrays or object literals are
818 // finished).
819 while (true) {
820 // The switch is immediately followed by 'break' so we can use 'break' to
821 // break out of the loop, and 'continue' to continue the loop.
822 switch (cont.type()) {
823 case JsonContinuation::kReturn:
824 return cont.scope.CloseAndEscape(value);
825
826 case JsonContinuation::kObjectProperty: {
827 // Store the previous property value into its property info.
828 property_stack.back().value = value;
829
830 if (V8_LIKELY(Check(JsonToken::COMMA))) {
831 // Parse the property key.
832 ExpectNext(JsonToken::STRING);
833
834 property_stack.emplace_back(ScanJsonPropertyKey(&cont));
835 ExpectNext(JsonToken::COLON);
836
837 // Break to start producing the subsequent property value.
838 break;
839 }
840
841 Handle<Map> feedback;
842 if (cont_stack.size() > 0 &&
843 cont_stack.back().type() == JsonContinuation::kArrayElement &&
844 cont_stack.back().index < element_stack.size() &&
845 element_stack.back()->IsJSObject()) {
846 Map maybe_feedback = JSObject::cast(*element_stack.back()).map();
847 // Don't consume feedback from objects with a map that's detached
848 // from the transition tree.
849 if (!maybe_feedback.IsDetached(isolate_)) {
850 feedback = handle(maybe_feedback, isolate_);
851 if (feedback->is_deprecated()) {
852 feedback = Map::Update(isolate_, feedback);
853 }
854 }
855 }
856 value = BuildJsonObject(cont, property_stack, feedback);
857 property_stack.resize_no_init(cont.index);
858 Expect(JsonToken::RBRACE);
859
860 // Return the object.
861 value = cont.scope.CloseAndEscape(value);
862 // Pop the continuation.
863 cont = std::move(cont_stack.back());
864 cont_stack.pop_back();
865 // Consume to produced object.
866 continue;
867 }
868
869 case JsonContinuation::kArrayElement: {
870 // Store the previous element on the stack.
871 element_stack.emplace_back(value);
872 // Break to start producing the subsequent element value.
873 if (V8_LIKELY(Check(JsonToken::COMMA))) break;
874
875 value = BuildJsonArray(cont, element_stack);
876 element_stack.resize_no_init(cont.index);
877 Expect(JsonToken::RBRACK);
878
879 // Return the array.
880 value = cont.scope.CloseAndEscape(value);
881 // Pop the continuation.
882 cont = std::move(cont_stack.back());
883 cont_stack.pop_back();
884 // Consume the produced array.
885 continue;
886 }
887 }
888
889 // Done consuming a value. Produce next value.
890 break;
891 }
892 }
893 }
894
895 template <typename Char>
AdvanceToNonDecimal()896 void JsonParser<Char>::AdvanceToNonDecimal() {
897 cursor_ =
898 std::find_if(cursor_, end_, [](Char c) { return !IsDecimalDigit(c); });
899 }
900
901 template <typename Char>
ParseJsonNumber()902 Handle<Object> JsonParser<Char>::ParseJsonNumber() {
903 double number;
904 int sign = 1;
905
906 {
907 const Char* start = cursor_;
908 DisallowGarbageCollection no_gc;
909
910 base::uc32 c = *cursor_;
911 if (c == '-') {
912 sign = -1;
913 c = NextCharacter();
914 }
915
916 if (c == '0') {
917 // Prefix zero is only allowed if it's the only digit before
918 // a decimal point or exponent.
919 c = NextCharacter();
920 if (base::IsInRange(c, 0,
921 static_cast<int32_t>(unibrow::Latin1::kMaxChar)) &&
922 IsNumberPart(character_json_scan_flags[c])) {
923 if (V8_UNLIKELY(IsDecimalDigit(c))) {
924 AllowGarbageCollection allow_before_exception;
925 ReportUnexpectedToken(JsonToken::NUMBER);
926 return handle(Smi::FromInt(0), isolate_);
927 }
928 } else if (sign > 0) {
929 return handle(Smi::FromInt(0), isolate_);
930 }
931 } else {
932 const Char* smi_start = cursor_;
933 AdvanceToNonDecimal();
934 if (V8_UNLIKELY(smi_start == cursor_)) {
935 AllowGarbageCollection allow_before_exception;
936 ReportUnexpectedCharacter(CurrentCharacter());
937 return handle(Smi::FromInt(0), isolate_);
938 }
939 c = CurrentCharacter();
940 STATIC_ASSERT(Smi::IsValid(-999999999));
941 STATIC_ASSERT(Smi::IsValid(999999999));
942 const int kMaxSmiLength = 9;
943 if ((cursor_ - smi_start) <= kMaxSmiLength &&
944 (!base::IsInRange(c, 0,
945 static_cast<int32_t>(unibrow::Latin1::kMaxChar)) ||
946 !IsNumberPart(character_json_scan_flags[c]))) {
947 // Smi.
948 int32_t i = 0;
949 for (; smi_start != cursor_; smi_start++) {
950 DCHECK(IsDecimalDigit(*smi_start));
951 i = (i * 10) + ((*smi_start) - '0');
952 }
953 // TODO(verwaest): Cache?
954 return handle(Smi::FromInt(i * sign), isolate_);
955 }
956 }
957
958 if (CurrentCharacter() == '.') {
959 c = NextCharacter();
960 if (!IsDecimalDigit(c)) {
961 AllowGarbageCollection allow_before_exception;
962 ReportUnexpectedCharacter(c);
963 return handle(Smi::FromInt(0), isolate_);
964 }
965 AdvanceToNonDecimal();
966 }
967
968 if (AsciiAlphaToLower(CurrentCharacter()) == 'e') {
969 c = NextCharacter();
970 if (c == '-' || c == '+') c = NextCharacter();
971 if (!IsDecimalDigit(c)) {
972 AllowGarbageCollection allow_before_exception;
973 ReportUnexpectedCharacter(c);
974 return handle(Smi::FromInt(0), isolate_);
975 }
976 AdvanceToNonDecimal();
977 }
978
979 base::Vector<const Char> chars(start, cursor_ - start);
980 number =
981 StringToDouble(chars,
982 NO_CONVERSION_FLAGS, // Hex, octal or trailing junk.
983 std::numeric_limits<double>::quiet_NaN());
984
985 DCHECK(!std::isnan(number));
986 }
987
988 return factory()->NewNumber(number);
989 }
990
991 namespace {
992
993 template <typename Char>
Matches(const base::Vector<const Char> & chars,Handle<String> string)994 bool Matches(const base::Vector<const Char>& chars, Handle<String> string) {
995 DCHECK(!string.is_null());
996 return string->IsEqualTo(chars);
997 }
998
999 } // namespace
1000
1001 template <typename Char>
1002 template <typename SinkSeqString>
DecodeString(const JsonString & string,Handle<SinkSeqString> intermediate,Handle<String> hint)1003 Handle<String> JsonParser<Char>::DecodeString(
1004 const JsonString& string, Handle<SinkSeqString> intermediate,
1005 Handle<String> hint) {
1006 using SinkChar = typename SinkSeqString::Char;
1007 {
1008 DisallowGarbageCollection no_gc;
1009 SinkChar* dest = intermediate->GetChars(no_gc);
1010 if (!string.has_escape()) {
1011 DCHECK(!string.internalize());
1012 CopyChars(dest, chars_ + string.start(), string.length());
1013 return intermediate;
1014 }
1015 DecodeString(dest, string.start(), string.length());
1016
1017 if (!string.internalize()) return intermediate;
1018
1019 base::Vector<const SinkChar> data(dest, string.length());
1020 if (!hint.is_null() && Matches(data, hint)) return hint;
1021 }
1022
1023 return factory()->InternalizeString(intermediate, 0, string.length());
1024 }
1025
1026 template <typename Char>
MakeString(const JsonString & string,Handle<String> hint)1027 Handle<String> JsonParser<Char>::MakeString(const JsonString& string,
1028 Handle<String> hint) {
1029 if (string.length() == 0) return factory()->empty_string();
1030
1031 if (string.internalize() && !string.has_escape()) {
1032 if (!hint.is_null()) {
1033 base::Vector<const Char> data(chars_ + string.start(), string.length());
1034 if (Matches(data, hint)) return hint;
1035 }
1036 if (chars_may_relocate_) {
1037 return factory()->InternalizeString(Handle<SeqString>::cast(source_),
1038 string.start(), string.length(),
1039 string.needs_conversion());
1040 }
1041 base::Vector<const Char> chars(chars_ + string.start(), string.length());
1042 return factory()->InternalizeString(chars, string.needs_conversion());
1043 }
1044
1045 if (sizeof(Char) == 1 ? V8_LIKELY(!string.needs_conversion())
1046 : string.needs_conversion()) {
1047 Handle<SeqOneByteString> intermediate =
1048 factory()->NewRawOneByteString(string.length()).ToHandleChecked();
1049 return DecodeString(string, intermediate, hint);
1050 }
1051
1052 Handle<SeqTwoByteString> intermediate =
1053 factory()->NewRawTwoByteString(string.length()).ToHandleChecked();
1054 return DecodeString(string, intermediate, hint);
1055 }
1056
1057 template <typename Char>
1058 template <typename SinkChar>
DecodeString(SinkChar * sink,int start,int length)1059 void JsonParser<Char>::DecodeString(SinkChar* sink, int start, int length) {
1060 SinkChar* sink_start = sink;
1061 const Char* cursor = chars_ + start;
1062 while (true) {
1063 const Char* end = cursor + length - (sink - sink_start);
1064 cursor = std::find_if(cursor, end, [&sink](Char c) {
1065 if (c == '\\') return true;
1066 *sink++ = c;
1067 return false;
1068 });
1069
1070 if (cursor == end) return;
1071
1072 cursor++;
1073
1074 switch (GetEscapeKind(character_json_scan_flags[*cursor])) {
1075 case EscapeKind::kSelf:
1076 *sink++ = *cursor;
1077 break;
1078
1079 case EscapeKind::kBackspace:
1080 *sink++ = '\x08';
1081 break;
1082
1083 case EscapeKind::kTab:
1084 *sink++ = '\x09';
1085 break;
1086
1087 case EscapeKind::kNewLine:
1088 *sink++ = '\x0A';
1089 break;
1090
1091 case EscapeKind::kFormFeed:
1092 *sink++ = '\x0C';
1093 break;
1094
1095 case EscapeKind::kCarriageReturn:
1096 *sink++ = '\x0D';
1097 break;
1098
1099 case EscapeKind::kUnicode: {
1100 base::uc32 value = 0;
1101 for (int i = 0; i < 4; i++) {
1102 value = value * 16 + base::HexValue(*++cursor);
1103 }
1104 if (value <=
1105 static_cast<base::uc32>(unibrow::Utf16::kMaxNonSurrogateCharCode)) {
1106 *sink++ = value;
1107 } else {
1108 *sink++ = unibrow::Utf16::LeadSurrogate(value);
1109 *sink++ = unibrow::Utf16::TrailSurrogate(value);
1110 }
1111 break;
1112 }
1113
1114 case EscapeKind::kIllegal:
1115 UNREACHABLE();
1116 }
1117 cursor++;
1118 }
1119 }
1120
1121 template <typename Char>
ScanJsonString(bool needs_internalization)1122 JsonString JsonParser<Char>::ScanJsonString(bool needs_internalization) {
1123 DisallowGarbageCollection no_gc;
1124 int start = position();
1125 int offset = start;
1126 bool has_escape = false;
1127 base::uc32 bits = 0;
1128
1129 while (true) {
1130 cursor_ = std::find_if(cursor_, end_, [&bits](Char c) {
1131 if (sizeof(Char) == 2 && V8_UNLIKELY(c > unibrow::Latin1::kMaxChar)) {
1132 bits |= c;
1133 return false;
1134 }
1135 return MayTerminateJsonString(character_json_scan_flags[c]);
1136 });
1137
1138 if (V8_UNLIKELY(is_at_end())) {
1139 AllowGarbageCollection allow_before_exception;
1140 ReportUnexpectedCharacter(kEndOfString);
1141 break;
1142 }
1143
1144 if (*cursor_ == '"') {
1145 int end = position();
1146 advance();
1147 int length = end - offset;
1148 bool convert = sizeof(Char) == 1 ? bits > unibrow::Latin1::kMaxChar
1149 : bits <= unibrow::Latin1::kMaxChar;
1150 return JsonString(start, length, convert, needs_internalization,
1151 has_escape);
1152 }
1153
1154 if (*cursor_ == '\\') {
1155 has_escape = true;
1156 base::uc32 c = NextCharacter();
1157 if (V8_UNLIKELY(!base::IsInRange(
1158 c, 0, static_cast<int32_t>(unibrow::Latin1::kMaxChar)))) {
1159 AllowGarbageCollection allow_before_exception;
1160 ReportUnexpectedCharacter(c);
1161 break;
1162 }
1163
1164 switch (GetEscapeKind(character_json_scan_flags[c])) {
1165 case EscapeKind::kSelf:
1166 case EscapeKind::kBackspace:
1167 case EscapeKind::kTab:
1168 case EscapeKind::kNewLine:
1169 case EscapeKind::kFormFeed:
1170 case EscapeKind::kCarriageReturn:
1171 offset += 1;
1172 break;
1173
1174 case EscapeKind::kUnicode: {
1175 base::uc32 value = ScanUnicodeCharacter();
1176 if (value == kInvalidUnicodeCharacter) {
1177 AllowGarbageCollection allow_before_exception;
1178 ReportUnexpectedCharacter(CurrentCharacter());
1179 return JsonString();
1180 }
1181 bits |= value;
1182 // \uXXXX results in either 1 or 2 Utf16 characters, depending on
1183 // whether the decoded value requires a surrogate pair.
1184 offset += 5 - (value > static_cast<base::uc32>(
1185 unibrow::Utf16::kMaxNonSurrogateCharCode));
1186 break;
1187 }
1188
1189 case EscapeKind::kIllegal:
1190 AllowGarbageCollection allow_before_exception;
1191 ReportUnexpectedCharacter(c);
1192 return JsonString();
1193 }
1194
1195 advance();
1196 continue;
1197 }
1198
1199 DCHECK_LT(*cursor_, 0x20);
1200 AllowGarbageCollection allow_before_exception;
1201 ReportUnexpectedCharacter(*cursor_);
1202 break;
1203 }
1204
1205 return JsonString();
1206 }
1207
1208 // Explicit instantiation.
1209 template class JsonParser<uint8_t>;
1210 template class JsonParser<uint16_t>;
1211
1212 } // namespace internal
1213 } // namespace v8
1214