Key.cpp (34942B)
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */ 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 "Key.h" 8 9 #include <stdint.h> // for UINT32_MAX, uintptr_t 10 11 #include <algorithm> 12 #include <cstdint> 13 14 #include "ReportInternalError.h" 15 #include "js/Array.h" // JS::NewArrayObject 16 #include "js/ArrayBuffer.h" // JS::{IsArrayBufferObject,NewArrayBuffer{,WithContents}} 17 #include "js/Date.h" 18 #include "js/MemoryFunctions.h" 19 #include "js/Object.h" // JS::GetBuiltinClass 20 #include "js/PropertyAndElement.h" // JS_DefineElement, JS_GetProperty, JS_GetPropertyById, JS_HasOwnProperty, JS_HasOwnPropertyById 21 #include "js/Value.h" 22 #include "js/experimental/TypedData.h" // JS::ArrayBufferOrView 23 #include "jsfriendapi.h" 24 #include "mozIStorageStatement.h" 25 #include "mozIStorageValueArray.h" 26 #include "mozilla/Casting.h" 27 #include "mozilla/EndianUtils.h" 28 #include "mozilla/FloatingPoint.h" 29 #include "mozilla/ResultExtensions.h" 30 #include "mozilla/dom/TypedArray.h" 31 #include "mozilla/dom/indexedDB/IDBResult.h" 32 #include "mozilla/dom/indexedDB/Key.h" 33 #include "mozilla/dom/quota/QuotaCommon.h" 34 #include "mozilla/dom/quota/ResultExtensions.h" 35 #include "mozilla/intl/Collator.h" 36 #include "nsJSUtils.h" 37 #include "nsTStringRepr.h" 38 #include "xpcpublic.h" 39 40 namespace mozilla::dom::indexedDB { 41 42 namespace { 43 // Implementation of the array branch of step 3 of 44 // https://w3c.github.io/IndexedDB/#convert-value-to-key 45 template <typename ArrayConversionPolicy> 46 IDBResult<Ok, IDBSpecialValue::Invalid> ConvertArrayValueToKey( 47 JSContext* const aCx, JS::Handle<JSObject*> aObject, 48 ArrayConversionPolicy&& aPolicy) { 49 // 1. Let `len` be ? ToLength( ? Get(`input`, "length")). 50 uint32_t len; 51 if (!JS::GetArrayLength(aCx, aObject, &len)) { 52 return Err(IDBException(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR)); 53 } 54 55 // 2. Add `input` to `seen`. 56 aPolicy.AddToSeenSet(aCx, aObject); 57 58 // 3. Let `keys` be a new empty list. 59 aPolicy.BeginSubkeyList(); 60 61 // 4. Let `index` be 0. 62 uint32_t index = 0; 63 64 // 5. While `index` is less than `len`: 65 while (index < len) { 66 JS::Rooted<JS::PropertyKey> indexId(aCx); 67 if (!JS_IndexToId(aCx, index, &indexId)) { 68 return Err(IDBException(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR)); 69 } 70 71 // 1. Let `hop` be ? HasOwnProperty(`input`, `index`). 72 bool hop; 73 if (!JS_HasOwnPropertyById(aCx, aObject, indexId, &hop)) { 74 return Err(IDBException(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR)); 75 } 76 77 // 2. If `hop` is false, return invalid. 78 if (!hop) { 79 return Err(IDBError(SpecialValues::Invalid)); 80 } 81 82 // 3. Let `entry` be ? Get(`input`, `index`). 83 JS::Rooted<JS::Value> entry(aCx); 84 if (!JS_GetPropertyById(aCx, aObject, indexId, &entry)) { 85 return Err(IDBException(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR)); 86 } 87 88 // 4. Let `key` be the result of running the steps to convert a value to a 89 // key with arguments `entry` and `seen`. 90 // 5. ReturnIfAbrupt(`key`). 91 // 6. If `key` is invalid abort these steps and return invalid. 92 // 7. Append `key` to `keys`. 93 auto result = aPolicy.ConvertSubkey(aCx, entry, index); 94 if (result.isErr()) { 95 return result; 96 } 97 98 // 8. Increase `index` by 1. 99 index += 1; 100 } 101 102 // 6. Return a new array key with value `keys`. 103 aPolicy.EndSubkeyList(); 104 return Ok(); 105 } 106 107 } // namespace 108 109 /* 110 Here's how we encode keys: 111 112 Basic strategy is the following 113 114 Numbers: 0x10 n n n n n n n n ("n"s are encoded 64bit float) 115 Dates: 0x20 n n n n n n n n ("n"s are encoded 64bit float) 116 Strings: 0x30 s s s ... 0 ("s"s are encoded unicode bytes) 117 Binaries: 0x40 s s s ... 0 ("s"s are encoded unicode bytes) 118 Arrays: 0x50 i i i ... 0 ("i"s are encoded array items) 119 120 121 When encoding floats, 64bit IEEE 754 are almost sortable, except that 122 positive sort lower than negative, and negative sort descending. So we use 123 the following encoding: 124 125 value < 0 ? 126 (-to64bitInt(value)) : 127 (to64bitInt(value) | 0x8000000000000000) 128 129 130 When encoding strings, we use variable-size encoding per the following table 131 132 Chars 0 - 7E are encoded as 0xxxxxxx with 1 added 133 Chars 7F - (3FFF+7F) are encoded as 10xxxxxx xxxxxxxx with 7F 134 subtracted 135 Chars (3FFF+80) - FFFF are encoded as 11xxxxxx xxxxxxxx xx000000 136 137 This ensures that the first byte is never encoded as 0, which means that the 138 string terminator (per basic-strategy table) sorts before any character. 139 The reason that (3FFF+80) - FFFF is encoded "shifted up" 6 bits is to maximize 140 the chance that the last character is 0. See below for why. 141 142 When encoding binaries, the algorithm is the same to how strings are encoded. 143 Since each octet in binary is in the range of [0-255], it'll take 1 to 2 144 encoded unicode bytes. 145 146 When encoding Arrays, we use an additional trick. Rather than adding a byte 147 containing the value 0x50 to indicate type, we instead add 0x50 to the next 148 byte. This is usually the byte containing the type of the first item in the 149 array. So simple examples are 150 151 ["foo"] 0x80 s s s 0 0 // 0x80 is 0x30 + 0x50 152 [1, 2] 0x60 n n n n n n n n 1 n n n n n n n n 0 // 0x60 is 0x10 + 0x50 153 154 Whe do this iteratively if the first item in the array is also an array 155 156 [["foo"]] 0xA0 s s s 0 0 0 157 158 However, to avoid overflow in the byte, we only do this 3 times. If the first 159 item in an array is an array, and that array also has an array as first item, 160 we simply write out the total value accumulated so far and then follow the 161 "normal" rules. 162 163 [[["foo"]]] 0xF0 0x30 s s s 0 0 0 0 164 165 There is another edge case that can happen though, which is that the array 166 doesn't have a first item to which we can add 0x50 to the type. Instead the 167 next byte would normally be the array terminator (per basic-strategy table) 168 so we simply add the 0x50 there. 169 170 [[]] 0xA0 0 // 0xA0 is 0x50 + 0x50 + 0 171 [] 0x50 // 0x50 is 0x50 + 0 172 [[], "foo"] 0xA0 0x30 s s s 0 0 // 0xA0 is 0x50 + 0x50 + 0 173 174 Note that the max-3-times rule kicks in before we get a chance to add to the 175 array terminator 176 177 [[[]]] 0xF0 0 0 0 // 0xF0 is 0x50 + 0x50 + 0x50 178 179 As a final optimization we do a post-encoding step which drops all 0s at the 180 end of the encoded buffer. 181 182 "foo" // 0x30 s s s 183 1 // 0x10 bf f0 184 ["a", "b"] // 0x80 s 0 0x30 s 185 [1, 2] // 0x60 bf f0 0 0 0 0 0 0 0x10 c0 186 [[]] // 0x80 187 */ 188 189 Result<Ok, nsresult> Key::SetFromString(const nsAString& aString) { 190 mBuffer.Truncate(); 191 auto result = EncodeString(aString, 0); 192 if (result.isOk()) { 193 TrimBuffer(); 194 } 195 return result; 196 } 197 198 // |aPos| should point to the type indicator. 199 // The returned length doesn't include the type indicator 200 // or the terminator. 201 // static 202 uint32_t Key::LengthOfEncodedBinary(const EncodedDataType* aPos, 203 const EncodedDataType* aEnd) { 204 MOZ_ASSERT(*aPos % Key::eMaxType == Key::eBinary, "Don't call me!"); 205 206 const auto* iter = aPos + 1; 207 for (; iter < aEnd && *iter != eTerminator; ++iter) { 208 if (*iter & 0x80) { 209 ++iter; 210 // XXX if iter == aEnd now, we got a bad enconding, should we report that 211 // also in non-debug builds? 212 MOZ_ASSERT(iter < aEnd); 213 } 214 } 215 216 return iter - aPos - 1; 217 } 218 219 Result<Key, nsresult> Key::ToLocaleAwareKey(const nsCString& aLocale) const { 220 Key res; 221 222 if (IsUnset()) { 223 return res; 224 } 225 226 if (IsFloat() || IsDate() || IsBinary()) { 227 res.mBuffer = mBuffer; 228 return res; 229 } 230 231 auto* it = BufferStart(); 232 auto* const end = BufferEnd(); 233 234 // First we do a pass and see if there are any strings in this key. We only 235 // want to copy/decode when necessary. 236 bool canShareBuffers = true; 237 while (it < end) { 238 const auto type = *it % eMaxType; 239 if (type == eTerminator) { 240 it++; 241 } else if (type == eFloat || type == eDate) { 242 it++; 243 it += std::min(sizeof(uint64_t), size_t(end - it)); 244 } else if (type == eBinary) { 245 // skip all binary data 246 const auto binaryLength = LengthOfEncodedBinary(it, end); 247 it++; 248 it += binaryLength; 249 } else { 250 // We have a string! 251 canShareBuffers = false; 252 break; 253 } 254 } 255 256 if (canShareBuffers) { 257 MOZ_ASSERT(it == end); 258 res.mBuffer = mBuffer; 259 return res; 260 } 261 262 if (!res.mBuffer.SetCapacity(mBuffer.Length(), fallible)) { 263 return Err(NS_ERROR_OUT_OF_MEMORY); 264 } 265 266 // A string was found, so we need to copy the data we've read so far 267 auto* const start = BufferStart(); 268 if (it > start) { 269 char* buffer; 270 MOZ_ALWAYS_TRUE(res.mBuffer.GetMutableData(&buffer, it - start)); 271 std::copy(start, it, buffer); 272 } 273 274 // Now continue decoding 275 while (it < end) { 276 char* buffer; 277 const size_t oldLen = res.mBuffer.Length(); 278 const auto type = *it % eMaxType; 279 280 // Note: Do not modify |it| before calling |updateBufferAndIter|; 281 // |byteCount| doesn't include the type indicator 282 const auto updateBufferAndIter = [&](size_t byteCount) -> bool { 283 if (!res.mBuffer.GetMutableData(&buffer, oldLen + 1 + byteCount)) { 284 return false; 285 } 286 buffer += oldLen; 287 288 // should also copy the type indicator at the begining 289 std::copy_n(it, byteCount + 1, buffer); 290 it += (byteCount + 1); 291 return true; 292 }; 293 294 if (type == eTerminator) { 295 // Copy array TypeID and terminator from raw key 296 if (!updateBufferAndIter(0)) { 297 return Err(NS_ERROR_OUT_OF_MEMORY); 298 } 299 } else if (type == eFloat || type == eDate) { 300 // Copy number from raw key 301 const size_t byteCount = std::min(sizeof(uint64_t), size_t(end - it - 1)); 302 303 if (!updateBufferAndIter(byteCount)) { 304 return Err(NS_ERROR_OUT_OF_MEMORY); 305 } 306 } else if (type == eBinary) { 307 // skip all binary data 308 const auto binaryLength = LengthOfEncodedBinary(it, end); 309 310 if (!updateBufferAndIter(binaryLength)) { 311 return Err(NS_ERROR_OUT_OF_MEMORY); 312 } 313 } else { 314 // Decode string and reencode 315 const uint8_t typeOffset = *it - eString; 316 MOZ_ASSERT((typeOffset % eArray == 0) && (typeOffset / eArray <= 2)); 317 318 auto str = DecodeString(it, end); 319 auto result = res.EncodeLocaleString(str, typeOffset, aLocale); 320 if (NS_WARN_IF(result.isErr())) { 321 return result.propagateErr(); 322 } 323 } 324 } 325 res.TrimBuffer(); 326 return res; 327 } 328 329 class MOZ_STACK_CLASS Key::ArrayValueEncoder final { 330 public: 331 ArrayValueEncoder(Key& aKey, const uint8_t aTypeOffset, 332 const uint16_t aRecursionDepth) 333 : mKey(aKey), 334 mTypeOffset(aTypeOffset), 335 mRecursionDepth(aRecursionDepth) {} 336 337 void AddToSeenSet(JSContext* const aCx, JS::Handle<JSObject*>) { 338 ++mRecursionDepth; 339 } 340 341 void BeginSubkeyList() { 342 mTypeOffset += Key::eMaxType; 343 if (mTypeOffset == eMaxType * kMaxArrayCollapse) { 344 mKey.mBuffer.Append(mTypeOffset); 345 mTypeOffset = 0; 346 } 347 MOZ_ASSERT(mTypeOffset % eMaxType == 0, 348 "Current type offset must indicate beginning of array"); 349 MOZ_ASSERT(mTypeOffset < eMaxType * kMaxArrayCollapse); 350 } 351 352 IDBResult<Ok, IDBSpecialValue::Invalid> ConvertSubkey( 353 JSContext* const aCx, JS::Handle<JS::Value> aEntry, 354 const uint32_t aIndex) { 355 auto result = 356 mKey.EncodeJSValInternal(aCx, aEntry, mTypeOffset, mRecursionDepth); 357 mTypeOffset = 0; 358 return result; 359 } 360 361 void EndSubkeyList() const { mKey.mBuffer.Append(eTerminator + mTypeOffset); } 362 363 private: 364 Key& mKey; 365 uint8_t mTypeOffset; 366 uint16_t mRecursionDepth; 367 }; 368 369 // Implements the following algorithm: 370 // https://w3c.github.io/IndexedDB/#convert-a-value-to-a-key 371 IDBResult<Ok, IDBSpecialValue::Invalid> Key::EncodeJSValInternal( 372 JSContext* const aCx, JS::Handle<JS::Value> aVal, uint8_t aTypeOffset, 373 const uint16_t aRecursionDepth) { 374 static_assert(eMaxType * kMaxArrayCollapse < 256, "Unable to encode jsvals."); 375 376 // 1. If `seen` was not given, let `seen` be a new empty set. 377 // 2. If `input` is in `seen` return invalid. 378 // Note: we replace this check with a simple recursion depth check. 379 if (NS_WARN_IF(aRecursionDepth == kMaxRecursionDepth)) { 380 return Err(IDBError(SpecialValues::Invalid)); 381 } 382 383 // 3. Jump to the appropriate step below: 384 // Note: some cases appear out of order to make the implementation more 385 // straightforward. This shouldn't affect observable behavior. 386 387 // If Type(`input`) is Number 388 if (aVal.isNumber()) { 389 const auto number = aVal.toNumber(); 390 391 // 1. If `input` is NaN then return invalid. 392 if (std::isnan(number)) { 393 return Err(IDBError(SpecialValues::Invalid)); 394 } 395 396 // 2. Otherwise, return a new key with type `number` and value `input`. 397 return EncodeNumber(number, eFloat + aTypeOffset); 398 } 399 400 // If Type(`input`) is String 401 if (aVal.isString()) { 402 // 1. Return a new key with type `string` and value `input`. 403 nsAutoJSString string; 404 if (!string.init(aCx, aVal)) { 405 IDB_REPORT_INTERNAL_ERR(); 406 return Err(IDBException(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR)); 407 } 408 return EncodeString(string, aTypeOffset); 409 } 410 411 if (aVal.isObject()) { 412 JS::Rooted<JSObject*> object(aCx, &aVal.toObject()); 413 414 js::ESClass builtinClass; 415 if (!JS::GetBuiltinClass(aCx, object, &builtinClass)) { 416 IDB_REPORT_INTERNAL_ERR(); 417 return Err(IDBException(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR)); 418 } 419 420 // If `input` is a Date (has a [[DateValue]] internal slot) 421 if (builtinClass == js::ESClass::Date) { 422 // 1. Let `ms` be the value of `input`’s [[DateValue]] internal slot. 423 double ms; 424 if (!js::DateGetMsecSinceEpoch(aCx, object, &ms)) { 425 IDB_REPORT_INTERNAL_ERR(); 426 return Err(IDBException(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR)); 427 } 428 429 // 2. If `ms` is NaN then return invalid. 430 if (std::isnan(ms)) { 431 return Err(IDBError(SpecialValues::Invalid)); 432 } 433 434 // 3. Otherwise, return a new key with type `date` and value `ms`. 435 return EncodeNumber(ms, eDate + aTypeOffset); 436 } 437 438 // If `input` is a buffer source type 439 if (JS::ArrayBufferOrView arrayBufferOrView = 440 JS::ArrayBufferOrView::fromObject(object)) { 441 return EncodeBinary(arrayBufferOrView, aTypeOffset); 442 } 443 444 // If IsArray(`input`) 445 if (builtinClass == js::ESClass::Array) { 446 return ConvertArrayValueToKey( 447 aCx, object, ArrayValueEncoder{*this, aTypeOffset, aRecursionDepth}); 448 } 449 } 450 451 // Otherwise 452 // Return invalid. 453 return Err(IDBError(SpecialValues::Invalid)); 454 } 455 456 // static 457 nsresult Key::DecodeJSValInternal(const EncodedDataType*& aPos, 458 const EncodedDataType* aEnd, JSContext* aCx, 459 uint8_t aTypeOffset, 460 JS::MutableHandle<JS::Value> aVal, 461 uint16_t aRecursionDepth) { 462 if (NS_WARN_IF(aRecursionDepth == kMaxRecursionDepth)) { 463 return NS_ERROR_DOM_INDEXEDDB_DATA_ERR; 464 } 465 466 if (*aPos - aTypeOffset >= eArray) { 467 JS::Rooted<JSObject*> array(aCx, JS::NewArrayObject(aCx, 0)); 468 if (!array) { 469 NS_WARNING("Failed to make array!"); 470 IDB_REPORT_INTERNAL_ERR(); 471 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR; 472 } 473 474 aTypeOffset += eMaxType; 475 476 if (aTypeOffset == eMaxType * kMaxArrayCollapse) { 477 ++aPos; 478 aTypeOffset = 0; 479 } 480 481 uint32_t index = 0; 482 JS::Rooted<JS::Value> val(aCx); 483 while (aPos < aEnd && *aPos - aTypeOffset != eTerminator) { 484 QM_TRY(MOZ_TO_RESULT(DecodeJSValInternal(aPos, aEnd, aCx, aTypeOffset, 485 &val, aRecursionDepth + 1))); 486 487 aTypeOffset = 0; 488 489 if (!JS_DefineElement(aCx, array, index++, val, JSPROP_ENUMERATE)) { 490 NS_WARNING("Failed to set array element!"); 491 IDB_REPORT_INTERNAL_ERR(); 492 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR; 493 } 494 } 495 496 NS_ASSERTION(aPos >= aEnd || (*aPos % eMaxType) == eTerminator, 497 "Should have found end-of-array marker"); 498 ++aPos; 499 500 aVal.setObject(*array); 501 } else if (*aPos - aTypeOffset == eString) { 502 auto key = DecodeString(aPos, aEnd); 503 if (!xpc::StringToJsval(aCx, key, aVal)) { 504 IDB_REPORT_INTERNAL_ERR(); 505 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR; 506 } 507 } else if (*aPos - aTypeOffset == eDate) { 508 double msec = static_cast<double>(DecodeNumber(aPos, aEnd)); 509 JS::ClippedTime time = JS::TimeClip(msec); 510 MOZ_ASSERT(msec == time.toDouble(), 511 "encoding from a Date object not containing an invalid date " 512 "means we should always have clipped values"); 513 JSObject* date = JS::NewDateObject(aCx, time); 514 if (!date) { 515 IDB_WARNING("Failed to make date!"); 516 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR; 517 } 518 519 aVal.setObject(*date); 520 } else if (*aPos - aTypeOffset == eFloat) { 521 aVal.setDouble(DecodeNumber(aPos, aEnd)); 522 } else if (*aPos - aTypeOffset == eBinary) { 523 JSObject* arrayBufferObject = DecodeBinary(aPos, aEnd, aCx); 524 if (!arrayBufferObject) { 525 IDB_REPORT_INTERNAL_ERR(); 526 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR; 527 } 528 529 aVal.setObject(*arrayBufferObject); 530 } else { 531 MOZ_ASSERT_UNREACHABLE("Unknown key type!"); 532 } 533 534 return NS_OK; 535 } 536 537 #define ONE_BYTE_LIMIT 0x7E 538 #define TWO_BYTE_LIMIT (0x3FFF + 0x7F) 539 540 #define ONE_BYTE_ADJUST 1 541 #define TWO_BYTE_ADJUST (-0x7F) 542 #define THREE_BYTE_SHIFT 6 543 544 IDBResult<Ok, IDBSpecialValue::Invalid> Key::EncodeJSVal( 545 JSContext* aCx, JS::Handle<JS::Value> aVal, uint8_t aTypeOffset) { 546 return EncodeJSValInternal(aCx, aVal, aTypeOffset, 0); 547 } 548 549 Result<Ok, nsresult> Key::EncodeString(const nsAString& aString, 550 uint8_t aTypeOffset) { 551 return EncodeString(Span{aString}, aTypeOffset); 552 } 553 554 template <typename T> 555 Result<Ok, nsresult> Key::EncodeString(const Span<const T> aInput, 556 uint8_t aTypeOffset) { 557 // aInput actually has no invalidatable pointers, but create a nogc token 558 // anyway just to satisfy the API. 559 JS::AutoCheckCannotGC nogc; 560 return EncodeAsString(aInput, std::move(nogc), eString + aTypeOffset); 561 } 562 563 // nsCString maximum length is limited by INT32_MAX. 564 // XXX: We probably want to enforce even shorter keys, though. 565 #define KEY_MAXIMUM_BUFFER_LENGTH \ 566 ::mozilla::detail::nsTStringLengthStorage<char>::kMax 567 568 void Key::ReserveAutoIncrementKey(bool aFirstOfArray) { 569 // Allocate memory for the new size 570 uint32_t oldLen = mBuffer.Length(); 571 char* buffer; 572 if (!mBuffer.GetMutableData(&buffer, oldLen + 1 + sizeof(double))) { 573 return; 574 } 575 576 // Remember the offset of the buffer to be updated later. 577 mAutoIncrementKeyOffsets.AppendElement(oldLen + 1); 578 579 // Fill the type. 580 buffer += oldLen; 581 *(buffer++) = aFirstOfArray ? (eMaxType + eFloat) : eFloat; 582 583 // Fill up with 0xFF to reserve the buffer in fixed size because the encoded 584 // string could be trimmed if ended with padding zeros. 585 mozilla::BigEndian::writeUint64(buffer, UINT64_MAX); 586 } 587 588 void Key::MaybeUpdateAutoIncrementKey(int64_t aKey) { 589 if (mAutoIncrementKeyOffsets.IsEmpty()) { 590 return; 591 } 592 593 for (uint32_t offset : mAutoIncrementKeyOffsets) { 594 char* buffer; 595 MOZ_ALWAYS_TRUE(mBuffer.GetMutableData(&buffer)); 596 buffer += offset; 597 WriteDoubleToUint64(buffer, double(aKey)); 598 } 599 600 TrimBuffer(); 601 } 602 603 void Key::WriteDoubleToUint64(char* aBuffer, double aValue) { 604 MOZ_ASSERT(aBuffer); 605 606 uint64_t bits = BitwiseCast<uint64_t>(aValue); 607 const uint64_t signbit = FloatingPoint<double>::kSignBit; 608 uint64_t number = bits & signbit ? (-bits) : (bits | signbit); 609 610 mozilla::BigEndian::writeUint64(aBuffer, number); 611 } 612 613 template <typename T> 614 Result<Ok, nsresult> Key::EncodeAsString(const Span<const T> aInput, 615 JS::AutoCheckCannotGC&& aNoGC, 616 uint8_t aType) { 617 // Please note that the input buffer can either be based on two-byte UTF-16 618 // values or on arbitrary single byte binary values. Only the first case 619 // needs to account for the TWO_BYTE_LIMIT of UTF-8. 620 // First we measure how long the encoded string will be. 621 622 // The 2 is for initial aType and trailing 0. We'll compensate for multi-byte 623 // chars below. 624 size_t size = 2; 625 626 // We construct a range over the raw pointers here because this loop is 627 // time-critical. 628 // XXX It might be good to encapsulate this in some function to make it less 629 // error-prone and more expressive. 630 const auto inputRange = mozilla::detail::IteratorRange( 631 aInput.Elements(), aInput.Elements() + aInput.Length()); 632 633 size_t payloadSize = aInput.Length(); 634 bool anyMultibyte = false; 635 for (const T val : inputRange) { 636 if (val > ONE_BYTE_LIMIT) { 637 anyMultibyte = true; 638 payloadSize += char16_t(val) > TWO_BYTE_LIMIT ? 2 : 1; 639 if (payloadSize > KEY_MAXIMUM_BUFFER_LENGTH) { 640 return Err(NS_ERROR_DOM_INDEXEDDB_KEY_ERR); 641 } 642 } 643 } 644 645 size += payloadSize; 646 647 // Now we allocate memory for the new size 648 size_t oldLen = mBuffer.Length(); 649 size += oldLen; 650 651 if (size > KEY_MAXIMUM_BUFFER_LENGTH) { 652 return Err(NS_ERROR_DOM_INDEXEDDB_KEY_ERR); 653 } 654 655 char* buffer; 656 if (!mBuffer.GetMutableData(&buffer, size)) { 657 aNoGC.reset(); // Done with aInput 658 IDB_REPORT_INTERNAL_ERR(); 659 return Err(NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR); 660 } 661 buffer += oldLen; 662 663 // Write type marker 664 *(buffer++) = aType; 665 666 // Encode string 667 if (anyMultibyte) { 668 for (const auto val : inputRange) { 669 if (val <= ONE_BYTE_LIMIT) { 670 *(buffer++) = val + ONE_BYTE_ADJUST; 671 } else if (char16_t(val) <= TWO_BYTE_LIMIT) { 672 char16_t c = char16_t(val) + TWO_BYTE_ADJUST + 0x8000; 673 *(buffer++) = (char)(c >> 8); 674 *(buffer++) = (char)(c & 0xFF); 675 } else { 676 uint32_t c = (uint32_t(val) << THREE_BYTE_SHIFT) | 0x00C00000; 677 *(buffer++) = (char)(c >> 16); 678 *(buffer++) = (char)(c >> 8); 679 *(buffer++) = (char)c; 680 } 681 } 682 } else { 683 // Optimization for the case where there are no multibyte characters. 684 // This is ca. 13 resp. 5.8 times faster than the non-optimized version in 685 // an -O2 build: https://quick-bench.com/q/v1oBpLGifs-3w_pkZG8alVSWVAw, for 686 // the T==uint8_t resp. T==char16_t cases (for the char16_t case, copying 687 // and then adjusting could even be slightly faster, but then we would need 688 // another case distinction here) 689 size_t inputLen = std::distance(inputRange.cbegin(), inputRange.cend()); 690 MOZ_ASSERT(inputLen == payloadSize); 691 std::transform(inputRange.cbegin(), inputRange.cend(), buffer, 692 [](auto value) { return value + ONE_BYTE_ADJUST; }); 693 buffer += inputLen; 694 } 695 696 aNoGC.reset(); // Done with aInput 697 698 // Write end marker 699 *(buffer++) = eTerminator; 700 701 NS_ASSERTION(buffer == mBuffer.EndReading(), "Wrote wrong number of bytes"); 702 703 return Ok(); 704 } 705 706 Result<Ok, nsresult> Key::EncodeLocaleString(const nsAString& aString, 707 uint8_t aTypeOffset, 708 const nsCString& aLocale) { 709 const int length = aString.Length(); 710 if (length == 0) { 711 return Ok(); 712 } 713 714 auto collResult = intl::Collator::TryCreate(aLocale.get()); 715 if (collResult.isErr()) { 716 return Err(NS_ERROR_FAILURE); 717 } 718 auto collator = collResult.unwrap(); 719 MOZ_ASSERT(collator); 720 721 AutoTArray<uint8_t, 128> keyBuffer; 722 MOZ_TRY(collator->GetSortKey(Span{aString}, keyBuffer) 723 .mapErr([](intl::ICUError icuError) { 724 return icuError == intl::ICUError::OutOfMemory 725 ? NS_ERROR_OUT_OF_MEMORY 726 : NS_ERROR_FAILURE; 727 })); 728 729 size_t sortKeyLength = keyBuffer.Length(); 730 return EncodeString(Span{keyBuffer}.AsConst().First(sortKeyLength), 731 aTypeOffset); 732 } 733 734 // static 735 nsresult Key::DecodeJSVal(const EncodedDataType*& aPos, 736 const EncodedDataType* aEnd, JSContext* aCx, 737 JS::MutableHandle<JS::Value> aVal) { 738 // If DecodeJSValInternal errors out and leaves a pending exception, then 739 // clear the exception on aCx here and return an error nsresult, which will 740 // be turned into a new JS exception that reflects that this operation failed 741 // (rather than using the initial exception, which was probably an 742 // information-less OOM). 743 QM_TRY(MOZ_TO_RESULT(DecodeJSValInternal(aPos, aEnd, aCx, 0, aVal, 0)), 744 QM_PROPAGATE, [aCx](const auto&) { JS_ClearPendingException(aCx); }); 745 746 return NS_OK; 747 } 748 749 // static 750 template <typename T> 751 uint32_t Key::CalcDecodedStringySize( 752 const EncodedDataType* const aBegin, const EncodedDataType* const aEnd, 753 const EncodedDataType** aOutEncodedSectionEnd) { 754 static_assert(sizeof(T) <= 2, 755 "Only implemented for 1 and 2 byte decoded types"); 756 uint32_t decodedSize = 0; 757 auto* iter = aBegin; 758 for (; iter < aEnd && *iter != eTerminator; ++iter) { 759 if (*iter & 0x80) { 760 iter += (sizeof(T) > 1 && (*iter & 0x40)) ? 2 : 1; 761 } 762 ++decodedSize; 763 } 764 *aOutEncodedSectionEnd = std::min(aEnd, iter); 765 return decodedSize; 766 } 767 768 // static 769 template <typename T> 770 void Key::DecodeAsStringy(const EncodedDataType* const aEncodedSectionBegin, 771 const EncodedDataType* const aEncodedSectionEnd, 772 const uint32_t aDecodedLength, T* const aOut) { 773 static_assert(sizeof(T) <= 2, 774 "Only implemented for 1 and 2 byte decoded types"); 775 T* decodedPos = aOut; 776 for (const EncodedDataType* iter = aEncodedSectionBegin; 777 iter < aEncodedSectionEnd;) { 778 if (!(*iter & 0x80)) { 779 *decodedPos = *(iter++) - ONE_BYTE_ADJUST; 780 } else if (sizeof(T) == 1 || !(*iter & 0x40)) { 781 auto c = static_cast<uint16_t>(*(iter++)) << 8; 782 if (iter < aEncodedSectionEnd) { 783 c |= *(iter++); 784 } 785 *decodedPos = static_cast<T>(c - TWO_BYTE_ADJUST - 0x8000); 786 } else if (sizeof(T) > 1) { 787 auto c = static_cast<uint32_t>(*(iter++)) << (16 - THREE_BYTE_SHIFT); 788 if (iter < aEncodedSectionEnd) { 789 c |= static_cast<uint32_t>(*(iter++)) << (8 - THREE_BYTE_SHIFT); 790 } 791 if (iter < aEncodedSectionEnd) { 792 c |= *(iter++) >> THREE_BYTE_SHIFT; 793 } 794 *decodedPos = static_cast<T>(c); 795 } 796 ++decodedPos; 797 } 798 799 MOZ_ASSERT(static_cast<uint32_t>(decodedPos - aOut) == aDecodedLength, 800 "Should have written the whole decoded area"); 801 } 802 803 // static 804 template <Key::EncodedDataType TypeMask, typename T, typename AcquireBuffer, 805 typename AcquireEmpty> 806 void Key::DecodeStringy(const EncodedDataType*& aPos, 807 const EncodedDataType* aEnd, 808 const AcquireBuffer& acquireBuffer, 809 const AcquireEmpty& acquireEmpty) { 810 NS_ASSERTION(*aPos % eMaxType == TypeMask, "Don't call me!"); 811 812 // First measure how big the decoded stringy data will be. 813 const EncodedDataType* const encodedSectionBegin = aPos + 1; 814 const EncodedDataType* encodedSectionEnd; 815 // decodedLength does not include the terminating 0 (in case of a string) 816 const uint32_t decodedLength = 817 CalcDecodedStringySize<T>(encodedSectionBegin, aEnd, &encodedSectionEnd); 818 aPos = encodedSectionEnd + 1; 819 820 if (!decodedLength) { 821 acquireEmpty(); 822 return; 823 } 824 825 T* out; 826 if (!acquireBuffer(&out, decodedLength)) { 827 return; 828 } 829 830 DecodeAsStringy(encodedSectionBegin, encodedSectionEnd, decodedLength, out); 831 } 832 833 // static 834 nsAutoString Key::DecodeString(const EncodedDataType*& aPos, 835 const EncodedDataType* const aEnd) { 836 nsAutoString res; 837 DecodeStringy<eString, char16_t>( 838 aPos, aEnd, 839 [&res](char16_t** out, uint32_t decodedLength) { 840 return 0 != res.GetMutableData(out, decodedLength); 841 }, 842 [] {}); 843 return res; 844 } 845 846 Result<Ok, nsresult> Key::EncodeNumber(double aFloat, uint8_t aType) { 847 // Allocate memory for the new size 848 size_t oldLen = mBuffer.Length(); 849 size_t newLen = oldLen + 1 + sizeof(double); 850 if (newLen > KEY_MAXIMUM_BUFFER_LENGTH) { 851 return Err(NS_ERROR_DOM_INDEXEDDB_KEY_ERR); 852 } 853 854 char* buffer; 855 if (!mBuffer.GetMutableData(&buffer, newLen)) { 856 return Err(NS_ERROR_DOM_INDEXEDDB_KEY_ERR); 857 } 858 buffer += oldLen; 859 860 *(buffer++) = aType; 861 862 WriteDoubleToUint64(buffer, aFloat); 863 864 return Ok(); 865 } 866 867 // static 868 double Key::DecodeNumber(const EncodedDataType*& aPos, 869 const EncodedDataType* aEnd) { 870 NS_ASSERTION(*aPos % eMaxType == eFloat || *aPos % eMaxType == eDate, 871 "Don't call me!"); 872 873 ++aPos; 874 875 uint64_t number = 0; 876 memcpy(&number, aPos, std::min<size_t>(sizeof(number), aEnd - aPos)); 877 number = mozilla::NativeEndian::swapFromBigEndian(number); 878 879 aPos += sizeof(number); 880 881 // Note: The subtraction from 0 below is necessary to fix 882 // MSVC build warning C4146 (negating an unsigned value). 883 const uint64_t signbit = FloatingPoint<double>::kSignBit; 884 uint64_t bits = number & signbit ? (number & ~signbit) : (0 - number); 885 886 return BitwiseCast<double>(bits); 887 } 888 889 template <typename F> 890 static Result<Ok, nsresult> ProcessArrayBufferOrView( 891 const JS::ArrayBufferOrView& aArrayBufferOrView, F&& aCallback) { 892 JSObject* object = aArrayBufferOrView.asObjectUnbarriered(); 893 894 mozilla::dom::ArrayBufferView arrayBufferView; 895 if (arrayBufferView.Init(object)) { 896 return arrayBufferView.ProcessData</* AllowLargeTypedArrays */ true>( 897 std::forward<F>(aCallback)); 898 } 899 900 mozilla::dom::ArrayBuffer arrayBuffer; 901 if (arrayBuffer.Init(object)) { 902 return arrayBuffer.ProcessData</* AllowLargeTypedArrays */ true>( 903 std::forward<F>(aCallback)); 904 } 905 906 MOZ_CRASH("ArrayBufferOrView must be ArrayBuffer or ArrayBufferView!"); 907 } 908 909 Result<Ok, nsresult> Key::EncodeBinary( 910 const JS::ArrayBufferOrView& aArrayBufferOrView, uint8_t aTypeOffset) { 911 // We can't exactly mimic the steps for "getting a copy of the bytes held by 912 // the buffer source" because for safety reasons, we have to use higher level 913 // APIs for accessing array buffer or array buffer view data. 914 // Also, EncodeAsString needs to encode the data anyway (making a copy), so 915 // doing a plain extra copy first would be inefficient. 916 917 // https://webidl.spec.whatwg.org/#dfn-get-buffer-source-copy 918 // 7. If IsDetachedBuffer(jsArrayBuffer) is true, then return the empty 919 // byte sequence. 920 // 921 // Note: As the web platform tests assume, and as has been discussed at 922 // https://github.com/w3c/IndexedDB/issues/417 - we are better off by 923 // throwing a DataCloneError. The spec language is about to be revised. 924 if (aArrayBufferOrView.isDetached()) { 925 return Err(NS_ERROR_DOM_INDEXEDDB_DATA_ERR); 926 } 927 928 // 1. Let aData be the result of getting the bytes held by the buffer source 929 // input. 930 // 2. Return a new key with type binary and value aData. 931 // 932 // Note: The wording of the steps has been adjusted to reflect implementation 933 // specifics which are described above. 934 return ProcessArrayBufferOrView( 935 aArrayBufferOrView, 936 [aTypeOffset, this]( 937 const Span<uint8_t>& aData, 938 JS::AutoCheckCannotGC&& aNoGC) -> Result<Ok, nsresult> { 939 if (aData.LengthBytes() > INT32_MAX) { 940 return Err(NS_ERROR_DOM_INDEXEDDB_DATA_ERR); 941 } 942 943 return EncodeAsString((const Span<const uint8_t>)aData, 944 std::move(aNoGC), eBinary + aTypeOffset); 945 }); 946 } 947 948 // static 949 JSObject* Key::DecodeBinary(const EncodedDataType*& aPos, 950 const EncodedDataType* aEnd, JSContext* aCx) { 951 JS::Rooted<JSObject*> rv(aCx); 952 DecodeStringy<eBinary, uint8_t>( 953 aPos, aEnd, 954 [&rv, aCx](uint8_t** out, uint32_t decodedSize) { 955 UniquePtr<void, JS::FreePolicy> ptr{JS_malloc(aCx, decodedSize)}; 956 if (NS_WARN_IF(!ptr)) { 957 *out = nullptr; 958 rv = nullptr; 959 return false; 960 } 961 962 *out = static_cast<uint8_t*>(ptr.get()); 963 rv = JS::NewArrayBufferWithContents(aCx, decodedSize, std::move(ptr)); 964 if (NS_WARN_IF(!rv)) { 965 *out = nullptr; 966 return false; 967 } 968 return true; 969 }, 970 [&rv, aCx] { rv = JS::NewArrayBuffer(aCx, 0); }); 971 return rv; 972 } 973 974 nsresult Key::BindToStatement(mozIStorageStatement* aStatement, 975 const nsACString& aParamName) const { 976 nsresult rv; 977 if (IsUnset()) { 978 rv = aStatement->BindNullByName(aParamName); 979 } else { 980 rv = aStatement->BindBlobByName( 981 aParamName, reinterpret_cast<const uint8_t*>(mBuffer.get()), 982 mBuffer.Length()); 983 } 984 985 return NS_SUCCEEDED(rv) ? NS_OK : NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR; 986 } 987 988 nsresult Key::SetFromStatement(mozIStorageStatement* aStatement, 989 uint32_t aIndex) { 990 return SetFromSource(aStatement, aIndex); 991 } 992 993 nsresult Key::SetFromValueArray(mozIStorageValueArray* aValues, 994 uint32_t aIndex) { 995 return SetFromSource(aValues, aIndex); 996 } 997 998 IDBResult<Ok, IDBSpecialValue::Invalid> Key::SetFromJSVal( 999 JSContext* aCx, JS::Handle<JS::Value> aVal) { 1000 mBuffer.Truncate(); 1001 1002 if (aVal.isNull() || aVal.isUndefined()) { 1003 Unset(); 1004 return Ok(); 1005 } 1006 1007 auto result = EncodeJSVal(aCx, aVal, 0); 1008 if (result.isErr()) { 1009 Unset(); 1010 return result; 1011 } 1012 TrimBuffer(); 1013 return Ok(); 1014 } 1015 1016 nsresult Key::ToJSVal(JSContext* aCx, JS::MutableHandle<JS::Value> aVal) const { 1017 if (IsUnset()) { 1018 aVal.setUndefined(); 1019 return NS_OK; 1020 } 1021 1022 const EncodedDataType* pos = BufferStart(); 1023 nsresult rv = DecodeJSVal(pos, BufferEnd(), aCx, aVal); 1024 if (NS_WARN_IF(NS_FAILED(rv))) { 1025 return rv; 1026 } 1027 1028 MOZ_ASSERT(pos >= BufferEnd()); 1029 1030 return NS_OK; 1031 } 1032 1033 nsresult Key::ToJSVal(JSContext* aCx, JS::Heap<JS::Value>& aVal) const { 1034 JS::Rooted<JS::Value> value(aCx); 1035 nsresult rv = ToJSVal(aCx, &value); 1036 if (NS_SUCCEEDED(rv)) { 1037 aVal = value; 1038 } 1039 return rv; 1040 } 1041 1042 IDBResult<Ok, IDBSpecialValue::Invalid> Key::AppendItem( 1043 JSContext* aCx, bool aFirstOfArray, JS::Handle<JS::Value> aVal) { 1044 auto result = EncodeJSVal(aCx, aVal, aFirstOfArray ? eMaxType : 0); 1045 if (result.isErr()) { 1046 Unset(); 1047 } 1048 return result; 1049 } 1050 1051 template <typename T> 1052 nsresult Key::SetFromSource(T* aSource, uint32_t aIndex) { 1053 const uint8_t* data; 1054 uint32_t dataLength = 0; 1055 1056 nsresult rv = aSource->GetSharedBlob(aIndex, &dataLength, &data); 1057 if (NS_WARN_IF(NS_FAILED(rv))) { 1058 return NS_ERROR_DOM_INDEXEDDB_UNKNOWN_ERR; 1059 } 1060 1061 mBuffer.Assign(reinterpret_cast<const char*>(data), dataLength); 1062 1063 return NS_OK; 1064 } 1065 1066 } // namespace mozilla::dom::indexedDB