Fix the block stack used by the bitstream cursor.

include/llvm/Bitcode/NaCl/NaClBitstreamReader.h

Index: include/llvm/Bitcode/NaCl/NaClBitstreamReader.h
diff --git a/include/llvm/Bitcode/NaCl/NaClBitstreamReader.h b/include/llvm/Bitcode/NaCl/NaClBitstreamReader.h
index 05cd91eb2aa92af2eb788d8c7289919604754b2e..9e63f3098576f553678467e2ba4f7b549cd3f8d9 100644
--- a/include/llvm/Bitcode/NaCl/NaClBitstreamReader.h
+++ b/include/llvm/Bitcode/NaCl/NaClBitstreamReader.h
@@ -27,6 +27,7 @@
 namespace llvm {
 
 class Deserializer;
+class NaClBitstreamCursor;
 
 namespace naclbitc {
 
@@ -55,12 +56,79 @@ raw_ostream &ErrorAt(raw_ostream &Out, ErrorLevel Level,
 /// the NaClBitstreamCursor class.
 class NaClBitstreamReader {
 public:
-  /// This contains information emitted to BLOCKINFO_BLOCK blocks. These
-  /// describe abbreviations that all blocks of the specified ID inherit.
-  struct BlockInfo {
+  // Models a raw list of abbreviations.
+  static constexpr size_t DefaultAbbrevListSize = 12;

[Jim Stichnoth, 2016/03/14 22:46:49]

same comment about constexpr

[Karl, 2016/03/15 20:29:41]

changed to "const".

+  using AbbrevListVector = SmallVector<NaClBitCodeAbbrev *,
+                                       DefaultAbbrevListSize>;
+
+  // Models and maintains a list of abbreviations. In particular, it maintains
+  // updating reference counts of abbreviation operators within the abbreviation
+  // list.
+  class AbbrevList {
+  public:
+    AbbrevList() = default;
+    explicit AbbrevList(const AbbrevList &NewAbbrevs) {
+      push_back(NewAbbrevs);
+    }
+    AbbrevList &operator=(const AbbrevList &Rhs) {
+      clear();
+      push_back(Rhs);
+      return *this;
+    }
+    void push_back(NaClBitCodeAbbrev *Abbv) {
+      Abbrevs.push_back(Abbv);

[Derek Schuff, 2016/03/15 17:47:04]

I don't really understand why you have to call addRef() in the other push_back
but not here?

[Karl, 2016/03/15 20:29:41]

This is part of the confusing usage of reference counts, because they don't use
a container class to maintain the reference counts. As a result, the user's must
be careful and follow the rules that when an abbreviation is first allocated,
the reference count is 1.

To try and clarify this, replaced this with methods appendUnique and
appendShare. appendUnique is used when the reference count has already been
incremented (i.e. like a unique_ptr, it owns the abbreviation and the method
takes ownership). appendShare is used when the reference count hasn't yet been
incremented (i.e. like a shared_ptr, where the caller continue to have
ownership, and the method takes ownership as well).

+    }
+    void push_back(const AbbrevList &NewAbbrevs) {

[Derek Schuff, 2016/03/15 17:47:04]

It seems a little weird that this is also called push_back, especially since
there is no analog in the std containers. Maybe it should be called extend, or
something that indicates its intent better? (but probably not insert, unless you
want to implement the same semantics as std::vector::insert but that's probably
overkill).

[Karl, 2016/03/15 20:29:41]

Changed to appendList, to better clarify.

+      for (NaClBitCodeAbbrev *Abbrev : NewAbbrevs.Abbrevs) {
+        Abbrev->addRef();
+        Abbrevs.push_back(Abbrev);
+      }
+    }
+    // Empties abbreviation list.
+    void clear() {
+      while(!Abbrevs.empty()) {
+        Abbrevs.back()->dropRef();
+        Abbrevs.pop_back();
+      }
+    }
+    const AbbrevListVector &getVector() const { return Abbrevs; }
+    ~AbbrevList() { clear(); }
+  private:
+    AbbrevListVector Abbrevs;
+    // Allow NaClBitstreamCursor to update, so that it can install abbreviations
+    // as they are read.
+    friend class NaClBitstreamCursor;
+  };
+
+  /// This contains information about abbreviations in blocks defined in the
+  /// BLOCKINFO_BLOCK block.  These describe global abbreviations that apply to
+  /// all succeeding blocks of the specified ID.
+  class BlockInfo {

[Derek Schuff, 2016/03/15 17:47:04]

does a BLOCKINFO_BLOCK have information other than abbreviations that isn't
modeled here? If so, maybe this class should be called BlockAbbrevInfo or
something like that?

[Karl, 2016/03/15 20:29:41]

For LLVM, there is more information. for PNaCl bitcode files, no other
information is stored in it. We never changed the name because:

1) We wanted to stay close to LLVM code for bitstream reading.
2) A number of other files refer to BlockInfo, and would have to be edited to
change the name.

+    BlockInfo &operator=(const BlockInfo&) = delete;
+  public:
+    BlockInfo() = default;
+    explicit BlockInfo(unsigned BlockID)
+        : BlockID(BlockID), Abbrevs() {}
+    BlockInfo(const BlockInfo&) = default;
+    unsigned getBlockID() const { return BlockID; }
+    void setBlockID(unsigned ID) { BlockID = ID; }
+    AbbrevList &getAbbrevs() { return Abbrevs; }
+    const AbbrevListVector &getVector() const {
+      return Abbrevs.getVector();
+    }
+    void push_back(NaClBitCodeAbbrev *Abbv) {
+      Abbrevs.push_back(Abbv);
+    }
+    void destroy() { Abbrevs.clear(); }

[Derek Schuff, 2016/03/15 17:47:04]

Is destroy() used anywhere?

[Karl, 2016/03/15 20:29:41]

Good catch. This clear has already been moved to AbbrevList, and doesn't have to
be done. Removing destroy() and simplifying the destructor.

+    ~BlockInfo() { destroy(); }
+  private:
     unsigned BlockID;
-    std::vector<NaClBitCodeAbbrev*> Abbrevs;
+    AbbrevList Abbrevs;
+    // Allow NaClBitstreamCursor to update, so that it can install

[Jim Stichnoth, 2016/03/14 22:46:49]

reflow comment (I think)

here and below

[Karl, 2016/03/15 20:29:41]

Done by removing need for friend class.

+    // abbreviations within a BlockInfo, as they are read.
+    friend NaClBitstreamCursor;
   };
+
 private:
   friend class NaClBitstreamCursor;
 
@@ -68,6 +136,9 @@ private:
 
   std::vector<BlockInfo> BlockInfoRecords;
 
+  // True if ReadBlockInfoBlock has been called.

[Derek Schuff, 2016/03/15 17:47:04]

Please fix the bug in English that the past and present tense of "read" are the
same.

+  bool HasReadBlockInfoBlock = false;
+
   /// \brief Holds the offset of the first byte after the header.
   size_t InitialAddress;
 
@@ -106,17 +177,7 @@ public:
   // Returns the memory object that is being read.
   MemoryObject &getBitcodeBytes() { return *BitcodeBytes; }
 
-  ~NaClBitstreamReader() {
-    // Free the BlockInfoRecords.
-    while (!BlockInfoRecords.empty()) {
-      BlockInfo &Info = BlockInfoRecords.back();
-      // Free blockinfo abbrev info.
-      for (unsigned i = 0, e = static_cast<unsigned>(Info.Abbrevs.size());
-           i != e; ++i)
-        Info.Abbrevs[i]->dropRef();
-      BlockInfoRecords.pop_back();
-    }
-  }
+  ~NaClBitstreamReader() {}
 
   /// \brief Returns the initial address (after the header) of the input stream.
   size_t getInitialAddress() const {
@@ -127,21 +188,17 @@ public:
   // Block Manipulation
   //===--------------------------------------------------------------------===//
 
-  /// Return true if we've already read and processed the block info block for
-  /// this Bitstream. We only process it for the first cursor that walks over
-  /// it.
-  bool hasBlockInfoRecords() const { return !BlockInfoRecords.empty(); }
-
   /// If there is block info for the specified ID, return it, otherwise return
   /// null.
   const BlockInfo *getBlockInfo(unsigned BlockID) const {
     // Common case, the most recent entry matches BlockID.
-    if (!BlockInfoRecords.empty() && BlockInfoRecords.back().BlockID == BlockID)
+    if (!BlockInfoRecords.empty() &&
+        BlockInfoRecords.back().getBlockID() == BlockID)
       return &BlockInfoRecords.back();
 
     for (unsigned i = 0, e = static_cast<unsigned>(BlockInfoRecords.size());
          i != e; ++i)
-      if (BlockInfoRecords[i].BlockID == BlockID)
+      if (BlockInfoRecords[i].getBlockID() == BlockID)
         return &BlockInfoRecords[i];
     return nullptr;
   }
@@ -151,8 +208,7 @@ public:
       return *const_cast<BlockInfo*>(BI);
 
     // Otherwise, add a new record.
-    BlockInfoRecords.push_back(BlockInfo());
-    BlockInfoRecords.back().BlockID = BlockID;
+    BlockInfoRecords.push_back(BlockInfo(BlockID));
     return BlockInfoRecords.back();
   }
 };
@@ -276,22 +332,58 @@ private:
   /// is always from [0...bits_of(word_t)-1] inclusive.
   unsigned BitsInCurWord;
 
-  /// This is the declared size of code values used for the current
-  /// block, in bits.
-  NaClBitcodeSelectorAbbrev CurCodeSize;
-
-  /// Abbrevs installed in this block.
-  std::vector<NaClBitCodeAbbrev*> CurAbbrevs;
-
-  struct Block {
-    NaClBitcodeSelectorAbbrev PrevCodeSize;
-    std::vector<NaClBitCodeAbbrev*> PrevAbbrevs;
-    Block() : PrevCodeSize() {}
-    explicit Block(const NaClBitcodeSelectorAbbrev& PCS)
-        : PrevCodeSize(PCS) {}
+  // Data specific to a block being scanned.
+  class Block {
+  public:
+    Block() = delete;
+    Block &operator=(const Block &Rhs) {
+      GlobalAbbrevs = Rhs.GlobalAbbrevs;
+      NumGlobalAbbrevs = Rhs.NumGlobalAbbrevs;
+      LocalAbbrevs = Rhs.LocalAbbrevs;
+      CodeAbbrev = Rhs.CodeAbbrev;
+      return *this;
+    }
+    Block(NaClBitstreamReader::BlockInfo *GlobalAbbrevs,
+          NaClBitcodeSelectorAbbrev& CodeAbbrev)
+        : GlobalAbbrevs(GlobalAbbrevs),
+          NumGlobalAbbrevs(GlobalAbbrevs->getVector().size()),
+          LocalAbbrevs(), CodeAbbrev(CodeAbbrev) {}
+    Block(NaClBitstreamReader::BlockInfo *GlobalAbbrevs)
+        : GlobalAbbrevs(GlobalAbbrevs),
+          NumGlobalAbbrevs(GlobalAbbrevs->getVector().size()),
+          LocalAbbrevs(), CodeAbbrev() {}
+    ~Block() = default;
+    const NaClBitstreamReader::AbbrevList &getGlobalAbbrevs() const {
+      return GlobalAbbrevs->getAbbrevs();
+    }
+    unsigned getNumGlobalAbbrevs() const { return NumGlobalAbbrevs; }
+    const NaClBitstreamReader::AbbrevList &getLocalAbbrevs() const {
+      return LocalAbbrevs;
+    }
+    const NaClBitcodeSelectorAbbrev &getCodeAbbrev() const {
+      return CodeAbbrev;
+    }
+    void setCodeAbbrev(NaClBitcodeSelectorAbbrev &Abbrev) {
+      CodeAbbrev = Abbrev;
+    }
+    void addNewLocalAbbrev(NaClBitCodeAbbrev *Abbv) {
+      LocalAbbrevs.push_back(Abbv);
+    }
+  private:
+    friend class NaClBitstreamCursor;
+    // The global abbreviations associated with this scope.
+    NaClBitstreamReader::BlockInfo *GlobalAbbrevs;
+    // Number of abbreviations when block was entered. Used to limit scope
+    // of CurBlockInfo, since any abbreviation added inside a BlockInfo block
+    // (within this block) must not effect global abbreviations.
+    unsigned NumGlobalAbbrevs;
+    NaClBitstreamReader::AbbrevList LocalAbbrevs;
+    // This is the declared size of code values used for the current block,
+    // in bits.
+    NaClBitcodeSelectorAbbrev CodeAbbrev;
   };
 
-  /// This tracks the codesize of parent blocks.
+  /// This tracks the Block-specific information for each nested block.
   SmallVector<Block, 8> BlockScope;
 
   NaClBitstreamCursor(const NaClBitstreamCursor &) = delete;
@@ -311,13 +403,20 @@ public:
     NextChar = (BitStream == nullptr) ? 0 : BitStream->getInitialAddress();
     Size = 0;
     BitsInCurWord = 0;
+    if (BitStream) {
+      BlockScope.push_back(
+          Block(&BitStream->getOrCreateBlockInfo(naclbitc::TOP_LEVEL_BLOCKID)));
+    }
   }
 
   ~NaClBitstreamCursor() {
     freeState();
   }
 
-  void freeState();
+  void freeState() {
+    while (!BlockScope.empty())
+      BlockScope.pop_back();
+  }
 
   // Replaces the current bitstream error handler with the new
   // handler. Takes ownership of the new handler and deletes it when
@@ -342,7 +441,9 @@ public:
   }
 
   /// Return the number of bits used to encode an abbrev #.
-  unsigned getAbbrevIDWidth() const { return CurCodeSize.NumBits; }
+  unsigned getAbbrevIDWidth() const {
+    return BlockScope.back().getCodeAbbrev().NumBits;
+  }
 
   /// Return the bit # of the bit we are reading.
   uint64_t GetCurrentBitNo() const {
@@ -559,9 +660,11 @@ private:
 public:
 
   unsigned ReadCode() {
-    return CurCodeSize.IsFixed
-        ? Read(CurCodeSize.NumBits)
-        : ReadVBR(CurCodeSize.NumBits);
+    const NaClBitcodeSelectorAbbrev &CodeAbbrev =
+        BlockScope.back().getCodeAbbrev();
+    return CodeAbbrev.IsFixed
+        ? Read(CodeAbbrev.NumBits)
+        : ReadVBR(CodeAbbrev.NumBits);
   }
 
   // Block header:
@@ -596,30 +699,18 @@ public:
   bool EnterSubBlock(unsigned BlockID, unsigned *NumWordsP = nullptr);
 
   bool ReadBlockEnd() {
-    if (BlockScope.empty()) return true;
+     if (BlockScope.empty()) return true;

[Derek Schuff, 2016/03/15 17:47:04]

extra space?

[Karl, 2016/03/15 20:29:41]

Done.

 
     // Block tail:
     //    [END_BLOCK, <align4bytes>]
     SkipToFourByteBoundary();
 
-    popBlockScope();
+    BlockScope.pop_back();
     return false;
   }
 
 private:
 
-  void popBlockScope() {
-    CurCodeSize = BlockScope.back().PrevCodeSize;
-
-    // Delete abbrevs from popped scope.
-    for (unsigned i = 0, e = static_cast<unsigned>(CurAbbrevs.size());
-         i != e; ++i)
-      CurAbbrevs[i]->dropRef();
-
-    BlockScope.back().PrevAbbrevs.swap(CurAbbrevs);
-    BlockScope.pop_back();
-  }
-
   //===--------------------------------------------------------------------===//
   // Record Processing
   //===--------------------------------------------------------------------===//
@@ -657,9 +748,16 @@ public:
   /// Return the abbreviation for the specified AbbrevId.
   const NaClBitCodeAbbrev *getAbbrev(unsigned AbbrevID) const {
     unsigned AbbrevNo = AbbrevID-naclbitc::FIRST_APPLICATION_ABBREV;
-    if (AbbrevNo >= CurAbbrevs.size())
+    const Block &CurBlock = BlockScope.back();
+    const unsigned NumGlobalAbbrevs = CurBlock.getNumGlobalAbbrevs();
+    if (AbbrevNo < NumGlobalAbbrevs)
+      return CurBlock.getGlobalAbbrevs().getVector()[AbbrevNo];
+    unsigned LocalAbbrevNo = AbbrevNo - NumGlobalAbbrevs;
+    NaClBitstreamReader::AbbrevListVector
+        LocalAbbrevs = CurBlock.getLocalAbbrevs().getVector();
+    if (LocalAbbrevNo >= LocalAbbrevs.size())
       reportInvalidAbbrevNumber(AbbrevID);
-    return CurAbbrevs[AbbrevNo];
+    return LocalAbbrevs[LocalAbbrevNo];
   }
 
   /// Read the current record and discard it.