1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #include "vm/RecordType.h"
8
9 #include "mozilla/Assertions.h"
10
11 #include "jsapi.h"
12
13 #include "gc/Nursery.h"
14 #include "gc/Rooting.h"
15 #include "js/Array.h"
16 #include "js/TypeDecls.h"
17 #include "js/Value.h"
18 #include "util/StringBuffer.h"
19 #include "vm/ArrayObject.h"
20 #include "vm/EqualityOperations.h"
21 #include "vm/JSAtom.h"
22 #include "vm/JSContext.h"
23 #include "vm/JSObject.h"
24 #include "vm/NativeObject.h"
25 #include "vm/ObjectFlags.h"
26 #include "vm/PropertyInfo.h"
27 #include "vm/PropMap.h"
28 #include "vm/StringType.h"
29 #include "vm/ToSource.h"
30 #include "vm/TupleType.h"
31
32 #include "vm/JSAtom-inl.h"
33 #include "vm/JSObject-inl.h"
34 #include "vm/NativeObject-inl.h"
35
36 using namespace js;
37
38 static bool RecordConstructor(JSContext* cx, unsigned argc, Value* vp);
39
40 const JSClass RecordType::class_ = {"record",
41 JSCLASS_HAS_RESERVED_SLOTS(SLOT_COUNT),
42 JS_NULL_CLASS_OPS, &RecordType::classSpec_};
43
44 const ClassSpec RecordType::classSpec_ = {
45 GenericCreateConstructor<RecordConstructor, 1, gc::AllocKind::FUNCTION>,
46 nullptr,
47 nullptr,
48 nullptr,
49 nullptr,
50 nullptr};
51
getInitialShape(JSContext * cx)52 Shape* RecordType::getInitialShape(JSContext* cx) {
53 return SharedShape::getInitialShape(cx, &RecordType::class_, cx->realm(),
54 TaggedProto(nullptr), SLOT_COUNT);
55 }
56
createUninitialized(JSContext * cx,uint32_t initialLength)57 RecordType* RecordType::createUninitialized(JSContext* cx,
58 uint32_t initialLength) {
59 RootedShape shape(cx, getInitialShape(cx));
60 if (!shape) {
61 return nullptr;
62 }
63
64 JSObject* obj = js::AllocateObject(cx, NewObjectGCKind(), initialLength,
65 gc::DefaultHeap, &RecordType::class_);
66 if (!obj) {
67 return nullptr;
68 }
69 obj->initShape(shape);
70
71 Rooted<RecordType*> rec(cx, static_cast<RecordType*>(obj));
72 rec->setEmptyElements();
73 rec->initEmptyDynamicSlots();
74 rec->initFixedSlots(SLOT_COUNT);
75
76 RootedArrayObject sortedKeys(cx,
77 NewDenseFullyAllocatedArray(cx, initialLength));
78 if (!sortedKeys) {
79 return nullptr;
80 }
81
82 rec->initFixedSlot(INITIALIZED_LENGTH_SLOT, PrivateUint32Value(0));
83 rec->initFixedSlot(SORTED_KEYS_SLOT, ObjectValue(*sortedKeys));
84 rec->initFixedSlot(IS_ATOMIZED_SLOT, BooleanValue(false));
85
86 return rec;
87 }
88
initializeNextProperty(JSContext * cx,HandleId key,HandleValue value)89 bool RecordType::initializeNextProperty(JSContext* cx, HandleId key,
90 HandleValue value) {
91 if (key.isSymbol()) {
92 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
93 JSMSG_RECORD_NO_SYMBOL_KEY);
94 return false;
95 }
96
97 if (!value.isPrimitive()) {
98 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
99 JSMSG_RECORD_TUPLE_NO_OBJECT);
100 return false;
101 }
102
103 mozilla::Maybe<PropertyInfo> prop = lookupPure(key);
104
105 if (prop.isSome()) {
106 MOZ_ASSERT(prop.value().hasSlot());
107 setSlot(prop.value().slot(), value);
108 return true;
109 }
110
111 constexpr PropertyFlags propFlags = {PropertyFlag::Enumerable};
112 Rooted<NativeObject*> target(cx, this);
113 uint32_t slot;
114 if (!NativeObject::addProperty(cx, target, key, propFlags, &slot)) {
115 return false;
116 }
117 initSlot(slot, value);
118
119 // Add the key to the SORTED_KEYS internal slot
120
121 JSAtom* atomKey = key.isString() ? AtomizeString(cx, key.toString())
122 : Int32ToAtom(cx, key.toInt());
123 if (!atomKey) {
124 return false;
125 }
126
127 uint32_t initializedLength =
128 getFixedSlot(INITIALIZED_LENGTH_SLOT).toPrivateUint32();
129 ArrayObject* sortedKeys =
130 &getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>();
131 MOZ_ASSERT(initializedLength == sortedKeys->getDenseInitializedLength());
132
133 if (!sortedKeys->ensureElements(cx, initializedLength + 1)) {
134 return false;
135 }
136 sortedKeys->setDenseInitializedLength(initializedLength + 1);
137 sortedKeys->initDenseElement(initializedLength, StringValue(atomKey));
138
139 setFixedSlot(INITIALIZED_LENGTH_SLOT,
140 PrivateUint32Value(initializedLength + 1));
141
142 return true;
143 }
144
finishInitialization(JSContext * cx)145 bool RecordType::finishInitialization(JSContext* cx) {
146 RootedNativeObject obj(cx, this);
147 if (!JSObject::setFlag(cx, obj, ObjectFlag::NotExtensible)) {
148 return false;
149 }
150 if (!ObjectElements::FreezeOrSeal(cx, obj, IntegrityLevel::Frozen)) {
151 return false;
152 }
153
154 uint32_t length = getFixedSlot(INITIALIZED_LENGTH_SLOT).toPrivateUint32();
155 ArrayObject& sortedKeys =
156 getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>();
157 MOZ_ASSERT(length == sortedKeys.getDenseInitializedLength());
158
159 Rooted<JSLinearString*> tmpKey(cx);
160
161 // Sort the keys. This is insertion sort - O(n^2) - but it's ok for now
162 // becase records are probably not too big anyway.
163 for (uint32_t i = 1, j; i < length; i++) {
164 #define KEY(index) sortedKeys.getDenseElement(index)
165 #define KEY_S(index) &KEY(index).toString()->asLinear()
166
167 MOZ_ASSERT(KEY(i).isString());
168 MOZ_ASSERT(KEY(i).toString()->isLinear());
169
170 tmpKey = KEY_S(i);
171
172 for (j = i; j > 0 && CompareStrings(KEY_S(j - 1), tmpKey) > 0; j--) {
173 sortedKeys.setDenseElement(j, KEY(j - 1));
174 }
175
176 sortedKeys.setDenseElement(j, StringValue(tmpKey));
177
178 #undef KEY
179 #undef KEY_S
180 }
181
182 // We preallocate 1 element for each object spread. If spreads end up
183 // introducing zero elements, we can then shrink the sortedKeys array.
184 sortedKeys.setDenseInitializedLength(length);
185 sortedKeys.setLength(length);
186 sortedKeys.setNonWritableLength(cx);
187
188 MOZ_ASSERT(sortedKeys.length() == length);
189
190 return true;
191 }
192
getOwnProperty(JSContext * cx,HandleId id,MutableHandleValue vp) const193 bool RecordType::getOwnProperty(JSContext* cx, HandleId id,
194 MutableHandleValue vp) const {
195 if (id.isSymbol()) {
196 return false;
197 }
198
199 uint32_t index;
200
201 // Check for a native dense element.
202 if (id.isInt()) {
203 index = id.toInt();
204 if (containsDenseElement(index)) {
205 vp.set(getDenseElement(index));
206 return true;
207 }
208 }
209
210 // Check for a native property.
211 if (PropMap* map = shape()->lookup(cx, id, &index)) {
212 PropertyInfo info = map->getPropertyInfo(index);
213 MOZ_ASSERT(info.isDataProperty());
214 vp.set(getSlot(info.slot()));
215 return true;
216 }
217
218 return false;
219 }
220
hash(const RecordType::FieldHasher & hasher)221 js::HashNumber RecordType::hash(const RecordType::FieldHasher& hasher) {
222 MOZ_ASSERT(isAtomized());
223
224 ArrayObject& sortedKeys =
225 getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>();
226 uint32_t length = sortedKeys.length();
227
228 js::HashNumber h = mozilla::HashGeneric(length);
229 for (uint32_t i = 0; i < length; i++) {
230 JSAtom& key = sortedKeys.getDenseElement(i).toString()->asAtom();
231
232 mozilla::Maybe<PropertyInfo> prop = lookupPure(AtomToId(&key));
233 MOZ_ASSERT(prop.isSome() && prop.value().hasSlot());
234
235 h = mozilla::AddToHash(h, key.hash(), hasher(getSlot(prop.value().slot())));
236 }
237
238 return h;
239 }
240
ensureAtomized(JSContext * cx)241 bool RecordType::ensureAtomized(JSContext* cx) {
242 if (isAtomized()) {
243 return true;
244 }
245
246 ArrayObject& sortedKeys =
247 getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>();
248 uint32_t length = sortedKeys.length();
249
250 RootedValue child(cx);
251 bool updated;
252 for (uint32_t i = 0; i < length; i++) {
253 JSAtom& key = sortedKeys.getDenseElement(i).toString()->asAtom();
254
255 mozilla::Maybe<PropertyInfo> prop = lookupPure(AtomToId(&key));
256 MOZ_ASSERT(prop.isSome() && prop.value().hasSlot());
257 uint32_t slot = prop.value().slot();
258
259 child.set(getSlot(slot));
260
261 if (!EnsureAtomized(cx, &child, &updated)) {
262 return false;
263 }
264 if (updated) {
265 setSlot(slot, child);
266 }
267 }
268
269 setFixedSlot(IS_ATOMIZED_SLOT, BooleanValue(true));
270
271 return true;
272 }
273
sameValueZero(JSContext * cx,RecordType * lhs,RecordType * rhs,bool * equal)274 bool RecordType::sameValueZero(JSContext* cx, RecordType* lhs, RecordType* rhs,
275 bool* equal) {
276 return sameValueWith<SameValueZero>(cx, lhs, rhs, equal);
277 }
278
sameValue(JSContext * cx,RecordType * lhs,RecordType * rhs,bool * equal)279 bool RecordType::sameValue(JSContext* cx, RecordType* lhs, RecordType* rhs,
280 bool* equal) {
281 return sameValueWith<SameValue>(cx, lhs, rhs, equal);
282 }
283
sameValueZero(RecordType * lhs,RecordType * rhs)284 bool RecordType::sameValueZero(RecordType* lhs, RecordType* rhs) {
285 MOZ_ASSERT(lhs->isAtomized());
286 MOZ_ASSERT(rhs->isAtomized());
287
288 if (lhs == rhs) {
289 return true;
290 }
291
292 ArrayObject& lhsSortedKeys =
293 lhs->getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>();
294 ArrayObject& rhsSortedKeys =
295 rhs->getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>();
296
297 uint32_t length = lhsSortedKeys.length();
298
299 if (rhsSortedKeys.length() != length) {
300 return false;
301 }
302
303 Value v1, v2;
304
305 for (uint32_t index = 0; index < length; index++) {
306 JSAtom* key = &lhsSortedKeys.getDenseElement(index).toString()->asAtom();
307 if (!EqualStrings(
308 key, &rhsSortedKeys.getDenseElement(index).toString()->asAtom())) {
309 return false;
310 }
311
312 {
313 mozilla::Maybe<PropertyInfo> lhsProp = lhs->lookupPure(AtomToId(key));
314 MOZ_ASSERT(lhsProp.isSome() && lhsProp.value().hasSlot());
315 v1 = lhs->getSlot(lhsProp.value().slot());
316 }
317
318 {
319 mozilla::Maybe<PropertyInfo> rhsProp = rhs->lookupPure(AtomToId(key));
320 MOZ_ASSERT(rhsProp.isSome() && rhsProp.value().hasSlot());
321 v2 = rhs->getSlot(rhsProp.value().slot());
322 }
323
324 if (!js::SameValueZeroLinear(v1, v2)) {
325 return false;
326 }
327 }
328
329 return true;
330 }
331
332 template <bool Comparator(JSContext*, HandleValue, HandleValue, bool*)>
sameValueWith(JSContext * cx,RecordType * lhs,RecordType * rhs,bool * equal)333 bool RecordType::sameValueWith(JSContext* cx, RecordType* lhs, RecordType* rhs,
334 bool* equal) {
335 if (lhs == rhs) {
336 *equal = true;
337 return true;
338 }
339
340 uint32_t length =
341 lhs->getFixedSlot(INITIALIZED_LENGTH_SLOT).toPrivateUint32();
342
343 if (rhs->getFixedSlot(INITIALIZED_LENGTH_SLOT).toPrivateUint32() != length) {
344 *equal = false;
345 return true;
346 }
347
348 *equal = true;
349
350 RootedString k1(cx), k2(cx);
351 RootedId id(cx);
352 RootedValue v1(cx), v2(cx);
353
354 RootedArrayObject sortedKeysLHS(
355 cx, &lhs->getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>());
356 RootedArrayObject sortedKeysRHS(
357 cx, &rhs->getFixedSlot(SORTED_KEYS_SLOT).toObject().as<ArrayObject>());
358
359 for (uint32_t index = 0; index < length; index++) {
360 k1.set(sortedKeysLHS->getDenseElement(index).toString());
361 k2.set(sortedKeysRHS->getDenseElement(index).toString());
362
363 if (!EqualStrings(cx, k1, k2, equal)) {
364 return false;
365 }
366 if (!*equal) {
367 return true;
368 }
369
370 if (!JS_StringToId(cx, k1, &id)) {
371 return false;
372 }
373
374 // We already know that this is an own property of both records, so both
375 // calls must return true.
376 MOZ_ALWAYS_TRUE(lhs->getOwnProperty(cx, id, &v1));
377 MOZ_ALWAYS_TRUE(rhs->getOwnProperty(cx, id, &v2));
378
379 if (!Comparator(cx, v1, v2, equal)) {
380 return false;
381 }
382 if (!*equal) {
383 return true;
384 }
385 }
386
387 return true;
388 }
389
390 // Record and Record proposal section 9.2.1
RecordConstructor(JSContext * cx,unsigned argc,Value * vp)391 static bool RecordConstructor(JSContext* cx, unsigned argc, Value* vp) {
392 CallArgs args = CallArgsFromVp(argc, vp);
393
394 // Step 1.
395 if (args.isConstructing()) {
396 JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
397 JSMSG_NOT_CONSTRUCTOR, "Record");
398 return false;
399 }
400 // Step 2.
401 RootedObject obj(cx, ToObject(cx, args.get(0)));
402 if (!obj) {
403 return false;
404 }
405
406 // Step 3.
407 RootedIdVector keys(cx);
408 if (!GetPropertyKeys(cx, obj, JSITER_OWNONLY, &keys)) {
409 return false;
410 }
411
412 size_t len = keys.length();
413
414 Rooted<RecordType*> rec(cx, RecordType::createUninitialized(cx, len));
415
416 if (!rec) {
417 return false;
418 }
419
420 RootedId propKey(cx);
421 RootedValue propValue(cx);
422 for (size_t i = 0; i < len; i++) {
423 propKey.set(keys[i]);
424 MOZ_ASSERT(!propKey.isSymbol(), "symbols are filtered out at step 3");
425
426 // Step 4.c.ii.1.
427 if (MOZ_UNLIKELY(!GetProperty(cx, obj, obj, propKey, &propValue))) {
428 return false;
429 }
430
431 if (MOZ_UNLIKELY(!rec->initializeNextProperty(cx, propKey, propValue))) {
432 return false;
433 }
434 }
435
436 if (MOZ_UNLIKELY(!rec->finishInitialization(cx))) {
437 return false;
438 }
439
440 args.rval().setExtendedPrimitive(*rec);
441 return true;
442 }
443
RecordToSource(JSContext * cx,RecordType * rec)444 JSString* js::RecordToSource(JSContext* cx, RecordType* rec) {
445 JSStringBuilder sb(cx);
446
447 if (!sb.append("#{")) {
448 return nullptr;
449 }
450
451 ArrayObject& sortedKeys = rec->getFixedSlot(RecordType::SORTED_KEYS_SLOT)
452 .toObject()
453 .as<ArrayObject>();
454
455 uint32_t length = sortedKeys.length();
456
457 Rooted<RecordType*> rootedRec(cx, rec);
458 RootedValue value(cx);
459 RootedString keyStr(cx);
460 RootedId key(cx);
461 JSString* str;
462 for (uint32_t index = 0; index < length; index++) {
463 value.set(sortedKeys.getDenseElement(index));
464 MOZ_ASSERT(value.isString());
465
466 str = ValueToSource(cx, value);
467 if (!str) {
468 return nullptr;
469 }
470 if (!sb.append(str)) {
471 return nullptr;
472 }
473
474 if (!sb.append(": ")) {
475 return nullptr;
476 }
477
478 keyStr.set(value.toString());
479 if (!JS_StringToId(cx, keyStr, &key)) {
480 return nullptr;
481 }
482
483 MOZ_ALWAYS_TRUE(rootedRec->getOwnProperty(cx, key, &value));
484
485 str = ValueToSource(cx, value);
486 if (!str) {
487 return nullptr;
488 }
489 if (!sb.append(str)) {
490 return nullptr;
491 }
492
493 if (index + 1 != length) {
494 if (!sb.append(", ")) {
495 return nullptr;
496 }
497 }
498 }
499
500 /* Finalize the buffer. */
501 if (!sb.append('}')) {
502 return nullptr;
503 }
504
505 return sb.finishString();
506 }
507