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