Bug 1586975 - Part 3: Remove NaiveHuffmanTable and use GenericHuffmanTable instead. r=Yoric
☠☠ backed out by 31f16b9b5863 ☠ ☠
authorTooru Fujisawa <arai_a@mac.com>
Mon, 21 Oct 2019 14:31:34 +0000
changeset 498378 7f0b3124697b07eff7ba29046f691c27a7009491
parent 498377 fbf2c90da04c85d8253ce146c0b229ef8b4a228f
child 498379 0750949021602aed8c36a833c258092522c448ee
push id36717
push usernbeleuzu@mozilla.com
push dateMon, 21 Oct 2019 21:51:55 +0000
treeherdermozilla-central@563f437f24b9 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersYoric
bugs1586975
milestone71.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1586975 - Part 3: Remove NaiveHuffmanTable and use GenericHuffmanTable instead. r=Yoric Differential Revision: https://phabricator.services.mozilla.com/D49562
js/src/frontend/BinASTTokenReaderContext.cpp
js/src/frontend/BinASTTokenReaderContext.h
--- a/js/src/frontend/BinASTTokenReaderContext.cpp
+++ b/js/src/frontend/BinASTTokenReaderContext.cpp
@@ -1917,75 +1917,36 @@ HuffmanLookupResult GenericHuffmanTable:
           -> HuffmanLookupResult { return implementation.lookup(key); },
       [key](const ThreeLookupsHuffmanTable& implementation)
           -> HuffmanLookupResult { return implementation.lookup(key); },
       [](const HuffmanTableUnreachable&) -> HuffmanLookupResult {
         MOZ_CRASH("GenericHuffmanTable is unitialized!");
       });
 }
 
-template <int N>
-JS::Result<Ok> NaiveHuffmanTable<N>::initWithSingleValue(
-    JSContext* cx, const BinASTSymbol& value) {
-  MOZ_ASSERT(values_.empty());  // Make sure that we're initializing.
-  if (MOZ_UNLIKELY(!values_.append(HuffmanEntry(0, 0, value)))) {
-    return cx->alreadyReportedError();
-  }
-  return Ok();
-}
-
-template <int N>
-JS::Result<Ok> NaiveHuffmanTable<N>::initStart(JSContext* cx,
-                                               size_t numberOfSymbols,
-                                               uint8_t) {
-  MOZ_ASSERT(values_.empty());  // Make sure that we're initializing.
-  if (MOZ_UNLIKELY(!values_.initCapacity(numberOfSymbols))) {
-    return cx->alreadyReportedError();
-  }
-  return Ok();
-}
-
-template <int N>
-JS::Result<Ok> NaiveHuffmanTable<N>::initComplete() {
-  MOZ_ASSERT(values_.length() <= N);
-  return Ok();
-}
-
-template <int N>
-JS::Result<Ok> NaiveHuffmanTable<N>::addSymbol(uint32_t bits, uint8_t bitLength,
-                                               const BinASTSymbol& value) {
-  MOZ_ASSERT(bitLength != 0,
-             "Adding a symbol with a bitLength of 0 doesn't make sense.");
-  MOZ_ASSERT(values_.empty() || values_.back().key().bitLength_ <= bitLength,
-             "Symbols must be ranked by increasing bits length");
-  MOZ_ASSERT_IF(bitLength != 32 /* >> 32 is UB */, bits >> bitLength == 0);
-  // Memory was reserved in `init()`.
-  MOZ_ALWAYS_TRUE(values_.emplaceBack(bits, bitLength, value));
-
-  return Ok();
-}
-
-template <int N>
-HuffmanLookupResult NaiveHuffmanTable<N>::lookup(HuffmanLookup key) const {
-  // This current implementation is O(length) and designed mostly for testing.
-  // Future versions will presumably adapt the underlying data structure to
-  // provide bounded-time lookup.
-  for (const auto& iter : values_) {
-    if (iter.key().bitLength_ > key.bitLength_) {
-      // We can't find the entry.
-      break;
-    }
-
-    const uint32_t keyBits = key.leadingBits(iter.key().bitLength_);
-    if (keyBits == iter.key().bits_) {
-      return HuffmanLookupResult::found(iter.key().bitLength_, &iter.value());
-    }
-  }
-
-  return HuffmanLookupResult::notFound();
+size_t GenericHuffmanTable::length() const {
+  return implementation_.match(
+      [](const SingleEntryHuffmanTable& implementation) -> size_t {
+        return implementation.length();
+      },
+      [](const TwoEntriesHuffmanTable& implementation) -> size_t {
+        return implementation.length();
+      },
+      [](const SingleLookupHuffmanTable& implementation) -> size_t {
+        return implementation.length();
+      },
+      [](const TwoLookupsHuffmanTable& implementation) -> size_t {
+        return implementation.length();
+      },
+      [](const ThreeLookupsHuffmanTable& implementation) -> size_t {
+        return implementation.length();
+      },
+      [](const HuffmanTableUnreachable& implementation) -> size_t {
+        MOZ_CRASH("GenericHuffmanTable is unitialized!");
+      });
 }
 
 SingleEntryHuffmanTable::Iterator::Iterator(const BinASTSymbol* position)
     : position_(position) {}
 
 void SingleEntryHuffmanTable::Iterator::operator++() {
   // There's only one entry, and `nullptr` means `end`.
   position_ = nullptr;
@@ -2046,18 +2007,17 @@ JS::Result<Ok> TwoEntriesHuffmanTable::i
 
 JS::Result<Ok> TwoEntriesHuffmanTable::initComplete() {
   MOZ_ASSERT(length_ == 2);
   return Ok();
 }
 
 JS::Result<Ok> TwoEntriesHuffmanTable::addSymbol(uint32_t bits,
                                                  uint8_t bitLength,
-                                                 const BinASTSymbol& value,
-                                                 reporter) {
+                                                 const BinASTSymbol& value) {
   MOZ_ASSERT(length_ < 2);
   // Symbols must be ranked by increasing bits length
   MOZ_ASSERT_IF(length_ == 0, bits == 0);
   MOZ_ASSERT_IF(length_ == 1, bits == 1);
 
   // FIXME: Throw soft error instead of assert.
   MOZ_ASSERT(bitLength == 1);
 
--- a/js/src/frontend/BinASTTokenReaderContext.h
+++ b/js/src/frontend/BinASTTokenReaderContext.h
@@ -255,73 +255,16 @@ const size_t HUFFMAN_TABLE_DEFAULT_INLIN
 
 // A flag that determines only whether a value is `null`.
 // Used for optional interface.
 enum class Nullable {
   Null,
   NonNull,
 };
 
-// An implementation of Huffman Tables as a vector, with `O(entries)`
-// lookup. Performance-wise, this implementation only makes sense for
-// very short tables.
-template <int N = HUFFMAN_TABLE_DEFAULT_INLINE_BUFFER_LENGTH>
-class NaiveHuffmanTable {
- public:
-  explicit NaiveHuffmanTable(JSContext* cx) : values_(cx) {}
-  NaiveHuffmanTable(NaiveHuffmanTable&& other) noexcept
-      : values_(std::move(other.values_)) {}
-
-  // Initialize a Huffman table containing a single value.
-  JS::Result<Ok> initWithSingleValue(JSContext* cx, const BinASTSymbol& value);
-
-  // Initialize a Huffman table containing `numberOfSymbols`.
-  // Symbols must be added with `addSymbol`.
-  // If you initialize with `initStart`, you MUST call `initComplete()`
-  // at the end of initialization.
-  JS::Result<Ok> initStart(JSContext* cx, size_t numberOfSymbols,
-                           uint8_t maxBitLength);
-
-  JS::Result<Ok> initComplete();
-
-  // Add a symbol to a value.
-  JS::Result<Ok> addSymbol(uint32_t bits, uint8_t bitLength,
-                           const BinASTSymbol& value);
-
-  NaiveHuffmanTable() = delete;
-  NaiveHuffmanTable(NaiveHuffmanTable&) = delete;
-
-  // Lookup a value in the table.
-  //
-  // The return of this method contains:
-  //
-  // - the resulting value (`nullptr` if the value is not in the table);
-  // - the number of bits in the entry associated to this value.
-  //
-  // Note that entries inside a single table are typically associated to
-  // distinct bit lengths. The caller is responsible for checking
-  // the result of this method and advancing the bitstream by
-  // `result.key().bitLength_` bits.
-  HuffmanLookupResult lookup(HuffmanLookup key) const;
-
-  // The number of values in the table.
-  size_t length() const { return values_.length(); }
-  const HuffmanEntry* begin() const { return values_.begin(); }
-  const HuffmanEntry* end() const { return values_.end(); }
-
- private:
-  // The entries in this Huffman table.
-  // Entries are always ranked by increasing bit_length, and within
-  // a bitlength by increasing value of `bits`. This representation
-  // is good for small tables, but in the future, we may adopt a
-  // representation more optimized for larger tables.
-  Vector<HuffmanEntry, N> values_;
-  friend class HuffmanPreludeReader;
-};
-
 // An implementation of Huffman Tables for single-entry table.
 class SingleEntryHuffmanTable {
  public:
   explicit SingleEntryHuffmanTable(const BinASTSymbol& value) : value_(value) {}
   SingleEntryHuffmanTable(SingleEntryHuffmanTable&& other) = default;
 
   SingleEntryHuffmanTable() = delete;
   SingleEntryHuffmanTable(SingleEntryHuffmanTable&) = delete;
@@ -956,38 +899,39 @@ struct HuffmanTableExplicitSymbolsU32 : 
       : GenericHuffmanTable(cx) {}
 };
 
 struct HuffmanTableIndexedSymbolsSum : GenericHuffmanTable {
   explicit HuffmanTableIndexedSymbolsSum(JSContext* cx)
       : GenericHuffmanTable(cx) {}
 };
 
-struct HuffmanTableIndexedSymbolsBool : NaiveHuffmanTable<2> {
+struct HuffmanTableIndexedSymbolsBool : GenericHuffmanTable {
   explicit HuffmanTableIndexedSymbolsBool(JSContext* cx)
-      : NaiveHuffmanTable(cx) {}
+      : GenericHuffmanTable(cx) {}
 };
 
 // A Huffman table that may only ever contain two values:
 // `BinASTKind::_Null` and another `BinASTKind`.
-struct HuffmanTableIndexedSymbolsMaybeInterface : NaiveHuffmanTable<2> {
+struct HuffmanTableIndexedSymbolsMaybeInterface : GenericHuffmanTable {
   explicit HuffmanTableIndexedSymbolsMaybeInterface(JSContext* cx)
-      : NaiveHuffmanTable(cx) {}
+      : GenericHuffmanTable(cx) {}
 
   // `true` if this table only contains values for `null`.
   bool isAlwaysNull() const {
-    MOZ_ASSERT(length() > 0);
+    MOZ_ASSERT(length() == 1 || length() == 2);
 
     // By definition, we have either 1 or 2 values.
     // By definition, if we have 2 values, one of them is not null.
-    if (length() != 1) {
+    if (length() == 2) {
       return false;
     }
+
     // Otherwise, check the single value.
-    return begin()->value().toKind() == BinASTKind::_Null;
+    return begin()->toKind() == BinASTKind::_Null;
   }
 };
 
 struct HuffmanTableIndexedSymbolsStringEnum : GenericHuffmanTable {
   explicit HuffmanTableIndexedSymbolsStringEnum(JSContext* cx)
       : GenericHuffmanTable(cx) {}
 };