[clangd][clang-tidy] Remove uses of `std::vector<bool>`

[jansvoboda11]

Summary

LLVM Programmer’s Manual strongly discourages the use of std::vector<bool> and suggests llvm::BitVector as a possible replacement.

This patch does just that for clangd and clang-tidy.

[jansvoboda11]

Split patches

[dexonsmith]

LGTM.

clang-tools-extra/clang-tidy/ClangTidyDiagnosticConsumer.cpp

 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/FileManager.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Frontend/DiagnosticRenderer.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Tooling/Core/Diagnostic.h"
 #include "clang/Tooling/Core/Replacement.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/Regex.h"
 #include <tuple>
 #include <utility>
 #include <vector>
for (const auto &FileAndReplace : *ErrorFixes[I].second) {
         } else {
           Events.emplace_back(Begin, End, Event::ET_Begin, I, Sizes[I]);
           Events.emplace_back(Begin, End, Event::ET_End, I, Sizes[I]);
         }
       }
     }
   }
 
-  std::vector<bool> Apply(ErrorFixes.size(), true);
+  llvm::BitVector Apply(ErrorFixes.size(), true);
   for (auto &FileAndEvents : FileEvents) {
     std::vector<Event> &Events = FileAndEvents.second;
     // Sweep.
     llvm::sort(Events);
     int OpenIntervals = 0;
     for (const auto &Event : Events) {
       switch (Event.Type) {
       case Event::ET_Begin:

clang-tools-extra/clang-tidy/readability/FunctionSizeCheck.cpp

 //===-- FunctionSizeCheck.cpp - clang-tidy --------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "FunctionSizeCheck.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "llvm/ADT/BitVector.h"
 
 using namespace clang::ast_matchers;
 
 namespace clang {
 namespace tidy {
 namespace readability {
 namespace {
 
struct FunctionInfo {
     unsigned Lines = 0;
     unsigned Statements = 0;
     unsigned Branches = 0;
     unsigned NestingThreshold = 0;
     unsigned Variables = 0;
     std::vector<SourceLocation> NestingThresholders;
   };
   FunctionInfo Info;
-  std::vector<bool> TrackedParent;
+  llvm::BitVector TrackedParent;
   unsigned StructNesting = 0;
   unsigned CurrentNestingLevel = 0;
 };
 
 } // namespace
 
 FunctionSizeCheck::FunctionSizeCheck(StringRef Name, ClangTidyContext *Context)
     : ClangTidyCheck(Name, Context),

clang-tools-extra/clangd/Selection.cpp

 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/AST/TypeLoc.h"
 #include "clang/Basic/OperatorKinds.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Tooling/Syntax/Tokens.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <string>
 
 namespace clang {
const syntax::Token *SelFirst =
           return SM.getFileOffset(Tok.endLocation()) <= SelBegin;
         });
     const syntax::Token *SelLimit = std::partition_point(
         SelFirst, AllSpelledTokens.end(), [&](const syntax::Token &Tok) {
           return SM.getFileOffset(Tok.location()) < SelEnd;
         });
     auto Sel = llvm::makeArrayRef(SelFirst, SelLimit);
     // Find which of these are preprocessed to nothing and should be ignored.
-    std::vector<bool> PPIgnored(Sel.size(), false);
+    llvm::BitVector PPIgnored(Sel.size(), false);
     for (const syntax::TokenBuffer::Expansion &X :
          Buf.expansionsOverlapping(Sel)) {
       if (X.Expanded.empty()) {
         for (const syntax::Token &Tok : X.Spelled) {
           if (&Tok >= SelFirst && &Tok < SelLimit)
             PPIgnored[&Tok - SelFirst] = true;
         }
       }

clang-tools-extra/clangd/SourceCode.cpp

 #include "clang/Driver/Types.h"
 #include "clang/Format/Format.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Lex/Token.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Error.h"

 };
 // Scans C++ source code for constructs that change the visible namespaces.
 void parseNamespaceEvents(llvm::StringRef Code, const LangOptions &LangOpts,
                           llvm::function_ref<void(NamespaceEvent)> Callback) {
 
   // Stack of enclosing namespaces, e.g. {"clang", "clangd"}
   std::vector<std::string> Enclosing; // Contains e.g. "clang", "clangd"
   // Stack counts open braces. true if the brace opened a namespace.
-  std::vector<bool> BraceStack;
+  llvm::BitVector BraceStack;
 
   enum {
     Default,
     Namespace,          // just saw 'namespace'
     NamespaceName,      // just saw 'namespace' NSName
     Using,              // just saw 'using'
     UsingNamespace,     // just saw 'using namespace'
     UsingNamespaceName, // just saw 'using namespace' NSName

clang/include/clang/Lex/HeaderSearch.h

 #define LLVM_CLANG_LEX_HEADERSEARCH_H
 
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/DirectoryLookup.h"
 #include "clang/Lex/HeaderMap.h"
 #include "clang/Lex/ModuleMap.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Allocator.h"
public:
   /// Determine whether the given file is known to have ever been \#imported.
   bool hasFileBeenImported(const FileEntry *File) {
     const HeaderFileInfo *FI = getExistingFileInfo(File);
     return FI && FI->isImport;
   }
 
   /// Determine which HeaderSearchOptions::UserEntries have been successfully
   /// used so far and mark their index with 'true' in the resulting bit vector.
-  // TODO: Use llvm::BitVector instead.
-  std::vector<bool> computeUserEntryUsage() const;
+  llvm::BitVector computeUserEntryUsage() const;
   /// Return a bit vector of length \c SearchDirs.size() that indicates for each
   /// search directory whether it was used.
-  std::vector<bool> getSearchDirUsage() const;
+  llvm::BitVector getSearchDirUsage() const;
 
   /// This method returns a HeaderMap for the specified
   /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.
   const HeaderMap *CreateHeaderMap(const FileEntry *FE);
 
   /// Get filenames for all registered header maps.
   void getHeaderMapFileNames(SmallVectorImpl<std::string> &Names) const;
 

clang/lib/Format/UnwrappedLineParser.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEPARSER_H
 #define LLVM_CLANG_LIB_FORMAT_UNWRAPPEDLINEPARSER_H
 
 #include "FormatToken.h"
 #include "clang/Basic/IdentifierTable.h"
 #include "clang/Format/Format.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/Support/Regex.h"
 #include <stack>
 #include <vector>
 
 namespace clang {
 namespace format {
 
 struct UnwrappedLineNode;
private:
   // New unwrapped lines are added via CurrentLines.
   // Usually points to \c &Lines. While parsing a preprocessor directive when
   // there is an unfinished previous unwrapped line, will point to
   // \c &PreprocessorDirectives.
   SmallVectorImpl<UnwrappedLine> *CurrentLines;
 
   // We store for each line whether it must be a declaration depending on
   // whether we are in a compound statement or not.
-  std::vector<bool> DeclarationScopeStack;
+  llvm::BitVector DeclarationScopeStack;
 
   const FormatStyle &Style;
   const AdditionalKeywords &Keywords;
 
   llvm::Regex CommentPragmasRegex;
 
   FormatTokenSource *Tokens;
   UnwrappedLineConsumer &Callback;

clang/lib/Format/UnwrappedLineParser.cpp

public:
   // Position, and return the token at that position in the stream.
   virtual FormatToken *setPosition(unsigned Position) = 0;
 };
 
 namespace {
 
 class ScopedDeclarationState {
 public:
-  ScopedDeclarationState(UnwrappedLine &Line, std::vector<bool> &Stack,
+  ScopedDeclarationState(UnwrappedLine &Line, llvm::BitVector &Stack,
                          bool MustBeDeclaration)
       : Line(Line), Stack(Stack) {
     Line.MustBeDeclaration = MustBeDeclaration;
     Stack.push_back(MustBeDeclaration);
   }
   ~ScopedDeclarationState() {
     Stack.pop_back();
     if (!Stack.empty())
       Line.MustBeDeclaration = Stack.back();
     else
       Line.MustBeDeclaration = true;
   }
 
 private:
   UnwrappedLine &Line;
-  std::vector<bool> &Stack;
+  llvm::BitVector &Stack;
 };
 
 static bool isLineComment(const FormatToken &FormatTok) {
   return FormatTok.is(tok::comment) && !FormatTok.TokenText.startswith("/*");
 }
 
 // Checks if \p FormatTok is a line comment that continues the line comment
 // \p Previous. The original column of \p MinColumnToken is used to determine

clang/lib/Lex/HeaderSearch.cpp

 void HeaderSearch::AddSearchPath(const DirectoryLookup &dir, bool isAngled) {
   unsigned idx = isAngled ? SystemDirIdx : AngledDirIdx;
   SearchDirs.insert(SearchDirs.begin() + idx, storeSearchDir(dir));
   if (!isAngled)
     AngledDirIdx++;
   SystemDirIdx++;
 }
 
-std::vector<bool> HeaderSearch::computeUserEntryUsage() const {
-  std::vector<bool> UserEntryUsage(HSOpts->UserEntries.size());
+llvm::BitVector HeaderSearch::computeUserEntryUsage() const {
+  llvm::BitVector UserEntryUsage(HSOpts->UserEntries.size());
   for (const DirectoryLookup *SearchDir : UsedSearchDirs) {
     if (UsedSearchDirs.contains(SearchDir)) {
       auto UserEntryIdxIt = SearchDirToHSEntry.find(SearchDir);
       // Check whether this DirectoryLookup maps to a HeaderSearch::UserEntry.
       if (UserEntryIdxIt != SearchDirToHSEntry.end())
         UserEntryUsage[UserEntryIdxIt->second] = true;
     }
   }
   return UserEntryUsage;
 }
 
-std::vector<bool> HeaderSearch::getSearchDirUsage() const {
-  std::vector<bool> SearchDirUsage(SearchDirs.size());
+llvm::BitVector HeaderSearch::getSearchDirUsage() const {
+  llvm::BitVector SearchDirUsage(SearchDirs.size());
   for (unsigned I = 0, E = SearchDirs.size(); I < E; ++I)
     if (UsedSearchDirs.contains(SearchDirs[I]))
       SearchDirUsage[I] = true;
   return SearchDirUsage;
 }
 
 /// CreateHeaderMap - This method returns a HeaderMap for the specified
 /// FileEntry, uniquing them through the 'HeaderMaps' datastructure.

clang/lib/Serialization/ASTWriter.cpp

 }
 
 template <typename T>
 static StringRef bytes(const SmallVectorImpl<T> &v) {
   return StringRef(reinterpret_cast<const char*>(v.data()),
                          sizeof(T) * v.size());
 }
 
-static std::string bytes(const std::vector<bool> &V) {
+static std::string bytes(const llvm::BitVector &V) {
   std::string Str;
   Str.reserve(V.size() / 8);
   for (unsigned I = 0, E = V.size(); I < E;) {
     char Byte = 0;
     for (unsigned Bit = 0; Bit < 8 && I < E; ++Bit, ++I)
       Byte |= V[I] << Bit;
     Str += Byte;
   }

clang/lib/Tooling/Syntax/Tree.cpp

 //===- Tree.cpp -----------------------------------------------*- C++ -*-=====//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "clang/Tooling/Syntax/Tree.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Tooling/Syntax/Nodes.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 
 using namespace clang;
 
 namespace {
 static void traverse(const syntax::Node *N,
static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
   // Handle 'eof' separately, calling text() on it produces an empty string.
   if (Token->kind() == tok::eof)
     OS << "<eof>";
   else
     OS << Token->text(SM);
 }
 
 static void dumpNode(raw_ostream &OS, const syntax::Node *N,
-                     const SourceManager &SM, std::vector<bool> IndentMask) {
+                     const SourceManager &SM, llvm::BitVector IndentMask) {
   auto DumpExtraInfo = [&OS](const syntax::Node *N) {
     if (N->getRole() != syntax::NodeRole::Unknown)
       OS << " " << N->getRole();
     if (!N->isOriginal())
       OS << " synthesized";
     if (!N->canModify())
       OS << " unmodifiable";
   };

clang/unittests/Lex/HeaderSearchTest.cpp

TEST_F(HeaderSearchTest, SearchPathUsage) {
   setSearchDirs(/*QuotedDirs=*/{"/M0"}, /*AngledDirs=*/{"/M2", "/M3"});
   createModule("M0");
   createModule("M2");
   createModule("M3");
 
   {
     Module *M2 = Search.lookupModule("M2");
     EXPECT_NE(M2, nullptr);
-    EXPECT_EQ(Search.getSearchDirUsage(), (std::vector<bool>{0, 1, 0}));
-    EXPECT_EQ(Search.computeUserEntryUsage(), (std::vector<bool>{0, 1, 0}));
+    EXPECT_EQ(Search.getSearchDirUsage(), (llvm::BitVector{0, 1, 0}));
+    EXPECT_EQ(Search.computeUserEntryUsage(), (llvm::BitVector{0, 1, 0}));
   }
 
   addSearchDir("/M1");
   createModule("M1");
 
   {
     Module *M1 = Search.lookupModule("M1");
     EXPECT_NE(M1, nullptr);
-    EXPECT_EQ(Search.getSearchDirUsage(), (std::vector<bool>{0, 1, 1, 0}));
-    EXPECT_EQ(Search.computeUserEntryUsage(), (std::vector<bool>{0, 1, 0}));
+    EXPECT_EQ(Search.getSearchDirUsage(), (llvm::BitVector{0, 1, 1, 0}));
+    EXPECT_EQ(Search.computeUserEntryUsage(), (llvm::BitVector{0, 1, 0}));
   }
 }
 
 } // namespace
 } // namespace clang