[include-cleaner] Loose matching for verbatim headers

[sammccall]

Summary

A verbatim header usually corresponds to a symbol from a header with
a pragma "IWYU pragma: private, include <foo.h>".

Currently this is only satisfied if the main file contains exactly

#include <foo.h>

In practice this is too strict, we also want to allow

#include "path/to/foo.h"

so long as they resolve to the same file.

We cannot be 100% sure without doing IO, and we're not willing to do
that, but we can detect the common cases based on paths.

[sammccall]

clean up some leftovers

[sammccall]

(ping - also happy to send this to someone else if you prefer!)

[kadircet]

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h

207

maybe add a comment saying that these spellings are generated heuristically?

clang-tools-extra/include-cleaner/lib/Types.cpp

110–112

nit: return P.rtrim('/'); // only separator we can encounter is forward slash at this point.

129

nit: prefer early exit

137

i think this assumption breaks when we have an absolute include search path, which is a subdirectory of the CWD of file manager. as we might now have a resolved include which is relative, but a search path that'll never match a prefix of those includes.

i guess this is fine, as we're trying to heuristically match. but it would be useful to mention it here and add a unittest for that. (unless I am missing something and headersearch already normalizes such paths)

141

nit: prefer early exit

142–144

nit: auto Rel = llvm::StringRef(Path).drop_front(Parent.size()).ltrim('/'); // we already normalized the path and only have forward slashes.

171–173

i think we shouldn't look into alternate spellings if we've already found an exact spelling. we would be matching wrong headers for sure in those cases.

[sammccall]

address review comments

clang-tools-extra/include-cleaner/lib/Types.cpp

110–112

Oops, yes!
Kept the loop though to avoid making an extra copy, APIs are awkward

137

This is part of the contract of the function, pulled in the doc comment from D155878 and added a test for the cases that don't work.

171–173

I had it this way initially and changed my mind. Having the presence of some includes affect whether others match at all breaks an "obvious" part of the contract. (So obvious that I assumed it in the test ten minutes after deliberately breaking it). I wouldn't add a special case here unless there's some observed bad-results motivation for it.

we would be matching wrong headers for sure in those cases.

You could be including the same header under two paths (and in fact that's what this testcase is doing). I don't know why you would, but we also don't have real examples of this happening with *different* headers.

[kadircet]

clang-tools-extra/include-cleaner/lib/Types.cpp

171–173

You could be including the same header under two paths (and in fact that's what this testcase is doing). I don't know why you would

I do think it's better to diagnose one of those as unused in such a scenario. As tools like clang-format won't be able to de-duplicate those automatically.

but you're right about not having examples for alternate spellings resolving to different files, so I guess this is at least "safe" and we can change the behaviour if we encounter examples.

clang-tools-extra/include-cleaner/include/clang-include-cleaner/Types.h

 #include "clang/Basic/SourceLocation.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfoVariant.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 #include <memory>
+#include <string>
 #include <utility>
 #include <variant>
 #include <vector>
 
 namespace llvm {
 class raw_ostream;
 } // namespace llvm
 namespace clang {
struct Include {
   std::string quote() const;           // e.g. <vector>
 };
 llvm::raw_ostream &operator<<(llvm::raw_ostream &, const Include &);
 
 /// A container for all includes present in a file.
 /// Supports efficiently hit-testing Headers against Includes.
 class Includes {
 public:
+  /// Registers a directory on the include path (-I etc) from HeaderSearch.
+  /// This allows reasoning about equivalence of e.g. "path/a/b.h" and "a/b.h".
+  /// This must be called before calling add() in order to take effect.
+  ///
+  /// The paths may be relative or absolute, but the paths passed to
+  /// addSearchDirectory() and add() (that is: Include.Resolved->getName())
+  /// should be consistent, as they are compared lexically.
+  /// Generally, this is satisfied if you obtain paths through HeaderSearch
+  /// and FileEntries through PPCallbacks::IncludeDirective().
+  void addSearchDirectory(llvm::StringRef);
+
+  /// Registers an include directive seen in the main file.
+  ///
+  /// This should only be called after all search directories are added.
   void add(const Include &);
 
   /// All #includes seen, in the order they appear.
   llvm::ArrayRef<Include> all() const { return All; }
 
   /// Determine #includes that match a header (that provides a used symbol).
   ///
   /// Matching is based on the type of Header specified:
   ///  - for a physical file like /path/to/foo.h, we check Resolved
   ///  - for a logical file like <vector>, we check Spelled
   llvm::SmallVector<const Include *> match(Header H) const;
 
   /// Finds the include written on the specified line.
   const Include *atLine(unsigned OneBasedIndex) const;
 
 private:
+  llvm::StringSet<> SearchPath;
+
   std::vector<Include> All;
   // Lookup structures for match(), values are index into All.
   llvm::StringMap<llvm::SmallVector<unsigned>> BySpelling;
+  // Heuristic spellings that likely resolve to the given file.
+  llvm::StringMap<llvm::SmallVector<unsigned>> BySpellingAlternate;
   llvm::DenseMap<const FileEntry *, llvm::SmallVector<unsigned>> ByFile;
   llvm::DenseMap<unsigned, unsigned> ByLine;
 };
 
 } // namespace include_cleaner
 } // namespace clang
 
 namespace llvm {

clang-tools-extra/include-cleaner/lib/Record.cpp

 //===--- Record.cpp - Record compiler events ------------------------------===//
 //
 // 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-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
 #include "clang/AST/ASTConsumer.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclGroup.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/Specifiers.h"
 #include "clang/Frontend/CompilerInstance.h"
+#include "clang/Lex/DirectoryLookup.h"
 #include "clang/Lex/MacroInfo.h"
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Inclusions/HeaderAnalysis.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/StringRef.h"
 #include <memory>
 #include <utility>
+#include <vector>
 
 namespace clang::include_cleaner {
 namespace {
 
 class PPRecorder : public PPCallbacks {
 public:
   PPRecorder(RecordedPP &Recorded, const Preprocessor &PP)
-      : Recorded(Recorded), PP(PP), SM(PP.getSourceManager()) {}
+      : Recorded(Recorded), PP(PP), SM(PP.getSourceManager()) {
+    for (const auto &Dir : PP.getHeaderSearchInfo().search_dir_range())
+      if (Dir.getLookupType() == DirectoryLookup::LT_NormalDir)
+        Recorded.Includes.addSearchDirectory(Dir.getDirRef()->getName());
+  }
 
   void FileChanged(SourceLocation Loc, FileChangeReason Reason,
                    SrcMgr::CharacteristicKind FileType,
                    FileID PrevFID) override {
     Active = SM.isWrittenInMainFile(Loc);
   }
 
   void InclusionDirective(SourceLocation Hash, const Token &IncludeTok,

clang-tools-extra/include-cleaner/lib/Types.cpp

 //===--- Types.cpp --------------------------------------------------------===//
 //
 // 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-include-cleaner/Types.h"
 #include "TypesInternal.h"
 #include "clang/AST/Decl.h"
 #include "clang/Basic/FileEntry.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
+#include <vector>
 
 namespace clang::include_cleaner {
 
 std::string Symbol::name() const {
   switch (kind()) {
   case include_cleaner::Symbol::Macro:
     return macro().Name->getName().str();
   case include_cleaner::Symbol::Declaration:

 }
 
 std::string Include::quote() const {
   return (llvm::StringRef(Angled ? "<" : "\"") + Spelled +
           (Angled ? ">" : "\""))
       .str();
 }
 
+static llvm::SmallString<128> normalizePath(llvm::StringRef Path) {
+  namespace path = llvm::sys::path;
+
+  llvm::SmallString<128> P = Path;
+  path::remove_dots(P, /*remove_dot_dot=*/true);
+  path::native(P, path::Style::posix);
+  while (!P.empty() && P.back() == '/')
+    P.pop_back();
+  return P;
+}
+
+void Includes::addSearchDirectory(llvm::StringRef Path) {
+  SearchPath.try_emplace(normalizePath(Path));
+}
+
 void Includes::add(const Include &I) {
+  namespace path = llvm::sys::path;
+
   unsigned Index = All.size();
   All.push_back(I);
   auto BySpellingIt = BySpelling.try_emplace(I.Spelled).first;
   All.back().Spelled = BySpellingIt->first(); // Now we own the backing string.
 
   BySpellingIt->second.push_back(Index);
-  if (I.Resolved)
-    ByFile[&I.Resolved->getFileEntry()].push_back(Index);
   ByLine[I.Line] = Index;
+
+  if (!I.Resolved)
+    return;
+  ByFile[&I.Resolved->getFileEntry()].push_back(Index);
+
+  // While verbatim headers ideally should match #include spelling exactly,
+  // we want to be tolerant of different spellings of the same file.
+  //
+  // If the search path includes "/a/b" and "/a/b/c/d",
+  // verbatim "e/f" should match (spelled=c/d/e/f, resolved=/a/b/c/d/e/f).
+  // We assume entry's (normalized) name will match the search dirs.
+  auto Path = normalizePath(I.Resolved->getName());
+  for (llvm::StringRef Parent = path::parent_path(Path); !Parent.empty();
+       Parent = path::parent_path(Parent)) {
+    if (!SearchPath.contains(Parent))
+      continue;
+    llvm::StringRef Rel =
+        llvm::StringRef(Path).drop_front(Parent.size()).ltrim('/');
+    BySpellingAlternate[Rel].push_back(Index);
+  }
 }
 
 const Include *Includes::atLine(unsigned OneBasedIndex) const {
   auto It = ByLine.find(OneBasedIndex);
   return (It == ByLine.end()) ? nullptr : &All[It->second];
 }
 
 llvm::SmallVector<const Include *> Includes::match(Header H) const {
   llvm::SmallVector<const Include *> Result;
   switch (H.kind()) {
   case Header::Physical:
     for (unsigned I : ByFile.lookup(H.physical()))
       Result.push_back(&All[I]);
     break;
   case Header::Standard:
     for (unsigned I : BySpelling.lookup(H.standard().name().trim("<>")))
       Result.push_back(&All[I]);
     break;
-  case Header::Verbatim:
-    for (unsigned I : BySpelling.lookup(H.verbatim().trim("\"<>")))
+  case Header::Verbatim: {
+    llvm::StringRef Spelling = H.verbatim().trim("\"<>");
+    for (unsigned I : BySpelling.lookup(Spelling))
+      Result.push_back(&All[I]);
+    for (unsigned I : BySpellingAlternate.lookup(Spelling))
+      if (!llvm::is_contained(Result, &All[I]))
         Result.push_back(&All[I]);
     break;
   }
+  }
   return Result;
 }
 
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const SymbolLocation &S) {
   switch (S.kind()) {
   case SymbolLocation::Physical:
     // We can't decode the Location without SourceManager. Its raw
     // representation isn't completely useless (and distinguishes

clang-tools-extra/include-cleaner/unittests/TypesTest.cpp

 //===-- RecordTest.cpp ----------------------------------------------------===//
 //
 // 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-include-cleaner/Types.h"
 #include "clang/Basic/FileManager.h"
+#include "clang/Basic/FileSystemOptions.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "llvm/ADT/IntrusiveRefCntPtr.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang::include_cleaner {
 namespace {
 using testing::ElementsAre;
+using testing::IsEmpty;
+using testing::UnorderedElementsAre;
 
 // Matches an Include* on the specified line;
 MATCHER_P(line, N, "") { return arg->Line == (unsigned)N; }
 
 TEST(RecordedIncludesTest, Match) {
   // We're using synthetic data, but need a FileManager to obtain FileEntry*s.
   // Ensure it doesn't do any actual IO.
   auto FS = llvm::makeIntrusiveRefCnt<llvm::vfs::InMemoryFileSystem>();
TEST(RecordedIncludesTest, Match) {
 
   EXPECT_THAT(Inc.match(&A.getFileEntry()), ElementsAre(line(1), line(2)));
   EXPECT_THAT(Inc.match(&B.getFileEntry()),
               ElementsAre(line(3), line(4), line(5)));
   EXPECT_THAT(Inc.match(*tooling::stdlib::Header::named("<vector>")),
               ElementsAre(line(4), line(5)));
 }
 
+TEST(RecordedIncludesTest, MatchVerbatim) {
+  auto FS = llvm::makeIntrusiveRefCnt<llvm::vfs::InMemoryFileSystem>();
+  FileManager FM(FileSystemOptions{});
+  Includes Inc;
+
+  // By default, a verbatim header only matches includes with the same spelling.
+  auto Foo =
+      FM.getVirtualFileRef("repo/lib/include/rel/foo.h", /*Size=*/0, time_t{});
+  Inc.add(Include{"lib/include/rel/foo.h", Foo, SourceLocation(), 1});
+  Inc.add(Include{"rel/foo.h", Foo, SourceLocation(), 2});
+  EXPECT_THAT(Inc.match(Header("<rel/foo.h>")), ElementsAre(line(2)));
+
+  // A verbatim header can match another spelling if the search path
+  // suggests it's equivalent.
+  auto Bar =
+      FM.getVirtualFileRef("repo/lib/include/rel/bar.h", /*Size=*/0, time_t{});
+  Inc.addSearchDirectory("repo/");
+  Inc.addSearchDirectory("repo/lib/include");
+  Inc.add(Include{"lib/include/rel/bar.h", Bar, SourceLocation(), 3});
+  Inc.add(Include{"rel/bar.h", Bar, SourceLocation(), 4});
+  EXPECT_THAT(Inc.match(Header("<rel/bar.h>")),
+              UnorderedElementsAre(line(3), line(4)));
+
+  // We don't apply this logic to system headers, though.
+  auto Vector =
+      FM.getVirtualFileRef("repo/lib/include/vector", /*Size=*/0, time_t{});
+  Inc.add(Include{"lib/include/vector", Vector, SourceLocation(), 5});
+  EXPECT_THAT(Inc.match(Header(*tooling::stdlib::Header::named("<vector>"))),
+              IsEmpty());
+}
+
+TEST(RecordedIncludesTest, MatchVerbatimMixedAbsoluteRelative) {
+  auto FS = llvm::makeIntrusiveRefCnt<llvm::vfs::InMemoryFileSystem>();
+  FS->setCurrentWorkingDirectory("/working");
+  FileManager FM(FileSystemOptions{});
+  Includes Inc;
+
+  auto Foo =
+      FM.getVirtualFileRef("/working/rel1/rel2/foo.h", /*Size=*/0, time_t{});
+  Inc.addSearchDirectory("rel1");
+  Inc.addSearchDirectory("rel1/rel2");
+  Inc.add(Include{"rel2/foo.h", Foo, SourceLocation(), 1});
+  EXPECT_THAT(Inc.match(Header("<foo.h>")), IsEmpty());
+
+  Inc = Includes{};
+  auto Bar = FM.getVirtualFileRef("rel1/rel2/bar.h", /*Size=*/0, time_t{});
+  Inc.addSearchDirectory("/working/rel1");
+  Inc.addSearchDirectory("/working/rel1/rel2");
+  Inc.add(Include{"rel2/bar.h", Bar, SourceLocation(), 1});
+  EXPECT_THAT(Inc.match(Header("<bar.h>")), IsEmpty());
+}
+
 } // namespace
 } // namespace clang::include_cleaner