Fix the block stack used by the bitstream cursor.

include/llvm/Bitcode/NaCl/NaClBitstreamReader.h

 //===- NaClBitstreamReader.h -----------------------------------*- C++ -*-===//
 //     Low-level bitstream reader interface
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This header defines the BitstreamReader class.  This class can be used to
 // read an arbitrary bitstream, regardless of its contents.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_BITCODE_NACL_NACLBITSTREAMREADER_H
 #define LLVM_BITCODE_NACL_NACLBITSTREAMREADER_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Bitcode/NaCl/NaClBitcodeHeader.h"
 #include "llvm/Bitcode/NaCl/NaClLLVMBitCodes.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/StreamingMemoryObject.h"
 #include <climits>
 #include <vector>
 
 namespace llvm {
 
 class Deserializer;
+class NaClBitstreamCursor;
 
 namespace naclbitc {
 
 /// Returns the Bit as a Byte:BitInByte string.
 std::string getBitAddress(uint64_t Bit);
 
 /// Severity levels for reporting errors.
 enum ErrorLevel {
   Warning,
   Error,
   Fatal
 };
 
 // Basic printing routine to generate the beginning of an error
 // message. BitPosition is the bit position the error was found.
 // Level is the severity of the error.
 raw_ostream &ErrorAt(raw_ostream &Out, ErrorLevel Level,
                      uint64_t BitPosition);
 
 } // End namespace naclbitc.
 
 /// This class is used to read from a NaCl bitcode wire format stream,
 /// maintaining information that is global to decoding the entire file.
 /// While a file is being read, multiple cursors can be independently
 /// advanced or skipped around within the file.  These are represented by
 /// 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;
 
   std::unique_ptr<MemoryObject> BitcodeBytes;
 
   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;
 
   // True if filler should be added to byte align records.
   bool AlignBitcodeRecords = false;
   NaClBitstreamReader(const NaClBitstreamReader&) = delete;
   void operator=(const NaClBitstreamReader&) = delete;
 
 
   void initFromHeader(NaClBitcodeHeader &Header) {
@@ skipping 18 matching lines @@
 
   /// Read stream from bytes, starting at the given initial address.
   /// Provides simple API for unit testing.
   NaClBitstreamReader(MemoryObject *Bytes, size_t InitialAddress)
       : BitcodeBytes(Bytes), InitialAddress(InitialAddress) {
   }
 
   // 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 {
     return InitialAddress;
   }
 
   //===--------------------------------------------------------------------===//
   // 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;
   }
 
   BlockInfo &getOrCreateBlockInfo(unsigned BlockID) {
     if (const BlockInfo *BI = getBlockInfo(BlockID))
       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();
   }
 };
 
 /// When advancing through a bitstream cursor, each advance can discover a few
 /// different kinds of entries:
 struct NaClBitstreamEntry {
   enum {
     Error,    // Malformed bitcode was found.
     EndBlock, // We've reached the end of the current block, (or the end of the
@@ skipping 103 matching lines @@
   /// follow the word size of the host machine for efficiency. We use word_t in
   /// places that are aware of this to make it perfectly explicit what is going
   /// on.
   typedef size_t word_t;
   word_t CurWord;
 
   /// This is the number of bits in CurWord that are valid. This
   /// 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;
   NaClBitstreamCursor &operator=(const NaClBitstreamCursor &) = delete;
 
 public:
   NaClBitstreamCursor() : ErrHandler(new ErrorHandler(*this)) {
     init(nullptr);
   }
 
   explicit NaClBitstreamCursor(NaClBitstreamReader &R)
       : ErrHandler(new ErrorHandler(*this)) { init(&R); }
 
   void init(NaClBitstreamReader *R) {
     freeState();
     BitStream = R;
     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
   // it is no longer needed.
   void setErrorHandler(std::unique_ptr<ErrorHandler> &NewHandler) {
     ErrHandler = std::move(NewHandler);
   }
 
   bool canSkipToPos(size_t pos) const {
     // pos can be skipped to if it is a valid address or one byte past the end.
     return pos == 0 || BitStream->getBitcodeBytes().isValidAddress(
         static_cast<uint64_t>(pos - 1));
   }
 
   bool AtEndOfStream() {
     if (BitsInCurWord != 0)
       return false;
     if (Size != 0)
       return Size == NextChar;
     fillCurWord();
     return BitsInCurWord == 0;
   }
 
   /// 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 {
     return NextChar*CHAR_BIT - BitsInCurWord;
   }
 
   NaClBitstreamReader *getBitStreamReader() {
     return BitStream;
   }
   const NaClBitstreamReader *getBitStreamReader() const {
@@ skipping 196 matching lines @@
       CurWord >>= BitsInCurWord-32;
       BitsInCurWord = 32;
       return;
     }
 
     BitsInCurWord = 0;
   }
 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:
   //    [ENTER_SUBBLOCK, blockid, newcodelen, <align4bytes>, blocklen]
 
   /// Having read the ENTER_SUBBLOCK code, read the BlockID for the block.
   unsigned ReadSubBlockID() {
     return ReadVBR(naclbitc::BlockIDWidth);
   }
 
@@ skipping 14 matching lines @@
 
     JumpToBit(SkipTo);
     return false;
   }
 
   /// Having read the ENTER_SUBBLOCK abbrevid, enter the block, and return true
   /// if the block has an error.
   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
   //===--------------------------------------------------------------------===//
 
 private:
   // Returns abbreviation encoding associated with Value.
   NaClBitCodeAbbrevOp::Encoding getEncoding(uint64_t Value);
 
   void skipAbbreviatedField(const NaClBitCodeAbbrevOp &Op);
 
@@ skipping 17 matching lines @@
   void reportInvalidAbbrevNumber(unsigned Index) const;
 
   // Reports that jumping to Bit is not valid.
   void reportInvalidJumpToBit(uint64_t Bit) const;
 
 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.
   void skipRecord(unsigned AbbrevID);
   
   unsigned readRecord(unsigned AbbrevID, SmallVectorImpl<uint64_t> &Vals);
 
   //===--------------------------------------------------------------------===//
   // Abbrev Processing
   //===--------------------------------------------------------------------===//
   // IsLocal indicates where the abbreviation occurs. If it is in the
   // BlockInfo block, IsLocal is false. In all other cases, IsLocal is
   // true.
   void ReadAbbrevRecord(bool IsLocal,
                         NaClAbbrevListener *Listener);
 
   // Skips over an abbreviation record. Duplicates code of ReadAbbrevRecord,
   // except that no abbreviation is built.
   void SkipAbbrevRecord();
   
   bool ReadBlockInfoBlock(NaClAbbrevListener *Listener);
 };
 
 } // End llvm namespace
 
 #endif