[clangd] Assert on varint encoding

[kadircet]

Summary

5th byte of a varint can't be bigger than 0x0f, fix a test and add an
assertion.

[kadircet]

• Also fix the high byte

[sammccall]

clang-tools-extra/clangd/index/Serialization.cpp

90

I'm fine with an assert, but this still leaves us with the suspected UB in NDEBUG mode, which doesn't seem OK.
(As noted on D91258 I'm not sure this is actual UB under C++ rules)

The issue here is integral promotion rules say that uint_8 << anything uses *signed* arithmetic. And same for a bunch of the other operations.

I think the clearest thing to do is explicitly type B as uint32_t, so no expression it is in can ever be promoted to (signed) int.
(Unless int is bigger than 32 bits, in which case we've always got enough bits to shift into)

clang-tools-extra/clangd/unittests/SerializationTests.cpp

371

/shamecube

In my defense, I grew up on a 68k mac... little endian is weird

[kadircet]

• Increase width of B to prevent integer promotion.

[sammccall]

clang-tools-extra/clangd/index/Serialization.cpp

90

hmm, actually it's also invalid to have the More bit set on the last byte...

[kadircet]

• Only assert on the 5th byte, prior bytes can have any value.

clang-tools-extra/clangd/index/Serialization.cpp

public:
   uint32_t consumeVar() {
     constexpr static uint8_t More = 1 << 7;
     uint8_t B = consume8();
     if (LLVM_LIKELY(!(B & More)))
       return B;
     uint32_t Val = B & ~More;
     for (int Shift = 7; B & More && Shift < 32; Shift += 7) {
       B = consume8();
+      assert((B & ~More) < (1 << (32 - Shift)) && "Invalid varint encoding");
       Val |= (B & ~More) << Shift;
     }
     return Val;
   }
 
   llvm::StringRef consumeString(llvm::ArrayRef<llvm::StringRef> Strings) {
     auto StringIndex = consumeVar();
     if (LLVM_UNLIKELY(StringIndex >= Strings.size())) {

clang-tools-extra/clangd/unittests/SerializationTests.cpp

TEST(SerializationTest, NoCrashOnBadArraySize) {
   // We want to set DirectIncludes.length to a huge number.
   // The offset isn't trivial to find, so we use the file digest.
   std::string FileDigest = llvm::fromHex("EED8F5EAF25C453C");
   unsigned Pos = Srcs->Data.find_first_of(FileDigest);
   ASSERT_NE(Pos, StringRef::npos) << "Couldn't locate file digest";
   Pos += FileDigest.size();
 
   // Varints are little-endian base-128 numbers, where the top-bit of each byte
-  // indicates whether there are more. 8fffffff7f -> 0xffffffff.
+  // indicates whether there are more. 8fffffff0f -> 0xffffffff.
   std::string CorruptSrcs =
-      (Srcs->Data.take_front(Pos) + llvm::fromHex("8fffffff7f") +
+      (Srcs->Data.take_front(Pos) + llvm::fromHex("8fffffff0f") +
        "some_random_garbage")
           .str();
   Srcs->Data = CorruptSrcs;
 
   // Try to crash rather than hang on large allocation.
   ScopedMemoryLimit MemLimit(1000 * 1024 * 1024); // 1GB
 
   std::string CorruptFile = llvm::to_string(*Parsed);