dom/indexedDB/Key.cpp

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