[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

94

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

94

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

 #include "support/Trace.h"
 #include "clang/Tooling/CompilationDatabase.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/raw_ostream.h"
+#include <cstdint>
 #include <vector>
 
 namespace clang {
 namespace clangd {
 namespace {
 
 // IO PRIMITIVES
 // We use little-endian 32 bit ints, sometimes with variable-length encoding.
llvm::StringRef consume(int N) {
     }
     llvm::StringRef Ret(Begin, N);
     Begin += N;
     return Ret;
   }
 
   uint32_t consumeVar() {
     constexpr static uint8_t More = 1 << 7;
-    uint8_t B = consume8();
+
+    // Use a 32 bit unsigned here to prevent promotion to signed int (unless int
+    // is wider than 32 bits).
+    uint32_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();
+      // 5th byte of a varint can only have lowest 4 bits set.
+      assert((Shift != 28 || B == (B & 0x0f)) && "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. ffffffff0f -> 0xffffffff.
   std::string CorruptSrcs =
-      (Srcs->Data.take_front(Pos) + llvm::fromHex("8fffffff7f") +
+      (Srcs->Data.take_front(Pos) + llvm::fromHex("ffffffff0f") +
        "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);