Move the BySpelling map to IncludeStructure.

[kadircet]

clang-tools-extra/clangd/Headers.h

166

instead of building this on-demand, what about building it as we're collecting directives around https://github.com/llvm/llvm-project/blob/main/clang-tools-extra/clangd/Headers.cpp#L52 ?

afterwards we can just have a lookup function exposed here, that returns an ArrayRef<HeaderID> ?

[VitaNuo]

Address review comments.

[VitaNuo]

Expose API for lookup instead of retrieving the whole map.

[VitaNuo]

Thanks for review!

clang-tools-extra/clangd/Headers.h

166

That's a great idea. I was thinking about this, but didn't know where to put it, so I thought if it was possible, you'd point out in review ;-)
Thanks!

[kadircet]

clang-tools-extra/clangd/Headers.cpp

76

right now we're only storing "resolved" includes from the main file and not all, this is creating a discrepancy between the view one gets through MainFileIncludes and through this map.
in addition to that only storing HeaderID gets the job done for IncludeCleaner, but won't really help anyone that wants to match main file includes apart from that (there's no easy way to go from a HeaderID to an Inclusion).

so instead of storing the HeaderID in the map values, we can actually store indexes into MainFileIncludes. later on during the lookup, we can build a SmallVector<Inclusion *> that contains pointers to the relevant includes. WDYT?

clang-tools-extra/clangd/Headers.h

166

what about renaming lookupHeaderIDsBySpelling to mainFileIncludesWithSpelling. with a comment explaining Returns includes inside the main file with the given Spelling. Spelling should include brackets or quotes, e.g. <foo>.

[kadircet]

oh forgot to mention, could you also please add some tests into llvm-project/clang-tools-extra/clangd/unittests/HeadersTests.cpp ?

[VitaNuo]

Address review comments.

[VitaNuo]

Thanks for the review!

clang-tools-extra/clangd/Headers.cpp

76

Ok sure.

[kadircet]

clang-tools-extra/clangd/Headers.h

167

we're still returning just the HeaderID, the suggestion was to return llvm::SmallVector<Inclusion*> so that applications can work with other information available in the Inclusion. we also won't have any requirements around include being resolved that way. the application should figure out what to do if HeaderID is missing.

also can you move this function body to source file instead?

[VitaNuo]

Address comments

[VitaNuo]

Thanks for the comments!

[VitaNuo]

Move to source file.

[kadircet]

clang-tools-extra/clangd/Headers.cpp

302

nit:

llvm::SmallVector<Inclusion*> Includes;
for (auto Idx : MainFileIncludesBySpelling.lookup(Spelling))
  Includes.push_back(&MainFileIncludes[Idx]);
return Includes;

clang-tools-extra/clangd/Headers.h

167

almost, but not right. we're returning copies of Inclusions here, not pointers to Inclusions inside the main file. the suggested signature was llvm::SmallVector<Inclusion*> any reason for returning by value?

clang-tools-extra/clangd/IncludeCleaner.cpp

516

nit:

if(!Inc.HeaderID.has_value())
  continue;
Used.insert(static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID));

[VitaNuo]

Address review comments.

[VitaNuo]

Thanks for the comments!

clang-tools-extra/clangd/Headers.cpp

302

But lookup will return 0 if it doesn't find the spelling in the map (default value of int). And at the same time 0 is a valid index. Isn't that just wrong?

clang-tools-extra/clangd/Headers.h

167

Sure, thanks. No particular reason.

[kadircet]

clang-tools-extra/clangd/Headers.cpp

302

MainFileIncludesBySpelling is a map with values of type vector, not int. hence it'll be an empty vector, not 0.

[VitaNuo]

Address review comments.

[VitaNuo]

clang-tools-extra/clangd/Headers.cpp

302

Oh right. Sorry I guess I got confused.

[kadircet]

thanks (both for the patch and for bearing with me)!

clang-tools-extra/clangd/Headers.h

 #include "clang/Format/Format.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/FileSystem/UniqueID.h"
 #include <optional>
 #include <string>
 
 namespace clang {
StringRef getRealPath(HeaderID ID) const {
     assert(static_cast<unsigned>(ID) <= RealPathNames.size());
     return RealPathNames[static_cast<unsigned>(ID)];
   }
 
   bool isSelfContained(HeaderID ID) const {
     return !NonSelfContained.contains(ID);
   }
 
-  bool hasIWYUExport(HeaderID ID) const {
-    return HasIWYUExport.contains(ID);
-  }
+  bool hasIWYUExport(HeaderID ID) const { return HasIWYUExport.contains(ID); }
 
   // Return all transitively reachable files.
   llvm::ArrayRef<std::string> allHeaders() const { return RealPathNames; }
 
+  llvm::SmallVector<HeaderID>
+  lookupHeaderIDsBySpelling(llvm::StringRef Spelling) const {
+    return MainFileIncludesBySpelling.lookup(Spelling);
+  }
+
   // Return all transitively reachable files, and their minimum include depth.
   // All transitive includes (absolute paths), with their minimum include depth.
   // Root --> 0, #included file --> 1, etc.
   // Root is the ID of the header being visited first.
   llvm::DenseMap<HeaderID, unsigned>
   includeDepth(HeaderID Root = MainFileID) const;
 
   // Maps HeaderID to the ids of the files included from it.
private:
   // the preamble.
   llvm::DenseMap<llvm::sys::fs::UniqueID, HeaderID> UIDToIndex;
   // Contains HeaderIDs of all non self-contained entries in the
   // IncludeStructure.
   llvm::DenseSet<HeaderID> NonSelfContained;
   // Contains a set of headers that have either "IWYU pragma: export" or "IWYU
   // pragma: begin_exports".
   llvm::DenseSet<HeaderID> HasIWYUExport;
+
+  // Maps written includes to headers IDs for easier lookup by spelling.
+  llvm::StringMap<llvm::SmallVector<IncludeStructure::HeaderID>>
+      MainFileIncludesBySpelling;
 };
 
 // Calculates insertion edit for including a new header in a file.
 class IncludeInserter {
 public:
   // If \p HeaderSearchInfo is nullptr (e.g. when compile command is
   // infeasible), this will only try to insert verbatim headers, and
   // include path of non-verbatim header will not be shortened.

clang-tools-extra/clangd/Headers.cpp

if (isInsideMainFile(HashLoc, SM)) {
         Inc.HeaderID = static_cast<unsigned>(HID);
         if (IsAngled)
           if (auto StdlibHeader = tooling::stdlib::Header::named(Inc.Written)) {
             auto &IDs = Out->StdlibHeaders[*StdlibHeader];
             // Few physical files for one stdlib header name, linear scan is ok.
             if (!llvm::is_contained(IDs, HID))
               IDs.push_back(HID);
           }
+        Out->MainFileIncludesBySpelling.try_emplace(Inc.Written)
+            .first->second.push_back(static_cast<HeaderID>(*Inc.HeaderID));
       }
     }
 
     // Record include graph (not just for main-file includes)
     if (File) {
       auto IncludingFileEntry = SM.getFileEntryRefForID(SM.getFileID(HashLoc));
       if (!IncludingFileEntry) {
         assert(SM.getBufferName(HashLoc).startswith("<") &&
for (unsigned Level = 1; !CurrentLevel.empty(); ++Level) {
     }
   }
   return Result;
 }
 
 void IncludeInserter::addExisting(const Inclusion &Inc) {
   IncludedHeaders.insert(Inc.Written);
   if (!Inc.Resolved.empty())
     IncludedHeaders.insert(Inc.Resolved);
 }
 
 /// FIXME(ioeric): we might not want to insert an absolute include path if the
 /// path is not shortened.
 bool IncludeInserter::shouldInsertInclude(
     PathRef DeclaringHeader, const HeaderFile &InsertedHeader) const {
   assert(InsertedHeader.valid());
   if (!HeaderSearchInfo && !InsertedHeader.Verbatim)

clang-tools-extra/clangd/IncludeCleaner.cpp

bool VisitCXXConstructExpr(CXXConstructExpr *CCE) {
     add(CCE->getConstructor());
     return true;
   }
 
   bool VisitTemplateSpecializationType(TemplateSpecializationType *TST) {
     // Using templateName case is handled by the override TraverseTemplateName.
     if (TST->getTemplateName().getKind() == TemplateName::UsingTemplate)
       return true;
-    add(TST->getAsCXXRecordDecl());                  // Specialization
+    add(TST->getAsCXXRecordDecl()); // Specialization
     return true;
   }
 
   // There is no VisitTemplateName in RAV, thus we override the Traverse version
   // to handle the Using TemplateName case.
   bool TraverseTemplateName(TemplateName TN) {
     VisitTemplateName(TN);
     return Base::TraverseTemplateName(TN);
std::vector<const Inclusion *> computeUnusedIncludes(ParsedAST &AST) {
   auto Refs = findReferencedLocations(AST);
   auto ReferencedFiles =
       findReferencedFiles(Refs, AST.getIncludeStructure(),
                           AST.getCanonicalIncludes(), AST.getSourceManager());
   auto ReferencedHeaders =
       translateToHeaderIDs(ReferencedFiles, AST.getIncludeStructure(), SM);
   return getUnused(AST, ReferencedHeaders, ReferencedFiles.SpelledUmbrellas);
 }
-std::vector<const Inclusion *> computeUnusedIncludesExperimental(ParsedAST &AST) {
-   const auto &SM = AST.getSourceManager();
-   const auto &Includes = AST.getIncludeStructure();
-   // FIXME: this map should probably be in IncludeStructure.
-   llvm::StringMap<llvm::SmallVector<IncludeStructure::HeaderID>> BySpelling;
-   for (const auto &Inc : Includes.MainFileIncludes) {
-    if (Inc.HeaderID)
-      BySpelling.try_emplace(Inc.Written)
-          .first->second.push_back(
-              static_cast<IncludeStructure::HeaderID>(*Inc.HeaderID));
-   }
-   // FIXME: !!this is a hacky way to collect macro references.
-   std::vector<include_cleaner::SymbolReference> Macros;
-    auto& PP = AST.getPreprocessor();
-   for (const syntax::Token &Tok :
-        AST.getTokens().spelledTokens(SM.getMainFileID())) {
+std::vector<const Inclusion *>
+computeUnusedIncludesExperimental(ParsedAST &AST) {
+
+  auto &PP = AST.getPreprocessor();
     auto Macro = locateMacroAt(Tok, PP);
     if (!Macro)
       continue;
     if (auto DefLoc = Macro->Info->getDefinitionLoc(); DefLoc.isValid())
       Macros.push_back(
           {Tok.location(),
            include_cleaner::Macro{/*Name=*/PP.getIdentifierInfo(Tok.text(SM)),
                                   DefLoc},
            include_cleaner::RefType::Explicit});
-   }
-   llvm::DenseSet<IncludeStructure::HeaderID> Used;
-   include_cleaner::walkUsed(
-       AST.getLocalTopLevelDecls(), /*MacroRefs=*/Macros,
-       AST.getPragmaIncludes(), SM,
-       [&](const include_cleaner::SymbolReference &Ref,
-           llvm::ArrayRef<include_cleaner::Header> Providers) {
-         for (const auto &H : Providers) {
-           switch (H.kind()) {
-           case include_cleaner::Header::Physical:
-             if (auto HeaderID = Includes.getID(H.physical()))
-               Used.insert(*HeaderID);
-             break;
-           case include_cleaner::Header::Standard:
-             for (auto HeaderID : Includes.StdlibHeaders.lookup(H.standard()))
-               Used.insert(HeaderID);
-             break;
-           case include_cleaner::Header::Verbatim:
-             for (auto HeaderID : BySpelling.lookup(H.verbatim()))
-               Used.insert(HeaderID);
-             break;
-           }
-         }
-       });
-   return getUnused(AST, Used, /*ReferencedPublicHeaders*/{});
+            for (auto HeaderID :
+                 Includes.lookupHeaderIDsBySpelling(H.verbatim()))
+  return getUnused(AST, Used, /*ReferencedPublicHeaders*/ {});
 }
 
 std::vector<Diag> issueUnusedIncludesDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   const Config &Cfg = Config::current();
   if (Cfg.Diagnostics.UnusedIncludes == Config::UnusedIncludesPolicy::None ||
       Cfg.Diagnostics.SuppressAll ||
       Cfg.Diagnostics.Suppress.contains("unused-includes"))